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

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

Иллюстрации

Показать все

Реферат

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

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

Структура это внутреннее устройство, компоненты объекта вместе с их взаимосвязями.

Таблица подстановок - структура данных (обычно массив или ассоциативный массив), используемая с целью заменить вычисления операцией простого поиска (http://ru.wikipedia.org/wiki/таблица_поиска). В данном описании под таблицей подстановок понимается устройство, выполняющее однотактную табличную выборку.

Известно техническое решение ячейки однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2310223 С2 от 3.10.2005, которое содержит N² полных сумматоров, (1+K)/2·K·(N-1) элементов И, где K=N-1, (N-2)(N-1) элементов ИЛИ, (1+K)/2·K·(N-1) управляющих входов. Недостаток состоит в значительном количестве элементов и связей, что приводит к снижению быстродействия и надежности устройства.

Известна также ячейка однородной структуры, авторское свидетельство SU №1501035 А2 от 15.08.1989, содержащая два информационных входа 1, 2, три настроечных входа 3-5, три информационных выхода 7-8, два мультиплексора 9, 10, два элемента ИЛИ 11, 12, два элемента И, триггер 15, шесть элементов ЗАПРЕТ 16-21, элемент ИЛИ-НЕ. Недостаток заключается в том, что обработка информации производится только в позиционной системе счисления, а также в том, что невозможно хранение информации в ячейке.

Наиболее близкой к заявляемому решению является техническое решение ячейки однородной вычислительной среды, патент RU №2295147 С1 от 29.09.2005, которая содержит семь элементов ЗАПРЕТ, три элемента И, три элемента ИЛИ, два триггера, сумматор, управляющие и информационные входы и выходы. Недостатком является относительно низкое быстродействие ячейки, которое составляет 5t, где t - время задержки сигнала одним логическим элементом, в предлагаемом решении время задержки сокращено в пять раз.

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

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

Примером построения ячейки может служить ее программирование на программируемых логических интегральных схемах (ПЛИС).

На фиг.1 приведена функциональная схема ячейки однородной структуры, где 1, 2 - информационные входы, 3 - вход синхронизации, 4, 5 - информационные выходы, 6 - элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, 7 - элемент И, 8, 9 - триггеры.

Ячейка однородной структуры реализует следующую систему логических функций:

Q₁(t)=a⊕b

Q₂(t)=a•b

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

Q₁(t), Q₂(t) - соответственно состояние сигналов на выходах 4 и 5 ячейки.

Ячейка работает в соответствии с таблицей 1, приведенной в приложении:

Второе заявляемое техническое решение - однородная вычислительная среда.

Известно техническое решение однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2310223 С2. Устройство содержит: N2 полных сумматоров, первый, второй, третий, …, i-й, …, n-й входы для первого слагаемого, первый, второй, третий, …, i-й, …, n-й входы для второго слагаемого, первый, второй, третий, …, i-й, …, n-й входы переноса, первый, второй, i-й, …, n-й выходы суммы, первый, второй, …, i-й, …, n-й выходы переноса, где N=1, 2, …, N. Недостаток состоит в больших аппаратурных затратах и значительном числе связей между элементами, что приводит к снижению быстродействия и надежности устройства.

Наиболее близкое к заявляемому решению является техническое решение однородной вычислительной среды, запатентованное в качестве изобретения - патент RU №2295147 С1. Устройство содержит: ячейки однородной вычислительной структуры, информационные входы однородной вычислительной структуры, Y_IN1-Y_IN3, OP1-OP3, ARITH1-AMTH3, LOAD1-LOAD3, SET1-SET3, М1-М3, K1-K3, Z1-Z3 - управляющие входы ОВС, OP_OUT1-OP_OUT3, ARITH_OUT1-ARITH_OUT3, LOAD_OUT1-LOAD_OUT3, SET_OUT1-SET_OUT3, Y_OUT1-Y_OUT3 - управляющие выходы, S1-S3 и P1-P3 - информационные выходы однородной вычислительной среды. Недостаток состоит в том, что устройству необходима предварительная настройка для работы по заданному модулю, что приводит к увеличению связей между ячейками однородной среды, что в свою очередь приводит к понижению надежности.

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

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

Описание работы устройства: на каждом такте на входы синхронизации триггеров подается сигнал синхронизации. На первый и второй входы ячеек первого столбца подаются соответствующие разряды информационных векторов первого и второго операндов соответственно, причем каждая следующая пара бит подается на следующий такт работы устройства. Затем вектор передается в соседний справа в преобразованном виде. Значение i-го разряда в j-м столбце определяется значением (i-1)-го разряда вектора в (j-i)-м столбце, а также значением i-м разрядом вектора в (j-i)-м столбце.

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

Так как в ячейке обе цепочки распространения сигнала имеют по одному логическому элементу, время задержки распространения сигнала составляет t, где t - время задержки сигнала одним логическим элементом, что меньше в три раза по сравнению с исходным вариантом, запатентованным в качестве изобретения - патент RU 2295147 С1, равным 5t.

Примером построения однородной вычислительной среды может служить ее программирование на ПЛИС.

На фиг.3 представлена структурная схема однородной вычислительной среды в общем виде на базе ячейки однородной структуры, предназначенная для подсчета единичных бит m-мерных двоичных векторов, где CELL - ячейки однородной структуры, информационные входы первого операнда X₁-X_m, информационные входы второго операнда Y₁-Y_m, выходы однородной вычислительной среды Z₁-Z_m+1.

На фиг.4 изображен пример суммирования двоичных векторов X=111 и Y=001 разрядностью m=3, которые подаются на информационные входы X₁-X₃ и Y₁-Y₃ соответственно. Внутри ячейки однородной вычислительной среды описаны номера входов и выходов ячейки. При этом на фиг.4 показана передача данных с выходов (i, j)-й ячейки на соответствующие входы (i, j+1)-й и (i+1, j+1) ячейки однородной вычислительной среды. Через четыре такта работы устройства младший бит результата доступен на выходах Z₁-Z₃ однородной вычислительной среды.

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

Известно техническое решение арифметического устройства на базе однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2310223 С2. Устройство содержит: N2 полных сумматоров, первый, второй, третий, …, i-й, …, n-й входы для первого слагаемого, первый, второй, третий, …, i-й, …, n-й входы для второго слагаемого, первый, второй, третий, …, i-й, …, n-й входы переноса, первый, второй, i-й, …, n-й выходы суммы, первый, второй, …, i-й, …, n-й выходы переноса, где N=1, 2, …, N. Недостаток состоит в больших аппаратурных затратах и значительном числе связей между элементами, что приводит к снижению быстродействия и надежности устройства.

Наиболее близкое к заявляемому решению является техническое решение арифметического устройства однородной вычислительной среды, запатентованное в качестве изобретения - патент RU №2295147 С1. Устройство содержит: ячейки однородной вычислительной структуры, информационные входы однородной вычислительной структуры, Y_IN1-Y_IN3, ОР1-ОР3, ARITH1-AMTH3, LOAD1-LOAD3, SET1-SET3, М1-М3, К1-К3, Z1-Z3 - управляющие входы ОВС, OP_OUT1-OP_OUT3, ARITH_OUT1-ARITH_OUT3, LOAD_OUT1-LOAD_OUT3, SET_OUT1-SET_OUT3, Y_OUT1-Y_OUT3 - управляющие выходы, S1-S3 и Р1-Р3 - информационные выходы однородной вычислительной среды. Недостаток состоит в том, что устройству необходима предварительная настройка для работы по заданному модулю, что приводит к увеличению связей между ячейками однородной среды, что в свою очередь приводит к понижению надежности.

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

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

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

Двухразрядный код операции подается на управляющие входы U₁ и U₂ всех таблиц подстановок (ТП).

Первая и вторая таблицы подстановок осуществляют преобразование двоичных m-разрядных векторов А и В соответственно, поданных на соответствующие разряды информационных входов первой и второй таблиц подстановок в выходной вектор Х и Y соответственно, по правилу, определяемому кодом операции. Кодирование операций и необходимое преобразование для первой и второй таблиц подстановок представлено в таблице 2, приведенной в приложении.

Третья таблица подстановок осуществляет преобразование двоичного (m+1)-разрядного вектора Z, поданного на соответствующие разряды информационных входов таблицы подстановок в выходной вектор С по правилу, определяемому кодом операции. Кодирование операций и необходимое преобразование для первой и второй таблиц подстановок представлено в таблице 3.

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

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

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

Так как в ячейке обе цепочки распространения сигнала имеют по одному логическому элементу, время задержки распространения сигнала составляет t, где t - время задержки сигнала одним логическим элементом, что меньше в четыре раза по сравнению с исходным вариантом, запатентованным в качестве изобретения - патент RU №2295147 С1, равным 5t.

Примером построения однородной вычислительной среды может служить ее программирование на ПЛИС.

На фиг.5 представлена структурная схема операционного устройства на базе ячеек однородной вычислительной среды, где 1, 2 - m-разрядные информационные входы, 3 - двухразрядный управляющий вход кода операции, 4, 5 - первая и вторая таблицы подстановок соответственно, 6, 7 - m-разрядные шины данных, соединяющие выходы первой и второй таблиц подстановок с первым и вторым информационными входами однородной вычислительной среды соответственно, 8 - однородная вычислительная среда на базе ячеек рассмотренного типа, 9 - (m+1)-разрядная шина данных, соединяющая выход однородной вычислительной среды с информационным входом третьей таблицы подстановок, 10 - третья таблица подстановок, 11 - m-разрядный информационный выход устройства.

На фиг.6 представлен пример реализации операции деления нацело по модулю 5, где 1, 2, 3 - первая, вторая и третья таблица подстановок соответственно. Внутри ячейки однородной вычислительной среды описаны номера входов и выходов ячейки. При этом делимое A=001₂, делимое B=011₂. Таблица подстановок делимого произвела переход из мультипликативной группы к аддитивной группе по модулю 5: A=|log₃1|₅=0₁₀=000₂. ТП делителя произвела замену остатка Y на обратную величину, взятую по модулю 5 с переходом из мультипликативной группы к аддитивной: B=|log₃((5+1)/3)|₅=3₁₀=011₂. Полученные остатки А и В просуммированы за пять тактов работы устройства в однородной вычислительной среде. При этом на фиг.6 показана передача данных с выходов j-го столбца на соответствующие входы (j+1)-го столбца. Затем с помощью выходной таблицы подстановок был осуществлен переход из аддитивной группы в мультипликативную группу: Z=|3³|₅=2₁₀=010₂.

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

Таблица 1
Вход a	Вход b	Q1(t)	Q2(t)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Таблица 2
Вход U1	Вход U2	Операция	Преобразование первой таблицей подстановок	Преобразование второй таблицей подстановок
0	0	Сложение	Х-А	Y=B
0	1	Вычитание	Х-А	Y=~B+1
1	0	Умножение	X=|log3A|p	X=|log3B|p
1	1	Деление нацело	X=|log3A|p	X=|1/log3B|p

Таблица 3
Вход U1	Вход U2	Операция	Преобразование третьейТП при Z<p	Преобразование третьейТП при Z≥p
0	0	Сложение	C=Z	C=Z-p
0	1	Вычитание	C=Z	C-Z-p
1	0	Умножение	C=|3Z|p	C=|3Z-p|p
1	1	Деление нацело	C=|3Z|p	C=|3Z-p|p

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

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

3. Устройство для конвейерных арифметических вычислений по заданному модулю р, где р - простое число, которое содержит первую таблицу подстановок, вторую таблицу подстановок, третью таблицу подстановок, где каждая из таблиц подстановок представляет собой устройство, выполняющее однотактную табличную выборку, однородную вычислительную среду по п.2, управляющие входы, информационные входы и выходы, первая таблица подстановок выполняет преобразование в соответствие с одной из функций, в зависимости от выполняемой операции: Х=А в случае выполнения операций сложения или вычитания, Х=|log₃ A|_р в случае операций умножения или деления нацело, где А - значение вектора на m-контактном информационном входе первой таблицы подстановок, X - значение вектора на m-контактном выходе первой таблицы подстановок, вторая таблица подстановок выполняет преобразование в соответствие с одной из функций, в зависимости от выполняемой операции: Y=B в случае выполнения операции сложения, в случае операции вычитания, Y=|log₃ B|_p в случае операции умножения, Y=|1/log₃ B|_p в случае операции деления нацело, где В - значение вектора на m-контактном информационном входе второй таблицы подстановок, Y - значение вектора на m-контактном выходе второй таблицы подстановок, третья таблица подстановок выполняет преобразование в соответствие с одной из функций, в зависимости от выполняемой операции и при Z<p:C=Z в случае выполнения операции сложения или вычитания, C=|3^Z-p|_P в случае операции умножения или деления нацело, при Z>p:C=Z-p в случае выполнения операции сложения или вычитания, C=|3^Z-p|_P в случае операции умножения или деления нацело, где С - значение вектора на (m+1)-контактном информационном входе третьей таблицы подстановок, Z - значение вектора на m-контактном выходе третьей таблицы подстановок, первый и второй управляющие входы первой, второй и третьей таблиц подстановок соединены соответственно с первым и вторым управляющими входами схемы, на которые подается двухразрядный код выполняемой операции, первый m-контактный информационный вход устройства соединен с m-контактным информационным входом первой таблицы подстановок, m-контактный выход которой соединен с первым m-контактным информационным входом однородной вычислительной среды, (m+1)-контактный выход которой соединен m-контактным информационным входом третьей таблицы подстановок, m-контактный выход которой соединен с неконтактным выходом устройства, с которого снимается результат, второй m-контактный информационный вход устройства соединен с m-контактным информационным входом второй таблицы подстановок, m-контактный выход которой соединен со вторым m-контактным информационным входом однородной вычислительной среды, вход синхронизации устройства соединен с входом синхронизации однородной вычислительной среды.