Введение к работе
Актуальность темы. В последнее время большую актуальность приобрело направление научных исследований, получивших название "Отображение вычислительной математики на архитектуру вычислительных систем". Это направление связано с комплексом исследований в области архитектуры параллельных вычислительных систем (ВС), структуры реиаемых задач и алгоритмов, средств поддержки. Репение данной проблемы имеет ключевое значение для конструирования высокопроизводительных ВС и прикладных алгоритмов, позволяет установить между ними оптимальное соответствие.
Одной из наиболее важных задач в этой области является отображение вычислительных алгоритмов на различные типы ВС. В нее входит анализ свойств и структуры алгоритмов', исследование возможности построения параллельных форм с заданными свойствами, разработка математических моделей ВС, их языковой поддержки, разработка общих методов для подобных исследований. В диссертационной работе рассматриваются вопросы изучения а записи структур алгоритмов, часто встречающихся в прикладных задачах в качестве составных частей.
В качестве основного объекта для изучения параллельных структур алгоритмов автором избран граф алгоритма, представ-ляхций из себя описание всех операций, которые должны быть выполнены в процессе его работы (что соответствует вершинам графа), в того, каким образом пересылаются между ними данные 3 (что соответствует дугам). Если у нас есть полное описание 0 графа алгоритма, то в любой момент его работы, зная, какие
операции ухе выполнены, всегда можно определить все операции, выполнимые в 8TOT момент.
Выбор в качестве основного объекта исследования графе алгоритма определяется следующим. Во-первых, при наличии графа алгоритма у нас есть полная информация о его структуре, что облегчает не только его отображение на различные типы параллельных архитектур, но и получение какой-либо другой интересующей исследователя информации. Так, при наличии графа алгоритма для отображения его на архитектуру Data Flow не должно возникнуть никаких сложностей, кроме чисто технических. Упрощается и нахождение его оптимальной ярусно-паралле-льной формы. Легко находятся потенциальные источники конфликтов в памяти - те операции, результаты которых используются в большом числе других в качестве аргументов. Кроме того, известна методика получения по графу алгоритма оценок влияния ошибок округления на его конечные результаты. Во-вторых, получение информации о графах распространенных алгоритмов освободило бы реализующего их на конкретной вычислительной системе от повторения заново дорогостоящего анализа их структур, позволив заниматься собственно их отображением на архитектуру ЭВЫ на единой методологической основе.
Цель работы: разработка принципов описания графа алгоритма в удобном виде для отображения на различные типы архитектур, создание соответствующего языка и его сопровождения (процедур быстрого извлечения различной информации из записи графа); создание пакета по решению систем линейных алгебраических уравнений в хорошо реализуемой на параллельных ЭВМ форме с сопровождающей информацией об их графах.
Научная новизна. Разработаны основные принципы, которым должна удовлетворять запись графа алгоритма; исходя из них, разработана конкретная форма записи. Создан пакет по решение
систем линейных алгебраических уравнений (СЛАУ). Исследована
і структура алгоритмов, входящих в пакет. Графы основных алгоритмов пакета записаны в разработанной форме. Разработан ряд конструктивных процедур для изучения графа.
Практическая ценность. Предложенная форма записи графов алгоритмов может быть использована в автоматизированных системах, нацеленных на отображение алгоритмов на различные архитектуры вычислительных систем, как в качестве промежуточного, так и в качестве входного языка. Ряд таких систем или уже созданы (например, систолизатор P.P. Хунафиной) или находятся в стадии отладки. Этому способствует наличие разработанных автором процедур для исследования графа, которые легко алгоритмизируемы. Созданный пакет програші может применяться не только для отображения представленных алгоритмов на различные архитектуры, но и как обычный программный продукт на стандартно!* Фортране.
Апробация работы. Основные результаты диссертации докладывались на XXII школе "Вопросы оптимизации вычислений" (Одесса, 1989 г.), семинарах лаборатории численных методов алгебры ОВЫ АН СССР, на научных конференциях в UWTJ в 1987-1990 гг.
Публикации. По теме диссертации опубликовано четыре работы, список которых приведен в конце автореферата.
Структура диссертации. Работа состоит из введения, двух глав, списка литературы, содержащего 55 наименований, трех'
приложений и заключения. Объем диссертации составляет 140 страниц, из них 10 с рисунками.
