Введение к работе
Актуальность темы. Современная концепция параллельной архитектуры позволяет существенно увеличить производительность многопроцессорных вычислительных систем (МВС) за 'счет совмещения в них двух уровней распараллеливания вычислений : распределения независимых задач, взаимодействующих программных модулей, процедур и т.д. на процессоры ШС; -распределения отдельных инструкций программы между элементами сложного ( векторного, конвейерно-потоковогс и ар. ) решающего ПОЛЯ каждого процессора.
Большинство усилий по разработке параллельных алгоритмов и программ сосредоточено на непосредственном обеспечении параллелизма второго уровня за счет создания системы прикладного программного обеспечения для каждой конкретной архитектуры. Однако, реализация такого подхода связана со значительными затратами вследствие разнообразия типов параллельных ВС и языков параллельного программирования. Альтернативный подход предполагает разработку машинно-независимых алгоритмов и их описаний, достаточно эффективных либо легко трансформируемых . для широкого класса архитектур. При этом максимальная эффективность распараллеливания на каждом уровне может быть достигнута согласованием структуры алгоритма с иерархической моделью параллельного вычисления, образованной объединением нескольких моделей с различкой степенью конкретизации архитектурных возможностей МВС.
Как показал анализ известных моделей параллельных вычислений, в качестве машинно-независимого языка описания синхронных параллельных алгоритмов, обеспечивающего эффективное двухуровневое распараллеливание в однородной ВС, целесообразно использовать математический аппарат клеточных автоматов. При этом каждая из изоморфных параллельных ветвей алгоритма, сопоставляемая с соответствующим процессором ВО, задается векторной функцией локальных переходов клеточного автомата (первый уровень описания). Определение функции переходов в явном аналитическом виде позволяет применить извест-
іше метода структурного анализа векторних математических функций к разработке эффективного отображения алгоритма на конкретную архитектуру процессоров ВС (второго уровня описания).
В настоящее время в области разработки клеточных схем алгоритмов создан серьёзный научный задел. Формальный аппарат для описания клеточных схем и методы анализа корректности синхронных параллельных вычислений рассмотрены в работах СМ. АчасовоЙ, О.Л. Бандман, А.В. Воеводина, Ю.К. Корнева, С.В.Пискунова и др.;синтез- клеточных алгоритмов для конкретных задач (преимущественно линейной алгебры) - в работах С.Ю.Лысаиова, Н.А.Недашковского, С.Г.Седухина и др.
Вместе с-тем проблема разработки эффективных клеточных алгоритмов приближенного решения КР-полішх задач планирования параллельных вычислений в МВС остается мало изученной.
В этой связи рассматриваемые в диссертации вопросы применения векторных представлений ордеревьев целочисленными порождающими функциями к разработке клеточных алгоритмов планирования параллельных вычислительных процессов с древовидной структурой представляются достаточно актуальными.
Направление работы определено в соответствии с комплексом НИР по республиканским программам "Информатика", и "Информатизацил" на 1992-1995 г.г., утвержденным постановлениями Совмина РБ.
Цель работа - разработка методов и средств эффективного пла-нирования параллельных вычислений в МВС на базе клеточных алгоритмов структурного преобразования ордеревьев.
Поставленная цель определила решение следующих основных задач исследования:
-
Разработка экономичных по памяти векторных целочисленных представлений ордвревьев/орлесов и принципов применения таких представлений к синтезу эффективных по временной сложности клеточных алгоритмов пошагового структурного преобразования (ПСП) ордвревьев/орлесов.
-
Разработка и исследование синхронных параллельных схем ПСП ордеревьев/орлвсов, формально описываемых соотношением эволюции состояний одномерного клеточного автомата. Разработка на основе таких схем параллельной процедуры
синтеза орлеса приближенного решения NP-полной задачи "Многопроцессорное расписание с условиями предшествования" (МРП).
-
Разработка иерархии параллельных описаний процедуры синтеза решения задачи МРП: машинно-независимого клеточного, описания и способов его аффективного отображения на век-торно-конвейевную архитектуру и архитектуру ВС на синхронном однородном решающем поле і
-
Создание алгоритмического и программного обеспечения планирования параллельных вычислений в МВС.
Методы исследования. Для решения перечисленных задач в рабо-те использованы математический аппарат клеточных автоматов, _ функций алгебры логики и целочисленной арифметики; модели и методы теории графов и теории параллельных вычислений; методы теории NP-полных задач; логико-комбинаторные методы.
Для подтверждения результатов теоретического исследования применен метод статистического моделирования на ППЭВМ.
Основные выносимые на защиту результаты:
-
Параллельная процедура пошагового структурного синтеза (ПСС) орлеса приближенного решения задачи МРП.
-
Способы взаимно однозначного представления корневых выходящих ордеревьев/орлесов целочисленными функциями.
-
Метод разработки клеточных описаний алгоритмов ПСП ордеревьев/орлесов,, заданных целочисленными функциями.
І-. Метод формирования функции переходов одномерного клеточного автомата, описывающей последовательность шагов про- . цедуры ПСС решения задачи МРП.
5. Методика оценки асимптотической погрешности процедуры ПСС
при различных алгоритмах ПСП частичного решения.
Научная новизна результатов заключается в следующем: і . Процедура ПЙС, в отличие от известных параллельных алгоритмов решения задачи МРП, реализует крупноблочную стратегию формирования изоморфных параллельных ветвей в ориентации на последующее отображение каждой ветзй на конкретную архитектуру процессора однородной ВС.
-
Предложенные алгоритмы структурного преобразования частичного решения, основанные на синхронном параллельном анализе и преобразовании характеристик дуг по эквивалентным правилам, обеспечивают возможность формирования одномерной клеточной схемы процедуры ПСС.
-
Разработанные представления ордеревьев/орлесов w-функцией и функцией, предшествования,- в отличие от известных векторных кодов, сочетают экономичность по памяти с возможностью независимого восстановления, анализа и преобразования локальных характеристик дуг по соответствующим элементам представления. Указанные особенности определяют возможность применения таких представлений к разработке синхронных параллельных схем преобразования ордеревьев/ орлесов'. ' /
-
Разработанный метод клеточного описания алгоритмов ПСП ордеревьев/орлесов позволяет задать результат преобразования векторной' функцией переходов одномерного клеточного автомата, которая определяется суперпозицией арифметических и логических операций над целочисленной функцией -представлением преобразуемой на текущем шаге промежуточной структуры.
-
Предложенный логико-комбинаторный метод формирования одномерной клеточной схемы, процедуры ПСС позволяет применить, хорошо апробированный аппарат структурного анализа векторных математических функций к разработке эффективных отображений функции переходов на конкретные архитектуры параллельных ВС.
-
Разрабртанная методика позволяет получить верхние оценки асимптотической погрешности процедуры ПСС при различных стратегиях формирования орлеса решения задачи МРП.
Практическая ценность работы заключается в.следующем: 1. Разработанные процедура, клеточные алгоритмы и программный комплекс планирования параллельных вычислений в неоднородной МВС могут быть эффективно использованы на двух .архитектурных уровнях: при статическом диспетчировании комплекса упорядоченных заданий; при распараллеливании программ на решающих долях,' в составе оптимизирующего
транслятора. 2. Использование предложенных векторных кодов ордеревьев позволяет существенно снизить затраты машинного времени и памяти при реализации алгоритмов планирования параллельных вычислительных процессов с древовидной структурой. Полученные результаты могут быть использованы проектными и научно-исследовательскими организациями, занимающимися разработкой алгоритмического и программного обеспечения параллельных ВО.
Апробация работа. Основные положения диссертационной работы докладывались й обсуждались на:.
Всесоюзном научно-практическом семинаре "Информатика 90-х " (Минск, 1991);
Одесском научно-исследовательском.семинаре по дискретной математике, посвященном теории графов и их обобщений (Одесса, 1993);
Всероссийской научно-технической конференции " Однородные вычислительные системы, структуры и среды" (Москва, 1993);
заседании школы-семинара "Анализ и применение систем и сетей массового обслуживания" (Минск, 1994); Научной конференции профессорско-преподавательского состава и сотрудников, посвященной 30-летию БГУйР (Минск, 1994). Реализация результатов работы. Исследования по теме диссер-тациокной работы выполнены в Белгосуниверситете информатики и радиоэлектроники в рамках госбюджетных, НКР "Организация подсистемы параллельного программирования" (ГР N 01910010162) и "Разработать интеллектуальные системы решения задач структурного синтеза изобретений" ( ГР N 01920011450).
Предложенные методы и алгоритмы внедрены в научно-исследовательские разработки и практику проектирования параллельного программного обеспечения в. Центре информатики и распределенной обработки данных Международной Академии Информатизации и Белорусском центре информатики БелАК ЮНЕСКО. Результаты исследований включены в материал трех книг. Публикации. Основное, содержание'диссертации, отражено в 9'по-
чатных работах, в том число 3 книгах и 2 отчетах о НИР. Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на. 174 страницах машинописного текста. Библиография включает 153 наименования. Основной текст содержит 29 рисунков и 7 таблиц.
