Экономичные коммутационные схемы и распараллеливание программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Адигеев, Михаил Георгиевич

• Адигеев, Михаил Георгиевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Адигеев, Михаил Георгиевич

Введение.

Глава 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 преобразования ориентированы на особенности организации памяти и коммутации в такой МВС.

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

Список литературы диссертационного исследования кандидат технических наук Адигеев, Михаил Георгиевич, 2000 год

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