Систолический автомат Советский патент 1992 года по МПК G06F7/00 

ных логических модулей от одной переменной являются входами автомата.

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

Целью изобретения является повышение универсальности и производительности автомата при преобразованиях информации по заданному алгоритму для m (m 1) входных последовательностей сигналов.

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

соответственно к первой группе m информационных двухразрядных входов автомата, первая группа m информационных двухразрядных входов 0+1)-й Q 1-(р-1)) систолической структуры из первой группы р систолических структур соединены соответственно с первой группой m информационных двухразрядных выходов j-й систолической структуры из первой группы р систолических структур, первая группа m информационных двухразрядных входов первой систолической структуры из второй группы п систолических структур соединена соответственно с первой группой m информационных двухразрядных выходов последней систолической структуры из первой группы р систолических структур. Первая группа m информационных двухразрядных входов (1+1)-й (i 1-(n-1)) систолической структуры из второй группы п систолических структур соединена соответственно с первой группой m информационных двухразрядных выходов i-й систолической структуры из второй группы п систолических структур. Вторые группы m информационных выходов первой группы р систолических структур подключены соответственно к группе m р информационных выходов автомата, вторая группа m информационных входов которого подключена соответственно к первой группе m информационных входов блока коммутации, вторая группа m п информационных входов которого соединена соответственно с вторыми группами m

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

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

