Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры
Подождите немного. Документ загружается.
РОССИЙСКАЯ АКАДЕМИЯ НАУК
ЮЖНЫЙ НАУЧНЫЙ ЦЕНТР
И.А. Каляев, И.И. Левин,
Е.А. Семерников, В.И. Шмойлов
РЕКОНФИГУРИРУЕМЫЕ
МУЛЬТИКОНВЕЙЕРНЫЕ
ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ
Ростов-на-Дону
Издательство ЮНЦ РАН
2008
394
Оглавление
Предисловие…………………………………………………………………… 3
Введение……………………………………………………………………….. 7
Глава 1. Принципы организации реконфигурируемых
мультиконвейерных вычислительных структур…………………...
17
1.1. Проблема производительности многопроцессорных систем.. 17
1.2. Потоковые задачи и способы их решения.……………………. 26
1.3. Принципы мультиконвейерной обработки потока данных.. 32
1.4. Мультимикро- и мультимакроконвейерные вычислительные
структуры………………………………………………...............
40
1.5. Структурно-процедурный способ организации
мультиконвейерных вычислений………………………………
47
Глава 2. Мультимикроконвейерные вычислительные структуры на
однородных средах.………………………………………………….
58
2.1. Архитектура однородной вычислительной среды…………….
58
2.2. Организация вычислительного процесса в ОВС……...……… 64
2.3. Математическая модель ОВС………………………………….. 67
2.4. Синтез спецпроцессоров в среде………………………………. 73
2.5. Структура микропрограммного обеспечения………………… 77
2.6. Процесс настройки поля ОВС…………………………………. 79
2.7. Программирование однородных сред………………………….
82
2.7.1. Образование и использование констант…………………….. 82
2.7.2. Внешняя подача констант в спецпроцессор…………………
85
2.7.3. Форматы операндов…………………………………………... 86
2.7.4. Спецпроцессоры арифметических и логических операций... 88
2.8. Решение прикладных задач на ОВС………………………….. 102
2.8.1. Задача обработки изображений……………………………… 102
2.8.2. Реализация цифровых фильтров в поле ОВС.……………….
104
395
2.9. Аппаратная реализация мультимикроконвейерных
структур на ОВС………………………………………………...
115
2.10. О перспективах развития однородных вычислительных
сред……………………………………………………………..
123
Глава 3. Структурно-процедурная организация вычислений
в мультиконвейерных структурах………................................
132
3.1. Принципы функционирования мультимакроконвейерных
вычислительных структур…..………………………………….
132
3.2. Преобразование информационных графов в структурно-
процедурные программы…...…………………………………...
142
3.3. Преобразование задачи в структурно-процедурную форму….
152
3.4. Преобразование функционально-регулярных
информационных графов……….................................................
161
3.5. Преобразование в кадровую форму решения задачи
Пуассона………………………………………………………....
164
3.6. Преобразование в структурно-процедурную форму
информационных графов нерегулярной структуры..................
181
3.7. Структурно-процедурная реализация задачи трассировки…...
186
Глава 4. Реконфигурируемые мультиконвейерные вычислительные
структуры на основе ПЛИС …………………………………
197
4.1. Модульно-наращиваемая реализация реконфигурируемых
мультиконвейерных вычислительных структур………………
197
4.2. Элементная база реконфигурируемых мультиконвейерных
вычислительных структур………………………………………
207
4.2.1. Заказные СБИС….……………………………………………. 207
4.2.2. Базовые матричные кристаллы……………………………….
208
4.2.3. Системы-на-кристалле………………………………………...
209
4.2.4. Программируемые логические интегральные схемы……….
211
396
4.3. Принципы построения базовых модулей реконфигурируемых
мультиконвейерных вычислительных структур на основе
ПЛИС…………..............................................................................
218
4.4. Реализация базовых модулей реконфигурируемых
мультиконвейерных вычислительных структур на основе
ПЛИС …………………………………………………………….
223
4.4.1. Структуры базовых модулей первого поколения…………... 223
4.4.2. Структура базовых модулей второго поколения…………… 226
4.4.3. Базовые модули третьего поколения………………………... 231
4.4.3.1. Базовый модуль третьего поколения 16V4-50…………… 232
4.4.3.2. Базовый модуль для решения задач цифровой обработки
сигналов……………………………………………………...
234
4.4.3.3. Базовый модуль 4V4-25 малогабаритного ускорителя
персонального компьютера…………………………………
238
4.4.4. Базовые модули перспективных разработок………………...
241
4.4.4.1. Структура базового модуля высокопроизводительных
систем………………………………………………………...
243
Глава 5. Реконфигурируемые мультиконвейерные вычислительные
структуры с макрообъектной архитектурой………………...
248
5.1. Принципы построения реконфигурируемых вычислительных
структур на основе макрообъектной архитектуры…….……...
248
5.2. Обобщенная структура макрообъекта.………………………... 256
5.3. Вычислительные блоки макрообъектов………………………. 259
5.3.1. Представление данных в макропроцессоре………………….
259
5.3.2. Обобщенная структурная схема функциональных узлов с
плавающей запятой……………………………………………
260
5.3.3. Функциональный узел сложения чисел с плавающей
запятой........................................................................................
261
397
5.3.4. Функциональный узел умножения чисел с плавающей
запятой…………………………………………………………
262
5.4. Макрообъект для решения задач математической физики
сеточными методами……………………………………………
263
5.5. Пример решения задачи математической физики с помощью
макрообъекта……………………………………………………
268
5.6. Макрообъект для решения задач цифровой обработки
сигналов………………………………………………………….
271
5.7. Макрообъект для решения задач линейной алгебры………….
287
5.7.1. Структура макрообъекта для решения задач линейной
алгебры…………………………………………………………
287
5.7.2. Реализация алгоритма решения СЛАУ методом Гаусса……
288
5.8. Универсальный макрообъект…………………………………...
292
5.8.1. Структура макропроцессора………………………………..... 293
5.8.2. Макропроцессор с каскадной коммутационной структурой.
295
5.8.3. Каскадный коммутатор макропроцессора …………………..
298
5.8.4. Элементарный процессор……………………………………..
299
5.8.5. Блок команд макропроцессора ……………………………… 300
5.8.6. Блок операндов………………………………………………...
302
Глава 6. Системное математическое обеспечение
реконфигурируемых мультиконвейерных вычислительных
структур………………………………………………………..
304
6.1. Структура системного математического обеспечения………..
304
6.2. Язык ассемблер…………………………………………………. 314
6.2.1. Общие сведения………………………………………………. 314
6.2.2. Элементы языка………………………………………………. 317
6.2.3. Программирование распределенной памяти………………...
323
6.2.4. Операторы управления……………………………………….. 332
6.2.5. Внешние операторы контроллера распределенной памяти.. 334
398
6.3. Язык параллельного программирования высокого уровня
COLAMO…………………………………………………………
336
6.4. Среда проектирования параллельно-конвейерных программ.. 364
Послесловие…………………………………………………………………… 377
Литература……………………………………………………………………...
380
Предметный указатель………………………………………………………... 390
Предисловие
Создание высокопроизводительных вычислительных систем входит в
первую десятку жизненно важных программ ведущих государств мира. Без
суперкомпьютеров невозможно обеспечить конкурентоспособность страны на
мировом рынке, без них нельзя поддерживать обороноспособность государства
на должном уровне. Очевидно, что без суперкомпьютеров затруднительно
проводить современные научные изыскания в самых различных областях, будь
то материаловедение, медицина, экономика, экология, кибернетика и т.д.
Амбициозные программы по нанотехнологиям и термоядерной энергетике так
и останутся впечатляющими программами, если российские ученые не будут
иметь в своем распоряжении постоянно обновляющийся парк суперЭВМ.
К сожалению, в России в настоящее время имеется серьезное отставание
в области суперкомпьютеров по сравнению с ведущими странами мира. В
последнем списке TOP 500 (ноябрь 2007 г.), содержащем сведения о наиболее
высокопроизводительных суперкомпьютерах, упомянуты семь российских
суперкомпьютеров, находящихся далеко не на первых позициях, причем из них
лишь два собственной разработки (self-made), остальные – покупные, от
зарубежных фирм. Для сравнения, в той же 30-й редакции ТОР 500 США
представлены 284-мя вычислительными системами.
Что же делать? Идти по пути копирования западных образцов, как это
практиковалось долгие десятилетия - малопривлекательное занятие, поскольку
при таком подходе отставание будет только нарастать. Выход из сложившейся
ситуации видится в поддержке и форсированном развитии оригинальных
отечественных разработок в области высокопроизводительных
вычислительных систем. Весьма перспективной нам представляется концепция
реконфигурируемых многопроцессорных вычислителей. Суть этой концепции
заключается в том, что архитектура вычислительной системы должна иметь
возможности адаптироваться под структуру решаемой задачи. Фактически это
означает, что пользователю должна быть предоставлена возможность
программировать проблемно-ориентированные многопроцессорные
вычислительные системы, структура которых адекватна решаемой ими задаче.
При этом в отличие от известных архитектур, достигается высокая реальная
производительность вычислительной системы на широком классе задач, а
также почти линейный рост производительности при увеличении числа
процессоров.
Концепция многопроцессорных вычислителей с реконфигурируемой
архитектурой развивается в нашей стране давно по нескольким направлениям.
Здесь следует упомянуть работы А.В. Каляева [46], Э.В. Евреинова [40],
И.В. Прангишвили [95], В.Г. Хорошевского [39], а также работы других
авторов [12, 59, 126]. Несмотря на все различия, сущность этих работ состоит в
организации вычислительного устройства с мультиконвейерным способом
вычислений, обладающего возможностями реконфигурирования связей и,
соответственно, адаптацией вычислительной системы под структуру решаемой
задачи. Отличие же подходов заключается лишь в той или иной степени
детализации конвейерной ступени, а также в том или ином способе
реконфигурирования связей между ними. Поэтому в дальнейшем
многопроцессорные вычислительные устройства такого типа будем называть
реконфигурируемыми многопроцессорными вычислительными структурами с
мультиконвейерным способом организации вычислений или, короче,
реконфигурируемыми мультиконвейерными вычислительными структурами.
Однако, несмотря на достаточно большое число исследований в этом
очень перспективном направлении, создание целого ряда экспериментальных и
макетных образцов таких машин, дело до широкого внедрения
реконфигурируемых многопроцессорных систем в нашей стране, к сожалению,
не дошло. Возможно, в некоторой мере это было вызвано экономическими и
политическими проблемами, имевшими место в 80-90-х годах прошлого века,
но основная причина, с нашей точки зрения, была связана с отсутствием
элементной базы, которая бы позволяла строить эффективные
реконфигурируемые мультиконвейерные вычислительные структуры.
Созданные на основе отечественной элементной базы экспериментальные
образцы реконфигурируемых мультиконвейерных вычислительных структур
оказывались громоздкими, малонадежными, слаборемонтопригодными, что
делало их неконкурентоспособными на отечественном и, тем более, на мировом
рынках.
В конце 90-х годов XX века российским разработчикам вычислительных
систем стала доступна элементная база западных фирм, которая позволяла
разрабатывать эффективные реконфигурируемые мультиконвейерные
вычислительные структуры. Это - так называемые программируемые
логические интегральные схемы (ПЛИС) нового поколения, в английской
аббревиатуре - FPGA (Field Programmable Gates Array).
ПЛИС представляют собой некоторую матрицу логических ячеек, за счет
программирования и коммутации которых можно создавать аппаратные
реализации различных вычислительных структур, причем
перепрограммирование логических ячеек и связей может осуществляться
многократно. Иными словами, ПЛИС – это некоторый «полуфабрикат»
микросхемы, внутреннюю структуру которой может определять сам
пользователь.
Появление ПЛИС сверхвысокой степени интеграции вдохнуло новую
жизнь в достаточно старую идею построения реконфигурируемых
вычислительных систем. Конечно, этот новый взгляд потребовал определенной
переработки, модернизации и адаптации этой идеологии с учетом особенностей
и возможностей современных ПЛИС.
В монографии излагаются результаты авторов, полученные в теории
реконфигурируемых мультиконвейерных вычислительных структур,
рассматривается практическая реализация этих структур на основе ПЛИС.
Представленные результаты были получены в рамках фундаментальных и
прикладных работ, проведенных в Научно-исследовательском институте
многопроцессорных вычислительных систем Таганрогского государственного
радиотехнического университета (ныне НИИ МВС Южного федерального
университета) и в Отделе информационных технологий и процессов
управления Южного научного центра РАН. Авторы выражают искреннюю
благодарность коллегам за неоценимую помощь при воплощении хрупких
теоретических построений в «железо», а также при подготовке рукописи
монографии к печати.
И.А. Каляев
23 января 2008 г.,
г. Таганрог