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

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

\ ЧЕФРАНОВ Александр Георгиевич

МЕТОДЫ И СРЕДСТВА АДАПТИВНОГО УПРАВЛЕНИЯ РЕСУРСАМИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальности:

05.13.13 - Вычислительные .машины, комплексы, системы и

сети

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

АВТОРЕФЕРАТ

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

Таганрог-1998

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

Научные консультанты:

Доктор технических наук, профессор, действительный член РАЕН и МАИ | А. Н.МЕЛИХОВ |

Доктор технических наук, профессор, действительный член МАИ О.Б.МАКАРЕВИЧ

Официальные оппоненты:

Доктор технических наук, профессор

А.Б.БАРСКИЙ

Доктор технических наук, профессор А.В.ПАНИШЕВ

Доктор технических наук, профессор Ю.В.ЧЕРНУХИН

Ведущая организация НИИ "Квант", г.Москва

Защита состоится ос^у^Р 1998 г. в /Г часов на заседании

специализированного совета Д 063.13.02 в Таганрогском государственном радиотехническом университете по адресу: 347915, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

Ученый секретарь совета Д 063.13.02 к.т.н., доцент

А.Н.ЦЕЛЫХ

ВВЕДЕНИЕ

\ктуальность гсмь! Параллельные и конвейерные вычислительные системы иироко испотыуются для решении фундаментальных научных н -фактических задач, требующих большого количества вычислений при )граничсниях на время выполнения Принципы распараллеливания и сонвеиерпзацни вычислении используются на разных уровнях зычислительного процесса и в различных комбинациях - от конвейеризации юработки команд в одном процессоре (например, Intel Pentium) до 1араллельно-конвейерной обработки на уровне ;адач в макроконвейерной лютеме ЕС-2701 Основой использования такого рода параллельно-юнвейерных архитектур является параллельно-последовательная природа 5ычислительны\ процессов. Для ускорения вычислений используются как ¡пециальные параллельно-конвейерные сосредоточенные системы, так и :ети. Потенциально высокая производительность параллельно-конвейерных ¡ычислительных систем может быть достигнута лишь при условии )авномсрного распределения вычислительной нагрузки между >брабатывающими устройствами. Известно, что времена выполнения ¡ычислительных процессов, как правило, имеют случайный характер, юэтому наиболее перспективны адаптивные методы балансировки игрузки. используемые, например, в сетях ЭВМ. Для рассматриваемых в диссертации сосрсдогочсниых параллельно-конвейерных вычислительных :истем и сетей на их основе значимость динамического управления юсурсамн. адаптирующегося к текущей ситуации еще более возрастает. ic:m в сетях ЭВМ в качестве показателя нагрузки берется, как правило, юличество заданий в очереди на обработку к соответствующей ЭВМ, то в :осредоточенных системах такой выбор неприемлем и следует работать с >еальной нагрузкой устройств, определяемой как доля времени наблюдения. 1 течение которого устройство было занято работой. В случае решения шкетов задач время наблюдения отсчитывается от момента времени начала >ешения пакета задач. Известно, что оптимальное распределение нагрузки гежду процессорами даже в простейших ситуациях ( например, два идентичных процессора, задачи решаются без прерываний) относится к :лассу NP-трудных оптимизационных задач, при этом ценность федварительного планирования весьма мала в силу случайного характера юведения планируемых процессов. Задачи в общем случае имеют сложную :трукгуру. прсдставимую иерархическим информационно-управляющим рафом. вершины которого - подзадачи - могут активизироваться при гстановке в единицу связанной с ни.мн функции готовности. Параллсльно-хшвейерные системы могут иметь разнообразную архитектуру (состоять из »динаковых или однородных процессоров или мультипроцессоров, число ;оторых может быть переменным, иметь ресурсы многих типов, содержать (дну или более сту пеней обработки и т.д.), что совместно с моделью задачи шределяет множество различных

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

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

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

Указанная цель достигает ся путем решения следующих задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты диссертации получены автором при выполнении научно-исследовательских и опытно-конструкторских работ в рамках важнейшей госбюджетной и хоздоговорной тематики в соответствии с Постановлением СМ СССР от 27.01.86, № 139-49: Постановлением С'М СССР от 16.06.87, № 675-155; Постановлением АН СССР от 17.10.85, № 1005. Результаты работы внедрены в

ч/д работах 51119 от 15.03.91 с НИИ ')ВМ, г. Минск. «Ланка-УН» с в/ч 12462. г. Москва. «Ларикп» по решению Г ВПК" СМ СССР от 24 (14 91. ОКР «Соловейко-ЗФ» указание N М0/01/96/5612.6"! от 20.11.% поддержанном рффи проекте «Алма?» N 96-01-016X1 распоряжение N %-1-Ю/М) от 4.04.96. поддержанном РФФИ проекте N 9¿-01-00695.

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

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

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

4. Система параллельного программирования, представляющая расширение языка Фортан-77. позволяющая представлять комплексы взаимосвязанных по управлению и данным параллельных задач, предназначенных для асинхронного динамического выполнения на параллельных вычислительных системах, причем каждая из задач выполняется в режиме ОПМД.

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

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

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

Результаты работы использованы в НИИ МВС при ТРГУ. г. Таганрог. ТАНТК им. Г.М.Берисва. г. Таганрог. НИТДЭВТ. г. Москва, в учебном процессе ТРТУ на кафедрах ВТ и МОП ЭВМ, что подтверждается соответствующими актами.

Апробация работы. Основные результаты диссертации представлены на: Всесоюзной школе-семинаре «Разработка и применение в народном хозяйстве ЕС ЭВМ» (Кишинев, 1985); 1 Всесоюзной конференции «Проблемы создания супер-ЭВМ. супер-систем и эффективность их применения» (Минск. 1987);

Международной научно-технической конференции «Актуальные проблемы фундаментальных наук» (Москва. 1991): на Международных конференциях «Parallel Computing Technologies» (Новосибирск. 1991: Обнинск. 1993; С.Петербург. 1995): на 1 Национальной конференции Indian Transputer User Group ( Punc. India. 1993): на 8-th Symposium on Microcomputer and Microprocessor Applications (Budapest. Hungaiy, 1994): на 8-й Международной конференции Information. Modeling and Control (Zakopane. Poland, 1995); на международном семинаре Summer Workshop on Computational Modeling and Imaging in Biosciences (Kecskemet. Hungaiy. 1995): EuroPar'96. Lyon. France. 19%; на научно-техническом семинаре «Многопроцессорные вычислительные системы» (Дивноморский. 1996). на конференциях профессорско-преподавательского состава ТРТУ ( Таганрог. 1995, 1996).

Публикации. Основные результаты отражены в 40 печатных работах, в том числе: 1 монография. 3 учебных пособия. 2 авторских свидетельства, 2 программы зарегистрированы в ОФАП Минвуза РСФСР.

Структура и объем диссертации. Текст диссертации изложен на 245 страницах, состоит из введения, четырех разделов, заключения и приложений, содержит 34 рисунка. 1 таблицу и список литературы (277 наименований).

Содержание

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

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

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

Параллельно-конвейерная обработка предполагает

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

нескольких стадий параллельно-конвейерной системы.

При обработке задач на многопроцессорных системах могут быть рассмотрены различные уровни параллелизма - так называемая зернистость. Режим решения наборов независимых задач может быть рассмотрен как крупнозернистые вычисления. а взаимосвязанных задач - как среднсзернистыс. При этом решение совокупности независимых задач, каждая из которых представляет собой набор взаимосвязанных подзадач может рассматриваться как решение набора независимых задач (при распределении ресурсов на уровне задач), либо как решение наборов вт.шмосвя шнных задач (при распределении pecv ра:в на уровне подзадач). Каждая задача может быть сложной, структурной, и требовать для решения несколько процессоров, либо же представлять собой последовательный процесс, выполняемый на одном процессоре Времена выполнения «дач (под задачей будем понимать программный объект, требующий определенных системных ресурсов) зависят, как правило, от исходных данных и поэтому, в общем случае, заранее неизвестны так же. как и действительная траектория вычислительного процесса в случае обработки множества взаимосвязанных задач. В натпих рассмотрениях все множества предполагаются конечными: задач, процессоров, поэтому интервалы времени, в течение которых задачи решаются на процессорах, также конечны. Рассмотрение начинается в некоторый момент времени t=0. когда множество системных ресурсов свободно, а задачи еще не решены. Критерий максимизации загрузит, производительности процессоров при сделанных предположениях эквивалентен минимизации времени решения юрвоначального набора задач на имеющихся процессорах. Эта штимизацпонная задача относится к классу ¡чР-трудных даже в случае двух иентичных процессоров и множества независимых задач, требующих по )дному процессору каждая, решаемых без прерываний, а также и в случае топустимостп прерываний, если задачи, например, связаны и представляют :обой граф, не являющийся деревом, или же задачи являются сложными ( ребуют для решения одновременно несколько процессоров и/или других .истомных ресурсов) Прерывания требуют определенных затрат, весьма ¡начительных при решении сложных задач, рашивающнхея в режидте )ГТМД на нескольких процессорах, поэтому в наших рассмотрениях мы ¡удем стремиться к организации вычислений по возможности без фсрыванин. К тому же известно, квантование времени приводит к более ¡ыстрому прохождению более коротких задач, что оптимизирует [роггускную способность системы, понимаемую как количество задач, 1сшаемых системой в единицу времени, но производительность, общее ремя решения задач при этом не оптимизируется.

С другой стороны, квантование времени позволяет, не зная заранее ремени решения задач, выделить из них более короткие по времени ешения и пропустить их в первую очередь, адаптируясь к множеству ешаемых задач: а так как алгоритм SPT (Shortest- Processing-Times tasks -rst). назначающий на

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

Для нашего случая критерия производительности или общего времени выполнения Т(2,8) множества задач Ъ на системе Б алгоритм А управления ресурсами системы Б будем считать адаптивным, если для любого множества задач Ъ и любой системы 8 имеет место

ТА {2,8) < аА /,', (7, Л'), (1)

