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

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

иил/7б57

КАЛЯЕВ Захар Владимирович

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

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

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

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

2 7 ДЕИ 2007

Таганрог-2007

003177657

Работа выполнена на кафедре вычислительной техники Технологического института Южного федерального университета в г Таганроге.

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

доктор технических наук, профессор Золотовский Виктор Евдокимович

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

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

доктор технических наук, профессор Целых Александр Николаевич

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Научно-исследовательский вычислительный центр Московского государственного университета им. М. В. Ломоносова, г. Москва

Защита состоится "28"декабря 2007 г. в 1420 на заседании диссертационного совета Д 212.208.24 Южного федерального университета

по адресу: 347928, г Таганрог, ул. Чехова 2, корп. И, комн. 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан "27" ноября 2007 г.

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

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

диссертационного совета ¿^уУ/^у^^ А П. Кухаренко

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

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

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

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

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

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

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

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

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

Для достижения этой цели в работе были решены следующие задачи

1) проведен анализ методов организации параллельных вычислений в РВС,

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

2) разработан метод автоматического масштабирования кадров путем распараллеливания в зависимости от вычислительного ресурса,

4) разработан метод масштабирования многокадровых параллельных программ,

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

6) проведен анализ эффективности разработанных методов и средств на примерах решения прикладных задач

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

Научная новизна работы состоите том, что в ней разработаны

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

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

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

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

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

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

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

В диссертационной работе решена важная научно-техническая задача, заключающаяся в создании методов и программных компонентов операционной системы, обеспечивающих автоматическое масштабирование прикладных параллельных программ на свободный ресурс РВС и позволяющих на 30% сократить время прохождения потока разнородных заданий Новые методы автоматического масштабирования позволяют сократить время создания параллельных масштабируемых программ для РВС в 1,5-4 раза Разработанная подсистема удаленного доступа к вычислительным ресурсам РВС позволяет упростить процесс отладки масштабируемых прикладных параллельных программ и, как следствие, сократить время их создания

Реализация и внедрение результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, в том числе в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы», в рамках научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», выполняемыми НИИ многопроцессорных вычислительных систем Южного федерального университета (г Таганрог) Созданные методы и программные компоненты внедрены в вч 26165 (г Москва), ФГУП «Курский НИИ» МО РФ (г Курск), Южном научном центре РАН (г Ростов-на-Дону), НИИ многопроцессорных вычислительных систем Южного федерального университета (г Таганрог)

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

На международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», 2003 г, 2005 г, Геленджик, на Международной научно-технической конференции «Искусственный интеллект Интеллектуальные и многопроцессорные системы», 2004 г, 2006 г, Кацивелли, на Международной научной школе «Высокопроизводительные вычислительные системы», 2004 г, 2005 г, 2006 г , на ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, 2005г, 2006г 2007г, Ростов-на-Дону, на IV республиканской научно-практической конференции «Дагинформ-2005», 2005г, Махачкала, на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы», 2007г, Геленджик

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

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

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

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

- программные компоненты многозадачной операционной системы для РВС

Личный вклад автора. Все научные и практические результаты получены автором

лично

Публикации. По теме диссертационной работы опубликовано 17 печатных работ, из них 5 статей, 2 из которых входят в список ведущих рецензируемых журналов ВАК, 12 тезисов и материалов докладов на российских и международных научно-технических конференциях

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

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

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

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

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

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

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

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

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

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

В диссертации разработана структура ОС, обеспечивающая многозадачный режим функционирования РВС (рис 1)

В состав ОС предложено ввести следующие основные компоненты подсистему

удаленного

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

Распределенная сеть

I Поток Г задании

Подсистема удаленного многопопьзовательског о доступа

Поток заданий

Планировщик заданий

