Планирование параллельных и распределенных вычислений

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

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

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

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

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

б) критерии оптимизации процесса планирования:
- качество планирования (возможность получения точного решения);
- общее время планирования;
- ресурсные затраты при выполнении планирования и др.

Основными составляющими процесса планирования являются определение пространственно-временных координат выполнения процессов в системы, выполнение решений планировщиков по перепланированию процессов и завершение процесса выполнения заданий.

Организация процесса планирования. Основными параметрами процесса планирования являются:
а) пропускная способность системы;
б) время нахождения задания в системы (время ответа);
в) длина очереди;
г) время ожидания задания в очереди к ресурсу системы.

Классическая трехуровневая схема планирования включает следующие этапы:
1) предварительное входное (статическое или динамическое) планирование исходного потока заданий, претендующих на захват ресурсов системы;
2) динамическое планирование потока процессов, претендующих на захват времени процессоров системы;
3) динамическое планирование времени выполнения заданий на процессорах системы.

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

Классическая трехуровневая модель планирования включает три типа планировщиков (рис. 9.1, 9.2).

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

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

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

Из всех поступающих в систему заданий ПВУ создает очередь О1 (рис.9.2) в соответствии с критериями:
- относительных приоритетов;
- сроков запуска и завершения заданий;
- времени выполнения заданий;
- интенсивность использования устройств ввода-вывода данных;
- потребности памяти.

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

ППУ может временно приостанавливать и активизировать (или возобновлять) процессы для достижения более эффективной и бесперебойной работы системы. ППУ является буфером между доступом заданий в систему и распределением ресурсов по этим заданиям.

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

Только после этого начинают выполняться задания. Задания, требующие продолжения, ПНУ отправляет:
- в очередь О2, если они могут быть выполнены на следующем цикле планирования;
- в буфер (Буф), если задания приостанавливаются из-за невозможности дальнейшего продолжения (например, из-за отсутствия ресурсов).

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

В современных сложных вычислительных системах, оснащенных ПВМ класса MIMD, классическая схема планирования подвергается существенным изменениям и дополнениям, основными из которых являются следующие (рис. 9.2):
- к функциям ПВУ добавляется структурный анализ связности входного потока заданий;
- в схему планирования вводится транспортный планировщик (ПТ), предназначенный для распараллеливания заданий и синхронизации процессов по данным с целью обеспечения поступления требуемых данных и поддержки связей между вычислительными узлами;
- задания или их распараллеленные модули, обработанные транслятором операционной системы и ПТ, становятся в новую очередь в буфер (Буф);

- к функциям ППУ добавляется функция адаптирования процесса распределения заданий к особенностям данной системы (например, к специальным схемам типа "гиперкуб", транспьютерным схемам, неоднородным средам системы и др.);
- к функциям ПНУ добавляется функция балансирования при перераспределении работ (реконфигурации системы) в случае отказа некоторых ее элементов.