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

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

ИВАНОВ Андрей Игоревич

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

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

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

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

Таганрог - 2005

Работа выполнена в войсковой части 26165 (г. Москва).

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

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

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

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

кандидат технических наук, сне Дрожжин Владимир Васильевич

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

Федеральное государственное унитарное предприятие "Научно-исследовательский институт "КВАНТ"", г. Москва

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

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

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

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

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

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

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

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

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

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

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

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

Появление программируемых логических интегральных схем (ПЛИС) высокой сте-

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

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

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

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

1) проведен анализ методов и моделей одновременных вычислений;

2) разработаны методы оценки эффективности реализации параллельных и конвейерных вычислений;

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Материалы диссертации использованы при выполнении НИОКР "Фактор", "Начинка", "Радикал", "Прокол-Б1", выполняемыми ЗАО "Эврика" (г. Санкт-Петербург) и ОАО "СКБ Топаз" {г. Москва), а также при разработке специального программного обеспечения в войсковой части 26165 (г. Москва). Кроме того, созданные программные средства были использованы при разработке и отладке программно-технических средств перегрузочной машины ядерного реактора, выполняемых в рамках ОКР "Контроль", что подтверждается соответствующими актами внедрения.

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

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

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

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

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

- программные средства поддержки смешанных одновременных вычислений.

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

автором лично.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Иаодвые Генератор

алшшие аотока

Правам формировав ва

р. с 1

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис 3 показан пример информационного графа G, соответствующего алгоритму

for 1=1 ton to, begin Ii=Ai Bi+Ci Di, Ki=EiFi-GiHi, Ji=hKi, end,

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

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

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

Рис. 4.

Рис.3

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

Рис. 5.

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

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

Данное утверждение следует из того, что входные (выходные) вершины преобразуются в кортеж,

Для операции конвейеризации параллельного действия справедливо высказывание

(С,»С2)+(03»С,)=(6'|+0з)»(02+04).

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

(0,+02)»0з=(01+Сз) >>(С2+Сз)

Введена операция последовательного выполнения подграфов, которую мы будем обозначать символом -* . Данная операция является некоммутативной С]-» Сг ^Ог*

Для операций последовательного и параллельного выполнения справедлива взаимная симметрия

(<?!-» С^С,-» С4)=(6',+03Н (С72+С74).

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

где - время решения задачи на аппаратном ресурсе Q; /„

конвейерную структуру; 1К - время заполнения конвейера; /ц операнда через конвейер.

При реализации £ подграфов время вычисления будет составлять

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

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

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

Типовая схема конвейеризации может быть записана

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

Переход к другой схеме распараллеливания также приводит к потере эффективности.

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

Так как время настройки может на несколько порядков превосходить остальные временные составляющие, то такой вариант невозможно реализовать на ПЛИС

Если ресурса достаточно для покрытия подграфа 0„ то предпочтительнее конвейерная реализация вычислений, в противном случае эффективнее параллельная реализация

Схема параллельной конвейерной обработки имеет следующий вид

Время выполнения задачи

Д>>) = '„+'л +

'п

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

Условный оператор можно представить в следующем виде

¡Г а №еп Ье£ш Ьь Ь2, , Ь„, еп<1,

еке begin с>, с2, , с„„ епё,

- группа операторов, которые - группа операторов, которые выполняются,

где а - логическое выражение. выполняются, если а истинно, если а ложно

Такой оператор может быть естественным образом преобразован в конвейерную

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

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

где р'ь - вероятность выполнения 1-й еке-ветви, р'Т • вероятность выполнения ¡-й {Иеп-ветви, А' - объем дополнитечьных вычислений для 1-й ветви

/я-кратно итоженный условный оператор имеет 2т' прямых и 2т 1 альтернативных функций Номера функций имеют индекс ¡=1,2, , 2т 1 Индекс А: соответствует номеру яруса в пирамидальной структуре условного оператора, индекс у - номеру элемента в ярусе Если эффективность конвейерной реализации будет выше некоторого значения, то

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

Рис 6

Структура трехкратно вложенного условного оператора показана на рис 7 Аналогичные оценки получены и для рекурсивных выражений Если некоторый информационный граф О соддшиг множество изоморфных подграфов С|, Сг, , 0„, соединенных непосредственно друг с другом, то данное множество изоморфных подграфов можно реализовать конвейерно Если вычислительного ресурса системы достаточно для аппаратной реализации только одного подграфа, то формируется структура, в которой множество входных и выходных вершин подграфов С/2, , Оп заменяется кортежными вершинами, а дуги, инцидентные связям подграфов, заменяются обратными связями Пример подобного преобразования показан на рис 8 Операнды на вход конвейера должны подаваться тогда, когда готовы результаты по обратным связям, это сводит быстродействие конвейера к быстродействию вычислений рекурсивных выражений

Доказана теорема. Если имеется некоторый информационный граф О, состоящий из множества взаимосвязанных изоморфных подграфов

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

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

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

к=3 к-2 к~1

а) исходный граф, б) конвейеризированный граф Рис 8

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

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

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