где Т4 (2,Л') - время выполнения множества задач Z на системе Б при использовании алгоритма А распределения ресурсов, не использующего при распределении информацию о временах решения задач. 70 (2Л1) -

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

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

Однако, как упоминалось, нахождение является К!Р-

трудной задачей даже в простейших ситуациях и требуют значительного объема вычислений для каждого примера Ъ, Б, поэтому надежды получить Т0 8) аналитически нет. Более того, для некоторых задач управления ресурсами показано, что при предположении о том, что т.е. НР-

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

С другой стороны, каждый, даже наиболее простой алгоритм управления ресурсами, дает расписания, существенным образом зависящие от параметров задач (запросы на ресурсы, время решения), поэтому получение аналитического выражения для Т, (И^Я) - также весьма сложная проблема.

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

В то же время, в теории автоматического управления давно известны

так

называемые передаточные функции. характеризующие устройство преобразования входных сигналов в выходные отношением образов выходных сигналов к образам входных и эго отношение одно и го же ,ття любых заранее неизвестных сигналов, '¡десь у нас в качестве преобразователя выступает алгоритм управления ресурсами, а в качестве образов входных и выходных сигналов - соответственно T(ZJi) и TJZ.S). Точные значения 7,'. (2,¿'). /'.(Z.-V), TA(Z,S)/TJZ>S} ни всей видимости, найги невозможно, но если найти оценки для 7¡:(Z,S) . Г, (Z, S). то можно найти оценку / , (Z,Л') / 7,',(2,Л'). что гоже вполне информативно. Таким обра' íom. если а существует. то таких значений существует бесконечное множество и из них наименьшее и будет час интересовать.

Если предположить. что могут быть найдены такие знакоположительные функции (р (Z.S). (// ÍZ.S). что

Tn(Z,S) > <p(¿,S), (2) ТА (2, S)<y/ (Z,S), (3)

то из (2). (3) можно получить

TA(Z,S) ^ y/{Z, S)

Г,(Z.S) rp(Z, S)

Если правая часть (4) ограничена, го оценка такого вида и приведет нас к искомой оценке (1).

Оценки (2). (3) представляют и самостоятельный интерес, так как дают возможность оценить производительность системы в лучшем случае (q> (Z.S) - время (естественно, нереализуемое) решения набора задач Z на системе S. не большее соответствующего оптимального значения) и в худшем случае ( у; (Z.S)- время решения задач Z на системе S, не меньшее времени их решения при распределении их алгоритмом А). Усреднение (р(Z.S) и ///(Z.S) по множеству задач Z дает оценку сверху и снизу

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

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

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

Параллельно-конвейерные вычислительные системы

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

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

которые состоит из N идентичных процессоров. Процессоры из разных-

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

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

Для случая системы из п идентичных процессоров с полнодоступной коммутацией и потоков «малых» взаимосвязанных многопроцессорных задач (каждой из которых требуется не больше п/2 процессоров) показано, что при использовании алгоритмов классов РВЬ-Б. РВЬ-Р. N61.-8, ШЬ-Р справедливо

Т(г,п)<ЗТ0{г,п). (5)

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

у1 > 0,/ - 1, /.; для пакетов задач у; —0,1 — 1, Ь. Суть алгоритмов класса

РБЬ (Рй-ВоПот-Ьей) распределения ресурсов при решении пакетов задач заключается в назначении на освобождающиеся процессоры очередной задачи из множества подходящих, т.е. тех задач, для решения которых свободных ресурсов достаточно. Конкретные алгоритмы класса РВЬ отличаются правилами упорядочения подходящих задач. Алгоритмы класса списковых, или ЫВЬ - алгоритмов (Нсх1-Воиот-ЬеП), назначают на освобождающиеся процессоры очередную задачу из задач, упорядоченных в соответствии с некоторым правилом. В случае, когда задачи взаимосвязаны или поступает поток задач, алгоритмы классов БВЬ и КВЬ могут порождать алгоритмы следующего вида: Б-модификации алгоритмов используют постоянно пополняемый пришедшими в состояние готовности задачами список задач - кандидатов на распределение, а Р-модификации учитывают при распределении вновь появившиеся готовые к решению задачи только по завершении назначения ранее имевшихся задач-кандидатов, первоначальное множество которых образовано задачами., исходно готовыми к решению.

При распределении потоков взаимосвязанных задач, среди которых могут быть и «большие» задачи, показано, что при использовании алгоритмов классов РВЬ-РЯ, КВЬ-РЛ также справедлива оценка (5). что доказывает адаптивность алгоритмов РВЬ-Б, РВЬ-Р, МВЬ-5. №Ь-Р. РВЬ-РК. ЫВЬ-РЯ в указанных условиях. РР„- модификации алгоритмов РВЬ-Б и №Ь-Б, отличаются тем, что при появлении в списке готовых к решению задач «большой» задачи (ранга, большего п/2) прерывается решение стольких «малых» задач (ранга, не большего п/2), чтобы освободившихся ресурсов хватило для назначения «большой» задачи, и назначается «большая» задача.

В случае систем, состоящих из п однородных мультипроцессоров, ь каждом и? которых реализована полнодосгупная коммутация N идентичных процессоров, и пакетов независимых многопроцессорных задач «окачаш что при использовании алгоритмов класса 1'Н1. справедливо

Тт(1^)<{г + с](1 •„ ' ■-))№,лу с.)

Т.ъ, (2,Л') < 29 + тих /, {2 • --— ). П)

I 1 ' х-ч

7 -I

где с',- относительные производительности процессоров 1-го мультипроцессора. ¡=1.п. с1 > с 1 >....> сп ■■■ 1; время решения ¡-й задачи

1'Л /

на )-м мультипроцессоре есть /с .,/ = 1,Ду ~ 1,/?, б1 = /п

/

. -1

Из (6).(7) следует, в частности, что для системы из п идентичных мультипроцессоров при тех же условиях справедливо

Тш (2, Л') < (4 - 1 / пЫ) Тп (7,5) (8}

Тт, (2, Я) <2в + (2~\/ пМ) шах . (9)

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

^.(ад <(2^,(1-......^---шад. (Ю)

1.1

2

(2,о) < 20 + тах/,(1 ------). (11)

г-1 I

А^с,

Из (10). (11) следует, что для системы из п идентичных

мультипроцессоров при тех же условиях спрзведтиво

Т,ыт(2^)<(3-2/}М)ТхХ7-Л) (12)

2

т«нв1 3) < 2в + тах /,(1- -—). (П)

,-Ы /\1ц

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

Для случая систем с мультипроцессорами со связями типа «линейка» (каждый процессор связан с ,двумя соседними) в каждом мультипроцессоре и для алгоритмов ЯРВЬ (из подходящих в первую очередь выбираются задачи с максимальным рангом) и ГШВЬ показано, что при распределении пакетов независимых многопроцессорных задач справедливо

7Хад)<(2 + С1(1--~))Тп(г,8) ,

1-1

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

Для случая систем, состоящих из однородных мультипроцессоров с полнодоступной коммутацией процессоров в каждом, при распределении пакетов взаимосвязанных задач, каждой из которых требуется не более N/2 процессоров, алгоритмами классов ИЗЬ-Р и КВЬ-Р справедлива оценка

Т{2,6') <(2 + (1----»Г»(¿.¿У (14)

В частности, для систем с идентичными мультипроцессорами оценка (14) превращается в

Г{2^)<{Ъ-21пЫ)Т,{2^). (15)

Так же, как и в случае одного мультипроцессора, при распределении пакетов взаимосвязанных задач произвольных рангов алгоритмами классов РВЬ-Б. МВЬ-Б, РВЬ-Р, ШЬ-Р могут быть получены расписания с произвольной ошибкой. Если же использовать алгоритмы классов РВЬ-РЯ. ЫВЬ-РЯ. то для них справедливы оценки (14), (15), что доказывает их адаптивность для произвольных пакетов взаимосвязанных задач в случае систем

мультипроцессоров.

Для случая системы, состоящей из нескольких мультипроцессоров с полнодоступной коммутацией процессоров в каждом, и распределении потоков независимых задач алгоритмами класса РВЬ-Б справедливо

Гт.Д2,5)<2Го(2>5)0 + С1) (16)

В частности, для системы с идентичными мультипроцессорами имеем

<47; (2,5). (17)

При использовании алгоритмов класса ЕВЬ-Р в системе с однородными мультипроцессорами при тех же условиях имеет место

(2,5)< 27; (2, 5)0 + 20,). (18)

Из (18) для системы с идентичными мультипроцессорами следует 7^(2,5) <6Г0(2,5) . (19)

Таким образом, из (18), (19) следует, что алгоритмы классов РВЬ-Б, РВЬ-Р являются адаптивными при распределении пакетов независимых задач на систему с однородными и идентичными мультипроцессорами.

Если в системе с однородными мультипроцессорами с полнодоступной коммутацией процессоров в каждом применять алгоритмы классов РВЬ-Б, КВЬ-Б, РВЬ-Р, НВЬ-Р для распределения потоков

взаимосвязанных задач с Д <Аг/2л'-1,Ь, N - число идентичных

процессоров в каждом мультипроцессоре, то

цг, я) <(2 +с, к (г, 5). (20)

Для системы с идентичными мультипроцессорами из (20) следует

дад<з7;(2,5) . (21)

Если задачи могут быть произвольных рангов и потоки взаимосвязанных задач распределяются в системе однородных или идентичных мультипроцессоров алгоритмами классов РВЬ-Р Я, ЫВЬ-РЯ. то для них также справедливы оценки (20), (21), что доказывает адаптивность алгоритмов рассмотренных классов в этих условиях.

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

m > 2 max Rf и используются алгоритмы класса FBL, то

1=1, л

mCv j(4-2/n)T0(Z,S), maxt,^

T(Z, S) < < (22) \(2A + 2-2/ri)T0(Z,S),else

где A=M/m, М - max max (/), m = min min n, (t),

i=l,n te{0,T(Z,S)) i=l,n isfO.TCZ.S'))

1=1 о '=1

Если т > тах , то при использовании алгоритмов класса 1=1.1.

БВЬ в тех же условиях имеет место

(4Т0(г,5),тах^ >6 Т&,8)<\ 0 1 ' (23)

. Оценки (22), (23) доказывают адаптивность алгоритмов класса БВЬ в соответствующих условиях.

Рассмотрим теперь системы с несколькими ступенями процессоров; коммутация процессоров осуществляется внутри каждой ступени и между ступенями. Задачи представляют собой совокупность подзадач, образующих цепочки, первая задача цепочки должна решаться на процессорах первой ступени, вторая - после завершения первой подзадачи на процессорах второй и т.д. Процессоры каждой ступени, таким образом, это некоторые специализированные (аппаратно, микропрограммно, программно) процессоры, задачи также относятся к некоторой одной предметной области как имеющие одну и ту же структуру (например, это могут быть задачи распознавания изображений в динамической среде). Как и в случае одноступенной обработки, задачи могут быть как независимыми, так и взаимосвязанными. В последнем случае считаем, что если задача может выполняться по завершении задач Zl¡,..., Zj|, то это означает, что

для любой ступени j подзадача Zf 0 -я подзадача задачи Zj) может

выполняться на|-й ступени по завершении подзадач Z}г,, j=1 ,М, М - число ступеней. Задачи на каждой ступени могут требовать по одному или несколько процессоров, а на каждой ступени может быть один или несколько мультипроцессоров.

Для случая систем с одним процессором на каждой ступени и распределении пакетов независимых задач алгоритмами классов ЕВЬ и МЗЬ

эценено время решения пакета в виде

T(Z,S)= ]Г// ,

z/<'Л'(г)

где W(Z) - некоторый путь пакета длиной L+M-1, т.е. совокупность L+M-1 подзадач пакета, где каждая очередная подзадача есть либо следующая подзадача той же задачи, либо подзадача той же ступени очередной задачи, гадачи считаются предварительно упорядоченными некоторым образом. Если на каждой ступени конвейера находится п идентичных процессоров, то, эаспределяя задачи равномерно-циклически между ними, получим п нитей юнвейера, на каждую из которых приходится JL/n[ задач и тогда дайна пути та кет а, определяющего время выполнения всех задач, будет равна ]L/n[ + М-I.

Для случая мно го ступенных систем с П] идентичными

троцессорами на j-й ступени и пакетов независимых однопроцессорных ¡адач, распределяемых алгоритмами классов FBL и NBL, справедливо

T(Z,S)< (М+1) T0(Z,S), (24) по доказывает адаптивность алгоритмов этих классов в указанных

,'словиях. Рассмотрим теперь случай М=2, t] = 1, i=l,L (времена решения

2 2 ^

¡адач на первой ступени единичные), и пусть tx > t2 >....>/£. Показано,