заданна (исполняемым код пиограммыУ

номера модупаА выдалемныа для решении задания

Подсистема посттрансляции

масштабированные код программы

Загрузчик программ

Драйверы и библиотеки низкоуровневого доступа

РВС (СМД),

заданий,

посттрансляции

модулей

программ,

параллельных

монитор

вычислительного драйверы и

подсистему исполняемых параллельных загрузчик программ, состояния ресурса, библиотеки

Рис I Структура ОС

низкоуровневого доступа СМД предназначенадля обеспечения

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

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

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

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

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

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

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

Требования к описанию

Рис 2 Подсистема посттрансляции

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

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

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

Слоем называется подграф для которого выполняется условие существует хотя бы одна дуга (а,Ъ), где вершина а е 5*,, вершина Ь и Дуги, соединяющие слои, называются межслойными дугами

Каждый подграф состоит из множества подграфов Q,Jk

При этом все подграфы должны быть изоморфны друг другу Подграфы QlJk называются базовыми подграфами Внутрислойные дуги должны принадлежать только одному базовому подграфу, те если существует дуга (а,Ь) е то вершина ак и вершина бефу*

Базовый подграф Qч к е Яу тогда, когда существует хотя бы одна дуга (а,Ь) такая, что а е£>,0-1», Ь е()цк

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

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

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

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

На рис 3 показан фрагмент процедуры покрытия вершин функционально-регулярного графа кадром, вычислительного ресурса для реализации которого достаточно, чтобы объединить два базовых подграфа £) На данном рисунке масштабирование кадра реализовано путем распараллеливания (одновременная независимая обработка подграфов £>Л и

При таком объединении масштабированный кадр включает в себя операционные, входные и выходные вершины объединяемых кадров

= К и XI Х*[= XI их] На основе функции ^ отображения подграфов () внутри слоя необходимо определить правила объединения подграфов Q

йгто-

х; =Р{хи),х>м=Р(х>К) Подставив Х{ в последнее равенство, получим

Следовательно,

= ад,)) )

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

В связи с этим при масштабировании кадра путем распараллеливания функция F должна описываться таким образом, чтобы существовала возможность определения функции композиции Ч>{Х',), которая определяется следующим образом

-хО) )=1пхи), (1)

функция ) по трудоемкости