Схематично структура объединенных параллельно-конвейерных вычислений представлена на рис 10 Здесь Г, обозначает устройство (контроллер) генерации данных, - приемное устройство, аналогичное генератору, но осуществляющее запись порченных результатов Латинскими буквами обозначены устройства (блоки), осуществляющие конвейерную обработку, греческими буквами обозначены устройства (блоки), реализующие процедурную обработку В общем случае блок процедурной обработки содержит множество процессоров

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

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

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

Рис.11.

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

Для проектирования конвейерных устройств на основе ПЛИС-технологии сформулированы два принципа:

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

2) использование связей с триггера на триггер в ПЛИС приводит к потере аппаратных ресурсов в виде логических элементов, пригодных для реализации вычислений.

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

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

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

Пользователь с помощью графического редактора создает конвейерный граф фрагмента вычислений. Скрин-шот графического редактора приведен на рис. 13.

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

Средства исполнения представлены ядром встраиваемой операционной системы. Его структурная схема приведена на рис 14. Здесь приняты следующие обозначения: К, - модуль конвейерной обработки, Г^ - процессор конвейера, М^ - модуль памяти, И, интерфейсный модуль. В модулях конвейерной обработки вычисления выполняются структурно, в то время как процессоры выполняют процедурные фрагменты вычислений. '

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

Графачсска!

редактор

. ^ КоамМераый граф

К!=п

Программа

сиятяксачсского _

КоррсктяыЯ коиаеИераы§ граф

2Е

Программа реиирмт«и

Ж

Сияхронмромяны* ._граф_„

21

Процедура модели роман

11

нентами ядра встраиваемой операционной системы.

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

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

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

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

которые поступают на блок вычисления функции.

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

производительность по сравнению с известными решениями.

МР1К1ГТЯЫ1 *" ппртпрвниы!

Коамртор УНОЬ

Оаяшн и УНПЬ фрагмгт иди!

Рис.

12

Рис 13.

Рис. 14.

Информационная структура генетического алгоритма включает в себя: подграф вычисления оптимизируемой функции подграф проверки гипотезы ПГ, который выбирает из N особей популяции и наиболее приспособленных особей, и подграф генерации новой популяции методами генетических алгоритмов ГГА Таким образом, информационный граф генетического алгоритма можно конвейеризировать аналогично

типовым рекуррентным выражениям. При сбалансированной нагрузке на реализацию ти-.^жл-^шшш-^»».»» повых блоков Г) ПГ, ГГА можно

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

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

Рассматриваемый информационный граф генетического алгоритма состоит из

изводится генерация нового поколения

подграфов создания популяции £

В свою очередь, граф представляет собой три подграфа

информационный граф вычисления

оптимизируемой функции для v-гo поколения; рУ - граф выбора элитных особей V -ГО поколения; г" - граф синтеза нового V +1 -ГО поколения из элитных особей поколения.

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

Наиболее удачной реализацией генетического алгоритма будет построение макроконвейера, в котором скорость вычисления значений оптимизируемой функции будет равна скорости генерации нового поколения. Общий ресурс системы, построенной на основе ПЛИС-технологии, составляет М логических блоков (элементов). Для вычисления конвейерной функции /¡" необходимо К логических блоков. При этом каждая хромосома обрабатывается за время Для вычисления нового члена популяции необходимо арифметико-логическое устройство, содержащее Ь логических блоков, причем время синтеза новой особи равно Для обеспечения

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

М

¡.Л к

'о

!? г*

'п

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

к

0 = »