гго если /,2 < [п2 / п} ], то назначение задач в соответствии с этим списком

алгоритм LPT) дает оптимальное расписание. Для случая VL > [п2 / пх ] токазано, что

TLPT (Z,S) < (4 / 3 -1 / Зп2) Г0 (Z, S). (25) Если задачи пакета могут иметь произвольные времена решения на ¡торой ступени, то

Tlpt(Z,S)<2T0(Z,S). (26)

Показано также, что последняя оценка справедлива для алгоритма „РТ в случае И, =1 и произвольных времен решения задач на первой ггупени. Таким образом, для алгоритма LPT при учете специфичных 'словий (единичные времена решения задач на первой ступени, один фоиессор, две сту пени и т.п.) справедливы оценки (25), (26), более точные, юм оценка (24).

Для случая пакетной обработки однопроцессорных ;заимосвязанных задач в системе с произвольным числом процессоров на аждой ступени показано(число ступеней произвольное), что для лгоритмов классов FBL и NBL справедливо неравенство (24), что [оказывает адаптивность этих алгоритмов в таких условиях.

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

коммутацией показано, что для алгоритмов класса FBL справедливо

T(Z,S)<2M T0(Z,S) что доказывает адаптивность алгоритмов класса FBL в указанных условиях.

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

T(Z,S)<(2M+1) T0(Z,S) , (27) если каждой задаче требуется на каждой ступени не более половины числа процессоров этой ступени. Обобщая алгоритмы классов FBL-PR, NBL-PR на эту систему, получаем, что (27) справедливо для этих алгоритмов в случае задач с произвольными требованиями на процессоры. Таким образом, алгоритмы классов FBL-S, NBL-S, FBL-PR, NBL-PR адаптивны в указанных условиях.

В случае обработки потоков независимых однопроцессорных задач в системе с произвольным теслом ступеней и распределении ресурсов алгоритмами класса FBL-S имеет место оценка (24). В случае потоков многопроцессорных задач и распределении ресурсов алгоритмами класса FBL-S справедлива оценка (27), что свидетельствует об адаптивности алгоритмов этого класса в указанных условиях.

Пусть имеется теперь М-ступенная параллельно-конвейерная система, на i-й ступени которой имеется ki мультипроцессоров по nt идентичных процессоров с полнодоступной коммутацией процессоров в

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

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

м

T(Z,S)<2(M +%Cli)T0(Z,S) i=i

Если пакет состоит из взаимосвязанных задач, то при распределении их алгоритмами класса FBL-S справедливо

T(Z,S) < (2М+ max си) Т0 (Z, S),

i=\M

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

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

Многостепенные многопроцессорные системы были исследованы экспериментально с помощью разработанной для IBM PC имитационной .модели. На основании результатов моделирования алшряпш FFBL (задачи из множества подходящих выбираются в порядке убывания номеров) получены аналитические эвристические формулы. определяющие предельное число процессоров каждой ступени двухступенной параллельно-конвейерной системы (М-~2). Под предельным понимается такое минимальное число процессоров, что дальнейшее его увеличение не ведет к рост> пропускной способности системы, характеризуемой временем решения пакетов задач и понимаемой как вероятность решения пакета задач за определенное время. Пусть /j (г;) максимально возможное число процессоров, необходимое для решения задач (время решении задач) на i-й ступени. i=l.М. Если l\ —1\ = 1, то предельное число процессоров i-й ступени определяется так:

п, = min(]2w3 iri /г _,.,[,/,), i=l.2.

Если 1] — 1, г3_, > 1. то

