Методы и средства адаптивного управления ресурсами параллельно-конвейерных вычислительных систем тема диссертации и автореферата по ВАК РФ 05.13.13, доктор технических наук Чефранов, Александр Георгиевич

• Чефранов, Александр Георгиевич
• доктор технических наук
• 1998

Оглавление диссертации доктор технических наук Чефранов, Александр Георгиевич

задач

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

Ti

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

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

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

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

5 \

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

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

г

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

/0Г

процессоров

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

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

i Pcj

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

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

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

jib

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

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

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

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

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

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

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

(Й

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

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

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

№

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

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

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

_ „ \f3

2.3. Выводы

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

_ , „ \ Ы

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

ъ

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

№

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

/П

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

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

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

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

_ , 2

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

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 ы pa&oiь! внедрены в х / д раВотах 51119 oí 15. 03. 91

с НИИ ЗВМ, г, Минск, "Ланка-УН" с в/ч 12462, г. Москва, "Ларика" по решению ГВПК СМ СССГ 01 24.04,91, ОКР "Солвейко ЗФ,[ указание N 150/01/96/541263 ог 20.11.96, поддержанном РФФИ проекте "Алмаз" N 96-01-01651, распоряжение N 96-1-10/30 от 4.04,96, поддержанном РФФИ проекте N 94-01-00695,

Внедрены и использованы следующие результаты

1. Ал ¡'ори г мы ада! 1 гивного управления рес урсами параллельно—конвейерных вычислительных сис!ем, позволяющие в динамике вычислений с гарантированной погрешнеетью о го&раха ть задачи на процессоры.

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

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

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

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

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

выражения, в три числе, программы, к тревуймой Форме» 7, Ci/ic i ема аналитического преобразования логическим выражений и докавательства теорем, позволяющая iест ировпiь коррек(мое гь параллельных программ.

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

Апробация Рабо ты. Основные рез у ль та ты дисеер гаиии предетавлены на Всесоюзной школе-семинаре "Разработка и применение а народном х оз яйс тве ЕС ЭВМ" (Кишинев, ! 9S5S; I Всесоюзной конференции "Проблемы создания супер-ЭВМ, с упер—систем и эффективное гь их применения" (Минск, 1987); Меж д ywapодной нйучно- т ехнической конференции "Акт уальные проблемы

Фундаментальных наук" (Москва, 1 991); на Международных конференция* "Рас аЗ1 el Computing Technfilogies" (Новосибирск, ХЩ91; Обнинск, 1993? С.-Пе1ербург, 1995); на Национальной конференции Indian Transputer Liber Br oup CPune, India, 1993); на S-Lh Symposium on Micr ocomputer and Mi cr oprocesbor Appl icati oris (Budapest, Hungarу, 1994); на S-й Международной конференции Informati on, Model 1i ng and Cuntг ol (Zakopane, Pol and, 1995)i на Международном семинаре Summer Workshop on CumputaLianal Modeling and Imaging in Biosciences (Kecskemet, Hungary,1995)i на Международной конференции E"ur uPar '96 (Lyon, Fr eince, ¡.996) ; нл научноеехническом семинаре "Многопроцессорные вычислит ельные сис темы" (Дивноморск, 1996); на конференциях

профессор cko-преттодавтельского сос тава ТРТУ (Таганрог, 1995. 1996).

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

т

авторских сбиде»ельс гва, 2 программы зарегистрированы в ОФАП Иинв у & а РСФС Р.

С1р УК г ура и обьем диссер тации. Диссер гация состой г из введения, четырех разделов, заключения и приложений« тексI изложен на 245 страницах, содержи! ЪЧ рисункО , 1 таблицу, список литературы на 277 наименований.

Содер жанне

Во введении обоснована ак. I уальность ! (Редс тавляемых исследований, сФормулированы цели и аадачи, решаемые в работе, приведены основные положения, выносимые на защит ут кра тко раскрыто соде?р жаиие разделов диссерт ации-

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

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

вычислит бпьныу. сет ей с одной и несколькими с; алиями о&рабо 1 ни.

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

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

При обРаеоIке заиач на многопроцессорных сис т емах мог ут выть рассмотрены различные уровни параллелизма - 1ак называемая

зернисIость, Режим решения наборов независимых задач может выть рассмотрен как крупнозернистые вычислении, а взаимосвязанных задач - как среднезернис * ые. При зт ом Решение совокупности независимых задач, каждая из кот орых преде гавляет собой набор в заимосвязанных подзадач может рассматриват вся как решение набора независимых задач (при распределении ресурсов на уровне задач), либо как решение наворот взаимосвязанных задач (при распределении рес урсов на уровне подзадач) . Каж пая задача нажег еыIь сложной, структурной, и требовав для решения несколько процессоров. /»ибо *е преус гав л ять собой последоват ельный процесс , выполняемый на одном процессоре.

Расемот рены методы адап гивного управления рес урсами одност упенных и многое Iупенных параллельно-конвейерных

вычислительных сис тем.

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

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

Для многое г упенных ммогопроцессорных Исследованы с л учаи, когда на каждой ступени находит ся пи одному и по несколько процессоров, исследованы режимы оьработки паке гов и по 1 оков независимых и взаимосвязанных много! )Роцес сорных задач. Экспериментально ( на имитационной модели) исследованы двух- и многост упенныв параллельно—конвейерные вычисли тельные системы.

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

позволяют проводи iь сравнение их эффективное га и оценива гь производительность сис тем, использующих э~! и алгоритмы.

В третьем разделе рассмогрены вопросы разрабогки средеre аппарат ной поддержки мегодов адаптивного управленин рее урсами. Лля сис ген с одной ст адней обработки при решении наборов взаимосвязанных задач можно выделить три основные проблемы: определение задач, гою&ых к решению в соогве гетвии с граФом взаимосвязей, определение cfism^ го говых к решению задач очередной (например, по алгоритму FBL-PR), выделение задаче конкретных процессоров и назначение ее. Кроме i ого, архитектура сис темы на ступени должна ьыть приспособлена к рассмотренным выше методам управления ресурсами. Предложены устройства для реализации этих проблем«

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

Разработан компилятор для языка парадлельного

программирования на основе языка Фортран—77 для разраватывавшейсн в НИИ ИВС при ТРТУ многопроцессорной сис темы, учитывавший специфику ее архитек1уры.

Разрабо гана гак¡s интегрированная система прорю ¿кования параллельных программ, предоет авляющая пользователю возможное i ь иерархического представления своей задачи в виде совокупноети инФормационно-управля^щ^х граФрё подзадач, причем кахда я вершина-подзадача может бы i ь, в свою очередь, задачей, представимой граФом или же терминальной вершиной, т.е. программой, нагмлсанной на каком-либо последовательном языке программировании, и реализуется в режиме SPMD.

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

16

11реобразовыва гь выражения, в том числе, программы, к тяее уемой Форме*

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

В заключении сформулированы основные результаты, полученные в диссерIации.

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

1. обзор известных результатов и постановка задач исследования

Рйь#в!/1 i ие вычислит ельной темники связано с необходимостью решения все волее сложных проблем, встающих перед человечеством ит в евию очередь, обуславливает постановку таких задач. К задачам такого типа относятся, например, задачи расчетоь для ядерной Физики СI3 * Задачами, порожденными вычислительной техникой, являются, например, ьадачи noti роения тренажеров, виртуальной реальности С2,33. Одним из главным критериев эффективности вычислительных систем являете я им производительность (

ьыс тродейс твие) С 4 3. Пути повышения производительности: поднятие тактовой частоты раьты процессоров и периферийного обор удования, например, ряд процессоров Intel 60x36, а также распараллеливание вычислений — на уровне выполнения команды (VLIW—архитектуры, конвейерные процессоры С61), мелкозернистый параллелизм — распараллеливание выполнения команд í с ис т одические пРоцессоРыСТ], SIMD-i 1РоцессоРыС БЗ ) , среднезернис тый параллелизм -

распараллеливание на уровне ьлоков программных кодов, и тераций циклов( [9,101) , кр упнозернис тый параллелизм íкр упноблочное распараллеливание) — на уровне подпрограмм, подзадач или задач пользователя С113. В настоящее время развитие вычислительны* систем идет по всем этим направлениям, включая как iювышени^ тактовой час готы, так и распараллеливание вычислений на всех уровнях - о? микрокоманд до организации нультизадачным режимов обел уживания. 01 ме тим также, что распараллеливание повышает надежность и точноет ь вычислений. Максимальный зФФект от распараллеливания получается в случае, если в течение времени выполнения задания все параллельные г :ру,6оры выли заняты вычислениями, го есть работали без простоев. Некоторые простои. связанные с разгоном или ос т анивкой конвейера, взаимной зависимостью выполняемых операций и т.п.С 113, избежать невозможно,

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

с временами выполнения соответственно "Ь =1 , 1: =2, то при

1 ^ 3

назначении первых двух заданий на первый процессор, а третьего -на второй в момент времени О, комплекс работ будет завершен к моменту времени 2, а при назначении первой задачи — на первый процессор, а второй и третьей - на второй процессор тот же комплекс задач будет решен к моменту времени о. Таким образом, при использовании параллельных приборов важную роль играет порядок выполнения работ, определяемый алгоритмом управления ресурсами. Алгоритмы управления ресурсами реализуются либо средствами системы, лиео же это воз лагается на прогр аммиста. В пос леднем случае в языкам параллельного программирования должны иметься конструкции. позволяющие поль зователю осуществлять управление ресурсами. Если же управление ресурсами берет на себя система, то необходима программно-аппаратная поддержка реализации таких алгоритмов. При этом времена выполнения заданий можно считать известными только в случае распараллеливания на уровне микрокоманд или команд (мелкозернистое>, в остальных сл учаях времена выполнения зависят, как правило, от исходных данных, априорные оценки времени выполнения являются приближенными и в ряде работ предлагаются подходы к их получении) Г12И. Известно Г133, что задача построения оптимального по критерию быстродействия многопроцессорного расписания даже в простейших случаях (например, два идентичных процессора) относится к классу МР—грудных, т.е. алгоритмы оптимального ее решения имеют тр удоемкость, растущую

