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

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

СЛАСТЕН Любовь Михайловна

I

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

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

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

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

Таганрог-2005

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ: член-корреспондент РАН,

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

ОФИЦИАЛЬНЫЕ доктор технических наук, профессор

ОППОНЕНТЫ: Лебедев Борис Константинович

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

кандидат технических наук, доцент Букатов Александр Алексеевич

Государственное научное учреждение «Научно-исследовательский институт «Специализированные вычислительные устройства защиты и автоматика»» Минобрнаукн России

Защита состоится "16" декабря 2005 г. в 14 на заседании диссертационного совета Д 212.259.0S в Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, ул. Чехова, 2, корп. И, комн. 347.

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

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

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

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

22.ÖZY46

M9ol

з

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

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

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

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

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

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

В связи с этим необходимо создание новых методов и средств, которые обеспечат автоматизированное отображение взаимосвязанных структурно-реализуемых подграфов задачи на архитектуру МВС, а также позволят реализовать созданную crJyigj^i^lWUJJölWUiviu щммрамму на различных конфигурациях МВС СПРВ с ограниченной коммутацис^|||Щ(ж|^™ЙЛ' Г

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

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

- исследованы коммутационные системы МВС и принципы отображения параллельных алгоритмов на архитектуру системы;

- разработаны принципы отображения информационного графа задачи на архитектуру МВС СПРВ с ограниченной коммутационной структурой;

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

- разработаны методы распределения секций памяти при отображении взаимосвязанных структурно-реализуемых подграфов информационного графа на МВС СПРВ;

- разработан алгоритм отображения взаимосвязанных структурно-реализуемых подграфов на архитектуру МВС СПРВ с различными типами коммутационных структур;

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

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

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

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

- новые методы и алгоритмы автоматического отображения на архитектуру МВС СПРВ множества взаимосвязанных структурно-реализуемых подграфов информационного графа;

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

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

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

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

Применение разработанных методов обеспечивает возможность минимизации аппаратных затрат на создание коммутационных структур на МВС СПРВ в процессе их синтеза.

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

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

ственного радиотехнического университета (НИИ МВС ТРТУ). Предложенные методы внедрены в НИИ МВС ТРТУ, г.Таганрог, Южном научном центре Российской академии наук (ЮНЦ РАН), г. Ростов-на-Дону, Московском институте электронной техники, г. Москва, в/ч 26165, г.Москва

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

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

- на всероссийских научных конференциях "Методы и средства обработки информации", г. Москва, 2003, 2005 гг.;

- на 9-й всероссийской межвузовской научно-технической конференции студентов и аспирантов "Микроэлектроника и информатика - 2002", г. Москва;

- на международных научно-технических конференциях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы", пос. Дивноморское, 2003, 2005 гг., пос. Кацивели, 2002,2004 гг.;

- на республиканских научно-практических конференциях "Информационные и телекоммуникационные системы: сетевые технологии", г. Махачкала, 2003,2005 гг.;

- на научной международной школе "Высокопроизводительные вычислительные системы (ВПВС) - 2004", пос. Кацивели, Украина, 2004;

- на всероссийской научно-технической конференции "Параллельные вычисления в задачах математической физики", г. Ростов-на-Дону, 2004.

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 16 печатных работ, из них: 5 статей, 10 тезисов и материалов докладов на российских и международных научно-технических конференциях, 1 свидетельство о регистрации программ для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения, списка использованных источников из 94 наименований и приложений. Диссертация содержит 214 страниц печатного текста, из которых 165 страниц основного текста, 49 страниц приложений и 72 рисунка.

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

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

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

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

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

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

В общем случае структурно-процедурный алгоритм описывается кортежем СйЯ, каждый элемент которого с„ ¡=1, ...,ЫС, содержит информационный граф кадра. Здесь М7- количество кадров параллельного алгоритма. В информационном графе кадра входные и выходные информационные вершины соответствуют каналам памяти МВС, внутренние (операционные) вершины - элементарным процессорам, а дуги - информационным зависимостям.

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

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

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

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

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

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

Начмо

X

Размещение информационных

вершин для всех кадров *

Упорядочивание кадров по степени сложности и формирование кортежа обрабатываемых ууул»

Счетчик кадров I =

ЗЕ

| Выбор /-го обрабатываемого кадра |

Выбор из графа каора (вершины х дяя размещении

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

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

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

-этапа размещения информационных вершин;

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

Исходными данными для реализации задачи отображения структурно-процедурных алгоритмов на архитектуру МВС СПРВ являются описание архитектуры и описание кадров. Разработанные принципы отображения и структурная схема алгоритма позволяют реализовал» процедуру отображения для МВС с различными типами архитектуры. Для отображения информационного графа задачи на конкретную архитектуру разработаны методы и средства описания архитектуры МВС СПРВ.

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

Элементом архитектуры МВС СПРВ является функциональная секция. Для каждой секции МВС задан тип секции Л, множество входов/выходов /'Л', множество элементов секции ЕЬ, а также правило формирования задержек а? при транзитной передаче данных через секцию.

Трассировка информационных каналов, соответствующих связям вершины х с размещенными _вершинами_

Псрсртмхикнис ранее размещенной вершины яг т - иг

Рис. 1

Параметр «тип секции» steST, где ST={MEM, MAP, SIV, ISWj. Здесь MEM - макропамять, MAP - макропроцессор, SW- коммутатор внутримодульный, 1SW- коммутатор межмодульный.

Входы/выходы секции описываются с помощью множества PN, каждый элемент которого представлен в виде списка параметров, характеризующих вход/выход секции: р=<п, pt, b>, где п -имя входа/выхода; pt - тип входа/выхода; b - степень занятости входа/выхода, означающая количество трасс, которые занимают вход/выход п.

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

В свою очередь, данные о структуре МВС СПРВ представляют собой множество вершин графа описания архитектуры А, элементы которого представляются в виде: я=<д st, PN, EL, d>, где n - имя секции; st - тип секции; PN - имя множества входов/выходов секции; EL - имя множества элементов секции; d - правило формирования задержек при транзитной передаче данных через секцию. На основе иерархического описания МВС формируется граф архитектуры, который используется при отображении структурных фрагментов структурно-процедурного алгоритма на архитектуру МВС. Аналогичным образом формируется описание каждого кадра.

Предлагается кадр структурно-процедурного алгоритма представлять в виде множества вершин С, элементы которого представляются в виде: с=<п, t,f NS, S>, где п - имя вершины; t -тип вершины;/- имя операции; NS- количество вершин-предшественников; S- множество вершин-предшественников. Входные и выходные информационные вершины могут быть кортежными вершинами, для которых существует структура данных, содержащая размер кортежа входных (выходных) вершин.

Имя операции feF, где F- множество имен операций доя операционных вершин графа кадра

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

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

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

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

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

-преобразование кадра из списка предшественников вершин в список предшественников/последователей;

- размещение вершин информационного графа кадра в секции МВС СПРВ и трассировка информационных каналов;

- формирование внутренних соединений в секциях МВС СПРВ.

ЯКФ представляет собой кораеж множеств вершин L~---<Ln, L,.....Lnl>, где L, - множество вершин /-го яруса; NL - количество основных ярусов. Кортеж ярусов L обрабатывается последовательно с двух сторон, что обеспечивает при размещении вершин относительно равномерное заполнение секций макропроцессора операционными вершинами графа обрабатываемого кадра.

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

разместить вершину, и секцией, в которой содержится ранее размешенная вершина, связанная с размещаемой вершиной информационной дугой.

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

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

В диссертации обоснована необходимость сохранения последовательности размещения вершин и последовательности обработки кадров при откатах назад. Для хранения размещенных вершин используется кортеж 2, каждый элемент которого г„ »=7,.. ,N2, является именем размещенной вершины графа кадра. Здесь N2 - общее количество размещаемых вершин графов кадра задачи. Для доступа к элементам кортежа 2 вводятся два указателя: & -указатель размещаемых вершин и сг- указатель размещенных вершин.

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

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

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

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

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

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

/И ... * ^ «Г ¡>^МАРО / \\ МАР4

—- \\ V

--¡MPS

\\V МАР1 / ——i =Y

Рис.2

Рис.3

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

Макровершины образуют множество М, элементы которого представляются в виде: т=<п, cdr, s, рг, с, МТ, ins, outs>, где п - имя макровершины; 5 - имя секции МВС, в которой размещена макровершина п; рг - тип макровершины (первичная - PRIMARY или вторичная -ORDINARY)-, с - параметр, определяющий, является макровершина закрытой или открытой (OPEN - открытая или CLOSE - закрытая); МТ - множество вершин графа кадра, принадлежащих макровершине п\ ins - количество входов для формирования связей макровершины п; outs - количество выходов для формирования связей макровершины п. Здесь cdr - номер обрабатываемого кадра.

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

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

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

и

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

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

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

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

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

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

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

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

При размещении информационной вершины учитывается, что соответствующие ей данные должны быть сохранены для всех кадров, графам которых принадлежит данная вершина. В связи с этим определяются номера кадров, в которых область памяти в канале, выделенная для данных вершины, не может быть использована. Для этого из номеров кадров, графам которых принадлежит вершина, выбираются минимальный и максимальный элементы: MinCN и MaxCN соответственно. Для каждого кадра г, где i=MinCN,..., MaxCN, данные в канале, в который размещена информационная вершина, сохраняются. На рисунке 4 представлена последовательность кадров задачи, указаны номера кадров, которым принадлежат вершины А и В, и номера кадров, для которых вершины А и В должны сохранять свои значения.

МшСЫв___iL. MaxCNB

-iMi/imi -iMi /Uii-^ra M 31 • IMT. Uli Ui^qj

I II III мьсй; t

а) 6)

Рис.4

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

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

Канал el секции макропамяти s, в который предполагается разместить информационную вершину х, должен иметь объем свободной памяти, достаточный для размещения данных, соответствующих размещаемой вершине. Для изменения объема свободной памяти в канале el секции s по имени вершины х определяется объем памяти v, требуемый для размещения данных, а также минимальный номер MinCN и максимальный номер MaxCN кадров, при реализации которых данные для вершины х должны сохраняться. Для каждого кадра i=MirtCN,...,MaxCN объем свободной памяти в канапе el секции s декрементируется на величину V.

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

В главе разработана процедура удаления информационной вершины из канала секции макропамяти. При удалении вершины из секции макропамяти освобождается канал, в котором размещена вершина. Для удаляемой вершины определяется объем памяти v, требуемый для размещения соответствующих ей данных. Определяются минимальный MinCN и максимальный MaxCN номера кадров, для которых данные, соответствующие удаляемой вершине, должны сохранять свои значения. Для каждого кадра i=MinCN,...,MaxCN объем свободной памяти в канале инкрементируется на величину v. Кроме того, необходимо проверить, не является ли секция пустой после удаления вершины. Если из секции макропамяти удаляется последняя вершина, тип операции для секции должен быть установлен в значение «пусто».

Рисунок 56 иллюстрирует процедуру удаления информационной вершины из канала секции макропамяти.

Мах -

el

-Y О

Мах

el

Мах

Мах

Мах

- 0 __

■ -

. _ _

Мах

—

EMPTY READ READ READ READ EMPTY

a) 6)

