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



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

 


Владельцы патента RU 2486576:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Вятский государственный университет ФГБОУ ВПО "ВятГУ" (RU)

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

 

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

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

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

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

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

Известно техническое решение параллельного асинхронного сумматора, запатентованное в качестве изобретения - патент RU 2097826 C1 от 27.11.1997. Устройство содержит: n блоков 61-6n параллельной обработки разрядных срезов, n-1 формирователей 71-7n-1 импульсов, запускающий формирователь 70 импульсов, элемент 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/2j] и i принимает лишь четные значения.

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

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

Устройство обеспечивает параллельно-конвейерное сложение 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 двоичное позиционное слагаемое можно представить в виде последовательности бит Ai(an,an-1,…,a1), где n - разрядность числа, i∈[1,m]. Тогда m слагаемых можно представить в виде матрицы:

( a 1, n , a 1, n 1 , , a 1,1 a 2, n , a 2, n 1 , , a 2,1 a m , n , a m , n 1 , , a m ,1 )

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

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

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

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

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

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



 

Похожие патенты:

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

Функциональная структура сумматора f2( cd) условно "k" разряда параллельно-последовательного умножителя f ( cd), реализующая процедуру "дешифрирования" входных структур аргументов слагаемых [1,2sj h1]f(2n) и [1,2sj h2]f(2n) позиционного формата "дополнительный код ru" посредством применения арифметических аксиом троичной системы счисления f(+1,0,-1) и логического дифференцирования d1/dn f1(+ -)d/dn аргументов в объединенной их структуре (вариант русской логики) // 2480817
Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнении арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых [ni]f(2n) и [mi ]f(2n) с применением арифметических аксиом троичной системы счисления f(+1,0,-1).

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

Изобретение относится к вычислительной технике и может быть использовано при построении многоразрядных быстродействующих сумматоров и АЛУ. .

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

Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано в высокоскоростных арифметико-логических устройствах или в качестве самостоятельного вычислительного элемента в гибридных вычислительных системах в качестве ускорителя арифметических вычислений.

Сумматор // 2455680
Изобретение относится к вычислительной технике и может быть использовано при построении надежных, портативных, многоразрядных, быстродействующих сумматоров и АЛУ.

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

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

Изобретение относится к области вычислительной техники, автоматики и может использоваться в различных цифровых структурах и системах автоматического управления, передачи информации. Технический результат: создание устройства, в котором внутреннее преобразование информации производится в многозначной токовой форме сигналов, определяемое состоянием входных потенциальных двоичных сигналов, что в конечном итоге позволяет повысить быстродействие и создать элементную базу вычислительных устройств, работающих на принципах многозначной линейной алгебры. Для этого предложен одноразрядный полный сумматор с многозначным внутренним представлением сигналов, который содержит первый, второй и третий входные коммутаторы квантов тока I0 с первым, вторым и третьим токовыми выходами, первый, второй и третий источники входных логических сигналов, управляющие состоянием соответствующих коммутаторов квантов тока I0, первый и второй вспомогательные источники опорного тока, при этом в схему введены первое, второе и третье токовые зеркала, каждое из которых имеет по два инвертирующих идентичных токовых выхода, три дополнительных токовых зеркала. 1 з.п. ф-лы, 13 ил.

Изобретение относится к области цифровой вычислительной техники и устройствам цифровой автоматики. Техническим результатом является повышение быстродействия выполнения ЭВО при минимальных затратах оборудования. Устройство содержит в каждом двоичном разряде один RS-триггер, семь логических элементов И, пять элементов ИЛИ, четыре элемента НЕ, информационный вход, первый и второй информационные выходы, шесть входов управления. Способ и устройство для его реализации обеспечивают выполнение таких логических операций, как прием кода в триггеры регистра, инвертирование кода всех триггеров регистра, операция сдвига принятого кода влево, операция сложения по модулю два, логическое сложение двух двоичных кодов, логическое умножение 7. н.п. ф-лы, 1 ил.

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство арифметической обработки дискретной информации. Техническим результатом является обеспечение формирования двоичного кода суммы двух трехразрядных чисел, задаваемых двоичными сигналами. Устройство содержит восемь элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и шесть элементов И. 1 ил., 1 табл.

Группа изобретений относится к вычислительной технике и может быть использована при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых с применением арифметических аксиом троичной системы счисления f(+1,0,-1). Техническим результатом является повышение быстродействия. В одном из вариантов функциональная структура выполнена с использованием логических элементов И, ИЛИ, НЕ. 4 н.п. ф-лы.

Способ формирования логико-динамического процесса преобразования условно минимизированных структур аргументов аналоговых сигналов слагаемых ±[ni]f(+/-)min и ±[mi]f(+/-)min в функциональной структуре сумматора ±f1(σru)min без сквозного переноса f1(±←←) и технологическим циклом ∆tσ → 5∙f(&)-и пять условных логических функций f(&)-и, реализованный с применением процедуры одновременного преобразования аргументов слагаемых посредством арифметических аксиом троичной системы счисления fru(+1,0,-1) и функциональные структуры для его реализации (вариант русской логики) // 2523876
Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств для выполнения арифметических процедур суммирования и умножения условно минимизированных аргументов аналоговых сигналов слагаемых. Техническим результатом является повышение быстродействия. В одном из вариантов функциональная структура реализована на логических элементах И, ИЛИ, ИЛИ-НЕ, И-НЕ. 5 н.п. ф-лы.

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

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов слагаемых ±[1,2 n j]f(2n) и ±[1,2 m j]f(2n). Техническим результатом является уменьшение аппаратурных затрат. В одном из вариантов сумматор реализован с использованием логических элементов, реализующих логические функции НЕ, И-НЕ. 5 н.п. ф-лы.

Изобретение относится к области вычислительной техники и может быть использовано в КМДП интегральных схемах для реализации арифметических устройств. Техническим результатом является повышение надежности. Устройство содержит логические транзисторы n-типа, предзарядовые транзисторы р-типа, инвертирующие элементы, каждый из которых содержит тактовый транзистор р-типа, логический транзистор р-типа и тактовый транзистор n-типа, шину питания, шину земли, логические выводы, логические входы, прямой и инверсный выходы. 1 ил.
Наверх