Ячейка однородной вычислительной среды и устройство для сжатия двоичных векторов на базе ячеек однородной вычислительной среды
Владельцы патента RU 2450327:
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Вятский государственный университет" (ФГБОУ ВПО "ВятГУ") (RU)
Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих сжатие массивов двоичных векторов в конвейерном режиме. Техническим результатом является повышение надежности однородной вычислительной среды за счет сокращения числа связей между ячейками однородной вычислительной среды и повышение быстродействия за счет использования более быстродействующих ячеек однородной вычислительной среды. Устройство содержит матрицу ячеек однородной вычислительной среды, содержащую m-1 строк и m-1 столбцов, где m - число разрядов входного сигнала, при этом ячейка содержит элемент ИЛИ, элемент И, два триггера. 3 ил., 1 табл.
Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих сжатие двоичных векторов.
Однородной вычислительной средой называется регулярная структура, состоящая из соединенных друг с другом одинаковых ячеек, выполняющая определенную функцию. Ячейка однородной вычислительной среды - элемент регулярной структуры. Разряды вектора кодируются состоянием сигнала и соответствуют значениям логической единицы или логического нуля на входах и выходах ячейки однородной вычислительной среды.
Известно техническое решение ячейки однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2284568 С2, которое содержит два информационных и один управляющий входы, два выхода, четыре элемента И, два элемента НЕ, элемент ИЛИ с соответствующими связями. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.
Наиболее близкой к заявляемому решению является техническое решение ячейки однородной вычислительной среды, авторское свидетельство SU №1513471 А1, которая содержит вход синхронизации 1, первый 2 и второй 3 информационные входы, логические входы 4-6, первый 7 и второй 8 функциональные выходы, триггеры 9, 11, элементы НЕ 10, 13, 19, элементы И 14, 16-18, элементы ИЛИ 12, 15 с соответствующими связями.
Недостатком является относительно низкое быстродействии ячейки, которое составляет 4t, где t - время задержки сигнала одним логическим элементом, в предлагаемом решении время задержки сокращено в четыре раза.
Технический результат заявляемого решения: предлагаемое изобретение направлено на повышение быстродействия ячейки за счет сокращения числа элементов в цепях распространения информационного сигнала и связей: первый информационный вход ячейки подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ подключен к второму информационному входу ячейки, первый и второй информационные входы ячейки подключены соответственно к первому и второму входу элемента И, выход которого подключен к информационному входу второго триггера.
Описание технического решения ячейки: ячейка однородной вычислительной среды состоит из одного двухвходового элемента И, одного двухвходового элемента ИЛИ и двух триггеров, вход синхронизации ячейки соединен с входами синхронизации первого и второго триггера, выход элемента ИЛИ подключен к информационному входу первого триггера, первый информационный вход ячейки подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ подключен к второму информационному входу ячейки, выход которого подключен к информационному входу первого триггера, первый и второй информационные входы ячейки подключены соответственно к первому и второму входу элемента И, выход которого подключен к информационному входу второго триггера, информационные выходы первого и второго триггера являются первым и вторым информационными выходами ячейки.
Примером построения ячейки может служить ее схема, созданная путем программирования на программируемых логических интегральных схемах (ПЛИС).
На фиг.1 приведена функциональная схема ячейки однородной структуры, где 1, 2 - информационные входы, 3 - вход синхронизации, 4, 5 - информационные выходы, 6 - элемент ИЛИ, 7 - элемент И, 8, 9 - триггеры.
Ячейка однородной структуры реализует следующую систему логических функций:
Q1(t)=a∨b
Q2(t)=a·b
где a, b - соответственно состояние сигналов на входах 1 и 2 ячейки;
Q1(t), Q2(t) - соответственно состояние сигналов на выходах 4 и 5 ячейки.
Ячейка работает следующим образом.
| Вход a | Вход b | Q1(t) | Q2(t) |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Второе заявляемое техническое решение - устройство для сжатия двоичных векторов на базе ячеек однородной вычислительной среды рассмотренного типа.
Известно техническое решение однородной вычислительной среды, запатентованное в качестве изобретения - патент RU 2284568 С2. Устройство содержит: ячейки однородной вычислительной среды 1,1-1,m, 2,1-2,m,…, n,1-n,m, информационные входы a0-an, b0-bm, информационные выходы p0-pn, c0-cm, управляющий вход М, соединенный с управляющими входами m, каждой ячейки однородной вычислительной среды.. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.
Наиболее близкое к заявляемому решению - техническое решение однородной вычислительной среды, авторское свидетельство SU №1513471 А1. Устройство построено на базе ячеек. В процессе работы устройства информационный вектор подается на входы 2 и 3 ячейки первого столбца, причем i-й разряд вектора подается на вход 2 (i, 1) ячейки и вход 3 (i+1, 1) ячейки. Логический вектор подается на входы 4-6 ячеек первого столбца, причем i-й разряд вектора подается на вход 6 (i, 1) ячейки и вход 4 (i-1, 1) ячейки. Недостаток состоит в том, что устройство работает не только с информационным вектором, но и с логическим, что приводит к увеличению связей между ячейками однородной среды, что в свою очередь приводит к понижению надежности.
Технический результат заявляемого решения: предлагаемое изобретение направлено на повышение надежности однородной вычислительной среды за счет сокращения числа связей между ячейками однородной вычислительной среды и повышение быстродействия за счет использования более быстродействующих ячеек однородной вычислительной среды: первый и второй информационные входы (m/2) ячеек первого столбца однородной вычислительной среды при четном значении m соединены с соответствующими разрядами m-разрядного вектора, при нечетном значении m m-разрядный вектор соединен с соответствующими информационными входами ((m+1)/2) ячеек первого столбца, а оставшиеся незадействованные входы ячеек первого столбца соединены со значением логического нуля, первый информационный выход каждой (i, j)-й ячейки подключен к второму информационному входу (i, j+1)-й ячейки, второй информационный выход каждой (i, j)-й ячейки подключен к первому информационному входу (1+1, j+1)-й ячейки, кроме ячеек первой строки, начиная со второго столбца, первый информационный вход которых соединен со значением логической единицы.
Описание технического решения устройства для сжатия двоичных векторов на базе ячеек однородной вычислительной среды.
Однородная вычислительная среда из ячеек рассмотренного типа, обеспечивающая сжатие двоичных векторов, представляет собой матрицу: количество столбцов однородной вычислительной среды равно m-1, количество строк однородной вычислительной среды равно m-1. На первый и второй информационные входы (m/2) ячеек первого столбца однородной вычислительной среды при четном значении m подаются соответствующие разряды m-разрядного вектора, при нечетном значении m m-разрядный вектор соединен с соответствующими информационными входами ((m+1)/2) первого столбца матрицы однородной вычислительной среды, а на оставшиеся незадействованные входы ячеек первого столбца подано значение логического нуля, первый информационный выход каждой (i, j)-й ячейки подключен к второму информационном входу (i, j+1)-й ячейки, второй информационный выход каждой (i, j)-й ячейки подключен к первому информационном входу (i+1, j+1)-й ячейки, кроме ячеек первой строки, начиная со второго столбца, на первый информационный вход которых подано значение логической единицы.
Описание работы устройства: в каждом такте на входы синхронизации триггеров подается сигнал синхронизации. В результате вектор передается в соседний справа столбец преобразованном виде. Значение i-го разряда вектора в j-м столбце определяется значением (i-1)-го разряда вектора в (j-1)-м столбце. В результате через (m-1) такт работы устройства происходит сжатие m-мерного двоичного вектора. Первый и второй информационные выходы последних (m/2) ячеек последнего столбца однородной вычислительной среды при четном значении m и первый и второй информационные выходы ((m+1)/2) ячеек последнего столбца однородной вычислительной среды при нечетном значении m являются выходами схемы, с которых снимается результат. На выходах остальных ячеек будет присутствовать логическая единица. Так как на каждом такте работы устройства вектор передается в соседний справа столбец ячеек матрицы, на вход устройства на каждом такте может быть подан следующий вектор. Таким образом, устройство реализует конвейерный принцип обработки информации.
Так как в ячейке обе цепочки распространения сигнала имеют по одному логическому элементу, время задержки распространения сигнала в составляет t, где t - время задержки сигнала одним логическим элементом, значит, время работы всей однородной вычислительной среды составляет (m-1)*t, что меньше в четыре раза по сравнению с исходным вариантом по авт. св. №1513471 А1, равным (m-1)*4t.
Примером построения однородной вычислительной среды может служить ее схема, созданная путем программирования на ПЛИС.
На фиг.2 представлена структурная схема однородной вычислительной среды в общем виде на базе ячейки однородной структуры, предназначенная для сжатия m-мерных двоичных векторов при четном значении m, где CELL - ячейки однородной структуры, информационные входы X1-Xm, информационные выходы Y1-Ym.
На фиг.3 изображен пример выполнения операции сжатия двоичного вектора Х=101000 с разрядностью m=6, поданного на информационные входы X1-Х6 однородной вычислительной среды. При этом на фиг.3 показана передача данных с выходов j-го столбца на соответствующие входы (j+1)-го столбца. Через пять тактов работы устройства результат сжатия Y=000011 доступен на выходах Y1-Y6 однородной вычислительной среды.
1. Ячейка однородной вычислительной среды, содержащая первой и второй информационные входы, вход синхронизации, два информационных выхода, двухвходовой элемент ИЛИ, двухвходовой элемент И, первый триггер с одним информационным входом и одним входом синхронизации, второй триггер с одним информационным входом и одним входом синхронизации, вход синхронизации ячейки соединен с входами синхронизации первого и второго триггеров, выход элемента ИЛИ подключен к информационному входу первого триггера, информационные выходы первого и второго триггеров подключены соответственно к первому и второму информационным выходам ячейки, отличающаяся тем, что первый информационный вход ячейки подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ подключен к второму информационному входу ячейки, первый и второй информационные входы ячейки подключены соответственно к первому и второму входам элемента И, выход которого подключен к информационному входу второго триггера.
2. Устройство для сжатия двоичных векторов на базе ячеек однородной вычислительной среды, состоящее из матрицы ячеек, количество столбцов матрицы однородной вычислительной среды равно m-1, где количество строк матрицы однородной вычислительной среды равно m-1, отличающаяся тем, что первый и второй информационные входы m/2 ячеек первого столбца матрицы однородной вычислительной среды при четном значении m, где m - число разрядов входного сигнала, соединены с соответствующими разрядами m-разрядного входного сигнала, при нечетном значении m m-разрядный входной сигнал соединен с соответствующими информационными входами (m+1)/2 первого столбца матрицы однородной вычислительной среды, а оставшиеся незадействованные входы ячеек первого столбца соединены со значением логического нуля, первый информационный выход каждой (i, j)-й ячейки подключен к второму информационном входу (i, j+1)-й ячейки, второй информационный выход каждой (i, j)-й ячейки подключен к первому информационном входу (i+1, j+1)-й ячейки, кроме ячеек первой строки, начиная со второго столбца, первый информационный вход которых соединен со значением логической единицы, первый и второй информационные выходы последних m/2 ячеек последнего столбца матрицы однородной вычислительной среды при четном значении m и первый и второй информационные выходы (m+1)/2 ячеек последнего столбца матрицы однородной вычислительной среды при нечетном значении m являются выходами схемы, с которых снимается результат, при этом ячейка однородной вычислительной среды выполнена из одного двухвходового элемента И, одного двухвходового элемента ИЛИ и двух триггеров, вход синхронизации ячейки соединен с входами синхронизации первого и второго триггеров, выход элемента ИЛИ подключен к информационному входу первого триггера, первый информационный вход ячейки подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ подключен к второму информационному входу ячейки, выход которого подключен к информационному входу первого триггера, первый и второй информационные входы ячейки подключены соответственно к первому и второму входам элемента И, выход которого подключен к информационному входу второго триггера, информационные выходы первого и второго триггеров являются первым и вторым информационными выходами ячейки.
