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

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

Дюбрюкс Сергей Александрович

00'

60 г

/О

388

V

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

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

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

2 Э АПР ¿ОТО

Курск-2010

004601388

Работа выполнена в ГОУ ВПО «Курский государственный технический универс на кафедре вычислительной техники в совместной научно-исследовательской лабо рии Центра информационных технологий в проектировании РАН и Курского госуд венного технического университета: «Информационные распознающие телекомму ционные интеллектуальные системы»

Научный руководитель:

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

официальные оппоненты: д.т.н., профессор К.Т.Н.

Сизов Александр Семенович Таныгин Максим Олегович

Ведущая организация: Белгородский Государственный Технологический Университет им.В.Г.Шухова

Защита диссертации состоится «13» мая 2010 г. в 14:00 часов на засед диссертационного совета Д 212.105.02 при Курском государственном техниче университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал). С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «11» апреля 2010 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.105.02

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

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

Количество процессоров в многопроцессорных системах постоянно увеличивается, поэтому для их полного и эффективного использования, требуется загрузка каждого процессора информационно-независимыми задачами. В связи с этим возникает задача отображения последовательных программ на множестве процессоров. Для этого применяются методы и алгоритмы выявления линейных, условных и циклических независимых участков (Вл.В. Воеводин, В.В. Воеводин, A.B. Каляев, Б .Я. Штейнберг, Э.А. Трах-тенгерц, А.П. Типикин, И.В. Зотов), которые в основном ориентированы на программную реализацию. В многопроцессорных системах задача распараллеливания выполняется, как правило, централизованно хост-процессором. Известно, что в число его задач кроме компиляции входит также маршрутизация, назначение и перераспределение заданий, реконфигурация системы в случае сбоев и другие функции, обеспечивающие управление системой. Процедура компиляции состоит из нескольких этапов, отличающихся вычислительной сложностью, поэтому для решения задачи обеспечения распараллеливания сложных последовательных программ требуется привлечение дополнительных технических средств.

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

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

Работа выполнена в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования и науки РФ в 20062009 годах.

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

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

Объектом исследования являются процессы обработки данных в вычислител системах.

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

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

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

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

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

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

Научная новизна результатов диссертации:

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

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

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

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

Практическая ценность результатов исследований:

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

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

3. Разработан пакет программ для имитационного моделирования, позволяющий получить оценку временного выигрыша в скорости решения задач с использованием разработанного вычислительного устройства. Моделирование показало, что применение устройства ускоряет решение задачи компиляции для 10-400 операторов в 5-8 раз, а для 520 и более - примерно в 10 раз.

Реализация и внедрение. Результаты диссертационной работы применены в модернизированной версии расчетного комплекса «ТОКСИ+» по оценке последствий аварий на опасных производственных объектах для увеличения быстродействия комплекса в ОАО «НТЦ «Промышленная безопасность», а также внедрены в учебном процессе на кафедре вычислительной техники КурскГТУ при проведении занятий по дисциплинам «Организация ЭВМ и систем», «Теоретические основы организации многопроцессорных комплексов и систем».

Научные результаты, выносимые на защиту:

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

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

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

Апробация работы. Основные положения и результаты диссертации обсуждались и получили положительную оценку на региональных российских и международных конференциях: "Машиностроение и техносфера XXI века" (Украина 2007, 2009 год), "Оптико-элекгронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (Курск 2008).

Публикации. По результатам диссертации опубликовано 12 печатных работ, среди которых 7 статей (из них 3 по перечню ВАК Минобрнауки РФ) и патент на изобретение, получены два свидетельства о государственной регистрации программ для ЭВМ.

Личный вклад автора.

Все выносимые на защиту научные результаты получены соискателем лично. В ботах, опубликованных в соавторстве, автором выполнено следующее: в [1] предло метод выявления параллелизма внутри линейных участков последовательных прогр в [2] описан метод объединения и разделения тел циклических участков последоват ных программ, в [3] предложен алгоритм выявления независимых фрагментов поел вательных программ, основанный на анализе их внутренней структуры, в [4] разраб на схема подключения вычислительного устройства к хост-процессору, в [5, 6] разр тан метод выявления параллелизма между линейными и циклическими участками следовательных программ, в [7] предложена структурная схема специализирован вычислительного устройства для выявления параллелизма внутри линейных и цикл ских участков программ, в [8] приведено решение задачи переназначения перемен при выявлении параллельных участков внутри последовательных программ, в [9] р ботана методика поиска и устранения избыточных вычислений в последователь участках программ, в [10] предложен принцип схемотехнической реализации устро ва, в [11, 12] разработан пакет программ для имитационного моделирования раб предлагаемых методов распараллеливания и устройства на их основе.

