Планирование, параллельная программа

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

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

Большинство алгоритмов планирования основывают на т. наз. классической модели целевой параллельной системы, примерно соответствующей однородным системам NUMA или системам UMA под управлением сред с передачей сообщений (см. MPI). В общем случае задача планирования считается NP-сложной.

Говорят о следующих характеристиках частей параллельной программы и расписания её работы: стоимость работы задачи и стоимость передачи данных между задачами, длина расписания, длина пути (сумма стоимостей вершин и ветвей) в расписании и критический путь в данном расписании, время завершения (работы по данному расписанию), время завершения при последовательном исполнении.

Две фундаментальные эвристики планирования это списочное планирование (list scheduling) и кластеризация (clustering). Это не столько алгоритмы планирования, сколько их группы; большинство алгоритмов планирования, как считается, принадлежит одной из этих групп.

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

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

— Ю.Т.