вычисления должна быть соизмерима с трудоемкостью вычисления функции Р В случае если данное условие выполняется, то нахождение композиции функции ^ возможно выполнить на этапе трансляции кадра, а подстановку параметра в функцию <р(Х[) можно осуществить на этапе постановки задачи на решение

При распараллеливании предъявляются дополнительные требования к каналам физической памяти Для сравнения можно привести параметры типового базового модуля РВС Базовый модуль содержит 256 элементарных процессоров и 32 канала Рис 3 Фрагмент процедуры покрытия распределенной памяти Преимуществом вершин функционально-регулярного графа масштабированием кадра путем

кадром распараллеливания является отсутствие тре-

бований к межмодульной коммутационной системе РВС

На рис 4 показан фрагмент процедуры покрытия вершин функционально-регулярного графа кадром, вычислительного ресурса для реализации которого достаточно, чтобы объединить два базовых подграфа На данном рисунке масштабирование кадра

реализовано путем конвейеризации (обработка подграфов * и

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

О/=Ф«2Г>0У' ).

Х{ =Ф(Х'е'\ХГ, ), ХГ' )

Подставив Х{ в последнее равенство* получим

ХГх=Ф(Ф(Х1\ ,х'-\ ))

Следовательно,

ХГ =ФЩ (Х1Л, ,Х1'\ ,ХГ

))

При больших значениях п вычисление X/*" является достаточно трудоемким роцессом рекурсивного вызова функции Ф и может существенно замедлить процесс асштабирования кадра

В связи с этим при масштабировании кадра с помощью конвейеризации функция Ф должна описываться так, чтобы существовала возможность определения функции композиции ф(Х/), которая определяется следующим образом:

ф{ХГ)=1ф{Х1~\Х1~\...), (2)

где функция ф(Х!*п) по трудоемкости

вычисления должна быть соизмерима с

трудоемкостью вычисления функции Ф. В

случае если данное условие выполняется,

то нахождение композиции функции Ф

возможно выполнить на этапе трансляции

кадра, а подстановку параметра в функцию

ф(Х!*") можно выполнить на этапе

постановки задачи на решение.

Необходимо отметить, что несмотря

на кажущуюся сложность вычисления

указанной функции, количество

параметров функции не так велико.

Например, для задач символьной

обработки количество параметров

„ . _ , функции - 1, для задачи решения СЛАУ-

Рис. 4. Фрагмент процедуры обхода вершин Т '

, , 2, для задач математической физики,

функционально-регулярного графа кадрсм. ,

решаемых сеточными методами - 3.

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

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

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

Задачу математической физики, решаемой сеточными методами, целесообразно масштабировать с помощью предложенного метода распараллеливания кадров. Базовый подграф (Э соответствует вычислениям, проводимым в сеточной области методом одновременных смещений. Для одномерной сеточной области на входы 1-го подграфа/-го слоя (2 поступают^./, хданные 0-1)-го слоя. Функционально-регулярный граф задачи представлен на рис. 5.

<хт..,х„>

<Хп 1,..,Х,>'

<Х„-!,..,Х,>

\<Ут.1-:У1,Уо,*.*>

Рис. 6. Схема масштабирования кадра методом распараллеливания.

Рис.5 Функционально-регулярный граф задачи.

Функции ГиФ будут определяться следующим образом:

Е- А( =Лм+ДЛ, X, =*А1.

Композиция функции ^ будет определяться следующим образом:

и„ = ° Г: А,- = А^-п+п-ЛА, X, .

Функция отображения межслойныхдуг определяется следующим образом:

Функция композиции будет определяться следующим образом:

ФП = о Ф

к =1

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

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

Кадр задачи решения СЛАУ методом Гаусса целесообразно масштабировать с помощью предложенногометода конвейеризации кадров. Функционально-регулярный

граф задачи решения СЛАУ приведен на рис. 7.Функции Г и Ф исходного функционально-

регулярного графа определяются следующим образом:

Г: ^</•';,/?2>; Г,: А, =4.,, X, = «Ц ; Р2: А, +&, Д = 1, X, =*А1 . Композиция функции ^ определяется следующим образом:

Ч>. =}хр1- л< = А-п- X, =М ; »

(»„ = о Р2: Л,. = + пАА, X, = *А, .

Функция отображения межслойныхдуг определяется следующим образом:

Ф: ф=<ф,,ф2>\ Ф,: X/ = бГ1; Ф2: X/ = <2>л. Композиции функции Ф определяется следующим образом:

Ф„ = Iф,: Х{ = ер Ф. = £Ф2: X! = е/-"'.

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

функционально-регулярный граф решения СЛАУ, приведена на рис. 8.

-----• ^ '

Рис. 8. Схема масштабирования путем конвейеризации. |

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

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

решения СЛАУ.

Р, производительность

Кадр С

Кадр А

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

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

Кадры структурно-Кадр в процедурной программы

имеют собственную

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

Например, на рисунке 9 показано, что задаче, 9 10 11 12 состоящей из трех кадров,

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

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

Остаточное количество базовых модулей для многокадровой задачи определяется ;ледующим образом:

Xj=m, ecnufj(m)>fj(m-l), где т=п.Л\ hj= птах -х/, H=max(hj),j=l..J, J - количество кадров задачи; "max-количество модулей системы; я-количество модулей выделенное для решения задачи. Количество ресурса, достаточное для обеспечения локального прироста фоизводительности системы, определяется след>ющим образом: deltaj=F(j+l), если F(j+l)>F(j),j=n..nnax-, Delta = Max(deltaj), j=n..nmax.

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

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

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

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

поставляемые вместе с программой (ИПП)

■$a5B3STJ52545SW 0x23 4S61FF28450129 0(284561292345056;

0*ZS4S«1FF28450J29 0»2>4S612828450561

Библиотека типовых схем масштабирования

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

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

Если кадр секции |

сформулирован в терминах технологии ИПП, схема

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

секции для каждого из базовых модулей РВС. Модифицированные (масштабированные) секции I

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

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

Модификация секции на основе поставляемых с программой схемами масштабирования

Модификация секций на основе схем масияа би рова н ия из библиотеки

Подсистема п острая сляу.

QK780061FF2R4S0129 0x23 4561J32 4450561 ¿ui44S6l2aifc«54l79 1 0x28456 If F 28*50129 I CSS4S612928*50065

0*284501*9284121» 0Х2В4661FF2S4S0129 0*2345612328450561 I 9x284561FF28450129 I 0x28456)2936450541

изпягиятгг

0*284661FF284S0129 СК2845612928450561

Tb2A4Soii«il5ei»" СК2М 56129284 И561

ГБг5*35Т5Е545вТЯ~)

0A284S61FF2S4SO129

0»28*S6 <2828450361 I ♦

Загрузчик параллельных программ - *

Рис. 10. Схема обработки секций исполняемого модуля параллельной программы

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

Время прохождения потока заданий, сек

Время прохождения потока заданий, сек

Количество БЫ

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

- Стандартный алгоритм планировщика заданий

- Модифицированный алгоритм планировщика заданий

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

Разработана подсистема удаленного многопользовательского доступа к ресурсам РВС. Подсистема обеспечивает прием и обработку удаленных запросов на исполнение параллельных программ на РВС. На рис. 12 представлена программа-сервер доступа к вычислительным ресурсам РВС. На рис. 13 представлена программа-клиент мониторинга состояния базовых модулей РВС.

р ЬтО[и*| (7 :гм1

Г

V ЬпЭ!»-,) Г? ЫМГмл] Г »«6

У <Ю1сд

824.19127.&111 слпвйвй 624:» 20 0* 1 СЧШ СО Н«л..7 1524:22127 00.1 -7

В22121 « а! ЫмХЬ Мт 7 182422127 0 41 С«**» ГГ М«Л. 7 13.2i.3i 127 00 1 С.асеАЛ

142X3! 24 041 1 »24:56 1 47 0 0 1 са**с1»1 1Э215Е127 0 01 СЧ'г*с_С0 7 182501 127001 СЛ'гм.СО й« 7 18 25:02 027 5 % 1 С««*;!»« ЬкяК*. 1&2&0212700 1<Ь«олпесЫ 1825 00 1 27

уат иг?«.».! О!»«»«. .7 1»Ж34127.!1П5№;мг»Л(я«. .7 1825 34 38 7 8 0в1Тм*1««С4 7 &2& 34 1 97 а81СПв»М«гпБ4 7 1825 3*127.501 ОМС Ям 7

:.....■ р рРЙ§

!йы«о(<«| О

®Ьг»1 а

□ ЬЙ а

а

а

□ ьт5 а

2Ьт6[£») а

ШЬЛПюу! а

Рис. 12. Программа-сервер доступа к Рис. 13. Программа-клиент мониторинга

вычислительным ресурсам РВС. состояния вычислительных модулей РВС.

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

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

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

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

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

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

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

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

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

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

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

1) Шматок АВ, Каляев ЗВ, Структурно-функциональный и структурно-декларативный методы разработки компонентов масштабируемых параллельных программ Тематический выпуск «Интеллектуальные и многопроцессорные системы» Известия ТРТУ - Таганрог Изд-во ТРТУ, 2004 -С 64-70

2) Каляев 3 В, Коваленко А Г, Многозадачная распределенная операционная система многопроцессорнойвычислительной системы с программируемой архитектурой Известия ТРТУ -Таганрог Изд-во ТРТУ, 2006 - С 179

3) Левин И И, Шматок А В, Каляев 3 В , Средства разработки параллельных программ для многопроцессорных вычислительных систем с программируемой архитектурой Искусственный интеллект Донецк (Украина) изд-во ДонГИИИ "Наука i осв1та", №3,2003 - С 147-149

4) Шматок А В, Каляев 3 В, Декларатнвньй и функциональный методы разработки компонентов масштабируемых параллельных программ Материалы международной научно-технической конференции «Искусственный интеллект Интеллектуальные и многопроцессорные системы», 20-25 сентября 2004г - Таганрог Изд-во ТРТУ, 2004 -Т 1 -С 227-229

5) Каляев 3 В Процедура масштабировашя задачи сложения чисел для МВС ПА Материалы первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН - Ростов-на-Дону Изд-во ЮНЦ РАН, 2005 - С 231-232

6) Каляев 3 В Процедура масштабирования операции умножения матриц Материалы Международной научной молодежной школы «Высокопроизводительные вычислительные системы», Таганрог Изд-во ТРТУ, 2005 С 176-178

7) Каляев 3 В Масштабирование операции умножения матриц Материалы IV республиканской научно-практической конференции «Дагинформ-2005» - Махачкала ДНЦ РАН, 2006 - С 190-192

8) Каляев 3 В Многозадачная распределенная операционная система Искусственный интеллект - Донецк Наука i освгга, 2006 - №3 - С 144-147

9) Каляев 3 В Структура многозадачной распределенной операционной системы Международна научно-технической конференции «Искусственный интеллект Интеллектуальные и многопроцессорные системы» - Таганрог Изд-во ТРТУ, 2006 - Т 2 -С 102-103

10) Каляев 3 В Компоненты многозадачной операционной системы для реконфигурируемой вычислительной системы Материалы Третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ PAR-Росгов-на-Дону Изд-во ЮНЦ РАН, 2007 -С 140-141

11) Каляев 3 В Система автоматического масштабирования параллельных программ для реконфигурируемых вычислительных систем Материалы Международной научно-технической конференции «Многопроцессорныевычислительные и управляющие системы - 2007» - Таганрог Изд-воТТИЮФУ,2007 - Т 1 -С 285-289

ЛР № 020565 от 23 июня 1997 г Подписано к печати /У. 2007 г Формат 60x84 1/16 Бумага офсетная Печать офсетная Уел пл -2,0 Уч -издл -1,8 Заказ № 271 Тираж 120 экз

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

ВВЕДЕНИЕ.

1. АНАЛИЗ СРЕДСТВ СОЗДАНИЯ МАСШТАБИРУЕМЫХ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ.

1.1. Архитектуры современных многопроцессорных систем.

1.2. Методы и средства создания масштабируемых параллельных программ.

1.3. Операционные системы многопроцессорных вычислительных систем.

1.4. Современные реконфигурируемые вычислительные системы и средства разработки параллельных масштабируемых программ.

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

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

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

1.8. Выводы.

2. МЕТОДЫ АВТОМАТИЧЕСКОГО МАСШТАБИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ ДЛЯ РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

2.1. Методы автоматического масштабирования однокадровых задач.

2.2. Масштабирование задачи математической физики.

2.3. Масштабирование задачи решения системы линейных алгебраических уравнений.

2.4. Метод автоматического масштабирования многокадровых задач.

2.5. Выводы.

3. КОМПОНЕНТЫ МНОГОЗАДАЧНОЙ ОПЕРАЦИОННОЙ СИСТЕМЫ

РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

3.1. Подсистема посттрансляции.

3.2. Планировщик заданий.

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

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

3.5. Загрузчик параллельных программ.

3.6. Выводы.

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

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

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

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

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

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

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

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

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

Целыо работы является минимизация времени решения потока разнородных заданий на РВС.

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

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

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

Для достижения указанной цели должны быть решены следующие научные задачи:

1) проведен анализ методов организации параллельных вычислений в РВС;

2) разработаны методы автоматического масштабирования однокадровых и многокадровых параллельных программ для РВС;

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

4) проведен анализ эффективности разработанных методов и средств на примерах решения прикладных задач.

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

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

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

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

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

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

Практическая значимость. В диссертационной работе решена важная задача, заключающаяся в создании методов и программных компонентов операционной системы, обеспечивающих автоматическое масштабирование прикладных параллельных программ на свободный ресурс РВС и позволяющих на 30% сократить время решения потока разнородных заданий. Новые методы автоматического масштабирования позволяют сократить время создания параллельных масштабируемых программ для РВС в 1,5+4 раза. Разработанная подсистема удаленного доступа к вычислительным ресурсам РВС позволяет упростить процесс отладки масштабируемых прикладных параллельных программ и, как следствие, сократить время их создания.

Использование результатов работы. Материалы диссертации использовались при выполнении ряда НИОКР, в том числе в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы», в рамках научно-технической программы Союзного государства «Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем», выполняемыми НИИ многопроцессорных вычислительных систем Южного федерального университета (г. Таганрог). К наиболее значимым НИОКР относятся:

- ОКР «Модульно-наращиваемая многопроцессорная вычислительная система с программируемой архитектурой на основе реконфигурируемой элементной базы», № гос. per. 0122.0510630, инв. № 02.2.007 00661, Таганрог, НИИ МВС ТРТУ, 2005 г.;

- НИОКР «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса», № гос. per. 01.2.00611470, инв. 02.2.00606581, Таганрог, НИИ МВС ТРТУ, 2006 г.;

НИР «Разработка и исследование принципов построения самонастраиваемых вычислительных систем на основе реконфигурируемых вычислительных блоков», № гос. per. 01.20.0301381, инв. № 02.2.00 601553, Таганрог, НИИ МВС ТРТУ, 2005 г.;

- НИР «Разработка и исследование методов синтеза виртуальных специализированных вычислителей в рамках фрейм-архитектуры СВПВС с многоуровневой организацией программирования архитектуры», № гос. per. 01.20.0301382, инв. №0220.0 601018, Таганрог, НИИ МВС ТРТУ, 2005 г.

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

На международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», 2003 г., 2005 г., Геленджик; на Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», 2004 г., 2006 г., Кацивелли; на Международной научной школе «Высокопроизводительные вычислительные системы», 2004 г., 2005 г, 2006 г.; на ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН, 2005г., 2006г. 2007г., Ростов-на-Дону; па IV республиканской научно-практической конференции «Дагинформ-2005», 2005г., Махачкала; на международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы», 2007г., Геленджик.

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

1) Шматок А.В., Каляев З.В., Структурно-функциональный и структурно-декларативный методы разработки компонентов масштабируемых параллельных программ. Тематический выпуск «Интеллектуальные и многопроцессорные системы». Известия ТРТУ. - Таганрог: Изд-во ТРТУ, 2004. -С. 64-70.

2) Каляев З.В., Коваленко А.Г., Многозадачная распределенная операционная система многопроцессорной вычислительной системы с программируемой архитектурой. Известия ТРТУ. - Таганрог: Изд-во ТРТУ, 2006.-С. 179.

3) Левин И.И., Шматок A.B., Каляев З.В., Средства разработки параллельных программ для многопроцессорных вычислительных систем с программируемой архитектурой. Искусственный интеллект. Донецк (Украина): изд-во ДонГИИИ "Наука i освгга", №3, 2003. - С. 147-149.

4) Шматок A.B., Каляев З.В., Декларативный и функциональный методы разработки компонентов масштабируемых параллельных программ. Материалы международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», 20-25 сентября 2004 г. -Таганрог: Изд-во ТРТУ, 2004. - Т 1. - С. 227-229.

5) Каляев З.В. Процедура масштабирования задачи сложения чисел для МВС ПА. Материалы первой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН. - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2005. - С. 231-232.

6) Каляев З.В. Процедура масштабирования операции умножения матриц. Материалы Международной научной молодежной школы «Высокопроизводительные вычислительные системы», Таганрог: Изд-во ТРТУ, 2005. С.176-178.

7) Каляев З.В. Масштабирование операции умножения матриц. Материалы IV республиканской научно-практической конференции «Дагинформ-2005». -Махачкала: ДНЦ РАН, 2006. - С. 190-192.

8) Каляев З.В. Многозадачная распределенная операционная система. Искусственный интеллект. - Донецк: Наука i осв1та, 2006. - №3. - С. 144-147.

9) Каляев З.В. Структура многозадачной распределенной операционной системы. Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы». - Таганрог: Изд-во ТРТУ, 2006. - Т. 2. - С. 102-103.

10) Каляев З.В. Компоненты многозадачной операционной системы для реконфигурируемой вычислительной системы. Материалы Третьей ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. -Ростов-на-Дону: Изд-во ЮНЦ РАН, 2007. - С. 140-141.

11) Каляев З.В. Система автоматического масштабирования параллельных программ для реконфигурируемых вычислительных систем. Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы - 2007». - Таганрог: Изд-во ТТИ ЮФУ, 2007. - Т. 1. - С. 285-289.

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

3.6. Выводы

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

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

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

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

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

161

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

Основные научные результаты диссертации опубликованы в работах [73, 78-83].

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

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

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

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

2. Воеводин В.В., Воеводин Вл.В. Параллельное программирование СПб. Изд-во «БХВ-Петербург», 2002 г.

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

4. Каляев А.В. Многопроцессорные однородные вычислительные структуры // Радиоэлектроника. -М., 1978. № 12. - С. 5-17.5. http://www.openmp.org.6. http://www.humanfactor.com/pthreads/pthreadlinks.html

5. Амамия М., Танака 10., Архитектура ЭВМ и искусственный интеллект: Пер. с японского. М.: Мир, 1993. - 400 с.8. http://www.beowulf.org.9. http://clusters.top500.org

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

7. Group W, Lusk Е, Skjellum A. Using MPI. Portable Parallel Programming with the Message-Passing Interface. MIT Press, 1994.

8. Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0. http://www-unix.mcs.anl.gov/mpi/.

9. Message-Passing Interface Forum, MPI-2: Extension to the Message-Passing Interface, 1997. http://www-unix.mcs.anl.gov/mpi/.

10. Foster I. Designing and Building Parallel Programs. Addison Wesley, 1994. http://www-unix.mcs.anl.gov/dbpp/text/nodel.html.

11. Корнеев В.В. Вычислительные системы. Издательство «Гелиос АРВ» 2004г.

12. Лав Р. Разработка ядра Linux Изд-во Вильяме, 2006 г.

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

14. Олифер В.Г., ОлиферН.А. Компьютерные сети, принципы, технологии, протоколы. СПб.: Питер, 2001. - 672 с.19. http://www.myri.com.20. www.infinibandta.org/21. www.linux.org/22. http://www.freebsd.org/

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

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

17. Microsoft Windows Driver Development Kit www.microsoft.com/whdc/devtools/ddk/default.mspx.

18. Грушвицкий Р.И., Мурсаев A. X., Угрюмов E. П. Проектирование систем на микросхемах программируемой логики. СПб.: БХВ-Петербург, 2002. - 608 с.

19. Соловьев В.В. Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия-Телеком, 2001. - 636 с.

20. ГОСТ Р 50754-95. Язык описания аппаратуры цифровых систем VHDL. Описание языка.

21. Суворова Е.А., Шейнин Ю.Е. Язык VHDL для проектирования систем на СБИС: Учебное пособие. / ГУАП, СПб., 2001. 212 с.

22. IEEE Std 1076-1993 // IEEE Standart VHDL Language Reference Manual. IEEE New York, USA, 1994. 632 p.31. www.xilinx.com.

23. Кузелин M. Основные семейства ПЛИС фирмы Xilinx // Электроника: наука, технология, бизнес. №5, 2004. http://www.electronics.ru/pdf/52004/16.pdf.

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

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

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

27. Вииевская Л.И., Дмитрепко U.M., Левин И.И., Логвинов С.А. Элементная база для построения высокопроизводительных систем // Труды международной конференции «Интеллектуальные многопроцессорные системы (ИМС'99)». Таганрог: Изд-во ТРТУ, 1999.-С. 93-97.

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

29. Каляев A.B., Левин И.И. Многопроцессорная система со структурно-процедурной организацией вычислений // Сборник научных трудов «Научная секция МИФИ-2001». М.: МИФИ, 2001. - Т. 2. - С. 206-207.

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

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

32. Левин И.И., Пономарев И.М. Методика организации высокоэффективных параллельных вычислений в многопроцессорных системах // Сборник тезисов Международной конференции «Искусственный интеллект 2000», Кацивели. - С. 142-144.

33. Kalyaev A.V. The Programming of Virtual Problem-Oriented Parallel Supercomputers in the Structure of Universal Supercomputers with Massive Parallelism. // High-Performance Computing. San Diego, California, USA,1999.-Pp.249-255.

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

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

36. Комолов Д.А., Мяльк Р.А., Зобепко А.А. и др. Системы автоматизированного проектирования фирмы Altera Max+Plus II и Quartus II: Краткое описание и самоучитель. М.: РадиоСофт, 2002. -352 с.

37. Стешенко В.Б. ПЛИС фирмы Altera: элементная база, система проектирования и языки описания аппаратуры. М.: Издательский дом «Додэка-ХХ1», 2002. - 576 с.

38. Суворова Е. А., Шейнин 10. Е. Язык VHDL для проектирования систем па СБИС: Учебное пособие. / ГУАП, СПб., 2001.-212 с.

39. Андрианов А.Н., Бугеря А.Б., Ефимкии К.Н., Задыхайло И.Б. Норма. Описание языка. Рабочий стандарт. Препринт ИПМ им. М.В.Келдыша РАН, 1995.-№ 120.- 50 с.

40. Проект ИПС РАН. Т-СИСтема. http://paraIIel.ru/paraIlel/russia/map/data/project 15.html

41. Булко И.М., Дорожко II.H.,. Дудко Л.И и др. Система виртуальных машин для ЕС ЭВМ: Справочник. М.: Финансы и статистика, 1985. -360 с.

42. IA-32 Intel Architecture Software Developer's Manual http://www.intel.com/products/processor/manuals/index.htm.

43. Шерр А. Анализ вычислительных систем с разделением времени М.: Изд-во «Мир», 1970 г.

44. Рихтер Дж. Windows для профессионалов. Изд-во"Питер", 2001.752 С.60. www.microsoft.com/rus/windows/default.mspx61. www.microsoft.com/windowsserver2003/ccs/default.aspx62. www.research.ibm.com/bluegene/

45. Ежеквартальный журнал # 1 Проспект. Ядра и потоки - новая парадигма.64. www.ru.sun.com/products/solaris/

46. Pountain D. High-powered Helios // PC World. 1988. - V. 11 № 7. - P. 162-165.

47. Марчук Г.И., Воеводин B.B., Вычислительные процессы и системы. Вып. 7. М.: Наука. Гл. ред. Физ.-мат. Лит., 1990. - 352 с.67. www.rosta.ru68. www.nallatech.com69. http://www.starbridgesystems.com70. www.fhpca.org

48. Hartenstein R. W., Hirschbiel A. G., Weber M. Xputers: An open family of non-von neumann architectures. Universität Kaiserslautern, Bau 12, Postfach 3049, D-675, Kaiserslautern, Germany.

49. Xputer Page //http://xputers.informatik.uni-kl.de/xputer/indexxputer.html

50. Сластен Л.М. Алгоритм отображения графа задачи в структуру многопроцессорной системы // Труды 9-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов "Микроэлектроника и информатика 2002". - М.: Изд-во МИЭТ, 2002.

51. Гудков В.А. Дордопуло А.И. Метод лексического и синтаксического анализа для языка высокого уровня COLAMO. Материалы научной молодежной школы «Высокопроизводительные вычислительные системы ВПВС-2005». Таганрог: Изд-во ТРТУ, 2005. - С. 174-176.

52. Каляев З.В. Многозадачная распределенная операционная система. Искусственный интеллект. Донецк: Наука i осв1та, 2006. - №3. - С. 144-147.

53. Каляев З.В. Гулеиок A.A. Процедура масштабирования операции умножения матриц. Труды Второй научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2006.-С. 133-134.

54. Каляев З.В. Коваленко А.Г. Многозадачная распределенная операционная система многопроцессорной вычислительной системы с программируемой архитектурой. Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2006. - С. 179.

55. Каляев З.В. Компоненты многозадачной операционной системы для реконфигурируемой вычислительной системы. Материалы Третьей ежегод-ной научной конференции студентов и аспирантов базо-вых кафедр ЮНЦ РАН. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2007. - С. HO-HI.

56. Гук Михил. Аппаратные интерфейсы ПК. Энциклопедия. СПб.: Издательский дом "Питер", 2002.

57. Катцан Г. Операционные системы. Москва: Изд-во «Мир», 1976 г, 470 с.

58. Цикритзис Д., Бернстайн Ф. Операционные системы: Пер. с англ. -Мир, 1977.-336 с.

59. Кейслер С. Проектирование операционных систем для малых ЭВМ: Пер. с англ. М.: Мир, 1986. - 680 с.

60. Семерников Е.А., Доронченко 10.И. Конвейерный макропроцессор цифровой обработки сигналов со структурно-процедурной организацией вычислений. Вестник компьютерных и информационных технологий. Москва: Машиностроение, 2005. -№8. - С. 49-55.

61. Ивенс Д.- Систем параллельной обработки. М.: Издательство «Мир» 1985.

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

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

64. Коваль Г.И., Коротун Т.М., Лаврищева Е.М. Программирование в системе виртуальных машин. М.: Финансы и статистика, 1990. 256 с.

65. Булко И.М., Дороженко U.M., Дудкин Л.И., Котов М.П., Марук З.А., Церлюкевич В.И. Система виртуальных машин для ЕС ЭВМ: Справочник. М.: Финансы и статистика, 1985. - 360 с.

66. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999.-320 с.96. http://parallel.ru97. http://www. cray. com/products/system s.98. www.mentor.com/products/esl/ highlevelsynthesis/catapultsynthesis/