Стадии планирования. Основные виды планирования

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

Рассмотрим основные этапы планирования, выполняемые на каждом уровне.

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

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

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

4) Адаптация: формирование (на каждом шаге алгоритма планирования) новых кластеров и присоединение их к текущим кластерам. Анализ возможности выполнения заданий на имеющихся в системе ресурсах.

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

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

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

5) Распределение заданий из буфера для назначения на имеющиеся в данный момент ресурсы. Назначения должны быть бесконфликтными и максимальными.

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

7) Перераспределение работосуществляется в случае отказа узлов (ресурсов) или каналов связи путем корректировки расписания в соответствии с новым состоянием системы. На следующем кванте планирования эти изменения фиксируются системой как новое состояние ресурсов.

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

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

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

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

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

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

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

Жесткая схема статического планирования не позволяет реагировать на текущие изменения в системы, в том числе - и на отказ ресурсов.

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

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

При динамическом планировании обычно используются приближенные или эвристические алгоритмы решения задач, не дающие гарантии получения точного оптимального решения.

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

Если поступившие задания распределены между узлами РВС неравномерно и управление ресурсами осуществляется каждым узлом независимо, то некоторые узлы могут оказаться перегруженными, в то время как другие – недогруженными или простаивающими. При этом могут быть сорваны сроки выполнения заданий.

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

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

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

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

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

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

4) Планирование в реальном времени характеризуется выполнением заданий с заданным временем выполнения. От системы планирования требуется минимизация отклонения суммарного времени выполнения заданий от заданных временных ограничений. Для решения этой задачи используется динамический режим планирования (см. п.2) с балансированием нагрузки (см. п.3).

5) В зависимости от структуры и размеров параллельных ветвей вычислений различают следующие виды планирования. а) Крупнозернистое планирование осуществляется путем разбиения задачи планирования на несколько крупных подзадач (так называемых зерен или гранул – от англ. grain), решаемых в определенной последовательности. Число заданий и ресурсов в каждой подзадаче является небольшим и измеряется единицами. Планирование выполняется с использованием так называемой "таблицы назначений", в которой указываются структура и способы взаимодействия больших параллельных ветвей алгоритма планирования.

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

в) При мелкозернистом планировании число заданий значительно превышает число ресурсов. Задания обычно являются неоднородными и разделяются нагруппы (кластеры) с небольшим числом заданий в каждом кластере. Этот процесс называется кластеризацией. Задания одного кластера выполняются на одном и том же ресурсе.

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

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

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

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

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

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

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