(«Поразрядных сдвиговых регистров.

Первая группа m информационных входов блока соединена соответственно с первыми информационными входами всех мультиплексоров, второй, третий(п+1)-й

информационные входы h-го () мультиплексора соединены соответственно с h- м, (m+h)-M,...,(m n-rrH-h)-M входами второй группы m п информаионных входов блока, управляющие входы h-го () мультиплексора соединены соответственно с выходами h-го счетчика

Группа m управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены вторым управляющим входом блока, первый управляющий вход которого соединен с синхронизирующими входами всех сдвиговых регистров, выход h-го () мультиплексора соединен с

первым информационным входом h-ro сдвигового регистра и подключен к (h w-w+1)- му выходу группы m w информационных выходов блока, первый, второй,...,(w-1)-u выходы h-го () сдвигового регистра подключейы соответственно к (h w-w+2)-My,

(h w-w+3)-My(h w)-My выходам группы

m w информационных выходов блока, причем s-я () систолическая структура содержит матрицу m m ячеек, m элементов

свертки, 4m элементов И, 2m элементов ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ соответствующего столбца матрицы, вторые входы которых соединены с выходами третьего и четвертого элементов И соответствующего столбца матрицы, первые входы которых соединены с вторым управляющим входом структуры и входом инвертора. Первый и второй разряды двухразрядного входа первой группы m информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого элементов И соответствующего столбца матрицы, второй информационный вход первой, второйm-й ячеек первого столбца матрицы соединен соответственно с s-м, (W+S)-M(m W-W+S)-M входом второй группы m информационных входов структуры. Вторые информационные входы остальных ячеек каждой строки матрицы соединены соответственно с вторыми информационными выходами ячеек, являющихся соседними ячейками в строке слева, первые информационные двухразрядные входы ячеек всех строк матрицы, кроме первой строки, соединены соответственно с первыми информационными двухразрядными выходами ячеек, являющихся соседними ячейками в столбце сверху.

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

Первая группа m управляющих входов структуры соединена соответственно с первой группой m управляющих входов элемента свертки, а вторая группа m управляющих

входов структуры - соответственно с второй группой m управляющих входов элемента свертки. Вторые управляющие входы элементов свертки соединены соответственно

с третьей группой m управляющих входов структуры.

Ячейка содержит три D-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата

0 ячейки, второй информационный вход которой соединен с D-входом первого D-триггера, прямой выход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячей5 ки, прямой выход второго D-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего D0 триггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, D5 входы второго и третьего D-триггеров соединены соответственно с первым и с вторым разрядом первого информационного двухразрядного входа ячейки, синхровхо- ды всех D-триггеров соединены с тактовым

0 входом ячейки.

Элемент свертки содержит группу m RST-триггеров, группу m элементов И с открытым коллектором, RS-триггер и резистор, с помощью которого выходы группы m

5 элементов И подключаются к источнику питания, группа m информационных входов элемента свертки соединена соответственно с S-входами группы m RST-триггеров, инверсные выходы которых соединены со0 ответственно с первыми входами группы m элементов И, выходы которых соединены также с S-входом RS-триггера, прямой выход которого соединен с информационным выходом элемента свертки. Первый управ5 ляющий вход элемента свертки соединен с Т-входами всех RST-триггеров, второй управляющий вход элемента свертки соединен с R-входом RS-триггера, первая группа m управляющих входов элемента свертки

0 соединена соответственно с R-входами группы m RST-триггеров, вторая группа m управляющих входов элемента свертки соединена соответственно с вторыми входами группы m элементов И.

5 В предлагаемом и в известном автоматах необходим этап предварительной подготовки перед началом работы автомата.

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

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

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

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

На фиг.1 представлена функциональная схема систолического автомата; на фиг.2 - функциональная схема блока коммутации (БК); на фиг.З - функциональная схема s-й () систолической структуры (СС); на фиг.4 - схема ячейки; на фиг.5 - схема элемента свертки; на фиг.6 - временная диаграмма управляющих сигналов; на фиг.7 - схема автомата Мили.

Систолический автомат содержит (фиг.1) БК 1, первую группу р СС 2, вторую группу п СС 3, первую группу m информационных двухразрядных входов 4, вторую группу m информационных входов 5, пер- вую - четвертую группы m управляющих входов 6-9, первый - четвертый управляющие входы 10-13, группу m р информационных выходов 14, первую группу m информационных входов 15 БК 1, вторую

группу m п информационных входов 16 БК 1, группу m управляющих входов 17 БК 1, первый управляющий вход 18 БК 1, второй управляющий вход 19 БК1, группу m w(rfle , если , или , если р п) информационных выходов 20 БК 1, первую группу m информационных двухразрядных входов 21 СС 2 и СС 3, вторую группу m информационных входов 22 СС 2 и 3, первую - третью группы m управляющих входов 23- 25 СС 2 и 3, первый - третий управляющие входы 26-28 СС 2 и 3, первую группу m информационных двухразрядных выходов 29 СС 2 и 3, вторую группу m информационных выходов 30 СС 2 и 3.

БК 1 предназначен для коммутации входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3.

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

Вторая группа п СС 3 предназначена для вычислений функций обратной связи автомата.

БК 1 содержит (фиг.2) группу m мультиплексоров 31, группу m счетчиков 32, группу m («Поразрядных сдвиговых регистров 33.

СС 2 и 3 имеют одинаковую структуру и содержат (фиг.З) m m ячеек 34, m элементов свертки 35, 4т элементов И 36, 2:т элементов ИЛИ 37, инвертор 38, первый информационный двухразрядный вход 39 ячейки 34, второй информационный вход 40 ячейки 34, тактовый вход 41 ячейки 34, первый информационный двухразрядный выход 42 ячейки 34, второй информационный выход 43 ячейки 34, выход результата ячейки 34, группу m информационных входов 45 элемента 35 свертки, первую группу m управляющих входов 46 элемента 35 свертки, вторую группу m управляющих входов 47 элемента 35 свертки, первый управляющий вход 48 элемента 35 свертки, второй управляющий вход 49 элемента 35 свертки, информационный выход 50 элемента 35 свертки.

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

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

Ячейка 34 (фиг.4) содержит D-триггеры 51-53, элемент 54 неравнозначности, элемент И 55.

Элемент 35 свертки (фиг.5) содержит группу m RST-триггеров 56, группу m элементов И 57 с открытым коллектором, RS- триггер 58 и резистор 59.

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

Автомат работает в режиме программирования и в режиме вычислений.

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

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

С помощью КСВ формируется функция р выходов, выражающая зависимость выхода Z автомата в момент времени t от выхода V и состояния А автомата в этот же момент времени:

Z(t)p(V(t),A(t)).

С помощью КСП формируется функция д переходов, выражающая зависимость состояния А автомата в момент времени t+1 от входа V и состояния А автомата в момент времени t:

A(t+1)5(V(t),A(t)).

Для автомата с г входами, р выходами и п элементами памяти, в качестве которых используются D-триггеры, схема КСВ является р-выходной схемой, на входах которой реализуются функции р 1 ,...,р, а схема КСП является n-выходной схемой, на выходах которой реализуются функции д 1дп .

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

D-покрытие (R-покрытие) некоторой булевой функции f - это представленная в кубической форме минимальная дизъюнктивная нормальная форма (МДНФ) прямой функции f (инверсной функции f). МДНФ прямой функции f (инверсной функции f) содержит все наборы, на которых функция f принимает значение логической 1 (логического О). D-покрытие (R-покрытие) состоит из кубов, число которых равно числу импли- кант МДНФ прямой функции f (инверсной функции f). Число компонент куба равно числу переменных МДНФ, а значениями компонент куба могут быть только три символа: 0,1.x, где ,1}. Каждый куб dj(rj) соответствует одной импликанте МДНФ прямой функции f (инверсной функции t) таким образом, что единичное (нулевое) значение компонент куба соответствует прямому (ин- версному) значению переменной в импликанте МДНФ (djЈD, rjtR).

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

Таким образом, схема КСВ описывается

группой из р покрытий DizDzp, а схема

КСП - группой из п покрытий DIADnA.

Djz-noKpbiTne состоит из т г-кубов, число которых равно числу импликант МДНФ прямой функции р :

Djz {diz,...,djDzduz}, , Jo-1-u.

DI -покрытие состоит из mi кубов, число которых равно числу импликант МДНФ прямой функции д i:

DiA {diA,...,dlDAduA}, , lD-1-u.

Число CD компонент куба всех покрытий равно CD r+n.

Пусть, например, автомат имеет три внешних входа (а,Ь,р) и два входа обратной связи (qi,q2), причем МДНФ функции имеет вид

(р (a,b,c,qi,Q2) acq2V bcqivqiq2, Тогда 0 2-покрытие, соответствующее МДНФ указанной функции, имеет вид a b с qi q2

(1 х 0 х 11 DJZ j x 1 1 0 х lx х х 1 1 J

Число mjz (miA) кубов 0 2-покрытия (D|A- покрытия) и число CD компонент кубов покрытий Djz и DIA (, ) связаны с параметром m схемы автомата следующим образом:

mjz m; miA m; CD m. Если CD m, то (m-Co) разрядов соответствующего покрытия дополняются значениями х. Если nrijz m (rrijA m), то к соответствующему О г-покрытию (оЛпокры- тию) добавляется m-mjz (m-miA) строк, являю- щихся копиями одной из строк этого покрытия (в дальнейшем, для простоты, рассматривают работу автомата только с т-раз- рядными 0 г-покрытиями (Di -покрытиями) содержащих по m кубов, при этом m г + п). Перед началом работы автомата исходные покрытия DizDpz и DIADnA преобразуются соответственно в покрытия Di,npzDp,npz и Di.npADn,npA, которые

затем в режиме программирования, записываются в СС 2 и 3.

Процесс преобразования указанных покрытий на примере одного D-покрытия вида { clu di2 ... dim

Id21 d22 ... d2m

D d(... dhm (1)

ч dm1 dm2 ... dmm

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

D-покрытие вида (1) преобразуется в Dnp-покрытие за два этапа. На первом этапе происходит транспортирование D-покрытия аналогично известной операции транспортирования матриц. На втором этапе компоненты первого столбца транспортированного D-покрытия циклически сдвигаются снизу вверх на одну позицию; компоненты второго столбца транспортированного D-покрытия циклически сдвигаются снизу вверх на две позиции, и т.д.. В итоге Dnp-покрытие принимает вид

dim d2(m-1) ... dm1 dljm-ty d2(m-2) ... dmm Dnp (h-1) ... dmj ... dm3 .dl1 d2m ... dm2

По аналогичному алгоритму происходит получение покрытий Di,npz,...,Dp,npz и

Пи А ПА

Ul.np ,-..,Un,np

Запись покрытий Di,npz,...,Dp,npz и Di,npA,...,Dn,npA в СС 2 и 3 осуществляется через первую группу m информационных двухразрядных входов 4 при наличии разрешающего сигнала (логической 1) на втором упраляющем входе 11. Запись указанных покрытий происходит в течение (п+р) m циклов, в каждом цикле записывается один куб, начиная с последнего куба Оп,прА-покрытия. Вначале на первую группу m информационных двухразрядных входов 4 поступают покрытия Di,npADn,npA, а затем покрытия Di,npzDp.npz. В режиме программирования образуется путь прохождения информации между всеми соседними парами СС 2 и 3.

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

Вычисление функций (р 1tpp и д 1д п в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих

функций, записанных ранее в режиме программирования в соответствующие СС 2 и 3.

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

В режиме вычислений на второй управляющий вход 11 поступает сигнал логического О и информационная связь между всеми соседними парами СС 2 и 3 прерыва- 0 ется.

Во время работы автомата на вторую группу m информационных входов 5 параллельно поступают m входных последовательностей сигналов: 5 ,..L.2m+iLm+iLi - последовательность

...L2m+2Lm+2l-2 - последовательность

...L3mL-2ml-m - последовательность т, в следующем порядке.

На первый вход 5i поступают компонен- 0 ты набора LI;

Li(liV...lr1), начиная с компоненты И .

На h-й вход 5ь со сдвигом во времени на (h-1) циклов относительно компоненты на- 5 бора LI поступают компоненты набора LM:

Lh (hV...lrh), начиная с компоненты И ().

После поступления на вход 5ь последней компоненты lrh набора через п циклов 0 начинают поступать компоненты набора

Lm+h:

1 . л ro+hi m+h Lm+h(ll 12

lrm+h),

начиная с компоненты Hm h.

Между поступлениями на вход 5и ком- понент набора Ц, и набора Lm+h поступают компоненты набора Оь сигналов обратной связи:

Qh (qiV-..qnh), начиная с компоненты qi . Компоненты набора Он поступают со сдвигом во времени на (h-1) циклов относительно компонент набора QL

На выходах БК 1 формируется w пакетов наборов следующим образом. Первый пакет формируется на следующих выходах БК 1:

...Qm+iLm+iQiU - на выходе 20i;

...Qrn+2Lm+2Q2l-2 - на выходе 20w+i; (2)

...Q2mL2mQmLm - на ВЫХОДв 20(m-1)w+1.

Наборы пакета (2) на входе 20hw+i поступают со сдвигом во времени на один цикл относительно наборов на соседнем входе 20(h-i)wH.

В общем случае, i-й пакет наборов фор- мируется на следующих выходах БК 1:

...Qm+iLm+iQiU - на выходе 20i; /g ...Qm+2Lm+2Q2l-2 - на выходе 20i+w;

...Q2mL2mQrnLm НЭ ВЫХОД6 20(m-1)w+i.

Наборы пакета (3) в каждой строке поступают со сдвигом во времени на (И) циклов относительно наборов в одноименной строке пакета (2). Наборы соседних сторон пакета (3) также поступают со сдвигом во времени на один цикл относительно друг друга внутри пакета.

Наборы пакета (2) поступают одновременно на входы первой СС 2 и на входы первой СС 3. Аналогично, наборы пакета (3) поступают одновременно на входы j-й СС 2 О 1-р) и на входы 1-й СС 3(1 1-п).

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

ч1 Значение функции р появляется на

первом выходе первой СС 2 на (2т-1)-м цикле после поступления на первый вход первой СС 2 первой компоненты И1 входного набора Ц.

Значение функции появляется на первом выходе j-й СС 2 через Q-1) циклов после вычисления функции р .

Значение функции j1 появляется на h- м выходе j-й СС 2 через (h+j-2) циклов после

вычисления функции (или на (2т-1)-м цикле после поступления на h-й вход j-й СС 2 первой компоненты hh+J входного набора Lh+j)G 1-p. ).

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

...L2m+hLm+hL-h

появляются через каждые m циклов на h-м выходе j-й СС 2.

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

Значение функции 6 i появляется на первом выходе первой СС 3 на (2т-1)-м цикле после поступления на первый вход первой СС 3 первой компоненты И входного набора Li, т.е. одновременно с вычислением

функции р .

Аналогично, значения функции д h появляются на h-м выходе i-й СС 3 одновременно с вычислением функции , если (i 1-n, j - 1-p, h 1-m).

БК 1 работает следующим образом.

Перед началом работы БК 1 устанавливается в исходное состояние по приходу сигнала сброса на второй управляющий вход 19. В исходном сотоянии все счетчики 32 находятся в нулевом состоянии.

Вначале управляющие сигналы в первом такте каждого цикла начинают поступать по первому входу 17i группы m управляющих входов 17.

Затем, со сдвигом на один цикл относительно соседних входов, начинают поступать управляющие сигналы на входы 172,...,17т группы т управляющих входов 17.

0 В итоге, счетчики 32 начинают считать, причем состояния соседних счетчиков в каждом цикле отличаются на единицу. Счетчики 32 имеют модуль пересчета т.

Мультиплексоры 31 коммутируют сигна5 лы так, что в течение первых г циклов на выходе h-ro мультиплексора 31 поступают сигналы с входа 15ь первой группы m информационных входов 15, а в течение последующих п циклов - поочередно от тех п входов

0 второй группы m п информационных входов 16, которые подключены к h-му мультиплексору. Далее на выход h-ro мультиплексора 31 снова поступают сигналы с входа 15н и т.д.

5 Сигналы с выхода каждого мультиплексора 31 записываются в соответствующий (м-1)-разрядный сдвиговый регистр 33, начиная с младшего разряда регистра 33. С помощью h-ro регистра 33 организуется за0 держка на 1w циклов сигнала с выхода

h-ro мультиплексора 31 на соответствующие выходы 20(h-i)w+220(h-i)w+w группы информационных выходов 20.

В первой группе р СС 2 j-я СС 2 работает

5 следующим образом 0 1-р).

В режиме программирования при наличии разрешающего сигнала (логической 1) на втором управляющем входе 27 происходит поступление кубов покрытий

0 Dj npzDp.np2 через первую группу m информационных двухразрядных входов 21

Покрытия D(j-t-i),npzDp.np2 проходят через

СС 2 на первую группу m информационных двухразрядных выходов 29, а покрытие

5 Dj,npz записывается в j-ю СС2.

В режиме вычислений в j-м СС 2 осуществляется вычисление функций путем выполнения ряда операций над записанным ранее покрытием 0,Прг.

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

При использовании кубического представления булевых функций установление принадлежности входного набора L указанному множеству наборов может быть выполнено аналитически с помощью операции пересечения кубов. По определению операции пересечения куба ...an и куба ...brt обозначается как с аПь и слу- -жит для выделения куба с С1С2...Сп, являю- щегося общей частью кубов а и Ь. Значение компоненты Ci определяется по табл.1, как Ci ai lbi (i 1-п), где знак ф означает пустое пересечение), Например, если

а х1 0x1, Ь 1 хО 1 1,

тогда куб с равен

х 1 0 х 1

О

1x011

1x011

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

(1, если Lildj. ф для любого е; f(L)|

0, если Lftdg ф для всех е , где L(lil2...ln),

de(dЈidg2...dtm).e l-m,d 6

Аналогичные соотношения справедливы и для комбинационной схемы КСП (фиг.7), на входы которого поступают входные наборы сигналов и наборы сигналов обратной связи.

и

Значение функции на h-м выходе j-й СС 2 может быть определено следующим образом:

1.0 если U Qhfldz. ф для любого Е

И(иа„)- сИ

0. если Lh Qh Л с(| ф для всех Е

где U (lihl2h,..lrh);

Qh (qihq2h...qnhJ;

dz (dj, d...dU;

-m, dz Ј Djz

Если, например, U (111) и Qh (00), тогда рассматривавшаяся функция (a,b,c,qi,q2) принимает единичное значение, так как имеется непустое пересечение с одним кубом покрытия DJZ этой функции:

л х 1 1 0 х

° 11100

11100

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

распараллеливается с помощью матрицы т т ячеек 34.

На вторую группу m информационных входов 22 j-й СС 2 поступает параллельно j-й пакет наборов:

...Qm+iLm+lQiLi - на вход 22s;

...Qm+2LnrH-2Q2l 2 - НЭ ВХОД 22w+s; (5) ...Q2m L2mQmLm - на вход 22(m-1)w+s.

Наборы соседних строк пакета (5) поступают со сдвигом во времени на один цикл относительно друг друга внутри пакета.

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

0,1).

На первом такте j-ro цикла работы на вход 40 указанной ячейки 34 поступает компонента И входного набора LI, а также происходит циклический сдвиг сверху вниз по столбцам содержимого матрицы ячеек 34. Вследствие этого сдвига на вход 39 ячейки 34 с координатами (1,1) поступает компонента dnz покрытия Dj,npz и на выходе 44 указанной ячейки 34 получается результат выполнения операции:

.

На первом такте j-ro цикла работы первый элемент 35 свертки устанавливается в исходное состояние, а на втором такте по входу 45i группы m информаицонных входов полученный результат из ячейки 34 с координатами (1,1) записывается в первый элемент 35 свертки.

На первом такте (j+1)-ro цикла работы компонента И1 набора LI поступает на вход 40 ячейки 34 с координатами (1,2), а на входы 40 ячеек 34 с координатами (1,1) и (2.1) поступают компоненты соответственно la и

ii2(i21ei i,ii2eL2).

После циклического сдвига в матрице ячеек 34 на входы 39 ячеек 34 с координатами (1,1), (1,2) и (2,1) поступают соответствующие компоненты покрытия Dj,npz. В итоге, на первом такте (j+1)-ro цикла выполняют следующие операции:

- в ячейке 34 с координатами 0-1):

И V)I21Z - в ячейке 34 с координатами (1,2);

И fldn - в ячейке 34 с координатами

(2,1).

На втором такте (j+1)-ro цикла результаты выполнения указанных операций в ячейках 34 с координатами (1,1) и (1,2) записываются в первый элемент 35 свертки, а результат выполнения операции в ячейке 34 с координатами (2,1) записывается во второй элемент 35 свертки.

После этого фронт выполняемых операций перемещается к ячейкам 34 с координатами (3,1), (2,2), (1,3) и, таким образом, порождается волна вычислений, бегущая вниз по матрице ячеек 34.

В течение первых m циклов, начиная с j-ro цикла, в ячейке 34 с координатами (1,1) поочередно получают результаты выполнения следующих операций:

hhdnz,...,lr1odirz, qrndi(r+i)zqnhdimz.

Тем самым на первом такте (j+m-1)-ro цикла заканчивается выполнение операции пересечения наборов LiQi с компонентами куба diz покрытия Dj,npz. Общий результат выполнения операции пересечения наборов UGH с кубом diz формируется в первом элементе 35 свертки на втором такте Q+m-1)- го цикла.

На первом такте (j+m)-ro цикла в ячейке 34 с координатами (1,2) заканчивается выполнение операции пересечения наборов LiQi с кубом d2z покрытия Dj,npz

На первом такте Q+2m-2)-ro цикла в ячейке 34 с координатами (1,т) заканчивается выполнение операции пересечения наборов LiQi с кубом dmz покрытия Dj,npz. Общий результат выполнения операции пересечения наборов UGH с кубом dmz формируется в первом элементе 35 свертки на втором такте (j+2m-2)-ro цикла.