экспане»(циально при Увеличении числа распределяемым заданий. В случае мелкозернистого распараллеливания подлежащие распределению заданий иного, в случае средне— и крупнозернистого распараллеливания заданий значительно меньше, но их времена заданы неточно, либо же совсем неизвестны до реализации вычислений. Поэтому мы будем рассматривать только простейшие стратегии распределения гееypcos, не обязательно приводящие к оптимальным решениям, но применимые в Реальных условиях ограниченности времени для принятий решения и временной неопределенности. В нижеследующих разделам 1.1—1.3 представлены основные известные результаты по алгоритмам управления ресурсами параллельным систем, аппаратной и программной поддержке и>; реализации. Р разделе 1.4 сформулированы нерешенные проблемы и поставлена цель настоящего исследования.

1.1. Алгоритмы управления ресурсами вычислительных систем

Основные принципы распараллеливания - этп собственно распараллеливание, когда имеется множество подлежащих выполнению работ и множество приёоров для их обработки, причем готовые? к выпапн&нмю работы могут выполняться любыми приборами, и конвейеризация, когда одна и та же работа должна быть последовательно обработана специализированными прийорами первого, второго и т.д. уровней. Для совмещения обоих этик принципов в одной модели можно считать, что приборы разбиты на классы прийоров первой, второй и т.д. стадий (ступеней, уровней), а каждая задача в общем случае состоит из ряда последовательно выполняемых подзадач, каждая из которых должна выполнятьс я приборами соответствующей стадииГ 14-16П. Приёоры каждой стадии могут быть идентичными Г171, однородными С!8] ( сравнимыми по производительности, например, процессоры ряда Intel>,

неоднородными Г191 (специализированные процессоры, имеющие

2С

различиуш производительное ть на различных задачах). Кроме г ого, при Воры , в с вон» очередь т мог у г вы ! ь параллельными процессорами ( мультипроцессорами), как, например, в случае системы Cedar состоящей из мультипроцессоров С211 и др, Простейший вариант предполагает независимость задач, их ' одностадийность, однопроцессорноеть задач (каждой задаче для решения тре&уется только один процессор), идентичность процессоров, каждый из которых яеляегся t foe ледова гельным овра&а гыванн#им т тройством. Такие характеристики мы будем считать заданными по умолчаний; все изменения вудем ивно указывав.

1.1,1. OpHot. 1 адийные сие темы

Вопросы управления рее урсами при решении независимых однопроцессорных задач рассмотрены в работах Г 22-6"]. Ь Т.221 показано, что при назначении задач в произвольном порядке на освовождающиеся процессоры (алгоритм FCFS- First - Cume - First Ser ved) имеет нест о

Т(П) < (2-1/п) Т0(П) для любого пакет а И неза&исмых зс1дач, Т(П) - опт имальное время выполнения пакета заданий П, Т fib - время, пол ученное при использовании i ip ив лишенного алгоритма, п чис л о идентичных

процессоров. Ей «и же задачи предвари гельно упор ядочены по невойрас t анию времени решения, т о при назначении и* в \ аком порядке ( алгоритм LFT -Longest-Processing-Times—f irsfc) справедливо

Т. .Т(П) < - ~ 1 Т.(П). С i. i)

LFT ^ on Q

В Г233 показано, что если длина LPT-^Расписамия пяев^шнег 3/28, где

•г1 — it. /п, L - число задач пакета 11, L. - время решения i— й

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Чефранов, Александр Георгиевич

4.6. Выводы

Таким образом, з раздела рассмотрены вопросы программной поддержки адаптивного управления ресурсами параллельно-конвейерных вычислительным систем. Конкретно, изложены концепция параллельного программировании на основе расширения языка Фортран-77, описан гранеля гор. Описана разрабо ганная сис тема проектирования параллельных программ, использующая иерархическое граФовое представление программ, рассмотрены вопросы ее реализации в системах с динамическим и статическим распределением Рес урсов, система апробирована на системе Р->СиЬе Фирмы РагвуЬес на основе транспьютеров Т-Б05 на примере задачи расчета гидродинамических характвристик летательных аппаратов. Разработана система аналитических преобразований выражений, построенных по правилам, задаваемым пользователем в виде сингаксических диаграмм; правила преобразования такхе задаются пользователем. Такого рода сис т ема преобразований может быть использована для оптимизации параллельных программ при представлении их выражениями в соответствующей алгебре. Эта же система, а также разработанные программы приведения логических выражений к базис у И-14ЛИ-ИЕ и к дизъюнктивной нормальной Форме могут быть использованы для анализа корректности управляющих граФое параллельных программ.

ЗАКЛЮЧЕНИЕ

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

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

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

2. Разрааотаны аппаратные средства поддержки адаптивного управления Ресурсами параллельно-конвейерные вычислительных систем, обеспечивающие в рамках модели задачи, представИмой информационно—управляющим граФом, определение готовым к выполнению подзадач ь-процессоры, включающие устройство определения задач, готовых к Решению в соответе гвии с грйфом взаимосвязей, определения среди готовых к решению задач очередной задачи в соотьетс1вии с алгоритмом FBL-PR, считающим "большие" задачи имеющими более высокий абсолютный приоритет, выделения задаче конкретных процессоров, а т акже г ¡редложен.* с тр укг ура вазовой вычисли тельной сис темы, использ veмой в качестве стУпени параллельно-конвейерной вычислительной системы.

3. Разрабо таны программные средс rea поддер жки адаптивного уПРавления ресурсами параллельно-конвейерных вычислит ельных систем, обеспечивающие визмохкооь предетавленин задачи в виде иерархического информационно-управляющего граФа, как в текстовой, iак и в виз уальной графической Форме, ав гома тическое отображение пользовательских процессов на ресурсы как при статическом, так и при динамическом использовании вес урсов, аналитическое преобразование пользоват ельских заданий к наиболее приемлемой Форме, а также возможное гь проверки корректности заданных описаний, включающие систему программирования на «зыке Параллельный Фортран, ин t егрированную среи у виз уального проектирования иерархических параллельных программ, ориентированную на мультитранспьютерные сис темы, сис тему аналитического преобразования выражений (в частности, программ) произвольной с тр укт уры в соотее(с твии с произвольными правилами, сис тему приведения логических выражений к базис у И-МЛИ-НЕ и приведения их к диз ьюмк t ивной нормальной Форме, чю может быть использовано для автоматического доказательства' теорем и киееек гности графовых параллельны;-; программ.

4. Раэравотайные ь диссер т ации мет оды и средст ва адаптивного управления рес урсами нашли ПРакгическое применение в НИИ MPC пей

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

Результ аты работы использованы в НИИ МВС при ТРТУ, г. Таганрог, НИЦЗВТ, г. Москва, ТАНТК" им. Г. М. Бериева, г. Таганрог', а также в учевном процессе ТРТУ на кач>едрах вычислительной техники и математического обеспечений и применения ЭВМ в лекционных курсах "Арх итект ура и математическое обеспечение супер-ЭВМ", "Архитект ура вычислительных сисIем", "Параллельное программирование", "Системы Реального времени", Опубликованы 3 учебных пособий: "Методы управления ресурсами вычислительных систем", "Архитектура и математическое обеспечение многопроцессорных с упер-ЭВМ",

Применение ЭВМ для решения задач ма тематической логики".

Список литературы диссертационного исследования доктор технических наук Чефранов, Александр Георгиевич, 1998 год

ЛИТЕРАТУРА

1, Рэзби В. Моделирование плазмы и рэг чртныр задачи >йпррнг.й Физики. — В кн.: Высокоскоростные вычисления. — Ппя рол. Я. Ковалика. - М. : Радио связь, ?9Яй, с.

Литвинцева Л. В. Виртуальная реальность - нпвый шаг- в технологии человеко-машинного вааимодействия: концепция и использование. — Известия РАН. Теория и системы управления, 1 99о, N -. 173-1 Я7. 3, Яа—Аео K.M. Виртуальная реальность, или Понедельник начинается. . . - Мир ПК, 199е;, n 1, 173~1P3i; N 7. 1^4-17^.

я. Вайеадян А, С. т Коровин А.и, Удалое R.Н Эффективное Функционирование управляющих Вычислительных систем. — М.i Радии и связь, !9Я4. - 37В г.

э. Скворцов С.В. Оптимизация кода для супеескалярный процессоров с использованием дизъюнктивных граФов. - Программирование, 1 , ^

2, с. 41-??.

Хорошевский P.P. Инженерный анализ Функционирования вычислительных машин и систем. - М, ; Рацио и сеяаь, 19Я7. — 7. Sednkhin S.R, Sy^toJ ic array architecture fnr t ио-di mensi nnifcl discrete Fourier transform. - Proc. Toint Tnt. Con-f. ОП Vector and ParaJ 1 el Ргбге??, , Zuri rh . Pwi tzerl and , Pent. 1 0-t 3 , 1 99o. CONPAP 90 - VAPP 4, Lact. Notes Comput. Sei., Fd. FM.tr kh art H. , W Berlin, SprSnger-Verlag, p. 682-A9J.

Я. Головкин Б.А. Параллельные вычислительные системы. — M.iHavKa, J 980. - f>i9 c,

9. Regua J - , Mrßrsvi J . K. The Pi erewi re Пд+а-М nw Arrhi tpcturp; arChi tectt-r al concepts. - TPFF Trans. Comp. , 1 9ЯЗ, v. C-37, N fi, p.423-438.

10, PoJ ychronopoul 05 C.D., tiuck П.Л., Padua П.А. Utilising mul t S di mensi onal I о op paral } el i ^m \ n 1 arge c;ral e рвга11 e1! processor systems. - TFFP Trans. Comput. , 1989, v. ! Я, M 9,