Рис.5

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

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

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

В главе разработана процедура размещения информационных и операционных вершин информационных графов многокадровой задачи в секциях макропамяти и макропроцессора базового модуля и трассировки информационных каналов. По аналогии с методом реализации однокадровой задачи на МВС СПРВ с ортогональной коммутационной структурой, рассмотренным в главе 2, для каждой размещаемой вершины х формируется множество размещенных предшественников/последователей Qx. Если множество Qx - пустое, то вершина х может быть размещена в любую секцию из множества MAP\RX, если вершина - операционная, или в любую секцию из множества MM\RX, если вершина - информационная. В случае, когда множество Qx - не пустое, вершина х может быть размещена в секции, не являющейся запрещенной для вершины х, а также если суммарная длина связей между данной секцией и секциями, в которых размещены вершины из множества Qx, минимальна. Поиск секции для размещения производится аналогично тому, как это делается при реализации однокадровой задачи на МВС СПРВ с ортогональной коммутационной структурой.

Для метода реализации многокадровой задачи предложено расширить описание кортежа размещенных вершин Z В общем случае, когда структурно-процедурный алгоритм состоит из множества взаимосвязанных структурно-реализуемых подграфов, элемент г„ i-l,...,NZ, представляет собой пару <х, п>, где х - имя размещенной вершины, а п - номер

