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

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

НОВИКОВ Алексей Владимирович

АВТОМАТИЗАЦИЯ РАСПАРАЛЛЕЛИВАНИЯ АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ

Специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

Тула 2007

003062383

Работа выполнена на кафедре электронных вычислительных машин в Тульском государственном университете

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

ДАНИЛКИН Федор Алексеевич

Официальные оппоненты ~ ДОКТОР технических наук, профессор

ИЗОТОВ Виктор Николаевич - кандидат технических наук, доцент ПОНЯТСКИЙ Валерий Мариафович

Ведущая организация ~ Тульский артиллерийский

инженерный институт

Защита состоится « ¡р » мая 2007 г в 14 часов на заседании диссертационного совета Д 212 271 07 при Тульском государственном университете (300600, г Тула, проспект Ленина, 92, 9 - 101)

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан « /у?"» апреля 2007 г Ученый секретарь

диссертационного совета __Ф А Данилкин

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

1 Формализация модели параллельных вычислений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Прикладные результаты диссертационной работы были внедрены 1) ООО «Научно-производственная фирма ОВЕН-К», г Москва 2) компания «Трейд-М», г Тула

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

Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях 1 Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2002,

2003, 2004, 2005, 2006 гг ) 2 Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2003,

2004, 2005) 3 7-я всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2002) 4 1 -я Всероссийская научно-техническая конференция студентов и аспирантов «Идеи молодых - новой России» (Тула, ТулГУ, 2004) 5 IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, ТПУ, 2006) 6 Международная научно-методическая конференция «Информатизация образования - 2006» (Тула, 2006) 7 Всероссийская научная конференция молодых ученых «Наука Технологии Инновации» (Новосибирск, НГТУ, 2006) 8 IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке Решения в условиях неопределенности» (Пенза, 2006) 9 I молодежная научно-практическая конференция Тульского государственного университета «Молодежные инновации» (Тула, ТулГУ, 2006)

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

работ

Структура и объем диссертации Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 142 страницах машино-

писного текста, содержит 54 рисунка, ]0 таблиц, список использованной литературы из 96 наименований и приложение

Краткое содержание работы

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

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

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

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

Класс 1 С детерминированными временными характеристиками отдельных блоков

Класс 2 Со случайными временными характеристиками отдельных блоков (при условии взаимной независимости случайных величин)

Класс 3 Со случайными временными характерисгиками отдечьных блоков (без наложения условий взаимной независимости случайных величин)

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

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

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

Во втором разделе построена модель параллельного вычислительного процесса, позволяющая анализировать алгоритмы линейной, разветвляющейся и циклической структур В качестве исходных данных, отражающих логическую и информационную структуру алгоритма, предлагается применить ори-ешированный граф G=(V, Е), вершинам которого соответствуют операторы алгоритма, а дуги обозначают последовательность передачи управления от одного оператора к другому Для задания информационной структуры графа также используется ориентированный граф H(V,A), который называется информационным графом алгоритма, множество вершин которого совпадает с множеством вершин графа алгоритма G, а множество дуг отражает информационную зависимость соответствующих операторов алгоритма

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

(г г г \

Ьп Sin

Ъ п2 ЬппУ

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

Показано, что множество матриц возможных значений

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

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

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

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

щ

о о

8 а

» з /

Ел'

5 «

3 2

4 }г

Ациклическое измерение

Циклическое измерение

Рис 1 Пример представления структуры алгоритма в виде решетчатого графа

При этом предлагается ввести два типа координат ациклическое измерение — номер ¡ь блока алгоритма, соответствующий вершине о„ определяемый сквозной щмерацией блоков алгоритма, и циклическое измерение - элемент Jk, вектора Уп который представляет собой значение переменной цикла, включающего блок, соответствующий вершине и1 Таким образом, вершине о, ставится в соответствие вектор индексов

1/.Л,. Л/Г-

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

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

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

последовательность 3* векторов индексов операций, входящих в состав сегмента 5

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

- нижняя граница изменения переменной цикла у,"5, (7 5) - верхняя граница изменения переменной цикла у/, //(.75) - модификатор переменной цикла В данном случае последовательность 11 формируется в процессе выполнения цикла 2 Аналитическая форма, в соответствии с которой последовательность выполнения вычислительных операций определяется рекуррентной функцией 31 = р5 а также вектором индексов 3* начальной операции и числом операций в сегменте Данная форма записи применима при реализации вычислительной системы на основе жесткой логики 3 Эмпирическая форма, при которой последовательность 3* задается в явном виде Данная форма применима для систем, не имеющих ограничений на память программ

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

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

Ег = Ет о Е1 ^ Еа

Дуги из множества Ер названы программными дугами и отражают последовательность выполнения операций внутри сегментов Дуги из множества Е, названы информационными дугами и отражают информационную зависимость , между связываемыми ими сегментами, реализованньши на различных исполнительных устройствах Дуги из множества!^ названы аппаратными дугами и отражают аппаратную зависимость между связываемыми ими сегментами Аппаратные дуги связывают сегменты, выполняемые на одном исполнительном устройстве в заданном порядке Отмечено, что если граф й является случайным, то и граф Г также является случайным графом