Объём и структура работы. Работа состоит из введения, четырех глав, закл ния, приложений и списка литературы, включающего 80 наименований. Диссерт содержит 141 страницу текста (включая 7 приложений) и поясняется 25 рисунками таблицами.

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

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

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

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

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

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

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

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

Реализация распараплеливателя на одном кристалле с процессором и несколькими вычислительными ядрами (архитектура VELOCITI в сигнальных процессорах Texas Instruments семейства 6000, EPIC в суперскалярных процессорах Itanium ф. Intel и др.) наряду с достоинствами также имеет ряд недостатков - требует увеличения объёма кристалла, следствием чего является увеличение количества и длин трасс внутри микросхемы, задержек распространения сигнала и повышение энергопотребления. Также аппаратная реализация устройства распараллеливания на одном кристалле с процессором требует существенного увеличения встроенной оперативной памяти или обращения к более медленным внешним запоминающим устройствам. Подобные распараллеливатели не обладают достаточной универсальностью, так как предназначены для работы в определённой архитектуре.

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

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

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

ременных, где / = к = \,М, N - количество строк исходной последовательной пр граммы, М - общее количество переменных. Для каждой строки О, существуют коэ фициенты \ki\y и \ко\^, показывающие наличие в ней входных переменных К/ и в ходных переменных (-'о, где Шр = {0,1}, кор = {0,1}, р-\,М ■ Тогда для будет вып няться равенство:

коf • Уок = кц ■ У'1{£И2 ■ Р722.. .2к1м ■ VIм, (1)

где И - признак выполняемой операции, /- номер единичного коэффициента ко для той строки.

Множество К1 = \к1р^к1р1,...,к1рЫ} из N подмножеств Шр , задаё

матрицей входных переменных I = ||/|| . где |/|? = Шр, д = 1,М.

