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

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

ЛЕВИН Илья Израилевич

МЕТОДЫ И ПРОГРАММНО-АППАРАТНЫЕ СРЕДСТВА ПАРАЛЛЕЛЬНЫХ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ

Специальности: 05.13.11 — "Математическое и программное

обеспечение

вычислительных машин, комплексов и компьютерных сетей1'

05.13.15 - "Вычислительные машины и системы"

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

Таганрог-2004

Работа выполнена на кафедре "Интеллектуальные многопроцессорные системы" (ИМС) ТРТУ и Южного научного центра РАН, а также в Научно-исследовательском институте многопроцессорных вычислительных систем (НИИ МВС) Государственного образовательного учреждения высшего профессионального образования "Таганрогский государственный радиотехнический университет" (ТРТУ).

НАУЧНЫЕ КОНСУЛЬТАНТЫ:

академик РАН, доктор технических наук, профессор Каляев Анатолий Васильевич,

член-корреспондент РАН, доктор технических наук, профессор Каляев Игорь Анатольевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

член-корреспондент РАН, доктор технических наук, профессор

Хорошевский Виктор Гаврилович

доктор технических наук, профессор Кравченко Павел Павлович

доктор технических наук, старший научный сотрудник Аграновский Александр Владимирович

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: Институт проблем информатики РАН

(ИПИ РАН), г. Москва

Защита состоится "8"октября 2004 г. в 1400 на заседании диссертационного совета Д 212.259.05 в Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, ул. Чехова, 2, корп. И, комн. 347.

С диссертацией можно ознакомиться в библиотеке ТРТУ.

Автореферат разослан и М " августа 2004 г.

Просим Вас прислать отзыв, заверенный печатью учреждения по адресу: 347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44, Таганрогский государственный радиотехнический университет Ученому секретарю диссертационного совета Д 212.259.05 Кухаренко А.П.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

А.П. Кухаренко

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

Актуальность темы. Суперкомпьютеры предназначены для решения сложнейших проблем современности, требующих обработки гигантских объемов информации в короткие промежутки времени. Создание и использование суперкомпьютеров относится к факторам стратегического развития науки и техники и входит в первую десятку приоритетных технологий развитых стран. Без суперкомпьютеров невозможно моделировать экономические и социальные системы, прогнозировать экологические процессы и природные геофизические явления, разрабатывать важнейшие техногенные объекты, решать проблемы космонавтики, астрофизики, медицины. Развитие микроэлектроники и создание семейств высокопроизводительных микропроцессоров привело к тому, что доминирующим направлением построения суперкомпьютеров в настоящее время являются многопроцессорные вычислительные системы (МВС) с массовым параллелизмом, содержащие тысячи параллельно функционирующих микропроцессоров. О темпах развития вычислительной техники говорит тот факт, что два десятилетия назад наиболее мощные. суперкомпьютеры имели производительность в несколько Гфлопс; в настоящее время эксплуатируются суперкомпьютеры с производительностью более триллиона операций в секунду, наиболее мощные суперкомпьютеры имеют производительность, превышающую 50 Тфлопс, и разрабатываются системы с производительностью от 100 до 1000 Тфлопс.

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

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

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

I ч*- Л. ■

г >>

' ' " У /

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

Решением данной проблемы занимались такие видные ученые как Э. Дейкстра, Ч. Хоар, Р. Хокни, В. Хейдлер, Д. Чамберлсн, а также российские ученые: B.C. Бурцев, В.Е. Котов, В.К.Левин, Д.А. Поспелов, В.Г. Хорошевский, В.В.Воеводин, В.А Вальков-ский и многие другие. Однако их исследования были ориентированы на разработку методов и аппаратно-программных средств параллельных вычислений для традиционной (жесткой) архитектуры МВС, что обеспечивает высокую реальную производительность только для некоторых классов задач.

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

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

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

В соответствии с поставленной целью определены задачи диссертации:

1) Провести анализ методов и моделей параллельных вычислений и на их основе разработать основные принципы эффективных структурно-процедурных вычислений.

2) Разработать формальные математические методы преобразования алгоритмов задач различных классов в структурно-процедурную форму, обеспечивающие решение за-

дач с реальной производительностью, близкой к пиковой производительности системы, для различных степеней распараллеливания.

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

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

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

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

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

Научная новизна диссертации заключается в том, что в ней впервые:

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

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

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

4) В языке программирования высокого уровня предложено следующее ограничение правила единственной подстановки, широко используемой в языках потоков данных для представления неявного параллелизма: каждая переменная в программе получает значение один раз в теле описания вычислительной структуры кадра, что обеспечивает детерминизм реализации параллельной программы и позволяет достигнуть взаимноод-

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

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

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

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

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

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

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

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

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

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

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

коэффициент использования оборудования на 40% и сократить время прохождения задач на 20-30%.

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

5) Разработать и создать элементную базу для построения МВС со СПОВ, с минимальной номенклатурой и четко обозначенными функциями. Технические решения защищены четырьмя патентами РФ.

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

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

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

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в НИИ МВС ТРТУ, непосредственным участником которой являлся автор диссертации. Результаты диссертации внедрены в ОАО "Научно-исследовательский центр электронной вычислительной техники" (НИЦЭВТ), г. Москва; Московском государственном институте электронной техники (технический университет), г. Москва; в/ч 26165, г. Москва; в/ч 25714, г. Курск; Таганрогском государственном радиотехническом университете, г. Таганрог, НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог; Научно-конструкторском бюро вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях: International Conference "Parallel Computing Technologies (PaCT)", Novosybirsk, 1991; Yaroslavl, 1997; Всероссийская научно-техническая конференция с международным участием "Теория цепей и сигналов", Новочеркасск, 1996; VI международный семинар "Распределенная

обработка информации", Новосибирск, 1998; IV, V Всероссийские научно-технические конференции '"Нейрокомпьютеры и их применение", Москва, 1998 - 1999; Международные конференции "Интеллектуальные многопроцессорные системы (ИМС'99)", Таганрог, 1999, пос. Дивноморское, 2001,2003; Международная конференция "Искусственный интеллект",-Кацивели, 2000, 2002; Международная научно-техническая конференция "СуперЭВМ и многопроцессорные вычислительные системы", Таганрог, 2002; Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000; Третья международная научно-техническая конференция "Электроника и информатика - XXI век", Зеленоград-Москва, МИЭТ, 2000; Между народная конференция "Параллельные вычисления и задачи управления (РАСО'2001)", М: ИПУ РАН им. В.А.Трапезникова, 2001; Конференция "С.А. Лебедев и развитие отечественной вычислительной техники", Москва, ИПИ РАН, 2002; Всероссийская научная конференция "Методы и средства обработки информации", Москва, ф-т вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2003.

Основные положения, выносимые на защиту:

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликованы 102 печатные работы, в том числе, 1 монография, 30 статей в центральной печати, из них 10 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК, получено 4 патента на изобретение.

Структура и объем диссертации. Диссертация состоит из введения, шести разделов, заключения и списка литературы из 232 наименований. Она содержит 363 страницы текста, 11 таблиц, 156 рисунков, 62 страницы приложений.

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

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

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

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

В последнее время появились реконфигурируемые системы, позволяющие синтезировать вычислительные структуры, адекватные решаемой задачи. Однако такие системы перестраиваются с одной структуры на другую за очень большое время, что ограничивает их применение для различных классов задач, таких как система НС Starbridge, или применяются только для систолических вычислений и сводимых к ним задач, например, система Xputer.

Альтернативой существующим МВС с массовым параллелизмом являются многопроцессорные вычислительные системы с программируемой архитектурой, концепция которых разработана в Научно-исследовательском институте многопроцессорных систем ТРТУ под руководством академика РАН А.В. Каляева. МВС с программируемой архитектурой обеспечивает пользователю возможность формировать в универсальной системе виртуальные специализированные вычислители, адекватные структуре решаемой задачи, что выводит на передний план "внутренний" параллелизм задачи. В тоже время формальные методы синтеза структурно-процедурных решений для задач различных классов не созданы.

Для более детального анализа целесообразно рассмотреть общую структуру задачи - информационный граф алгоритма. В информационном графе вершины соответствуют

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

