Систолический автомат

)5 6 06 Р 7/00 СУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТ И ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕН ИДЕТЕЛЪСТ К АВТОРСКО 2 работы систолического автомата. В режиме программирования в ячейки первой группы р систолических структур (СС) 2 и второй группы и систолических структур (СС) 3 записываются в-разрядные кубические покрытия функций выхода и функций перехода автомата, которые поступают по первой группе в информационных двухразрядных входов 4, В режиме вычислений происходит параллельное формирование на группе в р информационных выходов 14 выходных последовательностей сигналов, определяемых внутренним состоянием автомата и щ входными последовательностями сигналов, поступающих на вторую группу п 1 информационных входов 5, Коммутация входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3 осуществляется с помощью блока 1 коммутации, Вычисление функций выходов и функций переходов в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций, 4 з.п,ф-лы, 7 ил 2 табл,П. Теория и проекльных схем. - М,; Наиболее близким по техн ности к предлагаемому являет щий автомат на ц состояний, с универсальных логических мод 1 о 92 ц коммутаторов, дешифрат выходы которого связаны с вхо ратора, выходы которого явля ми автомата, информационные коммутаторов соединены с выхо сальных логических модулей, щие входы соединены с выхода входы которого соединены с в ка коммутаторов, причем входь тся к вычислитель начено для парал формации при ее льтате выполнения ательностныи автоивные матрицы для ратной связи и выавтомата является автомата от реали ая сложность и низ ходам униве(71) Винницкий политехнический инст(57) Изобретение относится к вычислительной технике и предназначено для параллельной обработки информации при ее преобразовании в результате выполнения заданного алгоритма, Целью изобретения является повышение универсальности и производительности автомата при преобразованиях информации по заданному алгоритму для в гп1) входных последовательностей сигналов, Имеются два режима Изобретение относ ной технике и предна лельной обработки и преобразовании в рез заданного алгоритма. Известен последов мат, содержащий итера реализации функции об ходной функцции,Недостатком этого зависимость структуры зуемых функций, больш кая производительностической сущся управляюодержащий о улей, блок из ор и регистр, дами дешифются выхода- входы блока дами универа управляюми регистра, ы и блоЧерез каждые в циклов ВЯТ-триггеры 56 снова устанавливаются в нулевое состояние в указанной последовательности.В ц - й ВЯТ-триггер 56 первого элемента 35 свертки в.конце первого такта каждого цикла по входу 45группы п 1 информационных входов 45 поступает результат опера 7 ции пересечения компоненты б с компонентойк или о 1 от ячейки 34 с коорь идинатами (1, д) (ту= 1 - гп). Этот результат поступает на Я-вход д - го ВЯТ-триггера 56, и при наличии пустого пересечения компоненты с компонентой 1 или о 1 ц - й ВЯТь ьтриггер 56 устанавливается в единичное состояние. Я-вход РЯТ-триггера 56 является синхронным и запись в РЯТ-триггер 56 осуществляется во втором такте каждого цикла по приходу тактового сигнала на вход 48.На втором такте в-го цикла в первом РЯТ-триггере 56 формируется результат операции пересечения наборов .101 с кубом б 1 покрытия 01,пр. При пустом (непустом) пересечении наборов 001 с кубом б 1 первый РЯТ-триггер 56 находится в единичном (нулевом) состоянии.На втором такте (2 щ)-го цикла в а-м ВЯТ-триггере 56 формируется результат операции пересечения наборов О 01 с кубом бп покРытиЯ О 1,пр аналогичным обРазом,Окончательный вывод о результате операции пересечения наборов О 01 со всем покрытием 01,пр согласно соотношению (4) можно сделать после анализа результатов операции пересечения наборов О 01 с от 7дельными кубами покрытия 01,пр .Поэтому до получения результата операции пересечения наборов О 01 с кубом бп сохраняются результаты операции пересечения наборов 001 с предыдущими кубами покРытиЯ О 1,пр. С этой целью на третьем такте в-го, (п 1+1)-го(2 т)-го циклов по сигналам, поступающим по второй группе в управляющих входов 47, происходит передача инверсного содержимого соответственно первого РЯТ-триггера 56, второго РЯТ-триггера 56е-го ВЯТ-триггера 56 через элементы И 57 в ВЯ-триггер 58. При наличии в указанные моменты времени хотя бы одного РЯТ-триггера 56 в нулевом состоянии РЯ-триггер 58 по Я-входу устанавливается в единичное состояние.Следовательно, на третьем такте (2 п 1-1)- го цикла в РЯ-триггере 58 формируется зна 1 1чение функции р 1 ( О 01) согласно соотношению (4): единичное (нулевое) состояние РЯ-триггера 58 свидетельствует о( ) том, что на наборах 1 101 функция (р 1 (1 101) принимает единичное (нулевое) значение.В ВЯ-триггер 58 первого элемента 35 свертки с интервалом в п 1 циклов формируются значения функций: Р 1(1 101), Р 1(4.+10+1), Р 1 (2 +102 +1),Во втором такте пт-го 2 гп-го, Зв-го, циклов РЯ-триггер 58 сбрасывается в нулевое состояние по сигналу, который поступает по входу 49,Элементы И 57 являются элементами с открытым коллектором, что позволяет вместе с резистором 59 реализовать на их выходах схему "Монтажное ИЛИ".Остальные элементы 35 свертки в автомате работают аналогично.На фиг.6 показана последовательность появления управляющих сигналов на входах 46 - 49 элемента свертки.Для определения технико-экономической эффективности предлагаемого автомата по сравнению с известным оценивают производительность обеих автоматов на о состояний для К входных последовательностей сигналов, состоящих из г-компонентных входных наборов.В известном автомате входные последовательности сигналов могут поступать лишь друг за другом, поэтому соответствующие им выходные последовательности сигналов формируются за время Т 1: 30 где т 1 - длительность цикла работы автомата,В предлагаемом автомате входные последовательности сигналов поступают в конвейерном режиме, причем значения выходных функций от очередной входной последовательности сигналов, начиная с (2 п 1-1)-го цикла (где п 1 = г+ 1 о 92 о), поя вля ются на соответствующих выходах автомата на каждом цикле, Поэтому общее время Т 2 вычислений составляетТ 2 = (2 й - 1 + К - 1)12 = К12 + 2(г + +1 о 92 ц -1) Е 2, та где с 2 - длительность цикла работы автомаРост по производительности иредлагаемого автомата по сравнению с известным составляет Т 1 й гТг К+2 г+1 о 92 а - 1при 11=12, Формула изобретения 1. Систолический автомат; содержащий блок коммутации, отл и ч а ю щи й с ятем, что, с целью повышения универсальности и производительности автомата при преобразованиях информации по заданному алгоритму для в (в 1) входных последовательностей сигналов, введеныпервая группа р систолитических структур и вторая группа п систолических структур, причем группа в а (где а=р, если ри, или а=п, если ри) информационных выходов блока коммутации соединена с р вторыми группами а информационных входов первой группы р систолических структур и с и вторыми группами а информационных входов второй группы п систолических структур, первая группа в информационных двухразрядных входов первой систолической структуры из первой группы р систолических структур подключена соответственно к первой группе в информационных двухразрядных входов автомата, первая группа щ информационных двухразрядных входов(+1)-й Ц=1-(нсистолической структуры из первой группы р систолических структур соединены соответственно с первой группой а информационных двух- разрядных выходов)-й систолической структуры из первой группы р систолических структур, первая группа гп информационных двухразрядных входов первой систолической структуры из второй группы и систолических структур соединена соответственно с первой группой в информационных двухразрядных выходов последней систолической структуры из первой группы р систолических структур, первая группа щ информационных двухразрядных входов (+1)-й (1=1 - (исистолической структуры из второй группы и систолических структур соединена соответственно с первой группой в информационных двухрязрядных выходов 1-й систолической структуры из второй группы и систолических структур, вторые группы в информационных выходов первой группы р систолических структур подключены соответственно к группе в р информационных выходов автомата, вторая группа гп информационных входов которого подключена соответственно к первой группе щ информационных входов блока коммутации, вторая группа гп п информационных входов которого соединена соответственно с вторыми группами гп информационных выходов второй группы и систолических структур, первая - третья группы щ управляющих входов автомата подключены соответственно к первой - третьей группам а управляющих входов первой группы р и второй группы и систолических структур, четвертая группа в управляющих входов автомата подключена соответственно к группе в управляющих входов блока коммутации, первый управляющий вход автомата подключен к первому управляющему входу блока коммутации и к первому управляющему входу первой группы р и второй группы и систоли 5 10 30 35 15 20 25 40 45 50 55 ческих структур, второй управляющий вход автомата подключен к второму управляю-. щему входу первой группы р и второй группы п систолических структур, третий управляющий вход автомата подключен к третьему управляющему входу первой группы р и второй группы и систолических структур, четвертый управляющий вход автомата подключен к второму управляющему входу блока коммутации. 2. Автомат по п.1, о т л и ч а ю щ и й с я тем, что блок коммутации содержит группу а мультиплексоров, группу а счетчиков и группу в(ю)-разрядных сдвиговых регистров, первая группа а информационных входов блока соединена соответственно с первыми информационными входами всех мультиплексоров, второй, третий(п+1)-й информационные входы й-го (й=1 - а) мультиплексора соединены соответственно с им, (в+1)-м(в и-и+Ь)-м входами второй группы в п информационных входов блока, управляющие входы и-го мультиплексора соединены соответственно с выходами и-го счетчика, группа а управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены с вторым управляющим входом блока, первый управляющий вход которого, соединен с синхронизирующими, входами всех сдвиговых регистров, выход и-го мультиплексора соединен с первым информационным входом й-го сдвигового регистра и подключен к (й а-а+1)-му выходу группы а а информационных выходов блока, первый, второй(а)-1 выходы Ь-го сдвигового регистра подключены соответственно к (й а-а+2)-му, (и а-а+3)-му(Ь а)-му выходам группы в, чч информационных выходов блока.3, Автомат по п,1, о т л и ч а ю щ и й с я тем, что 3-я (з = 1 - а) систолическая структура содержит матрицу в щ ячеек, в элементов свертки, 4 в элементов И, 2 а элементов ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ соответствующего столбца матрицы, вторые входы которых соединены с выходами третьего и четвертого элементов И соответствующего столбца матрицы, первые входы которых соединены с вторым управляющим входом структуры и входом инвертора, первый и второй разряды двухразрядного входа первой группы щ информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого эле 17323402423510 15 20 25 30 35 40 45 50 ментов И соответствующего столбца матрицы, второй информационный вход первой, второйгп-й ячеек первого столбца матрицы соединен соответственно с з-м, (з + а)- м(а в-а+в)-м входом второй группы в информационных входов структуры, вторые информационные входы остальных ячеек каждой строки матрицы соединены соответственно с вторыми информационными выходами ячеек, являющихся соседними ячейками в строке слева, первые информационные двухразрядные входы ячеек всех строк матрицы, кроме первой строки, соединены соответственно с первыми информационными двухразрядными выходами ячеек, являющихся соседними ячейками в столбце сверху, выходы первого и второго элементов ИЛИ в каждом столбце соединегы соответственно с первым и вторым разрядами первого информационного входа первой ячейки этого столбца, выходы результата ячеек й-й (Ь = 1 - в) строки матрицы соединены с группой е информационных входов Ь-го элемента свертки, информационные входы элементов свертки соединены соответственно с второй группой щ информационных выходов структуры, первый и третий управляющие входы которой соединены соответственно с тактовыми входами ячеек и с первым управляющим входом элемента свертки, первый и второй разряды первого информационного двухразрядного выхода ячеек последней строки матрицы соединены с вторыми входами первого и второго элементов И соответствующего столбца, а также с первым и вторым разрядами соответствующего выхода первой группы а информационных двухразрядных выходов структуры, первая группа а управляющих входов структуры соединена соответственно с первой группой в управляющих входов элемента свертки, вторая группа п управляющих входов структуры соединена соответственно с второй группой в управляющих входов элемента свертки, вторые управляющие входы элементов свертки соединены соответственно с третьей группой гп управляющих входов структуры. 4. Автомат по п.З, о т л и ч а ю щ и й с я тем, что ячейка содержит три О-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата ячейки, второй информационный вход которой соединен с О-входом первого О- триггера, прямой вход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячейки, прямой выход второго О-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего Отриггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, О- входы второго и третьего О-триггеров соединены соответственно с первым и вторым разрядами первого информационного двух- разрядного входа ячейки, синхровходы всех О-триггеров соединены с тактовым входом ячейки,5, Автомат по п.З, о т л и ч а ю щ и й с я тем, что элемент свертки содержит группу щ ,ВЯТ-триггеров, группу гп элементов И с открытым коллектором, ВЯ-триггер и резистор, через который выходы группы п элементов И подключаются к источнику питания, причем группа щ информационных входов элемента свертки соединена соответственно с Я-входами группы в ВЯТ-триггеров, инверсные выходы которых соединены соответственно с первыми входами группы а элементов И, выходы которых соединены также с Я-входом ВЯ-триггера, прямой выход которого соединен с информационным выходом элемента свертки, первый управляющий входэлемента свертки соединен с Т-входами всех ВЯТ- триггеров, второй управляющий вход элемента свертки соединен с В-входом ВЯтриггера, первая группа управляющих входов элемента свертки соединена соответственно с В-входами группы в ВЯТ- триггеров, вторая группа в управляющих входов элемента свертки соединена соответственно с вторыми входами группы вэлементов И,гарина, 10 Производственно-издательский комбинат "Патент", г, Ужгоро аказ 1583 ВНИИПИ Тираж дарственного комитета по из 113035, Москва, Ж, РПодписноебретениям и открытиям при ГКНТ СССРушская наб., 4/5ных логических модулей от одной переменной являются входами автомата.Недостатками известного автомата являются сложность перенастройки автомата для реализации заданных алгоритмов и его низкая производительность при преобразованиях информации для нескольких входных последовательностей сигналов.Целью изобретения является повышение универсальности и производительности автомата и ри преобразованиях информации по заданному алгоритму для в (в1) входных последовательностей сигналов.В систолический автомат, содержащий блок коммутации, введены первая группа р систолических стуктур и вторая группа и систолических структур, причем группа в а (где а=р, если рп, или а=п, если р 5 п) информационных выходов блока коммутации соединена с р вторыми группами в информационных входов первой группы р систолических структур и с п вторыми группами в информационных входов второй группы и систолических структур, первая группа в информационных двухразрядных входов первой систолической структуры из первой группы р систолических структур подключена соответственно к первой группе в информационных двухразрядных входов автомата, первая группа в информационных двухразрядных входов +1)-й О =.1-(рсистолической структуры из первой группы р систолических структур соединены соответственно с первой группой в информационных двухрэзрядных выходов )-й систолической структуры из первой группы р систолических структур, первая группа в информационных двухразрядных входов первой систолической структуры из второй группы и систолических структур соединена соответственно с первой группой в информационных двухразрядных выходов последней систолической структуры из первой группы р систолических структур. Первая группа в информационных двухразрядных входов (1+1)-й ( = 1 - (исистолической структуры из второй группы и систолических структур соединена соответственно с первой группой в информационных двух- разрядных выходов -й систолической структуры из второй группы п систолических структур. Вторые группы в информационных выходов первой группы р систолических структур подключены соответственно к группе в р информационных выходов автомата, вторая группа в информационных входов которого подключена соответствен но к первой группе в информационных входов блока коммутации, вторая группа в иинформационных входов которого соединена соответственно с вторыми группами в5 информационных выходов второй группы п 10 15 20 25 30 35 40 45 50 55 систолических структур. Первая - третья группы в управляющих входов автомата подключены соответственно к первой - третьей группе в управляющих входов первой группы р и второй группы и систолических структур. Четвертая группа в управляющих входов автомата подключена соответственно к группе в управляющих входов блока коммутации. Первый управляющий вход автомата подключен к первому управляющему входу блока коммутации и к первому управляющему входу первой группы р и второй группы п систолических структур, второй управляющий вход автомата подключен к второму управляющему входу первой группы р и второй группы и систолических структур, третий управляющий вход автомата подключен к третьему управляющему входу первой группы р и второй группы п систолических структур, четвертый управляющий вход автомата подключен к второму управляющему входу блока коммутации, который содержит группу в мультиплексоров, группу в счетчиков и группу гп (а)-разрядных сдвиговых регистров,Первая группа в информационных входов блока соединена соответственно с первыми информационными входами всех мультиплексоров, второй, третий,(п+1)-й информационные входы и-го (п=1 - в) мультиплексора соединены соответственно с им, (в+п)-м,.,(в и-в+и)-м входами второй группы в и информэионных входов блока, управляющие входы и-го (п=1 - в) мультиплексора соединены соответственно с выходами й-го счетчика,Группа в управляющих входов блока соединена соответственно с входами суммирования всех счетчиков, входы сброса которых соединены вторым управляющим входом блока, первый управляющий вход которого соединен с синхронизирующими входами всех сдвиговых регистров, выход и-го (й=1 - в) мультиплексора соединен с первым информационным входом и-го сдвигового регистра и подключен к (и а-а+1)- му выходу группы ва информационных выходов блока, первый, второй(а)-й выходы и-го (п=1 - в) сдвигового регистра подключены соответственно к (й а-а+2)-му, (и а-а+3)-му(й а)-му выходам группы в а информационных выходов блока, причем з-я (э=1 - а) систолическая структура содержит матрицу в в ячеек, в элементов10 15 20 25 30 35 40 45 50 55 свертки, 4 е элементов И, 2 е элементов ИЛИ и инвертор, вход которого соединен с первыми входами первого и второго элементов И соответствующего столбца матрицы, выходы которых соединены с первыми входами первого и второго элементов ИЛИ соответствующего столбца матрицы, вторые входы которых соединены с выходами третьего и четвертого элементов И соответствующего столбца матрицы, первые входы которых соединены с вторым управляющим входом структуры и входом инвертора. Первый и второй разряды двухразрядного входа первой группы в информационных входов структуры соединены соответственно с вторыми входами третьего и четвертого элементов И соответствующего столбца матрицы, второй информационный вход первой, второй,.;.,а-й ячеек первого столбца матрицы соединен соответственно с з-м, . (и+э)-м,(а в-а+э)-м входом второй группы в информационных входов структуры, Вторые информационные входы остальных ячеек каждой строки матрицы соединены соответственно с вторыми информационными выходами ячеек, являющихся соседними ячейками в строке слева, первые информационные двухразрядные входы ячеек всех строк матрицы, кроме первой строки, соединены соответственно с первыми информационными двухразрядными выходами ячеек, являющихся соседними ячейками в столбце сверху,Выходы первого и второго элементов ИЛИ в каждом столбце соединены соответственно с первым и вторым разрядами первого информационного входа первой ячейки этого столбца, выходы результата ячеек и-й (Ь=1 - гп) строки матрицы соединены с группой в информационных входов й-го элемента свертки, информационные выходы элементов свертки соединены соответственно с второй группой а информационных выходов структуры, первый и третий управляющие входы которой соединены соответственно с тактовыми входами ячеек и с первым управляющим входом элемента свертки, первый и второй разряды первого информационного друхразрядного выхода ячеек последней строки матрицы соединены с вторыми входами первого и второго элементов И соответствующего столбца, а также с первым и вторым разрядом соответствующего выхода первой группы в информационных двухразрядных выходов структуры.Первая группа а управляющих входов структуры соединена соответственно с первой группой щ управляющих входов элемента свертки, а вторая группа щ управляющих входов структуры - соответственно с второй группой а управляющих входов элемента свертки, Вторые управляющие входы элементов свертки соединены соответственно с третьей группой а управляющих входов структуры,Ячейка содержит три О-триггера, элемент неравнозначности и элемент И, выход которого соединен с выходом результата ячейки, второй информационный вход которой соединен с О-входом первого О-триггера, прямой выход которого соединен с первым входом элемента неравнозначности и с вторым информационным выходом ячейки, прямой выход второго О-триггера соединен с вторым входом элемента неравнозначности и с первым разрядом первого информационного двухразрядного выхода ячейки, прямой выход третьего Отриггера соединен с первым входом элемента И с вторым разрядом первого информационного двухразрядного выхода ячейки, выход элемента неравнозначности соединен с вторым входом элемента И, О- входы второго и третьего О-триггеров соединены соответственно с первым и с вторым разрядом первого информационного двухразрядного входа ячейки, синхровходы всех О-триггеров соединены с тактовым входом ячейки,Элемент свертки содержит группу щ КЯТ-триггеров, группу в элементов И с открытым коллектором, КЯ-триггер и резистор, с помощью которого выходы группы а элементов И подключаются к источнику питания, группа в информационных входов элемента свертки соединена соответственно с Я-входами группы а КЗТ-триггеров, инверсные выходы которых соединены соответственно с первыми входами группы в элементов И, выходы которых соединены также с Я-входом ВЯ-триггера, прямой выход которого соединен с информационным выходом элемента свертки. Первый управляющий вход элемента свертки соединен с Т-входами всех ЙЯТ-триггеров, второй управляющий вход элемента свертки соединен с Й-входом ЙЯ-триггера, первая группа в управляющих входов элемента свертки соединена соответственно с В-входами групоы а ЯЯТ-триггеров, вторая группа в управляющих входов элемента свертки соединена соответственно с вторыми входами группы а элементов И.В предлагаемом и в известном автоматах необходим этап предварительной подготовки перед началом работы автомата,В известном автомате предварительная подготовка автомата заключается в его настройке с помощью переключателей для ре10 15 20 томата ализации заданного алгоритма функционирования.В предлагаемом автомате перед началом работы в ячейки систолических структур записываются кубические покрытия функций выходов и функций переходов автомата. Выполняемая комбинационной частью автомата функция интерпретируется как установление принадлежности входного набора аргументов множеству наборов, на которых булева функция принимает значение логической "1" (логического "0"). Установление принадлежности входного набора аргументов указанному множеству наборов выполняется с помощью операций пересечения над кубами покрытий булевой функции, Разбиение всего процесса вычислений булевой функции на элементарные независимые друг от друга операции позволило организовать в предлагаемом автомате систолическую обработку данных. Начиная с определенного момента времени, на соответстветствующих выходах автомата на каждом цикле работы реализуется значение функции выхода автомата от очередной входной последовательности сигналов из группы входных последовательностей сигналов.В известном автомате следующая входная последовательность сигналов может быть подана на входы автомата только после окончание формирования выходной последовательности от предыдущей входной последовательности сигналов,В предлагаемом автомате программирование работы автомата заключается в записи новых кубических покрытий, тогда как изменения функционирования известного автомата выполняется аппаратурным способом путем перевода переключателей в другие положения,На фиг,1 представлена функциональная схема систолического автомата; на фиг.2 - функциональная схема блока коммутации (БК); на фиг.З - функциональная схема в-й (э=1 - а) систолической структуры (СС); на фиг.4 - схема ячейки; на фиг,5 - схема элемента свертки; на фиг,6 - временная диаграмма управляющих. сигналов; на фиг,7 - схема автомата Мили.Систолический автомат содержит (фиг.1) БК 1, первую группу р СС 2, вторую группу и СС 3, первую группу е информационных двухразрядных входов 4, вторую группу в информационных входов 5, первую - четвертую группы гп управляющих входов 6 - 9, первый - четвертый управляющие входы 10 - 13, группу в р информационных выходов 14, первую группу в информационных входов 15 БК 1, вторую 25 30 35 40 45 50 55 группу а и информационных входов 16 БК 1, группу в управляющих входов 17 БК 1, первый управляющий вход 18 БК 1, второй управляющий вход 19 БК 1, группу а чч(где а=р, если рп, или а=п, если ри) информационных выходов 20 БК 1, первую группу а информационных двухразрядных входов 21 СС 2 и СС 3, вторую группу щ информационных входов 22 СС 2 и 3, первую - третью группы в управляющих входов 23 - 25 СС 2 и 3, первый - третий управляющие входы 26 - 28 СС 2 и 3, первую группу т информационных двухразрядных выходов 29 СС 2 и 3, вторую группу в информационных выходов 30 СС 2 и 3.БК 1 предназначен для коммутации входных сигналов и сигналов обратной связи автомата на входы СС 2 и 3.Первая группа р СС 2 предназначена для вычислений функций выхода автомата.Вторая группа и СС 3 предназначена для вычислений функций обратной связи авБК 1 содержит (фиг,2) группу а мультиплексоров 31, группу т счетчиков 32, группу пз (а)-разрядных сдвиговых регистров 33,СС 2 и 3 имеют одинаковую структуру и содержат (фиг,З) т т ячеек 34, гп элементов свертки 35, 4 гп элементов И 36, 2:п элементов ИЛИ 37, инвертор 38, первый информационный двухразрядный вход 39 ячейки 34, второй информационный вход 40 ячейки 34, тактовый вход 41 ячейки 34, первый информационный двухразрядный выход 42 ячейки 34, второй информационный выход 43 ячейки 34, выход результата ячейки 34, группу щ информационных входов 45 элемента 35 свертки, первую группу а управляющих входов 46 элемента 35 свертки, вторую группу щ управляющих входов 47 элемента 35 свертки, первый управляющий вход 48 элемента 35 свертки, второй управляющий вход 49 элемента 35 свертки, информационный выход 50 элемента 35 свертки.Ячейка 34 предназначена для выполнения элементарной операции пересечения компоненты входного набора аргументов булевой функции с компонентой одного куба кубического покрытия этой функции,Элемент 35 свертки предназначен для формирования результата вычисления булевой функции на соответствующих входных наборах ее аргументов.Ячейка 34 (фиг.4) содержит О-триггеры 51 - 53, элемент 54 неравнозначности, элемент И 55,Элемент 35 свертки (фиг,5) содержит группу щ ЯЯТ-триггеров 56, группу щ элементов И 57 с открытым коллектором, ВЯтриггер 58 и резистор 59.Автомат работает следующим образом.Автомат работает в режиме программирования и в режиме вычислений.В режиме программирования производится запись в автомат информации, определяющей его функционирование привычислении заданных выходных последовательностей сигналов,Общей структурной моделью систолического автомата является автомат Мили(фиг.7), содержащий память (П), комбинационную схему выходов (КСВ) и комбинационную схему переходов (КСП),Функционирование автомата Мили однозначно определяется таблицами переключений элементов памяти, входящих в П, изначениями булевых функций, реализуемыхКСВ и КСП,С помощью КСВ формируется функциярвыходов, выражающая зависимость выхода 2 автомата в момент времени 1 от выхода Ч и состояния А автомата в этот жемомент времени:ф) = р(Ч(т),А(1.С помощью КСП формируется функцияд переходов, выражающая зависимость состояния А автомата в момент времени 1+1 отвхода Ч и состояния А автомата в моментвремени 1:А(т+1) = д (Ч(т),А(т,Для автомата с г входами, р выходами ии элементами памяти, в качестве которыхиспользуются О-триггеры, схема КСВ является р-выходной схемой, на входах которойреализуются функции р 1 р р, а схемаКСП является и-выходной схемой, на выходах которой реализуются функциид 1 ",дпВ систолическом автомате функции гр 1рр и д 1 д и задаются в виде кубических покрытий (О-покрытий илиВ-покрытий) этих функций.0-покрытие (В-покрытие) некоторой булевой функции 1 - это представленная вкубической форме минимальная дизьюнктивная нормальная форма (МДНФ) прямойфункции 1 (инверсной функции ). МДНФпрямой функции 1 (инверсной функции 1)содержит все наборы, на которых функцияпринимает значение логической "1" (логического "0"), 0-покрытие (В-покрытие) состоитиз кубов, число которых равно числу импликант МДНФ прямой функции 1 (инверснойфункции 1), Число компонент куба равночислу переменных МДНФ, а значениямикомпонент куба могут быть только три символа: 0,1,х, где х=(0,1, Каждый куб б(г) со 5 10 15 20 25 30 35 40 45 50 55 ответствует одной импликанте МДНФ прямой функции т (инверсной функции Ц таким образом, что единичное (нулевое) значение компонент куба соответствует прямому (инверсному) значению переменной в импликанте МДНФ (бфО, геВ),Каждое из покрытий (О и В) однозначно определяет функционирование комбинационной схемы, поэтому используется только одно из них, а именно то покрытие, которое содержит меньшее число кубов (в дальнейшем, для простоты, рассматриваются только О-покрытия),Таким образом, схема КСВ описывается группой из р покрытий 01 Ор, а схема КСП - группой из и покрытий 010 п,О-покрытие состоит из а 1-кубов, число которых равно числу импликант МДНФ прямой функции р. 01 = (б 1био,бц), ц=а, )о=1 - ц, 0 -покрытие состоит из а кубов, число которых равно числу импликант МДНФ прямой функции д : ОА (ААА) д Число Со компонент куба всех покрытий равно Со= г+ и. Пусть, например, автомат имеет три внешних входа (а,Ь,с) и два входа обратной связи (ц 1,ср), причем МДНФ функции имеет видр; = (а,Ь,с,ц 1,Ю) = асцгчЬсс 1 ь цщг, Тогда О-покрытие, соответствующее МДНФ указанной функции, имеет вид а Ь с р 1 ср 1 хах 1 О= х 110 хххх 11Число а 1 (пцд) кубов 0-покрытия (Одпокрытия) и число Со компонент кубов покрытий О и О (=1-р, =1 - и) связаны с параметром а схемы автомата следующим образом: а а;а а; Со а. Если Соа, то (а-Со) разрядов соответствующего покрытия дополняются значениями х, Если а а (аа), то к соответствующему О-покрытию (ОА-покрытию) добавляется а-а(а-а ) строк, являющихся копиями одной из строк этого покрытия (в дальнейшем, для простоты, рассматривают работу автомата только с а-разрядными О-покрытиями (О -покрытиями) содержащих по а кубов, при этом а = г+ и).Перед началом работы автомата исходные покрытия 01,Ор и 01 , Оп преобразуются соответственно в покрытия7 г А А01,пр,".,Ор,пр и 01,прО,пр, которыезатем в режиме программирования, записываются в СС 2 и 3.Процесс преобразования указанных покрытий на примере одного О-покрытия вида б 11 б 12б 1 в б 21 б 22 б 2 п 1 О =,бЬ 1 бЬ 2бЬп, бв 1 бв 2 , бвв происходит следующим образом.О-покрытие вида (1) преобразуется в Опр-покрытие за два этапа. На первом этапе происходит транспортирование О-покрытия аналогично известной операции транспортирования матриц. На втором этапе компоненты первого столбца транспортированного О-покрытия циклически сдвигаются снизу вверх на одну позицию; компоненты второго столбца транспортированного О-покрытия циклически сдвигаются снизу вверх на две позиции, и т,д,. В итоге Опр-покрытие принимает вид б 1 в бг(в)бв 1 01 в) бг(в) , бвв Опр = б 1) "бг(ь) , бв б 12 б 21 ., бвз б 11 б 2 вбв 2 По аналогичному алгоритму происходит1 г ПОЛУЧЕНИЕ ПОКрЫтИй 01,пр ,Ор,пр ИА А О 1,пр,".,Оп,прЗа ПИСЬ ПОКРЫТИЙ О 1,прОр,пр И О 1,пр,".,Оп,пр в СС 2 и 3 осуществляетсяд А через первую группу а информационных двухразрядных входов 4 при наличии разрешающего сигнала (логической "1") на втором упраляющем входе 11, Запись указанных покрытий происходит в течение (и+р) гп циклов, в каждом цикле записывается один куб, начиная с последнего куба Оп,пр -покрытия, Вначале на первую группуА п 1 информационных двухразрядных входов 4 постУпают покРытиЯ 01,пр Оп,пр, а зад А тем покРытиЯ 01,пр, Ор,пр. В Режиме пРограмми рован ия образуется путь прохождения информации между всеми соседними парами СС 2 и 3,В режиме вычислений происходит параллельное формирование на группе в р информационных выходов 14 выходных последовательностей сигналов, определяемых внутренним состоянием автомата и а входными последовательностями сигналов, поступаемых на вторую группу а информационных входов 5. Этот процесс осущестляется по циклам, каждый из которых состоит из трех тактов.Вычисление функцийр 1 ур и д 1 д и в автомате происходит путем выполнения ряда операций над кубическими покрытиями этих функций, записанных ранее в режиме программирования в соответствующие СС 2 и 3,Исходное состояние автомата принимается нулевым, т.е. значения функций5 д 1 д и вначале равны нулю.В режиме вычислений на второй управляющий вход 11 поступает сигнал логического "0" и информационная связь междувсеми соседними парами СС 2 и 3 прерыва 10 ется.Во время работы автомата на вторуюгруппу п 1 информационных входов 5 параллельно поступают в входных последовательностей сигналов:15 . 2 в+1 в+1 1 - ПОСЛЕдОВатЕЛЬНОСтЬ "1";. гв+г.в+г г - последовательность "2";.Зв гв)в - ПОСЛЕдОВатЕЛЬНОСтЬ "П 1",в следующем порядке,На первый вход 51 поступают компонен 20 ты набора1:1.1 =(1 )2)г)начиная с компоненты )1,На 1-Й вход 5 ь со сдвигом во времени на1-1) циклов относительно компоненты на 25 бора1 поступают компоненты набора Ь:Ь=(1 2 "г)начиная с компоненты 1 1=1 - в).После поступления на вход 5 ь последней компоненты г набора Ь через и цикловь30 начинают поступать компоненты набора)-в+и:в+Ь в+и, в+йНаЧИНаЯ С КОМПОНЕНТЫ 1 вМежду поступлениями на вход 5 ь ком 35 понент набора Ь и наборав+ь поступаюткомпоненты набора СЬ сигналов обратнойсвязи:СЬ = (а 1 ьс)РЦпь),начиная с компоненты с 1,40 Компоненты набора СЬ поступают сосдвигом во времени на 1-1) циклов относительно компонент набора О 1,На выходах БК 1 формируется цч пакетовнаборов следующим образом.45 Первый пакет формируется на следующих выходах БК 1:Ов+1 в+101- На ВЫХОДЕ 201;Ов+2 в+202 2 - на выходе 20+1; (2)Огв.гвцв в - На ВЫХОДЕ 20(в)ч+1.50 Наборы пакета (2) на входе 20 ь+1 поступают со сдвигом во времени на один циклотносительно наборов на соседнем входе20(Ь)а+1.В общем случае, )-й пакет наборов фор 55 мируется на следующих выходах БК 1:Наборы пакета (3) в каждой строке поступают со сдвигом во времени на (1-1) циклов относительно наборов в одноименной строке пакета (2). Наборы соседних сторон пакета (3) также поступают со сдвигом во времени на один цикл относительно друг друга внутри пакета.Наборы пакета (2) поступают одновременно на входы первой СС 2 и на входы первой СС 3, Аналогично, наборы пакета (3) поступают одновременно на входы )-й СС 2 О = 1 - р) и на входы 1-й СС 3(1 = 1 - п).С помощью группы р СС 2 происходит вычисление функций р 1 , у р для заданных а-входных последовательностей сигналов.и 1Значение функции о 1 появляется на первом выходе первой СС 2 на(2 а)-м цикле после поступления на первый вход первой СС 2 первой компоненты 11 . входного набора 11.(1)Значение функции р 1 появляется на первом выходе )-й СС 2 через Д) циклова 1)после вычисления функции ) 1.(ьзЗначение функции у) появляется на Н- м выходе)-й СС 2 через(Ь+)-2) циклов после11вычисления функции р 1(или на (2 а)-м цикле после поступления на 1-й вход)-й СС 2 первой компоненты 11"+ входного набора Ь+1) =1 - р, И=1 - гп).Очередные значения функции ус ), определяемые Ь-й входной последовательностью сигналов". 1-2 в+л Ьп+ь Ьпоявляются через каждые в циклов на и-м выходе)-й СС 2,С помощью группы и СС 3 происходит вычисление функций д 1 ддля заданных в входных последовательностей сигналов.111Значение функции д 1 появляется на первом выходе первой СС 3 на(2 щ)-м цикле после поступления на первый вход первой СС 3 первой компоненты 11 входного набора 11, т.е, одновременно с вычислением функции р 1 .Аналогично, значения функции д 1") появляются на Ь-м выходе 1-й СС 3 одновременно с вычислением функции р ), если 1=) 0 = 1 - и, ) - 1 - р, Ь = 1 - в).БК 1 работает следующим образом.Перед началом работы БК 1 устанавливается в исходное состояние по приходу сигнала сброса на второй управляющий вход 19. В исходном сотоянии все счетчики 32 находятся в нулевом состоянии. 5 10 15 20 25 30 35 40 45 50 55 Вначале управляющие сигналы в первом такте каждого цикла начинают поступать по первому входу 171 группы в управляющих входов 17,Затем, со сдвигом на один цикл относительно соседних входов, начинают поступать управляющие сигналы на входы 172,.,17 п группы а управляющих входов 17,В итоге, счетчики 32 начинают считать, причем состояния соседних счетчиков в каждом цикле отличаются на единицу, Счетчики 32 имеют модуль пересчета гп,Мультиплексоры 31 коммутируют сигналы так, что в течение первых г циклов на выходе Ь-го мультиплексора 31 поступают сигналы с входа 15 ь первой группы гп информационных входов 15, а в течение последующих и циклов - поочередно от тех и входов второй группы а и информационных входов 16, которые подключены к 6-му мультиплексору, Далее на выход Ь-го мультиплексора 31 снова поступают сигналы с входа 15 ь и т,д.Сигналы с выхода каждого мультиплексора 31 записываются в соответствующий (а)-разрядный сдвиговый регистр ЗЗ, начиная с младшего разряда регистра 33. С помощью и-го регистра 33 организуется задержка на 1а циклов сигнала с выхода Ь-го мультиплексора 31 на соответствующие выходы 20(ь)ду+2,20(ь)у+у группы гпаа информационных выходов 20.В первой группе р СС 2)-я СС 2 работает следующим образом 0 = 1 - р),В режиме программирования при наличии разрешающего сигнала (логической н 1 н) на втором управляющем входе 27 происходит поступление кубов покрытий О).пр,Ор,пр" через первую группу щ информационных двухразрядных входов 21, Покрытия О 1)+),пр,.,Ор,пр проходят через )=ю СС 2 на первую группу гп информационных двухразрядных выходов 29, а покрытие О),пр записывается в )-ю СС 2,В режиме вычислений в )-м СС 2 осуществляется вычисление функций путем выполнения ряда операций над записанным ранее покрытием О),пр.Традиционный метод вычисления булевой функции 1 на входном наборе 1 ее аргументов с помощью комбинационной схемы можно интерпретировать как установление принадлежности входного набора 1 множеству наборов, на которых функция 1 принимает значение логической н 1".При использовании кубического представления булевых функций установление принадлежности входного набора 1 указанному множеству наборов может быть выполвено аналитически с помощью операции пересечения кубов. По определению операции пересечения куба а=а 1 ага и куба Ь=Ь 1 ЬгЬд обозначается как с = а Л ь и слу,жИт дЛя ВЫдЕЛЕНИя Куба С = С 1 СгСл, яВЛяЮ. щегося общей частью кубов а и Ь. Значение компоненты с определяется по табл.1, как с = а 1 Ь ( = 1 - и), где знак ф означает пустое пересечение), Например, еслиа=х 10 х 1, Ь=1 х 011, 10 тогда куб с равенх 10 х 11 х 0111 х 011Входной наборпринадлежит множе ству наборов, на которых функция 1 принимает значение логической "1" (логического "0"), если имеет место непустое пересечение наборахотя бы с одним кубом О-покрытия функции 1 (пустое пересечение 20 наборасо всеми кубами О-покрытия функции т):1, если Об Фф для любого е;1(1 )=О, если .11 б, =ф для всех е, 25где :-( ги),б =(б 1 ббг бв ), е =1 - в, б 6 О. Аналогичные соотношения справедливы и для комбинационной схемы КСП 30(фиг.7), на входы которого поступают входные наборы сигналов и наборы сигналовобратной связи,Значение функции р на Ь-м выходе)-й СС 2 может быть определено следующимобразом:1, 0 если Ь ОДо. Фф для любого еуЬ)(лол)-(4), О, если ЬОллсф =ф для всех еГдЕ Ь=(1 г . г )ь ь ь 400 ( ь ь ь.л гаОтЕсли, например,ь = (111) и 0 ь =(00),тогда рассматривавшаяся функция(р (а,Ь,с,р 1,рг) принимает единичное значение, так как имеется непустое пересечениес одним кубом покрытия О этой функции:х 11 0 х501110011100Отличительной особенностью выполнения операции над кубами является возможность одновременной и независимойобработки отдельных компонент кубов. Благодаря указанной особенности процесс выполнения операции пересечения входныхнаборов аргументов булевой функции с кубами кубического покрытия этой функции распараллеливается с помощью матрицы п 1в ячеек 34.На вторую группу а информационныхвходов 22)-й СС 2 поступает параллельно)-йпакет наборов:".0 в+г.в+г 0 г г - на вход 22 и+е; (5)0 гв-гв 0 вщ На ВХОД 22(в)а+е,Наборы соседних строк пакета (5) поступают со сдвигом во времени на один циклотносительно друг друга внутри пакета.Процесс вычислений в матрице ячеек 34начинается с активизации первой ячейки 34первой строки, т,е. ячейки 1 с координатами(1,1).На первом такте )-го цикла работы навход 40 указанной ячейки 34 поступает компонента 1 входного набора .1, а также про 1исходит циклический сдвиг сверху вниз постолбцам содержимого матрицы ячеек 34.Вследствие этого сдвига на вход 39 ячейки34 с координатами (1,1) поступает компонента б 11 покрытия О 1,пр и на выходе 44указанной ячейки 34 получается результатвыполнения операции:1 О б 11.На первом такте )-го цикла работы первый элемент 35 свертки устанавливается висходное состояние, а на втором такте повходу 451 группы п 1 информаицонных входов полученный результат из ячейки 34 скоординатами (1,1) записывается в первыйэлемент 35 свертки.На первом такте (+1)-го цикла работыкомпонента 1 набора1 поступает на вход40 ячейки 34 с координатами (1,2), а на входы 40 ячеек 34 с координатами (1,1) и (21)поступают компоненты соответственно г и1 г (г 161, 1 г ег).После циклического сдвига в матрицеячеек 34 на входы 39 ячеек 34 с координатами (1,1), (1,2) и (2,1) поступают соответствующие компоненты покрытия 01,пр. В итоге,на первом такте (+1)-го цикла выполняютследующие операции:г Об 1 г - в ячейке 34 с координатами(2,1).На втором такте Ц+1)-го цикла результаты выполнения указанных операций в ячейках 34 с координатами (1,1) и (1,2)записываются в первый элемент 35 свертки,а результат выполнения операции в ячейке34 с координатами (2,1) записывается вовторой элемент 35 свертки,После этого фронт выполняемых операций перемещается к ячейкам 34 с координатами (3,1), (2,2), (1,3) и, таким образом, порождается волна вычислений, бегущая вниз по матрице ячеек 34.В течение первых а циклов, начиная с )-го цикла, в ячейке 34 с координатами (1,1) поочередно получают результаты выполнения следующих операций:11 Ьб 11, 1 г Гъб 1 гг, ц 1 бб 1(г+1),."кцп Ъб 1 а Тем самым на первом такте (1+в)-го цикла заканчивается выполнение операции пересечения наборов 001 с компонентами кУба б 1 г покРытиЯ Р 1,пр. Общий РезУльтат выполнения операции пересечения наборов 1101 с кубом б 1 г формируется в первом элементе 35 свертки на втором такте +а)- го цикла.На первом такте 0+в)-го цикла в ячейке 34 с координатами (1,2) заканчивается выполнение операции пересечения наборов 001 с кубом б 2 г покрытия О 1,пргНа первом такте (1+2 а)-го цикла в ячейке 34 с координатами (1,в) заканчивается выполнение операции пересечения наборов О 01 с кубом бп покрытия 01,пр. Общий результат выполнения операции пересечения наборов 1 101 с кубом бп формируется в первом элементе 35 свертки на втором такте Ц+2 в)-го цикла,На третьем такте О+2 в)-го цикла на первом выходе 301 второй группы в информационных выходов 30 получают окончательный результат выполнения операции пересечения наборов 1101 с покрытием О 1,пр, сфоРмиРованным в соответствии с соотношением (4). На выходе 301 в указанный момент времени значение логической н 1 и (логического нОи) соответствует значению фУнкции Р 1, покРытиЯ 01,пр котоРый записано в)-1 СС 2, на входном наборе 11 и наборе 01 сигналов обратной связи автомата.При дальнейшей работе автомата на третьем такте)+2 в)+За циклов на выходах 302,30 п 1 второй группы а информационных выходов 30 поочередно получают результаты выполнения операции с покрытием О 1,пр наборов 1 102Ьп 0 Ь,Во второй группе и СС 3 1-я СС 3 работает следующим образом (1 = 1 - и).В режиме программирования в 1-ю СС 3 записывается покрытие О 1,пр аналогичноАзаписи покрытия О 1,пр в 1-ю СС 2, В режиме вычислений в 1-й СС 3 осуществляется вычисление функций д 1), .д п аналогично вычислению функций у 1 , ю 1" в -й сс 2,Ячейка 34 работает следующим образом,На первом такте каждого цикла по входу39 в О-триггеры 52 и 53 записывается очередная компонента б . (б) покрытия 01,прг(О,пр ), а в О-триггер 51 - очередная компо нента 1 набора Ь или компонента ц набора 0 ь (К = 1 - г; 1 = 1 - и; Ь = 1 - в).Поскольку значениями компонент кубамогут быть символы из алфавита (0,1,х), поэтому для представления компоненты бв 10 двоичном алфавите необходимо два разряг 1 г 2да бе би0 -011 -11х -1015 Поэтому, на первом такте каждого цикла в О-триггер 52 и в О-триггер 53 записываются значения соответственно би бг 1 г 2После окончания записи соответствующей информации в О-триггеры 51-53 выпол 20 няется. операция пеъоесечения компонентыб ч с компонентой 1 или ц .г .ьПоскольку значениями компонент 1 ийц могут быть только символы нОи и и 1",поэтому в ячейке 34 укаэанная операция25 пересечения выполняется согласно табл.2.В ячейке 34 реализуется следующаяфункция О:О - (Е"О И,",1 П д,"для компонент 11 и би гВ-(, Пе 1,Пе 1 ДО(",Пе 1 ПЗ)ии(% 1 ы) "ы35 для компонент ц и би гФункция О, которая реализуется с помощью элемента 54 неравнозначности иэлемент И 55, принимает значение логической и 1 н (логического иОи) при наличии пус 40 того (непустого) пересечения компонентыб с компонентой 1 ь или ср В конце первого такта каждого циклазначение функции реализуется на выходе 44 45 ячейки 34.Аналогично реазлизуется функция О идля покрытия О,пр,АПервый элемент 35 свертки в первой СС2 работает следующим образом.50 На первом такте первого цикла по сигналу, поступающему по входу 461 первой группы в управляющих входов 46 первый ЯЯТ-триггер 56 устанавливается в нулевое состояние.55На первом такте каждого последующегоцикла поочередно устанавливаются в нулевое состояние второй ВЯТ-триггер 56 в-й ЯЯТ-триггер 56.