На третьем такте (j+2m-2)-ro цикла на первом выходе ЗСМ второй группы m информационных выходов 30 получают окончательный результат выполнения операции пересечения наборов UGh с покрытием Dj,npz, сформированным в соответствии с соотношением (4). На выходе 30i в указанный момент времени значение логической 1 (логического О) соответствует значению функции р , покрытия Dj,npz который записано в j-1 СС 2, на входном наборе U и наборе Он сигналов обратной связи автомата.

При дальнейшей работе автомата на третьем такте

j+2m-1j+3m-3

циклов на выходах 30230т второй группы

m информационных выходов 30 поочередно получают результаты выполнения операции с покрытием Dj,npz наборов UQ.2LmQm.

Во второй группе п СС 3 i-я СС 3 работает следующим образом (i t-n).

В режиме программирования в i-ю СС 3 записывается покрытие Dj,npA аналогично записи покрытия Dj,npz в j-ю СС 2, В режиме вычислений в i-й СС 3 осуществляется вычисление функций д - д К™ аналогично вычислению функций у рг1 вHI СС 2.

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

На первом такте каждого цикла по входу 39 в D-триггеры 52 и 53 записывается очередная компонента d|. (dAt ) покрытия Dj,npz (Dj,npA), а в D-триггер 51 - очередная компонента lkh набора и или компонента qih набора Qh (K 1-r; i 1-n; h 1-m).

