Результат интеллектуальной деятельности: ЯЧЕЙКА ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ, ОДНОРОДНАЯ ВЫЧИСЛИТЕЛЬНАЯ СРЕДА И УСТРОЙСТВО ДЛЯ КОНВЕЙЕРНЫХ ВЫЧИСЛЕНИЙ СУММЫ м n-РАЗРЯДНЫХ ЧИСЕЛ

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

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

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

Операнд - данное, которое обрабатывается в однородной вычислительной среде.

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

Известно техническое решение ячейки однородной вычислительной среды, авторское свидетельство SU №1513471 A1 от 07.10.1988, которая содержит вход синхронизации 1, первый 2 и второй 3 информационные входы, логические входы 4-6, первый 7 и второй 8 функциональные выходы, триггеры 9, 11, элементы НЕ 10, 13, 19, элементы И 14, 16-18, элементы ИЛИ 12, 15 с соответствующими связями.

Недостатком является относительно низкое быстродействии ячейки, которое составляет 4t, где t - время задержки сигнала одним логическим элементом, в предлагаемом решении время задержки сокращено в четыре раза и подсчет количества единичных бит двоичного вектора производится сразу в двоичном, а не в унитарном коде.

Наиболее близким к заявляемому решению является техническое решение ячейки однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2284568 C2 от 27.09.2006, которое содержит два информационных и один управляющий входы, два выхода, четыре элемента И, два элемента НЕ, элемент ИЛИ с соответствующими связями. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает функциональные возможности и быстродействие устройства, а также низкое быстродействие ячейки, которое составляет 3t, где t - время задержки сигнала одним логическим элементом, в предлагаемом решении время задержки сокращено в три раза.

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

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

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

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

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

Q₁(t)=a*b

Q₂(t)=a⊕b

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

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

Ячейка работает следующим образом:

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

Известно техническое решение параллельного счетчика единичных сигналов, запатентованное в качестве изобретения - патент RU №2260204 C1, устройство содержит семнадцать элементов «исключающее ИЛИ» и тринадцать элементов «И», первый и второй входы r-го элемента «исключающее ИЛИ» соединены соответственно с первым и вторым входами r-го элемента «И», подключенного первым входом к (r+1)-му входу параллельного счетчика единичных сигналов, первые выход и вход которого соединены соответственно с выходом седьмого элемента «исключающее ИЛИ» и вторым входом первого элемента «И», подключенного выходом к второму входу восьмого элемента «исключающее ИЛИ», выходы первого-пятого и шестого элементов «исключающее ИЛИ» соединены соответственно с вторыми входами второго-шестого и седьмого элементов «И», подключенных выходами соответственно к первым входам восьмого-двенадцатого и тринадцатого элементов «исключающее ИЛИ», выходы которых соединены соответственно с вторыми входами девятого-тринадцатого элементов «И» и вторым выходом параллельного счетчика единичных сигналов, первый и второй входы r-го элемента «исключающее ИЛИ» соединены соответственно с первым и вторым входами r-го элемента «И», а выходы десятого-двенадцатого и тринадцатого элементов «И» подключены соответственно к первым входам четырнадцатого - шестнадцатого и семнадцатого элементов «исключающее ИЛИ», подсоединенных выходами соответственно к вторым входам пятнадцатого-семнадцатого элементов «исключающее ИЛИ» и третьему выходу параллельного счетчика единичных сигналов. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.

Наиболее близкое к заявляемому решению является техническое решение однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2284568 C2. Устройство содержит: ячейки однородной вычислительной среды 1,1-1,m, 2,1-2,m,…,n,1-n, m, информационные входы а₀-а_n, b₀-b_m, информационные выходы р_о-р_n, с₀-c_m, управляющий вход М, соединенный с управляющими входами m, каждой ячейки однородной вычислительной среды. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства, а также состоит в значительных аппаратурных затратах.

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

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

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

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

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

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

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

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

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

