Систолическая структура для вычисления логических функций Советский патент 1991 года по МПК G06F7/00 

о сд

4ь

00

о

СО

рицы ячеек 1, а число кубов - числа га столбцов матрицы ячеек 1. В течение всего времени работы структуры на первую группу информационных входов 4,-4п структуры параллельно поступают наборы аргументов логической функции. Процесс вычисления логической функции- с числом аргументов не более п заключается в выполнении операций пересечения входных наборов аргументов с кубами покрытий логичес-f кой функции в ячейках 1 и формировании результата вычислений в элементах 2 свертки. Начиная c(n+m-1)- го цикла работы предлагаемой структуры, на выходах группы инфррмационных k-разрядных ( I, где

Д означает округление до ближайшего целого в большую сторону) выходов структуры на каждом цикле работы вы- числяется значение логической функции от очередного входного набора аргументов. 1 з.п. ф-лы, 5 ил., 3 табл.

Изобретение относится к вычислиJL/ 5AJ тельной технике и предназначено для параллельной обработки информации при вычислении логических функций. Целью изобретения является повышение быстродействия систолической структуры при вычислении логических функций на последовательностях входных наборов аргументов. В предлагаемой структуре перед началом работы в ячейки 1 через вторую группу информационных, двухразрядных входов Sj-Sfp записывается кубическое покрытие логической функции в преобразованном виде, причем его разрядность не должна превышать числа п строк матЦ .2 i

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

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

На фиг . 1 представлена функциональная схема систолической структуры; на фиг.2 - схема ячейки; на фиг.З - схема элемента свертки; на фиг.4 - схема потоков данных для систолической структуры в исходном состоянии; на фиг„5 - временная диаграмма сигналов на управляющих входах структуры.

Систолическая структура содержит (фиг.1) матрицу iWm ячеек 1, п эле ментов 2 свертки, 2т элементов ИЛИ 3 первую группу 4п информационных входов, вторую группу 5т информационных двухразрядных входов9 группу бп информационна k-разрядных выходов, первый 7 и второй 8 управляющие входы, первую 9ms вторую Ют и третью 11k группы управляющих входов струк туры, первый информационный вход 12 ячейки 1, второй информационный двухразрядный вход 13 ячейки 1, второй информационный выход 14 ячейки 1 первый информационный двухразрядный выход 15 ячейки t выход 16 результата ячейки 1, тактовьй вход 17 ячейки 1, группу 18т информационных входов элемента 2 свертки, информационный k-разрядный 19 элемента 2 свертки, тактовый вход 20 элемента 2 свертки, первую группу 21 го-тактовых входов элемента 2 свертки, вторую группу 22 m-тактовых входов элемента 2 свертки, третью группу 23 k-тактовых входов элемента 2 свертки

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

Элемент 2 свертки (ЭС) предназначен для формирования результата вычисления логической функции на соответствующих входных наборах ее аргументов о

Ячейка 1 (фиг.З) содержит D-триг- геры 24-26, элемент 27 неравнозначности и элемент И 28.

ЭС 2 (фиг.З) содержит группу m RST-триггеров 29, группу m элементов И 30 с открытым коллектором, k-разрядный регистр 31 и резистор 32.

Структура работает следующим образом.

Вычисление логической функции в структуре происходит в результате выполнения ряда операций над минимальным кубическим покрытием (D- или R-покрытием) этой функции.

