Содержание к диссертации
Стр.
ВВЕДЕНИЕ 4
I. ИСПОЛЬЗОВАНИЕ АСИНХРОННЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
В ПРОБШШО-ОРИЕЕІТИРОВАНШХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ . 10
Модели асинхронных параллельных вычислений .... 10
Базовая структура проблемно-ориентированных
систем потока данных . 26
1.3. Алгебраические методы исследования моделей,
асинхронных параллельных вычислений 32
1.4. Постановка задач исследования ... 43
ВЫВОДЫ 44
II. АЛГЕБРЫ СХЕМ ПОТОКА ДАННЫХ 45
Базовая алгебра обобщенных схем потока данных ... 45
Алгоритм построения регулярной,формулы,СПД. .
в базовой алгебре 61
Акторная алгебра невзвешенных схем потока данных . 68
Склейковая алгебра.невзвешенных схем
потока данных . . ....... 98
2.5. Алгебра взвешенных,схем потока,данных ....... 121
ВЫВОДЫ *.....;. 152
III. ЭКВИВАЛЕНТНЫЕ. ПРЕОБРАЗОВАНИЯ СХЕМ ПОТОКА ДАННЫХ . . 153
3.1. Тождественные преобразования.формул
схем потока данных 153
3.2. Гомоморфные отображения &-формул, и о -формул .
схем потока данных .......... 157
3.3. Эквивалентные преобразования,схем потока.данных . . 165
ВЫВОДЫ 198
Стр.
ІУ. МЕТОДИКА ПРОЖТЙРОБАНИЯ.ПРОБШШО-ОРИЕНТЙРОВАШЫХ .
. .СИСТЕМ ПОТОКА ДАННЫХ 199
Этапы проектирования подсистемы обработки проблемно-ориентированных систем потока данных . . 199
Этапы проектирования подсистемы управления проблемно-ориентированных систем.потока данных. . . 211
ВЫВОДЫ 228
ЗАКЛЮЧЕНИЕ 229
ЛИТЕРАТУРА 233
ПРИЛОЖЕНИЕ I ................ 244
ПРИЛОЖЕНИЕ II 260
_ 4 -
Введение к работе
Одним из перспективних направлений развития средств вычислительной техники является создание новых высокопроизводительных ЭВМ и систем с асинхронным способом реализации параллельных вычислений. Данное направление, связанное с развитием ЭВМ с нетрадиционной структурой и архитектурой /53/, сформировалось как альтернативное направлению, связанному с разработкой, улучшением и усовершенствованием ЭВМ и систем, основанных на архитектурных принципах построения ЭВМ, предложенных Дж. фон Нейманом, которое развивается на протяжении последних тридцати с лишним лет и носит в основном эволюционный характер.
Один из подходов к созданию ЭВМ и систем с нетрадиционной архитектурой состоит в разработке ЭВМ, реализующих потоковые модели параллельных вычислений, такие, например, как схемы потока данных Дж.Б.Денниса {data fgocv schemes )» управляемые данными сети Дейвиса ( data dH&en neicuor&s) и др. /I, 3, 26, 30, 40, 52, 59, 76, 92/;.
Идея управления ходом вычислений с помощью потока данных была предложена давно /26/, однако интерес к созданию реальных ЭВМ и систем, основанных на потоковых моделях, появился сравнительно недавно и с каждым годом все более увеличивается /54, 56, 78, 90, 96/. Потоковый принцип управления позволяет в максимальной степени выявить и реализовать естественный параллелизм, присущий решаемой задаче, поэтому требует создания вычислительной системы, структура которой в максимальной степени адекватна временным и структурным особенностям алгоритма задачи, представленного в форме потоковой модели /80/. Это требование предполагает построение вычислительных потоковых систем с большим числом
процессоров". Появление микропроцессоров и других БИС в качестве мошной, гибкой и относительно дешевой элементной базы создало реальные возможности построения потоковых систем. В настоящее время в этом направлении ведутся интенсивные исследования в нашей стране /6-9, 13-21, 23, 32, 37, 38, 46-50, 56, 59, 61, 62/ и за рубежом /54, 78/. Наибольший вклад в разработку теории потоковых вычислений и в создании проектов потоковых языков и машин внесла группа Дж.Б.Денниса из Массачусеттского технологического института /73, 79/. Потоковые машины и системы объявлены одними из наиболее перспективных для разработки ЭВМ пятого поколения в национальной программе по вычислительной технике в Японии /54, 100/; создание потоковых ЭВМ и систем отмечалось как новое направление в развитии средств вычислительной техники на европейских международных конференциях /54, 96/.
Принципиальное отличие машин потока данных от обычных ЭВМ заключается в следующем". Программы классической ЭВМ организованы линейно: команды программы упорядочены в памяти ЭВМ в соответствии с порядком предшествования команд, задаваемым управляющим графом алгоритма, и выбираются для выполнения с помощью счетчика команд, содержимое которого инкрементируется после выполнения очередной команды. Изменение порядка выполнения производится с помощью специальных команд условного и безусловного переходов. В отличие от указанного порядка выполнения, который реализуется в виде последовательного потока управления, организация вычислений в машинах потока данных предполагает, что команды выбираются для выполнения, как только получены их> операнды, что необходимо фиксировать специальными средствами. Таким образом, команды могут быть расположены в памяти потоковой машины в произвольном
порядке, наличие счетчика команд не обязательно /77, 93/. Следствием такой организации вычислений является одновременное выполнение нескольких команд потоковой программы. Упрощение задания и верификации программ, ориентация на мультимикропроцессорные и мультимикромашинные системы, эффективность работы в реальном масштабе времени - эти особенности потоковых машин вызывают большой интерес /56/.
Основное требование к системам потока данных, которое заключается в адекватности структуры системы структурным и временным характеристикам алгоритмов решаемых задач, предполагает создание эффективных средств представления, исследования и оптимизации структурных и временных характеристик алгоритма, представленного в форме той или иной модели параллельных программ. В связи с этим большое прикладное значение имеет использование алгебраических методов, которые широко используются при решении задач, связанных с распараллеливанием вычислительных алгоритмов, созданием языков параллельного программирования, исследованием моделей параллельных вычислений и созданием параллельных вычислительных систем. Глубокое развитие алгебраические методы получили в работах по параллельному программированию и параллельным вычислительным системам, проводимых в Вычислительном центре и Институте математики СО АН СССР /I, 14, 30, 31, 39-45, 50-52, 62/, Институте кибернетики им.В.М.Глушкова АН УССР /6-9, 23-25, 63/, и других работах.
Настоящая работа посвящена исследованию вопросов проектирования проблемно-ориентированных систем потока данных и является логическим продолжением исследований в области разработки высокопроизводительных проблемно-ориентированных вычислительных систем, проводимых на кафедре Вычислительной техники ЛЭТИ им.В.И.Ульянова
(Ленина) под научным руководством заслуженного деятеля науки и техники РСФСР, доктора технических наук, профессора В.Б.Смолова.
Дельта работы является разработка методов проектирования проблемно-ориентированных систем потока данных, которые могут служить основой создания автоматизированной системы проектирования проблемно-ориентированных систем потока данных.
С этой целью в работе решались следующие основные задачи:
разработка основ методики проектирования проблемно-ориен- ' тированных систем потока данных;
анализ моделей параллельных программ, методов их представления и средств исследования и оптимизации;
разработка эффективных методов представления и средств исследования и оптимизации схем потока данных.
В диссертационной работе использовались методы теории схем программ, теории множеств и отношений, элементы теорий универсальных алгебр, полугрупп, векторных пространств, методы сетевого планирования и управления, теории графов; в работе сочетаются формальный и содержательный подходы.
Научная новизна проводимых исследований состоит в том, что:
предложены алгебры схем потока данных, позволяющие представлять в текстовой форме схемы потока данных, проводить исследования их структурных и временных характеристик, а также осуществлять их оптимизацию с помощью алгебраических методов;
предложена система эквивалентных преобразований схем потока данных, отличающаяся тем, что она позволяет улучшать структурные и временные характеристики схемы потока данных алгоритма, реализуемого в проблемно-ориентированной системе потока данных (ПОС ПД);
~ 8 -
- предложена методика проектирования ПОС ПД, базовая структу
ра которых подобна структуре компьютера потока данных Дж. Б. Денниса,
отличающаяся тем, что она основана на анализе представленной в
текстовой форме СПД алгоритма, рассматриваемой как информационный
граф, а также на использовании результатов анализа для построения
структуры ПОС ІЩ, соответствующей структурным и временным харак
теристикам схемы потока данных алгоритма.
Практическая ценность полученных результатов заключается в следующем:
предложенные алгебры схем потока данных позволяют представлять СПД в текстовой форме и проводить анализ и оптимизацию схем потока данных с использованием алгебраических методов, а также могут быть положены в основу автоматизированного анализа и оптимизации программ потока данных;
предложенные эквивалентные преобразования схем потока данных позволяют улучшать временные и структурные характеристики схем потока данных с целью сокращения затрат памяти на хранение программы потока данных, приведения СПД к некоторому стандартному виду, а также уменьшения длительности реализации программы потока данных в ПОС ПД;
предложенная методика проектирования позволяет выбирать структуру ПОС ПД наиболее адекватную временным и структурным характеристикам схемы потока данных алгоритма, который будет реали-. зован в проектируемой системе.
Диссертационная работа состоит из четырех глав и двух приложений.
В первой главе рассмотрены модели асинхронных параллельных вычислений, в частности схемы потока данных (СПД), которые могут
служить основой асинхронного способа организации параллельного вычислительного процесса в высокопроизводительных ПОС ЦД; описана базовая структура потоковой вычислительной системы; проведен анализ алгебраических методов представления и средств исследования и оптимизации параллельных программ.
Во второй главе произведено построение альтернативных ак-торных и склейковых алгебр невзвешенных обобщенных и обыкновенных схем потока данных; сформулированы основные теоремы о возможности представления СЦЦ в виде формул в построенных алгебрах; разработаны алгоритмы построения минимальных алгебраических формул СЦЦ по матричному представлению схем; предложены акторные и склейко-вые алгебры взвешенных схем потока данных.
В третьей главе построены тождественные преобразования формул СГЩ; предложено гомоморфное отображение акторной и склейковой алгебр невзвешенных СЦЦ, которое может быть положено в основу создания трансляторов формул СПД; предложены эквивалентные преобразования схем потока данных, представленных в текстовом (формульном) виде; рассмотрены условия целесообразности проведения различных эквивалентных преобразований СПД.
В четвертой главе сформулированы этапы проектирования подсистем обработки и управления, которые составляют методику проектирования ПОС ПД; предложены методы решения вопросов, возникающих на отдельных этапах проектирования.
В приложения включены доказательства теорем и лемм, сформулированных в диссертации; описан пример проектирования подсистемы обработки специализированной системы потока данных для цифровой обработки сигналов'.
