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

: р. Р> 1

1 I о \> » 1

• ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ТАГАНРОГСКИЙ РАДИОТЕХНИЧЕСКИЙ ИНСТИТУТ им. В. Д. КАЛМЫКОВА

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

Саак Андрей Эрнестович

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

Специальности: 03.13.13. - вычислительные машины, комплексы,

системы и сети 05.13.14. - системы обработки информации к управления

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

Таганрог-1£93г.

Работа выполнена на кафедре математического обеспечения применения ЭВМ Таганрогского радиотехнического института и В. Д. Калмыкова

НАУЧНЫЙ РУКОВОДИТЕЛЬ-

доктор технических наук, профессор, действительный член АЕН РФ Мелихов А.Ч.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор Барский А. Б.,

доктор технических наук, профессор Ланишев к.В

Ведущее предприятие- Институт проблем кибернетики РАН, г. Москва

Защита диссертации состоится " " декабря 1983 г. в и часоь на заседании специализированного совета Д 063.13.02 ис эааите диссертаций при Таганрогском радиотехническом институте им. В. Д. Калмыкова £347915, г. Таганрог, пер Некрасовский 44). С диссертацией можно ознакомиться в-библиотеке института.

Автореферат разослан " ноября 1993 г.

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

А. К. Целых

о

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

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

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

Первый уровень представлен управляющей ЭВМ (HOST-машина). предназначенной для ввода информации с внешних устройств, трансляции с языков высокого уровня, загрузки задачи на процессоры решающего поля (ЕГП. Второй уровень представлен множеством параллельно действующих процессоров РП. На вычислительных центрах коллективного пользования первый уровень представлен множеством интеллектуальных терминалов пользователей, av второй уровень распределенной многопроцессорной вычислительной ■ системой (совокупностью многопроцессорных модулей). С другой стороны ускорению вычислений может способствовать более полное использование Фундаментальных принципов распараллеливания и конвейеризации, что позволяет рассматривать последовательные ступени конвейера как уровни. с параллельно действующими процессорами на каждом уровне.

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

Системы, содержащие несколько последбвательных уровней с параллельно Функционирующими процессорами на уровнях. будем называть параллельно- конвейерными системами (ИКС). Исследованию таких систем и посвящена настоящая работа.

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

Стремление минимизировать время обработки пакета, задач и

ч

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

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

Как правило, количество процессоров и время решения, требуемые пользователю,^ заключены в некоторых интервалах, внутри которых вероятности появления требований мохно считать одинакрвыми (отсутствие предварительной информации о конкретных 'задачах). Представляет практический интерес оценка вероятности Р прохождения пакетов задач (пропускной способности), в системе за заданное время Т. Практический интерес представляет определение такого предельного числа процессоров на уровнях в зависимости от числа задач в пакете. значения границ интервалов и числа процессоров на другом уровне, что дальнейшее увеличение числа процессоров не ведет к росту вероятности решения пакета зада»! и. следовательно, к росту производительности системы.

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

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

заданным требованиям по функцио>*ированию.

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

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

- предложить математическую модель и Формализовать задачу исследования:

- предложить приближенный быстродействующий незадерживаюший оперативный алгоритм для организации эффективного Функционирования ПКС:

- оценить время решения пакета зал&ч:

- оценить эффективность алгоритма:

- оценить пропускную способное,ть системы:

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

- провести экспериментальное определение пропускной способности системы:

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

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

Научная новизна лиссертационной работы состоит в получении детерминированных и вероятностных характеристик эффективности функционирования 19 классов ПКС (из них 13 исследованы впервые) в условиях неопределенности, в разработке алгоритмов управления ПКС в таких условиях и методики выбора параметров ПКС. в том числе:

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

2. Получены вероятностные характеристики процесса обработки для различных вариантов ПКС и пакетов задач, что позволяет .¡-.эирать параметры систем, удовлетворяющих заданным требованиям по Функционированию.

3. Получены границы времени решения для различных вариантов ПКС и пакетов задач как Функции от параметров системы и задач, что

Позволяет оценить абсолютное время Оработки.

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

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

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

На защиту выносятся:

- алгоритм организации вычислительного процесса в ЦКС:

- методики получения и оценки эффективности Функционирования ПКС:

- методики выбора параметров ПКС; ' . . ■ •

- программы имитационного моделирования ПКС.

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

в оценках эффективности алгоритма По. худпему . случаю, гарантирующих конечность погрешности;

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

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

Реализация результатов работы. Материалы ' диссертационной работы использованы при выполнении научно-исследовательских работ, проводимых в НИИ МВС г. Таганрог под руководством члена-корреспондента РАН A.B. Каляева в рамках Государственной научно- технической программы "Перспективные - информационные технологии" (постановление ГКНТ СССР от 10.05.89г. N3021 и по программе Гособразования СССР "Принципы создания универсального сверхпроизводительного супермакронейрокомпыотера с программируемой самоорганизующейся архитектурой , и элементами - искусственного

интеллекта" (приказ Гособразования СССГ от 10.07.90г. N482).

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

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

1987-1989. 1991гг.), Международной научно-технической конференции молодых ученых и специалистЬв "Молодые ученые в решении комплексной программы научно-технического прогресса стран-членов СЭВ" (Киев. 1989г.). VII.IX-XI Всесоюзном семинаре по однородным вычислительным средам и систоличесхим структурам (Львов.

1988-1991Г.г.). Всесоюзном семинаре "Распределенная обработка инФоЬмаш|и-1?" (Новосибирск-Гооко-Ллтайск. 1991г.). I Конференции "Транспьютерные системы й их применение" (Звенигород, 1991г.). Международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях" (Алма-Ата. 1991г.). Научно-исследовательском семинаре лаборатории вычислительных комплексов Факультета ВМ и К МГУ, Научном семинаре НИИ МЕС г.Таганрог. Научно-технических и научно-методических конференциях профессорско-преподавательского состава, аспирантов и сотрулников ТРТИ, г.Таганрог (1988-1992)Г.г.

ПуВ/шяаиии. Результаты диссертации освешены в 7 печатных работах.

Структура и оОт>»и работу. Диссертация состоит из введения, четырех разделов и заключения, изложенных на 192 страницах, содержит 41 рисунок. 2 таблицы, 91 наименование библиографии. 120 страниц приложения, всего 323- страницы.

С0ЛЕР1АНИЕ РАБОТЫ

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

Э. первой раздело на основании рассмотрения существенны признаков ПКС вводится классификация.'позволявшая с единых позици провопить изучение таких систем.

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

Т.к. везде далее рассматриваются системы, имевшие один ти!

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

i *

системой полнодоступной коммутации. обрабатывающие пакет! независимых задач и использующие для назначения задач «i процессоры незадерхиваюоий алгоритм, то в нотации класса ПКС буде] указывать следующие признаки: урдвень. модуль . процессор потреоность. Признаки этих характеристик разделяются запятыми. i соответствующий признак первого уровня"от признака второго уровня-наклонной чертой. Нотация класса заключается в круглые скобки. Эт> признаки могут принимать следующие значения: уровень=1 (оди! уровень). уровень=2 (два уровня); модуль-1 (один модуль). модуль=! (много модулей): npoueccop=l (один процессор в модуле'), процессорен (много процессоров в ' модуле): потребность^ (задач) требуют по одному процессору на уровне). потребность=М (задач! требуют по несколько процессоров каждая'на уровне) .

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