кадра, при обработке которого вершина х была размещена. Количество элементов N2 кортежа равно сумме количеств размещаемых вершин всех кадров алгоритма.

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

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

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

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

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

- тип операции секции - «чтение» или «пусто», а вершина - входная информационная;

• тип операции секции - «запись» или «пусто», а вершина - выходная информационная;

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

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

В случае удачной трассировки пара <х, ссЬ-> добавляется в кортеж размещенных вершин 2. Указатели ¿г и сг инкрементируются. Вершина х размещается в одном из свободных элементов секции 5. Если вершина * - информационная, то в канале е1 необходимо сократить объем свободной памяти на величину, соответствующую объему данных вершины. Когда трассировка неудачна, последовательность действий полностью аналогична действиям метода реализации графа кадра на МВС с произвольной коммутационной структурой, рассмотренного в главе 2.

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

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

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

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

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

Рис. 6 Рис. 7

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

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

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

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

и =

и,г

где

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

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

Параметр вычисляется по формуле ию = Чт+ир> где 1!т - количество секций макропамяти для размещения информационных вершин, С1р - количество секций макропроцессора для раз-

т

мещения операционных вершин. Параметр и„ вычисляется по формуле иш=—, где Тт - количест-

Ет

во информационных вершин графа, Ет - количество каналов в секции макропамяти. Параметр Ир

