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

Реализация конвейера на симметричной ВС


В СССР существовал опыт построения ВС конвейерного типа на основе систем типа MIMD. Такая система ("Украина"), названная рекурсивной машиной, разрабатывалась под руководством В.М. Глушкова в ИК АН УССР. Этот опыт уже тогда продемонстрировал общность принципа симметричных ВС, хотя направленность разработки на параллельное выполнение циклов типа "пересчет", по нашему мнению, раскрыта не полностью.

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

Пусть, однако, длительность решения задач управления одним объектом в несколько раз превосходит значение T, а характер решаемых задач не допускает их распараллеливания.

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

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

Свяжем теперь процессоры ВС в один конвейер, на первую станцию которого будем подавать заявки на обслуживание с максимальной частотой, обусловленной тактом, а с последней станции будем снимать результаты обработки информации — с той же частотой (рис. 8.12).


Рис. 8.12.  Организация конвейера

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

Некоторый выход из положения виден в том случае, когда в рассмотренном режиме производится управление одним объектом. Тогда на основе "физики" процесса может быть справедливым предположение, что каждый результат обработки информации, полученный в i+n-1 -м такте, на основе некоторой пролонгации соответствует данным, как бы полученным не в i-м, а в i+n-2 -м такте. Т.е. необходимо исследовать возможность пролонгации "устаревших" результатов на тот такт, в котором они получены. Такой пролонгацией на последней станции конвейера должен заканчиваться последний этап обработки заявки.



Содержание раздела