Приводится содержательная постановка задачи исследования. Рассматривается Н -уровневая. HS2, многопроцессорная система,

содержащая на .1 -м уровне п. модулей, каждый из которых состоит и;

____j j

N.. процессоров. .1 = 1.И. k-l.n,. Система предназначена для реденил пакетов n=fz.). , из l независимых задач, каждой из которых на .1

V

ч

-м '/совне требуется В.. ^ тах Н, прэи-зссопсв в течение некотоосг.-.

к« 1 . тч . '

I _____ .

заранее неизвестного времени I >0. 1-1.Ь, д = 1.М. Ни один из

"Л • ' .

процессоров л. -го уровня не может обрабатывать одновременно более

одной задачи. .1 = 1,К. Каждая задача г. должна обрабатываться на л

-м уровне одновременно процессорами любого к -го модуля.

1=ГЛГ. .1=Т7Н. к=Г7гГ. Нихакие два модуля-но могут объединять свои

ресурсы для решения задачи 1=1.1. На каждом уровне задачи

обрабатываются без прерываний. Каждая задача должна

последовательно обрабатываться всеми М уровнями. Предполагается.

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

соответствуюших диапазонах . Ос^^т^, 1=1.1,, Д=1,М.

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

Анализ функционирования ПКС в условиях неопределенности состоит в определении' времени решения пакета задач Тггв,/П1. вероятности Р решения пакета задач за заданное время, эффективности алгоритма по хтлиему случаю «ив среднем

Описаны методики получения опенок • величин

. а. V и предельного числа процессоров »на уровнях для исследуемых классов ПКС.