вычисляется по формуле и, = , где Тр - количество операционных вершин графа, Ер -Е„

количество

элементарных процессоров в секции макропроцессора.

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

На рисунках 8,9 кривая 1 иллюстрирует зависимости плотности размещения II и времени отображения I от количества вершин Г информационного графа в случае использования ортогональной коммутационной структуры при условии, что информационные вершины графа предварительно размещены

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

Кривая 3 иллюстрирует зависимости плотности размещения II и времени отображения ? от количества вершин Г информационного графа в случае использования произвольной коммутационной структуры при условии, что информационные вершины графа не являются размещенными.

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

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

Рис. 8

1,с

! . 1 1 ' '1 1 1

1 Л 1 1 |

1 1 2 1 ■ К 1 !

! 1 / ' \ ^^

- — ; т -1-1-1-г—

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

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

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

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

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

- разработаны новые методы и алгоритмы отображения на архитектуру МВС СПРВ множества взаимосвязанных структурно-реализуемых подграфов информационного графа;

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

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

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

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

2) Левин И.И., Сластен Л.М. Реализация информационных графов в архитектуре многопроцессорных систем // Материалы Межд. науч.-техн. конф. «СуперЭВМ и многопроцессорные вычислительные системы - 2002». - Таганрог: Изд-во ТРТУ, 2002. - С. 98-102.

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

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

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

6) Левин И.И., Сластен JI.M. Программа отображения информационного графа задачи на многопроцессорную вычислительную систему // Свидетельство № 2004612038, заявка № 2004611446, дата поступления 6.07.2004, зарегистр. 6.09.2004.

7) Левин И.И., Сластен Л.М. Алгоритм отображения графа на структуру системы // Материалы 3-й Респуб. науч.-практ. конф. «Информационные и телекоммуникационные системы. Сетевые технологии (Дагинформ - 2003)». - Махачкала- Изд-во ДНЦ РАН, 2004. - С. 24-26.

8) Сластен Л.М. Процедура реализации информационного графа задачи на процессорах многопроцессорной вычислительной системы // Материалы Межд. науч. конф. «Искусственный интеллект. Интеллектуальные и многопроцессорные системы - 2004». - Таганрог: Изд-во ТРТУ, 2004. - Т.1. - С. 223-227.

9) Сластен Л.М. Процедура отображения графа решения задачи на процессоры многопроцессорной вычислительной системы // Искусственный интеллект. - Донецк: Наука i ocbi-та, 2004. - Т.4. - С. 59-67.

10) Сластен Л.М. Алгоритм отображения информационного графа задачи на архитектуру многопроцессорной вычислительной системы с произвольной коммутационной системой // Материалы науч. межд. школы '(Высокопроизводительные вычислительные системы (ВПВС-2004)». - Таганрог: Изд-во ТРТУ, 2004. - С. 147-151.

11) Сластен Л.М. Отображение информационного графа задачи на архитектуру многопроцессорной вычислительной системы для решения задач математической физики II Всерос. науч.-техн. конф. «Параллельные вычисления в задачах математической физики». - Ростов-на-Дону, 2004. - С. 50-58.

12) Сластен Л.М. Анализ эффективности алгоритма трассировки при реализации многокадровой задачи на многопроцессорной вычислительной системе // Материалы Межд. науч. конф. «Искусственный интеллект. Интеллектуальные и многопроцессорные системы -2005». - Таганрог: Изд-во ТРТУ, 2005. - Т.1. - С. 200-204.

