ЯЧЕЙКА ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ Российский патент 2006 года по МПК G06F7/57 

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

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

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

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

где а и b - сигналы, подаваемые на первый и второй информационные входы ячейки, m - сигнал, подаваемый на управляющий вход ячейки, с и р - сигналы, формируемые соответственно на первом и втором информационных выходах ячейки, содержащую первый и второй информационные входы, первый и второй выходы, первый, второй, третий элементы И и элемент НЕ, дополнительно введены управляющий вход, четвертый элемент И, второй элемент НЕ и элемент ИЛИ, причем управляющий вход ячейки соединен с первым входом первого элемента И, первый информационный вход соединен со вторым входом первого элемента И, с входом первого элемента НЕ, с первым входом третьего элемента И, с первым входом четвертого элемента И, второй информационный вход соединен с третьим входом первого элемента И, со вторым входом второго элемента И, с входом второго элемента НЕ, со вторым входом четвертого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, выход второго элемента НЕ соединен со вторым входом третьего элемента И, выход первого элемента И соединен с первым входом элемента ИЛИ, выход второго элемента И соединен со вторым входом элемента ИЛИ, выход третьего элемента И соединен с третьим входом элемента ИЛИ, выход элемента ИЛИ соединен с первым выходом ячейки, выход четвертого элемента И соединен со вторым выходом ячейки.

Введение новых элементов и связей между ними обеспечивает решение поставленной задачи.

На фиг.1 изображен общий вид однородной вычислительной среды. Устройство (фиг.1) содержит: ячейки однородной вычислительной среды 1,1-1,m, 2,1-2,m,..., n,1-n,m, информационные входы а₀-а_n, b₀-b_m, информационные выходы p₀-p_n, c₀-c_m, управляющий вход М, соединенный с управляющими входами m, каждой ячейки однородной вычислительной среды.

На фиг.2 приведена функциональная схема ячейки. Устройство (фиг.2) содержит первый и второй информационные входы, первый и второй выходы, первый, второй, третий элементы И и элемент НЕ, управляющий вход, четвертый элемент И, второй элемент НЕ и элемент ИЛИ, причем управляющий вход ячейки соединен с первым входом первого элемента И, первый информационный вход соединен со вторым входом первого элемента И, с входом первого элемента НЕ, с первым входом третьего элемента И, с первым входом четвертого элемента И, второй информационный вход соединен с третьим входом первого элемента И, со вторым входом второго элемента И, с входом второго элемента НЕ, со вторым входом четвертого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, выход второго элемента НЕ соединен со вторым входом третьего элемента И, выход первого элемента И соединен с первым входом элемента ИЛИ, выход второго элемента И соединен со вторым входом элемента ИЛИ, выход третьего элемента И соединен с третьим входом элемента ИЛИ, выход элемента ИЛИ соединен с первым выходом ячейки, выход четвертого элемента И соединен со вторым выходом ячейки.

На фиг.3 схематически изображено выполнение операции сжатия двоичного вектора (выполнение операции подсчета числа единиц в унитарном коде). Устройство (фиг.3) содержит ячейки однородной вычислительной среды 1,1-1,4, 2,1-2,4,..., 4,1-4,4, информационные входы а₀-а₃, b₀-b₃ и информационные выходы с₀-с₃, р₀-р₃.

На фиг.4 схематически изображено выполнение операции подсчета числа единиц в двоичном коде. Устройство (фиг.4) содержит ячейки однородной вычислительной среды 1,1-1,4, 2,1-2,4,..., 4,1-4,4, информационные входы а₀-а₃, b₀-b₃ и информационные выходы c₀-c₃, р₀-р₃.

На фиг.5 схематически изображена работа однородной вычислительной среды в режиме подсчета числа единиц и представления результата в унитарном коде при работе с N+M разрядными данными, где N - количество информационных входов а ОВС, а М количество информационных входов b ОВС. Устройство (фиг.5) содержит ячейки однородной вычислительной среды 1,1-1,8, 2,1-2,8,..., 4,1-4,8, информационные входы а₀-а₃, b₀-b₇ и информационные выходы c₀-c₇, р₀-р₃.

Ячейка однородной вычислительной среды (ЯОВС) реализует следующую систему логических функций (1):

где а и b - сигналы, соответственно подаваемые на информационные входы 2 и 3 ячейки;

m - сигнал, формируемый соответственно на управляющем входе 1;

с и р - сигналы, формируемые соответственно на информационных выходах 4 и 5 ячейки;

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

Режим подсчета числа единиц в битовом массиве и представление результата в унитарном коде.

Задача, которую решает устройство в данном режиме, заключается в формировании на группе выходов c₀, c₁,..., c_m однородной среды унитарного кода, равного числу единиц двоичного вектора, поступающего в однородную среду соответственно по входам а₀, а₁,..., а_n.

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

Для выполнения данной операции достаточно исходный двоичный вектор подать на группу входов a₀, a₁,..., a_n однородной вычислительной среды, причем младший значащий разряд числа должен быть подан на вход а₀, т.е. на второй вход первой ячейки первого столбца первой строки. На группу входов b₀, b₁,..., b_m подается нулевой вектор. При этом в ячейках каждого столбца ОВС в соответствии с системой (1) выполняется вычисление следующих функций:

В результате значения с и р сигналов i-й ячейки ОВС формируются следующим образом. Если или сигнал а или сигнал b i-й ячейки ОВС имеет единичное значение, то на выходе с i-й ячейки формируется сигнал логической единицы, а на выходе р i-й ячейки формируется нулевой сигнал. Если и сигнал а и сигнал b i-й ячейки ОВС имеют единичное значение, то на выходе с i-й ячейки формируется сигнал логической единицы, и на выходе р i-й ячейки формируется сигнал логической единицы. Если и сигнал а и сигнал b i-й ячейки ОВС имеют значение логического нуля, то на выходе с i-й ячейки формируется сигнал логического нуля, и на выходе р i-й ячейки формируется сигнал логического нуля.