' 8а »тором раздел» рассматривается одноуровневая система, содержащая несколько модулей и допускающая мультипроцессорную обработку: задачи: М=1. п=п. Н =й, к=1.п. й=1!. г=г.

I »1С \ & • 1

Для класса ПКС (уровень=1. модудь=1.. процессорам. потребность=М) определена математическое ожидание ' НГХ1=2Н/К. дисперсия ОГХТ <N/1* числа одновременно решаемых задач и вероятность полной загрузки системы одновременно решаемыми задачами.

гже Г1- целая часть числа, = ■,. .

Для класса ПКС (урбвень=1. модуль=1. процессорам.

\С

потребность^!) получено

' , »о 4 ' ^С» ^

Для класса ПКС (\-ровень = 1. молуль=1. процессорам. п6требнссть=М) получено

. ГА1 J ] '21- . ГВ1 ] ^ - 21.

} =0 ,1-гО

тле А, У2:/£||Г.;

Для класса ПКС (уровень=1. мсдуль=М, процессорам. потребность=М) получено

4 ГА1 ] ] 21. ГВ1 1 ] и-

' (2ГГ! = ^саЬл Е <"1> 1 •

где (1-1/п)т ).. 2=2/^.

На осндве оценок вероятности разработана инженерная методика для выбора основных параметров системы при проектировании. Лля всех рассмотренных в этом разделе классов ПКС с поношыо имитационного моделирования определена средняя эффективность алгоритма. РРВЬ, что позволило обоснованно рекомендовать его использование ' в операционных системах проектируемых многопроцессорных систем.

Рассматривается класс ПКС (уровень=1. модуль=1, процессор=М, потребность^) и пусть имеется в различных групп пользователей. Задачи пользователей с -й группы для своего решения требуют число

процессоров, равновероятно распределенное в диапазоне II.....II >,

в течение некоторого заранее неизвестного времени, равновероятно

распределенного в диапазоне 11.....ш=ГТв. Требуется разделить

.все И процессоров системы между этими группами пользователей на в частей (в -я группа обслуживается в ю -й части. ш=ГТ5) так. чтобы качество обслуживания в каждой из частей было одинаковым. Под качеством обслуживания будем понимать вероятность решения пакета из Ь задач (пропускную способность).

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

1ается Формулой N^:——N. m=l,G. Для варианта' обслуживания всех"

' " Ж " •

к=1 • . .

задач за директивное звемй, число процессоров Нт. выделяемое в- й

' • аят '

группе пользователей■дается Формулой H = ™ m H. n=l,G.

m о

. ksi

В третьем раздела рассматривается^ двухуровневая система.

;одер».ашая по одному модулю на каждом уровне и - допускающая

мультипроцессорную обработку,задачи: Н-2. п.= 1. lTf=ir. .1 = 1.2.

- Введем обозначения, используемые в дальнейшем.

*Г

2, -naxt. :<в.

_iJ J ■ 1 ■ _

• - t.».t. . ô=g-Et..R... .1 = 1.2.

l+naxt^/э.. naxt^e. 1 nji*i 4 M ■

t ' =naxft. .'>. .1 = 1.2..'

Maxi - - vi.

1=1.L

Для. класса ПКС (уровень=2, модуль=1/1. npoueccop=l/l, п6требность=1/1) получены оценки вероятности решения пакета зздач

при' условии т-т. .1 = 1.2

j ■

И

• Для .класса ПКС .'(уровень=2. модулЬ=1/1. nPoueccop-1/M, потребность^1/11 получено

' ^ . .1

Определено предельное число процессоров на_. втором уровне

• :н;=»1п{[2-^], ь], •

Для'' класса ПКС (У1>овень=2, модуль=1/1, * ripoueccop=l/M. пот'р'0бность=1/М) получено ' •

I ЧЛ г : *>=<Е tu+ Е t.2R; , yà<> : «<3 :

i »1 Zut . ь »i V * 1

м

Для класса ПКС (уровень^?. молуль=1/1. проиессор-м/м. петребност£=1/1) .получено .