13) Сластен Л.М. Алгоритм многокадровой трассировки многопроцессорной вычислительной системы // Труды 2-й Всероссийской научной конференции «Методы и средства обработки информации». - М.: Изд. отдел ф-та вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. - С. 490-495.

14) Сластен Л.М., Коваленко В.Б. Процедура визуализации коммутационных соединений в многопроцессорной вычислительной системе // Материалы 1-й ежегодной йауч. конф. студентов и аспирантов базовых кафедр ЮНЦ РАН, 2005. - Ростов-на-Дону: Изд-во ЮНЦ РАН,2005.-С. 244-245.

15) Сластен Л.М. Анализ эффективности алгоритма трассировки многокадровой задачи для многопроцессорной вычислительной системы со структурно-процедурной организацией вычислений // Искусственный интеллект. - Донецк: Наука i оснпа, 2005. - Т.4. - С. 280-283.

ЛР № 020565 от 23 июня 1997 г Подписано к печати 2005 г

Формат 60x84 "|6 Бумага офсетная Печать офсетная Усл. пл -1,0 Уч -издл -0,9 Заказ № 271 Тираж 100 экз

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

¿23 8 05

РЫБ Русский фонд

2006-4

27901

4

ВВЕДЕНИЕ.

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

1.1 Архитектура вычислительных систем и методы распараллеливания последовательных алгоритмов.

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

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

1.4 Отображение параллельных алгоритмов с использованием ПЛИС-технологии.

1.5 Принципы отображения параллельных алгоритмов на архитектуру системы.

1.5.1 Описание архитектуры МВС СПРВ.

1.5.2 Описание структурно-реализуемого фрагмента алгоритма.

1.6 Выводы.

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

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

2.2.1 Методы и алгоритмы размещения вершин.

2.2.2 Графовый метод трассировки информационных каналов.

2.2.3 Схемный метод трассировки информационных каналов.

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

2.3.1 Метод группировки размещаемых вершин информационного графа кадра.

2.3.2 Методы выбора размещаемой вершины информационного графа кадра.

2.3.3 Обобщенный алгоритм отображения информационного графа кадра на архитектуру МВС.

2.3.4 Алгоритм трассировки информационных каналов между секциями

МВС с произвольной коммутационной структурой.;.

2.4 Выводы.

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

3.1 Методы размещения информационных вершин.

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

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

3.3.1 Обобщенные методы группировки и выбора размещаемых вершин информационного графа кадра.

3.3.2 Обобщенный метод и алгоритм отображения многокадровой задачи на архитектуру МВС СПРВ.

3.4 Выводы.

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

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

4.2 Примеры задач, реализованных на МВС с различными типами коммутационных структур.

4.2.1 Задача быстрого преобразования Фурье.

4.2.2 Задача решения уравнения Пуассона.

4.2.3 Многокадровая задача.

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

4.4 Выводы.

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

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

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

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

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

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

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

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

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

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

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

- разработаны принципы отображения информационного графа задачи на архитектуру МВС СПРВ с ограниченной коммутационной структурой;

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

- разработаны методы распределения секций памяти при отображении взаимосвязанных структурно-реализуемых подграфов информационного графа на МВС СПРВ;

- разработан алгоритм отображения взаимосвязанных структурно-реализуемых подграфов на архитектуру МВС СПРВ с различными типами коммутационных структур;

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

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

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

- новые методы и алгоритмы автоматического отображения на архитектуру МВС СПРВ множества взаимосвязанных структурно-реализуемых подграфов информационного графа;

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

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

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

Применение разработанных методов обеспечивает возможность минимизации аппаратных затрат на создание коммутационных структур на МВС СПРВ в процессе их синтеза.

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

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

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

- «Исследование эффективности МВС со структурно-процедурной организацией вычислений», № гос. per. 01200001267, инв. № 02.20.0300068, Таганрог, НИИ МВС ТРТУ, шифр "Такт";

- «Разработка методов и аппаратно-программных средств отказоустойчивого функционирования универсальных мультимикропроцессорных систем с массовым параллелизмом и программируемой архитектурой», № гос. per. 01.2.00104214, инв. № 02.200.206720, Таганрог, НИИ МВС ТРТУ, шифр "Регистр-2";

- «Исследование эффективности МВС со структурно-процедурной организацией вычислений», № гос. per. 01.20.0001267 инв. № 02.20.0300068, Таганрог, НИИ МВС ТРТУ;

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

