Автореферат (1150735), страница 2
Текст из файла (страница 2)
Вработе [5] автор выполнял математическое моделирование.6Объем и структура работы. Полный объем диссертации — 209 страниц. Основной текст диссертации — 167 страниц. Диссертация состоитиз введения, четырех глав и заключения с 9 рисунками, 14 таблицами и5 приложениями. Список литературы содержит 85 наименований.Содержание работыВо введении обосновывается актуальность исследований в областиразработки алгоритмов энергоэффективных вычислений.Первая глава посвящена анализу различных факторов, влияющих наэнергоэффективность и удобство применения вычислительных блоков при построении малопотребляющих специализированных полупроводниковых схем,а также анализу методов оптимизации энергопотребления.
Также в главерассматривается влияние на энергопотребление других факторов, таких, какархитектура памяти, представление числовых данных, архитектура процессора и операционной системы, использование языков управляемого выполнения (Java, C# и т.п.), моделей параллельных вычислений и средств автоматической верификации. Мощность вычислительного блока складываетсяиз статической мощности неотключаемых от питания компонент и мощности компонент с управляемым питанием.
К неотключаемым компонентамотносятся память кода и память состояния, остальные компоненты можноотключать на время простоя. К отключаемым компонентам относятся вычислительные устройства, память промежуточных данных и постоянное запоминающее устройство. Пусть алгоритм выполняется на вычислительном блокес процессоров. Минимизируем потребляемую мощность по .Алгоритм характеризуется постоянными параметрами: - вычислительная сложность алгоритма, в количестве элементарных операций в секунду; - нераспараллеливаемая доля алгоритма.Вычислительный блок характеризуется постоянными параметрами: 0- количество вентилей в неотключаемой части; 1 - количество вентилей в^2 - количество вентиотключаемой части без вычислительных компонент; лей в последовательной реализации вычислительных компонент блока; тактовая частота.Количество вентилей в вычислительных компонентах блока опреде^2 .
Тогда мощность вычислительного блока на участкеляется как 2 = линейного роста от частоты можно оценить как = 0 (0 + (1 + 2 )) = 1 (1 + 2 )7 = + = 0 (0 + (1 + 2 )) + 1 (1 + 2 )где - потери мощности от токов утечки, - динамическая мощность, 0 ,1 - постоянные коэффициенты, а = () ≤ 1 - скважность или отношениевремени вычислений к общему времени, включающему простой.Функцию () заменяют на функцию ускорения от параллелизма (),которую можно описать с помощью закона Амдала [Amdahl, 1967].() =,() = 0 0 + (0 / + 1 )() =.1 + ( − 1)^ 2 + 1,()arg min = 0 ., ≤0Лемма 1 Мощность достигает минимума по при значении)︃(︃ √︃1 (1 − ).0 = arg min = max 1,^2 При этом минимальная мощность имеет значение(︂)︂√︁^2 + 1 + 2 1 ^2 (1 − ) .min = 0 0 + (0 /0 + 1 ) (1 − )Функция мощности зависит от параллелизма и размера задачи : (, ) = 0 0 () + ()(0 / + 1 )^2 + 1 (),(, )где величины 0 (), 1 () зависят от размера памяти, который обычно рас^2 не зависит от , поскольку алготет с ростом размера задачи.
Величина ритм вычислений не меняется.Используем закон Густафсона-Барсиса [Gustafson, 1988]:(, ) = (1 − ) + .Лемма 2 Пусть размер памяти 0 (), 1 () и сложность алгоритма() растут линейно по размеру задачи. Тогда (1, ) = (2 ), а минимальная мощность min () = () при → ∞.Во второй главе изучаются способы расчёта элементарных функцийпри ограничениях на общий объём памяти вычислительного блока. Задачасводится к целочисленному программированию и оптимальной равномернойаппроксимации многозвенными квазисплайнами.8Функция на отрезке Δ разбивается на сегменты, и внутри каждогосегмента аппроксимируется полиномом.
В памяти хранятся параметры, длярасчёта значений полиномов по всем сегментам, сведённые в таблицу. Требуется минимизировать длину таблицы в битах при равномерном ограничениина точность расчёта значений функции.Пусть длины всех сегментов полиномиальной интерполяции равны 1.Тогда границы сегментов полиномиальной интерполяции есть целые числа, = , 0 ≤ < 20 , где 20 — количество звеньев почти гладкого квазисплайна. Квазисплайн будем обозначать { ()}, где () - полином -го звена. Егокоэффициенты ∈ , где — множество двоичных дробей с дробнойчастью из цифр.В пределах каждого звена выберем сетку отсчётов ¯ = 2−2 при0 ≤ < 2−2 с шагом = 2−2 .На промежутке 0 = [−1, 1] выберем интерполяционных узлов ипостроим по ним фундаментальные полиномы () = ()/(( − ) ′ ( )).Числом Лебега назовём∑︁(), = sup| ()|.∈[−1,1] =1Теорема 1 Пусть > 2, | ( ) ()| ≤ на [0, 20 ] и > 0 — заданнаяточность аппроксимации.
Определим(︂)︂ (︂)︂−1 2 ,2 (0 )2¯ = −1+.8( − 2)!2Пусть существует решение следующей смешанной целочисленнойзадачи линейного программирования относительно коэффициентов почти гладкого квазисплайна { ()} на отрезке [0, 20 ] при ограничении напредставление ∈ :⎧∑︀ ∑︀20 −1⎪⎨ = =0 =1 , |, | ≤ ¯⎪⎩ * = min ,∈[0..20 −1] где =, =sup | ( + ¯ ) − ( + ¯ )|,0≤<22() ( )()0 ≤ < 20 ,0 < < 20 .− −1 ( ),Тогда квазисплайн { ()} обеспечивает заданную равномернуюточность аппроксимации функции :sup | () − ()| ≤ ,∈[0,20 ]9а количество ненулевых бит для коэффициентов в промежуточных узлахквазисплайна не превосходит≤02∑︁−1 −1∑︁max(0, 2 + ⌈ + log2 |, |⌉),=0 =0где - минимальная допустимая длина дробной части коэффициентаполиномиальной аппроксимации в одном сегменте.Были построены таблицы для квадратичной аппроксимации функций√sin, ln, 1/, в интервале точностей 24-32 бит.
Уменьшение размера таблиц для двузвенного квазисплайна составляет более 40%, что соответствуетрезультатам Стролло. Для четырехзвенного квазисплайна уменьшение размера таблиц — более 60%, а уменьшение энергопотребления — до 2 раз, чтопревосходит известные результаты.В третьей главе изучаются комбинаторные задачи размещения данных в многобанковой памяти при реализации быстрого преобразования Фурье (БПФ).
Они формулируются в терминах антимашины в классификацииХартенштейна [Hartenstein, 1991] как задачи составления расписаний длягомогенного синхронного графа потока данных.Предположим, что алгоритм БПФ последовательно выполняет бабоч∏︀ки порядков 0 , 1 , . . . , . Длина входного массива есть = =0 . Память разделена на банков памяти, и число есть наименьшее общеекратное оснований ( )=0 . Предполагается, что на каждом такте процессорможет вычислить любое количество бабочек с записью результата в тех жеячейках памяти, из которых были считаны исходные данные для выполнения бабочек. Однако на каждом такте разрешено лишь одно обращение ккаждому банку памяти. Конфликтом доступа к памяти называется ситуацияодновременного обращения к двум или более адресам одного банка памяти.Требуется найти распределение входных данных по банкам (), прикотором на каждом такте отсутствует конфликт доступа к памяти. Требуется указать также для каждой стадии БПФ все наборы одновременновыполняемых бабочек.Наибольший общий делитель произвольного набора натуральныхчисел ( )=0 обозначим (( )=0 ), а наименьшее кратное набора —(( )=0 ).Теорема 2 Пусть в алгоритме БПФ последовательно выполняются стадии по основаниям 0 , 1 , .
. . , . Если алгоритм БПФ начинается с младших разрядов, то определим = ( , . . . , 0 ) и цифровое представление номера компоненты входного массива = = ( , . . . , 0 ).10Если алгоритм БПФ начинается со старших разрядов, то определим = (0 , . . . , ) и цифровое представление номера компоненты входного массива = = (0 , . .
. , ).∏︀Входной массив размерности = =0 записывается в банков данных, где = (0 , . . . , ) — наименьшее общее кратное оснований бабочек.Для каждого = 0, 1, . . . , введём обозначения = (( )=0 ), =,−1, =,( , ), =,,−1,0 ≤ < ,с доопределением −1 = −1, = 1.Определим номер банка (), в который помещается элементвходного массива с номером при = 0, 1, .
. . , − 1, по формуле() =∑︁ mod ,=0где = и = / . На стадии при 0 ≤ ≤ одновременно выполняются все бабочки с номерами ℓ, в цифровом представлении которыхсовпадают целые части ⌊ /, ⌋ при 0 ≤ < и целые части ⌊ / ⌋при < ≤ . Тогда при выполнении алгоритма БПФ не возникаетконфликтов памяти, и на каждом такте задействованы все банковпамяти.Модифицируем архитектуру акселератора вычисления БПФ для использования 1rw памяти, в которой чтение и запись в один банк памяти немогут производиться за один такт. Для этого задействуем 2 банков памятии потребуем, чтобы запись и чтение осуществлялись в непересекающиесямножества банков.Теорема 3 Пусть длина конвейера нечетна, mod 2 = 1. Рассмотримследующий порядок обхода и функцию распределения индексов по банкам:{︃(), = 0,2 () =, > 0,[︃(︃ −1)︃]︃∑︁( 0 ) = .
. . , + ¯1 + ¯1mod ,(︃ (︃ −1=2)︃∑︁2 () = 2 + 0 − (0=111)︃mod 2)mod 2.Такой выбор порядка обхода и функции распределения по банкам обеспечивает отсутствие конфликтов для архитектуры потоковогоБПФ акселератора с 2 банками 1rw памяти при выполнении одной бабочки за такт.Инверсия индексов требует дополнительного прохода по памяти.Цель самосортирующегося алгоритма состоит в замене начальной перестановки на постепенные частные перестановки на каждой стадии, осуществляемые при минимальной длине конвейера.
Введём оператор перестановкиначальной и конечной цифр в индексе произвольного вектора. Пусть векторимеет длину и число делится на 2 , где ≥ 1. Тогда матрица перестановки определяется уравнениями (, ⊗ ℓ,/2 ⊗ , ) = , ⊗ ℓ,/2 ⊗ , ,0 ≤ , < ,0 ≤ ℓ < / 2 .Алгоритм БПФ в частотной области описывается формулой ℱ = −1, −2, · · · 0, , где , — преобразование -й стадии, — перестановка по инверсии мультииндекса .
Пусть = −1 , где = .Определим матрицы перестановок (, ⊗ , ) = , ⊗ , ,0 ≤ < ,⎧⎪,⎪⎪⎨ −1 ⊗ ⊗ −−1 , =⎪/2−1 ⊗ ⊗ /2−1 ,⎪⎪⎩ −−1 ⊗ [( 2− ⊗ ) 2+1− ] ⊗ −−1 ,ℱ = −1 · . . . · 0 ,0≤< = 0,1 ≤ ≤ ⌊ −12 ⌋, = 2 ,⌈ +12 ⌉ ≤ ≤ − 1. = , .Последовательность выполнения бабочек на каждой стадии определяет необходимый объём внутренней памяти и длину конвейера. Последовательность выполнения бабочек в самосортирующемся алгоритме должнабыть изменена для избежания конфликтов при обращении к памяти.Пусть = (−1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