Поскольку значениями компонент куба могут быть символы из алфавита {0,1,х}, поэтому для представления компоненты d в

двоичном алфавите необходимо два разряда d|i dfk

х

Поэтому, на первом такте каждого цикла в D-триггер 52 и в D-триггер 53 записываzl

jz2

ются значения соответственно d и

После окончания записи соответствующей информации в D-триггеры 51-53 выпол- няется операция пересечения компоненты dЈt с компонентой Ik или qi .

Поскольку значениями компонент lkh и

qsh могут быть только символы О и 1,

поэтому в ячейке 34 указанная операция

пересечения выполняется согласно табл.2.

В ячейке 34 реализуется следующая

функция О:

9-(ndaendfelu(e ;nJ|;ndi|)

30

(Ehk©JgE)nd

гг ее )

для компонент lkh и d|

(пЗ«П«}Й).

(©di;ind

ZZ

ее;

для компонент qih и d|t

Функция 0, которая реализуется с помощью элемента 54 неравнозначности и элемент И 55, принимает значение логической 1 (логического О) при наличии пус- того (непустого) пересечения компоненты dz с компонентой lkh или qi h.

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

Аналогично реазлизуется функция Эй для покрытия Dj,npA.

Первый элемент 35 свертки в первой СС 2 работает следующим образом.

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

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

RST-триггер 56.

Через каждые m циклов RST-триггеры 56 снова устанавливаются в нулевое состояние в указанной последовательности.

В rj - и RST-триггер 56 первого элемента 35 свертки в конце первого такта каждого цикла по входу 45 ц группы m информационных входов 45 поступает результат опера- ции пересечения компоненты d2 с компонентой lkh или qih от ячейки 34 с координатами (1,J/) (Jj 1-m). Этот результат поступает на S-вход г - го RST-триггера 56, и при наличии пустого пересечения компоненты с компонентой lkh или qih 77- и RST- триггер 56 устанавливается в единичное состояние. S-вход RST-триггера 56 является синхронным и запись в RST-триггер 56 осуществляется во втором такте каждого цикла по приходу тактового сигнала на вход 48.

На втором такте m-ro цикла в первом RST-триггере 56 формируется результат операции пересечения наборов LiQi с кубом diz покрытия Di,npz. При пустом (непустом) пересечении наборов LiQi с кубом di2 первый RST-триггер 56 находится в единичном (нулевом) состоянии.

На втором такте (2т-1)-го цикла в т-м RST-триггере 56 формируется результат операции пересечения наборов LiQi с кубом dmz покрытия Di,npz аналогичным образом.

Окончательный вывод о результате операции пересечения наборов UGH со всем покрытием Di,npz согласно соотношению (4) можно сделать после анализа результатов операции пересечения наборов LiQi с отдельными кубами покрытия Di,npz.

Поэтому до получения результата операции пересечения наборов LiQi с кубом dmz сохраняются результаты операции пересечения наборов UQi с предыдущими кубами покрытия Di,npz. С этой целью на третьем такте m-ro, (m+1)-ro,...,(2m-1)-ro циклов по сигналам, поступающим по второй группе m управляющих входов 47, происходит передача инверсного содержимого со- ответственно первого RST-триггера 56, второго RST-триггера 56,...,т-го RST-тригге- ра 56 через элементы И 57 в RS-триггер 58. При наличии в указанные моменты времени хотя бы одного RST-триггера 56 в нулевом состоянии RS-триггер 58 по S-входу устанавливается в единичное состояние.

Следовательно, на третьем такте (2т-1)- го цикла в RS-триггере 58 формируется значение функции р( LiQi) согласно соотношению (4): единичное (нулевое) состояние RS-триггера 58 свидетельствует о

том, что на наборах LiQi функция р (UQi) принимает единичное (нулевое) значение.

5

0

0

5

В RS-триггер 58 первого элемента 35 свертки с интервалом в m циклов формируются значения функций:

У ГО-lQl), p4WlQm+l), рСГС-2т+10.2т+1),..