з' '* (*

у=! 1=1 '=■

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

= + 'о"

Данное время существенно меньше времени параллельной реализации задачи

л,

к >1 Р , ч

для которой время решения определяется как

(1)

(2)

где /0 - усредненное время вычисления элементов процедуры. Степень распараллеливания д можно определить как М. .

Для чисто конвейерной реализации вычислений

"с

* 5-

С = >> || >>(/М),+, + /\5~1><+г(.Н) •'*+')

время решения задач составит

Т2='н+(ЛЛ + ~к-(о-

5

(3)

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

На рис. 17 и рис. 18 приведены зависимости времени решения, согласно уравнениям (1-3), и эффективности при равных аппаратных затратах параллельной (кривая 1), конвейерной (кривая 2) и макроконвейерной (кривая 3) реализаций генетического алгоритма

10М м

Рис. 18

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

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

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

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

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

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

4) Разработаны программные средства поддержки смешанных одновременных вычислений.

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

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

1. Иванов А.И., Коновальчик П.М. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач // Информационные технологии. -Москва, 2004. - № 12. - С. 38-43.

2. Иванов А.И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. - Донецк: Наука 1 освгга, 2004. - Т4. - С. 15-26.

3. Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д., Модульно-наращиваемые многопроцессорные вычислительные системы для решения задач математической физики // Материалы Всероссийской Научно-Технической Конференции "Параллельные вычисления в задачах математической физики". - Ростов-на-Дону: Изд-во ЮГИНФО РГУ, 2004. - С. 77-83.

4. Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 2004. - Т 1. - С. 34-38.

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

системы Материалы международной научно-технической конференции - Таганрог Изд-воТРТУ, 2004 -Т1 -С 101-106

6 Иванов А И, Коновальчик П М, Левин И И, Малеванчук А Д Многопроцессорная система, адаптируемая под информационную структуру задач различных классов // Искусственный интеллект - Донецк Наука 1 осе1Та, 2004 - ТЗ - С 140-148

7 Иванов А И , Коновальчик П М , Левин И И , Малеванчук А Д Макрообъектная вычислительная система // Тематический выпуск "Интеллектуальные и многопроцессорные системы" Известия ТРТУ - Таганрог Изд-во ТРТУ, 2004 - С 2836

ЛР № 020565 ог 23 июня 1997 г Подписано к печати 26 04 2005 г Формат 60x84 1,16 Бумагу офсетная Печать офсетная Уел пл -1,0 Уч -издл -0,9 Заказ №301 Тираж 100 экз

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

Of, Л? -

/ «

1 a . ^

T f

/

Введение.

1. АНАЛИЗ ПРОЦЕССОВ ВЫСОКОСКОРОСТНОЙ ОБРАБОТКИ ДАННЫХ.

1.1. Определение задач больших размерностей.

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

1.3. Анализ путей построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач.

1.4. Архитектура ПЛИС-систем.

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

1.6. Выводы.

2. МЕТОДЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ПЛИС-ТЕХНОЛОГИИ ДЛЯ РЕШЕНИЯ РАСЧЕТОЕМКИХ ЗАДАЧ. ф 2.1. Конвейерная реализация трудновычислимых фрагментов задачи.

2.2. Параллельно-конвейерная реализация условных операторов.

2.3. Реализация рекуррентных выражений.

2.4. Реализация параллельных вычислений синхронизируемых макроконвейером.

2.5. Выводы.

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

3.1. Методы организации параллельно-конвейерных вычислений в вычислительных системах на основе ПЛИС.

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

V информации.

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

3.4. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Проведен анализ методов и моделей одновременных вычислений.

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

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

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

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

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

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

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

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

Практическая значимость. Использование созданных методов и программных средств позволяет повысить производительность при решении ряда вычислительно сложных задач в 1,5 - 2 раза.

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

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

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

Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИОКР "Фактор", "Начинка", "Радикал", "Прокол-Б1", выполняемыми ЗАО "Эврика" и ОАО "СКБ Топаз", а также при разработке специального программного обеспечения в войсковой части 26165. Кроме того, созданные программные средства были использованы при разработке и отладке программно-технических средств перегрузочной машины ядерного реактора, выполняемых в рамках ОКР "Контроль", что подтверждается соответствующими актами внедрения.

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