p.120O-129&.

11. Элементы параллельного 11Рограммирования, — Под ред. Котова Б.Е., М.:Радио и связь, 1983. - 244 с.

12. Головкин Б.А. Рас че г макак терис тик и планирование параллельных вычислительных процессов. - И.sFaflno и связь, 1903. - 272 с.

13. Гари М. , Дюнсон Д. Бычис ли тельные машины и тр уднорещаемые задачи.- М. : Мир, I9S2.

14 ¡, Блинова Л.М. , Пьявченко О.Н. Синтез структуры специализированной вычислит ельмой сис темы с ярусно-конеейерной □ьрёбиткой информации по крит ению баланса времени. - Элек т«анное моделирование, 1991, т. 13, N 2, с. 99-101,

15. Handl ег W. , Mi г enkov N. N. Mul L i рг ocessor s: «¡ту we favour pyr ami ds? - Fr oc. Int. Cunt. "Far al J el Coj»puLi rtg Tec) mo J oy i es, Obninsk, Russia, Auq. 30- Sept. 4, 1993", Ed. V.E.Maiyshkin, Computing Center , Novosibirsk, Russia, 1973, v.l, p. 1-24.

16. Валаев Г.Н. и др. РеконФигурируемая вычислительна« среда в интеллектуальной системе управления автономным ЛА. - Известия РАН. Теория и системы ^правления, 1995. N 4« с.234-245.

17. Еереинов Э.В., Хорошевский В.Г. Однородные вычисличельные сис темы. - Новосибирск: Наука, 1970. - 319 с.

18. Каган Ь.М. Электронные- вычислительные машины и системы. - П.: ЭнергоатомиздаГ, 1985. - 592 с.

19. Семердхян М.А. , Налбандян Ж.С. , ГаспаРян Л.К. Принципы работы и система программного обеспечения МП ЕС 2700. - М.tНаука. !988.

20. ГХ/5ег ies Ar chi tectиге Manual , A11 i ant Computer Systems Cur p. , At_Lon, Mass.« April, 1935.

21. Пяангишьили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с оьшим убавлением, - М.; Энергоатомиздат, 1983. - 312 с.

22. Бг aham R.L. Bounds on multipr licensing Lining anomalies. SIAM

3. Appl■ Hath. , 1969, v.17, N p. 416-429.

23. Cu-f-filian E.G., Leung Л.Y.-T. , SI ut2 D. On the optjmality of fdbl heur i ь!Л св -fur schedul i ng ai >ü &t or age all ucati on pr fbl ems. Found. ConLr. Eng. (ERL), I97S, у.З, N 4, pp. 161-169.

24. Бакенрот В. Ю. Об еФФекiивности одного алгоритма построении расписания. - Киберне гика, 1930, N 1, с. 140-143.

25. Трусов С.С. Об эффективное i и простых диспе î черов. - Иавес ги« АН СССР. Техническая кибернетика. 1973, N 4, с. 150-160.

26. Бакенрот Б.И. Исследование и р азработ ка алгорит мов опера тивного диспег чирования задач в mhotoi ipoueccoPHwx lmc i емах паке iного iипа. - Дисс. канд. iехн. наук, Таганрог: ТРТМ, i97S. -17В с.

27. Бакенрот Б.HJ., Макаревич О.&. Два алгоритма диспетчи^ования задач для однородных вычис лит ельных сис i ем. - В кн. s Гиьридные вычисли тельные машины, Киев, 1977 т с. 160-163.

20. Cof f mar* Е. 6. , Gar еу M. P. , J ohitbon D.S. An appî Ration uf bin-pac ki ng Lo muí t i pr ocessor scheduling. - SIAI4 J. Compot., 197в, v.7, N 1, p. 1-17.

29. Карелин Б.П., Ковалев С.M. Об одной задаче упаковки нескольких рюкзаков. - Известия СКИЦ ВШ. Технические науки, 1980, N 2, с. 21-23.

30. Спеснвиев A.B. Погрешнисгь некоторых приближенных алгоритмов составления многопроцессорного расписания. - Известия АН СССР. Техническая ки&ерне тика, 1985, N 6, с. 22-28.

31. Бакенрот В.№., ЧеФранов A.C. О верхних границах LPT-расписаний. — As томатика и телемеханика, 1981, N 9, l -173-177.

32. ЧеФранов А.Г. Исследование и разрабо тка алгорит мое оперативной загрузки многопроцессорных вычис ли i ельных синел со множес твенными iюiоками команд и данных. - Дисс. канд. техн. на ук,

Таганрог-; ТРТИ. 1984.