У-'п- +Е" С1'-4-)+1 ):>=(£ г '+»_);.

И " и Н ,И гг тг>ох1 И »*»ахг N ■. . м 1 2

Г1-1 21:1 .,1 2 3 - 1 I. =1 ' ,

«<3. ' ' ' '• .

Показано, что при- =1, 1=Т7Г небольшая . (ОСЬ1оягЬ1действий) , предварительная, обработка . пакета задач -упорядочение задач • по невозрастанию "времен обработки на втором уровне ■

приводит в случае ^12£ГНг/1Ь V к <*=1, а в случае к

,а£4/3-1/ЗН . Заметим, что при этом нам не требуется знание точных ' .времен I. . 1 = 1.1., а лишь их соотношение. • .

. •

При условии т=г,.'1Г=Н, .1 = 1.2 имеем. •

Гк1>1т"| г л

; = О. * Д«О " %

Н%вЦ[2Н4^], £}: Я>1Ь{[2Н,.. ь}. ...

2ля класса ПКС ■ "(уровень=2, • модуль=1/1. проиессор=М/М. потребность=1/Ю получено • .

1 ^ 1 *" ' 1

N .41 2 N и а тах! и

1». = * .21=1.. 1

Ь- и

Р=( + . Е* И ,')ДН +'«'): а<4. . 1.1 , 12- 1.2 ' • 1 2 -

1=1.1=1

Лля .класса ПКС (уровень=2. модуль=1/1. проц«ссор=М/М. потребность=М/М) получено.

, • ь -1 .2 1.

1И- . VI ч гК . 12 12 ** VI ъ |. ' 1 2

11=1.- 21=1

При условии' т-.=т, й =К, К .1 = 1,2 имеем

^ 11 г /»Г !■"• ■ Г

¿«о 4 ^ = о 4

■<=»«{«!■ »^{[г-^Х]. [ь^]}}-

Для класса ПКС (уровень=2. модуль='/1, пооцессор=М/М. потребность=М/1) получено

и ь . ь ь

Е ^.И. ,(1-4 ):*>=( Е й. + Е

И 11 И . • 12 т<ах2 И , 11 11 . 12 ' 1 2

IV =г! 21 = 1, 2 1=1 1=1

«<4: ь): Я^.ах^. .тД^Н.К,]. [ь

Лля класса ПКС (*уровенъ=2. модуль=1/1, . проиессов=М/1. потребность=1/1) получено

Ь Ь ' '2 1.

У =тА Еь. + Г*.,-^ ,(1-4-): *>=(£• Е^. ■>"• а<3-

И .4 . тпах1 и . . Ч 1

11=11=1 1 1=11=1

ь}. _ :

• Для класса ПКС <уровень=2. молуль=1/1. проиессор=М/1. потребность:!!/!') получено " х.

и=1 1 = 1 1 = 1 1 = »

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

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

\ч

Хультипроиессорную обработку залачи: Н=2. Н.^Н,. к=1.п^. ¿-1.2.

Для члвсса ИКС (уоовень-2,. «одуль=1/М. ; процессор=1/М. потребность-3/М) получено

и 2 •

г . ^ Ч П К ■ VI 12 2 тах2

1 = 1 2 21 = 1 ;

1, Ь

Г>=( .+ Е ,)/(1+п N ): а<5-2/п,.

11 . VI 12 ' 2 2. 2

Для класса ПКС Суровень=2. модуль=1/М, проиессор=М/М» потребность=1/Ю получено

1 ь 2 ь 1

ЕЬ • t. К. -К 1- П +2С1-1/П П .

N . 11 П И 12 и тах! » 2 тох2,

11« 1 .2 21=1 1

*>=( Е е и ^ 2 •>ЛЯ1+П*нг >: «<б-г/па-1/н4.

1=1 1=1 • ■

Лля класса ПКС (уровень=2. нодуль=1/И. проиессор=И/М. потребность=М/Ю получено

1 ь ' 2 и -у-х я- Еь..и. и.,+2(1-1/п,')ь

. й 11 П Н 12 12 2 тах2

И г» , г 21=1

Е Ег й )/(М1+пгНг>: а<б-2/пг. При условии т.=т; Б.-К. N =п К=Н. л=1.2 имеем

I 1 12 2

[г/Л л- [»"¿Д ' ,--

Г4ГУ1 -Л] -1)

где р=Ц{т-2а-1/п2)г^.

Лля класса ПКС (уровень=2. мрдуль=И/М, процессор=М/И

потребность=М/Ю получено . •

2 ь 2 ь

,В +-=55-2 +2(1-lZn.it +2(1-1/п)Ь .

П И . VI 11 П И . 12 12 1 ТПС1Х1 2 тох2

1 11 = 1 2 21»1

2 1» ' .

Е ЕЦй; .')/(п'N +п Н >: а<Ъ-2/п-г/пг. 4 1

При условии 11^=11. п1Н1=п2Н2=Н, л-1.2 имеем

J2^ ГГ ^ г[4® пгАГ Г" ("4ГТ1 Е (-п'сЦгЬ -.1] -р-(4ГТ! ^ -1J •

jt-2( 2-l/nt- l/n2 )tj

Для класса ПКС (уровень=2. мол>.-ль=М/1, процессор=М/1. потребность-М/1) получено »

2 L L

V=-Aj-Et R +?(1-1/n )t + Et.:

П N il vi 1 maxi . L2

*>=f EttlR + Et >/(п1Я1 + 1): a<5-2/nl.

Для класса ПКС (уровень=2, молуль=М/1. пР0цесс0Р=М/М, потребность=М/1) получено

2 L 1 L 1 V=-=h- Е t R. +4- Et +2fl-l/n )t + (1-4->t ,

П N 11 il N . iz 1 maxi и rnax2,

1 11 — 1 21 = 1 2

Ь Ь

»> =( Et.1RiJ+ E t.2)/fn1Hl + 32>: а<В-2/п1-1/Яг.

i=i i =i

Для класса ПКС (уровень=2, молуль=М/1, проиессор=М/М. потребность=М/М) получено

» = = 4zRi2 + 2a'1/ninmoxl.-

1 ll-1 2 V =1

V

2 L

Р -( £ Et. Е. )/(п N +N,): «<б-2/п .

. п 1 J 112 1

1=11=1

При'условии т =т, R.=R, и N =N, .1 = 1,2 имеем

j j 1 1 z

J2^ гГ J4t® . гЛГ Г; = v j =o

(4Ь>!

гле 1-1/па)т ^ .

На основе оценок вероятности разработана инженерная толика лля выбора основных параметров системы при проектировании. Лля всех рассмотренных в этом разделе классов ПКС с помошьы имитационного моделирования определена средняя эффективность алгоритма РРВЬ, что позволило обоснованно рекомендовать его

.'использование в операционных системах • проектируемых многопроцессорных систем. . ■

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

В приложениях описана организация вычислительного процесса в двухуровневой суперЭВМ с программируемой архитектурой на основе макропроцессорного комплекта СБИС. Функционирующей в многозадачном режиме с мультипроцессорной обработкой задач и -используюшей для распределения ресурсов алгоритн. РЕВ1,; показан практический выигрыш в экономии оборудования от использования инженерной методики; приведены Результаты исследования средней эффективности алгоритма для различных классов ПКС: приведены программы моделирования алгоритма ИЕВЬ для различных классов ПКС: . приведены документы, подтверждающие использование результатов диссертационной работы.

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

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

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

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

2. Получены оценки эффективности алгоритма по худшему случаю гарантирующие конечность погрешности.

3. Получены оценки пропускной способности системы. На основ' подученных оценок пропускной способности разработана инженерна: методика для выбора основных параметров многопроцессорных систе! (число модулей на уровне. число процессоров в модулях быстродействие процессоров, число задач в пакете и т.д.) на этап проектирования систем, удовлетворяюпих заданным требованиям п Функционированию.

4. Получены границы времени решения кля различных васианто

и

ПКС и пакетов задач как функции рт параметров.системы и. задач, что-позволяет оценить абсолютное время обработки; .

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Чефранов А.Г., Саак А.Э. О вероятности соблюдения директивных сроков многопроцессорной системой// Автоматика и вычислит.техника.-1987. -N6. -с. 67-71.

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

3. Саак А.Э. О границах применимости теории систем массового эбслухивания// Препринт N21-89. Львов: ИППММ, 1989. -с/17-20.

4. Саак А.Э. Вероятностный >анализ буферных устройств сонвейерных систем.- В кн.:Молодые ученыэ в решении, комплексной фограммы научно-технического прогресса стран- членов СЭВ. (ёждународная научно- техническая конференция молодых ученых и шециалисюв. Тезисы докладов. -Киев. -1983. -с. 143.

5. Саак А.Э., Чефранов А;Г. Анализ эффективности граллельно-конвейеркых систем// Препринт N7-91 Львов: ШЛММ, 991. -с. 8-14: . "

6. Саак А. Э. Анализ алгоритмов организации функционирования араллельно-конвейерной системы. -- В кн.: Распределенная обработка нформации-ТУ. Всесоюзный семинар. Тезисы докладов. - Новосибирск. -991.-

7. Саак А.Э. Анализ функционирования параллельно-конвейерной яотемы, -В кн.: Высокопроизводительныэ вычислительные системы в правлении и научных исследованиях. Международная конференция. 5зисы докладов. -Москва-Алма-Ата. -1991.-е. 51. *

.. Иа работ, выполненных в . соавторстве, ' в диссертации

1<5

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

АСсс,

оп трти: зал. 496 т*р. ¿о шю