Исследование и разработка алгоритмов диспетчеризации пакетов задач в многопроцессорных и многомашинных вычислительных системах

• Автор: Меликян, Арутюн Левонович
• Шифр специальности: 05.13.13, 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 270 c. : ил

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ

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

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

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

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

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

1.5. Выводы

ГЛАВА 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. Группа Ш ЭА
3.3.2. Класс 2 ЭА.
3.3.3. Класс 3 ЭА.
3.3.4. Результаты экспериментального исследования алгоритмов статической диспетчеризации
3.3.5. Алгоритмы динамической диспетчеризации для МПВС
3.4. Исследование задачи построения оптимальных расписаний для наборов задач процессов с заданным отношением предшествования, временами вводавывода и ограничением по ОП, реализуемых на многомашинных ВС
3.4.1. Постановка задачи .
3.4.2. Математическая модель,
3.4.3. Основные свойства исследуемой задачи построения оптимальных расписаний .
3.5. Алгоритмы статической и динамической диспетчеризации частично упорядоченных пакетов задач на многомашинной ВС
3.5.1. Алгоритмы статической диспетчеризации .
3.5.2. Алгоритмы динамической диспетчеризации
3.6. Выводы
ГЛАВА 4. РЕАЛИЗАЦИЯ УПРАВЛЯОЩЕЙ ПРОГРАММЫ ДИСПЕТЧЕРИЗАЦИИ ДЛЯ МНОГОМАШИННОЙ И МНОГОПРОЦЕССОРНОЙ ВС
4.1. Построение системы статической и динамической диспетчеризации для пакетов задач, исполняемых на ММВС
4.1.1. Особенности задачи построения оптимальных расписаний для пакетов, формируемых на основе ЦКЗ
4.1.2. Классификация пакетов задач
4.1.3. Режимы работы пакетов задач
4.1.4. Структура и функции управляющей программы многомашинной диспетчеризации .
4.2. Система статической и динамической диспетчеризации для наборов задач, реализуемых на многопроцессорной ВС
4.2.1. Многопроцессорная универсальная ВС с перестраиваемой структурой типа ПС .
4.2.2. Структура и принципы функционирования управляющей программы диспетчеризации для МПВС ПС
4.3. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Однако аналитические оценки эвристических алгоритмов обычно слишком осторожны и, зачастую, мало что дают для понимания реального поведения алгоритма в практических ситуациях. Кроме того, получение таких оценок в большинстве случаев представляет собой сложную математическую задачу. Указанные обстоятельства привели к развитию статистических методов исследования эвристических алгоритмов планирования вычислительных процессов в параллельных ВС. Всестороннее исследование ЭА диспетчеризации на имитационных моделях или с использованием реальных программ позволяет получать разностороннюю объективную информацию о поведении этих алгоритмов на практике, а также сравнивать между собой различные методы диспетчеризации. Описанию различных эвристических алгоритмов формирования эффективных расписаний для многопроцессорных и многомашинных ВС и изложению результатов их статистического исследования посвящен целый ряд работ , , , , , , . Алгоритмы диспетчеризации, рассматриваемые в этих работах, различаются по принципам их построения, по используемым критериям оптимальности, по методам выбора задач процессов и процессоров и назначения выбранных задач на процессоры для выполнения обработки информации. В зависимости от принципа построения расписания, различают алгоритмы статической и динамической диспетчеризации . Построение расписания при использовании первых происходит целикорл до исполнения пакета задач процессов. Использо вание статических алгоритмов, однако, предполагает априорное
знание точных значений используемых параметров задач. При использовании же динамических расписаний план прохождения задач пакета через параллельную ВС формируется в динамике вычислительного процесса. При этом не исключена возможность выполнения некоторых предварительных работ в период подготовки к решению пакета задач процессов на ВС для того, чтобы при многократном исполнении пакета сократить затраты машинного времени на построение расписания. Первые два критерия тесно связаны между собой. Если в первом случае требуется минимизировать максимальное время завершения обработки пакета задач процессов при заданном числе процессоров в ВС, то во втором случае требуется минимизировать число используемых процессоров при условии выполнения пакета задач за время, не превышающее заданное если это возможно. Критерий минимизации среднего времени завершения задач процессов из пакета ориентирован на уменьшение в среднем времени ожидания каждого из пользователей и на более быстрое освобождение занимаемых системных ресурсов. Последние два критерия ориентированы на более полное в среднем использование
времени центральных процессоров. Из всех перечисленных критериев наиболее широко применяется первый критерий. В число важнейших функций алгоритмов диспетчеризации многопроцессорных и многомашинных ВС входит выбор задач процессов из реализуемого пакета с целью их назначения на процессоры, выбор процессоров для назначения на них операторов, назначение выбранных задач на выбранные процессоры для выполнения обработки. Правила выбора задач из пакета, используемые в различных алгоритмах диспетчеризации, отличаются по критериям выбора и по используемым при этом параметрам задач процессов. Для выбора задачи используется, как правило, какойлибо один некомбинированный критерий. Такому критерию чаще всего соответствует несколько равнозначных с точки зрения данного критерия задач пакета, среди которых и производится окончательный произвольный выбор единственной задачи. В более сложных алгоритмах диспетчеризации после применения первого критерия на подмножестве отобранных задач дополнительно применяется другой критерий выбора. Два последовательных критерия образуют в совокупности комбинированный критерий. Подобная двухступенчатая процедура выбора задачи на исполнение может уменьшить суммарное время реализации всего пакета . В большинстве случаев, в алгоритмах диспетчеризации происходит предварительное упорядочение множества задач пакета формирование списка приоритетов, определяющее конкретное расписание реализации данного пакета.