- «Разработка и исследование методов реализации задачи в самонастраиваемой под структуру задачи вычислительной системе», № гос. per. 01.20.0301381, инв. № 02.2.00401921, Таганрог, НИИ МВС ТРТУ, шифр "Скатерть";

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

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

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

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

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

-на всероссийских научных конференциях "Методы и средства обработки информации", г. Москва, 2003,2005 гг.;

-на 9-й всероссийской межвузовской научно-технической конференции студентов и аспирантов "Микроэлектроника и информатика - 2002", г. Москва;

-на международных научно-технических конференциях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы", пос. Дивноморское, 2003,2005 гг., пос. Кацивели, 2002,2004 гг.;

- на республиканских научно-практических конференциях "Информационные и телекоммуникационные системы: сетевые технологии", г. Махачкала, 2003,2005 гг.;

- на научной международной школе "Высокопроизводительные вычислительные системы (ВПВС) - 2004", п. Кацивели, Украина, 2004;

- на всероссийской научно-технической конференции "Параллельные вычисления в задачах математической физики", г. Ростов-на-Дону, 2004.

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

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

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

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

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

4) Сластен Л.М. Процедура отображения графа решения задачи на процессоры многопроцессорной вычислительной системы // Искусственный интеллект. - Донецк: Наука i освгга, 2004. - Т.4. - С. 59-67.

5) Сластен JI.M. Отображение информационного графа задачи на архитектуру многопроцессорной вычислительной системы для решения задач математической физики // Всероссийская научно-техническая конференция "Параллельные вычисления в задачах математической физики". - Ростов-на-Дону, 2004. - С. 50-58.

6) Сластен JI.M. Алгоритм многокадровой трассировки многопроцессорной вычислительной системы // Труды 2-й Всероссийской научной конференции "Методы и средства обработки информации". -М.: Издательский отдел ф-та вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. - С. 490-495.

7) Сластен Л.М. Анализ эффективности алгоритма трассировки многокадровой задачи для многопроцессорной вычислительной системы со структурно-процедурной организацией вычислений // Искусственный интеллект. - Донецк: Наука i освгга, 2005. — Т.4. - С. 280-283.

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

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

4.4 Выводы

1) Для отображения структурно-процедурных алгоритмов на архитектуру МВС СПРВ было создано программное средство на основе:

- метода автоматического отображения множества взаимосвязанных структурно-реализуемых подграфов информационного графа структурно-процедурного алгоритма на МВС СПРВ для различных типов ограниченных коммутационных структур;

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

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

3) Использование созданной программы позволяет сократить время разработки структурно-процедурных программ 2-5 раз.

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

Заключение

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

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

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

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

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

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

5) Для отображения структурно-процедурных алгоритмов на архитектуру МВС СПРВ на основе разработанных методов и алгоритмов создана программа, использование которой:

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

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

- сокращает время разработки параллельных программ в 2-5 раз.

1. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н.Новгород: Изд-во ННГУ, 2001.

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

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

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

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

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

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

8. Горелик A.M. Средства поддержки параллельности в языках программирования. Открытые системы, 2/10/1995. http://osp.aanet.ru/os/1995/02/source/34.htm

9. DVM-система. http://www.keldvsh.ru/dvm

10. Корнеев B.B. Параллельные вычислительные системы. M.: «Нолидж», 1999. - 320 с.

11. Lastovetsky A. mpC — a Multi-Paradigm Programming Language for Massively Parallel Computers, ACM SIGPLAN Notices, 31(2): 13-20, February 1996.

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

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

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

15. Рубин А.Г., Смирнов В.К., Тульский В.П. Пользовательский интерфейс для прикладных задач.http://www.keldysh.ru/papers/2000/source/prep2000 74.doc

16. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей.http://spb.parallel.ru/tech/articles/krukov-cldvm2002f.pdf

17. Сбитнев Ю. Практическое руководство по параллельным вычислениям, http://linux-cluster.org.ru/

18. Богданов А.В., Корхов В.В., Мареев В.В., Станкова Е.Н. Архитектуры и топологии многопроцессорных вычислительных систем. 2004. 176 с.24. http://cray.com

19. J. Haataja, V. Savolainen. Cray ТЗЕ User's Guide. Center of Scientific Computing, Finland, 1998.

20. Корхов B.B. Современные высокоскоростные коммуникационные технологии. Computational Scientific Alliance http://www.csa.ru

21. The Scalable Coherent Interface (SCI). http://www.dolphinics.com/coфorate/scitech.html

