11.8. Распараллеливание арифметических операций

Не вызывает сомнения, что, удвоив объем вычислительного оборудования, можно увеличить быстродействие системы, однако на практике реализовать потенциальные возможности такого распараллеливания совсем непросто. Давно известным, но весьма эффективным методом введения (при необходимости) распараллеливания арифметики является байтовая организация регистров ЦВМ. Так, ЦВМ Линкольновской лаборатории  оперирует с 36-разрядными числами, составленными из четырех байтов длиной по девять разрядов каждый. Арифметическое устройство также имеет байтовую структуру, так что с помощью одной команды можно перемножить, например, пару 36-разрядных чисел, две пары 18-разрядных или 4 пары 9-разрядных. Используя программные хитрости, в такой структуре можно существенно повысить скорость обработки, если только допустимо применение малоразрядных чисел.

Увеличения степени параллелизма можно достичь, используя несколько арифметических устройств, каждое из которых оперирует с полноразрядными числами. Примером такой системы является быстродействующий цифровой процессор (FDP — Fast Digital Processor) Линкольновской лаборатории, содержащий четыре 18-разрядных АУ и два 18-разрядных ЗУ. При таком распараллеливании программирование, позволяющее использовать возможности машины, значительно усложняется. Основная трудность состоит в необходимости начальной установки блоков и в сложности вывода результатов. Перед началом совместной работы все АУ должны быть установлены в исходное состояние, а это требует времени. Результаты параллельных вычислений нужно записать в соответствующие места, на что также уходит время. Дополнительные трудности возникают, если различные АУ должны быть взаимосвязаны. Число возможных связей между  арифметическими устройствами растет как , поэтому число управляющих цепей, если не ограничивать эти связи, может выйти из-под контроля. Вынужденные ограничения в числе взаимосвязей превращают обмен данными в продолжительную и сложную процедуру.

Приведем несколько примеров систем с параллельной арифметикой, предназначенных для эффективного выполнения алгоритмов БПФ. Поскольку эти алгоритмы оперируют с комплексными числами, рассмотрим, каким образом «комплексное» АУ (фиг. 11.5) позволяет увеличить скорость вычислений. Предположим, что регистры  имеют двойную длину (т. е. предназначены для комплексных чисел), а сумматор и умножитель оперируют с комплексными числами. Ниже приведена программа выполнения базовой операции БПФ , причем предполагается, что перед началом вычислений в регистре  содержатся число .

Фиг. 11.5. Арифметическое устройство для обработки комплексных чисел.

В программу включены операции обмена с памятью и арифметические операции, используемые в варианте алгоритма БПФ с основанием 2 и прореживанием по времени. Операции над индексами здесь опущены; для их выполнения могут понадобиться, скажем, две дополнительные команды или же их можно выполнять параллельно с вычислениями и обращениями к памяти.

За счет дополнительного усложнения устройства управления количество команд в цикле можно уменьшить, совмещая обращение к памяти с арифметическими операциями:

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

Комплексное АУ (фиг. 11.5) содержит четыре умножителя (действительных чисел) и четыре сумматора (два для выполнения комплексного умножения и два для комплексного сложения). Вполне уместно спросить: целесообразно ли такое усложнение аппаратуры для ускорения выполнения базовой операции БПФ? Для сравнения на фиг. 11.6 показано АУ, содержащее два сумматора, два умножителя и те же восемь регистров.

Упражнение. Предполагая, что в схеме фиг. 11.6 арифметические операции   и обращения к памяти могут выполняться параллельно, определите число команд, необходимых для вычисления одной базовой операции БПФ с основанием 2 и прореживанием во времени. Запишите эту программу.

Фиг. 11.6. Арифметическое устройство с восемью регистрами.