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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

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

РГ6. од

КАЛМЫКОВА Мпина Аркадьевна

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

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

АВТОРЕФЕРА?

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

Минск 1994

Работа выполнена в Белорусском государственном университете информатики и радиоэлектроники. Научный руководитель: кандидат технических наук, доцент

КОРЯЕНЕВИЧ Ю.В. Официальные оппоненты : доктор физико-математических

наук, профессор ВАЛЬКОВСЮШ В. А. кандидат технических наук, доцеит йОБАЙЛО А. С. Ведущая организация: ШИ "Агат" Защита диссертации состоится 19 мая 1994г. в часов на заседании специализированного совета к 05б705.01-пс5 присуждению ученой степени кандидата технических наук при Белорусском государственном университете информатики и радиоэлектроники по адресу: 220027,г.Минск,ул.П.Бровки,6.

С диссертацией можно ознакомиться в библиотеке Белгоо-университета информатики и радиоэлектроники.

Автореферат разослан " 15 " анреЛЯ 1994 г.

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

то совета «их наук

специализированного совета Г)

кандидат технических наук , ^ , Л/ д> п ЩШКЕШЧ

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

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

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

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

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

В настоящее время в области разработки клеточных схем алгоритмов создан серьёзный научный задел. Формальный аппарат для описания клеточных схем и методы анализа корректности синхронных параллельных вычислений рассмотрены в работах С.М. АчасовоЙ, О.Л. Бандман, A.B. Воеводина, ¡O.K. Корнева, С.В.Пискунова и др.; синтез-клеточных алгоритмов для конкретных задач (преимущественно линейной алгебры) - в работах С.Ю.Лысаиова, Н.А.Недашковского, С.Г.Седухина и др.

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

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

Направление работы определено в соответствии с комплексом НИР по республиканским программам "Информатика", и "Информатизация" на 1992-1995 г.г., утвержденным постановлениями Совмина РБ.

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

Поставленная цель определила решение следующих основных задач исследования:

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

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

синтеза орлеса приближенного решения ИР-полной задачи "Многопроцессорное расписание с условиями предшествования" (МРП).

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

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

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

Для подтверждения результатов теоретического исследования применен метод статистического моделирования на ППЭВМ.

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

1. Параллельная процедура пошагового структурного синтеза (ПСС) орлеса приближенного решения задачи МРП.

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

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

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

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

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

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

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

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

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

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

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

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

программ на решающих долях," в составе оптимизирующего

/

транслятора.

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

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

Всесоюзном научно-практическом семинаре "Информатика 90-х " (Минск, 1991);

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

Всероссийской научно-технической конференции " Однородные вычислительные системы, структуры и срэды" (Москва,

1993);

заседании школы-семинара "Анализ и применение систем и сетей массового обслуживания" (Минск, 1994); Научной конференции профессорско-преподавательского состава и сотрудников, посвященной 30-летию БГУИР (Минск,

1994).

Реализация результатов работы. Исследования по теме диссертационной работы выполнен^ в Белгосуниверситете информатики и радиоэлектроники в рамках госбюджетных, НИР "Организация подсистемы параллельного программирования" (ГР-N 01910010162) и "Разработать интеллектуальные системы решения задач структурного синтеза изобретений" (■ ГР N 01920011450).

Предложенные методы й алгоритмы внедрены в научно-исследовательские разработки и практику проектирования параллельного программного обеспечения в. Центре информатики и распределенной обработки данных Международной Академии Информатизации и Белорусском центре информатики БолАК ЮНЕСКО. Результаты исследований включены в материал трех книг. Публикации. Основное, содержание'диссертации, отражено в 9'пе-

чатных работах, в том число 3 книгах и 2 отчетах о НИР. Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на. 174 страницах машинописного текста. Библиография включает 153 наименования. Основной текст содержит 29 рисунков и 7 таблиц.

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

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

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

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

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

ордерева/орлеоа 0/,Е),(V) =п вектором (<р(1 ),<р(2).....

Ф(п)) значений целочисленной функции предшествования Ф ,...,п-11, заданной на множестве номеров вершин