Таким образом, через k тактов (где k - число единиц в битовом массиве) на выходах c₀, c₁,..., c_m однородной вычислительной среды будет получен результат вычислений.

Пример выполнения операции подсчета числа единиц в битовом массиве и представления результата в унитарном коде приведен на фиг.3, где на группу входов а₀, а₁,..., а₃ подается вектор 1101₂. Для рассматриваемого на фиг.3 случая с входа а₀ ячейки однородной вычислительной среды первой строки первого столбца на выход с₀ коммутируется единица, которая транслируется по b_i-c_i - каналам первого столбца на выход с₀, при этом единицы с входов а ячейки 3,1 и ячейки 4,1 транслируются по каналам a_i-p_i на входы а ячейки 3,2 и ячейки 4,2 второго столбца третьей и четвертой строки однородной среды соответственно. Далее по аналогии, единица с входа а ячейки 3,2 транслируется по b_i-с_i - каналам второго столбца на выход c₁, а единица с входа а ячейки 4,2 транслируется по а_i-р_i на вход а ячейки 4,3 и затем на выход с₂. Таким образом на выходах с₀-c₂ формируется унитарный код равный числу единиц в битовом векторе.

Режим подсчета числа единиц в битовом массиве и представление результата в двоичном коде.

Задача, которую решает устройство в данном режиме вычислений, заключается в формировании на группе выходов c₀, c₁,..., c_m OBC двоичного кода, равного числу единиц двоичного вектора, поступающего в однородную среду соответственно по входам a₀, a₁,..., a_n.

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

Для выполнения данной операции достаточно, исходный двоичный вектор подать на группу входов a₀, a₁,..., a_n, причем младший значащий разряд числа должен быть подан на вход а₀, т.е. на второй вход первой ячейки первого столбца первой строки. На группу входов b₀, b₁,..., b_m подается нулевой вектор. При этом в ячейках каждого столбца однородной среды в соответствии с системой (1) выполняется вычисление следующих функций:

Таким образом, на выходах c_i каждой ячейки однородной среды формируется сумма чисел по модулю 2, а на выходах р_i - перенос в следующий столбец ОВС.

Пример выполнения операции подсчета числа единиц в битовом массиве и представления результата в двоичном коде приведен на фиг.4, где на группу входов а₀, а₁,..., а₃ подается вектор 1011₂.

Сложение нечетного числа единиц в первом столбце ячейки, поданных на группу входов а₀, а₁,..., а₃ ОВС (в данном примере их три) формирует единичный сигнал на выходе со первого столбца и одну единицу переноса в следующий столбец ОВС, которая, попадая на выход второго столбца c₁, формирует конечный результат, равный 11₂.

Заметим, что если в режиме подсчета числа единиц и представления результата в двоичном виде возможна работа только с N разрядными операндами, где N число информационных входов а однородной среды, то в режиме подсчета числа единиц и представления результата в унитарном коде возможна работа с N+M разрядными данными, где N - количество информационных входов а ОВС, а М количество информационных входов b ОВС.

Пример данного замечания приведен на фиг.5, где на группу входов а₀...а₃ подается двоичный вектор 1011₂, а на группу входов b₀...b₇ подается вектор 1110₂, в результате вычислений по формуле 2, на группе выходов с₀...c₇ формируется вектор результата, равный 111111₂.

Применение предлагаемой ячейки однородной вычислительной среды позволяет реализовать операции унитарного и двоичного счетчика. При этом заметим, что выполнение операций в данной ячейке производится быстрее, чем в прототипе, т.к. в обоих режимах, выполняемых в данной ячейке, наиболее длинные цепочки включенных элементов состоят из следующего набора элементов, соответственно, первая цепочка: первый элемент НЕ, второй элемент И и элемент ИЛИ, и вторая цепочка: второй элемент НЕ, третий элемент И и элемент ИЛИ. Таким образом, время задержки распространения сигнала в наиболее длинных цепочках элементов данного устройства (фиг.2) составляет время 3t, где t - время задержки сигнала одним логическим элементом, что меньше по сравнению с исходным вариантом по авт. св. №1513471 А1, равным 4t.

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

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

где а и b - сигналы, подаваемые на первый и второй информационные входы ячейки, m - сигнал, подаваемый на управляющий вход ячейки, с и р - сигналы, формируемые соответственно на первом и втором информационных выходах ячейки, содержащая первый и второй информационные входы, первый и второй выходы, первый, второй, третий элементы И и элемент НЕ, отличающаяся тем, что дополнительно введены управляющий вход, четвертый элемент И, второй элемент НЕ и элемент ИЛИ, причем управляющий вход ячейки соединен с первым входом первого элемента И, первый информационный вход соединен со вторым входом первого элемента И, с входом первого элемента НЕ, с первым входом третьего элемента И, с первым входом четвертого элемента И, второй информационный вход соединен с третьим входом первого элемента И, со вторым входом второго элемента И, с входом второго элемента НЕ, со вторым входом четвертого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента И, выход второго элемента НЕ соединен со вторым входом третьего элемента И, выход первого элемента И соединен с первым входом элемента ИЛИ, выход второго элемента И соединен со вторым входом элемента ИЛИ, выход третьего элемента И соединен с третьим входом элемента ИЛИ, выход элемента ИЛИ соединен с первым выходом ячейки, выход четвертого элемента И соединен со вторым выходом ячейки.