Iii ; = min(]/\ дг, , / г, f, ]/./',., /2[) . 1.2

4//% , г II = |Т1 in(]—— * —i—Г, 1-)

Если /; > 1. 1,2 то

и* = max(/;, min(]2 * [, }Lr /' 2[ ).

Экспериментально исследованы алгоритмы RBFL (из подходящих избираются в первую очередь задачи, требующие больше процессоров) и :FBL с точки зрения простоя ресурсов обеих фаз за время решения задач, с •очки зрения простоя ресурсов первой фазы за время решения задач первой ¡>азы и ресурсов второй фазы на интервале решения пакета задач в целом и : точки зрения отклонения времени решения набора независимых 1ногопроцессорных задач от нижней границы соо гветствующего ¡птимального значения. Полеченные экспериментально зависимости ;оответств\ ют интуитивным представлениям о поведении соответствующих :арактернстик. для которых предложены аналитические выражения, оэффнциенты которых подогнаны к экспериментальным данным.

Алгоритмы FFBL и FNBL также экспериментально исследованы для лучая параллельно-конвейерных вычислительных систем с произвольным иолом ступеней при решении пакетов независимых многопроцессорных адач. Алгоритм FNBL показал результаты, худшие в среднем на 10-30%. [ричем с

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

М 1 I- Л/-) 1 I

7,', = шах(шах £//, гпах —£ Л///, тш £// ^^^ )■

1-1,1 , г--\М /7 ГТ I и г~7

"! 1-.1 у -1 "и к Л

Был отмечен, в частности, интересный факт: максимальное значение ошибки наблюдалось при числе задач Ь. вдвое превышающем число ступеней, и зависимость погрешности от Ь при фиксированном М имеет вид унимодальной функции с максимумом в указанной точке. Это явление объясняется тем. что по мере продвижения по фазам задачи «рассеиваются», вследствие чего переход задачи со ступени на ступень осуществляется практически без задержки, связанной с отсутствием свободных процессоров очередной ступени.

В третьем разделе рассмотрены вопросы разработки средств аппаратной поддержки методов адаптивного управления ресурсами. Для систем с одной стадией обработки при решении наборов взаимосвязанных задач можно выделить три основные проблемы: определение задач, готовых к решению в соответствии с графом взаимосвязей, определение среди готовых к решению задач очередной (например, по алгоритму РВЬ-РЯ). выделение задаче конкретных процессоров и назначение ее. Кроме того, архитектура системы на ступени должка быть приспособлена к рассмотренным выше методам управления ресурсами.

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

тисзья). а ребра помечены символами О или 1. Граф для вычислений спо тьчустся следующим образом Проис«.-- начинается с корневой ершииы. Проверяется значение <;иугн екчтшшей переменной. Н 1ВИСИМОСТИ от ее значения осуществляется переход на лев^то, либо правую сришну следующего уровня и т.д да> попадания в листовую вершину качанное в последней значение и «веется вычисленным значением ункции. Номер готовой $адачи чгрез БП1 передается процессорам, [ри.менение чанного устройства позволяет организовать вычисление в ту чае неизвестной заранее траектории вычистигельного процесса.

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

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

требуется задаче, конъюнкгивно накладываются друг па друга и там. где элучаются единичные значения номер задачи проходит на )07ветств}т0щ»;с процессоры, а соответствующие разряды масок при этом 5нудяк>гся. после чего маска требования задачи сдвигается на один разряд траво. и процесс наложения повторяется, если в маске требования задачи це остались единицы. В случае связей процессоров по принципу тпзкодействия ожидается такой вариант наложения масок, когда все шнииы в маске требования были бы уничтожены одновременно и только в :ом c.ij час номер задачи передается на соответствующие процессоры, если е не все единицы пропали, то они восстанавливаются, маска сдвигается на ;нн разряд вправо и процеду ра конъюнктивного наложения маски задачи и иски процессоров повторяется.

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

В случае решения наборов ввакмосвязанных многопроцессорных ¡дач с произвольными требованиями задач к процессорам в соответствии с тгорптмами классов FBL-PR и NBL-RL необходимо обеспечивать режим

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

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

Описана структура многопроцессорной вычислительной системы, которая может выступать в качестве базовой при построении ступеней параллельно-конвейерной вычислительной системы. Система дает возможность объединять в группы процессоры, работающие по малоразличимым программам и осуществлять синхронизацию не всех процессоров сразу, а для каждой группы процессоров отдельно. Система содержит ведущую (хост) ЭВМ, узловые процессоры, связанные по близкодействию в тор. и системную магистраль. Узловой процессор содержит микропрограммное устройство управления, арифметико-логический блок, блок оперативной памяти, регистр состояния, регистр управления, регистр выбора, регистр группы, регистр номера группы, регистр адреса, регистр данных-, выходной регистр. Вычислительная система работает так. Управляющая ЭВМ определяет, какие из переданных ей из хост-машины программ готовы к решению, определяет конфигурацию свободных процессоров и проверяет, можно ли какую-либо готовую задачу назначить. Если можно, то ее номер (номер группы) рассылается по регистрам данных выделенных для ее решения процессоров, откуда далее попадает в регистр номера группы. Затем одновременно во все процессоры группы загружается код программы, а далее каждому процессору группы индивидуально передаются его данные. Группа процессоров запускается на выполнение подачей соответствующей команды. Если узловому процессору требуется общение с другими процессорами группы, то он выставляет в регистре состояния

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

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

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

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

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

