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



              

Диспетчер распределения частично упорядоченного множества работ в однородной ВС


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

Частичная упорядоченность заданий, точнее — программ их выполнения, означает, что одни программы используют результаты выполнения некоторых других программ данного пакета. Отражая этот факт графически и введя нумерацию программ, получают графовую структуру, показанную, например, на рис. 10.6.

Частично упорядоченное множество работ

Рис. 10.6.  Частично упорядоченное множество работ

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

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

  1. Выделяются входы графовой структуры, т.е. программы, не использующие выходную информацию других программ. В данном случае это — единственная программа № 1. Она назначается на первый свободный процессор 1. Множество входов исчерпано. Временная диаграмма загрузки процессоров ВС принимает вид, показанный на рис. 10.7.

    Первый шаг распределени

    Рис. 10.7.  Первый шаг распределени

  2. Имитируется счет времени t, чем отслеживается состояние системы. Видно, что только в момент t = 2, т.е. после окончания выполнения программы № 1, могут появиться возможности для дальнейшего назначения. Работу №1 необходимо исключить из рассмотрения. Граф-схема на момент t = 2 принимает вид, показанный на рис. 10.8.




    Содержание  Назад  Вперед