Диссертация (1150736), страница 30
Текст из файла (страница 30)
Другим способом переиспользования ресурсов является конвейеризация.A.16Отключение питанияВ состоянии простоя токи утечки являются основной причиной энергопотребления. Отключение схемы от питания исключает утечку и приводитк экономии энергии. Это достигается с помощью мощных транзисторов, которые отключают питание остальной схемы в режиме простоя. Эти транзисторы размещаются на шине питания, и иногда на шине заземления.
Транзисторы управляются высоким уровнем сигнала “сон”, который неактивен врабочем режиме. Во время простоя управляющая логика схемы выставляетсигнал “сон”, что отключает питание от остальной части схемы.Ограниченное сопротивление отключающих транзисторов приводит к шуму на шине питания в схемах, питанием которых они управляют. Чтобыуменьшить шум на шине питания, эти транзисторы должны иметь низкоесопротивление и, следовательно, большой размер и большое время переключения. Большой размер отключающих транзисторов приводит к увеличениюплощади кристалла.
Большое время переключения приводит к длительномупереходному процессу, превышающему один такт, что усложняет управляющую схему.В отличие от отключения тактирования, отключение питания приводит кпотере данных. Поэтому оно может применяться только для схем, поддерживающих эту возможность. Для сохранения необходимых в дальнейшей работе данных должна использоваться энергонезависимая или не отключаемая отпитания память. Использование дополнительной памяти приводит к дополнительным накладным расходам на копирование и хранение данных.187Другая возможность заключается в подключении к буферным регистрамв схеме неотключаемого питания.
При этом состояние регистров не теряется.Наличие двух параллельных схем питания внутри одного модуля усложняетразводку схемы на кристалле и приводит к существенным накладным расходам.A.17Динамическое управление частотой и напряжением питанияДинамическое управление частотой и напряжением питания одновременно изменяет оба параметра в зависимости от вычислительной нагрузки дляминимизации энергопотребления Этот метод обычно используется в многоядерных процессорах.
Операционная система отслеживает загрузку ядер и взависимости от загрузки и крайних сроков заданий повышает или понижает напряжение и частоту для обеспечения требований по производительности. Поскольку метод применим только за пределами области линейного масштабирования мощности от частоты, его применение для малопотребляющихсхем ограничено.A.18Использование параллельных алгоритмовВо многих случаях более эффективным способом распараллеливания посравнению с модификацией исходного алгоритма является применение других, более пригодных для распараллеливания алгоритмов. Распараллеливаниеможет достигаться за счет базовых операций.
Например при замене побитового вычисления в схеме CORDIC на полиномиальную аппроксимацию, итеративное суммирование заменяется параллельной реализацией умножения. Также распараллеливание может достигаться изменением порядка вычислений засчет устранения ложных зависимостей операций через память или промежуточные данные. Использование параллельных алгоритмов может приводить кувеличению вычислительной сложности по сравнению с последовательнымалгоритмом.188Приложение BПолиномиальнаяинтерполяцияКратко изложим необходимые нам результаты из теории интерполяции.B.1Интерполяционные полиномыБудем считать, что фиксированы различные между собой числа 0 , 1 , .
. .и соответствующие значения функции (0 ), (1 ), . . .Определение 16 Разностными отношениями первого порядка называютсячисла (+1 ) − ( ), = 0, 1, . . .+1 − Разностные отношения произвольного порядка n>1 определяются итера ( , +1 ) =тивно: ( , +1 , . . . , + ) = (+1 , . . . , + ) − ( , . .
. , +−1 ).+ − Лемма 29 ( ) = (0 )+( −0 ) (0 , 1 )+. . .+( −0 ) . . . ( −−1 ) (0 , 1 , . . . , ).189Доказательство. Данное равенство можно преобразовать следующим образом: ( ) − (0 )11− (0 , 1 ))− (0 , 1 , 2 ))− ... − 0 − 1 − 21= (0 , 1 , . . . , ),− (0 , 1 , . . . , −1 )) − −1(. . . ((что следует из определения разностных отношений и из возможности переставлять аргументы этих отношений.Определение 17 Назовем следующие полиномы фундаментальными полиномами системы узлов (0 , . .
. , ):() () =,( − ) ′ ( )() =∏︁( − ).=0Теорема 16 Существует и единственен полином степени не выше , удовлетворяющий интерполяционным данным (0 , (0 )), . . ., ( , ( )). Он может быть задан формулой Лагранжа () =∑︁ () ( ),=0или формулой Ньютона () = (0 ) + ( − 0 ) (0 , 1 ) + . . . + ( − 0 ) . . . ( − −1 ) (0 , 1 , . . . , ).Доказательство.1. Докажем, что полином Лагранжа интерполяционный.
Поскольку∏︁()=( − ), − =0,̸=то при → это значение стремится к ′ ( ). Кроме того, эта функция имееткорни во всех узлах , 0 ≤ ≤ , кроме узла . Поэтому в формуле Лагранжапри = в сумме остается только одно слагаемое при = . Это слагаемоесовпадает с ( ), что доказывает требуемое свойство интерполяции.В формуле Ньютона при = получаем значение ( ) по лемме 29.190Единственность интерполяционного полинома доказывается от противного. Пусть 1 () и 2 () – два интерполяционных полинома степени не выше.
Тогда полином 1 () − 2 () имеет степень не выше и имеет по крайней мере + 1 корней, а именно, 0 , . . ., . Следовательно, этот полиномтождественно равен нулю.B.2Погрешность интерполяционных полиномовПусть заданы различные числа 0 , 1 , . . ., , значения функции в них (0 ), (1 ), . . ., ( ) и соответствующий интерполяционный полином ().Требуется оценить погрешность интерполяции () = () − () для точек, отличных от узлов интерполяции.Лемма 30() = () (0 , 1 , .
. . , , ),где () = ( − 0 ) . . . ( − ).Доказательство. Выберем точку , отличную от всех узлов интерполяции.Добавим точку к набору узлов интерполяции вместе со значением (). Кполученному набору из + 2 исходных данных применим лемму 29: () = (0 ) + ( − 0 ) (0 , 1 ) + . . . + ( − 0 ) . .
. ( − −1 ) (0 , 1 , . . . , )+( − 0 ) . . . ( − −1 )( − ) (0 , 1 , . . . , , ).Но сумма слагаемых в правой части, кроме последнего, совпадает с интерполяционным полиномом в форме Ньютона. Отсюда следует утверждение леммы.Такимобразом,формыпредставленияразностногоотношения (0 , 1 , . . . , , ) можно использовать для оценки погрешности интерполяции.191Лемма 31 Пусть узлы 0 , 1 , . . ., лежат на отрезке [, ] и функция имеет производную порядка на этом отрезке.
Тогда∫︁ 1∫︁ 1 (0 , 1 , . . . , ) =12 . . .00(︃)︃∫︁ −1∑︁ () 0 + ( − −1 ) .0=1Доказательство. Аргумент функции () лежит на промежутке [, ], таккак он равен следующей выпуклой комбинации чисел :0 +∑︁ ( − −1 ) = (1 − 1 )0 + (2 − 1 )1 + . . . + (−1 − )−1 + .=1Поэтому функция () определена в области интегрирования.Для = 1 утверждение очевидно. Пусть оно доказано для − 1. Интегрируя один раз правую часть в утверждении теоремы, получим∫︁ 1∫︁ 1∫︁ −2112 . . .−1 − −1 000(︃(︃)︃−1∑︁ (−1) 0 + ( − −1 ) + −1 ( − −1 )=1(︃− (−1) 0 +−1∑︁)︃ )︃ ( − −1 )=11( (0 , 1 , . . . , −2 , ) − (0 , 1 , . . .
, −2 , −1 )) − −11=( (0 , 1 , . . . , −2 , ) − (−1 , 0 , 1 , . . . , −2 )) − −1= (0 , 1 , . . . , ).=В предпоследнем равенстве была использована симметричность функции (0 , 1 , . . . , ) относительно своих аргументов, а последнее равенство естьопределение (0 , 1 , . . . , ).Лемма 32 Пусть узлы 0 , 1 , . .
., лежат на отрезке [, ] и функция имеет непрерывную производную порядка на этом отрезке. Тогда существуеттакая точка ∈ [, ], что (0 , 1 , . . . , ) =1921 () ().!Доказательство. Воспользуемся утверждением леммы 31. Посколькуфункция () () предполагается непрерывной, то значение интеграла равнопроизведению значения этой функции в некоторой средней точке области интегрирования на объем этой области.
Объем равен∫︁ 1∫︁ 1∫︁ −1112 . . . = .!000Теорема 17 Пусть функция имеет непрерывную производную порядка + 1на отрезке [, ], содержащем все узлы интерполяции, которые предполагаются различными. Тогда при ∈ [, ]1∫︁() = ()1∫︁10∫︁2 . . .0+1 (+1)[0 +0+1∑︁ ( − −1 )],=1где +1 = , () = ( − 0 ) . . . ( − ).Кроме того, существует такая точка на [a,b], что() =() (+1)().( + 1)!Доказательство.
Рассмотрим выражение для погрешности интерполяциичерез разностные отношения из леммы 30 и воспользуемся теоремами 31 и 32для выражения разностных отношений.Функции, у которых существуют и ограничены производные старших порядков, обычно называют гладкими. Для таких функций значения в промежутках между узлами интерполяции не могут быть произвольными, посколькускорость изменения функции ограничена. Поэтому погрешность интерполяции может быть относительно небольшой.Рассмотрим (, [, ]) - класс всех функций на отрезке [, ], у которыхпроизводная порядка ограничена заданным числом:| () ()| ≤ .Это довольно широкий класс функций, допускающий интерполяцию любых n исходных данных (так как у интерполяционного полинома степень равна − 1, и поэтому () () = 0).193B.3Интерполирование производныхПусть в узлах интерполяции 1 , 2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