Разработан компилятор для языка параллельного программирования на основе языка Фортран-77 для разрабатывавшейся в НИИ МВС при ТРТУ многопроцессорной системы, учитывающего специфику ее архитектуры. Архитектура этой системы близка описанной в предыдущем разделе архитектуре базовой системы параллельно-конвейерных вычислительных систем. Предполагается, что задача представляет собой множество взаимосвязанных подзадач. Для решения каждой подзадачи требуется одновременно несколько процессоров, занимаемых в режиме БРМО, т.е. все процессоры подзадачи работают по одной программе, но над разными данными. Процесс решения задачи может быть представлен как совокупность процессов двух видов: обрабатывающие процессы, реализующие вычисления подзадач и управляющий процесс, реализующий управление обрабатывающими процессами на основе графа связей задачи. Управляющий процесс представляет задачу в целом, в то время как обрабатывающие программы представляют ее части, поэтому управляющий процесс назовем задачей, а обрабатывающие процессы подзадачами. Предполагается следующая модель памяти данных, ассоциируемых с задачей. В задаче (управляющий процесс) объявляются данные задачи, распределенные равномерно по всем процессорам, выделенным для решения задачи. Количество требуемых задаче процессоров задается с помощью специального оператора. Эти процессоры выделяются задаче при запуске задачи и фиксируются за ней на все время её жизни. Ресурсы, требуемые для выполнения подзадачи, выделяются из множества свободных ресурсов, отведенных задаче. Глобальные данные задачи распределяются по всем процессорам равномерно, причем карта распределения глобальных данных одна и та же для каждого процессора задачи. Глобальные данные подзадачи распределены равномерно по процессорам, отведенным для решения подзадачи. Подзадача является совокупностью параллельных процессов, протекающих по одной и той же программе, эти процессы могут иметь каждый свои локальные данные, но расположение их в памяти для всех процессов подзадачи одно и то же.

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

г; возможных реализаций управляющего процесса является организация его виде бесконечного цикла, в котором постоянно проверяется состояние одзадач. Этот процесс является последовательным и для его реализации южст бъпь выделен первый процессор из множества процессоров, ринадлежащих задаче. Обрабатывающие процессы также протекают по оследоватсльным программам, но на каждом процессоре одной и той же рограммой при этом обрабатываются свои данные. Поэтому Фортран-77 ыл дополнен конструкциями, отражающими специфику описанной модели адачи. такими, как TASK. SUBTASK. задающими задачу и подзадач). ROCESSORS (количество требуемых задаче или подзадаче процессоров). ASKDATA. SUBTDATA. определяющими глобальные данные задачи и одзадачи. Проверка состояния подзадач и запуск :гх на решение, а также инхронизация процессов осуществляется библиотечными функциями, азработаны на языке Турбо-СИ++ транслятор и символьный отладчик.

Разработана также интегрированная система проектирования араллельных программ, предоставляющая пользователю возможность ерархического представления своей задачи в виде совокупности нформационно-управляющих графов подзадач, причем каждая вершина-одзадача может быть, в свою очередь, задачей, представимой графом или е терминальной вершиной, т.е. программой, .написанной на каком-либо эследовательном языке программирования, я реализуется в режиме SPMD. истема позволяет создавать и редактировать графы задач, а также адготавливать загрузочные модули для реализации на вычислительной ¡сте.ме. Для конкретности разработка ориентирована на систему P-Cubc ир.мы Parsvtec- 8 транспьютерную систем)' на базе ¡ранспьготеров Т-805. эаф задачи описывается гак совокупность следующих объектов: список ;ршин графа - здесь перечисляются имена файлов, содержащих описания :ршин, и указывается количество вхождений вершин в граф: список травляющих связей: список информационных прижизненных связей, т.е. ¡язей в процессе жизнедеятельности подзадачи: список информационных )смертных связей, определяющих подзадачи, получающие результаты изнедеятельности данной подзадачи и активизирующиеся после ее вершения. При одном уровне рассмотрения задача представляется как ¡вокупность связанных друг с другом подзадач, а при другом уровне ^смотрения она представляется как одна вершина, специфицируемая едующим образом: наименование, управляющие входы и выходы. ,'нкция готовности вершины, информационные входы и выходы и и.х типы, >изнак терминальности вершины (является ли она. в свою очередь, афом). При задании структуры задачи создаются файлы двух типов, держащие информацию о графе задачи как объединении многих вершин нутреннее представление) и файлы, в которых эти же графы 1едставляются как единое целое со своими входами и выходами (внешнее едставление).

ссмотрены вопросы интерпретации графового описания задачи при

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

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

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

Разрабокша система, позволяющая осуществить аналитически преобразование выражений, построенных по задаваемы*: пользователем правилам, в соответствии с законами, также задаваемыми пользователем. Графы, в частности, могут быть представлены формулами и их можно преобразовывать к требуемому виду, например редуцировать к графу терминальных вершин. Правила построения выражений задаются синтаксическими диаграммами, на основании которых строится дерево выражения. Правила преобразования задаются в виде ЛЧ=ПЧ. где ЛЧ (левая часть) определяет шаблон для сопоставления в выражении, а ПЧ (правая часть) определяет подстановку в выражение на место, определяемое шаблоном. Правила могут быть также условными, а правая часть может генерироваться автоматически на основе конкретных значений, взятььч из части выражения, сопоставленной ЛЧ. Левая часть правила может быть также использована в специальном виде для выделения в выражении цепочек заранее неизвестной длины, полученной многократным повторным применением одной и тон же операции.

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

Если с каждой вершиной V связана функция готовности по входу 1пу(). функция выходов ОиЦ), определяющая возможных приемников управления от данной вершины, то граф корректен, если справедливо следующее утверждение

