Параллельные структуры в алгоритмах линейной алгебры тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

АКАДЕМИЯ НАУК СССР ОТДЕЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

На правах рукописи

ФРОЛОВ Алексей Вячеславович

ПАРАЛЛЕЛЬНЫЕ СТРУКТУРЫ В АЛГОРИТМАХ ЛИНЕЙНОЙ АЛГЕБРЫ

01.01.07— Вычислительная математика, 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 1990

Работа выполнена в Московском ордена Трудового Крап Знамени физико-техническом институте

Научный руководитель член-корреспондент АН С( ВОЕВОДИН В. В.

Официальные оппоненты: доктор технических наук АРУШАНЯН О. Б.; кандидат физико-математических наук КРАСНОВ С. А.

Ведущая организация Институт проблем кибернет

на заседании специализированного совета К 003.47.01 Отделе вычислительной математики АН СССР по адр< 119034-, Москва, ул. Рылеева, 29.

С диссертацией можно ознакомиться в библиотеке Отд вычислительной математики АН СССР.

Автореферат разослан « 23 ^^ 1990 г.

АН СССР

Защита состоится

1990 г. в ^^

Ученый секретарь специализированного совета доктор физико-математических нау.

Агошков В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В последнее время большую актуальность приобрело направление научных исследований, получивших название "Отображение вычислительной математики на архитектуру вычислительных систем". Это направление связано с комплексом исследований в области архитектуры параллельных вычислительных систем (ВС), структуры решаемых задач и алгоритмов, средств поддерзки. Решение данной проблемы имеет ключевое значение для конструирования высокопроизводительных ВС и прикладных алгоритмов, позволяет установить между ними оптимальное соответствие.

Одной из наиболее важных задач в этой области является отображение вычислительных алгоритмов на различные типы ВС. В нее входит анализ свойств и структуры алгоритмов', исследование возможности построения параллельных форм с заданными свойствами, разработка математических моделей ВС, их языковой поддержки, разработка общих иетодов для подобных исследований. В диссертационной работе рассматривается вопросы

изучения а записи структур алгоритмов, часто встречающихся в

\

прикладных задачах в качестве составных частей.

В качестве основного объекта для изучения параллельных структур алгоритмов автором избран граф алгоритма, представ-лящий из себя описание всех операций, которые должны быть выполнены в процессе его работы (что соответствует вершинам графа), в того, каким образом пересылаются нежду ними данные 3 (что соответствует дугам). Если у нас есть полное описание 0 графа алгоритма, то в любой момент его работы, зная, какие

операция уже выполнены, всегда мохао определить все операции, выполнимые в 8тот момент.

Выбор в качестве основного объекта исследования графе алгоритма определяется еле душим. Во-первых» при наличии графа алгоритма у нас есть полная информация о его структуре, что облегчает не только его отображение на различные типы параллельных архитектур, но и получение какой-либо другой интересующее исследователя информации. Так, при наличии графа алгоритма для отображения его на архитектуру Data Flow не должно возникнуть никаких сложностей, кроме чисто технических. Упрощается и нахождение его оптимальной ярусно-паралле-льной формы. Легко находятся потенциальные источники конфликтов в памяти - те операции, результаты которых используются в большом числе других в качестве аргументов. Кроме того, известна методика получения по графу алгоритма оценок влияния ошибок округления на его конечные результаты. Во-вторых, получение информации о графах распространенных алгоритмов освободило бы реализующего их на конкретной вычислительной системе от повторения заново дорогостоящего анализа их структур, позволив заниматься собственно их отображением на архитектуру ЭВМ на единой методологической основе.

Цель работы: разработка принципов описания графе алгоритма в удобном виде для отображения на различные типы архитектур, создание соответствующего языка и его сопровождения (процедур быстрого извлечения различной информации из записи графа); создание пакета по решении систем линейных алгебраических уравнений в хорошо реализуемой на параллельных ЭВМ форме с сопровождающей информацией об их графах.

Научная новизна. Разработаны основные принципы, которым должна удовлетворять запись графа алгоритма; исходя из них, разработана конкретная форма записи. Создан пакет по решению систем линейных алгебраических уравнений (СЛАУ). Исследована

I

структура алгоритмов, входящих в пакет. Графи основных алгоритмов пакета записаны в разработанной форме. Разработан ряд конструктивных процедур для изучения графа.

Практическая ценность. Предложенная форма записи графов алгоритмов может быть использована в автоматизированных системах, нацеленных на отображение алгоритмов на различные архитектуры вычислительных систем, как в качестве промежуточного, так и в качестве входного языка. Ряд таких систем или yse созданы (например, систолизатор P.P. Хунафиной) или находятся в стадии отладки. Этому способствует наличие разработанных автором процедур для исследования графа, которые легко алгоритмизируемы. Созданный пакет программ молит применяться не только для отоОрагвния представленных алгоритмов на различные архитектуры, но и как обычный программный продукт на стандартном Фортране.

Апробация работы. Основные результаты диссертации докладывались на XXII школе "Вопросы оптимизации вычислений" (Одесса, 1989 г.), семинарах лаборатории численных методов алгебр! ОВЫ АН СССР, на научных конференциях в ЮТИ в 19871990 гг.

Публикации. По теме диссертации опубликовано четыре работы, список которых приведен в конце автореферата. 5 Структура диссертации. Работа состоит из введения, двух

3 глав, списка литературы, содержащего 55 наименований, трех'

1-2

- 3 -

приложений и заключения. Объем диссертации составляет 140 страниц, из них 10 с рисунками.

СОДЕЕШМЕ РАБОТЫ

Во введении дается общая характеристика работы, приводится краткое ее содержание.

Первая глава, состоящая из четырех параграфов, посвящена вопросам, связанным с записью и методам изучения и преобразования графе алгоритма (ГА).

В параграфе 1 обсуждается актуальность изучения ГА, формулируются принципы, которым должна удовлетворять его запись (компактность описания, запись графа в явном виде, модульность зашей). Дается обзор существующих алгоритмических языков, появившихся в связи с широким применением параллельных вычислительных систем, с точки зрения описанных правил. Делается вывод о нужности создания специального языка записи ГА ввиду отсутствия подходящего среди уже существующих.

В параграфе 2 описаны основные черты языка записи графов алгоритмов (Сипла), с кратким описанием соответствия фортран-программ и Сигма-програш. Язык Сита обладает следующими основными чертами:

а) отсутствие привязки программ к памяти (даже виртуальной - такой, как массивы в языках типа Фортрана), исключая (формально) описание входных и выходных параметров подпрограмм,

