автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Экономичные коммутационные схемы и распараллеливание программ

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

од

АДИГЕЕВ Михаил Георгиевич ° ~

ЭКОНОМИЧНЫЕ КОММУТАЦИОННЫЕ СХЕМЫ И РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону 2000 г.

Работа выполнена на кафедре алгебры и дискретной математики Ростовского государственного университета.

Научный руководитель: кандидат физико-математических наук, с.н.с

Штейнберг Борис Яковлевич.

Официальные оппоненты: доктор технических наук, профессор

Кодачигов Виктор Ильич.

совета К 063.52.12 Южнороссийского регионального центра информатизации высшей школы при Ростовском государственном университете по адресу: 344090, Ростов-на-Дону, пр. Стачки 200/1, корп.2, ЮГИНФО РГУ, аудитория 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ по адресу: ул. Пушкинская, 148.

Автореферат разослан «2-3 » 2000 г.

Ученый секретарь совета

кандидат физико-математических наук,

с.н.с. Муратова Галина Викторовна

кандидат технических наук, доцент Левин Илья Израилевич.

Ведущая организация: Институт Программных Систем РАН

(г. Персславль-Залесский).

Защита диссертации состоится « 4. » ¡ХЮк^Р- 2000 г. в часов на заседании специализированного диссертационного

% 9¥5.018, О

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

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

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

Этим проблемам посвящены многочисленные исследования и публикации. Среди работ по коммутации следует отметить работы В.Э. Бенеша, В.И.Неймана, A.B. Каляева, В.И. Кодачигова. Распараллеливанию

посвящены работы B.B. Воеводина, Д.Кука, М. Вольфа, К.Кеннеди,.и многие другие Связь между коммутацией и распараллеливанием обычно рассматривается в одном направлении — при разработке методов распараллеливания программ и размещения данных учитывается структура системы коммутации МВС. Некоторыми исследователями (см., например, работы Валяха, A.B. Каляева, В.И. Кодачигова) проводится также анализ систем коммутации с точки зрения их эффективности для параллельных вычислений. Однако большинством исследователей эти проблемы изучаются по отдельности, без учета их взаимной связи и влияния. <. . Таким.образом, актуальной является задача комплексного изучения проблем коммутации и распараллеливания программ.

Цель и задачи диссертации. Цель работы — комплексное изучение возможностей снижения . затрат времени на межпроцессорные пересылки данных при параллельных вычислениях.

Для достижения этой цели необходимо учитывать взаимосвязь между коммутацией и распараллеливанием. Одной фразой эту связь можно охарактеризовать следующим образом: чем универсальнее коммутация, тем проще и эффективнее выполняется распараллеливание программ и размещение данных для такой вычислительной системы. В работе изучены различные варианты соотношения «коммутация-распараллеливание». Основным ограничением для использования универсальных коммутационных систем является их достаточно высокая структурная сложность. Поэтому в диссертации основным критерием при анализе выбрана сложность коммутационной схемы, т.е. количество элементов, из которых построена схема.

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

Если система коммутации позволяет реализовать любой набор :оединений, то на размещение данных накладывается одно основное |граничение — бесконфликтность. Бесконфликтное размещение данных в юдулях памяти является отдельной очень сложной проблемой, и в данной »аботе не рассматривается. Поэтому одной из основных проблем при >азработке полнодоступной системы коммутации является экономичность юммутационной схемы. Полнодоступная разовая коммутационная схема с <f входами должна содержать не менее 0{N log N) коммутационных лементов. Схемы с такой сложностью известны, в качестве примера южно привести схему Бенеша для разделенной коммутации и схему с [етлевыми соединениями для неразделенной коммутации. Сложность аких схем по порядку роста близка к теоретическому минимуму, однако тот минимум пока еще не достигнут. Поэтому можно добиваться меньшения сложности схемы по сравнению с известными ранее схемами, а счет уменьшения множителей при NXogN и/или за счет слагаемых юрядка 0(N).

Существенно более экономичные схемы можно получить только в лассе неполнодоступных коммутационных схем. Идея состоит в том, что ;ля многих важных классов алгоритмов требуются регулярные соединения 1ежду процессорами. Поэтому можно использовать схему, эффективно еализующую лишь ограниченный, но достаточный для вычислений класс оединений (например, решетка, тор или гиперкуб). Однако при азмещении данных для таких схем надо уже обеспечивать не только есконфликтность, но и реализуемость соединений, необходимых для оступа к данным в процессе работы.

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

сочетании с преобразованиями программ приобретают первостепенно* значение. Для такой модели МВС важно изучить вопрос о том, как надс размещать данные, чтобы программа могла быть реализована на МВС бе: лишних пересылок.

В диссертации для каждого из этих вариантов построена и изучен« математическая модель. Кроме экономичности, важной характеристике? системы коммутации является наличие эффективного алгоритме построения настройки коммутационной схемы на реализацию требуемогс набора соединений. Такие алгоритмы также разработаны в диссертации.

Помимо чисто теоретического анализа, важной являете* практическая сторона проблемы. Эффективность применения в МВС toi" или иной коммутационной схемы существенно зависит от способности распараллеливающего компилятора разместить данные и преобразовать текст программы оптимальным (для используемой системы коммутации} образом. Поэтому при разработке распараллеливающих компиляторов необходимо применять специальные преобразования, ориентированные на имеющуюся систему коммутации. Такие преобразования также представлены в работе.

Объект исследования — средства уменьшения пересылок данных при параллельных вычислениях. В диссертации изучаются графовые модели коммутаторов и эффективные размещения; . данных для автоматического распараллеливания.

Методы исследований. В работе использованы методы теории графов и теории чисел, а также теории автоматического распараллеливания и преобразования программ. Для программной реализации разработанных алгоритмов преобразований программ был использован язык программирования Arity Prolog для MS DOS. .

Научная новизна н практическая ценность работы. В

1иссертации получены новые классы экономичных коммутационных ;хем. Для полученных схем разработаны алгоритмы их настройки на )еализацию заданного соединения. Также проведен анализ множества фограмм, реализуемых на МВС с фиксированными соединениями, и федложен ряд преобразований, необходимых для распараллеливания фограмм для суперкомпьютера со структурной реализацией :ычислений.