Вакенрот В.Ю. , Макарекич П.Б. , Чрйрйнпй А.Г. П верхний Границах L Р Т—расписаний. - Известия СКНЦ TWt. Технические науки, (933, N 4,

34. Кова ленко Н. С. Пб одной иоде ли системы пард л лелкныу вычислений. - В кн.i Параллельиое программирование и высокопроизводительные системы. г1ат. Всесоюзной конференции. Ч. Новосибирск: ВЦ СО АН СССР, 19SO, с. 145— 15t.«

35. Шахбазян K.P., ТУшкина Т.А., Сохранскдя P.C., Товкач Л.М. Эксперимент по реализации алгоритмов лиспетчеризаиии для многопроцессорных систем. — Управляющие системы и нашины, N 3, с. 94-05,

36. Шахбазян К.В*, Tvuikhhb Т. А., Сох райская B.C. Статистические испытания различных алгоритмов диспетчеризации. — Программирование, 1976, N 4, с. 9I-100.

37. Ma кс имен ко В A.B. Анализ алгоритмов диспетчеризйшии яйпйч мультипроцессорной ЭВМ. - Vnp аелсистемы и naitiWHW, 197В, N 3, с. 62-68.

ЗВ. Канмелал с. А. , Малых О. Н. Классы расписаний i/t алгоритмы и"? построения. - В кн. г Автоматизированные системы управления и приборы автоматики, Харьков; ХГУ, 1979, N 51, с. 69—75.

39. Тиц П.Г. Организация параллельных вычислений на многопроцессорных вычислительных системах. - Авторрф. канд. дисе-- М.s МЭИ, 1975.

40. Канведал С.А. Вычислительные алгоритмы решения ®алач теории расписаний, - Известия АН СССР- Техническая кибернетика, 198?, N 3, с. 42-51.

41. Канцедзл С.А. Эффективные алгоритмы упорядочения Работ р многостадийных производственных системах пйсКРеТного типа. — Лис-, докт. техн. navii, Харьков? ХАДИ, 199'. - с.

42. Пп-F-f man F. R. , Sethi R. ft general i zed hound on LPT чрпнрпг! ng. - Pror . Int.. Bymp. Comput. Peri „ , Mndel 1 i ng and Fval t tat i nn , Marrh, 197A, p. 30A-317.

43. Астахов А-Я- К вопросу о граница« оФФективности многопроцессорных вычислительных систем. — йвтондтмка и телемех аника, 1975, N Ь, с. 132-137.

44. Oar-Fl F. М. , Kar ni R. ft, ft hybr i rí al gor i thm for i ndependent-tasks paral 1 el machi ne schedul i ng. - Omega, 1 9RO, v. я ч N 2 , г* -239-242.

45. Хорошевский Р. Г, Алгоритмы Функционирования однородных универсальных вычиг лительных сигтем. - Автоматика и рычи-литрльная техника, !972, N с. 35-4!.

46. Голоскокова Т. М. , Хорошевский В. Г, Алгоритмы Функционирования однородных универсальных еычиглительных систем в простейших ситуациях. - В кн.: Вычислительные системы, Новосибирск* ИМ СП fiH СССР, 1970, вып. 39, с. 15-2S.

47. Карский ft.В. Автоматическое распределение работ Mp*nv лв\1мя вычислительными устройствами одинаковой производительности. — Известия АН СССР. Техническая кибернетика, (9АЯ, W 4, с. 32-ЗЯ. 4R. «a-fura D.J - , Bhen V.Y, Ta^k яг herís ti i ng on a muí t i pr nreeeor в-ystem with independent memorier. - RIAM Л. Comput. , 1977, v. A, ftt t, p. ÍA7-ÍR7.

49. Барский А,Б. О построении диспетчеров для еычиглительных систем.-Известия АН СССР. Техническая кибернетика, 1971, N 1, г. Í 13-/ÍЯ,

50. Tbarra О. Н. , Ki m С. F. Heuri Stic a] gori thfn=i f or srhedul i ng

i ncíepeniient t asks nn non j dent i cal pr ocessörs . —J. ACM . 1 977, v. 74 , N 2, p. ;?ftO-2R9.

51. Романовский И,В,, Христова Н.П. Решение дискретных минимаксных задач методом дихотомии. - Журнал вычислительной математики и

математической Физики, 1973, т. 13, w 5, с, 1700-1209,

52. Макаеевич О.Б. Методика разделения задан на части дпя Решения их на цифровой ваичиспительной иададне, — В кн. : Цифровые модели w интегрирующие гтруктуры, Таганрогi ТРТИ, 1970, с. 700—707.

53. Ла-f-fe J.M. Bounds on the Schedul i ng o-F typed ta^ks pys-f-^rrt. MIT Lab. Comput. Sci . tecbn. Memo., L97S, N Hi, p. 1-25.

54. Chreust S. , Muhl bacber J. Ri vai 1 i og mul 1" i processor organi?ation — a novel approach to рег-f ormance Increases. — Euromicro J., 5 979, v.5, N 2, 65-72.

55. Бондаремко А.Т., Сапатый П.С. Алгоритм распределения независимых Работ на пераллельно работающие устройства. — Известив АН СССР. Техническая кибернетика, 1975, N 4, с. 101 — 103.

56. Шишкове кий Г. \Л. , Компанией В - И. Распределение независимых задач по вычислительным центрам. — В кн.i Исследование операций и АСУ, Киев, i979f N 13, с. 60-63.

57. Каспшицкая М. Ф. , Сергиенко И. в. к вопрос у о планировании процесса задач по комплексам ЭВМ. - Кибернетика, J 97(7, N 5, г, 41-45.

58. Гаврилова Н.А., Морозов А.А., Цыцурин B.F. Пб одном классе задач оптимального распределения ресурсов вычислительных грепгте. - В кн. s Программно-технические комплексы реального времени, Кие?;, 1979, г. J 16-129.

5*?. Gopzales т. , Ibarra П.Н. , Sahni 9. Bounds -for LPT schedules o-f honidentical uni-form processors. — S1AM J. Comput. , (977, V. 6, N 1, p.155-166.

60. Cbo Y. ,Rabni Bounds -for ] i st srbedi.il e^ on nni -f orm processors. - SIAM J. Comput., 198C, v. 9, N t, p.9t-103.

61, Еакенр&т R.K!. Алгоритмы функщлондаования неоднородный вычислительным систем. - Автоматика и вы чис лите л ь на я техника, 19R1, N 1, С. п4-А5.

62- КОПНИНСКИЙ F. А. Пб О он пн аЛГОРИТМР РР ШРНИЯ ЗалаЧИ ВЫбОРВ. ~

Журнэ п вычиг лительной математики и математической Физики, 196R, т. Я, N 6, с„ 1383-1304.

63. Власенкп H.A., КРаюхика Т.С. Пб алгоритме распределен ия независимых задач по ÜBM. - Упгавляннцие системы и машины, 1979. N 2, с. 32-34.

64. Барский А-Б. Минимизация числа эычислитрлей при реализации вычислительного процесса в заданное время. — Известия АН СССР. Техническая кибернетика, !968, Мб, с. 69—74.

65. Бенкова Н.Б., Тушкина Т.п., Шах базян К.Б- 0 расписании, нинимизирующем число процессоров однородной рычис лительной системы. - Известия АН СССР. Техническая кибернетика, 1971, N 5, С. 115-117.

¿6. Кикнядзй Д.А. Метод анализа структуры параллельных алгоритмов, реализ^мых на ОБС. - В кн. s Вычислительные системы, Трvn>,¡ симпозиума^ Новосибирск; ММ СП АН СССР, 1967, с. R9-96. 67. Седухина Л.А., Хорошевский Б.Г. Стохастические алгоритмы Функционирования однородных вычислительных систем. — Автоматика и телемеханика, 1973, N 3, с. 121-128.

6R. Хорошевский Б.Г., Сед ухина Л.А. Стохастические алгоритмы Функционирования однородных вычислительных систем. — б кн.г Вычислительные системы, 1972, бып, 51, с. 3—19.

69. Миренкor H.H. Алгоритмы планирования япя оигпетчрра однородной вычислительной системы. - 8 кн. ¡ Эычиглительные системы т 1970 „ вып. 42, с. 34-46.

70. Krause K.L., Shen V.Y., Srwetman Н.П, Analysis of several táfefc—scheduJ i n g al дог i thins for s mortpl o-f fflul + i progr^mmi ng computer systems. - J. ACM, 1975, v. 22, N 4, p. 522-JÍ50*

71. Johnson D.R. , Demers A., UlímaÉr Л.Б., (Загеу M.R. , Graham R.L. Worst— cas*= ¡performance hounds for himple one^di mensi onal

2P

bin-packing algorithms. - STAM J. Comput., 1974, v. 3, N 7, p. 799-325.

72. Yao А. Г. -с. We^ algorithms fnr bin-packing, - Л. ARM. v.27, W 2, p. 707-722.

73. Ьдкрнрпт В.(в. , Мйкэррйич O.R. , ЧеФРанов А.Г. П числе прямоугольников единичной ширины, достаточном дпй упаковки заданных прямоугольников. - Кибернетика, !984, N i, г. 26-27, 37.

74. Coffman Р. G. , Graham R. L. Opt i mal schecful i ng -f or two—processor system. - Acta Tnformatica, 1972, M I, p. 70Q—213,

75. Hu Т.О. Paral lei sequenci ng and assemhl у 1 \ hp prnhl ems. -Goer. Res., 1961, N 7, p. 841-348.

76. Lam S. , Sethi R. Worst—case anal ysi s o-f two sehedttl i ng algorithms. - SIAH J. Comput., 1977, v. 6, N 3, p. 518-536.

77. Muntz R. R. , Co-f -f man F. G. Optimal preempt i ve schedul i ng -f or two-^jrocessor systems. — TFFF Trans. , 1969, v. C-1R. N 1 1 , p. 1014— 1020.

7Я. Kau-f man M. T. An a) most opt i mal al gori thm -for the assemhl у 1 i n^ scheduling problem. - IFFF Trans., 1974, v. C—73, N 11, p. 1167-1174.

79. Rowi cki A. A note on opt} mal preempt! vp schedul i no -fftr two—processor systems, - Inform. Process. Lett., 1777, v. 6, W t, p. 25-28.

30. Muntz R. R. , По-f-f man E". G. Preempt" i vb schedu 1 i ng п-f real —t i tasks on multi processor systems. - Л.ARM, 1970, v. 17, N 7. p.324-338.

3T . Кйяйэгйи К. В, , Туш-Пяна Т. A, , Лебединская H. Ь. Пб оптимальном выполнении в ы числИт ель ных процессов двУня процессорами. — Управляющие системы и машины, Киев. 5975, N 1, с. 93-94. Я7. Шах баз ян И". В. , T "ущкина Т. А. Метол ветвей и границ ал я задач» параллельного упорядочения. — Записки научных семинаров лпми АН

СССР. - Л.s Наука, 1973, т. 35, г. 145-155.

ЯЗ. Шах баз ЯН «.Р. , Теткина Т. А. , Сохеанская B.C. Статистические? испытания различных методов диспетчеризации для многопроцессорные систем. - Программирование, 1976, М 4, с. 91-JOO.

R4. Бахания H.H. Распределение заданий для параллельных машин г разным Быстродействием. - Автоматика и телемеханика, 1995, N ?, г, 155-163.

RS. Головкин Б. А. Статигтичегкие методы Формализации ¡л диспетчирования параллельных вычислительных процессов. — Автоматика и телемеханика, 1974, f« с.. 163-769.

R6. Шварц И!.С. Автоматический процесс упорядочения мод у л ей и - г приложение к параллельному программированию. — я s

Кибернетический сворник? п.т 1964. вып. 9, г. 240-769. Я7. Копнинский F.A. Алгоритм параллельного выполнения программ. -Журнал вычислительной математики и математической Физики, 1969 - т. 9, N 5, с. 1137-3 J 44.

ВВ. Поспелов Я.А. Введению в теорию вычислительных -игтем. - М,! Советское рацио, 1977. - 2RO с.

В9. Mau ящик К. т Поспелов Д.А. Оптимальное пояр-усное распределение программ на параллельно работающие устройства. - В кн.; передачи информации и их автоматизация, м. : HavKa, 1965, г. 75-7*?

90. Бурков В.Н., Ловецкий С.Эвристический подкод к решению динамических задач распределения ppcvpcob. — Автоматика ¡.-i тедемеханика, 196А, N 5, г. B2-90«

91. Лйнский B.C., Корнев М,Л, Гоставление оптимальных расписаний для параллельно действующих процессоров. - Известия АН СССР. Техническая кибернетика, 1977, N. 3, г. 160-167.

97. Ramamoorthy С. У. , Chandy K.M. , Gonzalez М.Л. Optimal scherlul igg strategies in multiprocessor system. — TFFF Trans. , 1972, v. С—21, N 2, p. 137-146.

93. Пашкеев С. fl. , Минязов Р.И. Машинный алгоритм загруЗки мультипроцессорной бычислительной системы. - В св. ; Вычиг лительные средства в технике и системам Связи, 1977, вып. 2, с. 87-95.

94. Бочаров П. П. , Пвейдунов №. П. Прогнозирование выполнения сложных программных комплексов задач на параллельных вычислительных системах. - Автоматика и телемех дника, 199?, N 12, с. j48-154.

95. Костенко В.А. Автоматизация составления параллельных программ для вычислительных систем с MIMD—архитектурой. — Кибернетика и системный анализ, 1995, N 5, с. 170-179.

96. Крылов З.Г. , Миренков H.H. Алгоритмы планирования функциональных состояний однородных вычислительных систем. — в кн. : Вычислительные системы, Новосибирск; ИМ СО АН СССР, 1975, вып. 63, с. 29-43.

97. Hi 11 er L.W. Branch—and-bound and heuristic apprbache^ fо a sequencing problem with team—size requirements. — AT TP Тгдпс,1 1974, v. 6, N 3, p.206-215.

9B. Макавевич О. Б. К вопросу организации многоканального <"-,,-гт vns в высокопераллельных системах обр а ботки информации. — Автоматика и вычислительная Техника, i 9SO, N 5, с. 24^-30.

99. Каляев А. Р. , Бакенрот В.№. , Макарович O.P. Пб алгоритма ФункциониРовани однородных бычис лигельнь&; систем в режиме пакетной Обработки сложных задач. - Кибернетика, 1982, N 3. с. 68-71.

100. Бурков В.Н., Ловецкий С. Р. Эвристический подход к решению динамических янрач распределения яее увсов. - йетпматика и телемеханика, 1966, м 5, с. 82-90.

10t. Baker В.В., Cof-fman F.ß. , Rivest P.! . Orthogonal packings in two rti raensi ол5. - ST AM Л. Comput., 1980, v. 9, N 4. p. 846-85^. 302. Петунин A.A. Методы укладки прямоугольников в заданной последовательности и их Программное обеспечение. — в кн.; Мат.

обеспечение Расчетов линейного ипр^но vpí«(ьдаг * t pe» kpi "ат«

Всесоюзного семинара 27-77 июня Í980 Г*. , У^агУАИ, 1Я31, г, 142-145.

Í03. Ста ян №. Г. , Поном зр^нкп Л. Л- Рациональное размещение геометрически тел а задачах автоматического проектирования. -Известия АН СССР. Техническая кибернетика, 197R, N 1, с, 39-47.

104. Garey M.R,r Graham R„L. Bounds for multiprocessor scheduling with resource constraints. - SIAM J. Comput., 1975, v. 4, N 7, p. 187-700.

105. Gar ey U.R., .Johnson D. 3. Compl ex it y resul ts -For multiprocessor scheduling under resource constraínts. - яТАМ л Cofflput., 1975, v. 4, N 4, p. 397-411.

106. Бакенрот В. Hi. Эффективность алгоритмов планирования в г^т«» мультипроцессоров. — Известия АН СССР. Техническая кибернетика. 1905т N 1, с. 62— 71.

107. Вакенрот B.W. Границы расписаний паштетной обработки в сетяк мультипроцессоров. - Автоматика и вычислительмая техника, 19R5, М 2, с. 90-91.

í OB. Coffman P. G. , Gar ey M. R. , Johnson D.S., Tar i an R. F „ Per f or manee bounds f or 1 evel -orí erited two-di mensi on al pack i og algorithms. - 5ТАМ J. Comput., 1930, v. 9, N 4, p, 803-876.

109. 81 eat or D. A3. 5-t i шее opti mal al gor i thm f or рас И ng in two dimensi ons. - Inform. Process. Lett. , Í930, v. 10, N 1 , p. 37-40.

110. Hofri M. Two—di mens!onai pac k i ng; expected performance of simple level algorithms. - Inform, and Control , S 930, v. w 1 , p- 1-17.

111. Freder i c^son G.N. Prnbabi 1 i st; i с analyst =. f nr si mpl e one- яп^ two-dimensional hin—packing algorithms. — Inform. Process. Lett-, Í930. v. lí| # 4-5, p. 156-161.

112. Гроппен В.П. Модели и алгоритмы минимизации стоимости решения

некоторых задач на однородных ннсггопромессовным вычислительных комплексах. - Автоматика и телемеханика, 1994, N If, с. l3ft-147. ИЗ. Хорошевский В. Г. Об а л горитмах Функционирования унивевс а льных вычислительные систем» - В кн.; Вычислительные системы, Новосибирска ИМ СО АН СССР, 1970, вып. 39, с. 3-14.

114. Константинов В.и., Миренков h.Н. функиионирorание олноропной еычислительной системы при наличии приоритетного потока больших задач. — В кн.ï Вычислительные системы, Новосибирск! ИМ ГП АН СССР, 1970, вып. 42, с. «7-50.

115. Кевёель В.Г. "Загрузка однородной вычислительной системы потоком параллельных программ. — В кн.ï Вычислительные системы, Новосибирск* ИМ СО АН СССР, 1977, вып. 70, с. 7Я-Я9.

lié. Хорошевский В.Г., Талныкин 3.А. Теоретике—игровой подход к проблене Функционирования однородных вычислительных систем. — В кн.; Вычислительные системы, Новосибирск; ИМ СО АН СССР, 1977, вып. 51, с. 20-37.

117. Лавекий В.А., Хоеошееский В.г. Организация Функционирования однородных вычис лительных систем и стох ас тическое

программирование. — В кн.; Вычислительные систрмы, Новосибирскï СО АН СССР, 1975, вып. 63, с. 3-14.

î1В. Раврилов В.А,, Жирэтков В.И. Алгоритмы опееативнпгп планирования однородной вычислительной системы в Регине интерактивных вычислений. — Прог-ваммиеорание, 1978, N 5, с. 67-Ав. 119. Se h wet man H. D. .Tob-^chedul i ng in mul t i programmed rnmptiirpr eyst emfe. — Sn-f t ware - Pr act i re and Fx per . , ï 970 , у . В, W 3, p. 741-2^5.

170. Serey M.R., Graham R.L., Johnson П.Я., Van A.C.-C. Resource constrained scheduling as generalised hi n—paeki ng. — J. Comb. Th., 1976, v. A—21, N 3, p. 257-298.

121. Ecfcer K. Anal y si в о-F simple -strategy -F or resource constrai nt в

task scheduling» - Ргег. Int. Conf. Parallel Process., tV78. New York, 197R, p. 181-183.

122. Haberman A.N. Preventi on o-f system dead! пгИ, - По®«. АГ*м, 1969, v. 12, N 7, p. 373-377.

173. Бакемрот P.Ю, , ЧеФРаной А.Г. ЭФЛрктйрногть приближений« аПг-оРйтмоБ распределения программ в однородной вычислительной системе. - Известия АН СССР. Техническая кибернетика, 198=?, N 4„ с. 135-148.

124. Бакенвот В.Ю., Макаеевич 8.Б., ЧеФванов А.Г. Об эффективности алгоритмов опевативной диспвтчевизаиии слогным задач в пакетной режиме работы однородных вычислительных систем. — упрмя/тящда системы и машины, 1"81, N 5, с. 77-75.

125. ЕЧакаеебич О. Б- , Бабенко Л. К. , Карпов F. В. , ЧрФрзнор А, Г Управление параллельными процессорами многопроцессорной системы с прог-раммируемой архитектурой. — Известия CKHII Blil. Технические науки, 1986, N 4, с. 73-76.

176. Карпов P.P. , Ослопов И. Л- , Лаврова И.Г. , ЧирскиЙ А. г.. , ЧеФРанов А.Г. Управление параллельными процессорами в вычислительной системе FC ЭВМ - процессор- 27ОЗ. - Тез. докладов Всесоюзной школы—семинара "Разработка и применение е народном хозяйстве ЕС ЭВМ", Кишинев, 1988, Ч. 2, с. 171-172. 327. Макаревич О.Б. , Ремаеенко Л.В., ЧеФРанов А. Г. Об одном алгоритме планирования пакетной обработки в однородным вычислительный системам - - Известия АН СССР. Техническая кибернетика, 1986, N 5, с. 233.

128. ЧеФванов А. Г. , Саак А. Э. О вероятности соблюдения директивный срак^'5 многопроцессорной системой. — Автоматика и Вычислительная техника, 1987, N 6, с. 67—7).

129. ЧеФванов А.Г., Саак А.3. Детерминированные и вероятностные оценки эффективности многопроцессорных систем. — Труды 1

Всесоюзной конФ. "Прокпены создания с vnep3BM, с уперсистем и Эффективность и* применения", Мн.: МРТИ, i 987, ч. 2, с. 1R6—197.

130. Бакенрот В. Hl. t ЧеФРанов А. Г. Об Эффективности одного к narr а алгоритмов лвумерной упаковки. - Известия СКНц Bill. Технические науки, 1983, N 9.

131. ЧеФранов А.Г. Об эффективности алгоритмов оперативной загрузки ПРИ реализации асинхронных вычис лений. - Известия АН ПСПР. Хроническая кибернетика, 1985, N 6, с, 76-78.

132. ЧеФранов А.Г., Бакенрг.т B.W. Эффективность двух клйггой алгоритмов оперативной загрузки. - Кибернетика, 19Я5, N 5, с. 48-50.

133. Бабенко Л.К,, Макаревич О.Б., ЧеФранов А.Г. Адаптивное управление ресурсами многопроцессорные вычислительных систем. — Львовз НТЦ "Интеграл", 1992. - 275 г.

134. Макаревич О.Б., ЧеФранов А.Г. Пе эффективности алгоритмов динамического распределении pec vpcob многопроцессорных систем при решении потоков задач,— Автоматика и вычислительная техника, 1937, W 4, с. 14-17.

135. Макаревич О.Б., ЦеФраное А.Г. ЭФФективнпгть параллельных вычиспений в мнороррсурсных многопроиессорных системах. Электронное моделирование, 19R0, N 1, с. 14-17.

136. Бакенрот В.И., ЧеФранов А.Г. О качестве списковых диспетчеров. - Кибернетика, 1988, N 3, с. 118-1IV.

137. Теория расписаний и вычислительные машины/ Пол ррд Э.Г.КоФФмана. - М.: Наука, 1984. - 334 с.

138. Гене Г.В. , Левнер F.R. оптимизмиионные задачи эффективные приближенные алгоритмы. - Известия АН СГХР. Тех ничеен-а я кибернетика , 1979 , N 6 , с. 9-20.

139. Oarey М. R., Graham R.L., Johnson 0.8. Performance guarantees -for scheduling algorithms. - Oper. Res., 1978, v.26,N ä, p. З-'7!.

1 АО. Макаревич О. Б. , ЧеФранов А, Г. Пб яййрктийнпгти одного к лаг с а алгоритмов оперативного вэспрелелемия ресурсов нногопрпцеггорных систем г ненадежными процессорами. — Автоматика и телемеханика, 1986, N 2, с. 150—135*

141. Бакенрот , Чефранов А.Г. Эффективность одного клаггд алгоритмов планирования в сетях мультипроцессоров. - Автоматика и вычислительная техника, 19R4, N 1« с. 21.

142. Бакенрот В.К?. Границы расписаний пакетной обработки в гстяя мультипроцессоров. — Автоматика и вычислительная техника, 19Р5, fj 2, с. 90-91.

143. Рэрэкмн A.C., Панишев А. в, Верхняя оценка Длины расписания в qsvMуровневой многопроцессорной системе. — Кибернетика, 1990, N Ь с. 113-116.

144. Вавакин А.Г. Эффективные алгоритмы в системе управления гибкий автоматизированным участком металлообработки, — Дисс. ... канз$. техн. наук, Харькова ХАДИ, 1990. - 147 г.

145. Вавакин A.C. , Панишев A.B. Анализ алгоритма распределения pec vp со в в дв ухггтадийной вычислительной системе. - Автоматика и вычислительная техника, 1990т N 4, с - 57-5R.

146. Панишев А.Р. Эффективные алгоритмы упорядочения Работ я системах с параллельно действу»щими приборами, — Лист, ... цокт. техн. на укХарьков: ХАДИ, 19Э9. - 343 с.

147. ДанилЬчемко А. М- Эффективные алгоритмы Построения расписаний в двумуео&невых многопроцессорных система«. - Авторрф. лиге, канд. техн. наук, Харьков: ХАДИ, 1906. - 1Яс.

14В. Левченко С.Н. Эффективные алгоеитмы упорядочения в vnPaeпении ппгру9очнО^Транспортным процессом. - АвторвФ. лиге. канд. теин, наук, Харьков: ХАДИ, 19SS. - 16 с.

149, Ситникова П..П. Задала теории расписаний в многостадийный системах. - Кибернетика, 19ЯЯ, N fe, с. 114—116.

1 50. СРбастьямой о. Р. Пагтрорнме пр weли*енноро рйгпигян^ля пая системы поточного типа. — Управляемые системы, Новосибирск; ИИ сп РАИ, 1993, в ып. 31, с. 66-71.

15Í. Севастьянов Г.В. Неготовые обобщений задачи Я*онсона и целочисленные экстремальные задачи. - Управ лявные гигтрны, Новосибирск: ИМ СО АН CCCF, 193!, вып. 7!, г. 4^-61. Í 57. Сееасть янов С. ft. Алгоритм с оценкой для заяачи с мдрШрvtsmh деталей произвольного аира и альтернативными исполнителями- — Кибернетика, 19(36, N 6, с. 74-79.

í53- танарб p.c., Сотеков , Ствусевнч p.a. теория расписаний.

Многостадийные сигтвмы. - м-; Наука, 19r9. - 37я г.

154. Сотсков №.Н. Сетевые модели и методы теории расписаний. -АетоввФ. дисс. докт. Физ.-мат. наук, Минск: ИТК АН ВССР, 1991. -47 с.

155. Сотсков W. И. Устойчивость оптимальных по Выстводействию раслиганйй. — Журнал вычислительной математики и математический ФИЗИКИ, 19П9, N 5, с. 773-731.

156. Сотсков W. Н. Использование устойчивости огггимальны*; расписаний для синтеза информационно—вычислительных сетей. — Автоматика и вычислительная техника, 1990. N 3. с, 17—39.

157. Мереикий И-Ю- Построение оптимальных расписании выполнения работ для технических систем конвейерного типа. — АвтореФ. пис-. канд. техн. наук, М.г«ПУ РАН, 1993. - 1В с.

15В. Саак А.3. Анализ Функционирования паваллельно-конвейерных систем в условиях неопределенности* - Диес. канд. техн. на У к, Taranporï ТРТИ. 1993. - 323 с.

159. A.c. 976447 (СССР) Устройство для распределения заданий процессорам. - Воль нов М. П. , Долгий Hi, И. - Ппуёп. в ВИ, 1 , N

43

î 60. A.c. 1 111165 (СССР1 Устройство для распределения заданий

процесс dp ам. - КрыМов Н. И. , Поп>-»в В. А. - Опубл. р БИ, 1 984, N

32.

161. А.г. 1111163 (СССР) УСТРОЙСТВО пля рэспррцрлрния эар?н1лй ме*ду ЭВМ, - Ее-л яков В.В. , Жильченко Л.Г. , Соколов В. В. — Ппубл. я БИ, 1984, N 32.

!62. A.c. 1196866 (СССР) Устройство для распределения Заданий процессорам. — Адонин В.И., Баженов С.В, , Карна у* К.Г. и йр, -□публ. В БИ, 1985, N 45.

163. A.c. 964643 (СССР) Устройство для распределения ааданий процессорам. - Титов В.А», Алексеенко А.И., Гайдуков В.Л., Неман Л.Ф. - Опубл. в БИ, 1982, N 37.

164. a.c. 966697 (ссср) Устройство для распределения заданий процессорам. - Титов В.А., Брянцвв Н.М., HvrvHOP A.B., Гайдуков В.Д. - Опубл. r ВИ, 1982, N 38.

165. a.c. 1070551 (ссср) устройство ял я рр упповг^ро обслуживания запросов. - Попов B.C., Рйнитуллин А.У. - ПпУбЛ. в би, 1984, n 4.

166. A.c. 1425671 (СССР) Устройство для распределена;? и задач процессорам. — Писарвнко В.И., Надрдов Ht.A. — Ппур.л. в ВИ, 198а, N 35.

Í 67. A.c. )3906О9 (СССР} Устройство для распределения заданий. - Герасименко Г.Г., Михайловский С.К. - Опубл, в БИ, 1988, N 15.

j68. A.c. J425672 (СССР) Устройство для задач в многопроцессорной вычислительной системе, — Тарасов A.A. - Ппуйл. в БИ, 1988, N 35. 369. A.c. 1269136(СССВ) Устройство лля

заданий процессорам. - Матов А.Я. , Карловский С.Р, , Макарчук А.М., Якуб Н.М. - ОпуВл. в БИ, 1986, М 41. 170. A.c. 1267418 (СССР) Мнпг-окана

рас преде Крылов А. П, ,

р аспределения пронин в.н,.

обслуживания запросов - Тимонькин Г.Н., Харчен^п B.C., Дмитров Д.В., Ткаченкп С.Н. - ОпУбп. б БИ, N 40.

171. А.с. 1267417 (СССР) Устройство для обслуживания запросов в порядке поступления. - Чернов В.П. - Пп убл. в ВИ, 1^па, N 40.

172. A.c. 5205144 (СССР) Устройство для рзгпррлрлриия заданий процессорам. - Богатырев В.А. - Оп^бл. в ВИ, 1986, N 7. (73. A.c. 932005 fCCOP) Устройство для распределения задач меж ду процессорами. - Богатырев В. А. - Ппубл. в ВИ, 1987, N 46.

174. A.c. 1037267 (СССР) Устройство для управления вычислительной системой - Мазаник В.В. — Ппувл. в БИ, 1933, N31.

175. A.c. 377553(СССР) Устройство для распределения заданий процессорам. - Титов A.A. , Гайдуков В,Л. - Опубл. в ЯИ, 1931 , N 40.

i 76. А.г. 94016д (СССР) Устройство для распределения заданий процессорам. — Титов В.А, Афанасьев И).П., Комаров A.C. — Ппч>бл. в ВИ, 1933, N 74.

!77. A.c. 679538 (СССР) Устройство для распределения заданий пргшессорам. - Попякое Г.А. , Шути лов А.Т. , (Нарапанпр B.B. - 0nv6n, в БИ, 1978, N 39.

178. A.c. 366560 (СССР1 Устрпйство пля распределения заланий пп процессорам. - Захаров А.И. , Борисов В.И. , Ковалев я.В. , Яцук В.Я. - Опубл. в БИ, 1931, К 35.

179. A.c. 903876 (СССР) Устройство для распределения заданий. — Ганитуллин А. К. , {(¡маткое С.И. - ПпУбл. в ВИ. 1<737, М 5. 130. A.c. 807972(СССР) Устройство для пбгл ухивзния запросов -Бакенрот В.Ш., Лапшин И.А. - Опубл. в ВИ, J981, N 7.

1Я1. A.c. 913377 (СССР) Устройство пля распределения заданий процессорам. - Ганитуллин А.Х., Шутилов А.И., Круцик P.a. - nnvfin,

l<ji

в БИ, 1982, N 10.

132. А. £_. 9572 i 1 (СССР) У и гройс г во для распределения заданий. -Ганит уллин А.X. , Шутилов А.И., Дияров F. М. - Опубл. в БМ, 1932, N 33 .

J33. А.с. 109513J (СССР) Устройство для распределения заданий процессорам. — Ткаченко С.Н. , Типонькин Г.Н., Харченки B.G. , Ярионов Б.И.. - Опубл. в БЫ, 1984, N 20.

184, А.с. 1179340 iCCCP) Устройство для распределения заданий. - Ганитуллин А.X., Попов В.Г. - Опубл. в БИ, 1985, N 34,

185. Ларраби и. Р- , Пенник К.Э. , Стерн С. М. Параллельный проиегхор SBN Butterfly. — В кн.: Программирование на параллельные вычматт&льных cwci емая , М. s Мир , 1991, ред. F. Бобб 2, с. 57-72. 136. Узйман Р. Система проектирования программ для iранепьютеров, — В кн.: Транспьютеры. Архитектура и программное обеспечение. Н., Радио и связь, 1993, Ред. Г.Харп, с. 33-93.

187. Д*оунз Г. Программирование на языке ОККАМ. - И.: Мир, 1989. -208 с.

133. Сырков Б.Ю,, Матвеев С.В. , Корпев Ю,П. Программирование на языке Оккам-2. - М. : МАИ, 1991. - 120 с.

139. Ар*итектура и матемагическое овеспечение многопроцессорных суперЭВМ, - Бабенко Л.К., Крйьчвнко П,П., Макаревич G.Б., НеФранов А.Г. - Таганрог: ТРТИ, 1992. - 154 с.

190. Martin В., Bergan С., Russ Б. PARPC; a system for parallel proiedure calls. - Froc. Int. Conf. Paral1. Process,, Aug. 17-21, 1987, Univ. Park, Pd, 19S7, p. 449-432.

191. Ds;sd 0. , Fadgyas Т. T Kacsuk P. GRAPNEL: graphical pr o^r amffti ng 1 anguage f or par al 1 el pr ogr amroi rig. - Fr ol . |1P ' 9 4 Conference, Budapest, Hungar y, 1994.

192. Dozsa G. , Fadgyas T. , Ka«_suk P. Improved version of the GRAPNEL language. - Pr oc. [IP'93 Confer ence, Budapest, Hungary-,

1995, p. 47-65.

193. Коновалов H.A., Крюков Б.А., Михайлов Г-Н., Погребцов A.A. Für Lran DVH - язык для разработки мобильных параллельных программ. - Программирование, 1995, N 1, с. 49-54.

194. Вир т ц Г. Язык MEANDER к его программное окружение. Программирование, 1995, N 1, с. 15-25.

195. Сторм Л. Sequent Balance Series. - В кн.: Программирование на параллельных вычисли гельных сисiемах, М. :Мир, 1991 , ред . Р. Бзбб 2, с. 155-167.

196. Корнеев В.Д., Миренков H.H., Непомнящая А.Ш. D реализации «зыка сверхвысокого уровня PARIS. - Б св.: Высокопроизводительные еычислит ельные сисiемы для комплексных центров иа гемвплческого моделирования. Архитект ура и общесистемное математическое о вес (течение, Новосибирск: BU СО АН СССР, 1991, с. 145-151,

197. Корнеев В.Д*, Миренков H.H., Непомнящая А.Ш. Язык сверхвысокого уровня PARIS. - Кибернетика, 1990, N 1, с. 34-36. 19В. Модал К.Б. Cr ау-Х-ИР. - В кн.: Программирование на параллельных вычислтельных системах, М.:Мир, 1991, ред. Р. Бэбб 2, с. 73-S7.

199. Pratt T.W. The Pisces2 parallel programming environment. Int Con-f . Par al 1 . Pr uc. , 1987, p. 439-445.

200. Василеску №. Прикладное программирование на языке АДА. - М. : Нир, 1990. - 348 с.

201. Виг-zi M.D. , Padua D.A,, Hoefflinger J.F.,Lawrie D.H. Cedar For Lran and other vector and par al 1 el Fortran di al ec L в. - Fr ос . Supercomputi ng"BB, Nov. 14-1B, 19B3, Or)ando, Fl ori da, IEEF Comput. Sac., L988. p. 114-128.

202. Pollchr onopoulos C.D., Baner iee U. Pr осеввог a11ocati on for hur i z on Lai and ver t i cal par al 1 el ibm and r el a Led bpeetf-up bounds. -IEEE Trans. Comput., (987, v. C-36, N 4, p. 410-420.

JOO

203. Fang 2. , Yew F. -С. , tang P. , Zhu C. -0. Dynami с pr осеьаог sei f scheduli ng for gener a1 para11 el nested 1 оups. - Pr dc. Int. Conf . Parallel Process.9 Aug. 17-21, 1937, Ed. S.Sahni, v. 20, p.J-10.

204. Гайсарян С.С., Ласговецкий А.Л., Дедовских И.Н. , Халецкий Д.А. Расширение ANSI С для векторных и суперскапярных компьютеров. - Программирование, 1995, N 1, с. 26-36.

205. Пейа Д.М., Ларрави А,Р. Параллельная ЭВМ Intel iPSC. - В кн. ; Программирование на па^аппвльных вычислительных системах , М.:Мир, 1991, Ред. Р.Бзвв 2, с. 155-167.

206. Bemmerl Т., Ludwig Т., Riea В. A design and specification environment -for distributed memory multiprocessors. - TOFSYS Tools for Parallel Systems, Technische Universität München, TUM—19119, SFB-Bericht Nr. 342/13/91 A, Juni 1991, p. 83-92,

207. ДиНиччи Д.Ч. Loral Dataflo LDF-100. - В кн.: Программирование на ; ¡араллельных вычислиiельных системах, М. : Мир, 1991, ред. Р.Бэве 2, с. 155-167.

203. Lewis Т, El-Rewini Н. Parallax: a tool for parallel program scheduling. - IEEE Trans. Farailel & Distributed Technology, 1993, V. 1, N 2, p. 61-72.

209. Barhen J., Haibert E.C. ROSES: an efficient scheduler for precedence constrained tasks on concurrent multiprocessors. Hypercube Multiprocess., 1986, Proc. 1st Conf., Knoxville, Term., Aug. 26-27, 1985, Philadelphia, Pa, 1986, p. 123-147.

210. Gendr eau Т.B. Cooperative seif-scheduli ng in message—passi ny parallel systems. - IEEE South Eabt Con;B9. Conf. and Exhib. Energ. and Inf. Techn., South East, Columbia, S.C., Apr. 9-12, 1939, Froc., v. 2, p. 496-499.

211. Mirenkov N.N. parallel language developments in Russia. -Computi ngSiContr ol Eng. J., 1993, v. 4, N 1, p. 37-44.

212. Миренков H.H. Параллельное программирование для

многомод ульмых вычислительным систем. - М. ; радио и связь, 19S9. -

320 с.

213. Анисимов A.B., Борейша (O.E., Кулявко П.П. Технология параллельного программирования ПАРУС. - Abiоматика и т елемек аника,

1990, N 6, с. 153-160.

214. Ani si mov А. V, , Bor ei sha Y. E. Dynami с par al 1 el i sm in transputer systems. - Pr oc. Int. Conf. Parallel Comput. Techn., Novosibirsk, USSR, Sept, 7-11, 1991, Worl4 Sc i ent i f i с , Singapore,

1991, p. 477-486.

215. Bupta J.P., Winter S.C., Wilson D.R. CTDNet - a mechanism for the concur r ent executi on of 1 ambda yr aphs. - IEEE Tr ans. Sof twar e Eng., 1939, v. 15, N 11, p. 1357-1367,

216. KuLepov V., Falk V, Integrated tools -for -functional, logical and dataf1ow par al 1 el pr ogrammi ng and contr ol 1 i ng par a J 1 el compulations In computer systems* - Pr oc. Int. Conf. Parall. Cofljpui:. Techno! , , Novosibirsk, USSR, Sept. 7-1 1 , 1991 , Ed. N.N.Mirenkov, World Scientific, Singapore, 1991, p. 158-166.

217. Эглен-Леклерк M,-К,, Жулиан Ж. Компиляция параллельного языка LEQ класса "производитепь-потревитель". - Программирование, i 995, N 1 , с. 37-48.

21S. Андон Ф.И,, Поляченко Б.Е., Гунько О.Л. Система синтеза программного обеспечения для пар аляельныя мультитранспьютерных комплексов. - Управляющее системы и машины, 1992т N 9/10, с. 3-10,

219. Chapman В.И., Mehrotra P., Zima Н. Vienna Fortran - a Fortran 1anguage extension for distributed memory multiprocessors. - NASA Contractor Repor t 187634, ICASE Repot t No. 91-72, Contract No. NASI-18605, Sept. 1991, Institute for Computer Applicati ans in Science and Engineering, NASA Lanyley Research Center, Hampon, Virginia, 23665-5225, 23 p.

220. Snir M. The NVU Ш tracomputer - designing an MIMD shared

lot

mem or у par al 1 в1 computer. - IEEE Tr ans. Сотриt. , v. 32, N 2, p.175-189.

221. Bam J., Patnaik L.M., Gotwan A.K. Ordered Ports - a 1anguage concept -f or hi gh-1 evel di stributed pr ogr amming. - The Compu t. J . 5 19B7, v. 30, N 6, p. 487-497.

222. Пьявченко А.О. Параллельный язык описания н упр веления заданиями. - Львов: НТЦ "Интеграл", 19S9. - 85 с.

223. Пьявченко A.D. Исследование и разработка программно-аппаратным средств коммутации заданий в моделирующий комплексах реального времени. - Дисс. канд, техн. наук, Таганрог: ТРТИ, 1992. - 311 с,

224. Anand T.S., Gupta R. A tool for evaluating сompi1 er-based par al lei izati on strategies - Hath, and Computers in Simulation, 1989, v. 31, p. 509-516,

225. Lipps P., Munche U., Wilhelm R. OPTRAN - a language/system f ot the speci f i cat! on of pr Ograffl trartsf or mat i ons system over vi ew and experience. - Lect. Notes Comput. Sei. , 1989, N 371, p. 52-65.

226. Ж,, Оппен Д. Равенства и правила переписывания. Обзор, - В кн.: Математическая логика в программировании, ред. За*арьянцев N. Б. и Янов Ю.И., М.: Мир, 1991, с. 176-232.

227. Еднерал В.Ф., Крюков А.П., Родионов А.Я. язык аналитических вычислений Reduce. - М.: МГУ, 1988. - 232 с.

228. Кистлерив В.Л. Язык аналигических вычислений FL АС: модель вычислений и оиивные принципы построения. - Вопросы кивер нет ики, 1937, вып. 149, М. : АН СССР, Совет по комплексной проблеме "Кибернетика", с. 1Б-42.

22?. Компьютерная алгебра: символьные и алгебраические вычисления. - Ред. Б. Ьухбергев, М. : Мир, 1986. - 392 с.

230. Г л ушков В.М. , Грьпнченко Т.Д. , Дородницына A.A. и др. Аналитик—74. - Кибернетика, 1978, N 5, с. 114-147.

щ

231. Капитонова Ю-Б. Os аналитических преобразованиях с помощью ЭВМ. Состояние и перспективы. - Кибернетика, 1935, N 1, с. 86-96, 102.

232. Морозов А.А., Клименко В.П., Йишман Ю.С. и др. Основные свойсi ва алгоритмического языка АНАЛИТИК-91. - Киберне гкика, 1993, N 3, с. 117—128.

233. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ. - М.: Радио и связь, 1983. - 256 с.

234. Кутепов В. П. Об интэллек г уальных компью герах и больших компьютерных системах нового поколения. - Известия РАН. Теория и системы управления, 1996, N 5, с. 97-114.

235. ВаЬЬ 2 R.G., Raybdale W. С. A large grain daLa -flow scheduler for paral 1 el pr ocsssing on Cyber pi us. - Proc, Int. Con-f. Par all. Process., Aug. 19-22, 1986, p. 845-848.

236. Саак А.Э., Сапрыкин В.A., ЧеФранов А.Г. О времени решения пакетов задач в конвейерных системах. — В кн.: Вопросы кибернетики. Средства моделирования и разработки прикладных проррамн для супер-ЭВМ. - М. : АН РСФСР. Научный совет net комплексной проблеме "Кибеенет ика", 1992. - с. 125—132.

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

238. Саак А.Э., ЧеФранов А.Г. Анализ зФФек гивности параллельно-конвейерных сис тем. - В кн.: Анализ ЗФФек г ивнос ги Функционирования вычис ли тельных систем, Львов : HTL' "Инт еграл", 1991, препринт N 7-91, с. 8-14.

239. í-íakarevich O.S. , £abenko L.K., Chefranov A-G. Algorithm LPT wcr bt-case per -F or (nance bounds, - f or' Lwo-1 evel muí t i pr осевьог systems. - Pr ut. 8th Sympobi um Mi cr ocomp. Mi cr opr. Appl . , 0c t.

^qH

12-14, 1994, Budapest, Hungary.

240. Babenko L. K, , Makarevi ch 0. B, , Chefranov А. Б. On the algorithm LFT upper bounds -fur two-level multiprocessor systems. -Pr oc. Int. Conf. Europar '96, Aug. 26-29, 1996, Lyon, France, Laboratoire de 1 r Inf or mat i que du Par al lei i sme.

241. Saak A. E. , Chefranov А.Б. Worst-case per f ormance bounds -for par alI el pipeline systems pr ocessi ng sets of independent task s. ~ Pr oc. Bth Conf . Inf or mat i on , Model ling and Control, Zakopane . Poland, May, 1-5, 1995, v.2, p. 213-217.

24 2. А.с. N 525954 iCCCP) Устройство ялв определения кратчайшего пути в граФе. - Додонов А.Г., Хад*инов В.В., Шишмарев В.М. - Опубл. БИ, 1976, N 31

243. А.с. N 716043 (СССР) Устройс гво для моделирования сетевым грйФов. - Назаров С,Б.т Титов В.А. - Опубл. БИ, 1930, N 6

244. А.с. N 1700556 (СССР) Устройство для управления вычислительной системой. — Макаревич О.Б., ЧеФРанов А.Г., Каляев А.В., Бабенко Л.К. - Опубл. БИ, 1991, N 47

245. Я.l. N 3410029 (СССР) Ус ройство для распределения заданий процессорам - Макаревич О.Б., ЧеФРанов А-Г., Быков Б.А., Еремин С.А., Стоянов А.И.- Соловей Е.Б. - Опубл. БИ, 1933, М 26.

246. Kushino Т. and oth. Highly parallel array processor "Pax ,J' fo wide scientific applications. - Proc. Int. Conf. Parallel Pr ocess., 23-26 Aug. 1933, Si 1ver Spr i ng, 1983, p. 95-105,

247 Бабенко Л.К. Разяавотка принципов, средств и методов организации многопроцессорных вычисли гельных систем,

обьект но-ориентированных на динамические гр уппы процессоров произвольной конфигурации. - АвтоРеФ. дисс. ... докт, техн. наvk , Таганрог: TFTY, 1994. - 34 с.

248. Бабенко Л.К., Макаревич О.Б., Матвеева Л.Н.. Принципы up ганизации вычислений в многопроцессорные вычислительных

системах для приложений реального времени. - Препринт N 16-88, Львов: ИППММ АН УССР, 19S8. - 63 с.

249. Архитек т урное и матема тическое обеспечение МВС. Разработка среде 1 в динамического управления процессами в МВС. Сиенка Эффективное ти и ускорения Реализации параллельных алгоритмов

пр ямых методов на супертранспьютерных вычислительных системах с различными топологиями. - Таганрог, НИИ МВС при ТРТИ, 1994, N ГР 01.9.30006587, Инв. N 02.9.5000002764.

250. Babenko L.K. , Makar evich О.В. , Chefranov A.G. Parailel pr ligr ammi ng technol ugi es and г еьциг ce management i n mul t i pr ocessot systeuis. - Pr oc. Int. Con-f. "Par al lel Сотри t i ng Technol о g i es, Novossibirsk, LiSSR, Sept- 7-11, 1991 ", Singapuure: Wur 1 d Seientifïc, 1991, p. 495-502.

251 . Mafcar evi ch 0. B. , Babenko L. K. , Cfief r anov A. G. Imp3 ementat i on û-f the programming language para] lel For tran -for multiprocessor bybtem with programmable structure. - Proc. Int. Conf. "Parallel Comput. Technol. (FaCT-93), Obninsk, Ru&sia, Aug. 30-Sept. 4, 1993", p. 408-413.

252. Архитектурное и матема тичеекое овеслечение МВС. Разраьогка транслятора для параллельной версии языка Фортран. Моделирование архитект урных решений минис уперЭВМ, - Таганрог, 1992, НИИ МВС при ТРТИ, M ГР 01.91.0053609, Инв. N 02930004417.

253. Программирование на параллельных вычислительных сие i емах / Под ред Р. Бэьб 2. - М.: Мир, 1991. — 376 с.

254. Задыхайло И,Б,, Зеленеикий С.Д. Механизмы синхронизации в языках параллельного программирования. - Известия АН СССР. Техническая кибернетика, 1985, N 5, с. 129-174.

255. Иенсен К. , Вирт Н. Паскаль. Руководство для пользователя и описание языка. - М.: Финансы и l га гис гика, 1982. - 151 с.

256. Грис Д. Пр оект ирование комлилягupob для цифровых

Зоб

вычислительных систем. - M.: Мир, 1975. - 545 с.

257. Marca D.ñ. , Mcßüwan C.L, Structural analysis and design technique. - McGraw-Hill Inc., 1988.

256. Кутаное fi.Г., Юдицкий С.А. Компьютерно-ориентированнные комплексы моделей проектирования сис тем (САБЕ-теянология) . -Автоматика и телемех аника, 1995, N 1 , с. 174-187.

259. ANSI С Tool set handbook.- INMOS Limited, 72TPS 22600, August 1990.

260. Котов B.E. Теория параллельного программирования. Прикладные аспекты. - Кибернетика, 1971, N 1, l. 1-16.

261. Транспьютеры. Архитектура и программное обеспечение./ Ред. Г.Хорн - М.: Радио связь, 1993. - 303 с.

262. Baüenkö L.K. , Makarevich D.B. , Chefranov A.G. Integrated paral 1 el pr cgr ams f or uni ver sal muí t ipr ocessor systems desi gn system. - Pr ос. 1st Nat ion. Conf. Indi ал Transputer User Gr oup <ITUG—93), Pune, India, SepL, 9-11, 1993.

263. Седухин С.Г., Карапет ян Г.3. Проек гиеование оптимальных систолическим сис тем для матричных произведений различной стр укТУРЫ- - Новосибирск, 1990, Препринт N S85, 44 с.

264. Гузик В. Ф. , Питерский А.И. Принципы управления вычислмчте&ьмым процессом в MIMD системах со структурной реализацией программ. Электронное ноделиривание, 1932, N с. 18-24.

265. Каляев A.B., Макарезич О.В., Ьабенко П.К. Архитектура муль типроцессорной сис т емы на базе компьютеров ЕС и спецпроцессора для моделирования обыкновенных дифференциальных уравнений и линейной алгебры. - В сб.s Пакеты программ для обыкновенных дифференциальных уравнений, Новосибаяск, ИТПМ СО АН СССР. i984, с. 40-43.

266. May D., Shepherd R. The INMD3 transputer. - Parallel Prucess., Oxford, 1987, p.71-92.

loi

267. Ьабенко Л.К., Макаревич О.Б., ЧеФранов ft.Г, Принципы описания и организации асинхронных кр упноблочных вычислительных процессов в нульт«процессорных системах. - Электронное моделирование, 1^88, т. 10, N 3, с. 13-17.

268. Котов В.Е. Сети Петри. - И: Наука, 1984. - 160 с.

269. Хоар Ч. Взаимодействующие последовательные процессы. — И.: Мир, 1989. - 264 с.

270. Meertens L. Construct!ng a calculus of pr ograms. - Lect. Notes Cooiput. Sci. , 1989, N 375, p. 66-90.

271. Калинина H.A., Семенов А.Л. 0 работах по анали гическим вычислениям на ЭВМ. - Программирование, 1988, N 5, с. 77-88.

272. Капитонова Ю.В, Летичевский А.А. Методы и средства алгебраического программирования. — Кибернетика и системный анализ, 1993, N 3, с. 7-12.

273. Новиков Е.А., ЧеФранов С.Г. D нелинейном развитии возмущений в турбулентных потоках и проблемы предсказуемости. — Извести АН CCCF". Физика а гмосФеры и океана, 1^771 N 6, с. 611-619.

274. Мелихов А.Н., ЧеФранов А.Г. Применение ЭВМ для решения задач математнческой логики. - Таганрог; ТРТИ, 1^38.- 76 с.

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

276. Мелихов А.Н., Ьарзолевский Ф.Н., ЧеФранов А.Г. Приведение логических выражений к дизъюнктивной нормальной Форме. ТаганрогsТРТИ, 1987. - 15 с.

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