б) отсутствие описания порядка выполнения операций при условии явной записи всего графа,

в) компактность описания графа, что достигается с помощью помещения вершин графа в некоторое многомерное пространство,

г) возможность записи графа как в явном виде (т.е. когда все дуги, ведущие в'лобую из его вершин, быстро вычисляются через ее координаты в пространстве, о котором упомянуто выше), так и в неявном (т.е. когда такой зависимости не дано, однако круг вершин, которые могут поставлять в данную вершину свои результаты, сильно ограничен и дана информация, по которой можно осуществить выбор между ними).

д) возможность записи графов отдельных модулей в виде, позволяющем достаточно быстро "состыковывать" их друг с другом.

Параграф 3 содержит определения ряда характеристик ГА, а такге обоснованные процедур! их нахождения. Кроме этого, приводятся обоснованные процедуры "улучшения" параллельных свойств алгоритма (таких, как уменьшение критического пути ГА) с примером - программой решения СЛАУ с верхней треугольной матрицей обратной подстановкой с нормировкой.

Определение. В случае, если результат какой-либо операции используется в качестве аргумента во многих (т.е., в таком количестве, которое нельзя описать простым перечислением) других операциях, то будем говорить, что дуги, связанные с передачей этого результата, принадлежат пучку рассылочных дуг.

Определение. Если разница между координатами начала дуги и ее конца не может быть ограничена некоторой константой (не зависящей от размеров графа), причем это условие при та-

1-3

- 5 -

ких деформациях графа, которые ве изменяют взаимное расположение вершин внутри одной группы, остается в силе (т.е., либо выполняется для данной дуги, либо появляется другая дуга, для которой оно не выполнялось до деформации, но стало выполняться после), то такую дугу мы будем называть длинной.

Приводятся также теоремы, обосновывающие процедуры нахождения пучков рассылок и длинных дуг.