- Научная международная школа "Высокопроизводительные вычислительные системы (ВПВС-2004)", Москва-Ростов-на-Дону-Таганрог, 2004 г.;

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

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

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

1) Иванов А.И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Высокопроизводительные вычислительные системы (ВГТВС-2004). Материалы научной международной школы. - Таганрог: Изд-во ТРТУ, 2004. - С. 75-79.

2) Иванов А.И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. — Донецк: Наука \ осв1та, 2004. - Т 4. - С. 15-26.

3) Иванов А.И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 2004. -Т 1. - С. 101-106.

4) Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Модульно-наращиваемые многопроцессорные вычислительные системы для решения задач математической физики // Материалы Всероссийской Научно-Технической Конференции "Параллельные вычисления в задачах математической физики". - Ростов-на-Дону: Изд-во ЮГИНФО РГУ, 2004. -С. 77-83.

5) Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 2004. - Т 1. - С. 34-38.

6) Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Высокопроизводительные вычислительные системы

ВПВС-2004). Материалы научной международной школы. - Таганрог: Изд-во ТРТУ, 2004. - С. 44-49.

7) Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под информационную структуру задач различных классов // Искусственный интеллект. — Донецк: Наука i освгга, 2004.-ТЗ.-С. 140-148.

8) Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Макрообъектная вычислительная система // Тематический выпуск "Интеллектуальные и многопроцессорные системы". Известия ТРТУ. -Таганрог: Изд-во ТРТУ, 2004. - С. 28-36.

9. Иванов А.И., Коновальчик П.М. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач // Информационные технологии. Москва, 2004. - № 12. - С. 38-43.

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

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

3.4. Выводы

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

2) Проектирование вычислительных устройств на основе ПЛИС требует рационального сочетания следующих принципов:

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

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

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

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

4) В состав средств описания входят: графический редактор описания фрагмента конвейерного вычисления, программы анализа синхронизации, программа оптимизации информационного графа конвейера, а также транслятор конвейерного графа в УЬГОЬ-описание.

Средства исполнения, прежде всего, включают в себя компоненты ядра встраиваемой ОС.

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

172

ЗАКЛЮЧЕНИЕ

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

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

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

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

3) Показано, что при конвейерной реализации вычислений на ПЛИС основными препятствиями повышению производительности являются:

- условные операторы;

- обратные связи (рекурсии);

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

- большой объем информационно-незначимых пересылок.

4) Для каждого из этих препятствий определены методы преодоления.

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

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

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

8) В качестве примера преимуществ совмещения параллельной и конвейерной форм обработки в одном устройстве приведена оригинальная реализация параллельного генетического алгоритма.

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

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

3. Gordon Е. Moore. Cramming more components onto integrated circuits. Electronics, Volume 38, Number 8, April 19, 1965.

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

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

6. Иванов А.И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. Донецк: Наука i ocBiTa, 2004. - Т 4. - С. 15-26.

7. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Спб.: БХВ-Петербург, 2004. - 600 с.

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

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

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

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

12. П.Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. - 432 с.

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

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

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

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

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

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

19. Джон Т. Архитектуры вычислительных систем. // Электроника, 1989. -№2. -С. 11-20.

20. Хуан К. Перспективные методы параллельной обработки и архитектура суперЭВМ. //ТИИЭР, 1987. № 10. - С.4-41.22. http://www.beowulf.org23. http://clusters.top500.org.

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

22. MPI: the message passing interface //http://parallel.ru/tech/techdev/mpi.html.

23. Flynn M.J. Some computer organizations and their effectivenss. IEEE Trans., 1972, v. 6-21, p. 948-960

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

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

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

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

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

29. Кохонен Т. Ассоциативная память. М.: Мир, 1980.34. http://www.cray.com/products/systems/.

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

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

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

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

34. IEEE Std 1076-1993 // IEEE Standart VHDL Language Reference Manual. IEEE New York, USA, 1994. 632 p.

35. 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.

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

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

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

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

40. Т. Makimito. The Rising Wave of Field Programmability. Proceeding of Tehth International Conference on Field-Programmable Logic and Applications FLP-2000. Villach. Austria. August 2000.Springer Lecture Notes in Computer Science 1996. P. 1-6.

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

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

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

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

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

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

47. Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под информационную структуру задач различных классов // Искусственный интеллект. Донецк: Наука i освгга, 2004.-ТЗ.-С. 140-148.

48. Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Макрообъектная вычислительная система // Тематический выпуск

49. Интеллектуальные и многопроцессорные системы». Известия ТРТУ. -Таганрог: Изд-во ТРТУ, 2004. С. 28-36.

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

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

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

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

54. Сергиенко A.M. VHDL для проектирования вычислительных устройств. Киев: ЧП «Корнейчук», ООО «ТИД «ДС», 2003. - 208 с.

55. Рао С.К., Кайлат Т. Регулярные итеративные алгоритмы и их реализация в процессорных матрицах // ТИИЭР, 1988. Т. 76. - №3. - С. 58-69.

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

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

58. Иванов А.И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. Донецк: Наука i освгга, 2004. - Т 4. - С. 15-26.

59. Иванов А.И., Коновальчик П.М. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач // Информационные технологии. Москва, 2004. № 12. - С. 38-43.

60. Шейнин Ю.Е. Организация асинхронного вычислительного процесса над структурными данными / В кн.: Параллельное программирование и высокопроизводительные системы. Новосибирск: ВЦ СО АН СССР, 1980. -Ч. 2.-С. 107-116.

61. Мясников В.А., Игнатьев М.Б., Кочкин A.A., Шейнин Ю.Е. Микропроцессоры: системы программирования и отладки. М.: Энергоатомиздат, 1985. - 272 с.

62. Шейнин Ю.Е. Формальная модель динамических параллельных вычислений в параллельных вычислительных системах обработки экспериментальных данных. Научное Приборостроение, 1999. - Т. 9. - № 2. -С. 22-29.

63. Sheynin Y., Novoselova a.I. Object-orientation in parallel VSIPL architecture. Object-Oriented Real-Time Distributed Computing, 2001. ISORC -2001.Proceedings. Fourth IEEE International Symposium on Object-Oriented RealTime Distributed.

64. Котов B.E. Сети Петри. M.: Наука. Главная редакция физико-математической литературы, 1984. - 160 с.

65. VHDL'93. IEEE Standard VHDL Language Reference Manual. IEEE Std 1076-1993.-264 p.

66. Beveridge & Wiener. Multithreading Applications in Win32 / Addison-Wesley, 1997.-368 p.

67. Курейчик B.M. Генетические алгоритмы: Монография. Таганрог: Изд-воТРТУ, 1998.

68. Курейчик В.М. Генетические алгоритмы и их применение: Монография. Таганрог: Изд-во ТРТУ, 2002.

69. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.

70. Искусственный интеллект: В 3 кн. Кн. 2. Модели и методы . Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

71. Попов Э.В., Фирдман Г.Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта. М.: Наука, 1976.

72. Курейчик В.В. Эволюционные методы решения оптимизационных задач. Монография. Таганрог: Изд-во ТРТУ, 1999.

73. Нейронные сети, генетические алгоритмы и нечеткие системы М. Пилиньский, Д. Рутковская. 452 стр., 2004 г. Издательство: Горячая Линия -Телеком. ISBN 5-93517-103-1

74. Goldberg,Deb. A comparative analysis of selection schemes used in genetic algorithms. 1991.

75. De Jong, K. (1975). An analysis of the behaviour of a class of genetic adaptive systems. PhD thesis, University of Michigan.

76. Cavicchio, Daniel J. (1970). Adaptive Search Using Simulated Evolution. Ph.D. Dissertation, Ann Arbor: University of Michigan.

77. Syswerda, 1989 Syswerda, G. (1989). Uniform crossover in genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, pages 2-8. Morgan Kauffman.

78. D. E. Goldberg, 1989c. Genetic Algorithms in Search, Optimization & Machine Learning Addison-Wesley (Reading, Mass).

79. Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

80. Goldberg, D. (1983). Computer-Aided Gas Pipeline Operation using Genetic Algorithms and Rule Learning. PhD thesis, The University of Michigan.

81. Genetic Algorithms and the Variance of Fitness (1991) David E. Goldberg, Mike Rudnick

82. Genetics Algorithms. Editor T.Back. Proceedings of the 7th International conf., San Francisco, USA, Morgan Kaufman Publishers, Inc, 1997.

83. Эволюционные вычисления и генетические алгоритмы. Составители Гудман Э.Д., Коваленко А.П. Обозрение прикладной и промышленной математики. М.: Изд-во ТВП, 1966.