Все приведенные в диссертации теоретические результаты юлучены лично автором. Программная реализация преобразований, [редставленных в четвертой главе, также выполнена автором как часть аспараллеливаюшего компилятора, разработанного группой сотрудников, спирантов и студентов мехмата РГУ.

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

Апробация работы. Основные результаты диссертации экладывались на Всероссийской научной конференции Фундаментальные и прикладные, аспекты разработки больших определенных программных комплексов» (Абрау-Дюрсо, 1998 г.), на [еждународной научно-технической конференции «Интеллектуальные ногопроцессорные системы» (ИМС'99) (Таганрог, 1999), а также на 1учных семинарах РГУ.

Публикации. Основные результаты диссертации опубликованы в [ботах [1—7]. В совместной работе [2] автору диссертации принадлежит

описание алгоритма распределения переменных по страницам памяти и алгоритма разбиения программы на кадры.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, библиографического списка и приложения, имеются 2 таблицы и 29 рисунков. Полный объем диссертации — 143 страницы, библиографический список содержит 96 наименований работ отечественных и зарубежных авторов.

СОДЕРЖАНИЕ РАБОТЫ '

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

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

Во второй главе описывается новая схема неразделенного полнодоступного коммутатора.

Неразделенный коммутатор — это устройство, имеющее N входов (полюсов) и способное соединять входы друг с другом попарно. Для построения коммутатора с N входами будем использовать два типа коммутационных элементов: • -

* Разделенный коммутационный элемент с 2 входами и 2 выходами. Такой коммутационный элемент (будем обозначать его как РК{2)) может находиться в одном из двух возможных состояний, обозначаемых как ' = ' (рис. 2.1а) и'х'(рис. 2.16).

■ Неразделенный коммутатор НК(М) с М входами (М < N/2).

Частным случаем ' неразделенного коммутатора является неразделенный коммутатор НК(4) с 4 входами. Такой коммутатор в

любой момент времени находится в одном из трех возможных состояний, обозначаемых соответственно ' = ', 'х' и '| (см. рис.2.1).

1

2

3 1

4 2

3 1

4 2

3

4

£2

б

в

рис. 2.1

Настройка коммутатора — это отображение множества КЭ во множество состояний.

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

Структуру неразделенного коммутатора будем описывать с помощью неориентированного графа С = (УС,ЕС). Вершинами графа й являются входы коммутатора и коммутационные элементы (У%), из которых состоит коммутатор. Входы графа й (т.е. вершины множества Ух) являются висячими вершинами (имеют степень 1), вершины, соответствующие коммутационным элементам (внутренние вершины графа С) имеют степень 4.

Сформулируем условие полнодоступности неразделенного коммутатора в терминах теории графов. Два входа коммутатора соединены друг с другом, если на графе С соответствующие этим входам вершины связаны цепью. Коммутатор полнодоступен, если для любого разбиения множества входов (висячих вершин) на пары (N/2 пар) на графе й найдется N12 цепей, соединяющих вершины этих пар, причем никакие две из этих цепей не имеют общих ребер. Граф

С, обладающий этим свойством, будем называть коммутационным графом.

рис. 2.2

Во второй главе диссертации для построения полнодоступных неразделенных схем используется граф, изображенный на рис.2.2. Этот граф содержит N входов (/V = 2к, к >4), N внутренних вершин степени 4 и две вершины (А и В) степени N12. Доказано, что такой граф является коммутационным.

На основе этого графа, рекурсивно заменяя вершины А и В на аналогичные графы с N12 входами, получаем граф, содержащий только висячие вершины и вершины степени 4. Учитывая, что для 8 входов существует коммутационный граф с 6 внутренними вершинами (рис.2.3), для N входов можно получить коммутационный граф, содержащий 9

()н = N • N — N внутренних вершин степени 4.

рис. 2.3

При построении коммутатора вместо вершин степени 4 на построенном коммутационном графе подставляются коммутационные элементы. При этом на место некоторых вершин надо подставлять НК(4),,а на место других вершин можно подставлять более простые элементы РК(2).

Основным результатом второй главы является следующая теорема

Теорема 2.1 Для любых целых чисел п (п>3) и к (2 < к < п - \) существует полнодоступный неразделенный коммутатор с N = 2" входами, состоящий из (п, к) = 2" (и - к) разделенных коммутационных

п—к

элементов РК(2) и (п, к) = 2 неразделенных коммутационных элементов НК(2к)

Опираясь на теорему 2.1, найдем сложность неразделенных схем, построенных из коммутационных элементов РК{2) и НК{4).

Теорема 2.2 Для любого п (« > 3) существует'полнодоступный неразделенный коммутатор с И-2" входами, состоящий из

QP = N • log 2 A' - ^j разделенных коммутационных элементов PK(2) и

QH = —N неразделенных коммутационных элементов НК(4). 4

Следующие две теоремы содержат утверждения о сложности схем, полностью построенных из однотипных коммутационных элементов.

Теорема 2.3 Для любого п (п>3) существует полнодоступный неразделенный коммутатор с N = 2" входами, состоящий из 9

Qn~N- log2 N — N неразделенных коммутационных элементов 4

НК{ 4)

Теорема 2.4 Для любого п (л> 3) существует полнодоступный неразделенный коммутатор с N—2" входами, состоящий из Qp = N ■ log2 Л' - 2N разделенных коммутационных элементов РК(2).

Лучшей из известных ранее полнодоступных неразделенных схем является схема с петлевыми соединениями,. ..содержащая N'• log2 N - N/2 коммутационных элементов. Поэтому предложенная в диссертации схема построения коммутационных графов экономичнее предлагавшихся ранее.

Приводится алгоритм сложности 0(N log N) для настройки полученной коммутационной схемы на реализацию требуемого набора соединений.

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

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

Рассмотрим многопроцессорную вычислительную систему, состоящую из N процессорных элементов (ПЭ). Необходимо построить коммутационную схему, которая позволяла бы изменять конфигурацию данной вычислительной системы, причем множество допустимых конфигураций есть семейство двумерных решеток размера 1к х 1'к (1к ■Гк = АО для некоторого набора размеров {(1\,1[),---,(1т,1'т)}-

Формализуем задачу. Пусть V = — множество

процессорных элементов вычислительной системы. Каждый ПЭ имеет 4 входных и 4 выходных порта для соединения с соседними ПЭ. Искомая коммутационная схема должна для каждого ПЭ ук е V реализовать соединения с соседними процессорными элементами для всех конфигураций из заданного множества. Потребуем, чтобы при конфигурации, реализующей решетку /х/', для процессорного элемента ук е V соседями были — и по горизонтали и и по вертикали (все индексные выражения при \к е V понимаются по модулю /V). Очевидно, что в таком случае граф конфигурации МВС будет содержать подграф, изоморфный решетке 1x1'.

Заметим, что горизонтальные соединения у(1г±1) не зависят от

размеров решетки и присутствуют в любой конфигурации. Эти соединения сделаем фиксированными, и тогда для решения поставленной задачи необходимо построить коммутационную схему, реализующую соединения vk н» ук±/ для некоторого множества значений параметра /. Допустимыми

будут только те значения /, которые делят число N — количество процессорных элементов МВС.

. Искомая коммутационная схема £*, реализующая множество конфигураций-решеток {/, х/[,/2 х,-••,/„></„}, строится в .:: виде параллельного объединения блоков, каждый из которых реализует определенную часть соединений (схема может состоять и из одного блока). Количество'! блоков Ь и размер п блока определяются требуемым множеством конфигураций.

Каждый блок E„(s) состоит из s каскадов, каждый каскад имеет 2и' входов и 2п выходов, и содержит п коммутационных элементов (КЭ) 2x2. Один из входов (выходов) КЭ условимся называть верхним, другой вход (выход) — нижним. Соединения между каскадами коммутационной схемы £„(s)устанавливаются следующим образом:

■ верхний выход j- го КЭ к- го каскада соединен с нижним входом у-го коммутационного элемента (£+1)-го каскада;

■ нижний выход j-го КЭ А-го, каскада соединен с верхним входом (у + 2*+1 )-го коммутационного элемента (¿+1)-го каскада.

Основным результатом 3-й главы является следующая теорема (нумерация такая же; как в диссертации).

Теорема '3.3. Последовательность конфигураций-решеток {/, х/,', /jx/j, ..., lm у,1'т} (/, </2 <...</„,) реализуется коммутационной схемой Еьп с параметрами Ь-НОД{И,12 -/,,/3 -/,,...,/„ -/,} ип- N / Ь.

Общее количество КЭ коммутатора равно N ■ (flogj(// + 1)"]+ 1), где М =-—--, и ГсЛ означает наименьшее целое число, большее

- нод{1р-1,у;=1

или равное а.

В диссертации приведен также алгоритм настройки коммутационной схемы на требуемую конфигурацию. Отличительной

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

Описанная схема легко обобщается и на решетки произвольной размерности. Каждая ¿/-мерная (е?>2) решетка х/(2) х...х/(</) (/(1) •...•/(</' =//) однозначно задается вектором с из с! — 1 элемента; множество из т конфигураций-решеток задается набором {ср}трМ из т

векторов. Разложим последовательность {ся}"=1 «по координатам» —

получим й-1 последовательностей к = 1,..., (1 — 1. При

построении коммутационной схемы, реализующей семейство (/-мерных решеток, достаточно реализовать соединения по каждой «координате» в виде отдельного блока коммутационной схемы в соответствии с описанным методом построения коммутационных схем для двумерных решеток.

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

Рассматривается вычислительная система, состоящая из N процессорных элементов (ПЭ) и М модулей памяти (МП). Каждый ПЭ может выполнять некоторый набор бинарных операций (функций). Между процессорными элементами и модулями памяти установлены жесткие (фиксированные) соединения. Каждый ПЭ соединен с двумя входными модулями памяти и одним выходным.

Топологию рассматриваемой вычислительной системы будем описывать графом С = (УС, ЕС), где

• множество вершин УС есть множество ПЭ и МП;

• множество дуг ЕС задается следующим образом: для любых и, V е КО (и,у)еЕС тогда и только тогда, когда выход устройства и соединен с входом устройства V.

Тогда для любой вершины уеГС на графе С выполняются следующие условия:

в1) из V выходит не более одной дуги;

й2) в V входит ровно две дуги.

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

Определение Пусть С — произвольный граф, корневое дерево Т — его подграф. Если на б есть дуга из корня дерева Г в вершину у, не принадлежащую Т, то будем говорить, что дерево Т подвешено к вершине V. Если на, О есть контур и Т подвешено к одной из вершин этого контура, то будем говорить, что Т подвешено к данному контуру.

рис. 4.1

Доказана следующая теорема, описывающая топологию связей в рассматриваемой модели МВС.

Теорема 4.1 Если для каждой вершины графа С выполняются условия и (С2), то каждая компонента связности этого графа

состоит из контура с подвешенными к нему ОБ—деревьями, т.е. имеет вид, изображенный на рис. 4.1.

Для вычислительной системы с описанной структурой связи будем рассматривать программы, представляющие последовательность операторов вида

00 / = 1, и

/((/) =/(£(0, С(0)

где.я — константа (общая для всех операторов программы),/*,В и С —-одномерные массивы длины п, а/ — функция двух аргументов (в разных циклах функции могут быть различными).

Далее вводится понятие приведенной формы программы и доказывается, следующая лемма:

Лемма 4.1. Для любой программы П найдется программа П *, находящаяся в приведенной форме, такая, что П можно реапизовать на некоторой МВС тогда и только тогда, когда на этой МВС можно реализовать П *.

Предлагается алгоритм построения программы в приведенной форме для заданной программы П. Для программ в приведенной форме определяется граф Н = {УН, ЕН). Этот граф задает ограничения на допустимое размещение данных.

Определение Наряду с ОБ-деревьями будем рассматривать ориентированные полубинарные деревья (ОП-деревья) — они отличаются от бинарных тем, что в некоторые вершины может входить по одной дуге.

Теорема 4.2 Каждая компонента графа Н есть либо ОП-дерево, либо контур, к некоторым вершинам которого подвешены ОП-деревья.

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

Будем рассматривать МВС, для которых граф в удовлетворяет следующим дополнительным условиям однородности:

1) в — связный граф;

2) все деревья Т, (/ = 1,..., () — полные ОБ-деревья высоты И > О. Высоту деревьев Т! в графе С? будем обозначать Ь(С).

Определение Пусть С = (КС,£С) и Н = (УН,ЕН) — ориентированные графы, имеющие описанный выше вид. Вложением графа Я в граф С называется отображение <р: УН -> УС, для которого выполняется следующее свойство: если на графе Н есть дуга из вершины V''. в вершину v", то на С есть дуга из вершины <р(\'') в вершину <р{х")■

Определение Пусть Т — ОП-дерево. Для любых вершин V' и V дерева Т через 5ир(г',у") будем обозначать такую вершину у, для которой выполняются следующие условия:

а) у достижима как из V', так и из у";

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

Введем обозначения: Л(у',у'') =гшп{/г(у'),/7(у'')}-/;(5ир(у',у'')), если существует 5ир(у',у"), иначе Л(у',у") не определено; Л(Т) = шахА(у!,у") где максимум' берется по всем парам вершин у' и у",'для которых определено значение Д(у', у").

Доказаны следующие утверждения.

Лемма 4.2 Если ОП-дерево Т вложгшо вС, то ЦТ) < /г(С) +1. .

ЛЕММА 4.3 Пусть Т = (УТ, ЕТ) — ОП-дерево и /?(Т) > /г + 1. Тогда для того, чтобы дерево Т было вложгшо в. граф С, необходимо, чтобы существовала вершина у* е УТ, для которой о((у*) = И +1.

Теорема 4.3 ОП-дерево Т можно вложить в & тогда и только тогда, когда либо /¡(Г) < /г, либо выполняются условия лемм 4.2 и 4.3 одновременно.

Теорема 4.4 Если граф Н содержит контур, то он вложим в граф С тогда и только тогда, когда высота любого ОП-дерева, подвешенного к контуру графа Н, не превышает ЫО)■

Полный критерий реализуемости программы на заданной МВС без дополнительных пересылок сформулирован в виде следующей теоремы.

Теорема 4.5 Пусть архитектура МВС задается графом С?. Тогда программа П может быть выполнена на этой МВС тогда и только тогда, когда Н — граф зависимости между массивами программы П — удовлетворяет одному из следующих условий:

а) Н является ОП-деревом и для него выполняются условия теоремы 4.3;

б) граф Н содержит контур и для него выполняется условие теоремы 4.4. • .

В пятой главе разработаны и описаны преобразования, необходимые для распараллеливания программ на суперпроцессоре со структурной реализацией вычислений. Этот суперпроцессор разработан в НИИ МВС, г. Таганрог. Опнсанные преобразования вошли в состав экспериментального распараллеливающего компилятора языка Фортран для данного суперпроцессора (см. [2]).

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

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

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

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

Распараллеливающий компилятор для такой вычислительной системы должен на выходе кроме откомпилированного текста программы выдавать дополнительную информацию о размещении данных, кадрах и о перенастройке коммутатора при выполнении кадров. Поэтому помимо универсальных распараллеливающих преобразований (раскрутка и развертка циклов, перестановка и расщепление операторов, замена переменных) в данный компилятор были включены также машинно-ориентированные преобразования. В пятой главе представлены наиболее существенные из таких преобразований, разработанных автором диссертации — распределение всех переменных и массивов программы по страницам памяти и разбиение текста программы на кадры. Ограничения, накладываемые архитектурой суперпроцессора на исполняемую программу, привели к тому, что не все вычислительные программы могут быть эффективно реализованы на рассматриваемой архитектуре в исходном виде (т.е. в том виде, в котором они написаны программистом). Распараллеливающий компилятор должен адаптировать программу к архитектуре МВС с помощью набора преобразований (которые, конечно, должны сохранить семантику программы). Для распределения переменных по страницам памяти и для разбиения программы на кадры наиболее полезными оказались следующие преобразования: переименование

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

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

Приложение содержит используемых в диссертации.

список терминов

теории графов,

Основные результаты, выносимые на защиту:

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

2. Построен новый класс неполнодоступных коммутационных схем для многопроцессорных вычислительных систем с перестраиваемой структурой типа решетки; эти схемы позволяют реализовать более широкий класс решеток, чем известные ранее схемы. Разработан алгоритм настройки схемы на реализацию требуемых соединений.

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

4. Разработан и программно реализован набор преобразований, необходимых для автоматического распараллеливания программ для суперпроцессора со структурной реализацией вычислений. Эти преобразования ориентированы на особенности организации памяти и коммутации в такой МВС.

Публикации

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

1.Адигеев М.Г. Неразделенный коммутационный граф с числом 9

вершин ЛПо§2 N --N11 Математические заметки, т. 58 — 1995. — вып.З. — с. 323 - 333.

2.Адигеев М:Г.; Дубров Д.В., Лазарева C.B., Штейнберг Б.Я. Экспериментальный распараллеливающий компилятор на суперЭВМ со структурной реализацией вычислений // Всероссийская научная конференция «Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов», 21-27 сентября 1998 г., Абрау-Дюрсо. Тезисы докладов. — с. 101-108.

3. Адигеев М.Г. Вычислительные возможности МВС с распределенной памятью и фиксированными соединениями // Деп. ВИНИТИ № 272-

4. Адигеев М.Г. О методе построения коммутационных схем, реализующих семейство решеток // Деп. ВИНИТИ № 1698-В99 от 28.05.99г.

5. Адигеев М.Г. Теоретико-графовая модель МВС с программируемой структурой // Сборник «Модели и дискретные структуры» ■— Элиста, АПП «Джангар», 1999 г. —■ с. 23-29.

6. Адигеев М.Г. Коммутационная схема для систем обработки изображений // Международная научно-техническая конференция «Интеллектуальные многопроцессорные вычислительные системы»,

. 1-5 сентября 1999 г., г. Таганрог. Тезисы докладов. — с. 87-89.

7. Адигеев М.Г. Коммутационная схема для систем обработки изображений // Труды международной научно-технической конференции «Интеллектуальные . многопроцессорные системы»

ДНТП «Биос» РГУ.344006, г. Ростов-на-Доку, ул. Б. Садовая. 105. Тел 64-82-22,65-95-32. Подписано в печать 27.04.2000, Заказ № 104, Бумага офсетная,Гарнитура «Танмс»,печать офсетная. Тираж 100 экземпляров Печ. лист 1,0. Формат 60*84/16 Усл. печ.л. 1,0. Компьютерный набор и верстка. Издательско-лолчграфический комплекс «Биос» РГУ 344091, г. Ростов-на-Дону, ул/Р. 3ojire, 28/2, корпус 5 «В», 4 этаж. Лицензия на полиграфическую деятельность -V- 65-125 от 09 02.98 г.

В96 от 23.01.96.

(ИМС'99), 1-5 сентября 1999 г., г. Т с. 197-202.

Введение.

Глава 1. Проблемы коммутации и распараллеливания для суперкомпьютеров.

1.1. Основные классы суперкомпьютеров.

1.2. Системы коммутации.

1.3. Распараллеливание программ и размещение данных.

Глава 2. Полнодоступные неразделенные коммутационные схемы.

2.1. Постановка задачи и определения.

2.2. Семейство коммутационных графов, их свойства.

2.3. Построение полнодоступных неразделенных схем.

Глава 3. Коммутационные схемы для реализации семейства решеток.

3.1. Постановка задачи и определения.

3.1.1. Модель МВС.

3.1.2. Основные определения.

3.2. Описание коммутационной схемы.

3.2.1. Базовый блок коммутатора.

3.2.2. Построение коммутационной схемы из блоков.

3.3. Коммутационная схема для семейства решеток.

3.3.1. Двумерные решетки.

3.3.2. Решетки произвольной размерности.

3.4. Доказательства и вспомогательные результаты.

Цель и основные результаты диссертации.

Целью диссертации является комплексное изучение возможностей снижения затрат времени на межпроцессорные пересылки данных при параллельных вычислениях.

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

Этим проблемам посвящены многочисленные исследования и публикации. Связь между коммутацией и распараллеливанием обычно рассматривается в одном направлении — при разработке методов распараллеливания программ и размещения данных учитывается структура системы коммутации МВС [22]. Некоторыми исследователями (см., например, работы Валяха [17], A.B. Каляева [26], B.PI. Кодачигова [30]) проводится также анализ систем коммутации с точки зрения их эффективности для параллельных вычислений. Однако большинством исследователей эти проблемы изучаются по отдельности, без учета их взаимной связи и влияния.

Таким образом, поставленная в данной диссертации задача исследования комплексного подхода к проблемам коммутации и распараллеливания программ является актуальной. 5

Одной фразой связь между коммутацией и распараллеливанием можно охарактеризовать следующим образом: чем универсальнее коммутация, тем проще и эффективнее выполняется распараллеливание программ и размещение данных для такой вычислительной системы. В работе изучены различные варианты соотношения "коммутация-распараллеливание". Основным критерием при анализе выбрана сложность коммутационной схемы. Под сложностью понимается количество элементов, из которых построена схема. В качестве элементов схемы рассмотрены коммутационные элементы 2x2 (или элементы с 4 входами для неразделенных схем), так как в [41,с. 162] показано, что для систем разовой коммутации такие схемы являются наиболее экономичными.

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

Если система коммутации позволяет реализовать любой набор соединений, то на размещение данных накладывается одно основное ограничение — бесконфликтность [46]. Полнодоступная разовая коммутационная схема с N входами должна содержать не менее 0( А^к^ТУ) коммутационных элементов [41,с. 163]. Схемы с такой сложностью известны, в качестве примера можно привести схему Бенеша [13] для разделенной коммутации и схему с петлевыми соединениями [41,с. 163] для неразделенной коммутации. Сложность таких схем по порядку роста близка к теоретическому минимуму, однако этот минимум пока еще не достигнут. Поэтому можно добиваться уменьшения сложности схемы по сравнению с известными ранее схемами, за счет уменьшения множителей при Шо%Ы и/или за счет слагаемых порядка 0(Ы).

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

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

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

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

Объектом исследования являются средства уменьшения пересылок данных при параллельных вычислениях. В диссертации изучаются графовые модели коммутаторов и эффективные размещения данных для автоматического распараллеливания. Рассматриваются модели коммутаторов, действующих по принципу разовой коммутации и пространственного разделения каналов [13,41]. Все рассматриваемые в диссертации коммутационные схемы являются ординарными ([41, с.94]), т.е. могут устанавливать только соединения "один-к-одному".

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

Получены и выносятся на защиту следующие основные результаты:

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

2. Построен новый класс неполнодоступных коммутационных схем для многопроцессорных вычислительных систем с перестраиваемой структурой типа решетки; эти схемы позволяют реализовать более широкий класс решеток, чем известные ранее схемы. Разработан алгоритм настройки схемы на реализацию требуемых соединений.

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

4. Разработан и программно реализован набор преобразований, необходимых для автоматического распараллеливания программ для 8 суперпроцессора со структурной реализацией вычислений. Эти преобразования ориентированы на особенности организации памяти и коммутации в такой МВС.

Структура диссертации.

Диссертация состоит из пяти глав, библиографического списка и приложения.

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

Во второй главе описывается новая схема полнодоступного неразделенного коммутатора. Неразделенным [41, с. 115] называется такой коммутатор, у которого все полюсы равноправны, т.е. каждый полюс может быть как входом, так и выходом. Неразделенные коммутаторы рассматриваются например, в работах A.A. Архангельской, В.А. Ершова, Л.А. Бассалыго, И.И. Ерушко и В.И. Неймана [9,12,41], В.И Кодачигова [30].

Неразделенная схема разовой коммутации называется полнодоступной [12], если она способна реализовать попарное соединение полюсов (входов) при любом разбиении множества полюсов на пары. В работах [12] и [41] представлены некоторые полно доступные неразделенные схемы. Во второй главе диссертации описано новое семейство полнодоступных неразделенных коммутационных схем, содержащее меньшее количество коммутационных элементов, чем известные ранее схемы. Эти схемы строятся из коммутационных элементов 2x2 и неразделенных коммутационных элементов с 4 входами.

Структуру неразделенного коммутатора (коммутационной схемы) будем описывать с помощью неориентированного графа G. Вершинами графа G являются входы коммутатора (эти вершины имеют степень 1) и 9 коммутационные элементы (вершины степени 4), из которых состоит коммутатор. Два входа коммутатора соединены друг с другом, если на графе G соответствующие этим входам вершины соединены цепью. Коммутатор полнодоступен, если для любого разбиения множества входов (висячих вершин) на пары {N12 пар) на графе G найдется N/2 цепей, соединяющих вершины этих пар, причем никакие две из этих цепей не имеют общих ребер.

Во второй главе на основе такой графовой модели построено семейство полнодоступных неразделенных коммутационных схем. Схема с N входами (N — степень 2, N>8) из этого семейства содержит 9

N log 2 N - — N коммутационных элементов с четырьмя входами.

Известные ранее схемы (например, схема с петлевыми соединениями [12,41]) требуют большего количества коммутационных элементов.

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

В третьей главе рассматривается задача построения коммутационных схем для многопроцессорных вычислительных систем с перестраиваемой структурой типа решетки. Топологию типа решетки (без возможности реконфигурации) имеют коммуникационные сети многих вычислительных систем (например, Intel Paragon и Cray T3D [69]). Исследованию различных вопросов, связанных с коммуникационными сетями типа двумерной или многомерной решетки посвящены работы [55, 57, 61, 73,77, 78,80,86,89].

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

10 работе [55]. Полученный в диссертации класс схем содержит коммутационные схемы для более широкого класса соединений, чем в [55]. При этом все решетки, реализуемые схемами из [55], могут быть реализованы и схемами из предложенного в диссертации класса.

Постановка задачи выглядит следующим образом. Рассмотрим многопроцессорную вычислительную систему, состоящую из N процессорных элементов. Необходимо построить коммутационную схему, которая позволяла бы изменять конфигурацию данной вычислительной системы, причем множество допустимых конфигураций есть семейство двумерных решеток размера 1кх1'к {1к ^l'k=N) для некоторого набора размеров {(!х,1[),.,(1т,1'т)}.

В результате формализации данная задача сведена к задаче построения коммутационной схемы, реализующей соединения Ук\->Ук + 1 для некоторого множества значений параметра /. Разработан алгоритм, позволяющий для заданного множества размеров решеток построить коммутационную схему, реализующую множество решеток с указанными размерами. Получена формула для количества коммутационных элементов в построенной схеме. Разработанный алгоритм обобщен также на случай решеток произвольной размерности.

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

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

11

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

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

В пятой главе разработаны и описаны преобразования программ, необходимые для выполнения программ на супер-ЭВМ со структурной реализацией вычислений [23,24,25,29,37,38,39,42]. Описанные преобразования вошли в состав экспериментального распараллеливающего компилятора языка Фортран для суперпроцессора, разработанного в НИИ МВС, г. Таганрог (см. [2] и [23]).

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

12

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

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

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

Распараллеливающий компилятор для рассматриваемой вычислительной системы должен на выходе кроме откомпилированного текста программы выдавать дополнительную информацию о размещении данных, кадрах и о перенастройке коммутатора при выполнении кадров. Поэтому помимо универсальных распараллеливающих преобразований — раскрутка и развертка циклов, перестановка и расщепление операторов, замена переменных (см., например, [18]) — в данный компилятор были включены также машинно-ориентированные преобразования. В пятой главе представлены наиболее существенные из таких преобразований, разработанных автором диссертации — распределение всех переменных и массивов программы по страницам памяти и разбиение текста программы на кадры.

Ограничения, накладываемые архитектурой суперпроцессора на исполняемую программу, привели к тому, что не все вычислительные программы могут быть эффективно реализованы на рассматриваемой архитектуре в исходном виде, то есть в том виде, в котором они написаны программистом. Распараллеливающий компилятор должен адаптировать программу к архитектуре МВС с помощью набора преобразований (которые, конечно, должны сохранить семантику программы). Для распределения переменных по страницам памяти и для разбиения программы на кадры наиболее полезными оказались следующие преобразования: переименование переменных, замена вхождений переменной на ее значение (обобщение операции протягивания констант) и расщепление оператора (вершины) [18]. Поскольку при формировании кадров необходимо проверять существование подходящего размещения данных и настройки коммутатора, процедура разбиения программы на кадры должна быть многоступенчатой. Если на очередном шаге выясняется, что анализируемый оператор не может быть включен в текущий кадр (даже после применения преобразований), компилятор должен произвести откат к предыдущему сформированному кадру.

14

Одновременно производится размещение данных по модулям распределенной памяти.

Приложение содержит список терминов теории графов, используемых в диссертации.

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

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

Основные результаты диссертации опубликованы в работах [1-7]. В совместной работе [2] автору диссертации принадлежит описание алгоритма распределения переменных по страницам памяти и алгоритма разбиения программы на кадры.

ЗАКЛЮЧЕНИЕ

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

Получены следующие основные результаты:

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

2. Построен новый класс неполнодоступных коммутационных схем для многопроцессорных вычислительных систем с перестраиваемой структурой типа решетки; эти схемы позволяют реализовать более широкий класс решеток, чем известные ранее схемы. Разработан алгоритм настройки схемы на реализацию требуемых соединений.

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

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

127 преобразования ориентированы на особенности организации памяти и коммутации в такой МВС.

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

1. N log 2 N — N // Математические заметки, т. 58 — 1995. — вып.З. — с. 323 -333.

2. Адигеев М.Г. Вычислительные возможности МВС с распределенной памятью и фиксированными соединениями // Деп. ВИНИТИ № 272-В96 от 23.01.96.

3. Адигеев М.Г. О методе построения коммутационных схем, реализующих семейство решеток // Деп. ВИНИТИ № 1698-В99 от 28.05.99г.

4. Адигеев М.Г. Теоретико-графовая модель МВС с программируемой структурой // Сборник "Модели и дискретные структуры" — Элиста, АЛЛ "Джангар", 1999 г. — с. 23-29.

5. Адигеев М.Г. Коммутационная схема для систем обработки изображений // Международная научно-техническая конференция "Интеллектуальные многопроцессорные вычислительные системы", 15 сентября 1999 г., г. Таганрог. Тезисы докладов. — с. 87-89.129

6. Адигеев М.Г. Коммутационная схема для систем обработки изображений // Труды международной научно-технической конференции "Интеллектуальные многопроцессорные системы" (ИМС'99), 1-5 сентября 1999 г., г. Таганрог. — с. 197-202.

7. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. — М.: "Радио и связь" ,1991. — 248 с.

8. Архангельская A.A., Ершов В.А., Нейман В.И. Автоматическая коммутация каналов связи. — М.: "Связь", 1970. — 192 с.

9. Архангельская В.М. Элементарная теория чисел. — Изд-во Саратовского университета, 1963. — 126 с.

10. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —М.: "Мир", 1979. — 536 с.

11. Бассалыго J1.A., Грушко И.И., Нейман В.И. Некоторые теоремы о структурах неразделенных систем разовой коммутации // Проблемы передачи информации — 1962 — т. V. — №2 — с. 45-52.

12. Бенеш В.Э. Математические основы теории телефонных сообщений. — М.: "Связь", 1968 г. — 292 с.

13. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов //Кибернетика — 1982 — №2. — с. 51-62.

14. Вальковский В.А. Параллельное выполнение циклов. Метод пирамид // Кибернетика— 1983. —№5. — с.51-55.

15. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. — М.: "Радио и связь", 1989. — 176 с.130

16. Валях Е. Последовательно-параллельные вычисления. — М.: "Мир", 1985 —456 с.

17. Векторизация программ: теория, методы, реализация. Сборник статей. — М., "Мир", 1991 г. — 272 с.

18. Воеводин В.В. Математические модели и методы в параллельных процессах — М.: "Наука", 1986 г. — 296 с.

19. Воеводин В.В. Математические основы параллельных вычислений — М.: Изд-во Моск. ун-та, 1991 г. — 345 с.

20. Воеводин Вл. В. Теория и практика исследования параллелизма последовательных программ // Программирование. — 1992. — №.3. С.38-54.

21. Каляев A.B., Каляев И.А., Левин И.И., Пономарев И.М. Базовый модуль для построения реконфигурируемых под задачу вычислительных систем // «Известия вузов. Электроника» — 1998. —№ 4. — с. 67-74.

22. Каляев A.B. Многопроцессорные системы с программируемой архитектурой // М.: "Радио и связь", 1984. — 240 с.

23. Каляев A.B. Однородные коммутационные регистровые структуры. — М.: "Сов. радио", 1976. — 372 с.

24. Каляев A.B., Фрадкин Б.Г., Левин ИИ. Унифицированная элементная база для построения реконфигурируемых под задачу вычислительных систем // «Известия высших учебных заведений. Электроника» — Москва, 1997. — №1 — с. 74-83.

25. Кодачигов В.И. Электронная коммутация информационных каналов. — Изд-во Ростовского университета, 1983. — 208 с.

26. Корнеев В.В., Хорошевский В.Г. Структура и функциональная организация вычислительных систем с программируемой структурой. Препринт ОВС-11. — Новосибирск, 1979. — 47 с.132

27. Кратко М.И., Павленко В.А. О множествах подстановок, порождаемых коммутационными графами // Препринт института математики АН УССР — 1981,—№ 15 —с. 21-33.

28. Крицкий С.П. Логико-грамматические средства спецификации и реализации языков программирования // Кандидатская диссертация — Ростов-на-Дону, 1990. —125 с.

29. Крицкий С.П. Логические средства проектирования языкового интерфейса // Тезисы докладов конференции "Диалог "Человек-ЭВМ". Часть 2. Свердловск. 1989. С.30-32.

30. Крицкий С.П. Предикативные грамматики в интеллектуальных системах // Всесоюзн. научно-практич. семинар "Интеллектуальное программное обеспечение ЭВМ". 13-19 мая 1990. Тезисы докладов. 4.1. Ростов-на-Дону-Терскол, 1990. С. 56-57.

31. Лазарева С. А. Многоуровневое представление программ и его использование в автоматическом распараллеливании // Математическое моделирование. — 1997. —т. 9 — №2 — с. 31-33.

32. Левин И.И. Сопроцессор для решения задач математической физики структурно-процедурным методом распараллеливания //В кн. «Анализ эффективности вычислительных систем» / Под ред. Я.А. Дуброва — Львов, 1991. —ПрепринтНТЦ "Интеграл". — № 7-91. — с.14-21.133

33. Левин И.И., Шматок A.B. Технология параллельных индуктивных программ // Труды международной научно-технической конференции "Интеллектуальные многопроцессорные системы" (ИМС'99), 1-5 сентября 1999 г., г. Таганрог. — с. 142-146.

34. Метлицкий Е.А., Каверзнев В.В. Системы параллельной памяти. Теория, проектирование, применение.— Ленинград, ЛГУ, 1989.

35. Нейман В.И. Структуры систем распределения информации. — 2-е изд., перераб. и доп. — М.: Радио и связь, 1983. — 216 с.

36. Пономарев И.М. Методы преобразования задач в структурно-процедурную форму // Труды международной научно-технической конференции "Интеллектуальные многопроцессорные системы" (ИМС'99), 1-5 сентября 1999 г., г. Таганрог. — с. 147-150.

37. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением — М.: Энергоатомиздат, 1983. — 312с.

38. Фролов A.B. Оптимизация размещения массивов в Фортран-программах на многопроцессорных вычислительных системах II Программирование — 1998. —№3. — с. 70-80.

39. Харари Ф. Теория графов. —М.: Мир, 1973. — 302 с.

40. Штейнберг Б.Я. Бесконфликтные размещения массивов при параллельных вычислениях // Кибернетика и системный анализ — 1998. — №1 — с. 166-178.

41. Штейнберг Б.Я. Оптимальные параллельные переразмещения двумерных массивов // Программирование — 1993. — №6 — с. 81-87.134

42. Штейнберг Б.Я. Оптимальные параллельные переразмещения многомерных массивов // Труды международной научно-технической конференции "Интеллектуальные многопроцессорные системы" (ИМС'99), 1-5 сентября 1999 г., г. Таганрог. — с. 151-155.

43. Adda М. A scalable multibus configuration for connecting transputer links // IEEE Trans. Parallel and Distrib. Syst. — 1997. — vol. 8. — № 3. — March 1997. — pp. 245-253.

44. Agrawal J., Zhang Y. A fast and low cost self-routing permutation network // IEEE Trans. Computers — 1998. — vol. 47. — № 9. — September 1998. — pp. 1033-1036.

45. Anderson J.M., Lam M.S. Global optimizations for parallelism and locality on scalable parallel machines // Proceedings of SIGPLAN'93 Conference on Programming Language Design and Implementation (PLDI). Albuquerque, New Mexico, June 23-25, 1993.

46. Bagherzadeh N., Dowd M., Nassif N. Embedding an arbitrary binary tree into the star graph // IEEE Trans. Computers — 1996. — vol. 45. — № 4. — April 1996. — pp. 475-482.

47. Banerjee U., Chen S. C., Kuck D., Towle R. Time and Parallel Processor Bounds for Fortran-like Loops // IEEE Trans. Computers. — 1979. C-28. — №.9. — September 1979. — pp.660-670.

48. Bettayeb S., Cong В., Girou M., Sudborough I.H. Embedding star networks into hypercubes // IEEE Trans. Computers — 1996. — vol. 45. — № 2. — February 1996. — pp. 186-194.135

49. Bliandarkar S.M., Arabnia H.R. Parallel computer vision on a reconflgurable multiprocessor network // IEEE Trans. Parallel and Distrib. Syst. — 1997. — vol. 8. — № 3. — March 1997. — pp. 292-309.

50. Bokhari S.H. Multiphase complete exchange: a theoretical analysis // IEEE Trans. Computers — 1996. — vol. 45. — № 2. — February 1996. — pp. 220-229.

51. Bokka V., Gurla H., Olariu S., Schwing J.L. Constant-time algorithms for constrained triangulations on reconflgurable meshes // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 11. — November 1998. — pp. 1057-1072.

52. Cao F., Du D.-Z., Hsu D.F., Teng S.-h. Fault tolerance properties of pyramid networks // IEEE Trans. Computers — 1999. — vol. 48. — № 1. — January 1999. — pp. 88-93.

53. Day K., Al-Ayyoub A.-E. The cross product of interconnection networks // IEEE Trans. Parallel and Distrib. Syst. — 1997. — vol. 8. — № 2. — February 1997, —pp. 109-117.

54. De Azevedo M.M, Bagherzadeh N., Latifi S. Low expansion packings and embeddings of hypercubes into star graphs: a performance-oriented approach // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 3. — March 1998. — pp. 261-274.

55. Fernandez-Zepeda J.A., Vaidyanathan R., Trahan J. Scaling simulation of the fusing-restricted reconflgurable mesh // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 9. — September 1998. — pp. 861-871.136

56. Fray D.Q.M., Das P.K. Hardware Reconfiguration of Transputer Networks for Distributed Object-Oriented Programming // Microprocessing and Microprogramming — 1987. — vol. 21. — pp. 623-628.

57. Fu A. W.-c., Chau S.-C. Cyclic-cubes: a new family of interconnection networks of even fixed-degrees // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 12. — December 1998. — pp. 1253-1268.

58. Gravenstreter G., Melhem R.G. Realizing common communication patterns in partitioned optical passive stars (POPS) networks // IEEE Trans. Computers1998. — vol. 47. — № 9. — September 1998. — pp. 998-1013.

59. Greene W., Pooch U.W. A review of classification schemes for computer communication networks // Computer. — 1977. — November. — pp. 12-21.

60. Guo W., Oruç A.Y. Regular sparse crossbar concentrators // IEEE Trans. Computers — 1998. — vol. 47. — № 3. — March 1998. — pp. 363-368.

61. Gupta V., Schenfeld E. Annealed embeddings of communication patterns in an interconnection cached network // IEEE Trans. Parallel and Distrib. Syst.1995, —vol. 6. — № 11, — November 1995,— pp. 1153-1167.

62. Ho C.-T., Johnsson S.L. Embedding hyperpyramids into hypercubes // IBM Journal of research and development — 1994. — vol.38. — №1 — pp. 3145.

63. Hockney R. Classification and Evaluation of Parallel Computer Systems // Lecture Notes in Computer Science — 1987. — N 295. — pp. 13-25.

64. Hu Q., Shen X., Liang W. Optimally routing LC permutations on k-extrastage cube-type networks // IEEE Trans. Computers — 1996. — vol. 45. — № 1. — January 1997, —pp. 97-103.137

65. Hu Q., Shen X., Yang J. Topologies of combined (21ogN l)-stage interconnection networks // IEEE Trans. Computers — 1997. — vol. 46. — № 1. — January 1997. — pp. 118-124.

66. Hwang F.K. A modification to a decomposition algorithm of Gordon and Srikanthan // IEEE Trans. Computers — 1997. — vol. 46. — № 8. — August 1997,—pp. 958-960.

67. Kim G., Yoon H. On submesh allocating for mesh multicomputers: a best-fit allocation and a virtual submesh allocation for faulty meshes // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 2. — February 1998. — pp. 175-185.

68. Ku H.-K., Hayes J.P. Systematic design of fault-tolerant multiprocessors with shared buses // IEEE Trans. Computers — 1997. —vol. 46. — № 4. — April 1997. — pp. 439-455.

69. Lamport L. The coordinate method for the parallel execution of DO-loops. // Sagamore computer conference on parallel processing, 1973.

70. Lamport L. The parallel execution of DO loops // Commun. ACM. — 1974. — vol. 17 — №.2. — pp. 83-93.

71. Lau F.C.M, Chen G. Optimal layouts of midimew networks // IEEE Trans. Parallel and Distrib. Syst. — 1996. — vol. 7. — № 9. — September 1996. — pp. 954-961.

72. Lee S.-K., Choi H.-A. Embedding of complete binary trees into meshes with row-column routing // IEEE Trans. Parallel and Distrib. Syst. — 1996. — vol. 7. — № 5. — May 1996. — pp. 493-497.138

73. Lin M.-B., Oru9 A.Y. The design of an optoelectronic arithmetic processor based on permutation networks // IEEE Trans. Computers — 1997. — vol. 46. — № 2. — February 1997. — pp. 142-153.

74. Lin R., Olariu S., Schwing J.L., Wang B.-F. The mesh with hybrid buses: an efficient parallel architecture for digital geometry // IEEE Trans. Parallel and Distrib. Syst. — 1999. — vol. 10. — № 3. — March 1999. — pp. 266-280.

75. Lin W., Wu C.L. A distributed resource management mechanism for a partitionable multiprocessor system // IEEE Trans. Computers. — 1988. — vol.37 — № 2. — February 1988. — pp. 201-210.

76. Liu G., Lee K.Y., Jordan H.F. TDM and TWDM de Brrnjn networks and ShuffleNets for optical communications // IEEE Trans. Computers — 1997. — vol. 46. — № 6. — June 1997. — pp. 695-701.

77. Nakano K., Olariu S. An efficient algorithm for row minima computations on basic reconfigurable meshes // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 6. — June 1998,—pp. 561-569.

78. Opartny J., Sotteau D., Srinivasan N., Thulasiraman K. DCC linear congruential graphs: a new class of interconnection networks // IEEE Trans. Computers — 1996. — vol. 45. — № 2. — February 1996. — pp. 156-164.

79. Pearlmutter B.A. Doing the twist: diagonal meshes are isomorphic to twisted toroidal meshes // IEEE Trans. Computers — 1996. — vol. 45. — № 6. — June 1996. — pp. 766-767.139

80. Protic J., Tomasevic M., Milutinovic V. Distributed shared memory: concepts and systems // IEEE Trans. Parallel and Distributed Technology — Summer 1996. — pp. 63-79.

81. Ratha N.K., Jain A.K. Computer vision algorithms on reconfigurable logic arrays // IEEE Trans. Parallel and Distrib. Syst. — 1999. — vol. 10. — № 1.

82. January 1999. — pp. 29-43.

83. Shen X., Liang W., Hu Q. On embedding between 2D meshes of the same size // IEEE Trans. Computers — 1997. — vol. 46. — № 8. — August 1997.pp. 880-889.

84. Siegel H.J. A model of SIMD machines and a comparison of various interconnection networks // IEEE Trans. Computers. — 1979. — vol. c-28.12, —December 1979,—pp. 907-917.

85. Sovis F. Theory and construction of shuffle-exchange type permutation networks // Computer and artificial intelligence. — 1985. — t.4. — №4. — c. 367-384.

86. Szymanski T.H. Design principles for practical self-routing nonblocking switching networks with 0(N • log N) bit-complexity // IEEE Trans. Computers — 1997. — vol. 46. — № 10. — October 1997. — pp. 10571069.

87. Treleaven P.C. Parallel architecture overview // Parallel Computing. —1998.8.— pp. 59-70.

88. Vadapalli P., Srimani P.K. A new family of Cayley graph interconnection networks of constant degree four II IEEE Trans. Parallel and Distrib. Syst. — 1996. — vol. 7. — № 1, —January 1996. — pp. 26-32.140

89. Wang C.-F., Sahni S. Basic operations on the OTIS-mesh optoelectronic computer // IEEE Trans. Parallel and Distrib. Syst. — 1998. — vol. 9. — № 12. — December 1998. — pp. 1226-1236.

90. Yang Y. A class of interconnection networks for multicasting // IEEE Trans. Computers — 1998. — vol. 47. — № 8. — August 1998. — pp. 899-906.141