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

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ

ВВЕДЕНИЕ.

ГЛАВА I. МЕТОДЫ ДИСПЕТЧЕРИЗАЦИИ ПАКЕТОВ ЗАДАЧ НА ПАРАЛЛЕЛЬНЫХ ВС.1*/

1.1. Общие положения.1Ч

1.2. Аналитические граничные оценки некоторых эвристических алгоритмов диспетчеризации

1.3. Принципы построения ЗА планирования параллельных вычислительных процессов.

1.4. Некоторые направления дальнейших исследований и разработок

1.5. Выводы.2?

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

ЗАДАЧ.

2.1. Задача о построении оптимального расписания для набора независимых задач (процессов) с заданными временами ввода-вывода и ограничением по ОП.

2.1.1. Постановка задачи

2.1.2. Математическая модель.

2.2. Алгоритмы диспетчеризации наборов независимых задач на МПВС.кЗ

2.2.1. Группа I ЭА и структура алгоритма построения потока

2.2.2. Группа П ЭА.

2.2.3. Группа Ш ЭА.

2.2.4. Результаты экспериментального исследования ЭА диспетчеризации

2.3. Выводы.

ГЛАВА 3. ФОРМИРОВАНИЕ РАСПИСАНИЙ ДЛЯ ПАКЕТОВ ЗАДАЧ С

ЗАДАННЫМ ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ, ИСПОЛНЯЕМЫХ НА МНОГОПРОЦЕССОРНЫХ И МНОГОМАШИННЫХ ВС

3.1. Задача оптимальной диспетчеризации частично упорядоченных наборов задач (процессов) на многопроцессорной ВС при отсутствии дополнительных ресурсов

3.1.1. Постановка задачи

3.1.2. Математическая модель и некоторые свойства исследуемой задачи.

3.2. Задача оптимального распределения ресурсов МПВС между задачами (процессами) пакета с заданным отношением предшествования, при учете времен ввода-вывода и ограничения по ОП.

3.2.1. Постановка задачи

3.2.2. Математическая модель

3.2.3. Исследование вычислительной сложности определения оптимальных расписаний в Задаче 1У

3.3. Эвристические алгоритмы диспетчеризации частично упорядоченных пакетов задач при заданных временах ввода-вывода и ограничении на ОП. Алгоритмы динамической диспетчеризации для МПВС.

3.3.1. Класс I ЗА и структура алгоритма построения по

3.3.1.1. Группа I ЗА.

3.3.1.2. Группа П ЭА.

3.3.1.3. Группа Ш ЭА.1 Oh

3.3.2. Класс 2 ЭА.

3.3.3. Класс 3 ЭА.

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

3.3.5. Алгоритмы динамической диспетчеризации для МПВС 112 3.4. Исследование задачи построения оптимальных расписаний для наборов задач (процессов) с заданным отношением предшествования, временами ввода-вывода и ограничением по ОП, реализуемых на многомашинных ВС ИЗ

3.4.1. Постановка задачи.

3.4.2. Математическая модель . 12,

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

3.5. Алгоритмы статической и динамической диспетчеризации частично упорядоченных пакетов задач на многомашинной ВС.13*

3.5.1. Алгоритмы статической диспетчеризации . 13^

3.5.2. Алгоритмы динамической диспетчеризации . 1^

3.6. Выводы.

ГЛАВА 4. РЕАЛИЗАЦИЯ УПРАВЛЯЮЩЕЙ ПРОГРАММЫ ДИСПЕТЧЕРИЗАЦИИ ДЛЯ МНОГОМАШИННОЙ И МНОГОПРОЦЕССОРНОЙ ВС

4.1. Построение системы статической и динамической диспетчеризации для пакетов задач, исполняемых на ММВС

4.1.1. Особенности задачи построения оптимальных расписаний для пакетов, формируемых на основе ЦКЗ

АСПР.

4.1.2. Классификация пакетов задач

4.1.3. Режимы работы пакетов задач

4.1.4. Структура и функции управляющей программы многомашинной диспетчеризации . 16?

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

4.2.1. Многопроцессорная универсальная ВС с перестраиваемой структурой типа ПС

4.2.2. Структура и принципы функционирования управляющей программы диспетчеризации для МПВС ПС

4.3. Выводы.

В основных направлениях экономического и социального развития СССР на 1981-1985 годы и на период до 1990 года указано, что одной из важнейших задач в области естественных и технических наук является ". совершенствование вычислительной техники, её элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации" [I].

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

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

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

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

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

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

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

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

Для получения расписания строится математическая модель процесса диспетчеризации с использованием модифицированного аппарата однопродуктовых динамических потоков (ДП) в потоковых сетях (ПТС).

Исследуется вычислительная сложность нахождения оптимального решения поставленной задачи формирования расписаний, показана её ЯР-полнота.

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

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

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

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

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

Исследована зависимость времени исполнения пакета от объема ОП при различных значениях числа ЦП, а также от числа ЦП при фиксированных объемах ОП (в том числе для крайних случаев -дефицита и избытка ОП), для каждого из предложенных эвристических алгоритмов (ЭА). Получены и обоснованы рекомендации по выбору ЭА для построения расписаний в условиях дефицита отдельных ресурсов (в том числе обоих).

В главе разработаны алгоритмы диспетчеризации в динамике исполнения пакета применительно к многопроцессорным и многомашинным ВС.