Множество = задаёт коэффициенты, показывающие наличие выходн переменных Уо в строке Множество КО из N подмножеств ко5 ={ко„ко2,...,к задаётся матрицей выходных переменных 0 = где = ~ •

Множество операторов программы задаётся как , где Мор - ко

чество операторов программы, Л,гор=Л/

Связи по управлению между операторами программы описываются матрицей с дования М? = ||Л&|| :

м (1, если Л,• Л»

л \0, в противном случае.'

где к = \,М, символ '>" обозначает наличие перехода между операторами.

Матрица М? используется для анализа внутренней структуры программ. Она ка матрицы / и О являются исходными данными для организации процесса распаралле вания. Матрице следования Ш соответствует матрица достижимости М<1: если Я н> &

Ш*= п

[0, в противном случае.

где символ "ь> "обозначает возможность достижения оператора К/, из оператора Если Я, н» /?,, то существует подмножество И, такое й'сЛД. р^.н; рЛ.<рК\.,Н\ уЯк.

Множеству К операторов программы соответствует множество VI = {У,,У2,..., уровней вложенности. Максимальное значение уровня вложенно

Участком уровня вложенности V, УеУЬ будем называть последовательность оп торов где У=У„л =У„Л11 =... = УКг, а А,А + \,А + 2,...,В-\,В - послед

тельные натуральные числа. Тогда длина участка ь = В-А + \. При У=0 участок явля линейным, иначе - циклическим. Общее число участков Ии находится по следую формуле:

М-1

О, если УЬ,=УЬ^

" % 1, если УЦ * У1М! Представим программу как множество участков и" ={{/,'',С^,...,^}, характеризующихся разными значениями V уровней вложенности операторов, где Z = V-\,МУ. Она задаётся следующими матрицами:

- следования для участков = ||Лй_С/||^ ^ ,

где АЛ и = (!.' если и' V , 8=Щ.

- [0, в противном случае. "

- входных переменных для участков I= |]/_£У|д, ^,

- выходных переменных для участков 0_11 = \0_и\^ ,

-достижимости для участков Мс1 _11 = ||Мг/_С/||^ хд, . В её ячейку записывается 1,

если из участка £/, можно достигнуть участка : (I, если и, и, [О, в противном случае. Если и, 1н> иг, то существует подмножество {/'.такое что и' с и,и, (р и;,и; <р иг,...,а'ЫА <р ср и,.

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

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

F_t/(z,g) = (1_иг А0_иё) Vл0_и2) V{0_и2 л0_иё) (2)

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

Яи) = (/; А Ок) V (1к Л О, ) V (О, А Ок) (3)

Полный набор информационных зависимостей между всеми участками программы задаётся матрицей неполного параллелизма МКР_11=\МИР_11^ . Пользуясь (2),

получаем

(О, если(М/_6г =0)у((Л/</_£/ =1)л(^_(/(г,г) = 0),

ШР-и* если(Ш_[/ч=1)л(Р_£/(г,з) = 1). Полный набор информационных зависимостей между всеми операторами программы задаётся матрицей неполного параллелизма ММР=\АШР^х^. Используя (3), получаем

(0, если {Мс11к = 0) V ((АЦ , = 1) л к) = 0)),

Д/Д/Р = ^

[1, если (Ш1к = 1) л (Р0, к) = 1).

Для представления результата распараллеливания в работе используются пон яруса и ветви. Ветвями применительно к участкам будем называть не имеющие пер чений подмножества Вг _11 = {Ьги1,Ьги1,...,Ьги0} участков исходной програ (Вг _и е и, £) е [1, N„1), сформированные при распараллеливании, предназначенные последовательного выполнения. Ярусами применительно к участкам будем называт имеющие пересечений подмножества Уаг_и = {уагщ,уаги1,...,уагис} участков исход программы {Yar_Ue.lI, Се[1,Л^]), сформированные в процессе распараллелива предназначенные для параллельного выполнения.

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

Значения XII и ЯУ при Щ1иг\Уа\хи, ШеВг_и, ХЦеУаг_и назовём координат участка V,. Они определяют порядок выполнения участка V, в многопроцессорной теме, то есть номер У11 процессорной группы, на которую его следует назначить, и дию XII, на которой будут готовы все операнды для его выполнения. Исходя из э распараллеливание участков программы можно представить как эквивалентное пр

разование множества и = ,иг,...,иА} к множеству ирЦг~и уагиХ

При распараллеливании участков и,, 11! -к|>0) выявляется параллелизм; ня циклов, позволяющий назначать информационно-независимые циклы на раз группы процессоров. Каждому участку Уг ставится в соответствие номер Ю обр тывающей его группы процессоров, а также номер ХУ стадии выполнения участка данной группой.

На основе вышеприведённой формализации разработан метод распараллелива программ, состоящий из следующих этапов:

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

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

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

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

Все операторы л,, входящие в линейные и циклические участки, подвергаю дальнейшему распараллеливанию. При выявлении параллелизма на уровне операто ветвями будем называть не имеющие пересечений подмножества Вг = [Ьг^Ьгг, ~, операторов участка и, (Дг е (У,, Де^ЛЧ), сформированные в процессе распаралле вания, предназначенные для последовательного выполнения. Ярусами будем назыв

не имеющие пересечений подмножества Уаг = {Уаг„Уаг2.....Уагс} операторов внутри участка U, программы (YareUj, Се[1,7V]), сформированные в процессе распараллеливания, предназначенные для параллельного выполнения.

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

в одно и только в одно подмножество Вт, а также в одно и только в одно подмножество Yar. Значения Хор и Yop при YopeBr, Хоре Yar назовём координатами

оператора R,. Координаты (Хор,Yop) определяют порядок выполнения оператора R, в многопроцессорной системе, то есть номер Yop процессора, на который его следует назначить, и стадию Хор, на которой будут готовы все операнды для его выполнения.

Распараллеливание операторов участка программы можно представить как эквивалентное преобразование множества R = {R,,R2,...,Rt} к множеству

Rp'rar = ю'I > -> КРн^а}, состоящее из следующих этапов:

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

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

3. Преобразование множества R операторов участка программы в последовательной форме к множеству операторов Rp программы в параллельной форме с помощью матрицы неполного параллелизма.

При таком распараллеливании каждому оператору Д ставится в соответствие номер Уор обрабатывающего его процессора из группы YU, которая должна выполнять участок Ut,ReUt, а также номер Хор стадии выполнения участка Uz процессорной группой YU.

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

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

1. Построение матрицы достижимости Md на основе матрицы следования Ms.

2. Определение уровня вложенности V для каждого оператора из множества R с использованием матрицы следования Ms, формирование множества VL.

3. Анализ элементов множества VL с дальнейшим преобразованием множества R операторов программы к множеству U участков, операторы которых имеют одинаковый уровень вложенности.

3.1. Нахождение общего числа участков Nu.

3.2. Нахождение начальной Beg, и конечной Endz границ всех участков U2.

4. Распараллеливание операторов Ä ei/,, где i = IL, L = Endг - Beg, +1.

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

4.2. Вычисление частных матриц достижимости Мд. на основе частных матри

следования Ш.

4.3. Вычисление частных матриц неполного параллелизма МИР.

4.4. Распараллеливание операторов участков С/г на основе матриц МИР.

5. Преобразование множества и к множеству 1101 участков с V равным 0 или 1.

5.1. Нахождение общего числа участков Ыит.

5.2. Нахождение начальной BegOlч и конечной Епй01ч границ участков

6. Распараллеливание участков и01?.

6.1. Вычисление матрицы следования Мз_и01, матриц входных и выходных переменных /_(/01 и 0_С01 для участков.

6.2. Вычисление на основе матрицы следования М$_ио\ матрицы достижимо сти Мс1_и01 для участков.

6.3. Вычисление матрицы неполного параллелизма МИР_ио\ для участков.

6.4. Распараллеливание участков £/01, на основе матрицы MNP _и01.

6.5 Определение количества процессоров для выполнения программы.

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

Графики 1-3 (рис.1) показывают результаты моделирования работы метода выяв ния информационно-независимых операторов в линейных участках последовательн программ, преобразующего их к параллельному виду: по оси X отложено прираще количества операторов от 15 до 100, а по оси У - число ярусов полученной паралле ной программы. Общее число М входных и выходных переменных равно 60 (кривая 40 (кривая 2) и 20 (кривая 1). Для графика 1 значение доверительной вероятности, численная по методу Стьюдента, изменяется от 95,3% до 98,3%, для графика 2 -93,8% до 98%, для графика 3 - от 92 до 97,5%.

Разность Д = Д'-С, где С - число ярусов полученной программы в параллель форме, N - количество операторов исходной программы в последовательной форме, допуске, что время выполнения операторов одинакова, определяет размер времени выигрыша при переходе к параллельной форме представления программ. Из графи 1-3 следует, что при увеличении как числа операторов N. так и числа переменных разность N-0 увеличивается, следовательно, применение метода выгоднее при реше объёмных задач, требующих оперативной реакции системы.

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

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

На рисунке 2 приведена структурно-функциональная организация разработанного устройства. Оно состоит из микропроцессорного ядра MP, контроллера прямого доступа KPDP, схемы умножения частоты PLL, ОЗУ данных RAM_16_Ю размерностью 1024*16, ОЗУ программ RAM_16_512 размерностью 512x16, D-триггеров D1 признака выполнения задания, D2 выборки внешней памяти, D3 и D4 генерации стробов чтения и записи внешней памяти. Устройство также содержит четыре типовых вычислительных блока F1-F4, которые выполняют функции расчета матрицы достижимости, элементов множества уровней вложенности, матрицы неполного параллелизма для последующего распараллеливания операторов программы.

Каждый типовой вычислительный блок (рис.3) содержит входное RAM_IN и выходное RAM_OUT ОЗУ для сохранения заданий, поступающих от микропроцессорного ядра. Такая структура позволяет блокам параллельно выполнять отдельные стадии распараллеливания участков программы. Также типовой блок включает интерфейс взаимодействия с микропроцессором, функциональный вычислительный модуль FUNCTION и

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

vcc m

ЦГЗ—е=эмт

Р Пс. —1

IN_P[15..01

КРОР

0(15.J I HLD EN

AJ/..UI RE2

INT

CS A_RAW5..0

HLDA 00[15..0]

RW WE PCS

'IN_P|15..0] INT3

_3HOLD

— IN P[15..0J —WRST —P ID7

Рис.2 Структурно-функциональная организация устройства

Рис.3 Функциональная схема типового вычислительного блока При завершении выполнения распараллеливания устройство вырабатыв прерывание INT, получает от хоста начальный адрес блока памяти, вырабатыв запрос на прямой доступ и при его подтверждении записывает результат (выход слова) в указанный блок внешней памяти. Их структура приведена на рисунке 4. Сл содержит номер оператора N_op, поля Yarusl и Branch 1, определяющие но процессорной группы для выполнения участка, в который входит данный оператор порядок выполнения группы, а также поля Yarus2 и Branch2, определяющие но

процессора для выполнения оператора в процессорной группе ВгапсЫ и порядок его выполнения. Поле V показывает уровень вложенности оператора.

N_op V Yarns 1 ВгапсЫ Yarus2 Branch2

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

Результаты имитационного моделирования работы вычислительного устройства и хост-процессора при распараллеливании тестовых задач показаны на графиках 1 и 2 (рис.5). На них представлена обобщённая зависимость времени выполнения задач распараллеливания в секундах хост-процессором (график 1) и предлагаемым вычислительным устройством (график 2) от числа N операторов компилируемого фрагмента программы при суммарном числе входных и выходных переменных М, равном 200. При этом каждой точке графиков соответствует отдельная задача, характеризующаяся исходными данными - бинарными матрицами ||/

%*м и 1м4хЛ'-Времявы-

М„ и И при

ВДхА/'

поинения этапов метода рассчитано для вариантов ||~цдгхд/ - ]Г'"Цд[хдг

которых суммарная временная сложность задачи является максимальной. Частоты работы устройства и хост-процессора равны 200 МГц, время доступа к внешней памяти хост-процессора - 20 не, время доступа к внутренней памяти предлагаемого устройства -8 не. Полученный выигрыш во времени (разность между 1 и 2) обусловлен как меньшим временем доступа к внутренней памяти, так и параллельным вычислением бинарных матриц для разных участков программы.

1 - хост-пооиессор

2 - акселератор

4 500 4 000 3 500

0 3 000

1 2 500 §■2 000

1 500 1 000 500

1050100150 200250 330350 400450 500 число операторе в, N Рис.5 Зависимость времени компиляции задач хост-процессором и устройством от числа операторов

Таблица 1. Зависимость времени распараллеливания от числа операто

Количество опе- 50 100 150 200 250 400 520

раторов

Хост-процессор 5.1с 26.1с 37.4 с 64.1 с 265.2 с 1711,1с 4896 с

Устройство 0.93 с 3.8 с 5.3 с 9с 37,1 с 219,3 с 454 с

Отношение 5.49 6,86 7,05 7.12 7.15 7,81 10,78

Из зависимостей 1 и 2 на рисунке 5 и таблицы 1 следует, что временной выигр предлагаемого устройства растет с увеличением числа операторов. Так, при числе о раторов больше 510 применение аппаратной компиляции с использованием разработ ного устройства позволяет увеличить скорость её выполнения более чем в 10 раз сравнению с аналогичной программной реализацией распараллеливания на хо процессоре.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в изданиях по перечню ВАК Минобрнауки РФ

\. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Метод выявления параллелизма внутри линейных участков последовательных программ и его аппаратная реализация // Известия вузов. Приборостроение. - 2007. - Т.51, №2. - 4 п.л. (лично автором 3,4 пл.).

2. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Метод объединения и разделения циклических участков последовательных наследуемых программ // Известия вузов. Приборостроение. - 2008. - Т.51, №2. 4 п.л. (лично автором 3,5 пл.).

3. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Математическая модель выявления независимых параллельных участков последовательных программ // Нейрокомпьютеры: разработка, применение. - 2009. - №12 - 4 п.л. (лично автором 3,3 пл.).

Статьи

4. Дюбрюкс, СЛ., Борзов Д.Б. Аппаратные средства для размещения задач в параллельных системах II Системы и методы обработки и анализа информации: Сборник научных статей. - Москва: Горячая линия - Телеком, 2005. - 5 пл. (лично автором 3,9 пл.).

5. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Выявление параллелизма внутри линейных участков последовательных программ со связями по управлению // Сборник трудов XIV Международной научно-технической конференции «Машиностроение и техносфера XXI века. Т2». - Донецк, 2007. - 4 пл. (лично автором 3,3 пл.).

6. Дюбрюкс, СЛ. Аппаратно-ориентированный подход к выявлению параллелизма в последовательных программах со связями по управлению и циклами // Сборник трудов XVI международной научно-технической конференции "Машиностроение и техносфера XXI века. Т1». - Донецк, 2009. - 4 пл. (лично автором 3,1 пл.).

Тезисы докладов и материалы конференций

7. Дюбрюкс, СЛ., Борзов Д.Б., Минайлов В.В. Устройство выявления параллелизма внутри линейных участков программ со связями по управлению // Материалы VIII Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах». - Новочеркасск, 2007. -3,9 пл. (лично автором 3,3 пл.).

8. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Методика переназначения переменных при выявлении параллельных участков внутри последовательных программ // Сборник материалов VIII Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации». - Курск, 2008 - 2,8 пл. (лично автором 2 пл.).

9. Дюбрюкс, СЛ., Борзов Д.Б. Методика поиска и устранения избыточных вычислений в последовательных участках программ П Студенческий научно-технический журнал «Инженер». - Донецк. 2008. - №9. - 2,9 пл. (лично автором 2,3 пл.).

10. Дюбрюкс, СЛ., Борзов Д.Б., Титов B.C. Принцип организации устройства-акселератора выявления параллельно-независимых линейных и циклических участков программ // Материалы VIII Международной научно-практической конференции «Микропроцессорные, аналоговые, и цифровые системы: проектирование и схемотехника, теория и вопросы применения». - Новочеркасск, 2008 - 3.5 п.л. (лично автором 2,3 пл.).

Свидетельства о государственной регистрации программ для ЭВМ

11 .Дюбрюкс, С.А., Борзов Д.Б., Титов B.C. Свидетельство о государственной р гистрации программы для ЭВМ №2010610466. Программная модель распараллеливай линейных и циклических участков последовательных программ со связями по управл нию - Москва: РосПатент, зарегистрировано в Реестре программ для ЭВМ 11 янва 2010 г.

12.Дюбрюкс, С.А., Борзов Д.Б., Титов B.C. Свидетельство о государственной р гистрации программы для ЭВМ № 2010610467. Программная модель распараллелив ния линейных участков последовательных программ со связями по управлению - Мое ва: РосПатент, зарегистрировано в Реестре программ для ЭВМ 11 января 2010 г.

Соискатель

С. А. Дюбрюкс

Подписано в печать_. Формат 60x84 1/16.

Печатных листов Тираж 100 экз. Заказ Курский государственный технический университет 305040, г. Курск, ул 50 лет Октября, 94.

Введение.

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

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

1.2. Распараллеливание как стадия компиляции программ.

1.3. Классификация методов распараллеливания.

Выводы.

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

2.1. Формализованная постановка задачи распараллеливания.

2.2. Анализ внутренней структуры программ.

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

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

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

2.6. Способ устранения избыточных вычислений.

Выводы.

3. Обобщённый алгоритм распараллеливания линейных, условных и циклических фрагментов программ.

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

3.1.1. Построение матрицы достижимости на основе матрицы следования

3.1.2. Формирование множества уровней вложенности операторов.

3.1.3. Преобразование множества операторов программы к множеству участков на основе множества значений уровней вложенности.

3.1.4. Распараллеливание участков программы с одинаковым уровнем вложенности с использованием программной модели.

3.1.5. Распараллеливание участков с уровнями вложенности 0 и 1.

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

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

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

Выводы.

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

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

4.2. Обобщённый алгоритм работы специализированного вычислительного устройства.

4.3. Контроллер прямого доступа к памяти.

4.4. Описание работы типовых вычислительных блоков.

4.5. Описание работы функциональных вычислителей.

4.5.1. Вычислитель множества уровней вложенности операторов программ

4.5.2. Вычислитель матрицы достижимости.

4.5.3. Вычислитель матрицы неполного параллелизма.

4.5.4. Распараллеливатель.

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

Выводы.

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

Количество процессоров в многопроцессорных системах постоянно увеличивается, поэтому для их полного и эффективного использования, требуется загрузка каждого процессора информационно-независимыми задачами. В связи с этим возникает задача отображения последовательных программ на множестве процессоров. Для этого применяются методы и алгоритмы выявления линейных, условных и циклических независимых участков (Вл.В. Воеводин, В.В. Воеводин, A.B. Каляев, Б.Я. Штейнберг, Э.А. Трахтенгерц, А.П. Типикин, И.В. Зотов), которые в основном ориентированы на программную реализацию. В многопроцессорных системах задача распараллеливания выполняется, как правило, централизованно хост—процессором. Известно, что в число его задач кроме компиляции входит также маршрутизация, назначение и перераспределение заданий, реконфигурация системы в случае сбоев и другие функции, обеспечивающие управление системой. Процедура компиляции состоит из нескольких этапов, отличающихся вычислительной сложностью, поэтому для решения задачи обеспечения распараллеливания сложных последовательных программ требуется привлечение дополнительных технических средств.

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

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

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

Объектом исследования являются процессы обработки данных в вычислительных системах.

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Разработан пакет программ для имитационного моделирования, позволяющий получить оценку временного выигрыша в скорости решения задач с использованием разработанного вычислительного устройства. Моделирование показало, что применение устройства ускоряет решение задачи компиляции для 10-500 операторов в 5-8 раз, а для 520 и более - примерно в 10 раз.

На защиту выносится следующие результаты

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

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

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

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

1. Цилькер, Б .Я. Организация ЭВМ и систем Текст.: учебник для вузов / Б .Я. Цилькер, С.А. Орлов. СПб.: Питер, 2004. 668 с.

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

3. Ахо,А. Компиляторы: принципы, технологии и инструменты Текст. / Р.Сети, Дж.Ульман. М.: Издательский дом "Вильяме", 2001.

4. Ахо, А. Теория синтаксического анализа, перевода и компиляции Текст. : в 2 т. / Дж.Ульман. М.:Мир, 1978.

5. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин Текст. . М.: Мир, 1975.

6. Емельянов, П.Г. Абстрактная интерпретация императивных программ. Текст.: В сб. Системная Информатика, Вып.6. Новосибирск: Наука, 1998. - с.7—47.

7. Flynn, М. Very high-speed computing system Text. / M. Flynn // Proc. IEEE. 1966. N54. P. 1901-1909.

8. Flynn, M. Some Computer Organisations and Their Effectiveness Text. / M. Flynn // IEEE Trans. Computers. 1972. V.21. N 9. P. 948-960

9. Higbie, L. C. Supercomputer architecture Text. / L. Higbie // Computer. 1973. V.6. N 12. P.48-56.

10. Handler, W. On classification schemes for computer systems in the post Von Neumann era Text. / W. Handler // Lecture Notes in Computer Science, 1975. №89. P 34^16.

11. Thurber, K. J. Large Scale Computer Architecture Text. / K.L. Thurber // Hayden Book Company, Rochelle Park, New Jersey, 1976.

12. Hwang, K. Computer Architecture and Parallel Processing. Text. / K. Hwang, F.A. Briggs // Lecture Notes in Computer Science. 1984. P.32-40.

13. Feng, Т. Some Characteristics of Assotiative Parallel Processing Text. / T. Feng // Proc. 1972 Sagamore Computing Conf. New Jersey, 1972. P. 5-16.

14. Hockney, R. Parallel Computers: Architecture and Performance Text. / R. Hockney // Proc. of Int. Conf. Parallel Computing'85. Computer Architecture News. 1986. P. 33-69.

15. Hockney, R. Classification and Evaluation of ParallelComputer Systems Text. / R. Hockney // Lecture Notes in Computer Science. 1987. N 295. P. 13-25.

16. Johnson, E. E. Completing an MIMD Multiprocessor Taxonomy Text. // E.E. Johnson // Computer Architecture News. 1988. V. 16. N 2. P. 44-48.

17. Duncan, R. A survey of parallel computer architectures Text. // R. Duncan // Computer. V.23. N 2. 1990. P. 5-16.

18. Killicorn, D. A. Taxonomy for Computer Architectures Text. / D.A. Skillicorn // Computer. 1988. V.21. N 11. P. 46-57.

19. Ортега, Дж. Введение в параллельные и векторные методы решения линейных систем Текст. . М. Мир, 1991. - 365с.

20. Чинин, Т.Д. Векторизация программ: теория, методы, реализация Текст.: сб. -М.: Мир, 1991.-272с.

21. Денисенко, В.А. Проблемы схемотехнического моделирования КМОП СБИС Текст. // Компоненты и технологии, 2002. №4.

22. Пяткин, А.К. Реализация на ПЛИС быстрого преобразования Фурье для алгоритмов ЦОС в многофункциональных PJIC Текст. / М.В. Никитин //- "Цифровая обработка сигналов" №3, 2003.

23. Пат. 2039375 РФ, МКИ6 G 06 F 17/00, 17/20. Устройство для реализации продукций. В.М. Довгаль.

24. Пат. 2067315 РФ, МКИ5 G 06 F 15/20. Устройство для реализации подстановок. В.М. Довгаль

25. S. Gochman et al. The Intel Pentium M Processor: Microarchitecture and Performance. Intel Technology Journal, V.7, Issue 2, 2003.

26. Дюбрюкс, C.A. Устройство для формирования размещения и оценки его качества / Д.Б. Борзов // Международный сборник научных трудов «Информационные технологии моделирования и управления. Выпуск 17». Воронеж: Из-во «Научная книга», 2004. — С. 3-8.

27. Картунов, В. Prescott: Последний из могикан? (Pentium 4: от Willamette до Prescott). Ф-Центр, 2005.

28. Бессонов, О. Новое вино в старые мехи. Сопгое: внук процессора Pentium III, племянник архитектуры NetBurst? iXBT.com, 2005.

29. Бессонов,О. Двухъядерный процессор Yonah: уже не Pentium III, ещё не Сопгое. iXBT.com, 2006.

30. Sean Lee, Н.Н. Р6 & NetBurst Microarchitecture. School of ЕСЕ, Georgia Institute of Technology, 2003.

31. IA—32 Intel Architecture Optimization Reference Manual. Intel, 2006.

32. IA-32 Intel Architecture Software Developer's Manual. Intel, 2006.

33. Картунов, В. Детальное исследование архитектуры AMD64. iXBT.com, 2003.

34. De Vries, Н. Understanding the detailed Architecture of AMD's 64 bit Core. Chip-Architect, 2003.

35. Kanter, D. AMD's K8L and 4x4 Preview. Real World Technologies, 2006.i

36. Tendler et al, J. POWER4 system microarchitecture. IBM Journal of Research and Development, V.46, No.l, 2002.

37. Толл, P. P. Множества. Логика. Аксиоматические теории Текст. М.: Просвещение, 1968. - 232 с.

38. Кантор, Г. Труды по теории множеств Текст. -М.: Наука, 1985. с. 173.

39. Куратовский, К. А. Теория множеств Текст. — М.: Мир, 1970. 416 с.

40. Верещагин, Н. К. Лекции по математической логике и теории алгоритмов Текст.: Часть 1. Начала теории множеств / А.Шень.

41. Френкель, А. Основания теории множеств Текст. / И. Бар—Хиллел; Перевод с английского Ю. А. Гастева под редакцией А. С. Есенина-Вольпина. — М.: Мир, 1966.-366 с.

42. Гетманова, А. Д. Учебник по логике. — М.: Владос, 1995. — 303 с.

43. Кондаков Н. И.: Логический словарь-справочник. — М.: Наука, 1975. — 720 с.

44. Дюбрюкс С.А. Метод выявления параллелизма внутри линейных участков последовательных программ и его аппаратная реализация / Д.Б.Борзов, В.С.Титов // Известия вузов. Приборостроение. Т.2 Санкт-Петербург, 2008 - с. 34-38.

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

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

47. Патент №2285289 РФ, БИ №28. Устройство планирования размещения задач в системах с кольцевой организацией при направленной передаче информации / Д.Б. Борзов Д.С. Горощенков; №2005101060/09; заявл. 18.01.2005; опубл. 10.10.2006, Бюл. № 28. 13 с.

48. Ивлев, Ю. В. Учебник логики Текст.: Семестровый курс: Учебник. — М.: Дело, 2003. —208 с.

49. Бочаров, В. А. Основы логики Текст.: Учебник. / В. И. Маркин. — М.: ИН-ФРА-М, 2001. —296 с.

50. Ивин, А. А. ЛогикаТекст.: Учебное пособие. Изд. 2-е. —М.: Знание, 1998.

51. Ивин, А. А. Словарь по логике Текст. / Никифоров A. JI. — М.: Туманит, ВЛАДОС, 1997. —384 с.

52. Корнеев, В.В. Параллельные вычислительные системы Текст. -М:"Нолидж", 1999. 320 с.

53. Дюбрюкс, С.А. Методика поиска и устранения избыточных вычислений в последовательных участках программ / Д.Б.Борзов // Студенческий научно-технический журнал «Инженер», №9. Донецк. 2008. - С.62-64.

54. Дюбрюкс, С.А., Устройство для формирования размещения и оценки его качества / Д.Б. Борзов // Международный сборник научных трудов «Информационные технологии моделирования и управления. Выпуск 17». — Воронеж: Из-во «Научная книга», 2004. — с. 3-8.

55. Костенко, В.А. К вопросу об оценке оптимальной степени параллелизма. -Программирование. 1995, с. 24—28.

56. Антонов, A.C. Параллельное программирование с использованием технологии MPI Текст.: Учебное пособие. -М.: Изд-во МГУ, 2004. 71 с.

57. Бочаров, Н.В. Технологии и техника параллельного программирования. Обзор. // "Программирование", № 1, 2003. с.5-23.

58. Соколинский, Л.Б. Параллельные машины баз данных. // Сборник научно-популярных статей "Российская наука на заре нового века". Под редакцией академика В.П. Скулачева. М.: научный мир, 2001. - с. 484-494.

59. Таненбаум, Э. Распределенные системы. Принципы и парадигмы Текст. -СПб.: Питер, 2003. 877 с.

60. Дюбрюкс, С.А. Метод объединения и разделения циклических участков последовательных наследуемых программ / Д.Б.Борзов, В.С.Титов // Известия вузов. Приборостроение. №2. — Санкт-Петербург,2009 с.34-38.

61. Дюбрюкс, С.А. Программная модель распараллеливания линейных участков последовательных программ со связями по управлению. / Д.Б.Борзов, В.С.Титов // Свидетельство о государственной регистрации программы для ЭВМ № 2010610467. Москва: РосПатент.

62. Кобзарь, А. И. Прикладная математическая статистика Текст. — М.: Физ-матлит, 2006. — 816 с.

63. Бибило, П. Н. Основы языка VHDL Текст. М.: «Солон-Р», 2000.

64. Зотов, В.Ю. Проектирование цифровых устройств на основе ПЛИС фирмы Xilinx в САПР WebPACK ISE Текст. / В.Ю. Зотов. М.: Горячая линия-Телеком, 2003. - 624 с.

65. Зотов, В.Ю. Проектирование цифровых устройств на основе ПЛИС фирмы Xilinx в САПР WebPACK ISE Текст. / В.Ю. Зотов. М.: Горячая линия-Телеком, 2006. - 550 с.

66. Поляков, А.К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры Текст. М.: Солон-пресс, 2009. — 320 с.

67. Максфилд, К. Проектирование на ПЛИС. Курс молодого бойца Текст., 2007. - 440 с.

68. Армстронг Д. Моделирование цифровых систем на языке VHDL Текст. — М.: Мир, 1992.

69. Суворова, Е. Проектирование цифровых систем на VHDL Текст. / Шейнин Ю. Cn6.:BHV, 2003. - 576 с.

70. Тарасов, И. Е. Разработка цифровых устройств на основе ПЛИС Xilinx с применением языка VHDL Текст. / И.Е. Тарасов. М.: Горячая линия-Телеком, 2005.-252 с.

71. Суворова, Е.А. Проектирование цифровых систем на VHDL Текст. / Е.А. Суворова, Ю.Е. Шейнин. СПб.: БХВ-Петербург, 2003. - 576 с.

72. Сергиенко, А.М. VHDL для проектирования вычислительных устройств Текст. / А.М. Сергиенко К.: ЧП "Корнейчук", ООО "ТИД ДС", 2003. - 208 с.

73. Патент №2319204 РФ, МПК G06F 17/50. Устройство для формирования размещения в системах с линейной организацией / С.А.Дюбрюкс, Д.Б.Борзов, В.С.Титов- №2006127974/09; заявл. 01.08.2006; опубл. 10.03.2008, Бюл. № 7. 11 с.