Во втором такте m-ro 2m-ro, 3m-ro,... циклов RS-триггер 58 сбрасывается в нулевое состояние по сигналу, который поступает по входу 49.

Элементы И 57 являются элементами с открытым коллектором, что позволяет вместе с резистором 59 реализовать на их выходах схему Монтажное ИЛИ.

Остальные элементы 35 свертки в автомате работают аналогично.

На фиг.6 показана последовательность появления управляющих сигналов на входах 46-49 элемента свертки.

Для определения технико-экономической эффективности предлагаемого автомата по сравнению с известным оценивают производительность обеих автоматов на q состояний для N входных последовательностей сигналов, состоящих из г-компонент- ных входных наборов.

5 в известном автомате входные последовательности сигналов могут поступать лишь друг за другом, поэтому соответствующие им выходные последовательности сигналов формируются за время Ti:

Ti N т -ti,

где ti -длительность цикла работы автомата.

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

Т2 (2т - 1 + N - 1) t2 N 12 + 2(r +

+IOQ2 q - 1) t2,

где t2 - длительность цикла работы автомата.

Рост по производительности предлагаемого автомата по сравнению с известным составляет

Ti N-r

Т2

0

5

+ 2 ( г + log 2 q -1 ) при .

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

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

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

блока коммутации.

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

