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

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- определить предельное число процессоров на УРОВНЯХ для
увеличения пропускной способности системы;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ц-

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

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

Дпоофацид работы. Основные результаты диссертационной работы докладывались и обсухдались на: I Всесоюзной конференции "Проблемы создания супер-ЗВМ. суперсистем и эффективность их. применения" (Минск. 1987г.). Всесоюзной научно-меголическсй конференции "Интенсификация учебного процесса в высшей школе на базе микропроцессорных вычислительных систем" (Воронеж. 1987г.). I-III.V Межреспубликанской научной конференции "Актуальные проблемы разработки автоматизированных систем управления" (Киев. 1987-1989. 1991гг.). Международной научно-технической конференции молодых ученых и специалистов "Молодые учение в решении комплексной программы научно-технического прогресса стран-членов СЭВ" (Киев. 1989г.}. VII.IX-XI Всесоюзном семинаре по однородным вычислительным средам и систоличесхим структурам (Львов. 1988-1991г.г.). Всесоюзном семинаре "Распределенная обработка инФоЬмашіи-IV" (Новосибирск-Горно-Алтайск. 1991г.). I Конференции "Транспьютерные системы и их применение" (Звенигород, 1991г.). Меадународной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях" (Алма-Ата. 1991г.). Научно-исследовательском семинаре лаборатории вычислительных комплексов Факультета ВМ и К МГУ, Научном семинаре НИИ МЕС г.Таганрог. Научно-технических и научно-методических конференциях профессорско-преподавательского состава, аспирантов и сотрулникоб ТРТИ. г.Таганрог (1988-1992)Г.г.

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

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

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

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

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

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

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

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

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

j j

Н., процессоров. .1 = 1.Н. k-l.n.. Система предназначена для реиениі
^Jk _t >

пакетов n=fz.). . из L независимых задач, каждой из которых на .1

-м '/Ровне требуется R. ^ max Н, npou-зссопсв в течение некотоосг.^-.

'J . . Jk

КК 1 . ГЧ . '

) .

заранее неизвестного времени t >0. i-l.L, д = 1.М. Ни один из

^lJ ' .

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

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

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

і=ГЛГ. .і = 1.М. к=1,п . Никакие два модуля-но могут объединять свои

ресурсы для решения залачи z_r i=l,L. На каждом уровне задачи

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

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

что R_t, и t - случайные величины. " равномерно распределенные в

соответствуюших диапазонах 0<В_; ^J?.. 0=1,М.

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

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

ОПИСДНЫ МеТОДИКИ ПОЛУЧеНИЯ ОЦеНОК ВеЛИЧИН ^р5^ггяі/^П^~*'^-

?(i?i)Z?SP(pt), a, v и предельного числа процессоров »на уровнях для исслевуемих классов ПКС.

' 8а втором раздела рассматривается одноуровневая система. содержащая несколько модулей и допускающая мультипроцессорную обработку задачи: М=1. п=п. N .=Н. k=ITn. R=R. r=r.

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

J«o

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

1» Jit »— J і *

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

\c

РотреРнс-сть^І) получено

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

. ГА1 J J 21. ' ГВ1 І j - 2L

^Г(-пс_ІЬ«-.і) ^aiTi S(-nc₂jB-.i) .

j=o .1-=0

гле А, "^У{|Г: B=2r|f".

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

4 ГАЇ і j 21. ГВ1 j j 2L ' (2ГГ! = ⁽"^ ^Сг^^А-^ ^(Щ-і E <-П С^СВ-Л ) .

гле А:т^Ь^(Т-2<1-1/пК>.-В=2У(^.

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

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

процессоров, равновероятно распределенное в диапазоне d В 1.

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

распределенного в диапазоне II т >, m=l.G. Требуется разделить

.все N процессоров системы между этими группами пользователей на G частей (в -я группа обслуживается в ю -й части. m=l.G) так. чтобы качество обслуживания в каждой из частей было одинаковым. Под качеством обслуживания будем понимать вероятность решения пакета из L задач (пропускную способность).

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

R.

a -k=l

іается формулой Н_д = ^ H. m=l,G. Для варианта' обслуживания всех'

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

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

' _b*Vk . -.-' в третьем раздело рассматривается^ двухуровневая система. :одерж.ашая по одному модулю на каждом уровне и - лопускаюшая мультипроцессорную обработку,задачи: М=2. n.= l. Н.,=Н.. .1 = 1.2. - Введем обозначения, используемые в дальнейшем.

2. -naxt. :<.

'J і і

- iM,L . е- =g- Е t. .R.., .1 = 1-.2.

l+maxt_iye.. naxt^e. ' ⁿji*i ^{M M}

t =maxCt. .'>. .1 = 1.2..-

MOJCJ - V і .

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

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

*⁼_i^^1|r_l^^+t-⁽¹"t^):"liE^t^^/a+1'^{i); а<3}-'

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

н;=»ш{[2-і],ь}.-

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

^.^и^аГ.гЧАг^: *»', = ^ьи⁺.Е*и^Кі,^А'і+Н,>і -<3:

_{»>'{[«. f3-14']}}

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

v=a- It. +'й- Et+t fl'-4-)+t ( 1--4- );р-(Е Е t )/fB '+N_>:.

ft-i 2ksl .,1 2 j=lv=l ' ,

Показано, что при- t\ =1. i=l,L небольшая . (0СІ.1оЯ_гЬ1дейсхвийі

, предварительная, обработка . пакета задач -упорядочение задач по

невозрастанию "времен обработки на втором уровне ^t₁₂-^t₂₂-- -^t_vx

приводит в случае ^ ІГН /HI к a=i, а в случае Ч^ГК,/!?^ ^к

,<х<4/3-1/ЗН . Заметим, что при этом нам не требуется знание точных

.времен t. . i=l,L, а лишь их соотношение. .

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

)=0. ^v * J = О * ^v *

H^»in{[2H_t-Ii]. і}: Я>іЬ{[2Н,-у..'ь}. ...

2ля класса ПКС 'Суровєнь=2, модуль=1/1. npoueccop-M/M.
потребность=І/Ю получено ' .

. v=h- Zt+x'4- Е t..R +t ,a-4-">;

N _ \i 2 N ^w U vl max! И
1». = * 2 v =1. 1

p=< Et +.E.t,R ,'iA" +N.V. «<4.

. Li , 12- V.2 ' 1 2 -1 = i . I =1

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

. I. . ' .. І.' .2 1.

^.r-Et-ЛЛг Et- R" . *>=( Е Et R. . уся +Н-): «<4.-

lN-.vltl Zjj . 12 12 *^ ** її і. і, ' 1 2
11=1 21=1 )=11=1

При условии'т-.=т, R =R, к =Н. .1 = 1.2 имеем

\ъ