22. Борзенко А. Архитектура NUMA-Q. http://www.pcweek.ru/Y ear2001/N13/CP1251/CorporationSystems/chaptl .htm

23. Memory Channel Application Programming Interfaces. http://h30097.www3.hp.com/docs/cluster doc/cluster 15/ps mcapi/title.htm

24. Fast Ethernet http://www.lantronix.com/learning/net-tutor-fastetnt.html

25. Gigabit Ethernet Sites http://www.gigabit-ethernet.org

26. InfiniBand http://www.infinibandta.org

27. Myricom, Inc. http://www.myri.com

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

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

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

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

32. Беркс А., Голдстайн Г., Нейман Дж. Предварительное рассмотрение логической конструкции электронного вычислительного устройства // Кибернетический сборник. М.: Мир, 1964. - Вып. 9.

33. Майерс Г. Архитектура современных ЭВМ: в 2-х кн.: Пер. с англ. — М.: Мир, 1985.

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

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

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

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

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

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

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

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

42. Шмойлов В.И. Архитектура однородных вычислительных сред. — Львов: НТЦ «Интеграл», 1993. 289 с.

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

44. DeHon A. Reconfigurable Architectures for General-Purpose Computing, http://www.cs.caltech.edu/research/ic/transit/rcgp/rcgp.html

45. Wawrzynek J. and others. Stream Computations Organized for Reconfigurable Execution (SCORE): Introduction and Tutorial. http://brass.cs.berkeley.edu/documents/score tutorial.pdf

46. Callahan T.J., Wawrzynek J. Adapting Software Pipelining for Reconfigurable Computing, http://brass.cs.berkeley.edu/documents/cases2000.html

47. ПЛИС фирмы 'XILINX': описание структуры основных семейств. -М.: Издательский дом «Додэка XXI», 2001 г. 238 с.

48. Кузелин М.О., Кнышев Д.А., Зотов В.Ю. Современные семейства ПЛИС фирмы Xilinx. Справочное пособие. М.: Горячая линия - Телеком, 2004 г.-440 с.59. http://www.altera.com60. http://www.xilinx.com61. http://www.actel.com

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

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

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

52. Стешенко В.Б. ПЛИС фирмы Altera: проектирование устройств обработки сигналов. М., 2000.

53. Антонов А.П. Язык описания цифровых устройств AlteraHDL. М.,2001.67. http://www.starbridgesystems.com

54. Левин И.И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений. : Дис. на соискание ученой степени доктора техн. наук : 05.13.11, 05.13.15 / ТРТУ. — Таганрог, 2004. 363 с.

55. Drewes F., Hoffmann В., Plump D. Hierarchical Graph Transformation. // Journal of Computer and System Sciences 64, 249-283 (2002). http://www-users.cs.york.ac.uk/~det/Papers/icss.02.pdf

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

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

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

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

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

61. Сигорский В.П. Математический аппарат инженера. Киев: Техника, 1975. - 766 с.

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

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

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

65. Шрайнер П.А. Основы программирования на языке Пролог. 2005,176 с.

66. Готра З.Ю., Григорьев В.В., Смеркло Л.М., Эйдельнант. Сквозное автоматизированное проектирование микроэлектронной аппаратуры. М.: Радио и связь, 1989. - 280 с.

67. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь, 1987. 152 с.

68. Сорокопуд В.А. Автоматизированное конструирование микроэлектронных блоков с помощью малых ЭВМ. — М.: Радио и связь, 1988. 128 с.

69. Ахо А.В., Хопкрофт Дж. Э., Ульман Дж. Структуры данных и алгоритмы. Вильяме, 2001. - 384 с.

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

71. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М.: Мир, 1978. - 432 с.

72. Харари Ф. Теория графов. М.: Мир, 1973.

73. Сластен JI.M. Процедура отображения графа решения задачи на процессоры многопроцессорной вычислительной системы. //Искусственный интеллект. — Донецк (Украина): изд-во ДонГИИИ «Наука i oceiTa», 2004. — Т.4. С. 59-67.

74. Гольденберг JI.M. и др. Цифровая обработка сигналов: Учеб. Пособие для вузов / JI.M. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. 2-изд., перераб. и доп. - М.: Радио и связь, 1990. - 256 е.: ил.

75. Тихонов А.Н., Самарский А.А. Уравнения математической физики. М.: Наука. -1972. -735 с.