Если множество вершин V информационного графа (7 может быть представлено в виде объединения некоторых непересекающихся подмножеств

таких, что если вершина , а вершина и существует дуга то такое

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

Для мультипроцедурных методов организации параллельных вычислений широкое распространение получили ярусно-параллельные формы (ЯПФ). Представление графа алгоритма в ярусно-параллельной форме заключается в упорядочении вершин графа по подграфам разбиения (1). Упорядоченные подмножества называются ярусами. Множество нулевого яруса ^определяет совокупность входных вершин X. В общем случае, вершина принадлежит ярусу тогда и только тогда, когда существует, по крайней мере, хотя бы одна дуга А-(с, где с — вершина, принадлежащая ярусу с номером !-/. Данное утверждение можно записать в реляционном исчислении следующим образом:

К- = {с\А({с. ф) л уи(ф}. (2)

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

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

С-((Х.Лх),(О.Л^.(У,Аг)Х (3)

где Х- множество входных вершин графа, У- множество выходных вершин, Q - множество операционных вершин.

Объединение множеств входных дуг Ах, операционных дуг Ад и выходных дуг А у описывает информационные связи в задаче. Для любой дуги (иу), принадлежащей к Ах, вершина и еХ, а вершина Для любой дуг1{51щ1рнадлежащей ш и н а u€Q

и вершина г>е£>. Для любой дуг^принадлежащей к^е р ш и н шина

veY.

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

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

(4)

таких, что если вершина и вершина и существует хотя бы одна дуга

то Будем называть дуги, соединяющие подграфы, - внешними, а дуги, принадлежащие подграфу Р{, - внутренними. Данное разбиение коренным образом отличается от ранее рассмотренных разбиений (1, 2) возможностью связей внутри фрагментов.

Подграфы информационного графа задачи, последовательно реализуемые на многопроцессорной системе, принято называть кадрами, а механизм последовательного обхода информационного графа задачи подграфами - структурно-процедурной программой. Кадр представляет собой структурно-реализованный подграф задачи, через который следует поток данных. Подобная организация вычислений обеспечивает максимальную скорость обработки данных, сопоставимую со скоростью специализированных вычислителей. Вычисления выполняются по принципу управления потоком данных и не требуют синхронизации. Настройка на кадры производится по единой управляющей программе, что обеспечивает фон-неймановский детерминизм. Кадр часто описывается как объект, определенный в виде тройки <0,/,О>, где (2 - функциональный граф кадра; I, О - множество информационных потоков. На практике зачастую понимается, что информационные потоки, входящие в кадр, однозначно определены и соответствуют появлению входных данных в заданном временном масштабе. Однако, как показали проведенные исследования, такой взгляд на информационные потоки кадра является частным случаем. На рис.1, представлено графическое изображение кадра. Несложно заметить, что вышеприведенное определение кадра соответствует кортежу элементарных кадров - размер информационных потоков на входе (выходе) кадра.

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

Рис 1. Графическое изображение кадра.

ко один результат. Элементарный кадр определяется тройкой где Л-,, и У, - это

множества входных и выходных вершин, соответствующие информационному потоку в определенный момент времени. Множества входных и выходных вершин элементарного кадра К/ можно определить следующим образом: X/ = ¡(¡¡), У] — 0(1/).Следует отметить,

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

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

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

Рис.2. Кортеж изоморфных кадров.

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

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

Если существуют два изоморфных подграфа <7/ и См, не являющиеся информационно независимыми, и существует единственная дуга, начальная вершина которой является е С?|, а конечной вершиной я в л я и не существует другого пути информационной зависимости между подграфами С/ И См, то п о д г р аЗфш<мо ж н о упорядочить в кадр, при этом имеется единственное правило упорядочивания <С,,02>, определенное дугой <аи1>2 >■• В этом случае производится дополнительное преобразование информационного графа. Формируется дуга, соединяющая вершину а и вершину Ь. На эту дугу вводится начальный элемент, обеспечивающий реализацию обратной связи. Начальное значение определяется начальной вершиной дуги, входящей в граф С;. Вершина ^ соответствует вершине ^ (графы С/ и С; изоморфны). Дуги сд^,^ > и >

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

Данные преобразования расширены на произвольное количество подграфов. Если имеется множество изоморфных подгра-

Рис.З. Преобразование связанных информационных графов в кадр.

фов С/,См,...С,,, являющихся информационно-зависимыми только по смежным дугам , соединяющим подграфы С/, (начальной вершиной дуг смежности является а, еС5у, конечной вершиной - ¿>( е и вершина <7| является соединенной с входной вершиной Xто под графы С7;,(7',...С?,, могут быть преобразованы в кадр, причем, правило упорядочивания подграфов определяется путем, связующим подграфы Пример такого графа показан на рис.4.

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

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

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

общем случае выделяется функциональная зависимость между начальной вершиной a¡ е G¡ и конечной вершиной ¿y^j е G^/j ■ Следует отметить, что связь может быть не

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

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

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

Будем называть информационным кадром следующую тройку: К =< R,Q,W >, где

R - узел чтения; Q- структурно-реализованный подграф задачи; W- узел записи. Здесь

й= U<fl;,r/>. (5)

где N(Á) - мощность множества входных дуг кадра А.

Аналогично узел записи представляет собой объединение упорядоченных пар:

W = "{]<bj,wj>, (6)

где - мощность множества выходных дуг кадра.

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

таких, что если существует хотя бы одна дуга (а,Ь) и вершина а е Si¡¡, а вершина Ь е Si¡¡, то i<j. Подграфы S¡j будем называть слоями. При этом дуги, соединяющие слои, будем называть межслойными дугами, а дуги, соединяющие операционные вершины одного слоя, будут внутрислойными дугами. Наконец, каждый подграф S,j можно представить в виде множества подграфов

при этом все подграфы g,j¿ должны быть изоморфны друг другу. Подграфы gщ будем называть базовыми подграфами.

Кроме того, выполняются следующие условия. Внутрислойные дуги должны прина-

длежать какому-нибудь базовому подграфу. Если существует дуга (a,b) е S,j. то вершина aeg,jh и вершина beg,jk. Как следствие, не существует дуг, соединяющих вершины, принадлежащие базовым подграфам одного слоя. Базовый подграф gljk soi^ и только тогда, когда существует, по крайней мере, одна дуга (а.Ь) такая, что аецч.,1„и ЬеЦф

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

(9)

где Fm — функция, отображающая дуги базового подграфа на базовый подграф

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

Если в результате выполнения секвенции в подграфе Рт подграфы g, „ j е S, „ и изоморфны для всех значений и существуют обобщающие функции

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

При функциональном секвентировании фрагменты Р, являются функционально-регулярными P,~0,(F,(gJ). Информационный граф алгоритма задачи, представленный в этом виде, будет называться функционально-регулярной формой графа вычислительною процесса решения задачи.

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

При формировании кадра происходит объединение множеств входных (выходных) информационных вершин в функциональный узел чтения (записи), дугам которого поставлен в соответствие кортеж функций. Элемент кортежа функций чтения ставит в соответствие моменту времени / множество (группу) входных информационных вершин х. Формируется операционная структура кадра, которая описывается графом Q=(Vç, A/J.

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

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

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

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

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

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

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

где Ог^с - адрес чтения в канале РП с логическим номером с в момент времени

а(к,с) - номер элемента вектора коммутации чтения, значение которого в момент времени равно с.

Аналогично, с-й элемент еыс кортежа функций исполнительной адресации записи /^»'определяется следующим образом:

где - адрес записи в канале РП, имеющем логический номер в момент времени

(10)

(11)

Р(Кс) - номер элемента кортежа функций коммутации записи, значение которого в момент времени равно с.

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

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

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

к2.

Массивы данных отображаются на множество адресов распределенной памяти.

Управляющая программа смены кадров и процедуры обращения к каналам распределенной памяти осуществляется в контроллере распределенной памяти (^П).

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

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

а

Рис.5. Отображение кадровой структуры на архитектуру МВС ПА.

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

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

Время выполнения кадра можно определить по следующей формуле:

Г* =/,(» + /„+г-Л, (12)

где - время заполнения конвейера графа кадра;

- время настройки на кадр;

N - размер потока данных, следующих через кадр;

- время следования операнда.

Время следования операнда можно оценить по формуле:

г = тах(/;(0),/о), (13)

где - время следования операнда в потоке; - максимальная величина задержки по обратной связи в графе Q.

При большой величине N временем заполнения конвейера и временем настройки на кадр можно пренебречь. Время вычисления кадра можно оценить как

Однако если существует рекурсивная связь, то время выполнения кадра замедляется до величины

Тк-г,(.ф-Ы. (15)

При достаточно больших структурных фрагментах это время может многократно превысить минимальное время выполнения кадра. Величину ¡¡(О) можно оценить как

- число вершин в графе кадра.

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

(16)

где р - число одновременно реализуемых базовых подграфов.

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

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

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

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

Адресом служит функция которая определяет: к какому элементу гистограм-

мы относится пришедший операнд Полученные результаты записываются в промежуточную вершину-массив WX.

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

Поэтому в отличие от первичной векторизации здесь предложено в вершину-массив прео-РИС.<5. Пример Аграфа, после выползня векторизации бразовывать адресные признаки информационныхвершин. которые можно рассматривать как информационные адресные вершины.

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

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

Рис.7. Вторичная векторизация адресных вершин.

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

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

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

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

Время решения задачи определятся суммой времен выполнения кадров:

Т = Р'«- (17)

Время выполнения кадра существенным образом зависит от степени распараллеливания. Когда число процессоров, отведенных для решения задачи, не превышает К -число арифметико-логических операций в базовом подграфе, то время выполнения кадра на N процессорах определяется по следующей формуле:

Тсп(М)

Ча+!,(*) + г)-

Если Ы2К, то

Тсп(Ы)=1„ + 1,(К) + т

{И

Эффективность распараллеливания Е(М) =

Т(У ГГЛ9-ЛГ

можно оценить

Е(М)_ + +

1„+1/К) + т-т-п

(18)

(19)

(20)

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

Таким образом, если справедливо неравенство

т({и+1])>1н+1/К), (21)

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

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

На рис 8 представлены сравнительные |рафические зависимости времени решения (Т) и эффективности распараллеливания (Е) от различного числа процессоров (№). Здесь кривые, обозначенные цифрой 1, соответствуют мультипроцедурной организации вычислений; кривые, обозначенные цифрой 2, - структурно-процедурной организации вычислений.

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

Рис.8. Зависимости времени решения и эффективности от числа процессоров.

В третьей главе представлены разработанные средства описания структурно-процедурных вычислений на основе языка программирования высокого уровня с неявным представлением параллелизма. В отличие от языков потоков данных предложено ограничение: правило единственной подстановки действует в специальных конструкциях языка, описывающих вычислительные структуры, задаваемые пользователем. Кадр языка соответствует совокупности арифметико-логических команд, выполняемых на различных ЭП и контроллерах распределенной памяти, соединенных между собой в соответствии с информационной структурой алгоритма. В теле кадра может находиться несколько операторов присваивания; программист не выделяет в них параллельные участки вычислений; в результате преобразования программы транслятором параллелизм, содержащийся в описании ВС, извлекается из нее естественным образом на основании взаимосвязей между данными. Описание кадра: CADR name,P; END name; где Р - список внутренних операторов кадра. Внутренние операторы кадра реализуются структурно, внешние - процедурно. При этом обеспечивается биективное соответствие программе на языке и граф-схемам.

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

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

Рис.9. Использование мемориальной и коммутационной переменных.

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

ОСЬ (А,В.С)[10 вТИ];

DCL (А,В,С) MEM [10 VEq; CADR summap;C=A+B; END summap;

CADR suromas,OA+B; END summas;

All|

44

A|l«l

B|lo|

A110I

Л|2| А|1|

Ч2| В)1|

№

QU С|2| qi4

XH

Рис. 10. Параллельное и последовательное сложение массивов.

Все записи, находящиеся во внутреннем операторе цикла FOR, мультиплицируются в соответствии с параметрами цикла на вычислительную структуру для векторов или осуществляется периодическое поступление элементов массивов по заданной оператором цикла процедуре для потоков. Внешний по отношению к описанию вычислительной структуры оператор FOR осуществляет циклическое выполнение операторов, в том числе, и кадров, находящихся в теле цикла. На рис.11 представлен пример оператора цикла.

Семантика синтаксически одинаковых конструкций кадра определяется структурой

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

DCL (А.В.С) [10 VEC]; Г^Т

FOR 1=1 ТО 10 BY 2 DO;- 1--1-u

CADR summa; Г^П

FOR J=ITO I+l DO; 1-1 «—

C[J]=A[J]+B[J]; END; ,-, rEND summa;END; I "'"l Li

1 M'ûl 1 [si*

Рис. 11. Использование циклических операторов.

f>> ' С1Ч I CPI У. H cm I

Ьм

J..-G

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

Рис. 12. Обращение к элементам векторов и потоков.

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

Рис. 13. Последовательное и параллельное сложение элементов массива.

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

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

Рис. 14. Структурный аналог условного перехода

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

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

Функции отображения базовых подграфов в одном слое могут в зависимости от степени распа-Рж.15. Исжодньш кадр. раллеливания реализовать-

ся как последовательно, так и параллельно. Функции отображения слоев реализуются исключительно последовательно.

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

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

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

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

Параллельные индуктивные программы описываются четверкой <Р0,Х0,Рр,Рх>, где Р0 параллельная структурно-процедурная программа, решаемая на минимальном ресурсе Х0; Fp-функция, ставящая в соо-

Рис. 16. Распараллеливание кадра

тветствие варианты распараллеливания задачи: Р,=Рр(Р,.1); Fx-функция, ставящая в соответствие варианты конфигурации МВС: Х,=Рх(Х,.|).

Алгоритм планировщика заданий представлен ниже. Если пришло новое задание то оно ставится в очередь 2°. Если задание 1, в очереди активных заданий Ра завершилось, то перейти к 3°, иначе к 5°.

3°. Переводится задание в выходную очередь (}0: 5(30=5(30+1, Р,[5(30]=.Га; 8(3,,=5(За-1,

4°. Множество базовьж модулей Ь(1а), которые занимало задание освобождается. Модифицируется свободный ресурс системы F: Р = Р и Ц.1а).

6°. Отбирается ресурс, удовлетворяющий требованиям .¡-го задания во входной очереди С=(5,[)]: ЦС)={11 Я(/) & ~Яа(С)& Ба(/) & Кс(С)<5с(/)}, где Ба(/) - характеристики /-го

модуля системы, 5с(/) •• описание связей 1-го блока системы. Если т= М(Е(0))>0, то перейти к 7°, иначе к 8°. М(Е(0)) - мощность множества Е(О), т - степень распараллеливания (число базовых модулей для О).

7°. Задание снимается с входной очереди (3,[1]=Е. 8°. Модифицируется свободный ресурс F = F / Е(О).

90. Инициализируется программа Рс(О,т), по окончании которой задание ставится в очередь активных заданий: 5(2,= Б<За +1, (5„[5<За]=0. 10°. ^+1. Если ЭО,^, то перейти к 6°, иначе к 11°.

11°. Просматривается очередь выходных заданий. Если к заданию q поступил запрос от пользователя, то задача пересылается пользователю и исключается из выходной очереди: 5<50= БОо- I, Ро[50о]=Е.

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

Т (рис.17). При проведении вычислительного эксперимента интенсивность обслуживания была зафиксирована и варьировалась интенсивность поступления. Интенсивность поступления 6=///, I - среднее время между заданиями. Интенсивность обслуживания а=1/1р> где Iр - время решения задачи.

О 0.04 0,08 0,12 0,1« а/Ь • ОМ «.12 (.11 а/Ь

Рис. 17. Эффективность планировщика индуктивных заданий.

Здесь цифрой 1 помечены кривые, соответствующие потоку индуктивных заданий, цифрой 2 - кривые, соответствующие потоку заданий с фиксированной степенью распараллеливания. Анализируя полученные результаты, можно отметить следующее. Технология параллельных индуктивных заданий позволяет существенно повысить загрузку оборудования системы и, следовательно, уменьшить стоимость решения задачи. Причем, для коммутационных сетей с меньшими возможностями по организации связей преимущество индуктивных параллельных заданий будет больше. Так, для плотно поступающих заданий для коммутационной сети, построенной по полному графу, выигрыш в коэффициенте использования оборудования для индуктивных заданий составляет 20-25%; для коммутационной сети, построенной по графу типа "бинарное дерево" - 40-43%. При этом коэффициент использования оборудования для потока индуктивных заданий снижается незначительно. Для коммутационной сети по полному графу коэффициент использования оборудования для индуктивных заданий равен 0,97, для идеальных индуктивных заданий коэффициент использования оборудования равен 0,97, для коммутационной сети, построенной по графу типа "бинарное дерево" - 0,94. Примерно такие же соотношения имеют место для времени прохождения потока заданий Т.

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

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

Задание представляет собой тройку: <2.,М(гЯр>, Z -загрузочный модуль; Мо -граф минимальной конфигурации вычислительного ресурса, необходимого для структурно-процедурного решения задачи; W— секция правил наращивания графа конфигурации вычислительного ресурса при увеличении степени распараллеливания задачи. Задание должно быть запрограммировано в соответствии с технологией индуктивных параллельных программ. Показано, что в кадр преобразуется функционально-регулярный подграф задачи К,=Р,(Ф,($), где К( - базовый подграф, который тиражируется для параллельного и последовательного выполнения; - правило наращивания базового подграфа при параллельной реализации, Ф, - правило наращивания базового подграфа при последовательной реализации. Можно сказать, что функции соответствует коммутационная

Рис.18. Структура системы посттрансляции. составляющая, функции Ф,- - составляющая обращения к каналам распределенной памяти, реализуемая последовательно во времени. Множество базовых подграфов всех кадров К={К/, К;,...,Кщ} образует наборы макроопераций. Множество функций р={р1,рз,...,р„} образует набор макрокоммутаций. Множество функций Ф-(Ф1,Ф2,...,Фп} образует набор обращений каналам РП.

Если оборудования МВС достаточно для того, чтобы обеспечить максимальное распараллеливание не только в кадре К„ но и в кадре Кр который непосредственно связан с кадром Л) (расположен с ним на одном уровне графа кадров С?*- или на смежных ярусах), то компоненты кадров К{ могут объединяться, образуя единый кадр К. Подобное объединение можно описать с помощью операции параллельного соединения. Для результирующего кадра формируются единый узел чтения и единый узел записи. При формировании объединенного кортежа функций чтения Ря' в него включаются все функции, принадлежащие кортежу РЯ„ а также те элементы кортежа РЛу, которые не состоят в отношении информационной зависимости с элементами кортежа функций чтения /У?/ и с элементами кортежа функций записи Р\\\. Здесь и далее будем говорить, что две функции информационно зависимы, если для всей области их определения наблюдается равенство получаемых информационных вершин, формируемых выражениями/^ и у(1+А), где А - константа. В этом случае говорится о том, что существует отношение информационной зависимости у. А). Подобная зависимость может быть легко реализована с помощью элементов задержки, при этом дуги а и Ь, начало или конец которых связаны с функциями /ч (</, связаны отношением \{а, Ь. А). Причем, если в отношении указана входная дуга, то с функцией чтения связано начало дуги, а если -выходная, то с функцией записи связан конец дуги. Аналогично формируется кортеж функций чтения объединенного узла записи. Исходные кадры показаны на рис.19. Здесь функция чтения, соответствующая источнику дуги а/, находится в отношении с функцией чтения, соответствующей началу дуги Ь/, а функция записи, соответствующая кон-

цу дуги а;, находится в отношении р с функцией чтения, соответствующей началу дуги 6'. Данные дуги модернизируются: изменяется источник дуги, и на дугу включается буфер с соответствующей задержкой операндов. Результат объединения кадров представлен на рис.20.

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

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

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

Рис.21. Свертка кадров

г-А

А

7FW

ж.

Э в

Я

BEGIN Graph;

DCL а 18, g-3, d.4, к: 18, b:4, q-3, ca-10, cd 2, ac:5,acd 8,ad l,ab 4,ba 6; INPUT (a,g,d);

OUTPUT (k,b,q); «—

A(IN(a,ca,ba),OUT(ac,acd,b,ad,ab),) В (IN (ab,g); OUT(ba);); С (IN (acd,ac); OUT(cd),); D(IN(ad,acd,d);OUT(q,g);); END Graph;

Рис.22. Пример графа минимальной конфигурации. DCL k; FOR ¡=0 TO_Par-l DO;

D

2Г

i l

Рис.23. Пример секции линейного наращивания.

DCL a,b,ij,k,l; Par^a-b; a:=log(_Paryiog2,b=a; Tf a - int(a) - 0 BREAK; a:-a+l; b:»N/a;

IF b - int(b) ■= 0 BREAK; b:-b-l; a:=N/b,c:=b/4; FORk=l TO a DO; n:=cadd(k,-t,a); s:=0; FORj=l TO b DO;

FOR ¡=1 TO 4 DO; s:=s+l; l.=s mod 4; m:=s / 4; Wi[kj,i].=Wo[n,l,rn]; END; END; END;

END PROGRAM.

Рис.24. Пример секций наращивания ресурса в соответствии с косвенным бинарным графом для процедуры БПФ.

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

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

Для МВС ПА основными функциональными устройствами являются: макропроцессор, блок распределенной памяти, макрокоммутатор.

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

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

В диссертации разработаны средства программирования макроопераций, представляющих собой программно-неделимую совокупность команд элементарных процессоров, образующих структурно-реализуемую функционально законченную математическую операцию. Директива описания макроопераций имеет следующий формат. Macrooperation имя (In список формальных параметров входов, processors список формальных имен ЭП, out список формальных параметров выходов) Совокупность команд ЭП, Endmacro;

Команда ЭП имеет вид: Р = <pl (<р2(Х) 0 (p3(Y)); где Р - идентификатор ЭП; X,Y -идентификатор s операндов, <pl —префиксные (постфиксные) функции, 0 - мнемоника операции.

Для удобства пользователей разработана и создана система программирования макроопераций, включающая в себя среду визуального программирования макроопераций (рис 25) и базу данных, в которой хранятся макрооперации для различных проблемных областей, например, для задач математической физики, для задач САПР СБИС, для процедур цифровой обработки сигналов

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

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

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

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

Разработаны функциональные схемы макрокоммутатора, его система команд, атак-

Рис 25 Среда синтеза макроопераций

Т 1 И

Рис 26 Структура макрообращения.

же средства описания макрокоммутаций Макрокоммутации используются для программирования каналов распределенной памяти и для каналов связи между РП и макропроцессорами

Macromemory имя макрообращения (In список формальных параметров входов, channel список имен выходов каналов РП, out список формальных параметров выходов) Совокупность описания каналов РП,

Ниже приведен пример определения доступа к каналам распределенной памяти.

Структура макрообращения показана на рис 26

Macromemory A (in a,b,<\d, channel А,В< out q,v,w,u) A«a,B«c(b), q«d. v«A, w«B,u«c, Endmacro;

Описание коммутаций используется для построения кадров: Declare Cadr имя кадра (In список формальных параметров входов, out список формальных параметров выходов. Com список коммутационных переменных) Обращения к структурным конструкциям, Endcadr;

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

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

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

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

На основе анализа коммутационных структур показаны преимущества коммутаций иерархических (рис.28) и ортогональных (рис.29), требующих минимальных аппаратных затрат при реализации функций системы. Разработаны структуры МВС с многоуровневой коммутацией, эффективно реализующей решение задачи математической физики и бинарного N-графа, эффективно реализующего вычисления БПФ. На основе ортогональной и иерархической систем коммутации разработаны и созданы семейства базовых модулей (БМ), структурные схемы которых показаны на рис.30 и рис.31. Предложены одномерные и двумерные структурные

[у Ер Ер ■•• Ор

к

Щ [м] [м] ... [м]

Рис 27. Структура МВС СПОВ

схемы синхронизации системы, вторая обеспечивает более скоростную согласованную перестройку системы. Базовые модули реализованы на основе ПЛИС-технологии.

к к К

к =

к

к е* К

к

8=: -

« к к

Г*н-> -Ш3>" 0*2)— в

«чзш -шэ

Ч?П

ШСПЦГГТ II М 1мт

ХАЛ || уп | ММ1 [| м |

• 1Т и и I

КМ 11 РП

Рис.28. Иерархическая коммутационная система

МАЛ I РП

| РП

Рис.29. Ортогональная коммутационная система.

Рис.30. БМ с иерархической коммутационной Рис 31. БМ с ортогональной коммутационной системой. системой.

На основе БМ создан ряд модульно-наращиваемых МВС (рис.32-34). В частности, модулыю-наращиваемая МВС со структурно-процедурной организацией вычислений, созданная в рамках Программы Союзного государства России и Беларуси "Разработка и освоение в серийном производстве семейства высокопроизводительных вычислительных систем с параллельной архитектурой и создание прикладных программно-аппаратных комплексов на их основе (шифр "СКИФ")", имеет следующие характеристики:

Количество БМ 8

Количество ЭП 512

Количество каналов РП Производительность,

256 210" оп/с

Рис 32. Одноплатный ускоритель 1МВ РС. Количество ЭП 64

Количество каналов РП 16

Производительность 2,5-10,0оп/с

Рис 33 Автомат сопровождения цели. Количество ЭП 64

Время обработки информации, не более 20мс Размеры области анализа 256x256 пиксел

Рис.34. Многопроцессорные вычислители.

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

Созданные в рамках диссертации программные средства и многопроцессорные вычислительные системы демонстрировались на ряде международных научно-технических выставок, в том числе: на Всемирных выставках оргтехники, информации и телекоммуникаций CeBIT, Ганновер, Германия, 1997, 1998, 2001; на Международных выставках SIMO TCI, Мадрид, Испания, 1997, 1998; на Международной выставке-ярмарке Hannover Messe, Ганновер, Германия, 2002.

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

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

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

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

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

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

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

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

6) Доказана более высокая эффективность структурно-процедурной организации вычислений по сравнению с традиционными мультипроцедурными методами организации параллельных вычислений для широкого класса задач.

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

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

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

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

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

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

Основные публикации по теме диссертации

1. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - М.: Янус-К, 2003. - 380 с. (опубликована при поддержке РФФИ, грант № 02-07-95004-д).

2. Левин И.И., Пономарев И.М. Реализация БПФ на многопроцессорной системе со структурной организацией вычислений //Электромеханика, 1995. -№ 4. - С.72 - 74.

3. Левин И.И., Гузик В.Ф., Сафронов О.О. Представление параллелизма в программах для многопроцессорной системы с программируемой архитектурой // Известия ВУЗов. Северокавказский регион. Технические науки, 1996. - № 2. - С. 4-15.

4. Каляев А.В., Фрадкин Б.Г.Левин И.И., Унифицированная элементная база для построения реконфигурируемых под задачу вычислительных систем // Известия вузов. Электроника, 1997. -№ 1. - С.75-83.

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

6. Каляев А.В., Левин И.И. Многопроцессорные системы с перестраиваемой архитектурой; концепции развития и применения //Наука - производству, 1999.-№11.-С.11-19.

7. Каляев А.В., Левин И.И., Пономарев И.М. Базовый модуль многопроцессорной вычислительной системы с программируемой архитектурой для эффективного решения исследовательских и производственных задач //Наука - производству, 1999.-№ 11.-С.ЗЗ-39.

8. Левин И.И., Пономарев И.М. Структурно-процедурная реализация кластерной группировки данных в задачах обработки изображений //Электромеханика, 1999.-№2.-С.54-57.

9. Левин И.И. Структурно-процедурная реализация электрического моделирования на многопроцессорной системе//Известия ВУЗов. Электромеханика, 2002. -№1. - С. 2730.

10.Левин И.И., Коробкин В.В., Чернов Е.И. Об одном подходе к проблеме повышения надежности управляющего вычислительного комплекса с использованием технологии МВС ПА // Мехатроника, автоматизация, управление. -М.: Новые технологии, 2003.-№4.-С.40-43.

11.Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование реконфигурируемых МВС // Электромеханика, 2004. -№ 3. - С. 11-15.

12. Каляев ВА, Левин И.И., Фомин С.Ю. Об оценке эффективности решения задач математической физики на многопроцессорных системах // Электронное моделирование, 1989.-№6.-С.11-15.

13. Kalyaev A.V., Kaliaev I.A., Levin I.I. The Base Module of Multiprocessor System with Structural-Procedural Organization of Computing // Parallel Computing Technologies. Proceedings of 4-th International Conference, PaCT-97. Yaroslavl, Russia, 1997. - Pp.394-396.

14. Левин И.И. Язык параллельного программирования высокого уровня для структурно-процедурной организации вычислений // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000. -М:Изд-во МГУ.-С.108-112.

15. Каляев А.В., Левин И.И. Структурно-процедурная организация параллельных вычислений // Труды межд. конф. "Параллельные вычисления и задачи управления (РАСО'2001)". -М: ИПУ РАН им. В.А.Трапезникова, 2001. -Т. 5. - С. 112-121.

16. Левин И.И., Штейнберг Б.Я. Сравнительный анализ эффективности параллельных программ для различных архитектур многопроцессорных систем // Искусственный интеллект. - Донецк: Наука i освгга, 2001. - №3. -С.234-242.

17. Левин И.И., Шахов Р.В., Шматок А.В., Сластен Л.М. Математическое обеспечение многопроцессорных вычислительных систем с программируемой архитектурой // Искусственный интеллект. - Донецк: Наука i освита, 2002. - №3. - С.286 294.

18. Левин И.И. Многопроцессорная система с программированием архитектуры на нескольких уровнях // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации". -М.: МГУ, 2003. - С. 111-118.

19. Левин И.И., Пономарев И.М. Структурно-процедурная реализация задачи трассировки // Искусственный интеллект. Донецк: Наука i освита, 2003. - №3. - С.121-129.

20. Левин И.И. Ресурсонезависимое параллельное программирование // Искусственный интеллект. - Донецк: Наука i освиа, 2002. - №3. - С.277-285.

21. Левин И.И. Модульно-наращиваемая многопроцессорная вычислительная система со структурно-процедурной организацией вычислений на основе ПЛИС-технологии // Искусственный интеллект. - Донецк: Наука i освита, 2003. - №4. -С.446-453.

22. Матричный коммутатор: Патент РФ № 2059288 на изобретение по заявке № 94029855/09. / Левин И.И., Ерохин А.В., Рыжих ОА., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.04.1996. - Бюлл. № 12. - 5 с.

23. Матричный коммутатор: Патент РФ № 2103729 на изобретение по заявке № 94029856/09. / Левин И.И., Ерохин А.В., Рыжих ОА., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.01.1998. - Бюлл. № 3.-7 с.

24. Макропроцессор: Патент РФ № 2210808 на изобретение по заявке № 2001100388. / Каляев А.В., Левин И.И., Виневская Л.И., Станишевский О.Б. - Заявл. 05.01.2001; Опубл. 20.08.2003. - Бюлл. № 23. - 26 с.

25. Мультиконтроллер распределенной памяти: Патент РФ № 2210804 на изобретение по заявке № 2001122359. / Каляев А.В., Левин И.И., Виневская Л.И., Дмитренко Н.Н. -Заявл. 08.08.2001; Опубл. 20.08.2003.-Бюлл. №23.-44 с.

26. Левин И.И., Каляев В.А., Фомин С.Ю. Многопроцессорная система для оперативного моделирования гидрофизических процессов. // Сб. "Программные и аппаратные средства машинного моделирования", Москва, 1988.

27. Левин И.И. Сопроцессор для решения задач математической физики структурно-процедурным методом распараллеливания. // Сб. "Анализ эффективности вычислительных систем". -Львов, 1991. - Препринт НТЦ "Интеграл". -№ 9-16.

28. Левин И.И., Рвачев В.Л., Шевченко А.Н., Кошеленко А.И. Software and Hardware of Simulation of Phisical Mechanical Fillds. // Сб. "Parallel Computing Technologies Word Scientific". - Новосибирск, 1991.

29. Левин И.И., Пономарев И.М. Реализация алгоритма волновой трассировки на многопроцессорной системе со структурной организацией вычислений. - М., 1995. - Деп. ВИНИТИ, № 1553-В95. - 49 .

30. Левин И.И. Высокоэффективный алгоритм структурно-процедурной реализации задачи логико-временного моделирования на многопроцессорной системе. - М., 1995. -Деп. ВИНИТИ, № 1445-В95. - 31 с.

31. Левин И.И. Структурно-процедурная реализация функционального моделирования на многопроцессорной системе. -М., 1995. - Деп. ВИНИТИ, № 2043-В95. - 25 с.

32. Левин И.И., Пономарев И.М., Фрадкин Б.Г. Анализ эффективности структурно-процедурной организации вычислительного процесса при решении прикладных задач на МВС. // Сборник аннотаций и научных статей по результатам исследований, проведенных в ходе выполнения межвузовской научно-технической программы "Фундаментальные исследования в области прикладной физики и математики в технических ВУЗах России". ФИЗМАТ 1992-1995. -М.:ГКРФ по Высшему образованию, 1995.

33. Левин И.И., Виневская Л.И., Дмитренко Н.Н., Логвинов С.А. Элементная база для построения высокопроизводительных систем. // Труды международной конференции "Интеллектуальные многопроцессорные системы". -Таганрог: Изд-во ТРТУ, 1999.-С. 9397.

34. Левин И.И., Шматок А. В. Технология параллельных индуктивных программ. // Труды международной конференции "Интеллектуальные многопроцессорные системы (ИМС99)". -Таганрог: Изд-во ТРТУ, 1999. - С. 142-146.

35. Левин И.И. Методы построения самонастраиваемой элементной базы. // Тезисы международной конференции "Интеллектуальные и многопроцессорные системы-200Г. - Таганрог: Изд-во ТРТУ, 2001. - С. 126-129.

36. Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование многопроцес-сорныхсистем с массовым параллелизмом.//Искусственный интеллект. Донецк: Наука i освгта, 2002. - № 3. - С.295-302.

37. Левин И.И. Отображение структурно-процедурной формы задачи на архитектуру многопроцессорной системы. // Материалы Международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы". - Таганрог: Изд-во ТРТУ, 2002. - С. 95-98.

38. Каляев А.В., Каляев И.А., Левин И.И. Модульно-наращиваемые многопроцессорные системы с программируемой архитектурой и структурно-процедурной организацией вычислений. // Сборник докладов конференции "С.А. Лебедев и развитие отечественной вычислительной техники". -М., 2002. - С. 112-116.

40. Левин И.И., Шахов Р.В. Алгоритмы трансляции структурно-реализуемого фрагмента задачи для многопроцессорной системы с программируемой архитектурой. // Искусственный интеллект. -Донецк: Наука i освгта, 2003. - №3. - С.138-146.

ЛР № 020565 от 23 июня 1997 г. Подписано к печати 02 »#У.2004 г. Формат 60x841 16. Бумага офсетная Печать офсетная Усл. п.л -2,0. Уч. - изд л. - 1,8.

Заказ N° 271. Тираж 100 экз

ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Таганрогского государственного радиотехнического университета.

Ц49 1*

ВВЕДЕНИЕ.

1. СТРУКТУРНО-ПРОЦЕДУРНАЯ ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ.

1.1. Методы организации параллельных вычислений.

1.2. Модели параллельных вычислений.

1.3. Формальное определение структурно-процедурных вычислений.

1.4. Основные принципы преобразования задачи в структурно-процедурную форму.

1.5. Выводы.

2. МЕТОДЫ ПРЕОБРАЗОВАНИЯ ЗАДАЧИ К ЭФФЕКТИВНОЙ СТРУКТУРНО-ПРОЦЕДУРНОЙ ФОРМЕ.

2.1. Преобразование функционально-регулярных графов.

2.2. Преобразование в структурно-процедурную форму информационных графов нерегулярной структуры.

2.3. Структурно-процедурная реализация нерегулярных информационных графов.

2.4. Эффективность структурно-процедурных вычислений.

2.5. Выводы.

3. СРЕДСТВА ОПИСАНИЯ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ.

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

3.2. Некоторые особенности и алгоритмы трансляции.

3.3. Выводы.

4. ТЕХНОЛОГИЯ ИНДУКТИВНЫХ СТРУКТУРНО-ПРОЦЕДУРНЫХ ПРОГРАММ.

4.1. Принципы построения технологии индуктивных структурно-процедурных программ.

4.2. Планировщик индуктивных заданий.

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

4.4. Программные средства поддержки технологии индуктивных программ.

4.5. Выводы.

5. ЭЛЕМЕНТНАЯ БАЗА МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ПРОГРАММИРУЕМОЙ АРХИТЕКТУРОЙ И СТРУКТУРНО-ПРОЦЕДУРНОЙ ОРГАНИЗАЦИЕЙ ВЫЧИСЛЕНИЙ И СРЕДСТВА ЕЕ

ПРОГРАММИРОВАНИЯ.

5.1. Макропроцессор.

5.1.1. Структура макропроцессора.

5.1.2. Программирование макроопераций.

5.2. Макрокоммутатор.

5.2.1. Структура макрокоммутатора.

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

5.3. Контроллер распределенной памяти.

5.3.1. Структура КРП.

5.3.2. Программирование РП.

5.4. Выводы.

6. АРХИТЕКТУРА МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ ДЛЯ

СТРУКТУРНО-ПРОЦЕДУРНОГО РЕШЕНИЯ ЗАДАЧ РАЗЛИЧНЫХ .ПРОБЛЕМНЫХ ОБЛАСТЕЙ.

6.1. Синтез структуры многопроцессорной вычислительной системы для решения задач структурно-процедурным методом распараллеливания.

6.2. Анализ вариантов построения коммутационных структур МВС со структурно-процедурной организацией вычислений.

6.2.1. МВС с фиксированной топологией информационных связей.

6.2.2. Иерархическая коммутационная система.

6.2.3. Ортогональная система коммутации.

6.2.4. МВС с коммутационной системой косвенного бинарного п-куба.

6.2.5. Многоуровневая коммутационная структура.

6.3. Модульная организация МВС.

6.3.1. Структура базового модуля МВС с иерархической коммутационной системой.

6.3.2. Структурная схема базового модуля с ортогональной системой коммутации.

6.3.3. Конструкция базового модуля.

6.4. Выводы.

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

О темпах развития вычислительной техники говорит тот факт, что два десятилетия назад наиболее мощные суперкомпьютеры имели производительность в несколько Гфлопс; в настоящее время эксплуатируются суперкомпьютеры с производительностью более триллиона операций в секунду, наиболее мощные суперкомпьютеры имеют производительность, превышающую 50 Тфлопс, и разрабатываются системы с производительностью от 100 до 1000 Тфлопс [2]. В то же время для ряда сложных расчетоемких задач реальная производительность современных суперкомпьютеров существенно ниже пиковой производительности [3].

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

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

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

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

Решением данной проблемы занимались такие видные ученые как Э. Дейкстра, Ч. Хоар, Р. Хокни, В. Хейдлер, Д. Чамберлен, а также российские ученые: B.C. Бурцев, В.Е. Котов, В.К. Левин, Д.А. Поспелов, В.Г. Хорошевский, Р.Ю. Ясинявичус, В.В. Воеводин, В.А. Вальковский и многие другие.

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

Альтернативой существующим МВС с массовым параллелизмом являются многопроцессорные вычислительные системы с программируемой архитектурой (МВС ПА). Концепция таких систем была разработана в Научно-исследовательском институте многопроцессорных систем ТРТУ под руководством академика РАН|А.В.КаляёшГ1 [4, 5, 6, 7, 8,9,10,11,12].

Идея МВС с программируемой архитектурой заключается в том, чтобы обеспечить пользователю возможность с помощью программно-аппаратных средств программировать и формировать в универсальной системе виртуальные специализированные вычислители, адекватные структуре решаемой задачи. Это позволяет не только подбирать структуру алгоритма к архитектуре системы, но и, наоборот, адаптировать структуру многопроцессорной системы к параллельному алгоритму, что выводит на передний план "внутренний" параллелизм задачи, а не организацию вычислительных средств [13].

Для многопроцессорной системы с программируемой архитектурой используется структурно-процедурная (кадровая) форма задачи. Кадр представляет собой структурно (аппаратно) реализованный подграф задачи, через который следует поток данных. Подобная организация вычислений обеспечивает максимальную скорость обработки данных, сопоставимую со скоростью специализированных вычислителей. Вычисления в теле кадра выполняются по принципу управления потоком данных и не требуют синхронизации. Настройка на кадры производится по единой управляющей программе, что обеспечивает фон-неймановский детерминизм вычислительной процедуры [14, 15,16].

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

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

В соответствии с поставленной целью определены задачи диссертации:

1) Провести анализ методов и моделей параллельных вычислений и на их основе разработать основные принципы эффективных структурно-процедурных вычислений.

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

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

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

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

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

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

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

Наиболее важными из них являются:

- "Исследование возможности путей создания вычислителя с программируемой архитектурой", руководитель НИР - член-корреспондент РАН И.А. Каляев, заказчик в/ч 26165;

- "Инструментальная программно-математическая система суперкомпьютеров с массовым параллелизмом для решения различных военно-прикладных задач", руководитель НИР - академик РАН A.B. Каляев, № ГР ИН-858;

- "Разработка универсальных мультимикропроцессорных систем с массовым параллелизмом и средствами аппаратно-программной поддержки синтеза виртуальных архитектур и модульной реконфигурации", руководитель - академик РАН A.B. Каляев; № ГР 01200100688;

- "Исследование и разработка математических и программных средств для эффективного распараллеливания прикладных задач на высокопроизводительных вычислительных комплексах", руководитель - член-корреспондент РАН И.А. Каляев, по договору с в/ч 11135;

- "Разработка модульно-наращиваемой многопроцессорной системы со структурно-процедурной организацией вычислений и программируемой архитектурой на основе ПЛИС-технологии", главный конструктор, кандидат техн. наук И.И. Левин, по договору с ОАО НИЦЭВТ и в рамках Программы Союзного государства «Разработка и освоение в серийном производстве семейства высокопроизводительных вычислительных систем с параллельной архитектурой (суперкомпьютеров) и создание прикладных программно-аппаратных комплексов на их основе» (шифр «СКИФ»), утвержденная Постановлением Исполнительного Комитета Союза Беларуси и России от 22 ноября 1999 г. №43;

- "Многопроцессорные ЭВМ с параллельной структурой в бортовых системах принятия решений и управления автономных объектов", руководитель - к.т.н. С.Г. Капустян, № ГР 01.9.90002062;

- "Дальнейшее развитие теории многопроцессорных вычислительных систем с массовым параллелизмом, программируемой под структуру задачи архитектурой и структурно-процедурной реализацией вычислительного процесса", руководитель - академик РАН A.B. Каляев, № ГР 01.2.00102845;

- "Разработка и создание методов и программно-аппаратных средств для структурно-процедурной организации вычислений в суперЭВМ с программируемой архитектурой", руководитель - академик РАН A.B. Каляев;

- "Разработка методологии организации структурно-процедурных вычислений на многопроцессорных суперЭВМ с массовым параллелизмом и программируемой архитектурой", руководитель - к.т.н. И.И. Левин, № ГР 01990002076;

- "Теоретические и практические основы построения и применения мультипроцессорных вычислительных систем с программируемой архитектурой для решения задач прикладной физики и математики", руководитель - академик РАН A.B. Каляев, № ГР 01970003041;

- "Разработка и исследование архитектуры, принципов построения и элементной базы высокопроизводительного универсального суперпроцессора со структурной организацией вычислений", руководитель - академик РАН A.B. Каляев, № ГР 019100054183;

- "Разработка и исследование принципов создания интеллектуальной самонастраиваемой элементной базы для построения структурноперестраиваемых процессорных полей МВС со структурно-процедурной организацией вычислений", руководитель - к.т.н. И.И. Левин,

ГР 01.20.0001267;

- "Исследование и разработка фундаментальных принципов и методов программирования многопроцессорных вычислительных систем с массовым параллелизмом, программируемой архитектурой и структурно-процедурной организацией вычислений", руководитель - академик РАН A.B. Каляев;

- "Разработка и изготовление экспериментального образца модульно-наращиваемой многопроцессорной системы со структурно-процедурной организацией вычислений и программируемой архитектурой на основе ПЛИС-технологии ", главный конструктор - к.т.н. И.И. Левин;

- "Исследования по созданию программно-аппаратных средств телевизионного автомата слежения за целями для перспективных наземных автономных роботизированных комплексов", руководитель - член-корреспондент РАН И.А. Каляев;

- "Исследование и разработка математических и программных средств для эффективного распараллеливания прикладных задач на высокопроизводительных вычислительных комплексах", руководитель - член-корреспондент РАН И.А. Каляев.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:

- Всероссийская научно-техническая конференция "Актуальные проблемы твердотельной электроники и микроэлектроники", Таганрог, 1994 г.;

- Всероссийская научно-техническая конференция с международным участием "Теория цепей и сигналов", Новочеркасск, 1996 г.;

- 4-th International Conference, РаСТ-97. Yaroslavl, Russia, 1997 г.;

- VI международный семинар "Распределенная обработка информации", Новосибирск, 1998 г.;

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

- IV всероссийская научно-техническая конференция "Нейрокомпьютеры и их применение", Москва, 1998 г.;

- V всероссийская научно-техническая конференция "Нейрокомпьютеры и их применение", Москва, 1999 г.;

- Международная конференция "Интеллектуальные многопроцессорные системы (ИМС'99)", Таганрог, 1999 г.;

- Международная конференция "Искусственный интеллект-2000",-Кацивели, 2000 г.;

- Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 29 октября - 2 ноября 2000 г.;

- Третья международная научно-техническая конференция "Электроника и информатика - XXI век", 22-24 ноября, Зеленоград-Москва, МИЭТ, 2000 г.;

- Международная конференция "Интеллектуальные и многопроцессорные системы-2001", пос. Дивноморское, 2001 г.

- Международная конференция "Параллельные вычисления и задачи управления (РАСО'2001)", М: ИПУ РАН им. В.А.Трапезникова, 2001 г.;

- Международная конференция "Искусственный интеллект-2002",-Кацивели, 2002 г.;

- Международная научно-техническая конференция "СуперЭВМ и многопроцессорные вычислительные системы-2002", Таганрог, 2002 г.;

- Конференция "CA. Лебедев и развитие отечественной вычислительной техники", Москва, 2002 г.;

- Международная конференция "Интеллектуальные и многопроцессорные системы-2003", пос. Дивноморское, 2003 г.;

- Первая Всероссийская научная конференция "Методы и средства обработки информации". Москва, ф-т вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2003 г.

По теме диссертации опубликованы 102 печатные работы, в том числе, 1 монография, 30 статей в центральной печати, из них 10 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК, получено 4 патента на изобретение.

Наиболее важными из публикаций являются:

Каляев A.B., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - М.: Янус-К, 2003. - 380 с. (опубликована при поддержке РФФИ, грант № 02-07-95004-д),

Левин И.И., Пономарев И.М. Реализация БПФ на многопроцессорной системе со структурной организацией вычислений // Электромеханика, 1995. -№ 4. - С.72 - 74.

Левин И.И., Гузик В.Ф., Сафронов О.О. Представление параллелизма в программах для многопроцессорной системы с программируемой архитектурой // Известия ВУЗов, Северокавказский регион. Технические науки, 1996. - № 2. -С. 4-15.

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

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

Каляев A.B., Левин И.И. Многопроцессорные системы с перестраиваемой архитектурой; концепции развития и применения //Наука - производству, 1999. -№11. -С. 11-19.

Каляев A.B., Левин И.И., Пономарев И.М. Базовый модуль многопроцессорной вычислительной системы с программируемой архитектурой для эффективного решения исследовательских и производственных задач // Наука - производству, 1999. - № 11. - С. 33-39.

Левин И.И., Пономарев И.М. Структурно-процедурная реализация кластерной группировки данных в задачах обработки изображений // Электромеханика, 1999. - №2. - С. 54-57.

Левин И.И. Структурно-процедурная реализация электрического моделирования на многопроцессорной системе // Известия ВУЗов. Электромеханика, 2002. - №1. - С. 27-30.

Левин И.И., Коробкин В.В., Чернов Е.И. Об одном подходе к проблеме повышения надежности управляющего вычислительного комплекса с использованием технологии МВС ПА // Мехатроника, автоматизация, управление. - М.: Новые технологии, 2003. - № 4. - С. 40-43.

Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование реконфигурируемых МВС // Электромеханика, 2004. - № 4. - С. 11-15.

Каляев В.А., Левин И.И., Фомин С.Ю. Об оценке эффективности решения задач математической физики на многопроцессорных системах // Электронное моделирование, 1989. - № 6. - С. 11-15.

Kalyaev A.V., Kaliaev I.A., Levin I.I. The Base Module of Multiprocessor System with Structural-Procedural Organization of Computing // Parallel Computing Technologies. Proceedings of 4-th International Conference, PaCT-97. Yaroslavl, Russia, 1997.-Pp. 394-396.

Левин И.И. Язык параллельного программирования высокого уровня для структурно-процедурной организации вычислений // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000. - М: Изд-во МГУ. - С. 108-112.

Каляев A.B., Левин И.И. Структурно-процедурная организация параллельных вычислений // Труды межд. конф. "Параллельные вычисления и задачи управления (РАСО'2001)". - М: ИПУ РАН им. В.А.Трапезникова, 2001. -Т. 5.-С. 112-121.

Левин И.И., Штейнберг Б.Я. Сравнительный анализ эффективности параллельных программ для различных архитектур многопроцессорных систем // Искусственный интеллект. - Донецк: Наука i освгга, 2001. - №3. - С. 234-242.

Левин И.И., Шахов Р.В., Шматок A.B., Сластен Л.М. Математическое обеспечение многопроцессорных вычислительных систем с программируемой архитектурой // Искусственный интеллект. - Донецк: Наука i освгга, 2002. - №3. - С. 286-294.

Левин И.И. Многопроцессорная система с программированием архитектуры на нескольких уровнях // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации". - М.: МГУ, 2003. -С. 111-118.

Левин И.И., Пономарев И.М. Структурно-процедурная реализация задачи трассировки // Искусственный интеллект. Донецк: Наука i освгга, 2003. - №3. -С. 121-129.

Левин И.И. Ресурсонезависимое параллельное программирование // Искусственный интеллект. - Донецк: Наука i освгга, 2002. - №3. - С. 277-285.

Левин И.И. Модульно-наращиваемая многопроцессорная вычислительная система со структурно-процедурной организацией вычислений на основе ПЛИС-технологии // Искусственный интеллект. - Донецк: Наука i oceiTa, 2003. -№4.-С. 446-453.

Матричный коммутатор: Патент РФ № 2059288 на изобретение по заявке № 94029855/09. / Левин И.И., Ерохин A.B., Рыжих O.A., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.04.1996. - Бюлл. № 12. - 5 с.

Матричный коммутатор: Патент РФ № 2103729 на изобретение по заявке № 94029856/09. / Левин И.И., Ерохин A.B., Рыжих O.A., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.01.1998. - Бюлл. №3.-7 с.

Макропроцессор: Патент РФ № 2210808 на изобретение по заявке № 2001100388. / Каляев A.B., Левин И.И., Виневская Л.И., Станишевский О.Б. -Заявл. 05.01.2001; Опубл. 20.08.2003. - Бюлл. № 23. - 26 с.

Мультиконтроллер распределенной памяти: Патент РФ № 2210804 на изобретение по заявке № 2001122359. / Каляев A.B., Левин И.И., Виневская Л.И., Дмитренко H.H. - Заявл. 08.08.2001; Опубл. 20.08.2003. -Бюлл. №23.-44 с.

Левин И.И., Каляев В.А., Фомин С.Ю. Многопроцессорная система для оперативного моделирования гидрофизических процессов // Сб. "Программные и аппаратные средства машинного моделирования", Москва, 1988.

Левин И.И. Сопроцессор для решения задач математической физики структурно-процедурным методом распараллеливания // Сб. "Анализ эффективности вычислительных систем". - Львов, 1991. - Препринт НТЦ "Интеграл". - № 9-16.

Левин И .И., Рвачев В .Л., Шевчен ко А .Н., Кошелен ко А .И. S oftware and Hardware of Simulation of Phisical Mechanical Fillds // Сб. "Parallel Computing Technologies Word Scientific". - Новосибирск, 1991.

Левин И.И., Пономарев И.М. Реализация алгоритма волновой трассировки на многопроцессорной системе со структурной организацией вычислений. - М., 1995. - Деп. ВИНИТИ, № 1553-В95. - 49 с.

Левин И.И. Высокоэффективный алгоритм структурно-процедурной реализации задачи логико-временного моделирования на многопроцессорной системе. -М., 1995. - Деп. ВИНИТИ, № 1445-В95. - 31 с.

Левин И.И. Структурно-процедурная реализация функционального моделирования на многопроцессорной системе. - М., 1995. - Деп. ВИНИТИ, № 2043-В95. - 25 с.

Левин И.И., Пономарев И.М., Фрадкин Б.Г. Анализ эффективности структурно-процедурной организации вычислительного процесса при решении прикладных задач на МВС // Сборник аннотаций и научных статей по результатам исследований, проведенных в ходе выполнения межвузовской научно-технической программы "Фундаментальные исследования в области прикладной физики и математики в технических ВУЗах России". ФИЗМАТ 1992-1995. - М.: ГК РФ по Высшему образованию, 1995.

Левин И.И., Виневская Л.И., Дмитренко H.H., Логвинов С.А. Элементная база для построения высокопроизводительных систем // Труды международной конференции "Интеллектуальные многопроцессорные системы". - Таганрог: Изд-во ТРТУ, 1999. - С. 93-97.

Левин И.И., Шматок А. В. Технология параллельных индуктивных программ // Труды международной конференции "Интеллектуальные многопроцессорные системы (ИМС'99)". - Таганрог: Изд-во ТРТУ, 1999. - С. 142-146.

Левин И.И. Методы построения самонастраиваемой элементной базы // Тезисы международной конференции "Интеллектуальные и многопроцессорные системы-2001". - Таганрог: Изд-во ТРТУ, 2001. - С. 126129.

Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование многопроцессорных систем с массовым параллелизмом // Искусственный интеллект. - Донецк: Наука i ocBiTa, 2002. - №3. - С. 295-302.

Левин И.И. Отображение структурно-процедурной формы задачи на архитектуру многопроцессорной системы // Материалы Международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы". - Таганрог: Изд-во ТРТУ, 2002. - С. 95-98.

Каляев A.B., Каляев И. А., Левин И.И. Модульно-наращиваемые многопроцессорные системы с программируемой архитектурой и структурно-процедурной организацией вычислений // Сборник докладов конференции "С.А. Лебедев и развитие отечественной вычислительной техники". - М., 2002. -С. 112-116.

Левин И.И., Шахов Р.В. Алгоритмы трансляции структурно-реализуемого фрагмента задачи для многопроцессорной системы с программируемой архитектурой // Искусственный интеллект. - Донецк: Наука I освгга, 2003. - №3. -С. 138-146.

Основные положения, выносимые на защиту:

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

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

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

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

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

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

Структура диссертации. Диссертация состоит из введения, шести глав, заключения и библиографического списка.

6.4. Выводы

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

2) На основе анализа различных вариантов коммутационных структур МВС показано, что для эффективной реализации параллельных программ задач различных классов наиболее перспективной является иерархическая коммутационная система, а для минимизации аппаратных затрат и повышения характеристик "производительность/стоимость" целесообразно использовать ортогональные коммутационные системы.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна диссертации заключается в том, что в ней впервые:

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

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

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

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

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

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

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

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

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

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

Практическое использование научных результатов позволило:

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

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

3) Разработать алгоритмы планировщика индуктивных заданий, распределяющего свободный ресурс системы с минимизацией времени прохождения потока заданий. Реализация планировщика заданий показывает его высокую эффективность, в том числе, и для ограниченных коммутирующих структур, для которых преимущество технологии индуктивных структурно-процедурных программ более заметно и позволяет повысить коэффициент использования оборудования на 40% и сократить время прохождения задач на 20-30%.

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

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

5) Разработать и создать элементную базу для построения МВС со СПОВ, с минимальной номенклатурой и четко обозначенными функциями. Технические решения защищены четырьмя патентами РФ.

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

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

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

Основные научные результаты диссертации опубликованы [57, 58, 69, 7783, 86-88, 95, 96, 98-101, 107-109, 133, 135, 137-140, 144-146, 153, 159, 160, 162, 167-169, 173-177, 187, 196, 198-200, 214, 215, 223, 224].

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

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

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

1. Фортов В.Е., Савин Г.И., Левин В.К. и др. Создание и применение высокопроизводительных вычислений на базе высокопроизводительных сетевых технологий. // Информационные технологии и вычислительные системы, 2001. № 1. - С.3-10.

2. Митропольский Ю. суперкомпьютеры и микропроцессоры. // Электроника: наука, технология, бизнес, 2000. -№2. С Л 8-21.

3. Аладышев О.С., Дикарев Н.И., Овсянников А.П., Телегин П.Н., Шабанов Б.М. СуперЭВМ: области применения и требования к производительности. // Известия ВУЗов. Электроника, 2004. №1. - С. 13-17.

4. Каляев А.В. Теория цифровых интегрирующих машин и структур. М.: Сов. радио, 1970.-471 с.

5. Каляев А.В. Автоматы с программируемой структурой. // Problems of control and Information Theory. -Budapest, 1975. №1. - 1758. - Pp. 35-36.

6. Каляев А.В. Многопроцессорные однородные вычислительные структуры. // Радиоэлектроника. -М., 1978. № 12. - С. 5-17.

7. Kalyaev A.V. Multiprocessor homogeneous calculation structures with distributed memory and universal commutation. // Euromicro Journal, 1979. V.5. -№ 2. - Pp.73-81.

8. Каляев А.В. Многопроцессорные системы с распределенной памятью, универсальной коммутацией и программируемой структурой микропроцессоров. // Электронное моделирование. Киев, 1979. -№ 1. -С.31-41.

9. Каляев А.В. Микропроцессоры с программируемой структурой и многопроцессорные системы с универсальной коммутацией и распределенной памятью. // Параллельное программирование и высокопроизводительные системы. Новосибирск, 1980. - T.I. - С.87-117.

10. Каляев А.В. Принципы организации многопроцессорных систем сверхвысокой производительности. // Микропроцессорные средства и системы. -Москва, 1984.-№2.-С.31-35.

11. Kalyaev A.V. Multiprocessor Systems with a Programmable Architectures. // Fifth Generation Computer Architectures. Amsterdam. New York. Oxford. Tokyo, 1986.-Pp.291-300.

12. Kalyaev A.V. Multimicroprocessor Systems. // Information Processing-86. Proceedings of the IFIP 10-th World Computer Congress. Ireland, Dublin, 1986. -Pp.949-954.

13. Каляев A.B., Каляев И.А. СТОРК-компьютер многопроцессорная вычислительная система со структурной организацией вычислений. // Электронное моделирование. - Киев, 1996. - № 4. - С.5-14.

14. Kalyaev A.V. The Programming of Virtual Problem-Oriented Parallel Supercomputers in the Structure of Universal Supercomputers with Massive Parallelism. // H igh-Performance Computing. S an D iego, С alifornia, U SA, 1 999. -Pp.249-255.

15. Каляев A.B. Принципы и методы программирования виртуальных архитектур в многопроцессорных суперкомпьютерах. // Высокопроизводительные вычисления и их приложения. Черноголовка, 2000. -С. 12-16.

16. Каляев A.B. Программирование виртуальных архитектур в суперкомпьютерах с массовым параллелизмом. //Информационные технологии и вычислительные системы. Москва, 2000. № 2,- С.5-21.

17. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.- 519 с.

18. Мизин И.А., Махиборода A.B. Архитектура самоопределяемых данных в среде взаимодействия открытых систем. // Материалы Н-ой Международной Конференции «Развитие и применение открытых систем», Петрозаводск, 1995.

19. Shmid P. Intel Merced vs. Alpha 21264. // http://www.thg.ru/cpu/19980725/index.html

20. Hamilton S. Taking Moore's Law into the Next century. Computer, 1999,1.21. http://www.cray.com/products/systems/.

21. Бурцев B.C. Новые подходы к созданию высокопараллельных вычислительных структур. // Искусственный интеллект 2000. Тез. докл. науч. конф. - Таганрог: ТРТУ, 2000.

22. Бурцев B.C. Новые подходы к оценке качества вычислительных средств. // Параллелизм вычислительных процессов и развитие архитектуры супер-ЭВМ. М.: Нефть и газ, 1997.

23. Бурцев B.C. Новые методы организации вычислительных процессов для задач, обладающих высоким параллелизмом. // Труды международного симпозиума ICSNET*. М., 2001. - С. 61-64.

24. Бурцев B.C. Вычислительные процессы с массовым параллелизмом. Электроника. Наука, Технология, бизнес, 2002. №1.

25. Кохонен Т. Ассоциативная память. М.: Мир, 1980.28. 32-разрядный транспьютер фирмы Inmos. // Электроника, 1985. №21, - С.35-39.

26. Fortran-M. // http://www.chair36.msiu.ru/education/cs/4-fplp/4-fplp-4/materials/parbook/node67.html30. http://www.llnl.gov/sisal/SisalHomePage.html.

27. Аллен P., Кеннеди К. Автоматическая трансляция Фортран-программ в векторную форму. // Векторизация программ: теория, методы, реализация. -М.: Мир, 1991.-С. 77-140.

28. MPI: the message passing interface. // http://parallel.ru/tech/techdev/mpi.html.34. http://www.openmp.org.

29. Проект: ИПС РАН /Т-система // http://parallel.ru/parallel/ /russia/map/data/project 15 .html.

30. Абрамов С., Адамович А., Коваленко M. Т-система: среда программирования с поддержкой автоматического динамического распараллеливания на платформе «IP-сеть UNIX-компьютеров», www.botik.ru/'abram/ts-pabs.html.

31. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Непроцедурный язык для решения задач математической физики. // Программирование. 1991. №2. -С. 80-94.

32. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Язык Норма.

33. Ш Препринт ИПМ им. М.В.Келдыша АН СССР, 1985. № 165.

34. Задыхайло И.Б., Крюков В.А., Поздняков Л.А. РАМПА система автоматизации разработки мобильных параллельных программ. // http://www.keldysh.ru/dvm/dvmhtml 107/publishr/rampar.html.

35. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж,

36. Корнеев В.В., Киселев А.В. Современные микропроцессоры. М.: Нолидж, 1998.

37. Кузьминский М. Между строк таблиц Linpack. // COMPUTER WEEK -Москва, 1998. № 13. - С. 41 - 43.49. http://www.starbridgesystems.com.

38. J. Child. FPGAs Pave Road to Reconfigurable Computing. // http://www.cotsjournalonline.com/pdfs/2004/02/cots02techfocusl.pdf.

39. R.W.Hartenstain, A.G.Hirschbil, M.Weber. Xputers: an Open Family of non-vov Neuman Arhitecture for Early Vision. // Int'l. Conf.on System Science. Honolulu, Hawaii, 1996.

40. R.W.Hartenstain, J.Beker.Performance Analylis in Co-DeX Partitioning for Sructural Programmable Acselerators. // Proc. of 5th Int'l. Workshop on Hardware/Software Co-Design Codes. Braunsweing, Germany, 1997.

41. M.Bolotski. Abacus: A Reconfigurable Bit Parallel Architectures. Ph.Dd.Thesis //. Massachusetts Insitut of Tehnologe, 1996. 126 PP.

42. Каляев А.В. Многопроцессорные вычислительные системы с программируемой архитектурой. М.: Радио и Связь, 1984. - 240 с.

43. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. - 380 с.

44. Каляев А.В., Левин И.И. Многопроцессорные системы с перестраиваемой архитектурой: концепции развития и применения. // Наука — производству, 1999. № 11. - С.11-19.

45. Перестраиваемые цифровые структуры на основе интегрирующих процессоров. / Под ред. А.В. Каляева. М.: Радио и связь, 1982. -368 с.

46. Kalyaev A.V. Ultra-high Performance Multiprocessor Supersystems with Programable Architecture. Aspects of computation on Asynchronous Parallel Processors. -Amsterdam. New York. Oxford. Tokyo, 1989. Pp. 111-123.

47. Каляев A.B., Станишевский О.Б. Принципы построения программно-аппаратных средств супермакрокомпьютеров. // Информатика, 1990. № 2. - С. 13-21.

48. Бабаян Б.А., Бочаров А.В., Волин А.С. и др. Многопроцессорные ЭВМ и методы их проектирования. / Под ред. Смирнова Ю.М. М.: Высшаяшкола, 1990.

49. Воеводин B.B. Математические модели и методы параллельных процессов. М.: Наука, 1986. - 286 с.

50. Воеводин В.В. Информационная структура алгоритмов. М.: Изд-во МГУ, 1997.

51. Воеводин В.В. Отображение проблем вычислительной математики на архитектуру вычислительных систем. // Вычислительная математика и математическое моделирование. Тр. международной конф. М.: Ин-т вычисл. математики РАН, 2000. - Т.1. - С. 242-255.

52. Воеводин В.В. Параллельные структуры алгоритмов и программ. М.: ОВМ АН СССР, 1987.

53. Воеводин В.В. Математические основы параллельных вычислений. -М.: МГУ, 1991.-345 с.

54. Siegel L.J., Siegel H.J., Swain Р.Н. Performance Measures for Evaluation Algorithms for SIMD-Machines. // IEEE Trans. Software Eng. V. 8. -№ 4. - Pp. 319-331.

55. Каляев B.A., Левин И.И., Фомин С.Ю. Об оценке эффективности решения задач математической физики на многопроцессорных системах. // Электронное моделирование, 1989. №6. - С. 11-15.

56. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. радио, 1972.-280 с.

57. Воеводин В.В. Воеводин Вл.В. Параллельные вычисления. С-Петербург: БХВ-Петербург, 2002. - 599 с.

58. Воеводин Вл.В. Статистические оценки возможности выявления параллельной структуры последовательных программ. // Программирование, 1990.-№4.-С. 44-54.

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

60. Программирование на параллельных вычислительных системах. / Под ред. Р. Бэба И. М.: Мир, 1991. - 376 с.

61. Самарский A.A. Введение в численные методы. М.: Наука, 1987.280 с.

62. Шуп Т.Е. Прикладные численные методы в физики и технике. М.: Высшая школа, 1990. - 255 с.

63. Каляев В.А., Левин И.И., Фомин С.Ю. Об эффективности моделирования на многопроцессорной системе процессов распространения

64. Ш цунами. // Сб. "Многопроцессорные вычислительные структуры", Таганрог,1987.-Вып. 9. С.14-18.

65. Каляев В.А., Левин И.И., Фомин С.Ю. Многопроцессорная система для оперативного моделирования гидрофизических процессов. // Сб.

66. Программные и аппаратные средства машинного моделирования". Москва, 1988.-С. 70-77.

67. Левин И.И. Организация вычислительного процесса для физико-топологического моделирования транзисторных структур СБИС на многопроцессорной системе. // Сб. "Математическое моделирование элементов и фрагментов БИС". Рига, 1990. - С. 51.

68. Рвачев В.Л. Шевченко А.Н., Левин И.И., Кошеленко А.И. Software and Hardware о f Simulation of Phisical Mechanical Fillds.// Сб. "Parallel Computing Technologies Word Scientific". Новосибирск, 1991. - Pp. 385-394.

69. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. М: Мир, 1978. - 848 с.

70. Применение цифровой обработки сигналов. / Под редакцией Э. Оппенгейма. М: Мир, 1980. -552 с.

71. Левин И.И., Пономарев И.М. Реализация быстрого преобразования Фурье на многопроцессорной системе со структурно-процедурной организацией вычислений. //Изв. вузов. Электромеханика, 1995. -№ 4. -С.72-74.

72. Левин И.И., Пономарев И.М. Методика организации высокоэффективных параллельных вычислений в многопроцессорных системах. // Тезисы международной конференции "Искусственный интеллект-2000", Кацивели. Таганрог: Изд-во ТРТУ, 2000. - С. 142-144.

73. Левин И.И., Пономарев И.М., Шматок A.B. Методы преобразования параллельных программ под структуру вычислительной системы. // Искусственный интеллект. Донецк: Наука i освгга, 2001. - №3. - С. 227-231.

74. Векторизация программ: теория, методы, реализация. / Сборник переводов статей. М.: Мир, 1991. -С. 246-267.

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

76. Lamport L. The parallel execution of DO loops. // Commun. ACM, 1974.-V.17.-№2.-Pp. 83-93.

77. Штейнберг Б.Я. Распараллеливание рекуррентных циклов с условными операторами. // Автоматика и телемеханика, 1995. -№6. С. 176-184.

78. Ривкин М.Н. Векторные операции для моделирования процедур преобразования данных. // Программирование, 1991. № 3.

79. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. / Учеб. пособие для вузов. М.: Высшая школа, 1983. - 272 с.

80. Левин И.И., Пономарев И.М. Структурно-процедурная реализация задачи трассировки. // Искусственный интеллект. Донецк: Наука i освгга, 2003. -№3. - С.121-129.

81. Aykanat С., Kurc T. M. and Ercal F. Parallelization of Lee's routing algorithm on a hypercube multicomputer," Proc. of 2nd European Dist. Mem. Сотр. Conf. (EDMCC2), April 1991. Pp. 244-253.

82. Левин И.И. Высокоэффективный алгоритм структурно-процедурной реализации задачи логико-временного моделирования на многопроцессорной системе. М., 1995. - Деп. в ВИНИТИ, № 1445-В95. - 31 с.

83. Левин И.И. Структурно-процедурная реализация функционального моделирования на многопроцессорной системе. М., 1995. - Деп. в ВИНИТИ, № 2043-В95. - 25 с.

84. Левин И.И., Левина М.Г. Структурно-процедурная реализация электрического моделирования на многопроцессорной системе. М., 1995. -Деп. в ВИНИТИ, № 3425-В95. - 25 с.

85. Левин И.И. Структурно-процедурная реализация электрического моделирования на многопроцессорной системе. // Известия ВУЗов "Электромеханика", 2002. №1. - С. 27-30.

86. Параллельные вычисления. / Под ред. Родрига Г. М.: Наука, 1986.376с.

87. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. - 256 с.

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

89. Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. / Пер.с англ. -М.: Радио и связь, 1986. 392 с.

90. Shore J.E. Second thoughts on parallel processing. Comput. Elect. Eng., 1973.-№1.-Pp. 95-109.

91. Каляев A.B., Левин И.И., Фрадкин Б.Г. Унифицированная элементная база для построения реконфигурируемых под задачу вычислительных систем. //Известия ВУЗов. Электроника, 1997. № 1. - С. 7583.

92. Левин И.И., Штейнберг Б .Я. Сравнительный анализ эффективности параллельных программ для различных архитектур многопроцессорных систем. // Искусственный интеллект. Донецк: Наука i осв1та, 2001. - № 3. - С. 234-242.

93. Хуан К. Перспективные методы параллельной обработки и архитектура суперЭВМ. //ТИИЭР, 1987. № 10. - С.4-41.

94. Майерс Г. Архитектура современных ЭВМ. М.: Мир, 1985. - Кн.1.364 с.

95. Дейкстра Э. Взаимодействие последовательных процессов. // В сб. Языки программирования. / Под ред. Женюи Ф. М.: Мир, 1972. - С. 9-86.

96. Джехани Н. Язык Ада. М.: Мир, 1988. -540 с.

97. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.-265с.

98. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Вильяме, 2003. - 320с.

99. Фути К., Судзуки Н. Языки программирования и схемотехника СБИС. М.: Мир, 1988. - 224 с.

100. Кутепов В.П., Кораблин Ю.П. Язык граф-схем параллельных алгоритмов. // Программирование, 1978. № 1. - С. 1-16.

101. Краснов С.А. Транспьютеры, транспьютерные вычислительные системы и Оккам. // Вычислительные процессы и системы. М.: Наука, 1983. -С.5-80.

102. The Occam Language.// http://www.wotug.org/occam/.

103. Затуливетер Ю.С. Введение в проблему параметризованного синтеза программ для параллельных компьютеров. / М., ИПУ РАН, препринт, 1993. -89 с.

104. Дейкстра Э. Дисциплина программирования. -М.: Мир, 1978. 278 с.

105. Элементы параллельного программирования. / Под ред. Котова В.Я. -М.: Радио и связь, 1983. 240 с.

106. Бабенко JI.K., Макаревич О.Б., Чефранов А.Г. Принципы описания и организации асинхронных крупноблочных вычислений в многопроцессорных системах. // Электронное моделирование, 1988. № 3. - С. 13-17.

107. May D. Occam 2 manual.-Bristol, UK:Inmos Ltd, 1986.

108. Вальковский B.A., Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. - 176 с.

109. Хендерсон П. Функциональное программирование. / Пер. с англ. -М.: Мир, 1983.

110. Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. //Программирование, 1992. № 3. - С. 16-37.

111. Сир Ж.К. Метод потока операндов в многопроцессорных системах типа MIMD // В сб. Системы параллельной обработки. / Под ред. Ивинса Д. -М.: Мир, 1985.-С. 240-276.

112. Chamberlin D.D.Parallel Implementation of a'LAU Ph.D.Thesis Report 19, 1971.

113. Котов B.E. Теория параллельного программирования. Прикладные аспекты. // Кибернетика, 1974. № 1. - С. 1-16.

114. Стерлинг JL, Шапиро Э. Искусство программирования на языке Пролог. М.: Мир, 1990. - 235 с.

115. Братко И. Программирование на языке Пролог для искусственного интеллекта. М.: Мир, 1990. - 560 с.

116. Гузик В.Ф., Левин И.И., Сафронов О.О. Представление параллелизма в программах для многопроцессорной системы с программируемой архитектурой. // Известия ВУЗов СКНЦВШ. Технические науки, 1996. № 2. - С. 4-15.

117. Kuch D.J. ILLIAC IV. Software and Application Programming. // IEEE Trans. Computer, 1968. - V C17. - № 8. - Pp. 758-770.

118. Левин И.И. Язык параллельного программирования высокого уровня для структурно-процедурной организации вычислений. // Труды Всероссийской научной конференции. М.: Изд-во МГУ, 2000. - С. 108-112.

119. СБИС для распознавания образов и обработки изображений. / Под ред. К. Фи. М.: Мир, 1988. - 248 с.

120. Левин И.И., Пономарев И.М. Структурно-процедурная реализация кластерной группировки данных в задачах обработки изображений. // Изв. вузов. Электромеханика, 1999. №2. - С. 54-57.

121. Левин И.И., Шахов Р.В. Алгоритмы трансляции структурно реализуемого фрагмента задачи для многопроцессорной системы с программируемой архитектурой. // Искусственный интеллект. Донецк: Наукаi освгга, 2003. №3. - С. 138-146.

122. Левин И.И., Шахов P.B. Алгоритмы трансляции структурно реализуемого фрагмента задачи для многопроцессорной системы. // Методы и средства обработки информации. Труды первой Всероссийской научной конференции. М.: МГУ, 2003. - С. 125-130.

123. Штейнберг Б.Я. Бесконфликтные размещения массивов при параллельных вычислениях. // Кибернетика и системный анализ, 1999. № 2.

124. Вычислительная математика и математическое моделирование. // Труды международной конференции. М.: Ин-т вычислительной математики РАН, 2000. - Т. 1,2.

125. Высокопроизводительные вычисления на кластерных системах. // Материалы международного научно-практического семинара. Нижний Новгород: Изд-во Нижегородского университета, 2002. - 218 с.

126. Левин И.И. Структурно-процедурное программирование. //Тезисы международной конференции "Искусственный интеллект". Таганрог: Изд-во ТРТУ, 2000.-С. 148-150.

127. Каляев A.B., Левин И.И., Шматок A.B. Средства программирования суперкомпьютеров с массовым параллелизмом ■ и программируемой архитектурой. // Тезисы международной конференции "Искусственный интеллект". Таганрог: Изд-во ТРТУ, 2000. - С. 151-152.

128. Левин И.И. Ресурсонезависимое параллельное программирование. // Искусственный интеллект. Донецк: Наука i освгга, 2002. - №3. - С.277-285.

129. Pountain D. High-powered Helios.//PC-World, 1988. V.ll. - №7. -Pp.162-165.148. http://www.perihelion.co.uk/helios/tranos.html.

130. Ачасова C.M., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990.

131. Ильин В.П. О стратегиях распараллеливания в математическом моделировании. //Программирование, 1999. № 1. - С. 41-46.

132. Миренков H.H. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989.

133. Тербер К. Дж. Архитектура высокопроизводительных • вычислительных систем. / Пер. с англ. М.: Наука, 1985.

134. Каляев A.B., Левин И.И. Структурно-процедурная организация параллельных вычислений. // Труды межд. конф. "Параллельные вычисления изадачи управления (РАСО'2001)". М: ИПУ РАН им. В.А.Трапезникова, 2001. -Т.5. - С.112-119.

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

136. Евстигнеев В.А. Применение теории графов в программировании. / Под ред. Ершова А.П. М.: Наука, 1985.

137. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ. М.: Наука, 1981.

138. Бочаров Н.В. Технологии и техника параллельного программирования. // Программирование, 2003. №1. - С. 5-23.

139. Ершов Н.М., Попов A.M. Оптимизация параллельных вычислений с учетом архитектуры и быстродействия связей в вычислительной системе. // Вестн. Моск. ун-та. Сер. 15, Вычислительная математика и кибернетика. 1993. -№ 1. С. 24-30.

140. Левин И.И., Шматок A.B. Технология индуктивных параллельных программ. // Труды международной научно-технической конференции. -Таганрог: Изд-во ТРТУ, 1999. С. 142-146.

141. Станишевский О.Б., Левин H.H. Метод решения задач в частных производных на макрокомпьютере. // В кн. Многопроцессорные вычислительные структуры. Таганрог, 1991. - С. 14-15.

142. Левин И.И. Элементная база для построения реконфигурируемых нейросетей. // Нейрокомпьютеры. Разработка и применение, 2001. № 7-8. - С. 36-45.

143. Левин H.H., Виневская Л.И., Дмитренко H.H., Логвинов С.А. Элементная база для построения высокопроизводительных систем. // Труды международной научно-технической конференции. Таганрог: Изд-во ТРТУ, 1999.-С. 98-103.

144. Каляев A.B. Принципы и методы программирования виртуальных архитектур в многопроцессорных универсальных суперкомпьютерах. // Высокопроизводительные вычисления и их приложения. Труды всероссийской научной конференции. -М.: Изд-во МГУ, 2000. С. 12-16.

145. Каляев A.B., Станишевский О.Б., Фрадкин Б.Г. Макропроцессорный комплект СБИС. // Сборник докладов I Всесоюзной конференции "Однородные вычислительные средства и систолические структуры". Львов, 1990. - Т.2. -С.33-46.

146. Корнеев В.В., Киселев A.B. Современные микропроцессоры. М.: • Нолидж, 1998.

147. Станишевский О.Б. Эффективность арифметической обработки при конвейерных и нейроконвейерных вычислениях. // Конвейерные вычислительные системы. Тезисы докладов. Кишинев, 1988.

148. Макропроцессор: Патент РФ № 2210808 на изобретение по заявке № 2001100388. / Каляев A.B., Левин И.И., Виневская Л.И., Станишевский О.Б. -Заявл. 05.01.2001; Опубл. 20.08.2003. Бюлл. № 23. - 26 с.

149. Матричный коммутатор: Патент РФ № 2059288 на изобретение по заявке № 94029855/09. / Левин И.И., Ерохин A.B., Рыжих O.A., Фрадкин Б.Г. -Заявл. 05.08.1994; Опубл. 27.04.1996. Бюлл. № 12. - 5 с.

150. Мультиконтроллер распределенной памяти: Патент РФ № 2210804 на изобретение по заявке № 2001122359. / Каляев A.B., Левин И.И., Виневская Л.И., Дмитренко H.H. Заявл. 08.08.2001; Опубл. 20.08.2003. -Бюлл. №23.-44 с.

151. Суммирующее устройство: Патент РФ №2069009 на изобретение по заявке №93054701. / Виневская Л.И., Станишевский О.Б., Ерохин A.B., Рыжих O.A.-Опубл. 10.11 1996.-Бюл.№31.-12с.

152. Устройство умножения: Патент РФ № 2418270 на изобретение по заявке № 98110224. / Каляев A.B., Виневская Л.И., Станишевский О.Б. Опубл. 27.04.2000. - Бюл. № 12. - 9 с.

153. Каляев A.B., Духнич Е.И., Сулин Г.А. Алгоритмы макроопераций для аппаратурной реализации в микропроцессорах с программируемой архитектурой. // Известия высших учебных заведений. Технические науки. -Ростов-на-Дону, 1996. № 2. - С. 15-20.

154. Левин И.И., Шахов Р.В., Шматок A.B., Сластен Л.М. Математическое обеспечение многопроцессорных вычислительных систем с программируемой архитектурой. // Искусственный интеллект. Донецк: Наука i осв1та, 2002. - №3. -С.286 294.

155. Ясинявичус Р. Параллельные пространственно-временные вычислительные структуры. Вильнюс: Мокслас, 1988. - 183 с.

156. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. Д.: Машиностроение, 1979. - 379 с.

157. Норкин К.Б. Специализированные гибридные управляющие вычислительные устройства. М.: Энергия, 1984. - 215 с.

158. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. М.: Наука, 1981.

159. Касьянов В.Н., Оптимизирующие преобразования программ. М.: Наука, 1988.-336 с.

160. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. М.: Радио и связь, 1981.

161. Kuck D. The structure of computers and computations. John Wiley and Sons. Inc., New York, NY, 1978.

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

163. Гузик В.Ф. Модульные интегрирующие вычислительные структуры. М.: Радио и связь, 1984. - 216 с.

164. Каляев A.B., Каляев И.А., Левин И.И., Пономарев И.М. Параллельный компьютер с программируемой под структуру задачи архитектурой. // Труды шестого международного семинара "Распределенная обработка информации". Новосибирск, 1998. - С.25-29.

165. Коуги П.М. Архитектура конвейерных ЭВМ. / Пер. с англ. М.: Радио и связь, 1985.

166. Самофалов К.Г., Луцкий Г.М. Основы теории многоуровневых конвейерных вычислительных систем. Москва: Радио и связь, 1989. - 272 с.

167. Станишевский О.Б. Сверхскоростные СБИС для многопроцессорных вычислительных систем. // XXX Всесоюзная школа семинар им. М.А. Гаврилова "Развитие теории дискретных систем и проблема логического проектирования СБИС". Кишинев, 1988.

168. Гузик В.Ф., Каляев A.B., Станишевский О.Б. Архитектура микропроцессоров с программно-перестраиваемой структурой и их математического обеспечения. // Тезисы докладов Всесоюзной конференции

169. Ш "Микропроцессоры-85": Методы и микроэлектронные устройствапреобразования и обработки информации. М.: Изд-во МИЭТ, 1985. - Т.2.

170. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распараллеливающих компиляторах. // Программирование, 1996. № 6. - С. 12

171. Wolf M., Baneijee U. Data Dependence and i ts Application to Parallel Processing/ International Journal of Parallel Programming//. Vol.16. - № 2. 1987. -Pp. 137-178.

172. J.Anderson, M.S.Lam. Global Optomizations for Parallelizm and Localits on Scalable Parallel Machines. // Rpocecdings of SIGPLAN'93 Conference on Programm Language Design and Implementation. Albucerque, 1993.

173. Amy W. Lim, Monika S. Lam Maximizing Parallelism and Minimizing Synchronization with Affine Partitions. Parallel Computing, 24, 1998. Pp. 445-475.

174. Каляев A.B., Левин И.И., Пономарев И.М. Базовый модуль многопроцессорной вычислительной системы с программируемой архитектурой. // Наука производству, 1999. № 11. - С. 33-39.

175. Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование многопроцессорных систем с массовым параллелизмом. // Искусственный интеллект. Донецк: Наука i oceiTa, 2002. - №3. - С. 295-302.

176. Левин И.И. Структурно-процедурное программирование. // Тезисы докладов Международной научной конференции "Искусственный интеллект-2000", п. Кацивели, 2000. С. 148-150.

177. Савин Г.И., Телегин П.Н., Шабанов Б.М. Кластеры Беовульф. // Известия Вузов. Электроника, 2004. №1. - С.7-12.

178. Архитектура семейства компьютеров Ultra. //http://www.jetinfo.rU/1997/23-24/l/arhult.html.

179. Джон Т. Архитектуры вычислительных систем. // Электроника, 1989. №2. - С. 11-20.206. http: //parallel .ru/computers/computers.html.• 207. Stokes R.A. ILLIAC-IV:route to Parallel Computers. // Electronic Design,1967.-№26.-Pp.64-69.

180. Connection Mashine. Model CM-2. Technicae Summarg. Thinking Mashine Corporation, Cambridge, MA, 1989.

181. Y.Pan, S.Q.Zheng, K.Li, H.Shen. An Improved Generalization of Mesh-Connected Computers witch muple Buses. // IEEE Trans, on Parallel and Distributed Systems, 2001. V. 12. - № 3. - pp. 293-305.210. http://uginfo.rsu.ru/img/prj/ncube.

182. Дубова H. Суперкомпьютеры nCube. // Открытые системы, 1995.2.

183. Каляев A.B. Однородные коммутационные регистровые структуры. -М.: Советское радио, 1978. 240 с.

184. Левин И.И. Модульно-наращиваемая многопроцессорная вычислительная система со структурно-процедурной организацией вычислений на основе ПЛИС-технологии. // Искусственный интеллект. Донецк: Наука i ocBÎTa, 2003. - №4. - С.446-453.

185. Хэндлер В. Новая архитектура ЭВМ как увеличить параллелизм, не увеличивая сложности. // Системы параллельной обработки. / Под ред. Ивенса Д. - М.: Мир, 1985.-С. 10-44.

186. Handler W. Zur Geneslogie, Stuktur und Klasssifizieren von Rechern Arbeitsbetdeiberichte des IMMD, 1976. № 9. - Ss. 1-30.

187. Евреинов Э., Хорошевский В. Однородные вычислительные системы. Новосибирск: Наука, 1978.

188. Метлицкий Е.А., Каверзнев В.В. Системы параллельной памяти. Теория, проектирование, применение. Ленинград: ЛГУ, 1989.220. http://www.osp.ru/lan/bg96/nms.htm.

189. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир,1981.

190. Евстигнеев В.А. Применение теории графов в программировании. // -М.: Наука, 1985.-352 с.

191. Левин И.И., Сластен Л.М. Унифицированный алгоритм коммутации элементов многопроцессорной системы при структурной реализации фрагмента задачи. // Искусственный интеллект. Донецк: Наука i освгга, 2003. - № 3. - С. 130-137.

192. Левин И.И., Сластен Л.М. Алгоритм коммутации элементов многопроцессорной системы со структурно-процедурной организацией вычислений. // Труды Первой Всероссийской научной конф. "Методы и средства обработки информации". -М.: МГУ, 2003. С. 119-124.