V ^еУ г (-Т7п. Последовательность упорядочения элементов векторного представления и способ однозначного восстановления структуры 1 определяются правильным */спосоОом нумерации

* Динамический подход к анализу структур, описываемых графэ-ми /М.А.Айзерман.Л.А.Гусев, Л.В.Петров и др. Исследования по теории структурой.науч, тр./АН СССР.-М.:Наука, 1980.-С.5-7?.

вершин ярусно-параллельной формы (ЯПФ) Т. Определен порядок сопоставления элементов вектора элементам расширенного множества дуг Е и ((Тф,^)} ордере ва/орле с а Т. Здесь Оо{) -множество корневых вершин Т, - фиктивная вершина, имеющая статус начальной в Т. На основе функции предшествования для представления взвешенных ордеревьев/орлесов сформирована целочисленная «-функция ,2,...,гпхп), где ш - максимальный из натуральных весов вершин древовидной структуры. Высокая экономичность представления у?-функцией по памяти достигается определением совокупности локальных (структурных и весовой) характеристик каждой дуги ордерева/орлеса единственным элементом целочисленного массива значений

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

Разработан метод отображения алгоритмов ПСП Ордеревьев/ орлэсов на схему одномерного клеточного автомата.Полагается, что последовательность шагов преобразования t=TГ,^f' порождает соответствующую последовательность' древовидных структур Т(0)-Т(1)-». ),' не изменяющую п-элементное множество вершин исходной структуры Т(0). В основе предлагаемого метода лежит описание множества последовательно формируемых алгоритмом ордеревьев/орлесов последовательностью целочисленных. векторов .....г* ) ,г=0,г' значений функций предшествования (либо »-функции). Совокупность векторных представлений интерпретируется множеством глобальных