Известно техническое решение многоуровневой матричной суммирующей структуры вертикальной арифметики В.М.Таранухи, запатентованное в качестве изобретения - патент RU 2246128 С2 от 10.02.2005. Многоуровневевая m-мерная матричная суммирующая структура содержит узлы одноразрядного суммирования первого, второго и третьего уровней, m-мерные матричные структуры одноразрядного суммирования второго, третьего и четвертого уровней, образующих иерархическую многоуровневую суммирующую структуру вертикальной арифметики, представляющую регулярную связанную по вертикали иерархическую логарифмическую структуру с межуровневыми связями, по горизонтали иерархическую матричную структуру, в которой матричные структуры предыдущих уровней, объединенные связями, образуют матричную структуру следующего иерархического уровня многоуровневой m-мерной матричной структуры. Недостаток состоит в значительных аппаратурных затратах и большом количестве связей, что приводит к снижению надежности устройства, а также сложности масштабирования устройства.

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

Техническим результатом от использования устройства для конвейерных вычислений суммы m n-разрядных чисел является повышение быстродействия за счет замены операции сложения операцией подсчета количества единичных бит в разрядных срезах, где младший бит подсчета Y₁ является i-м битом результата суммирования, каждый следующий бит Y_k, где k∈[2, log₂m], является переносом в i+k столбец устройства, который затем также участвует в процессе подсчета единиц в соответствующем столбце. Также появляется возможность простого масштабирования благодаря регулярности структуры.

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

