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

• Автор: Чефранов, Александр Георгиевич
• Шифр специальности: 05.13.13
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Таганрог
• Количество страниц: 314 с. : ил.

?/' Зг/м-и,
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ Таганрогский гас удаве таенный радиотехнический Университет
На правах рукописи УДК 6Я1
Специальное 1 И!
05.13.13- Вычислительные комплексы, системы, сети
05.13.16- Применение вычислительной техники, математического
моделирования и математических методов в научный исследавани«*
На умные коне уль 1 ант ы:
ЧВФРАНОВ Александр Георгиевич
МЕТОДЫ И СРЕДСТВА АДАПТИВНОГО УПРАВЛЕНИЯ РЕСУРСАМИ
ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
ДИССЕРТАЦИЯ
на соискание ученой степени
доктора технических наук
доктор технических наук, профессор.
действительный член АРН РФ и МАИ
А.Н.Мелихов
ДОКТОР технических на УК , профессор.
действительный член МАИ
П.Б.Макаревич
Таганрог-199Я
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. 0В30Р ИЗВЕСТНЫХ РЕЗУЛЬТАТОВ И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ . $
1.1.Алгоритмы управления ресурсами вычис/тгельных систем
1.1.1. ОднисIадийные системы
1.1.2. Многостадийные системы
1.2. Аппаратные средства управления ресурсами
1.3. Средства представления, преобразования и

верификации параллельных задании
1.3.1. Средства представления параллельных заданий
І.З.2. Средства преобразования и верификации параллельных
программ
1.4. -ювка задан исследования
2. МЕТОДЫ АДАПТИВНОГО УПРАВЛЕНИЯ РЕСУРСАМИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ
СИСТЕМ

2.1. Системы с одной ступенью процессоров
2.1.1. Обработка потоков многопроцессорных взаимосвязанных

задан
2.1.2. Пакетная обработка независимых многопроцессорных задан
в однородных системах со многими мульТИПРОМессОРдМИ
2.1.3. Пакетная обработка взаимосвязанных многопроцессорных задач в многопроцессорной системе с несколькими
мультипроцессорами
2.1.4. Обработка потоков независимых многопроцессорных задан в

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

2.1.6. Пакетная овравотка независимых мног'опроиессорных задач в системе с несколькими мультипроцессорами из ненадежных
1C S'
ПРОЦЄССОРОЄ
2.2. Системы с несколькими ступенями процессоров
і С'і
2.2.1. Пакетная обработка однопроцессорных независимых задач в

системе с одним процессором на каждой ступени
2.2.2. Пакетная обработка однопроцессорных независимых задач в
гемах с произвольным числом ііроцєссоров на каждой ступени .»Лі
2.2.3. Пакетная обработка однопроцессорных взаимосвязанных задач в системе С ПРОИЗВОЛЬНЫМ числом процессоров на каждой ступени

2.2.4. Пакетная обработка многопроцессорных независимых задач
2.2.5. Пакетная обработка взаимосвязанных многопроцессорных
1Ь С
задач
2.2.6. Обработка потока независимых задач
2.2.7. Система с сетями мультипроцессоров на каждой стадии при

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

ступени двухетупенной многопроцессорном системы
2.2.8.2. Исследование эффективности двухступенной

многопроцессорном системы
2.2.9. Исследование эффективности многоетупенной
! S2
многопроцессорном сис темы
i S'S
2.3. Выводы
3. РАЗРАбОТКА АППАРАТНЫХ СРЕДСТВ УПРАВЛЕНИЯ РЕСУРСАМИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
-г . V 1 &
о-l. Устройство определении готовности задач к решению

В С1103 для алгоритма ЫПЗН показано, что
Е(Т(П) )/Е(Т0<П) ) ё <|_ + 2 )/ <4Е + 2 ) , 1_€< 10,100),
где Е(х) - математическое ожидание х.
Уровневый алгоритм ЕЕОЕБ исследован в [1113, доказана его асимптотическая в среднем оптимальность, т.е.

Е<Т(П) )/Е(Т0(П) ) < 1 + ОСЕ 4),
где 0<х) - величина порядка х. Суть алгоритма ЕЕОЕО заключается в
том, что задачи с временами решения из < < 1-1) (3, т рз , г >0 - целое,
Р=0(Е 1/4)тах , группируются и задачи каждой группы назначаются 1 = 1 ,Е
на процессоры следующим оьразом. Задачи, для которых >С1- (1-
-1/4
ОСЕ ))п назначаются по одной на соответствующем уровне;
оставшиеся задачи упорядочиваются так, что К. . 'УЗ. и если Вс

+ В. п, то задачи Т.. и 2 помещаются на одном уровне, 1р-І+1
иначе - на разный, 1=1,Ср/23, при нечетном р задача [р/гз+І помещается на отдельном уровне.
В [1123 получены Формулы огп имального назначения ресурсов многопроцессорным задачам в случае их строго параллельного и строго последовательного решения на системе.
В [45,113—1193 исследованы алгоритмы управления ресурсами систем с идентичными процессорами при решении потоков многопроцессорных задач. В С113-1153 методами теории массового обслуживания получены некоторые вероятностные характеристики