конфигураций одномерного клеточного автомата, определенных в , алфавитах натуральных имен и состояний клеток. .При этом каждому элементу представления .г^.- ставится в соответствие состояние клетки { в дискретный момент времени 1=0,1,...,г'. ' Тогда задача формирования корректной клеточной схемы алгоритма ДСП сводится к определению.векторной• функции переходов автомата ,. удовлетворяющей .соотношению

<г£-х'5Ч-х+1 .....(1 )

V г=Г7Т', чигТп,

и условию завершаемое™ "параллельного вычисления

где константы и у определяют окрестность клетки í, используемую для вычисления ёе состояния .

• Выполнение условия завершаембсти - сходимости алгоритма ПСП к результирующей структуре .1(1; •) - обеспечивается свойством однонаправленности (монотонного невозрастания / неубывания) функции переходов "и принадлежностью области ее значений конечному целочисленному ' диапазону. Разработаны' клеточные описания алгоритмов пошаговой деструктуризации "ордеревьев в виде набора несвязных' вершин.Соответствующие.функции переходов сформированы" на основе суперпозиции функций алгебры логики и арифметических функций над Целочисленным представлением. преобразуемой на текущем шаге древовидной структуры.

Во второй главе рассмотрены вопросы, разработки и исслё-довашя параллельной процедуры ПСС граф-модели решения МР-шлной аадачи о многопроцессорном расписании. Указанная задача решается для случая распределения системы упорядоченных вычислительных работ (А, <•) с единичными временами выполнения в неоднородной МВС на ш спецпроцессорах. Здесь

А=(а1 ,а£.....ап> - множество элементарных задач, подлежащих

выполнению в' МВС; <• - лес отношений частичного порядка На ' множестве А, определяемый : информационно-логическими связями меаду отдельными задачами. Правила закрепления каждой задачи

за единственным спецпроцессором задают вариант .разбиения А на совокупность т непересекающихся подмножеств*

Вход процедуры моделируется корневым выходящим взвешенным орле сом Т =(У,Е), множеству вершин которого сопоставлено множество задач А, а множеству дуг - совокупность отношений порядка. Скалярный вес вершины определяется номером спецпроцессора, закрепленного за соответствующей задачей. Выход процедуры моделируется ЯПФ корневого выходящего орлеса Т', каждая компонента связности которого является орцепыо и определяет выборку расписания для одного процессора.

В процедуре реализован метод- поярусного формирования ЯПФ орлеса расписания на основе пошагового анализа и преобразования ЯПФ исходного орлеса отношений порядка задач. Пусть в дискретный момент времени , Ъ-1 (1: = 1,2,...) сформирована пара корневых выходящих орлесов (г-1),Т2(г-1)1, где Т1(г-1) - орлее отношений порядка на включенных в расписание задач; Т£(1;-1) - подграф орлеса решения, содержащий 1>1 его ■первых ярусов. Полагаем Т?(0)=Т, Т2(О)=0. На текущем шаге I процедуры ПСС . осуществляется структурное преобразование [Т., (1-1 ),?2а-1 )]-(Т1 (г),Т2сг>3. общий результат которого состоит в добавлении очередного яруса У^'к орлесу ?г (г-!) й исключении, из Т1 1) непустого множества дуг, соответствующего учтенным в- Т2(1;) отношениям порядка. Основной-операцией пошагового преобразования является выбор единственной вершины каждого' веса 1,... ,ш в- формируемый ярус расписания У^еТ2([). шагов ь>■ процедуры определяется свойством

сходимости последовательности орлесов (0(1 )->...--Т.,(1;)-... к результирующей структуре Т., (г')=0. Соответственно, орлее Т2(1:' )=Т' определяет приближенное решение -допустимое расписание длины 1'.

Результат структурного • преобразования на шаге г =ТЙ1' однозначно определяется орлесом С(г)=т1 (Ъ) ) с неизменным множеством вершин V. здесь У(0,°У(1;) - операция склеивания орлесов и Т2(Х) по одноименным вершинам ярусов У^е^Ш^и (г).Указанная особенность отличает процедуру ПСС от известных пошаговых схем решения задачи МРП и позволяет применить крупноблочную стратегию распараллеливания процедуры, связав число ее изоморфных ветвей с мощно-

стью |V| =n. При этом функциональное содержание отдельной ветви связано с выбором предшественника соответствующей вершины на каждом шаге преобразования.

Предложены параллельные алгоритмы ПСП [T^t-1), T2(t-1 )]-tT1 (t), T2(t)], реализующие различные стратегии выбора вершин в текущий ярус орлеса расписания ( МАКСИМАЛЬНАЯ СВЯЗНОСТЬ /.МИНИМАЛЬНЫЙ ЯРУС ВЕРШИНЫ , МАКСИМАЛЬНЫЙ УРОВЕНЬ ВЕРШИНЫ ). Существенные особенности алгоритмов ПСП, обеспечивающие , возможность синтеза.клеточного описания процедуры ПСС, состоят в следующем.

1. Способ ПСП определен в терминах операций над элементами расширенного множества дуг орлеса частичного решения (ВКЛЮЧЕНИЕ, УДАЛЕНИЕ, ПЕРЕНОС в формируемую структуру), что определяет ориентацию алгоритмов на представление орле сов w-функцией.

2. Правила выбора способа преобразования дуги эквивалентны по всем ве.тЕЯм алгоритма и основаны на анализе локальных характеристик совокупности дуг преобразуемой на текущем шаге структуры. • К анализируемым характеристикам дуги могут быть отнесены номер яруса/уровня, вес, связность на глубину один, определенные да-инцидентных дуге вершин.

3. Результат ПСП задается синхронной параллельной реализацией всех п ветвей алгоритма.

Параллельная временная сложность алгоритмов ПСП, определенная для n-йроцессорной PRAM-модели параллельного вычислителя, составляет О(п). Время реализации алгоритмов на р-процессорной однородной ВС (реп) возрастает в fn/p"j раз, ■что позволяет отнести алгоритмы к области эффективного распараллеливания. Для вычисления связностей верйин разработана параллельная'процедура сложности 0(п-1).

Предложенная методика оценки асимптотической погрешности процедуры ПСС основана на построении класса индивидуальных задач (I*} оптимального планирования с произвольно большим значением оптимального решения L(I*)~n, для каждой из которых выполняется система условий:

L(I*)=min L(If),

1,бМ

AimaxtL' (I, )-L(I,)), (3)

где M - множество индивидуальных задач, инвариантных задаче IОтносительно нижней границы длины оптимального расписания [Yij/mjl;

(nj.m^) - значения параметров задачи IjsM ; I.'(I{ ) - длина расписания,определяемого выбранной стратегией синтеза ЯПФ орлеса приближенного решения задачи I j; Д*=Ь'(1*)-ВД*).

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

определена как lim L1 (1*)/Ш*), где 1/(1*) и 1(1*) -функции L(I*)->!»

максимального веса вершины т.и числа сегментов каждого типа в орлеса Т*. Получено, что асимптотическая погрешность процедуры ПСС удовлетворяет условию вт < 2 при формировании орлеса приближенного решения по критерию МАКСИМАЛЬНЫЙ УРОВЕНЬ ВЕРШИНЫ и условию 8* < 3/2 при применении комбинированного критерия МАКСИМАЛЬНАЯ СВЯЗНОСТЬ/МИНИМАЛЬНЫЙ ЯРУС ВЕРШИНЫ.

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

Разработана одномерная, клеточная схема процедуры ПСС, предполагающая описание последовательности шагов преобразования орлесов частичных решений G(t-t )-*G(t) . векторной функцией переходов, определенной над л-элемеитнш w-предстэвле-нием орлеса G(t-1) и удовлетворяющей системе соотношений (1-2) при x=t-1, y=n-l. К формированию арифметико-логической функции переходов применен логико-комбинаторный подход. На текущем шаге процедуры ПСС каждой дуге орлеса частичного решения сопоставлено множество г вариантов альтернативного выбора единственного из заданного набора правил преобразования

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

• 9к:(а^-1,0»Рк(П-ЧРкиМ), У1=Т7п, к=ТТБ, (4)

где (г*"1,1) - база подстановки;

Рк(г) - значение контекстного логического предиката,

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

шаге Ч:

....г*-1,... ) - функция целочисленной ари$мвтики, определяющая состояние клетки I в момент времени г (дугу в орлесе С(Ш-

Каждый из логических предикатов представляется вектором свойств подмножеств дуг орлеса С(г-1). В качестве таких

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

ч .

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

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

СНЛ«.*,.»)). (5)

к=1 . К .

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

шагой обеспечивается выполнением системы условий:

Е нка ,

н1 , тг,

если арифметическая функция Р.|(1;) задает тождественное преобразование С (г-1 НС (1).

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

Последовательно решены следующие задачи:

1. формирование стандартной ВК ИС функции переходов в виде Е-разложения;

2. разработка системы операционных шаблонов - базовых ИС, рассматриваемых в качестве сложных аппаратных . операций, каждая из которых реализуется по конвейерному принципу ;

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

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

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

Эффективность- ВК-реализйции вычисления функции переходов оценена. • величинами замедлений. ^ =2,25-8/(8п+20), =6,75-85/(Sn+20), соответственно достигаемых при исключении конвейерного зацепления функциональных устройств и при отказе от использования'векторных-регистров. Сравнение полученных замедлений с максимально возможными ( 3 и 10 соответственно) позволяет считать- разработанный способ отображения f на ВК-архитектуру достаточно, эффективным.

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

Снижение, временной, сложности программы до' ОЦо^п) достигается применением метода сдваивагшя к операциям логической свертки векторных массивов при согласовании размерности массивов с числом элементарных вычислителей решающего поля процессора."

В четвертой главе представлено алгоритмическое и программное обеспечение планирования параллельных вычислений в неоднородной МВС. В состав многоуровневого программного комплексе (ПК) планирования включены:

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

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

ПК реализован для ППЭВМ класса IBM PC/AT, MS-DOS в сис-• теме программирования Turbo С.

В режиме вычислительного эксперимента исследованы ста-' тистическая точность и временная сложность процедуры ПСС орлеса расписания при различных приближенных стратегиях планирования. Последовательности случайных конфигураций системы распределяемых в МВС задач моделируются потоками взвешенных орлесов с заданным числом йершин п и псевдослучайной структурой отношений предшествования. При правильном способе нумерации ярусно-параллельной формы орлеса потока соответствующая функция предшествования задается рекуррентным правилом <p(i)=<p({-1 )+l, Vi=37n, где I - равномерно распределен- . ная величина из целочисленного диапазона [0,...,n-<p(i-1 )); причем (p(i)=0 для { = 1,2. Верхняя граница натурального диапазона равномерно распределенного случайного веса вершины определяется числом m спецпроцессоров МВС. При испытании алгоритмов планирования исследованы потоки случайных орлесов с числом вершин п « 25 и максимальным весом вершины те(2,...,8). Число орлесов в каждом потоке не превышало 80.

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

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

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

в среднем величиной- 0(п/ш). 'Показано, что предложенные клеточные алгоритмы планирования в неоднородной МВС обеспечивают достаточно высокие характеристики точности по сравнению с базовым алгоритмом псевдослучайной генерации допустимого расписания. В частности, для худшего потока орлесов клеточный алгоритм стратегии; МАКСИМАЛЬНАЯ СВЯЗНОСТЬ/МИНИМАЛЬНЫЙ ,ЯР^С ВЕРШИШ обеспечивает точное решение в 95% . случаев, в то время как алгоритм псевдослучайной генерации - лишь в 80%. Порученные с помощью системы случайных тестов максимальные статистические погрешности приближенных решений подтверждают ■достоверность аналитических оценок точности процедуры ГОС расписания,

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

стратегии выбора - вершин .в формируемый на текущем шаге • процедуры ярус орлеса расписания.

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

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

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

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

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

1.Калмыкова И,А..Корженевич Ю.В. И-функция как эффективный способ представления графовых моделей параллельных вычислительных процессов // Информатика 90-х:Тез.докл.и сообщений науч.-практ.семинара,16-20 дек.1991г.-Минск,1991.-С.42-43.

2. Организация подсистемы параллельного программирования: Отчет о НИР/Минск, радиотехн.ин-т; Науч. руководите ль Корженевич Ю.В.; 31,12.91; N ГР 01910010162.-Минск,1991.-256с.

3.Разработать интеллектуальные системы решения задач струк-

турного синтеза изобретений¡Отчет о НИР / Минск.радиотега, ин-т; Науч.руководитель Корженевич 13.В.; 31.12.92; N ГР 01920011450.-Минск,1992.-120с.

4.Калмыкова И.А., Корженевич В.В. Комбинаторные алгоритмы.-Минск:БЦИ БелАК ШЕСК0,1993.-С.1039-Ш4.-(Сер.:Информатика: в 12т.-Т.12)

5.Калмыкова И.А., Корженевич Ю.В. Реализация языков программирования. -Минск:БЦЙ БелАК ЮНЕСКО, 1993.-С.943-1038.-(Сер.: Шформатика :в 12т.-Т. II)

6. Калмыкова И.А., Корженевич Ю.В. Трудаорешавмые задачи.-Минск:БВД БелАК ЮНЕСКО, 1993.-C.III5-II60.-(Сер. .-Информатика: в 12т.-Прил.)

7.Калмыкова И.А.Параллельная процедура структурного синтеза решения задачи "многопроцессорное расписание" // Однородные вычислительные системы.структуры и среды:Тез.докл.VI Всероссийской науч.-техн.конф. ,23-25 нояб.1993г.-М.,1993.-С.24.

8.Калмыкова И.А. Планирование параллельного вычислительного процесса на основе клеточной процедуры преобразования орле-сов // Анализ и применение систем и сетей массового обслуживания :Тез.шк.-семинара,1-5 февр.1994г.-Минск,1994.-С.63-64. Э.Калмыкова И.А. Разработка и исследование клеточных алгоритмов планирования параллельных вычислений в МВС // Тез.докл. науч.конф.,поев.30-летию Белгосуниверситета информатики и радиоэлектроники,15-18 февр.1994г.-Минск,1994.-С.259.

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

КАЛМЫКОВА Ирина Аркадьевна .

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

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

Подписано в печать 25*03.94* Формат 60 ^ 84:/16. Объём 1.0 усл. печ. л. 1.0 уч.-ивд. л. 3ак,.153. Тираж 90 экз. Бесплатно.

Отпечатано на ротапринте БГУИР, 220600 г. Минск, ул. П.Бровки,6