Вводится также определение ярусно-параллельной формы (ЯПФ) ГА, а также определение корректной ЯПФ. Для программ, содержащих операции, выполняющиеся в зависимости от каких-то вычисляемых ей данных, приводится преобразование, приводящее программу к "безусловному" виду, ЯПФ которого является также корректной и для исходной программы. Приводится соответству-щая теорема, обосновывапцая преобразование.

В параграфе 4 приводятся два преобразования графа для упрощения нахождения его ЯПФ. Поскольку реальные ГА состоят из нескольких областей разной размерности, их выполнение может существенно облегчить эту задачу. Одно из преобразований можно назвать условно "приведение к тесно вложенному гнезду", а в терминах ГА - размещение всех вершин в одной области с единым лексикографическим порядком. Для него предлагается также приведение к регулярному графу путем дополнения для нахождения неоптимальной, но всегда корректной (что доказывает специальная теорема) ЯПФ.

Другое преобразование позволяет находить ЯПФ отдельно по областям (перед ее нахождением добавляя к дугам внутри нее также такие, которые отражают обмен с другими областями), что фактически дает возможность рассматривать для нахо-

здения ЯПФ только регулярные графа. Условно его можно назвать "подстановка дуг". Приведен пример на рисунке, как по графу зависимостей выбирается порядок такой подстановки, а также в каком порядке следует после него находить ЯПФ отдельных областей графа. Для этого преобразования также приводится обосновывающая его теорема (о корректности ЯПФ преобразованного графа для первоначального ГА).

В главе 2 содержится описание созданного автором пакета по решению систем линейных алгебраических уравнений (СЛАУ) и его сопровождения с информацией о структурах основных его алгоритмов.

В параграфе 5 описана общая структура пакета.

В параграфе б описана его информационная часть, т.е. какую информацию содержат прилагающиеся к пакету описания программ.

Параграф 7 посвящен краткому описанию методов, применявшихся в основных программах пакета, а также общей характеристике их графов по тем их особенностям, выявлять которые позволяет методология параграфа 3. Описаны наиболее характерные для программ пакета подграфы.

Параграф 8 посвящен правилам написания фортран-программ, которых придерживался автор при составлении пакета. Кроме этого, описаны некоторые чисто технические приемы, позволяющие уменьшить количество условных операций в программах, не пользуясь при этом теми приемами "по существу", которые описаны в первой главе, а используя только стандартные средства Фортрана.

В заключении приведены следующие основные результаты

работы:

1. Разработаны требования к записи графов алгоритмов, удовлетворяющий им язык, а также конструктивная методология получения по записи графа ряда важных для параллельной реализации характеристик.

2. С использованием предложенных методов и языка исследованы и записаны структуры алгоритмов из пакета по решению систем линейных алгебраических уравнений.

Приложение 1 содержит набор синтаксических правил языков Сигма-П и Сигма.

В приложении 2 приводятся графы основных программ пакета (без версий, не отличающихся по графу), записанные на языке Сигма-П, а также ряд их характеристик.

В приложении 3 приводится список основных программ пакета, краткий перечень применяемых там методов, а также описания ряда основных програм« пакета (тоже без версий, отличающихся, скажем, только типом данных).

Основные результаты работы изложены в следующих публикациях:

1. Фролов A.B. СИША - язык описания графов алгоритмов // Архитектура ЭВМ и численные методы / ОВД АН СССР. - Ы.: ОВЫ АН СССР, 1988. - С. 129-147.

2. Фролов A.B. Принципы построения и описание языка Сигма. - И., 1989. - 27 с. /Препринт/ ОВД АН СССР: Р 236/

3. Фролов A.B. Об улучшении параллельных свойств вычислительных методов // Архитектура ЭВМ и численные методы / ОВД АН СССР. - И.: ОВЫ АН СССР, 1969. - С. 69-73.

4. Фролов A.B. Способы распознавания длинных и рассылочных дуг в графах // Архитектура ЭВМ и численные методы / ОВМ АН СССР. - Ы.: ОВМ АН СССР, 1989. - С. 74-76.

Сдано в набор, 12.11. ПО Подписано в печать 14.11.00

Формат 60x90 1/16 Печать офсетная

Усл. печ.л. 0,75 Усл.жр.-отт. 0,81 Уч.-изд.л. О.ЗЯ

Тир. ЮО экз. За*. 8700

Провзаодствеяно-вздатепьсххЯ комбвнат ВИНИТИ 140010, Люберпы Ю, Московски* обл., Октябрьски» проспект, 403