Однородная вычислительная среда для конвейерных вычислений суммы m n-разрядных чисел

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих многооперандных параллельно-конвейерных сумматоров для обработки массивов целых положительных чисел. Техническим результатом является повышение быстродействия за счет параллельно-конвейерного выделения бит переносов разрядного среза слагаемых в следующий разрядный срез и формирования разрядов искомой суммы каждый такт работы устройства. Однородная вычислительная среда обеспечивает параллельно-конвейерное сложение m n-разрядных операндов и состоит из одинаковых ячеек, выполненных из двух двухвходовых элементов И, двух двухвходовых элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, двухвходового элемента ИЛИ, элемента НЕ, трех информационных триггеров, при этом количество столбцов в однородной вычислительной среде равно p, где p=log₂m, а количество ячеек в j-м столбце равно m/2^j. 4 ил.

 

Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих функцию суммирования m n-разрядных операндов путем параллельно-конвейерного выделения бит переносов разрядного среза слагаемых в следующий разрядный срез и формирования разрядов искомой суммы.

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

Ячейка однородной вычислительной среды - элемент регулярной структуры.

Разрядный срез - совокупность бит i-й позиции от m участвующих в операции операндов.

Известно устройство для суммирования одноразрядных чисел - авторское свидетельство SU 1023922 A1 от 27.06.2000. Устройство содержит двоичный суммирующий блок, который содержит группы одноразрядных двоичных сумматоров, причем одноразрядные двоичные сумматоры каждой группы образуют пирамиду одноразрядных двоичных сумматоров, входы одноразрядных двоичных сумматоров первой группы соединены со входами первой группы и первым входом второй группы блока, входы одноразрядных сумматоров каждой последующей группы соединены с выходами переноса одноразрядных двоичных сумматоров предыдущей группы и соответствующим входом второй группы блока, выходы каждой группы одноразрядных двоичных сумматоров соединены с соответствующими выходами блока. Недостаток устройства состоит в том, что оно обрабатывает числа в двоично-десятичной системе, а также не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.

Известно техническое решение параллельного асинхронного сумматора, запатентованное в качестве изобретения - патент RU 2097826 C1 от 27.11.1997. Устройство содержит: n блоков 6₁-6_n параллельной обработки разрядных срезов, n-1 формирователей 7₁-7_n-1 импульсов, запускающий формирователь 7₀ импульсов, элемент 8 ИЛИ-НЕ, каждый блок 6 содержит 4 ключа 1-4, имеющих выходы с высокоимпедансным состоянием, и арифметический полусумматор 5. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.

