Введение к работе
Актуальность темы. Создание параллельных вычислительных систем различной архитектуры, внедрение их в практику решения больших прикладных задач и задач в реальном времени привело к необходимости углубления и расширения знаний об алгоритмах, систематической разработки и исследования алгоритмов, ориентированных на параллельную реализацию. Поэтому актуальными и перспективными являются построение математических моделей параллельных вычислений, разработка и исследование методов построения параллельных форм вычислительных алгоритмов, предназначенных для реализации на алгоритмически-ориентированных матричных процессорах.
Связь работы с крупными научными программами, темами. Исследования проводились в рамках бюджетных тем "Исследование математических проблем теории принятия решений, моделирования процессов легирования многослойных полупроводниковых структур, проблем размещения и укладки графо-геометрических систем, проектирования систолических вычислителей на базе СБИС" (1990-1993) и "Методы моделирования процессов переноса в полупроводниковых структурах и отображение вычислительных алгоритмов на систолические матричные спецпроцессоры" (1993-1995), включенных в план важнейших НИР в области естественных, технических и общественных наук по Республике Беларусь.
Цель исследования. 1. Разработка теории построения параллельных форм вычислительных алгоритмов для реализации на систолических матричных процессорах, позволяющей синтезировать одновременно с параллельными формами оптимальные систолические структуры. 2. Построение параллельных форм алгоритмов решения задач вычислительной математики для реализации на матричных процессорах.
Научная новизна. Все результаты, сформулированные в виде методов, теорем и приближенных формул, являются новыми. По сравнению с известными методиками отображения алгоритмов, на систолические процессоры, предлагаемая теория включает ряд новых методов, позволяющих формализовать все этапы отображения и в рамках единой теории получать оптимальные систолические структуры разных типов и параллельные формы алгоритмов мини-
мальной высоты для реализации на этих структурах.
Практическая и теоретическая значимость. Полученные в диссертации теоретические результаты можно применять при разработке штодов построения параллельных форм алгоритмов для реализации на различных многопроцессорных вычислительных системах. Предложенные параллельные формы алгоритмов в виде вычислительных графов являются моделями высокопроизводительных специализированных матричных процессоров, удобных для реализации на базе технологии производства сверхбольших интегральных схем.
Основные положения диссертации, выносимые на вашиту:
1. Метод стыковки двух базовых вычислительных графов. Метод
позволяет получать параллельные формы сложных (декоглюзиро-
ванннх) алгоритмов.
2. Конструктивное правило построения таймирующей функции
при отображении базовых вычислительных графов посредством ли
нейного оператора, размерность ядра которого больше единицы;
получение функционального описания вершин синтезируемого вы
числительного графа.
4. Подход к получению одномерных вычислительных графов. Предлагаемый подход дает больше возможностей для минимизации высоты получаемой параллельной форлы алгоритма по сравнению с известными подходами.
Ь. Методы построения параллельных форм заданной ширины для реализации на линейных матричных процессорах. По сравнению с известными способами предлагаемые процедуры получения линейных ВГ проще и эффективнее.
-
Локально параллельный глобально последовательный метод построения параллельных форм заданной ширины для реализации на двумерных матричных процессорах без глобальных межсоединений.
-
метода получения линейных и полуограниченных вычислительных графов без глобальных межсоединений.
-
Методы построения параллельных форм итерационных алгоритмов. Методы позволяют строить параллельные форм заданной ширины для итерационных алгоритмов, а также реализовывать итерационные алгоритмы на систолических матричных процессорах с числом процессорных элементов, не зависящим от числа итераций.
- 9. Способы получения двухуровневых вычислительных графов.
10. Разработка, исследование и параллельная реализация составных приближенных формул пятой степени точности для вычисления винеровских и пуассоновских континуальных интегралов. В отличие от известных составных формул для приближенного вычисления винеровских и пуассоновских континуальных интегралов, построенные формулы содержат не кратные интегралы, а кратные конечные суммы.
-
Разработка, исследование и параллельная реализация составных кубатурных формул пятой степени точности для приближенного вычисления кратных интегралов с гауссовым!! весовыми функциями и кратных пуассоновских рядов. Формулы аналогичны составным квадратурным формулам для вычисления интегралов по отрезку прямой: при фиксированной степени точности сходимость к точному значению интеграла (ряда) осуществляется за счет увеличения целочисленного параметра формулы.
-
Параллельные формы алгоритмов вычислительной математики, представляющие модели систолических матричных процессоров. Соответствующие модели систолических матричных' процессоров защищены авторскими свидетельствами и патентами.
Личный вклад соискателя. Из совместных работ в диссертацию включены только результаты, полученные лично автором или полученные при непосредственном участии автора. Строгое разделение результатов приведено в диссертации.
Апробация результатов. Основные результаты диссертации были представлены и докладывались на VII Всесоюзном совещании "Методы Монте-Карло в вычислительной математике и математической физике", Новосибирск, 1985; на її Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники, Ереван, 1987; на I Всесоюзном семинара "Логические метода построения однородных и систолических структур", Москва, 1988; на і Всесоюзной конференции "Однородные вычислительные среды и систолические структуры", Львов, 1990; на международных конференциях "Parallel Computing Technologies", Новосибирск, 1991; "Real Time Data Distributed Front-End Processing", Дубна, 1994; "Parallel Processing and Applied Mathematics", Ченстохова, Польша, 1994; на семинарах в Институте математики АН Беларуси, в институте прикладных проблем механики и математики АН Украины.
Опубликованность результатов. По результатам исследований в рамках данной диссертации опубликовано 93 работы, включая два выпуска библиотеки научных программ и 45 изобретений. Основные результаты диссертации опубликованы в работах [1-26]. Структура и объем диссертации. Диссертация .состоит из введения, пяти глав, разбитых на разделы, списка использованных источников из 232 наименований. Полный объем диссертации -268 страниц, включая иллюстрации, таблицы и список использованных источников, которые занимают 74 страницы.
Похожие диссертации на Методы построения параллельных алгоритмов для реализации на систолических матричных процессорах