Четвертая глава посвящена црактической разработке системы статической и динамической диспетчеризации крупных пакетов задач применительно к многомашинному комплексу на ЭВМ типа ЕС и многопроцессорной ВС типа ПС-3000.

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

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

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

Научная новизна работы заключается в следующем.

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

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

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

Разработанные в диссертации алгоритмы и методы использованы при построении управляющей программы диспетчеризации пакетов задач для многопроцессорной ВС ПС-3000, разработанной в Институте проблем управления и на заводе "Импульс", а также при построении блока диспетчеризации пакетов и комплексов задач для двухмашинного ВК на базе ЭВМ ЕС-104-5, создаваемого в ВЦ ЕрФИ Госкомитета СССР по использованию атомной энергии.

На защиту выносятся следующие основные положения:

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

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

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

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

Основные результаты диссертационной работы докладывались на Всесоюзном совещании по высокопроизводительным вычислительным системам (Тбилиси, 1981 г.)» на У Всесоюзной школе-семинаре по параллельному программированию и высокопроизводительным системам (Киев, 1982 г.)» на УП Всесоюзной школе-семинаре по вычислительным сетям (Ереван, 1982 г.)» на 1У Всесоюзном симпозиуме по системному и теоретическому программированию (Кишинев, 1983 г.), на IX Всесоюзном совещании по проблемам управления (Ереван, 1983 г.)» & также на семинарах Института проблем управления (1980-1984 гг.)» НИМ ЭВМ (Минск, 1983 г.)» ИНЭУМ (Москва, 1984 г.).

Основные научные результаты опубликованы в работах [2-10].

4.3. Выводы

Четвертая глава посвящена вопросам практической разработки системы статической и динамической диспетчеризации крупных пакетов задач применительно к многомашинному комплексу на ЭВМ типа ЕС и многопроцессорной ВС типа ПС-3000.

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

Построена управляющая программа, в которой реализованы разработанные в диссертации методы и алгоритмы (главы 2 и 3) статической и динамической диспетчеризации для ММВС. Управляющая программа состоит из следующих блоков: координатора, блока анализа запроса-, блоков построения статических и динамических расписаний, блока сбора и обработки статистики и периферийных управляющих блоков,

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

5. Доказана .КР -полнота исследованных задач построения оптимальных расписаний.

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

7. На базе разработанных моделей и методов построен комплекс программ диспетчеризации для многомашинного ВК из трех ЭВМ ЕС-1022, используемый в АСПР Госплана Армянской ССР, и управляющая программа диспетчеризации для МВС ПС-3000. Разработан также блок диспетчеризации пакетов и комплексов задач для двухмашинного ВК на базе ЭВМ ЕС-1045, создаваемого в ЕрФИ Госкомитета СССР по использованию атомной энергии. Экономический эффект, полученный от данных разработок, составляет 21 тыс.руб. в год, ожидаемый - 48 тыс.руб. в год.

1. Основные направления экономического и социального развития СССР на 1981-1985 годы и на период до 1990 года. -В кн.: Материалы ХХУ1 съезда КПСС. - М.: Политиздат, 1982, с. 146.

2. Бронштейн И.И., Меликян А.Л., Трахтенгерц Э.А. Факторы, влияющие на эффективность работы вычислительных систем. М., 1981. 47 с. (Препринт/Ин-т проблем управления).

3. Бронштейн И.И., Меликян А.Л., Трахтенгерц Э.А. Методы оптимизации программного обеспечения в процессе проектирования. В кн.: Автоматизация проектирования систем управления: Сб. статей. Вып.4. М.: Финансы и статистика, 1982, с. 41-61.

4. Меликян А.Л. Методы построения квазиоптимальных расписаний в диспетчерах задач многопроцессорных ВС. В кн.: Параллельное программирование и высокопроизводительные системы: Тез. докл. У Всесоюзн. школы-семинара, ч.4. Киев: Наукова думка, 1982, с. 51-53.

5. Меликян А.Л. Методы оптимизации распределения задач между процессорами в локальных сетях обработки информации. В кн.: Тез. докл. УП Всесоюзн. школы-семинара по вычислительным сетям, ч.1. Москва - Ереван, 1983, с. 9398.

6. Меликян А.Л. Методы построения расписаний для реализации пакета задач в многопроцессорной вычислительной системе типа ПС-3000. Автоматика и телемеханика, 1983, .№ 12, с. 148-160.

7. Меликян А.Л. Методы минимизации времени обработки пакета задач, связанных отношением предшествования, в многопроцессорной ВС. В кн.: Тез. докл. IX Всесоюзн. со-вещ. по проблемам управления. Ереван, 1983, с. 302-303.

8. Головкин Б.А. Параллельные вычислительные системы. -М.: Наука, 1980. 520 с.

9. Мультипроцессорные системы и параллельные вычисления. Под ред. Ф.Г.Энслоу. М.: Мир, 1976. - 384 с.

10. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. Под ред. А.П. Ершова. М.: Наука, 1982. - 336 с.

11. Поспелов Д.А. Введение в теорию вычислительных систем. -М.: Советское радио, 1972. 280 с.

12. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979. - 247 с.

13. Панфилов И.В., Половко A.M. Вычислительные системы. -М.: Советское радио, 1980. 304 с.

14. Барский А.Б. Планирование параллельных вычислительных18