Массив исходных n-разрядных слагаемых количеством m помещается в блок срезов, который выполнен на базе информационных триггеров, образующих прямоугольную матрицу, вход синхронизации блока задержки соединен с входами синхронизации всех триггеров, информационный вход блока задержки соединен с соответствующими информационными входами триггеров первого столбца, информационный выход каждого (ij)-го триггера подключен к информационному входу (i,j+1)-го триггера, количество строк блока срезов равно m, количество столбцов блока срезов равно n*p+m-1, где p=]log₂m+g-1[, g=]log₂m[,] [ - окгругление до большего целого, информационный выход последних в строке триггеров блока задержки является выходом блока задержки.

Однородная вычислительная среда рассмотренного типа имеет размерность m+р-1 строк и р столбцов.

Выход Y₂ подключен к X_m+1 входу однородной вычислительной среды. Выходы Y₃-Y_p подключены к соответствующим входам блока задержки, выполненного на базе информационных триггеров. Вход синхронизации блока задержки соединен с входами синхронизации всех триггеров. Информационные входы блока задержки соединены с соответствующими информационными входами триггеров первого столбца, информационный выход каждого (i,j)-го триггера подключен к информационному входу (i,j+1)-го триггера, количество строк однородной вычислительной среды равно р-2, причем в i-й строке содержится i*p триггеров, информационный выход последних в строке триггеров является выходами блока задержки, который подключен к соответствующим X_m+2-X_m+p-1 входам однородной вычислительной среды. Задержка необходима для того, чтобы распространение переноса в i-й столбец происходило в момент времени, когда идет обработка i-го столбца. Количество тактов задержки для выхода Y_k равно t=(k-2)*p, k∈[2,p].

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

i-e слагаемое записывается в i-ю строку блока срезов, при этом оно предварительно сдвинуто на i-1 разрядов влево.

Устройство осуществляет подсчет количества единичных бит в столбце (разрядном срезе) приведенной выше матрицы, в результате чего вычисляется результат суммирования текущего среза Y₁, а также переносы Y₂-Y_p в соответствующие разрядные срезы, следующие за текущим. С выхода Y_r, r∈ [2,p] снимается единица переноса в (i+r)-й разрядный срез.

Пример: необходимо сложить четыре (m=4) трехбитных (n=3) операнда: a₁=111, а₂=101, а₃=001, a₄=111. Запишем их в виде матрицы с элементами aij:

Первоначально операнды записываются в строки блока срезов размерностью m=4 строк и n*p+m-1=12 столбцов в виде матрицы, где p=]log₂(4+3-1)[=3. Так как производится обработка одной суммы, то между каждым из разрядов слагаемых записывается р-1=2 нуля, при этом i-e слагаемое сдвинуто на (i-1) разрядов влево:

Каждый такт информация из блока срезов (крайний правый столбец матрицы) передается на входы однородной вычислительной среды, при этом содержимое блока срезов сдвигается на один разряд вправо. Однородная вычислительная среда имеет размерность m+р-1=6 строк и р=3 столбцов.

Так как в первом разрядном срезе слагаемых четыре единицы, на выходе однородной вычислительной среды, через шесть тактов работы устройства будет сформирован бит результата s_1,1=0, на седьмом такте будет сформирован перенос во второй столбец s_1,2=0, на восьмом такте будет сформирован перенос в третий столбец s_1,3=1, который записывается в блок задержки, размерность которого р-2=1 строка и 1*р=3 столбца. Затем происходит подсчет единиц во втором столбце матрицы с учетом переноса из первого столбца, бит результата s_2,1=0, бит переноса в третий столбец s_2,2=1, перенос в четвертый столбец s_2,3=0. При подсчете единиц в третьем столбце учитываются перенос из первого столбца s_1,3=1 (доступен с выхода блока задержки) и перенос из второго столбца s_2,2=1. Так как общее количество единиц стало равно пяти, то бит результата s_3,1=1, бит переноса в четвертый столбец s_3,2=0, перенос в пятый столбец s_3,3=1. Так как s_2,3=0, то переносы s_3,2 и s_3,3 станут старшими битами результата суммирования, который равен (s_3,3, s_3,2, s_3,l, s_2,1, s_1,1)=10100.

Для избегания простоев работы конвейера в сумматоре необходимо вычислять сразу p разных сумм, при этом разрядные срезы должны подаваться на вход сумматора друг за другом в одном и том же порядке. В этом случае быстродействие сумматора линейно зависит от разрядности слагаемых и время вычисления каждой суммы равно n тактам, в то время как время суммирования итерационным способом равно m*n тактов. При вычислении одной суммы время вычисления равно m+2*p-1+p*n тактов.

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

На фиг.5 представлена структурная схема блока задержки в общем виде, предназначенного для формирования задержки выдачи информации на определенное количество тактов. Блок задержки построен на базе информационных триггеров, где Tg - информационные триггеры, 1-3 - информационные входы блока задержки, 4 - вход синхронизации, 5-7 - информационные выходы блока задержки.

На фиг.6 представлена структурная схема блока задержки в общем виде, предназначенного для формирования задержки выдачи информации на определенное количество тактов. Блок задержки построен на базе информационных триггеров, где Tg - информационные триггеры, 1-3 - информационные входы блока задержки, 4 - вход синхронизации, 5-7 - информационные выходы блока задержки.

На фиг.7 представлена структурная схема устройства для конвейерных вычислений суммы m n-разрядных чисел в общем виде, предназначенного для вычисления суммы n-мерных двоичных векторов на базе однородной вычислительной среды, где 1 - блок срезов, 2 - однородная вычислительная среда, 3 - блок задержки, информационные входы схемы Z₁-Z_m, выход однородной вычислительной среды Y₁ является выходом устройства, выход Y₂ подключен к информационному входу Х_m+1 однородной вычислительной среды, выходы однородной вычислительной среды Y₃-Y_p подключены к соответствующим входам блока задержки, выходы которого подключены к соответствующим входам X_m+2-X_m+p-1 однородной вычислительной среды.

На фиг.8 изображен пример построения устройства для конвейерных вычислений суммы m=4 n-разрядных чисел на базе однородной вычислительной среды, где 1 - блок срезов, 2 - однородная вычислительная среда, 3 - блок задержки, информационные входы схемы Z₁-Z₄, выход устройства Y₁, выход однородной вычислительной среды Y₂ подключен к информационному входу Х₅, выход однородной вычислительной среды У₃ подключен к входу блока задержки, выход которого подключен к входу Х₆ однородной вычислительной среды.