Получена общая методика вычисления функции распределения времени выполнения алгоритма при условии, что время выполнения операторов является многомерной случайной величиной, Т =(ТХ,Т2, ,Тп), которая имеет функцию распределения

Л) = С^<^</2, ,Ги</„),

или задана рядом распределения

(ТиТ2, ,ГЯ)=('1Л ^

Р{Тг=гЬ1 Тп=Чи}\

Данная методика основана на определении множества {Г„,} реализаций случайного графа Г, для каждой из которых определяется множество путей И^ ={т]1,7]2, ?/н(1,Г)}, после чего вычисляется функция распределения времени

выполнения алгоритма для каждой из реализаций Г„,

РгМ(1) = Р тах| Л)

(_ к и®?* ) )

где 0(г) - множество картежей значений ,'„), для которых выполняется

шах-! 2 гЛ < Г Переход от функции распределения ¥ ^ (г) к ряду распределе-

к I - -I " " "

ния Р(Т£ где г,"-возможные значения случайной величины дает

следующий результат

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

1 Среднее время выполнения алгоритма ?а,ег Данный критерий является важным в том случае, когда алгоритм выполняется асинхронно с данными

2 Максимальное значение времени выполнения алгоритма /тах (а2д) Данный критерий находится в зависимости от заданного значения ссзд - вероятности того, что время выполнения алгоритма превысит заданное значение ?тах(ам) Критерий является применимым в том случае, когда алгоритм выполняется синхронно с данными, то есть данные поступают с определенной частотой^

3 Вероятность ошибки а(/т.,Хад) Данный критерий находится в зависимости от заданного значения /п1Мзд Является обратным к предыдущему критерию и, соответственно, применяется при таких же условиях Характеризует надежность вычислительной системы, выражая вероятность того, что отсчет не будет обработан за заданное время

4 Необходимое число процессоров А' Данный критерий отличается от трех предыдущих тем, что имеет целочисленный характер (является натуральным числом)

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

Г* = агдтт^Г)

при учете поставленных ограничений на значение прочих критериев

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

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

Разработана методика разбиения индексного пространства решетчатого графа алгоритма на отдельные сегменты с целью объединения вершин графа, составляющих сегмент, в одну вершину Для этого на предварительном этапе группировки необходимо произвести нумерацию вершин графа, при которой каждой вершине о, е V ставится в соответствие номер по следующему правилу если из вершины о, не существует пути в вершину о,, то м>(ь}), при этом общее число элементов множества различных номеров должно быть минимально возможным На основе указанной нумерации для каждой вершины определяются следующие параметры правое сопровождение А~(г>,) вершины о, - сумма весов вершин с номерами, большими, чем и левое сопровождение А~(и,) вершины V, - сумма весов вершин с номерами, меньшими, чем Кроме того, введены понятия значимости вершины и обратной значимости вершины Значимостью вершины о, называется сумма весов элементов ее транзитивного замыкания Обратной значимостью вершины о, называется сумма весов элементов ее обратного транзитивного замыкания

В работе приводятся условия, на основе которых производится группировка операций Отмечается, что вершины о, и vJ следует относить к различным группам (сегментам), если данным вершинам соответствуют существенно различные значения хотя бы одного из параметров А/Г, Приведен алгоритм, по котором} множество вершин графа дробится на отдельные сегменты

