Конвейеризация обработки данных

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

Конвейерный сумматор целых чисел

В основе алгоритма суммирования целых чисел лежит суммирование одного двоичного разряда (рис. 1).

Рис. 1.

Представим операцию в следующем виде (рис. 2).

Рис. 2.

Здесь и – значения соответствующего разряда в первом и втором слагаемых, — перенос из младшего разряда, –- значение в рассматриваемом разряде после сложения, –- значение переноса в старший разряд.

Рассматриваемая операция может быть представлена таблицей:

Таблица 1

С использованием данного алгоритма легко может быть построен классический сумматор целых чисел с последовательным переносом (рис. 3).

Рис. 3.

Данный сумматор выполняет операцию .

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

Такой же сумматор в конвейерном варианте выглядит следующим образом (рис. 4):

Рис. 4.

Как видно из рис. 4, на каждом шаге конвейера происходит суммирование одного разряда. Остальные разряды остаются неизменными, хранятся в специальных фиксаторах. Такой конвейер позволяет выполнять суммирование потока целых чисел — в то время как происходит сложение второго разряда первой пары чисел, может уже начинаться суммирование первого разряда второй пары чисел. Важно заметить, что время суммирования одной пары не изменяется — оно остается равным . Но интервал схода результатов с сумматора теперь равен не , как раньше, а . То есть при суммировании потока данных конвейерный сумматор в раз быстрее.

Конвейерный сумматор чисел в формате с плавающей запятой

В формате с плавающей запятой представление числа состоит из двух составляющих — порядка и мантиссы (рис. 5).

Рис. 5.

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

Рис. 6.

Под представление числа отводится определенное количество разрядов (минимум 32). Самый старший разряд кодирует знак числа, далее расположена мантисса и вслед за ней — порядок, также со знаком.

Для сложения двух чисел в формате с плавающей запятой, представленных в нормализованной форме, необходимо:

1. Произвести выравнивание порядков по большему из чисел, "сдвинув" мантиссу меньшего числа вправо на соответствующее число разрядов.
2. Так как у полученных чисел порядки одинаковые, их сложение сводится к сложению мантисс как обычных целых чисел (мантисса — целое число).
3. После сложения необходимо представить полученную сумму в нормализованной форме, скорректировав мантиссу и порядок.

Работающий по такому алгоритму конвейеризированный сумматор представлен на рис. 7.

Рис. 7.

Итак, на вход конвейера поступают два числа в формате с плавающей запятой ( и ).

На первой ступени конвейера происходит сравнение порядков и определение максимального из двух чисел, а также разницы порядков. На выходе промежуточные значения фиксируются в фиксаторах: F1 — старший порядок, F2 — мантисса числа со старшим порядком, F3 — мантисса числа с младшим порядком, F4 — разность порядков.

На второй ступени конвейера происходит приведение чисел к одному порядку путем сдвига мантиссы меньшего числа вправо. На выходе промежуточные значения фиксируются в фиксаторах: F1 — порядок (он теперь одинаков для обоих чисел), F2 — мантисса первого слагаемого, F5 — мантисса второго слагаемого.

На третьей ступени выполняется целочисленное суммирование мантисс. Используемый при этом целочисленный сумматор в свою очередь может быть конвейеризирован. На выходе имеем F1 — порядок суммы, F6 — мантисса суммы.

На четвертой ступени выполняется приведение полученной суммы к нормализованной форме с коррекцией мантиссы и порядка. На выходе: F1 — порядок суммы после приведения к нормализованной форме, F6 — мантисса суммы после приведения к нормализованной форме. В результате получили число в формате с плавающей запятой , которое будет являться суммой исходных чисел и .