мультиплексоров, второй, третий(п+1)-й

информационные входы h-го () мультиплексора соединены соответственно с h- м, (m+h)-M,...,(m п-п+п)-м входами второй группы m п информационных входов блока, управляющие входы h-ro мультиплексора соединены соответственно с выходами h-ro

счетчика, группа m управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены с вторым управляющим входом блока, первый управляющий вход

которого соединен с синхронизирующими . входами всех сдвиговых регистров, выход h-ro мультиплексора соединен с первым информационным входом h-ro сдвигового регистра и подключен к (h w-w+1)-My выходу

группы m w информационных выходов блока, первый, второй,...,(w-1)-1 выходы h-ro сдвигового регистра подключены соответственно к (h w-w+2)-My, (h w-w+3)-My(h

wj-му выходам группы m. w информационных выходов блока.

3.Автомат по п. 1,отличающийся тем, что s-я (s 1-w) систолическая структура содержит матрицу nvm ячеек, m элементов свертки, 4т элементов И, 2т элементов

ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ

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

входом структуры и входом инвертора, первый и второй разряды двухразрядного входа первой группы m информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого элементов И соответствующего столбца матрицы, второй информационный вход первой, второй,...,т-й ячеек первого столбца матрицы соединен соответственно с s-м, (s + w)м(m W-W+S)-M входом второй группы m

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

4.Автомат по п.З, отличающийся тем, что ячейка содержит три D-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата ячейки, второй информационный вход которой соединен с D-входом первого D- триггера, прямой вход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячейки, прямой выход второго D-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего D- триггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, D- входы второго и третьего D-триггеров соединены соответственно с первым и вторым разрядами первого информационного двухразрядного входа ячейки, синхровходы всех D-триггеров соединены с тактовым входом ячейки.

5.Автомат по п.З, отличающийся тем, что элемент свертки содержит группу m RST-триггеров, группу m элементов И с открытым коллектором, RS-триггер и резистор, через который выходы группы m элементов И подключаются к источнику питания, причем группа m информационных входов элемента свертки соединена соответственно с S-входами группы m RST-триггеров, инверсные выходы которых соединены соответственно с первыми входами группы m элементов И, выходы которых соединены также с S-входом RS-триггера, прямой выход которого соединен с информационным выходом элемента свертки, первый управляющий вход элемента свертки соединен с Т-входами всех RST- триггеров, второй управляющий вход элемента свертки соединен с R-входом RS- триггера, первая группа управляющих входов элемента свертки соединена соответственно с R-входами группы m RST- триггеров, вторая группа m управляющих входов элемента свертки соединена соответственно с вторыми входами группы m элементов И.

Таблица 1

Изобретение относится к вычислительной технике и предназначено для параллельной обработки информации при ее преобразовании в результате выполнения заданного алгоритма Целью изобретения является повышение универсальности и произ- водительностиавтоматапри преобразованиях информации по заданному алгоритму для m (m 1) входных последовательностей сигналов, Имеются два режима Изобретение относится к вычислительной технике и предназначено для параллельной обработки информации при ее преобразовании в результате выполнения заданного алгоритм., Известен последовательностный автомат, содержащий итеративные матрицы для реализации функции обратной связи и выходной функцции. Недостатком этого автомата является зависимость структуры автомата от реализуемых функций, большая сложность и низкая производительность. работы систолического автомата. В режиме программирования в ячейки первой группы р систолических структур (СС) 2 и второй группы п систолических структур (СС) 3 записываются m-разрядные кубические покрытия функций выхода и функций перехода автомата, которые поступают по первой группе m информационных двухразрядных входов 4. В режиме вычислений происходит параллельное формирование на группе т-р информационных выходов 14 выходных последовательностей сигналов, определяемых внутренним состоянием автомата и m входными последовательностями сигналов, поступающих на вторую группу m информационных входов 5. Коммутация входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3 осуществляется с помощью блока 1 коммутации. Вычисление функций выходов и функций переходов в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций. 4 з.п,ф-лы, 7 ил., 2 табл. Наиболее близким по технической сущности к предлагаемому является управляющий автомат на q состояний, содержащий q универсальных логических модулей, блок из 1од2 q коммутаторов, дешифратор и регистр, выходы которого связаны с входами дешифратора, выходы которого являются выходами автомата, информационные входы блока коммутаторов соединены с выходами универсальных логических модулей, а управляющие входы соединены с выходами регистра, входы которого соединены с выходами блока коммутаторов, причем входы универсальС/1 с S со ю со Јь о

Таблица 2

С-А

Ifт

19

%

18

f/- t41 I

tf

l6 47 W

АЛ ААААААА jrWinjiJTrL

ППППП

mni

I2$ t$bl$3I™ 3пг+ 13m+1

-П

IT

IT