(Уу,, V., е (/)(у, -передала-управление—» 7//^())

Доказательство истинности таких утверждении может быть произведено автоматически разработанной программой ЬОСТЯАЫ преобразования логических выражений к дизъюнктивной нормальной ¡гарме. Разработана также программа перевода логических выражений в Зазис И-ИЛИ-НЕ которая может быть здесь использована как препроцессор.

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

Заключение

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

Основные теоретические и практические результаты, полученные в диссертации, заключаются в следующем:

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

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

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

эоцессов на ресурсы как при статическом, гак и при динамическом ^пользовании ресурсов, аналитическое преобразование потыовзгельских ланий к наиболее приемлемой форме, а также возможность проверки >ррсктностн заданных описаний, включающие систему программирования 1 языке Параллельный Фортран, интегрированную среду визуального гоектирования иерархических параллельных программ, ориентированную I мультитранспьютерные системы. систему аналитического >еобразования выражений (в частности, программ) произвольной руктуры в соответствии с произвольными правилами, систему приведения )гичсских выражений к базису И-ИЛИ-НЕ и приведения их к тзъюнктивной нормальной форме, что может быть использовано для тематического доказательства теорем и корректности графовых фаллельных программ.

Разработанные в диссертации методы и средства адаптивного управления ресурсами нашли практическое применение в НИИ МВС при ТРТУ в математическом обеспечении созданных экспериментальных образцов МВС ЕС-2703. многопроцессорной минисупер-ЭВМ и ее векторного блока, при выполнении хоздоговорных, бюджетных и инициативных работ, поддержанных РФФИ. Результаты работы использованы в учебном процессе ТРТУ на кафедрах вычислительной техники и математического обеспечения и применения ЭВМ в лекционных курсах «Архитектура и математическое обеспечение суперЭВМ». «Архитектура вычислительных систем». «Параллельное программирование». «Системы реального времени». Опубликованы три учебных пособия: «Методы управления ресурсами вычислительных систем». «Архитектура и математическое обеспечение многопроцессорных супер-ЭВМ», "Применение ЭВМ для решений задач математической логики".

Основные результаты опубликованы в работах: Бабенко Л.К.. Макаревич О Б.. Чефранов А.Г. Адаптивное управление в многопроцессорных вычислительных системах. - ИГТПМ АН УССР. Львов. 1992. -273с.

Бакенрот В.Ю.. Чефранов А.Г. О точности оперативных диспетчеров. -Управляющие системы и машины. 1983. №4.

Бакенрот В.Ю.. Чефранов А.Г. Эффективность одного класса алгоритмов планирования в сетях мультипроцессоров. • Автоматика и вычислительная техника. 1984. № 1.

Бакенрот В.Ю.. Макаревич О.Б.. Чефранов А.Г. О числе прямоугольников единичной ширины, достаточном для упаковки заданных прямоугольников. - Кибернетика. 1984. №1. Бакенрот В.Ю., Чефранов А.Г. Эффективность приближенных алгоритмов распределения программ в однородной вычислительной системе. - Известия АН СССР. Техническая кибернетика, 1985, №4. Чефранов А.Г. Об эффективности одного класса алгоритмов оперативной

загрузки многопроцессорных систем при реализации асинхронных вычислении. - Известия АН СССР. Техническая кибернетика. 1985. №6.

7. Макаревич О.Б.. Чефранов А.Г. Об эффективности одного класса алгоритмов оперативной загрузки многопроцессорных систем с ненадежными процессорами. - Автоматика и телемеханика. 1986. №2.

8. Чефранов А.Г.. Бакенрот В.Ю. Эффективность двух классов алгоритмов оперативной загрузки. -Кибернетика. 1485. №5.

9. Макаревич О.Б.. Ремаренко Л.В.. Чефранов А.Г. Об одном алгоритме планирования пакетной обработки в однородных вычислительных системах. - Известия АН СССР. Техническая кибернетика. 1986. №5.

10 Чефранов А.Г.. Саак А.Э. О вероятности соблюдения директивных сроков многопроцессорной системой. - Автоматика и вычислительная техника. 1987. №6.

11. Чефранов А.Г., Саак А.Э. Детерминированные и вероятностные оценки эффективности многопроцессорных систем. - В книге: Проблемы создания суперЭВМ, супер-систем и эффективность их применения. I Всесоюзная конференция. Тезисы докладов. - Минск. 1987. -4.2.

12. Макаревич О.Б.. Чефранов А.Г. Об эффективности алгоритмов динамического распределения ресурсов многопроцессорных систем при решении потоков задач. - Автоматика и вычислительная техника. 1987. №4.

13. Бабенко Л.К.. Карпов Е.В.. Макаревич О.Б.. Чефранов А.Г. Управление параллельными процессами в многопроцессорной системе с программируемой архитектурой. - Известия СКНЦ ВШ. Технические науки. 1986." №4.

14. Карпов Е.В.. Ослопов М.Д.. Лаврова И.Н.. Чирский A.C.. Чефранов А Г. Управление параллельными процессорами в вычислительной системе ЕС ЭВМ - процессор 2703. - В кн: Разработка и применение народном хозяйстве ЕС ЭВМ. Тезисы докладов Всесоюзной школы семинара. Кишинев. 1988. ч. II.

15. Бакенрот В.Ю.. Чефранов А.Г. О качестве списковых диспетчеров. -Кибернетика. 1988. №3.

16. Бабенко Л.С.. Макаревич О.Б.. Чефранов А.Г. Принципы описания и организации асинхронных крупноблочных вычислений в многопроцессорных системах. - Электронное моделирование. 1988. №3. с. 13-17.

17. Макаревич О.Б., Чефранов А.Г. и др. Устройство для распределения заданий процессорам. - A.c. СССР №1410029. БИ. 1988. №26.

18. Мелихов А.Н.. Битюкова С.Л.. Чефранов А.Г. Программа обучения преобразованиям булевых формул к дизъюнктивной нормальной форме. - ОФАП Минвуза РСФСР, № ГР 148.7000.032.

19. Мелихов А.Н.. Битюкова С.Л.. Чефранов А.Г. Программа обучения

реобразованюш логических выражений к базису И-ИЛИ-НЕ. - ОФАП Минвуза СФСР, № ГР 148.7000.052.

0. Макаревич О.Б., Чефранов А.Г. Эффективность параллельных вычислений в многоресурсных многопроцессорных системах. - Электронное моделирование, 1990, №2.

1. Саак А.Э., Чефранов А.Г. Анализ эффективности параллельно-конвейерных

систем. - Препринт №7-91, Львов: ИППММ, 1991.

2. Лугай Н.В., Чефранов А.Г. Об одном подходе к реализации системы

верификации программ. - В кн.: Актуальные проблемы фундаментальных , наук. Меж. научно-техн. конференция, СССР, Москва, 18 окт.-З нояб., 1991, т.1, с. 107.

3. Makarevich О.В., Babenko L.K., Chefranov A.G. Parallel programming

technology and resource management problems. - In Proc. «Parallel Computing Technologies, Novosibirsk, USSR, 7-11 Sept, 1991», p. 495-502.

4. Бабенко Л.К., Каляев A.B., Макаревич О.Б., Чефранов А.Г. Устройство для управления вычислительной системой. - А_с. СССР №1700556, БИ, 1991, № 47.

5. Саак А.Э., Сапрыкин В. А., Чефранов А.Г. О времени решения пакетов задач

в конвейерных системах. - Вопросы кибернетики (М.), 1992, № 174. 5. Makarevich О.В., Babenko L.K., Chefranov A.G. Implementation of the programming language parallel Fortran for multiprocessor system with programmable structure. - Proc. Int. Conf. «Parallel computing technologies, Obninsk, Russia, Aug. 30- Sept. 4., 1993», p. 409-419. 7. Makarevich O.B., Babenko L.K., Chefranov A.G. Integrated Parallel Programs for Universal Multiprocessor System Design System. - Proc. 1st Nat. Conf. Indian Transputer User Group, Pune, India, Sept. 9-11, 1993. 5. Makarevich O.B., Babenko L.K., Chefranov A.G. Algorithm LPT Worst-case performance bounds for two-level multiprocessor systems. - Proc. 8th Symp. Microcomputer and Microprocessor Appl., Oct. 12-14, Budapest, Hungary, 1994. h Chefranov A.G., Saak A.E. On the effective performance bounds for two-level multiprocessor systems. - Proc. 8th Conf. Systems, Modelling Control, May 1-5,

1995, Zakopane, Poland.

). Makarevich O.B., Babenko L.K., Chefranov A.G.Hierarchical structured situations recognition system based on fussy logics. - Proc. Summer Workshop on Computational Modelling and Imaging in Biosciences, Aug. 28-30, 1995, Keczkemet, Hungary. . Babenko L.K., Makarevich O.B., Chefranov A.G. On the algorithm LPT upper bounds for two-level multiprocessor systems. - In Proc. EuroPar'96, Aug. 26-29,

1996, Lyon, France.

;. Бабенко Л.К., Кравченко П.П., Макаревич О.Б., Чефранов А.Г. Архитектура и математическое обеспечение многопроцессорных суперЭВМ. - Таганрог:

ТРТИ, 1992, 154с.

33. Кравченко П.П., Чефранов А.Г. Методы управления ресурсами вычислительных систем. - Таганрог: ТРТИ, 1991,76 с.

34. Мелихов А.Н., Чефранов А.Г. Применение ЭВМ для решения задач

математической логики. - Таганрог, ТРТИ, 1988, 76с.

35. Мелихов А.Н., Битюкова С.Л., Чефранов А.Г. Преобразование логических выражений к базису И-ИЛИ-НЕ в режиме диалога с ЭВМ. - Таганрог: ТРТИ, 1990, 15с.

36. Мелихов А.Н. Барзолевский Ф.Н., Чефранов А.Г. Приведение булевых формул к дизъюнктивной нормальной форме путем эквивалентных преобразований в режиме диалога с ЭВМ. - Таганрог: ТРТИ, 1987,15 с.

