Лекции по дисциплине «Теория вычислительных процессов» (стр. 7 )

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

 

Источники-потребители информации

 

Процессоры передачи данных и ввода-вывода

 

Система памяти ВС

 

Очередь заданий

 

Супервизор

 

Диспетчер Формирование очереди заданий

 

Процессор 0 Процессор n-1

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

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

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

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

Схема распараллеливания в ВС на решающем поле имеет вид: (см. рис.)

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

Программа

 

Поток инструкций

 

Диспетчер

 

Решающее поле

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

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

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

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

Существуют два способа диспетчирования: централизованный и децентрализованный.

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

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

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

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