D-покрытие (R-покрытие) функции Ср - это представленная в кубической форме минимальная дизъюнктивная нормальная форма (МДНФ) прямой функции ($ (инверсной функции Й )

МДНФ прямой функции (р (инверсной функции ср ) содержит все наборы, на которых функция принимает значение логической 1 (логического О).

D-покрытие (R-покрытие) состоит из ) кубов, число которых равно числу импликант МДНФ прямой функции Ср (инверсной функции ср )

D

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

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

пЈ п.;

m i m,

или

n n

R

m ь тл

Если n n.(n пк) , тогда п - n(n - HO) разрядов соответствующего

преобразуется в Dnp-покрытие за два этапа. На первом этапе происходит

транспонирование D-покрытия аналогично известной операции транспонирования матриц. На втором этапе компоненты первого столбца транспонированного D-покрытия циклически сдвигаются

снизу вверх на одну позицию, компоненты второго столбца транспонированного D-покрытия циклически сдвигаются снизу вверх на две позиции и т.д. В итоге покрытие имеет вид

45

50

k

4m- in - n + 2 , m + 2 ,

если n с m - 2 если n m - 2

Аналогично происходит преобразование исходного R-покрытия.

Запись Dm,-покрытия в матрицу ячеек 1 осуществляется через вторую группу 5т информационных двухразряд1654809ных входов построчно, начиная с последней строки Dnp-покрытия. Через п циклов запись Dflp-покрытия завершает ся и получено начальное положение структуры в котором i-я строка мат- рицы ячеек 1 содержит i-ю строку D p-покрытия i 1 :п (фиг.4)-.

Традиционный метод синтеза комбинационной схемы (КС) на основе заданных МДНФ или покрытий функции (J заключается з выборе совокупности логических элементов из заданной системы логических элементов, которые соединяются таким образом, чтобы КС реали- з овал а функцию С{.

Пусть на некотором вкодном наборе L аргументов функции на выкоде КС появляется значение логической 1. Тогда реализуемую КС функцию q мож- но интерпретировать как установление принадлежности входного набора L множеству наборов, на которых функция ср принимает значение логической 1.

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

быть выполнено аналитически .с помощью 0 процесс вычисления значений логиоперации пересечения кубов. По определению операции пересечения куба а а,аЈ, ,..,апн куба b bjb, ...ЬЙ

обозначаются как с выделения куба с

anb и служат для

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

Входные наборы L, ,LЈ, ... ,Ц,.,

С1са.

h

яв- -.,-,,... -- - - -- | 5 -II ъ f

ляющегося общей частью кубов а и b. J5

Значение компоненты с| ощ еделя ется по табл.1, как с« tt а;пЬ (1 1 f п), Знак ф означает пустое

поступают на первую групп

ресечение. Например, если а 1 х 10 b х 0 х 0 тогда куб с равен

40

4 п информационных входов структур следующим образом (фиг .4).

На вход 4j первой группы 4 п ин формационных входов структуры пост пают компоненты набора

м .

О

п

1 х 1 О

х е xj) о

Входной набор L принадлежит множеству наборов, на которых функция ер принимает значение логической 1 (логического О), если имеет место непустое пересечение набора L хотя бы с одним кубом В,, -покрытия (R - покрытия):

{о;

если Lndjp ф для любого j ; 55 если bnrjR для любого j

(1)

где 1 (1, ,...,1; ,...ДП);

9d)0(d

JD

8 d i

-V

Y

.iR

m.

|j 5 dn}l)

P

vr,jr , ...,r{jg, .. .,rnjR - 1 - mn, ryn

);

1 7

«(r

JR

Соотношение (1) справедливо такж и для исходных покрытий (D и R).

Например, набор L 1101 принадлежит множеству наборов, на которых функция Ср (а,Ь,с,е) принимает едининое значение, так как имеется непустое пересечение с одним кубом D-пок рытия:

1101 п

XXXI

1101

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

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

Входные наборы L, ,LЈ, ... ,Ц,.,.

еи

поступают на первую группу

4 п информационных входов структуры следующим образом (фиг .4).

На вход 4j первой группы 4 п информационных входов структуры посту-, пают компоненты набора

L1

м .

9

О

начиная с младшего разряда.

На вход 4g первой группы 4 п ин- формационных входов структуры со сдвигом на один цикл so времени поступают компоненты набора

1& - lflj,...,

начиная с младшего разряда.

На вход 4 первой -группы 4 п информационных входов структуры со сдвигом во времени на (п - 1) циклов поступают компоненты набора

ClV

i 2

ф,

начиная с младшего разряда,

На фиг.4 величина сдвига в циклах обозначена Јi

После поступления на вход первой группы 4 п информационных входов структуры последней компоненты 1 набора L ;

L-, - u; i;,...,i;.

на следующем цикле на указанный вход

цЧп

бора L

поступает первая компонента

4

+-п

на

и Г iltn

и

п

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

Процесс вычисления в матрице ячеек 1 начинается с активизации первой ячейки t первой строки, т.е. ячейки 1 с координатами (1.1).

На первом такте первого цикла работы на вход 12 ячейки 1 поступает компонента l набора L,, а также происходит циклический сдвиг сверху вниз по столбцам содержимого матрицы ячеек. Вследствие этого сдвига на вход 13 ячейки 1 с координатами (1.1 поступает компонента d Вдр-покры- тия и на выходе 16 ячейки 1 получает ся результат выполнения-операции

ltnd«.

(2)

На первом такте (п-Н)-г ячейке 1 с координатами (1 чено выполнение операции п всех компонент набора L с

На первом такте первого цикла рабо-jg тами куба d Dnp-покрытия.

ты первый ЭС 2 устанавливается :в исходное, состояние, а на втором такте по первому входу 18 группы 18 m информационных входов результат (2) записывается в первый ЭС 2.45

На первом такте второго цикла работы компонента lt набора L, поступает на вход 12 ячейки 1 с координатами (1.2), а на входы 12 ячеек 1 с координатами (1.1) и (2.1) поступают компо- 50 ненты соответственно т2 1 6LЈ) .

- После циклического сдвига в матрице ячеек 1 на входы 13 ячейки 1 с координатами (1.1), (1.2) и (2.1) поступают соответствующие компоненты Dflp-покрытия. В итоге на первом такте второго цикла выполняются следующие операции:

if die ц,

55

На первом такте (п+т-1) в ячейке 1 с координатами кончено выполнение операци чения всех компонент набор бом dmDn.-покрытия. Общи выполнения операции пересе ра L t с кубом dm формируе вом ЭС 2 на втором такте ( цикла.

На третьем такте (п+та-1 на первом выходе Ъ, групп формационных k-разрядных в структуры получен окончате результат выполнения опера сечения набора L{ с Dnp-п сформированный в соответст соотношением (1).

На выходе bl в указанн времени значение логическо

54809

l|nd2,

10

в ячейке 1 с координатами ( 1 .1)j в ячейке 1 с координатами (1.2)

в ячейке 1 с координатами (2.1)

(3)

10

15

20

На втором такте второго цикла результат выполнения операций (3) в ячейке 1 с координатами (1.1) и (1.2) записываются в первый ЭС 2, а результат выполнения операции (3) в ячейке 1 с координатами (2.1) записывается во второй ЭС 2.

После этого фронт выпЪлняемых операций перемещается к ячейке 1 с координатами (3.1), (2.2) и (1.3), и, таким образом, продолжается волна вычислений, бегущая вниз по матрице ячеек 1. В течение первых п циклов в ячейке 1 с координатами (1.1) поочередно получены результаты выполнения следующих операций:

l ndM

Vd 4;

-I , Ijnd,,,

Vd««(4)

Тем самым на первом такте п-го цикла закончено выполнение операции пересечения всех компонент набора Ц с компонентами куба d Dn«-покрытия. Общий результат выполнения операции пересечения набора L( с кубом d, формируется в первом ЭС 2 на втором такте n-го цикла.

На первом такте (п-Н)-го цикла в ячейке 1 с координатами () закон- чено выполнение операции пересечения всех компонент набора L с компонентами куба d Dnp-покрытия.

тами куба d Dnp-покрытия.

На первом такте (п+т-1)-го цикла в ячейке 1 с координатами (1,т)-закончено выполнение операции пересечения всех компонент набора Lf с кубом dmDn.-покрытия. Общий результат выполнения операции пересечения набора L t с кубом dm формируется в первом ЭС 2 на втором такте (п+т-1)-го цикла.

На третьем такте (п+та-1)-го цикла на первом выходе Ъ, группы 6 п информационных k-разрядных выходов структуры получен окончательный результат выполнения операции пересечения набора L{ с Dnp-покрытием, сформированный в соответствии с соотношением (1).

На выходе bl в указанный момент времени значение логической 1 (логического О) соответствует значению логической функции (О , Dn. -покрытие которой записано в матрицу ячеек 1, на входном наборе Ц.

При дальнейшей работе структуры на третьем такте (n+m), (n+m+1),..., (2n+m-2)-ro циклов на выходах bl, Ц, ...,Ь группы 6 п информационных k-разрядных выходов структуры поочередно получены результаты операции пересечения с Впк покрытием входных наборов соответственно Lg,,... ,Lf,,

Значения логической функции ср на последующих вхёдных наборах аргументов появляются на каждом цикле поо- чередно на выходах группы 6 п информационных k-разрядных выходов структуры в последовательности показанной на фиг.4 .

Значение k определяется па формуле

где Г означает округление до ближай- шего целого в большую сторону.

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

На первом такте каждого цикла по входу 13 в D-триггеры 25 и 26 записывается очередная компонента d, :6(r %ft ) О™-покрытия (RОр-покрытия), а в D-триггер 24 - очередная компонента Г1-,набора L.

Поскольку значениями комлонент кубов djj.jjCr ;j jj) могут быть символы из алфавита 0,1, х, для представления компоненты ,. (г,) в двоичном алфавите необходимо два разряда (табл.2

Поэтому на первом такте каждого цикла в D-триггер 25 и в D-триггер 26 записываются значения соответственHod ;b(r;3R)Hd(r ;k).

После окончания записи соответствующей информации в D-триггеры 24-26 выполняется операция пересечения ком- поненты d;jB(r;}.. ) с компонентой 1;( Поскольку значениями компоненты lj могут быть только символы 0 и 1, в ячейке 1 указанная операция пересечения выполняется согласно табл.3

В ячейке 1 реализована следующая функция Z:

Z - (lind nd djndj nd)- (.0)т1. .рдля Dnp-покрытия;

Z a;nr;JRnrrJR)U(.R) (1;®г; |й )пг.-лдляЕПр-покрытия.

Функция Z, которая реализуется с помощью элемента 27 неравнозначности и элемента И 28, принимает значение логической 1 (логического О) при наличии пустого (непустого) пересечения компоненты 1; с компонентами ,i ,п f i

dndb j jVВ конце первого такта каждого цикла значение функции реализуется на выходе 16 ячейки 1.

ЭС 2 работает следующим образом.

На первом такте первого цикла по сигналу, поступающему по входу 21 первой группы 21 m тактовых входов, первый RST-триггер 29 устанавливается в нулевое состояние.

На первом такте каждого последующего цикла поочередно устанавливаются в нулевое состояние второй RST- триггер 29, третий RST-триггер 29, ..., га-й RST-триггер 29.

Через каждые п циклов RST-Tpnrr e- ры 29 снова установлены в нулевое состояние в указанной последовательности о

В Q -и RST-триггер 29 -го ЭС 2 в конце первого такта каждого цикла по группе 18 m информационных входов поступает результат операции пересечения компоненты lj с компонентой d (rjjR) от ячейки 1 с координатами Ј, Q находящейся в Ј -и строке ив б -м столбце матрицы ячеек 1 ( 9 1-п 9 Ггт).

Указанный результат поступает на S-вход RST-триггера 29, и при наличии пустого пересечения компоненты 1 с компонентой d ij .p(r ;j R) соответствующий RST-триггер 29 устанавливается в единичное состояние S-вход RST- триггера 29 является синхронным, и запись в RST-триггер 29 осуществляется во втором такте каждого цикла по приходу тактового сигнала на вход 20.

На втором такте n-го цикла в первом RST-триггере 29 первого ЭС 2 формируется результат операции пересечения всех компонент набора L( с компонентами куба d( 0Пр-покрытия. При пустом (непустом) пересечении набора L, с кубом d первый-RST-триггер 29 первого ЭС 2 находится в единичном (нулевом) состоянии.

На втором такте (п+1)-го цикла во втором RST-триггере 29 первого ЭС 2 формируется результат операции пересечения набора L, с кубом d 0Пр-покрытия аналогичным образом.

На втором такте (n+tn-1)-ro цикла в т-м RST-триггере 29 первого ЭС 2 формируется результат операции пересечения набора LJ с кубом БПр-покры- тия.

Окончательный вывод о результатах операции пересечения набора L ( с Dnp-покрытием согласно соотношения (1; можно сделать после анализа ре- 10 зультатов операций пересечения набора Ц со всеми кубами Dnp-покрытия.

Поэтому до получения результата операции пересечения набора L кубом d ,„.Ј необходимо сохранять резуль- таты операций пересечения набора LJ с предыдущими кубами В„р-покрытия. С этой целью на третьем такте п, (п+1),...,(п+т-1)-го циклов по сигналам, поступающим на второй группе jn 22 ja тактовых входов, происходит передача инверсного содержимого соответственно первого RST-триггера 29, второго RST-триггера 29,...,т-го RST-триггера 29 через элементы И 30 25 в первый триггер регистра 310 При наличии в указанные моменты времени хотя бы одного RST-триггера 29 в нулевом состоянии первый триггер регистра 31 по S-входу устанавливается 30 в единичное состояние.

Следовательно, на третьем такте (n-Hn-l)-ro цикла в первом триггере регистра 31 формируется значение логической функции (о(L () согласно соотношения (1): единичное (нулевое) состояние первого триггера регистра 31 свидетельствует о том, что на входном наборе L( функция Ср принимает единичное (нулевое) значение. Начиная с (п-И)-го и по 2 п-й

цикл в первом RST-триггере 29 форми-- руется результат операции пересечения набора L(c кубом d, Dnp-покрытия. На третьем такте 2п-го цикла этот результат из первого RST-триггера 29 передается через первый элемент И 30 в регистр 31.

Если

2n n + m - 1(5)

40

45

50

тогда на третьем такте 2п-го цикла инверсное содержимое первого RST-триггера 29 записано во второй триггер регистра 31.

На третьем такте (2п + 1),..., (2n + m - 1)-го циклов во второй триггер регистра 31 записано инверсное содержимое соответственно второго ... га-го RST-триггеров 29.

0

n 5 0

0

5

0

5

Если неравенство (5) не выполняется, тогда, начиная с 2п-го цикла, информация от RST-триггеров 29 снова записывается в первый триггер регистра 31, поскольку в этом случае регистр 31 состоит из одного триггера. В общем случае регистр 31 содержит k(k - Г) триггеров. J П1

Таким образом, в регистре 31 первого ЭС 2 с интервалом в п циклов формируются значения функции

cjcv; срал+|), tfaaiK1....

Элементы И 30 являются элементами с открытым коллектором, что позволяет вместе с резистором 32 реализовать на их выходах схему МОНТАЖНОЕ ИЛИ.

Работа ячеек 1 и ЭС 2 осуществляется под воздействием управляющих сигналов. На фиг.5 показана последовательность появления управляющих сигналов на управляющих входах 8-11 после начала работы структуры до 3 х (т + п - 1)-го такта работы структуры для случая k 2.

Формула изобретения

;1 . Систолическая структура для вычисления логических функций, содержащая матрицу ячеек из п строк и m столбцов, причем п информационных входов первой группы структуры х соединены с первыми информационными входами первых из m последовательно соединенных ячеек каждой строки матрицы, первые информационные выходы ячеек первой строки которой подключены к вторым информационным входам первых из п-1 последовательно соединенных ячеек каждого столбца матрицы, отличающаяся тем, что, с целью повышения быстродействия при (вычислении логических функций из пос- ледовательностей входных наборов ар- |гументов, в нее введены п элементов свертки, 2га элементов ИЛИ, причем первые информационные выходы и вторые информационные входы всех ячеек являются двухразрядными, входы первого и второго разрядов каждого из m информационных входов второй группы структуры соединены с первыми входами соответственно первого и второго эле- ментов ИЛИ соответствуюшего столбца,

вторые входы первого и второго элементов ИЛИ которого соединены с выходами одноименных разрядов первого информационного выхода n-й ячейки этого же-столбца, выходы первого и второго элементов ИЛИ каждого столбца матрицы соединены соответственно с входами первого и второго разрядов второго информационного входа первой ячейки этого же столбца, выходы результата ячеек i-й (ie1-n) строки матрицы соединены с m информационными входами группы 1-го элемента свертки (1е )) k-рззрядные выходы которых являются k-разрядными

s

выходами структуры, первый

и второй управляющие входи, которой соединены соответственно с тактовы- ми входами ячеек матрицы и элементов свертки, га управляющих входов первой и второй групп структуры подключены к соответствующим m тактовым входам одноименных групп элементов свертки, k управляющих входов третьей группы структуры подключены к тактовым вхо-1 дам третьей группы элементов свертки. 2, Структура по п.1, отличающая с я тем, что каждая ячейка матрицы содержит три D-триггера, элемент неравнозначности и элемент И, выход которого является выходом ячейки, первый информационный вход котог/ рой соединен с -D-входом первого

Исходное обозначение компонент.

D-триггера, прямой выход которого со единен с Первым входом элемента неравнозначности и вторым информационным выходом ячейки, прямой выход второго D-триггера соединен с вторым входом элемента неравнозначности и с входом первого разряда первого информационного выхода ячейки, прямой выход -третьего D-триггера соединен с первым входом элемента И и входом второго разряда первого информационного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, D-входы второго и третьего D-триггеров соединены с входами соответственно первого и второго разрядов второго информационного входа ячейки, синхрОБХОДЫ всех D-триггеров соединены с тактовым входом ячейки.

Таблица 1

Таблица2

01 11 10 01 11 10

ТаблицаЗ

О О О 1 1 1

О 0 О 0 1 1

Фиь2

I

I I I

hsEMsC

P k

fc f.

ni

f

T Ln

j;- со о vo

л

v уж v

-Si, Si.

3fa+fl-f)f

3fflt+ff-f)

3(/n+/t-f)-1

входы

QCM CSfMAJ

СмСЧ|С |Сч СмСм S-5

s

СЧ|

5ЛЛЗ

Ш

Е

CViCvi