37. Мелихов А.Н., Коровин С.Я., Чефранов А.Г. Автоматическое доказательство теорем в режиме диалога с ЭВМ. - Таганрог: ТРТИ, 1990,11с.

38. Саак А.Э., Чефранов А.Г. Оценка эффективности параллельно-конвейерных систем при обработке пакетов независимых задач. - Известия РАН. Теория и системы управления, 1996, № 2, с. 179-186.

39. Чефранов А.Г. Об эффективности алгоритмов адаптивного планирования ресурсов параллельно-конвейерных вычислительных систем. - Известия ТРТУ. Специальный выпуск. Материалы 42-й научно-технической конференции, 1998, с. 101-103.

40. Саак А.Э., Чефранов А.Г. О предельном числе процессоров одной ступени двухфазной параллельно-конвейерной системы. - Известия ТРТУ. Специальный выпуск. Управление в социальных и экономических системах, 1998, №1(7), с. 272-275.

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

Типография Таганрогского государственного радиотехнического университета. Заказ № 160. Тираж 100 экз. 1998 г.

y президиум d A ■■ \ -

\ зш;;| л*IL" -IL SI- ÎMYL

J» uy.iz'/v.. учсяух» ci e r г. y 4

âÂÂMé^

lavK

Ha" UbHu i--^ йздекик ïjAK России ^-----jj

//.- у/- V// -

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ Таганрогский г ос уконный ядлиотеяинческий унивёрсмт^!

¡-¡а правах рукописи УДК 6В1.3Г4

^ /

ЧЕФРАНОВ Александр Г&оргш&ВИЧ

4

МЕТОДЫ И СРЕДСТВА АДАПТИВНОГО УПРАВЛЕНИЯ РЕСУРСАМИ ПАРАЛЛЕЛЬНО—КОНВЕЙЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

ДИССЕРТАЦИЯ на соискание ученом сгитенм йок1орг! технических наук

Специальное ил;

05.13.13— Вычислительные комплексы, сис»"^мы, сети

