Просмотр исходного текста страницы Планирование, параллельная программа

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

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

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

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

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

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

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

— [[user:Yury Tarasievich|Ю.Т.]]

[[category:параллельные вычисления]]