Разработана методика распараллеливания алгоритма на N вычислителей, основанная на дифференцированном подходе к распараллеливанию алгоритма Указанный подход предполагает, что для определения времени выполнения алгоритма не нужно устанавливать, на каком именно вычислителе выполняется очередной оператор Достаточно выяснить, какие из операторов выполняются на одном и том же вычислителе, а какие - на разных вычислителях, и определить порядок выполнения операторов, назначенных одному вычислителю Как показано во втором разделе, граф Г отражает структуру вычислительного процесса следующим образом (рис 2) если аппаратная дуга гк = (и„ присутствует в графе, то операторы и, и и, будут выполнены на одном вычислителе в порядке, указываемом направлением дуги, если дуга п удалена из графа, то операторы V, и V, будут выполнены на разных вычислителях

Рис. 2. Распараллеливание вычислительного алгоритма

Для более четкой формализации методики распараллеливания, основанной на приведенном принципе, введено понятие ордер. Ордер - числовой индикатор, определяемый для аппаратных дуг графа вычислительного процесса и предписывающий порядок выполнения вершин, соединяемых соответствующей дугой. Каждой аппаратной дуге п, - (о;, щ ставится в соответствие ордер 1% который может принимать одно из трех значений {1; 0; -1}. Каждому ордеру задается начальное значение, равное 1. Значения ордера ¡\ имеют следующий смысл:

1,еслигк имеет прямое направлен®, 1к =• -1, еслиг* имеет обратное направлена О, если гу отсутствует. Показано, что задача распараллеливания будет заключаться в нахождении такой комбинации /* ордеров, при которой критерий качества проектируемой системы будет наилучшим',

Т' = а^тт^СО.

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

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

t = max J У-'-i-,Г 1,

\t?min{Ar,w,4-l} "J

где n - число операторов алгоритма, Tcr - критический путь информационного графа алгоритма, v, - время выполнения оператора «„ w, - количество операторов, которые могли бы быть выполнены параллельно с оператором v, Использование данной прогрессивной оценки позволяет существенно сократить количество проверяемых вариантов распараллеливания

Предложена методика распараллеливания линейных алгоритмов с детерминированным временем выполнения операторов, основанная на решении задачи целочисленного линейного программирования Согласно данной методике каждой дате графа процессов ек = (о,, и;) ставится в соответствие вес ук, численно равный интервалу времени между началом выполнения операции У/ и операции ц Вес информационной дуги может быть только положительным, в то время как вес аппаратной дуги может иметь любой знак Отрицательный вес аппаратной дуги означает, что дуга имеет обратное направление Значения ордера 1к преобразуются к двум целочисленным переменным /к и рк как показано в таблице

Таблица 1

№ Значение^ Значение ордера Д Значение /к Значение рк

1 У'к >', 1 1 0

2 yk<-tj -1 0 1

3 -*j <Ук <t, 0 0 0

Сформулированная задача ЦЛП минимизирует функцию

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

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

Рис. 3. Структурная схема экспериментального стенда и измерительного

монитора

Экспериментальный стенд состоит из исследуемого микропроцессора, необходимых модулей памяти и дополнительного внешнего регистра идентификатора операции OIR, в качестве которого может выступать один из портов ввода-вывода микропроцессора, В конце каждой операции в регистр идентификатора операции выдается числовой идентификатор данной операции. Логический анализатор (LA), представляет собой связующее звено между исследуемой микропроцессорной системой и персональным компьютером. Логический анализатор содержит в своем составе тактовый генератор GEN, счетчик тактов CTR, компаратор СМР, буфер данных BUF.

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

KZ^dPAK =^Qtog2 TjBJ+}ogi лй1[)>

1 roin ^ÍÍVSTL rmin

где rraiI1 - нижняя предварительная оценка времени выполнения самой короткой операции, выраженная в тактах, rmax - время выполнения самой длинной операции, выраженное в тактах, N&, - количество операций, на которые дробится исследуемый алгоритм, Fose ~ тактовая частота исследуемого процессора.

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

ритм, производится замена стандартных типов данных, типами, обладающими возможностью мониторинга чтения или записи в ячейку памяти Для каждого объекта й еБ (где В - множество информационных объектов) задается множество *Р(0) итераций, на которых осуществляется запись данных в объект ¡1 На каждой итерации / цикла выполняются следующие действия

1 Рассматривается множество К={К\, Яг, , Як, , Ллвд)} объектов, из которых производится чтение

2 Рассматривается множество , Ждю) объектов, в которые на данной итерации производится запись Для каждого объекта 1¥теЦ7 устанавливается, что запись произведена из данной итерации, то есть во множество ^(Ду добавляется элемент I

3 По формуле

К(И)

Феутся,)

м

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

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

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

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

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

- осуществлять определение временных параметров алгоритма на экспериментальном стенде,

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

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

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

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

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

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

Основные результаты

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

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

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

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

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

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

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

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

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

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

10 Прикладные результаты работы внедрены в ООО «Научно-производственная фирма ОВЕН-К» (г Москва), компании «Трейд-М» (г Тула) Теоретические результаты работы внедрены в учебном курсе «Проектирование процессоров для цифровой обработки сигналов», а также в дипломном проектировании бакалавров и инженеров по специальности «Вычислительные машины, комплексы, системы и сети»

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

1 Данилкин Ф А, Новиков А В Целочисленное линейное программирование в задаче планирования параллельных вычислительных процес-сов//Известия Тульского государственного университета Вычислительная техника Информационные технологии Системы управления Выпуск 1 Вычислительная техника - Тула ТулГУ , 2005 - С 75-82

2 Новиков А В , Сычугов А А Оценка максимального времени выполнения алгоритма с заданной вероятностью ошибки// Известия Тульского государственного университета Вычислительная техника Информационные технологии Системы управления Том I Выпуск 2 Вычислительная техника-Тула ТулГУ, 2003 -С 127-132

3 Данилкин ФА, Новиков AB, Сычугов А А Задача построения диспетчера параллельного выполнения многомерного цикла в многопроцессорной системе // Известия Тульского государственного университета Серия Вычислительная техника Информационные технологии Системы управления Выпуск 1 Вычислительная техника Тула Изд-во Тулье гос ун-та, 2006 - С 310

4 Сычугов А А , Новиков А В Оценка времени ожидания освобождения канала передачи данных в многопроцессорных системах//Известия Тульского государственного университета Вычислительная техника Информационные технологии Системы управления Том 1 Выпуск 3 Вычислительная техника-Тула ТулГУ, 2004 -С 155-161 j

5 Данилкин Ф А , Сычугов А А, Новиков А В Расчет характеристик канала передачи данных на основе графово-множественного подхода/ЛТзвестия Тульского государственного университета Вычислительная техника Автоматика Управление Том 4 Выпуск 1 Вычислительная техника - Тула ТулГУ , 2002 - С 80-88

6 Данилкин Ф А , Новиков А В Алгоритм оценки быстродействия многопроцессорных систем распознавания образов//Интеллектуальные и информационные системы Материалы межрегиональной научно-технической конференции / Тульский государственный университет - Тула, 2003 - С 5253

7 Соколов В А, Новиков А В , Козлов Д Б , Данилкин Ф А Медианная фильтрация в системе цветного микрофильмирования// Известия Тульского

государственного университета Вычислительная техника Автоматика Управление Том 4 Выпуск 1 Вычислительная техника - Тула ТулГУ , 2002 - С 205-209

8 Данилкин Ф А , Новиков А В Задача построения лабораторных систем анализа алгоритмов для микропроцессорных систем // Информатизация образования — 2006 Материалы Международной научно-методической конференции В 3 томах - Тула Изд-во Тульского государственного педагогического университета им Л H Толстого, 2006 - ТЗ -С 212-219

9 Данилкин Ф А, Новиков А В Получение исходных данных для проектирования высокопроизводительных вычислительных сис-тем//Интеллектуальные и информационные системы Материалы межрегиональной научно-технической конференции / Тульский государственный университет - Тула, 2004 - С 70-72

10 Данилкин Ф А, Новиков А В Построение информационного графа циклического алгоритма//Интеллектуальные и информационные системы Материалы межрегиональной научно-технической конференции / Тульский государственный университет -Тула, 2005 - С 31-33

11 Новиков А В Применение кластерного анализа при распараллеливании алгоритмов для многопроцессорных систем//Искусственный интеллект в XXI веке решения в условиях неопределенности Сборник статей IV Международной научно-технической конференции -Пенза, 2006 - С 189-192

12 Новиков AB Группировка операций в задачах распараллеливания вычислительных алгоритмов// Наука Технологии Инновации Материалы всероссийской научной конференции молодых ученых в 7-ми частях Новосибирск Изд-во НГТУ, 2006 Часть 2 - С 86-88

13 Новиков AB Моделирование вычислительных систем на основе графовой.структуры алгоритмов//ХХУИ "Гагаринские чтения" Тез докл Международной молодежной научной конференции - M МАТИ, 2002 Т 5 - С 5455

14 Новиков AB, Сычугов А А Функция распределения случайных чисел в задачах моделирования//Новые информационные технологии в научных исследованиях и в образовании Тез докл 7-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов - Рязань РГРТА, 2002 - С 7-8

15 Новиков А В Разработка базы окончаний для шашечной програм-мы//ХХ1Х "Гагаринские чтения" Тез докл Международной молодежной научной конференции - M МАТИ, 2003 Т5 -С 52

16 Новиков AB, Сычугов А А Расчет производительности процессорных модулей, подключенных к общей системной шине//1-я Всероссийская научно-техническая конференция студентов и аспирантов «Идеи молодых - новой России» [Электронный ресурс] Тезисы докладов - Электрон дан и ирогр -Тула ТулГУ, 2004 - 1 электрон оптич диск(CD-R), 12 см Систем требования IBM PC, Windows 95 (OSR) — загл с этикетки диска - Регистрационное свидетельство № 3928 от 18 03 04 № гос регистрации 0320400297

17 Новиков AB Оптимальное распределение задач между модулями многопроцессорной системы//ХХХ "Гагаринские чтения" Тез докл Международной молодежной научной конференции - М МАТИ, 2004 Т 5 - С 46-47

18 Новиков А В Метод «ветвей и границ» в задаче планирования параллельных вычислительных процессов//ХХХ1 "Гагаринские чтения" Тез докл Международной молодежной научной конференции - М МАТИ , 2005 Т4 - С 22-23

19 Новиков А В , Данилкин Ф А Исследование параллелизма в программах на языке высокого уровня/Молодежь и современные информационные технологии сборник трудов IV Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых Томск, 28 февраля - 2 марта 2006 г - Томск Изд-во ТПУ, 2006 - С 391-393

20 Новиков А В , Сычугов А В Модель диспетчера параллельного выполнения многомерных циклов в мультипроцессорной сети//ХХХП "Гагаринские чтения" Тез докл Международной молодежной научной конференции в 8 томах Москва, 4-8 апреля2006г-М МАТИ,2006 Т4 -С 27-29

л

Изд лиц ЛР № 020300 от 12 02 97 Подписано в печать 13 04 07 Формат бумаги 60x84 1/16 Бумага офсетная Уел -печ л Уч -изд л

Тираж экз Заказ ОС С.

Тульский государственный университет 300600, г Тула, пр Ленина, 92 Отпечатано в издательстве ТулГУ 300600, г Тула, ул Болдина, 151

ВВЕДЕНИЕ.

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

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

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

1.3. Анализ и синтез параллельного программного обеспечения. Преимущества графового метода и метода «ветвей и границ».

1.4. Выводы.

2. МОДЕЛЬ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА.

2.1. Представление вычислительного алгоритма в виде решетчатого орграфа.

2.2. Модель параллельного вычислительного процесса.

2.3. Определение временных характеристик исследуемого алгоритма

2.4. Формализация оптимизационных критериев.

2.5. Выводы.

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

3.1. Сегментация алгоритма.

3.2. Распараллеливание алгоритма на основе системы ордеров.

3.3. Распараллеливание линейных алгоритмов на основе целочисленного линейного программирования.

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

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

3.6. Выводы.

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

4.1. Программный комплекс для автоматического распараллеливания алгоритмов.

4.2. Пример синтеза программного обеспечения спецвычислителя

4.3. Исследование точности полученных результатов и проведение практического эксперимента.

4.4. Исследование времени поиска оптимального решения.

4.5. Исследование эффективности распараллеливания при использовании разработанного подхода.

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

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

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

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

Эффективность параллельной обработки существенно зависит от правильности распараллеливания операций между исполнительными устройствами [7, 10, 11, 41]. Основное противоречие, которое должно быть преодолено в процессе решения задачи распараллеливания, заключается в том, что, с одной стороны, к разрабатываемой вычислительной системе предъявляются требования повышенного быстродействия, с другой - ставятся жесткие ограничения на объем используемых аппаратных ресурсов. Разрешение данного противоречия представляет собой сложную оптимизационную задачу большой размерности [7,10,31].

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

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

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

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

1. Формализация модели параллельных вычислений.

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

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

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

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

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Прикладные результаты диссертационной работы были внедрены: 1) ООО «Научно-производственная фирма ОВЕН-К», г. Москва. 2) компания «Трейд-М», г. Тула.

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

Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2002, 2003, 2004, 2005, 2006 гг.) 2. Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, Тул-ГУ, 2003, 2004, 2005). 3. 7-я всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2002). 4. 1-я Всероссийская научно-техническая конференция студентов и аспирантов «Идеи молодых - новой России» (Тула, ТулГУ, 2004). 5. IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, ТПУ, 2006). 6. Международная научно-методическая конференция «Информатизация образования - 2006» (Тула, 2006). 7. Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, НГТУ, 2006). 8. IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности» (Пенза, 2006). 9. I молодежная научно-практическая конференция Тульского государственного университета «Молодежные инновации» (Тула, ТулГУ, 2006).

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

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

3.6. Выводы

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

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

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

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

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

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

4.1. Программный комплекс для автоматического распараллеливания алгоритмов

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

Разработанный программный комплекс позволяет:

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

- осуществлять определение временных параметров алгоритма на экспериментальном стенде;

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

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

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

Файл Обработка

Прием данных

Идвкп*и*0х12

I данных

Рис. 4.1. Модуль визуального синтеза структуры алгоритма (главное окно и окно инспектора объектов)

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

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

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

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

Ограничена на время Число процессоров ииш

Канал обмена Вр 1°" | Время передав 1 пакета

И ' Г Период 110000

Построить программу

- л.

Процессор 0 } Проце

Этап 1 Б04

Этап 2.Б02 Этап 2. БОЗ Этап 2. Б04 Этап 3, БОЗ Этап 3, Б04 Конец ООСООСЮ120112010020Ш2112222220322 = 1

Прием данных Этап 2, Б01 Этап1,Б02 Этап 2.Б02 Этап 1. Б01 Этап 1. БОЗ Этап 2, БОЗ Этап 2.Б04 Ятлп 1 РП4

1531 Время. мс:5551 »

Рис. 4.2. Окно модуля синтеза параллельной программы

Модуль измерительного монитора .(рис. 4.3) предназначен для испытания алгоритма функционирования системы на экспериментальном стенде. Связь с экспериментальным стендом осуществляется через ЬРТ-порт компьютера.

Программа сбора данных

Запуск

Стоп j

Число тактов ;1185000 Число записей 10 Сохранить

Отладка.

Импульс

Переключать О

Рис. 4.3. Главное окно модуля измерительного монитора

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

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

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

Для создания классов, реализующих указанные типы, используется механизм шаблонов, предоставляемый языком С++. Шаблон класса CDataObject<T> используется для замены типа Т переменных, хранящих обрабатываемые данные. Шаблон класса CIndexObject<T> используется для замены типа Т переменных, хранящих переменные цикла.

Для упрощения внесения построенных типов в текст программы, задаются следующие символические имена: typedef CDataObject<int> Datalnt; typedef CIndexObject<int> Indexint; Кроме того в данном модуле содержится описание класса CAnalizer. Данный класс используется для создания объекта Analizer, который осуществляет сбор статистики о чтении/записи данных в ячейки памяти и строит информационный граф.

В качестве примера рассмотрим вычисление одномерной свертки. Математически она выражается следующим образом y[i] = Nth[j]x[i-j],i = 0.N + M-2.

J=О

Программное представление на языке Си одного из возможных алгоритмов ее вычисления для случая N=M=3, реализованного на основе цикла с параметром, имеет следующий вид: double х[3], h[3], у[3] ; int i, j; for(i = 0; i<3; i++) for(j=0; j<3; j++) y[i+j] = у[i+j] + x[i]h[j]; Для построения информационного графа данного алгоритма, необходимо преобразовать программу к следующему виду: создать экземпляр объекта анализатора CAnalizer * Analizer = new CAnalizer; // объявить переменные-данные CDataDouble х[3], h[3], у[3]; // объявить переменные цикла CIndexInt i, j; // выполнить алгоритм for(i = 0; i<3; i++) for(j=0; j<3; j++) y[i+j] = у[i+j] + x[i]h[j]; удалить объект-анализатор delete Analizer;

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

Для преобразования полученных данных о структуре алгоритма к требуемому формату используется метод WriteDataGraph() объекта Analizer. Данный метод вызывается в деструкторе класса CAnalizer реализует вывод в файл данных, которые формируются в результате работы программы. В результате будет получен текстовый файл со следующим содержимым: <gxl> graph id="graphl"> node id="nodel" vars= 4=0;j =0"/> node id="node2" vars= 4=0; j =l"/> node id="node3" vars= 'i=0;j =2"/> node id="node4" vars= 'i=l;j =0M/> cnode id="node5" vars= 4=1; j =l"/> node id="node6" vars= 4=1; j =2"/> cnode id="node7" vars= 4=2; j =0"/> cnode id="node8" vars= 4=2; j =l"/> cnode id="node9" vars= 4=2; j =2"/>

Cedge from="node4 " to= 'node8 " id=" edgel cedge from="nodel " to= 'node5 " id=" edge2 cedge from="node5 " to= 'node9 " id=" edge3 cedge from="node2 " to= 'node6 " id=" edge4 graph> </gxl>

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

4.2. Пример синтеза программного обеспечения спецвычислителя

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

Формат входных данных - 16 битное'целое. Входные данные представляют собой равномерно распределенную случайную величину.

Схема выполнения 8-точечного БПФ с прореживанием по частоте [28] представлена на рис. 4.4. т *0) *(2) *(3)

5) *(7)

J V.

J К J

ДО) Д4) Д2) т

Д1) Д5) ДЗ) Х{1)

Этап 1

Этап 2

Этап 3

Рис. 4.4. Схема выполнения 8-точечного БПФ с прореживанием по частоте

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

Данный алгоритм может быть записан в виде программы на языке Си следующим образом: объявление констант const int k[3][4]={{0,1,2,3},{0,1,4,5},{0,2,4,6}}; const int m[3] [4] = { {4,5,6,7}, {2',3,6,7}, {1,3,5,7}}; const int 1[3] [4] = {{0,1,2,3}, {0,2,0,2}, {0,0,0,0}}; объявление массивов и переменных int datare[8], dataim[8], i, j;

GetlnputData(); // Получить массив входных данных for(i=0; i<3; i++) for(j=0; j<4; j++)

BaseOper(k[i][j],m[i][j],1[i][j]); // базовая операция if(windowenabled) // Если включен режим обработки окном

WindowO; // выполнить оконное преобразование

WriteOutputData() ; // Выдать рассчитанные данные В данном фрагменте программы функция BaseOper(k, m, 1) осуществляет выполнения базовой операции БПФ над элементами к и ш массивов входных данных data re и dataim. Функция Window выполняет оконное преобразование выходного спектра и запускается при выставленном значении флага windowenabled.

Требуемый алгоритм будет включать 15 вычислительных операторов.

ЗАКЛЮЧЕИИЕ

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

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

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

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

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

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

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

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

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

10. Прикладные результаты работы внедрены в ООО «Научно-производственная фирма ОВЕН-К» (г. Москва), компании «Трейд-М» (г. Тула). Теоретические результаты работы внедрены в учебном курсе «Проектирование процессоров для цифровой обработки сигналов», а также в дипломном проектировании бакалавров и инженеров по специальности «Вычислительные машины, комплексы, системы и сети».

1. Алексеев О.Г., Комплексное применение методов дискретной оптимизации.-М.: Наука, 1987.-316 с.

2. Анализ производительности ЭВМ: Учеб. пособие / В.М. Игнатьев, Е.В. Ларкин; Тул. гос. техн. ун-т. Тула, 1994. 104 с.

3. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. - 192 е., ил.

4. Берж X. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.-319 с.

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.:Мир, 1989. - 448 с.

6. Брахман Т.Р. Многокритериалность и выбор альтернативы в технике. М.: Радио и связь, 1984. - 288 с.

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

8. Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2-е изд., стер. - М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 208 с. -(Пробл. науки и техн. прогресса).

9. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука. Гл. ред. физ.-мат. лит. - 1988. -480 с.

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

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

12. Глушков В.М, Капитонова Ю.В., Летичевский A.A. Автоматическое проектирование вычислительных машин. Киев., 1978. -230 с.

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

14. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М. Радио и связь, 1983. - 272 с.

15. Горбунов B.J1., Панфилов Д.И., Преснухин Д.Л. Справочное пособие по микропроцессорам и микро-ЭВМ:/Под. Ред. Л.Н. Преснухина. М.: Высш. шк., 1988.-272 е.: ил.

16. Данилкин Ф.А., Новиков A.B. Построение информационного графа циклического алгоритма//Интеллектуальные и информационные системы: Материалы межрегиональной научно-технической конференции / Тульский государственный университет. Тула, 2005. - стр. 31-33.

17. Джордейн Р. Справочник программиста персональных компьютеров типа IBM РС,ХТ и AT: Пер. с англ. М: Финансы и статистика, 1992. - 544 с.

18. Долинский М., Толкачев А., Коршунов И. Программный комплекс для разработки параллельных вычислительных систем//Компоненты и технологии, 2004, №5, с. 94-100.

19. Евреинов Э.В. Однородные универсальные вычислительные системы высокой производительности. Новосибирск, Наука, 1966. -306 с.

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

21. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. 1990. 384 с.

22. Ильин A.A., Титов B.C., Евсюков Е.В. Быстрые алгоритмы цифровой обработки сигналов: Учебное пособие. Тула: Тульский государственный университет, 2003. - 125 с.

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

24. Карцев М.А. Архитектура цифровых вычислительных машин. М.: Наука, 1978.-295 с.

25. Касьянов В.Н. Методы оптимизации программ. Новосибирск: НГУ. 1984. 92 с.

26. Коваленко H.H., Филиппова A.A. Теория вероятностей и математическая статистика: Учеб. пособие. 2-е изд., перераб. И доп. - М.: Высш. Школа, 1982.-256 е., ил.

27. Колемаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: Учебник/ Под ред. В.А. Колемаева. М.: ИНФРА-М, 2001. -302 с. - (Серия «Высшее образование»).

28. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985. - 167 с.

29. Корячко В.П. Микропроцессоры и микроЭВМ в радиоэлектронных средствах: Учеб. для вузов по спец. «Конструирование и технология радиоэлектронных средств». М.: Высш. шк., 1990. - 407 е., ил.

30. Кофман А. Введение в прикладную комбинаторику. М.: Наука. Гл. ред. физ.-мат. лит., 1975. -480 е., ил.

31. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование. Пер. с франц. Б.Т. Вавилова, Е.В. Бабичевой, Г.Г. Устинченко. М.: Мир, 1977.-432 с.

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

33. Левкин Г.Н., Левкина В.Е. Введение в схемотехнику ПЭВМ PC/AT. М.: Изд-во МПИ, 1991. - 96 е.: ил.

34. Литвин В.Г., Ададышев В.П., Винниченко А.И. Анализ производительности мультипрограммных ЭВМ. М.: Финансы и статистика, 1984. -159 е., ил.

35. Лорин Г. Распределенные вычислительные системы. М.: Радио игсвязь, 1984. -296 с.

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

37. Марков А.А, Нагорный Н.М. Теория алгоритмов. М.: Наука, 1984. -432 с.

38. Микропроцессорный комплект К1810: структура, программирование, применение. Справочная книга/ Ю.М. Казаринов, В.Н. Номоконов, Г.С. Подклетнов, Ф.В. Филиппов/. М.: Высшая школа, 1990. - 269 с.

39. Мультипроцессорные вычислительные системы/ Под. Ред. Я. А. Хетагурова. М.: Энергия, 1971. - 320 с.

40. Мультипроцессорные системы и параллельные вычисления/ Под. Ред. Ф.Г. Энслоу. М.: Мир, 1976. - 384 с.

41. Новиков A.B. Группировка операций в задачах распараллеливания вычислительных алгоритмов// Наука. Технологии. Инновации. Материалы всероссийской научонй конференции молодых ученых в 7-ми частях. Новосибирск: Изд-во НГТУ, 2006. Часть 2. с. 86-88.

42. Новиков A.B. Метод «ветвей и границ» в задаче планирования параллельных вычислительных процессов//ХХХ1 "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: MATH., 2004. Т.4., стр. 22-23.

43. Новиков A.B. Моделирование вычислительных систем на основе графовой структуры алгоритмов//ХХУИ "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: MATH., 2002. Т.5. Стр. 54-55.

44. Новиков A.B. Оптимальное распределение задач между модулями многопроцессорной системы//ХХХ Тагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: МАТИ., 2004. Т.5. Стр. 46-47.

45. Новиков A.B. Разработка базы окончаний для шашечной програм-мы//ХХ1Х "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: МАТИ., 2003. Т.5. Стр. 52.

46. Новикова Н.М. Основы оптимизации (курс лекций). Электронный ресурс. Электрон, дан. - М.: МГУ, 1998. Режим доступа: http://www.ccas.ru/depart/malashen/papper/oonovikl .pdf, свободный. Требования: Adobe Acrobat Reader 3.0 или выше. - Заглавие с экрана.

47. Однородные микроэлектронные ассоциативные процессоры / Под. Ред. И.В. Прангишвили. М. Советское радио, 1973. - 280 с.

48. Панюков A.B. Линейное программирование: Конспект лекций. -Челябинск: Издательство ЮУрГУ, 2001. 59 с.

49. Пашкеев С.Д. Основы мультипрограммирования для специализированных систем. М.: Советское радио, 1972,183 с.

50. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. -367 стр.

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

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

53. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. М.: «Сов. радио», 1976. 344 е., ил.

54. Розен B.B. Цель, оптимальность, решение. Математические модели принятия оптимальных решений. М.: Радио и связь, 1982. 168 стр.

55. Рыбников К.А. Введение в комбинаторный анализ. М.: Издательство Московского университета, 1972. -256 с.

56. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычислительных систем / Под ред. О.И. Авена. М.: Наука, 1991. - 256 с.

57. Скэнлон J1. Персональные ЭВМ IBM PC и ХТ. Программирование на языке ассемблера. М.: Радио и связь. 1989. - 336 с.

58. Страуструп Б. Язык программирования С++. СПб.: БХВ-Петербург, 2001 - 863с.

59. Фет Я.И. Параллельные процессоры для управляющих систем. М. Энергоиздат, 1981. - 158 с.

60. Теория систем и методы системного анализа в управлении и связи/В.Н. Волкова, В.А. Воронков, A.A. Денисов и др. М.: Радио и связь, 1983.-248 с.

61. Толковый словарь по вычислительным системам/Под ред. В. Иллин-гуорта и др.: Пер. с англ. А.К. Белоцкого и др.; Под ред. Е.К. Масловского. -М.: Машиностроение, 1991. 560 е.: ил.

62. Транспьютеры. Архитектура и программное обеспечение. Под ред. Г.Хорна. М. Радио и связь 1993г. 304 с.

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

64. Ушкар М.Н. Микропроцессорные устройства в радиоэлектронной аппаратуре/Под ред. Б.Ф. Высоцкого. М.: Радио и связь, 1988. - 128 е.: ил. -(Массовая б-ка инженера «Электроника»).

65. Фор А. Восприятие и распознавание образов. М: Машиностроение, 1989 г. - 272 е.: ил.

66. Фостер К. Ассоциативные параллельные процессоры. М.: Энерго-издат, 1981.-240 с.

67. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

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

69. Цифровая и вычислительная техника: Учебник для вузов/Э.В. Ев-реинов, Ю.Т. Бутыльский, И.А. Мамзелев и др.; Под. ред. Э.В. Евреинова. -М.: Радио и связь, 1991.-464 е.: ил.

70. Шеннон Р. Имитационное моделирование систем искусство и наука. / Пер. с англ. под ред. Е.К. Масловского. М.: «Мир», 1978. - 418 с.

71. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие. Мн.: Белгосуниверситет, 1996. - 296 е.: ил.

72. Шрайбер Т. Моделирование на ОРББ. М.: Машиностроение, 1990.

73. Электронные промышленные устройства: Учеб. для студ. Вузов спец. «Пром. электрон.»/В.И. Васильев, Ю.М. Гусев, В.Н. Миронов и др. -М.: Высш. Шк., 1988. 303 е.: ил.

74. Элементы параллельного программирования/В.А. Вальковский, В.Е. Котов, А.Г.Марчук, Н.Н. Миренков. М.: Радио и связь, 1986. - 392 с.

75. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975. 255 с.

76. Языки и параллельные ЭВМ. Москва: Наука. 1990. серия Алгоритмы и алгоритмические языки. 93 с.

77. LPSOLVE: Linear Programming Code. Electronic resource. Electronic data and progr. - [USA]: 1996. Access: http://www.cs.sunysb.edu/~algorith/implement/lpsolve/implement.shtml, free. -Title from screen.

78. Mplab IDE, simulator, editor. User's guide. USA: Microchip Technology Inc., 2001.-272 p.

79. Smith S.W. The Scientist and Engineer's Guide to Digital Signal Processing. San Diego: California Technical Publishing, 1999, - 650 p.