Наиболее близкое к заявляемому решению является техническое решение устройства, построенное на базе пирамидального способа суммирования чисел - сдваивания (http://parallel.ru/fpga/Summ2/SummColamo.html#pirsum). Являясь одним из наиболее быстродействующих устройств суммирования m операндов, устройство обладает значительными аппаратурными затратами, что приводит к снижению надежности, при этом не реализован конвейерный принцип обработки информации, что в еще большей степени повысило бы его быстродействие.

Техническим результатом от использования устройства для конвейерных вычислений суммы m n-разрядных чисел является повышение быстродействия за счет параллельно-конвейерного выделения бит переносов разрядного среза слагаемых в следующий разрядный срез и формирования разрядов искомой суммы в каждом такте работы устройства. Также при увеличении количества участвующих слагаемых количество ячеек однородной вычислительной среды возрастает линейно.

Описание технического решения однородной вычислительной среды для конвейерных вычислений суммы m n-разрядных чисел. Заявляемое устройство состоит из m-1 ячеек однородной вычислительной среды, которые объединены регулярными связями.

Ячейка однородной вычислительной среды состоит из двух двухвходовых элементов И, двух двухвходовых элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, одного двухвходового элемента ИЛИ, одного элемента НЕ, трех информационных триггеров.

Вход синхронизации ячейки соединен с входами синхронизации первого, второго триггера и элемента НЕ, выход которого соединен с входом синхронизации третьего триггера. Первый и второй информационные входы ячейки подключены соответственно к первому и второму входу элемента И, выход которого подключен к второму входу элемента ИЛИ. Первый и второй информационные входы ячейки подключены соответственно к первому и второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к информационному входу второго триггера, выход которого подключен к информационному входу третьего триггера, выход которого подключен к второму входу второго элемента И и второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу первого триггера, выход которого является информационным выходом ячейки.

На фиг.1 приведена функциональная схема ячейки однородной структуры, где 1, 2 - информационные входы; 3 - вход синхронизации; 4, 6 - элементы ИСКЛЮЧАЮЩЕЕ ИЛИ; 5, 7 - элементы И; 9, 10, 13 - информационные триггеры; 12 - информационный выход. Ячейка может быть реализована на любой элементной базе, имеющей возможность представления булевых функций, в том числе: сверхбольшие интегральные схемы и программируемые логические интегральные схемы (ПЛИС). Вариант реализации на языке программирования аппаратуры VHDL приведен на фиг.2.

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

Вход синхронизации однородной вычислительной среды соединен с входами синхронизации всех ячеек. Массив исходных m n-разрядных двоичных чисел поступает на обработку в виде n двоичных m-мерных векторов, причем m должно быть кратно степени двойки, первый и второй информационные входы ячеек первого столбца однородной вычислительной среды соединены с соответствующими разрядами m-разрядного входного вектора. Информационный выход каждой (i-1, j)-й и (i, j)-й ячейки подключен соответственно к первому и второму информационному входу (i/2, j+1)-й ячейки, причем i∈[2,m/2^j] и i принимает лишь четные значения.

Количество ячеек в j-м столбце однородной вычислительной среды равно m/2^j, количество столбцов однородной вычислительной среды равно, где p=log₂m. Информационный выход ячейки последнего столбца однородной вычислительной среды является выходом схемы, с которого снимается результат.

Описание работы устройства

Устройство обеспечивает параллельно-конвейерное сложение m n-разрядных операндов, где ячейка однородной вычислительной среды (фиг.1) реализует следующую систему логических функций:

s(t)=a⊕b⊕p(t-1);

p(t)=(a&b)v(p(t-1)&(a⊕b)),

где a, b - соответственно состояние сигналов на входах 1 и 2 ячейки;

s(t) - состояние сигнала на выходе 12 ячейки;

p(t) - обратная связь сигнала переноса внутри ячейки.

Каждое i-e двоичное позиционное слагаемое можно представить в виде последовательности бит A_i(a_n,a_n-1,…,a₁), где n - разрядность числа, i∈[1,m]. Тогда m слагаемых можно представить в виде матрицы:

$$\left(\begin{array}{l}{a}_{\mathrm{1,}n},a_{\mathrm{1,}n-1},\dots ,a_{\mathrm{1,1}}\hfill \\ a_{\mathrm{2,}n},a_{\mathrm{2,}n-1},\dots ,a_{\mathrm{2,1}}\hfill \\ \dots \hfill \\ a_{m,n},a_{m,n-1},\dots ,a_{m\mathrm{,1}}\hfill \end{array}\right)$$

Столбцы матрицы с элементами $$$$ (a_1j,a_2j,…,a_mj) $$$$ являются входными векторами, которые поступают на обработку в однородную вычислительную среду.

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

В результате через log₂m тактов работы устройства формируется младший бит суммы m n-разрядных чисел, причем m должно быть кратно степени двойки. После чего конвейер является заполненным и биты результата доступны на выходе устройства каждый последующий такт работы. Так как в каждом такте работы устройства вектор передается в соседний справа столбец матрицы, на вход устройства на каждом такте может быть подан следующий вектор. Таким образом, устройство реализует конвейерный принцип обработки информации. Так как в ячейке самая длинная цепочка распространения сигнала имеет три логических элемента, время задержки распространения сигнала составляет 3·t, где t - время задержки сигнала одним логическим элементом.

Если принять за время суммирования пары n-разрядных чисел n-тактов работы устройства, то время вычисления суммы в предлагаемом устройстве в конвейерном режиме равно m тактов, в то время как время суммирования пирамидальным способом равно p·n тактов, где p=log₂m. Таким образом, быстродействие устройства на базе описанного способа в log₂m раз выше по сравнению с быстродействием устройства на базе известного итерационного способа суммирования. Например, при количестве слагаемых m=64 быстродействие предлагаемого устройства больше в 8 раз.

На фиг.3 представлена структурная схема однородной вычислительной среды в общем виде на базе ячейки однородной структуры, предназначенная для конвейерных вычислений суммы m n-разрядных чисел, где CELL - ячейки однородной структуры, информационные входы X₁-X_m, информационный выход Y. Ячейка может быть реализована на любой элементной базе, имеющей возможность представления булевых функций, в том числе: сверхбольшие интегральные схемы и программируемые логические интегральные схемы (ПЛИС). Вариант реализации на языке программирования аппаратуры VHDL приведен на фиг.4.

Однородная вычислительная среда для конвейерных вычислений суммы m n-разрядных чисел, состоящая из ячеек, выполненных из двух двухвходовых элементов И, двух двухвходовых элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, одного двухвходового элемента ИЛИ, одного элемент НЕ, трех информационных триггеров, вход синхронизации ячейки соединен с входами синхронизации первого, второго триггера и элемента НЕ, выход которого соединен с входом синхронизации третьего триггера, первый и второй информационные входы ячейки подключены соответственно к первому и второму входу элемента И, выход которого подключен к второму входу элемента ИЛИ, первый и второй информационные входы ячейки подключены соответственно к первому и второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к информационному входу второго триггера, выход которого подключен к информационному входу третьего триггера, выход которого подключен к второму входу второго элемента И и второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу первого триггера, выход которого является информационным выходом ячейки, где вход синхронизации соединен с входами синхронизации всех ячеек, массив исходных m n-разрядных двоичных чисел поступает на обработку в виде n двоичных m-мерных векторов, причем m должно быть кратно степени двойки, первый информационный вход ячеек первого столбца однородной вычислительной среды соединен с нечетными разрядами n-разрядного входного вектора, второй информационный вход ячеек первого столбца однородной вычислительной среды соединен с четными разрядами m-разрядного входного вектора, информационный выход каждой (i-1,j)-й и (i,j)-й ячейки подключен соответственно к первому и второму информационному входу (i/2,j+1)-й ячейки, причем i∈[2, m/2^j] и i принимает только четные значения, количество ячеек в j-м столбце однородной вычислительной среды равно m/2^j, количество столбцов однородной вычислительной среды равно p, где p=log₂m, информационный выход ячейки последнего столбца однородной вычислительной среды является выходом схемы, с которого снимается результат.