Модели и алгоритмы планирования вычислений

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

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

Требуется составить оптимальное расписание выполнения заданий на имеющихся ресурсах, т.е. распределить задания между ресурсам таким образом, чтобы обеспечить минимальное значение заданных критериев оптимальности.

В качестве критериев оптимальности могут выступать:
- минимальное время решения задачи планирования;
- суммарное минимальное время выполнения заданий;
- максимальное использование ресурсов;
- минимальное время передачи информации по каналам связи и др.

Число возможных расписаний (вариантов распределения) существенно зависит от особенностей системы и определяется следующим образом.

а) В полунеоднородной системе, в которой или задания, или ресурсы являются соответственно однородными или неоднородными, число расписаний z заданий между r ресурсами определяется соотношением:
V₁ =z! / ( z – r )! , где! –знак факториала.

б) В неоднородной системе и задания z и ресурсы r являются неоднородными, поэтому любое назначение "задание-ресурс" является возможным (различны лишь времена выполнения заданий и времена коммуникаций). В этом случае число возможных расписаний определяется соотношением:
V₂ =z! r! / ( z – r )! .

в) В строго неоднородной системе имеет место понятие совместимости ресурса с заданием, когда некоторые назначения "задание-ресурс" могут быть несовместимыми (невозможными). Поэтому планирование в таких системах состоит из двух этапов:
- на 1-м этапе ищутся расписания возможных назначений максимальной мощности;
- на 2-м этапе определяется оптимальное расписание из найденных на 1-м этапе назначений.

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

Основные характеристики алгоритмов планирования. Исходными данными для разработки алгоритма планирования являются:
- требования к системе планирования;
- структурная схема системы планирования
- характеристики ресурсов;
- характеристики заданий;
- требования к характеристикам алгоритма планирования;
- набор приемлемых вариантов планирования;
- характер планировщика и его динамичность;
- требования к характеристикам и режимам работы Off-line и On-line-частей системы и др.

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

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

3) Модель решения отражает цель и стратегию планирования, а также способ организации процесса планирования.

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

В зависимости от использования тех или иных тактических приемов алгоритмы планирования могут принимать различные формы. Для решения задач планирования используются:
- графовые модели представления алгоритмов;
- алгоритмы математического программирования;
- эвристические алгоритмы определения перспективных вариантов расписаний и др.

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