05. 13. 1Ь- Пр№»енуние вычис /петельной г©х ники, ма I еИа (ического

нояелироеанмя и ма1 ема плческиа истодов в научных исслевованин*

На учные коне ^ль I анты:

доктор техническим наук, профессор цейс ! вит еньный член АЕН РФ и МА£/1

А.N. Мелихов

доктор технических ни^н. прпФр< ■ , «ей« твительыый член МАИ

П.Б.Мак ^ревич

Та(*аняог-| 9Ч>П

ОГЛАВЛЕНИЕ..................................................... Р

ВВЕДЕНИЕ....................................................... £>

;. ОБЗОР ИЗВЕСТНЫХ РЕЗУЛЬТАТОВ И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ - И 1.1«АЛГОРИТМЫ Управления ресурсами вычис/ттильныя систем......20

1.1.1. Од нос i адийные сис г в мы.................................

1.1.2. Многостадийные системы ................................

1.2. Аппаратные средства управления ресурсами .................^

1.3. Средства прсдс! авленмя, преовразования и вериФикации параллельные задании...........................

1.3.1. Средства представления параллельны* заданий ...........

1.3.2. Средства преобразования и вериФикации параллельных

6 2

программ .......................................................

(- 9

1.4. Пос гановка задач исследования............................

2. МЕТОДЫ АДАПТИВНОГО УПРАВЛЕНИЯ РЕСУРСАМИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ

СИСТЕМ ........................................................Ш

■з т

2.1. Сис I емы с одной ступенью процессоров .....................ле-

2.1.1. Оьрайотка потоков многопроцессорный взаимосвязанный

щ

задач ........................................................... 7

2.1.2. Пакетная обработка независимых многопроцессорным задач

Ti

в однородный системах со многими мультипроцессорами ..............

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

мультипроцессорами............................................it

2.1.4» D&p аВотка потоков независ иным многопроцессорным задач в

5 \

многопроцессорной системе с несколькими мультипроцессорами ....

2. 1.5, Овр аьо i пот оков взаимосвязанных многопроцессорные за^ач в системе со многими мульгиприцессорами....................... ®

г

2.1.6. Пакет наи обрйьа тка кезаеисимыя многопроцессорных задач и смс теме с несколькими нуль i ипроцессорами из ненадежных

/0Г

процессоров ..................................................1

2.2. Системы с несколькими ступенями процессоров .............

2.2.1. Пакеiпая обработка однопроцессорных независимых задач в

i Pcj

системе с одним процессором на каждом i_iv!!i?hh.................' "'

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

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

jib

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

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

2.2.5. Пакеiная обраби гка взаимосвязанных многопроцессорных задач.........................................................1'

2.2.6. Обработка потока независимых задач ....................

2.2.7. Сис тема с сет ими мультипроцессоров на каждой с талии при

обработке многопроцессорных задач ..............................

2.2.В. Эксперимент альное исследование мв ухст упенной

(Й

многопроцессорной системы ...................................... J

2.2.5.1. Определение предельного числа процессоров каждой ступени двух с т упенной многопроцессорной сис темы ..........., . . . L3

2.2.3.2. Исследование эффективное1 и двухе »упенной

№

многопроцессорной системы......................................

2.2.9, Исследование эФФективности многоетупенной

многопроцессорной сис. темы ......................................

_ „ \f3

2.3. Выводы...................................................

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

_ , „ \ Ы

о.1. Устройство определении готовности задач к решению .......:

ъ

3. 2. Устройст во «ля айГР узки MHD»• опр оц ее сорных задач на

№

процессоры сис reмы.....................................-.......

/П

3.3. Устройство для определения порядка выполнения задам ......

3.4. Базовая многопроцессорная вычислительная система .........

3.5. Аппаратная поддержка методов адаптивного управления

ресурсами в многостадийны« параллельно—конвейерных системах ....

_ , 2 00

3.6. Выводы ...................................................

4. программные; средства управления ресурсами

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

2 flí

4.1. Язык программировании Параллельный Фортран ...............

4.1.1. Концепций параллельного программирования на основе

__ 10'¿

расширения языка Фортран-77 ....................................

... . 'гп-

4.1.2. Описание транслятора ..................................

4.2. Интегрированная система i ipobk тирования параллельным

117

программ........................................................

111

4.2.1. Описание подхода......................................

72 8

4.2.2. Интерфейс пользователя................................

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

2%Ч

рес урсов .......................................................

4.2.4. Организация вычислений при статическим pai прецеленмм

т

рес урсов .....................................- -.....- -.........

4.2.4.1. Организация межпроцессорных обменов ................

1ЧЧ

4.2.4.2. Управление процессами..............................

4.2.4.3. Технология i iapa л лельного программирования прьч

2 S0

статическом распределении ресурсов .............................

4.3. Принципы реализации операционных систем

ПЧ

параллельно-конвейерных систем .................................

4.4. Разработка i программных средств опт ыммзацш на основе

ц

2 él

аналитическая преобразований ...................................

71 i

4. f.. Прпйрркд правильности ч-правлякншл>: граФпв прпгряин......ч

„ , _ 2Я 4.л. шведа*...................................................

2fäf

3AKnW4FHWF ..................................................

m

/iMTFPATVPA

Î09

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

Акт Уешь-нас Iь ¡емы. Парадne льные ¡л конвейерные вуЧ!Ж литрль.чые системы широко используются цля решения Фундаментальных научных и i грак илческих s а дан , гревующих ьильшого колмч^с тва вычислений при ограничениях hei время выполнения. Принципы распаралмепдаании и конвейеризации вычислений используются на разных уровням вычислительного процесса и в различных комбинациях - от конвейеризации обработки команд в одной iipoueccope (например t In Lei Pentlum) до параллельно-ковейерной оераБотки на уровне ^адач е макроконзейерной сие гене ЕС-2701, Основой использования такого рода параллельно-конвейерных армтект ур являете я

параллельно—t юс ледова г ель на я природа вычислительных пр ou et. cos - Для ускорения вычислений используются как специальные-

параллельно-конвейерные сосредоточенные системы, гак и сети Пот енциально высокая пр оиьвидительность параллельно—конвейерные вычисли тельных систем может &ьиь достигнута лишь при условии равномерного распределения вычислит ельной нагрузки netд >• о&раьа iывающими ус тройствами. Извес тно , что времена выполнения вычислит ельных процессов , как правило, имеют случайный >; ар актер , поэтому наиболее перепек гь*вны aцаптмъкыв методы балансировки нагрузки, используемые, например, ь сетях ЭВМ, Для рассматриваемых в диссертации сосредо гоченных параллельно—конвейерных

вычислит ельны* сис i ем и ce t ей на их основе значимое ть динамического управления Рес урсами, адаптирумщегося к тек ущей Lwi уации еще ьолее bo&pat.тает . Ef-ли в сетях ЭВМ в качестве j юказателя нагруэки вере г ся, как правило, количес reo заданий е ичереди на обработку к соитьетс тв ующей ЗВИ, i о в сосредо(оченных Системах Такой выБор неприемлем и следует работать с Реальной haiр узкой ус1ройс i в, определяемой как доля времени наблюдении, в

6

-: ечение ко» орого ус тройство было занято равотой. В с й у чае решения паке 1 ов задач время наьпюдений Йтсчиты&ает с я от момент а времени начала решения пакета задач. Извес гно, что оптимальное распределение нагр узки между процессорами даже в пррстейЩих ситуациям (например, два идентичных процессора, задачи решаются вез прерываний) относите« к классу ЫР—трудных оптимизационных задач, при этом ценность предвари тельного планирования весьма мала в сипу сл учайного характера 1 введения планируемых процессов. Задачи в общем с л у чае имеют с ложн ун> стр ук т ур у , прецс та ним ую иерархическим информационно-управляющим граФон, вершины которого — подзадачи - мог ут активизирова гьс я при ус 1ановке в единиц у связанной с ними Функции го товности- Пораллельно-коквейерные системы могут иметь разнообразную ар х итект ур у (состоять из одинаковых или однородных процессоров или мультипроцессоров, число которых может &ьл ь 1временным, со цер ж а т ь одну или во лее с т у пеней обработки и I,д.>, что совместно с моделью задачи определяет сложноеI в проблемы управления ресурсами.

& диссертации на основе получения аналитических оценок точноети ^асписан^н решена важная научная задача разработки методов и средств адаптивного управления кес урсами параллельно-конвейерных вычислительных систем разнообразных типов, ггрименимыя в динамик«? вычислений и овеет ¡ечивашщих гарантированное качество эагр узки при малой гр удоемкости использования, что может вы ть квалифицировано как новое кр Упное достижение в развит им еоотве!с тв ушщего на учного направления. Использование предлагаемы* методов (юзволяе т рассматривать вычислительную систему с ограниченными ресурсами кйк В1/?р г уа льну к» параллельно—конвейерную вычислит ел ьн уя* систем >* с неограниченными ресурсами, т.к. отовразение процессов на системные ресурсы ьерет на севя сис тема. Параллельно—конвейерная организация

1

вычислений поддерживается предлагаемыми в щлссертации аппаратными и программными средствами, пр1л этом в качестве элементарного рассматривается процесс:, протекающий одновременно на нескольких процессорах <многапроиессорная задача), например, в режиме ОПИД (одна программа — много данным>, чго позволяй) значительно сократить затраты на управление.

Цель работы. Разработка методов и средств адаптивного управления Fee урсами параллельно—конвейерных вычислительных сие тем, обладающих малой тр удоемкос ты-о и обеспечивающих гаранiИРовамное качество запр уйки. пут ем динамического pací гределения pet- урсрв .

Указанная цель Mot. гигаетс я путем решения с лед ук>ших зауач.

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

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

3, Разработка средств аппаратной поддержки организации вычислений при использовании алгоритмов адаптивного управления f ее урсами-обеспечивающих в рамках модели задачи » ПРедставимой информационно-управляющим граФом, определение готовых к выполнению подзадач на основа вычисления их Функций гоговнос rw, определение очередное i и i/чх выпи .мнения и загрузку на прОЦИшры.

4. разработка tPfui. ih '^"^раммной поддержки организации вычислений при использовании алгоритмов адат явного управпения рес урсами, обеспечивавших возможноеi ь пяедс тав ленин задачи в вире иерархического информационно-управляющего граша, как в текстовой, так и е виз уальной графической Форме, ав гомагические о гображение пользовательских процессов на ресурсы как при статическом, так и при динамическим использовании ресурсов, аналитическое

преобразование пользовательских заданий к наиболее приемлемой Форме, а также возможное ть проверки корректноети заданных опис аний.

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

Научная новизна. Основным научным реиуль)ат ом являете я разяаьо гка теоретических основ, а также аппара гных w программные среде t в поддержки адаптивного управления рес урсами

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

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

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

2. Методы адаптивного >Ч1Равления ресурсами параллельно—конвейерных вычиелительных сиеiем со многими еiадиями обработки и оценки их точное ти для однопроцессорным и многопроцессорных задач, независимым и взаимосвязанных, макетов и потоков, системы при этом

9

маг у t содержа гь в качест не процессоров идентичные и оинородныр му>1Ь i илр оцес с оры.

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

4-. Среде теа программной под дер зеки организации вычислений при использовании алгорит mob адапiивного управпения рес урсами, обеспечивающих возможное¡ь преде гавления задачи в виде иерархического информационно-управляющего гр^Фа, как в текс¡оной, так и в визуальной графической Форме, автоматическое 0|0бражение пользовательских процессов на ресурсы как при статическом, так и при динамическом ио юлъзовании рес урсов, аналитическое преоьразование пользовательских заданий к наиболее приемлемой Форме, а также возможность проверки корректности заданныи описаний.

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

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

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

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

to

организации вычмолмгельныя процессов в napa/i лельно-конвейерным вычислительным системах, а 1акхе позволяют оценивать производи ге/тьность сие i емы в зависимост и от парапет ров системы при выборе параметров системы на з)апе эскизного проектирования.

Предлагаемые 8 диссер тации аппаратные срерс rea поддержки организации вычислений при использовании динамически« адаптивным алгори тмов управления рес урсамн ПРедсгавляют совий комплекс .устройств, позволяющим ь совокупности практически полное »ью переложи гь на аппарат ур у управление i |араллельными вычислениями и т тем самым, сократигь Расходы времени на управление.

Предлагаемые s диссер i <ации программные срэдс тва поддержки организации вычислений при использовании адапт ивных методов управления рес урсами даю i возможное гь преде i веления задач пользова геля в виде иерархическим информационно—управляющим графов , as t ома гически о ¡ отражаемых на сис i емные рес урсы , предоставляй пользова гелю, ]аким отразим, виртуальную

; iapa/1 лельно—конвейерную вычислит ельную систему с неограниченными ресурсами. Ра зр а вот анныь; среде тва преовразования выражений произвольной с тр уктуры по задаваемым пользова i ел ем правилам мог у i бытъ использованы для получения программ с требуемыми свойствами. Разрабо¡анные средс гва аналит ических 11Реовразований логическим выражений и доказа тельсi ва теорем можно использоват ь для t ее гировнин коррек i hol ти i tapaллельных программ.

Реализация и внедрение резуль гатов. Основные Результаты диссер тации получены as тором при выполнении

научио-исследоваjельских и ипытно-кинстр ук юрских ра&от в рамках важнейшей гос йюдже гной и хоздоговорной генатики в соо гве г ствии с Постановлением СМ СССР от 27.0í.e6, N 139-49: Постановлением СМ СССР от 16.06.87, N 675-155; Постановлением АН СССР от 17.10.S5, N 1 005, Резулыa t