Рассмотрим три варианта выполнении программы ярусно-параллельной формы (рис. 2.1).

Вариант 1. Процессор 1 выполняет ветви 1-4-5-9-10-13, процессор 2 - ветви 2-6-3-7-8-1112-14. При этом процессор 1 затрачивает 260 единиц времени, из которых 55 простаивает, так как не готовы данные для ветви 13. Процессор 2 затрачивает 230 единиц времени.

Вариант 2. Процессор 1 выполняет ветви 1-4-5-9-10-11-13, процессор 2 - ветви 2-6-3-7-812-14. При этом процессор 1 затрачивает 245 единиц времени, из которых 25 простаивает по той же причине, что и в варианте 1. Процессор 2 затрачивает 215 единиц времени.

Вариант 3. Процессор 1 выполняет ветви 1-4-8-12-11-13, процессор 2 - ветви 2-5-6-3-7-910-14. При этом процессор 1 затрачивает 235, а процессор 2 - 205 единиц времени, из которых 5 он простаивает.

Сравнение этих вариантов показывает следующее. Во всех случаях время, через которое двухпроцессорная система выдает результаты у\ъ, y\4, существенно сокращается: вместо 435 единиц времени результаты выдаются в первом варианте через 260, во втором - через 245 и в третьем - через 235 единиц времени, т. е. в последнем случае время решения задачи уменьшается в 1,85 раза. Выигрыш по времени может существенно колебаться в зависимости от последовательности выполнения ветвей каждым процессором (читатель при желании может построить и другие варианты решения задачи), поэтому процессор должен выбирать новую ветвь с учетом этого обстоятельства. При решении задачи каждый процессор перед началом выполнения очередной ветви должен иметь информацию о готовности данных для этого.

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

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

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

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

Это могут быть и чисто математические задачи, например задачи векторной алгебры -операции над векторами и матрицами, характеризующиеся некоторой совокупностью чисел. Решение задачи при этом в значительной степени сводится к выполнению одинаковых операций над парами чисел двух аналогичных объектов. Так, например, сложение двух матриц размерностью m х n заключается в сложении соответствующих элементов этих матриц: A + B = \aik ]+[bik ]=\aik + bik ]. При этом операция сложения должна быть проведена над m х n парами чисел. Произведение матрицы размерностью m х n на скаляр сводится к

выполнению mхn умножений элементов матрицы на скаляр: aA = a\aik]=\aaik] и т. д.

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

Третий путь параллельной обработки информации - конвейерная обработка - может быть реализован в системе и с одним процессором, разделенным на некоторое число последовательно включенных операционных блоков, каждый из которых специализирован на выполнении строго определенной части операции. При этом процессор работает таким образом: когда i-й операционный блок выполняет i-о часть j-й операции, (1-1)-й операционный блок выполняет (1-1)-ю часть (/+1)-й операции, а (1+1)-и операционный блок выполняет (1+1)-ю часть (/-1)-й операции. В результате образуется своего рода конвейер обработки, который хорошо может быть проиллюстрирован следующим простым примером.

В

Рис. -.2. Структурная схема (а) и временная диаграмма (б) конвейера операций

Операцию сложения двух чисел с плавающей запятой A -х + B -У = C -хУу можно разделить на четыре последовательно исполняемых этапа, или шага: сравнение порядков (СП); выравнивание порядков - сдвиг мантиссы с меньшим порядком для выравнивания с мантиссой с большим порядком (ВП); сложение мантисс (СМ); нормализация результата (НР). В соответствии с этим в составе процессора предусмотрены четыре операционных блока, соединенных последовательно и реализующих четыре вышеперечисленных шага операции сложения: блоки СП, ВП, СМ и НР (рис. а). Примем, что время выполнения каждого шага равно соответственно 60, 100, 140, 100 нс. Таким образом, операция сложения будет выполняться последовательностью операционных блоков за время 400 нс.

Далее предположим, что возникает задача сложения двух векторов А и В, содержащих по и элементов с плавающей запятой. Очевидно, для решения этой задачи потребуется сложить два числа:

A + B = a -х]+\bi -y]=\c, -хУу]

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

На рис. 2.2, б представлена временная диаграмма процесса. Общее время сложения двух векторов с помощью описанного конвейера TK = (n + m -1) т, где т - число операционных блоков. Если бы конвейер не использовался, то это время было бы равно

m

T0 = т где т - время выполнения i-го этапа обработки. Если применить конвейерную

обработку к векторам, состоящим из 25 элементов, то получим ТК= (25 + 4- 1) • 140 = 3920 не, Т0 = 25 • 400 = 10 000 нс.

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

В приведенном выше примере было рассмотрено конвейерное выполнение арифметических операций, но идея конвейера может быть распространена и на выполнение команд. Надо сказать, что конвейер команд применяется уже давно в обычных ЭВМ. При этом цикл выполнения команды разбивается на ряд этапов, например формирование адреса команды (ФАК), выборка команды из памяти (ВК), расшифровка кода операции (РКО), формирование адреса операнда (ФАО), выборка операнда из памяти (ВО) и, наконец, арифметическая или логическая операция (АЛО). В устройстве управления предусматриваются блоки, которые независимо друг от друга и параллельно могут выполнять указанные этапы. Временная диаграмма показана на рис. 2.3. Для простоты время выполнения каждого этапа принято одинаковым (что, вообще говоря, не обязательно и не всегда делается).

Рис. 2.3. Временная диаграмма конвейера команд

Таким образом, если в конвейере арифметических операций происходит параллельная обработка т пар операндов, то в конвейере команд происходит совмещение во время выполнения l операций (/ - число этапов, на которое разбито выполнение команды), что позволяет существенно увеличить производительность такой конвейерной системы.

К сожалению, выигрыш по производительности в l раз практически невозможен, так как может быть получен только при выполнении программы без условных переходов. Наличие условных переходов сразу нарушает работу конвейера и приводит к «холостым» пробегам конвейера, когда по выработанному в команде K признаку результата надо перейти к выполнению некоманды, а совершенно другой, что вызывает

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