Систолическая структура для вычисления логических функций

Редактор елобанова аказ 1951 Тираж 399 НИИПИ Государственного комитета по 113035, Москва, Ж906 Гагарин, 1 ц ент", г, Ужгород дательский комбин Произ дпФ бл 3 Ан 8 бй+1Ел бпб-г бпбпЗг+3Ъв ЧрЪ сй М м ьз,счсчПодписное ениям и открытиям при ГКНТ ССС кая наб, д, 4/51654809 рицы ячеек 1, а число кубов - числа щ столбцов матрицы ячеек 1. В течение всего времени работы структуры на первую группу информационных вхо 5 дов 4-4 п структуры параллельно поступают наборы аргументов логической функции. Процесс вычисления логической функции с числом аргументов не более и заключается в выполнении опе раций пересечения входных наборов аргументов с кубами покрытий логичес+ кой функции в ячейках 1 и формирова- нии результата вычислений в элеменИзобретение относится к.-вычислительной технике и предназначено для 20параллельной обработки информациипри вычислении логических Функций,Цель изобретения - повышение быстродействия при вычислении логическихфункций из последовательностей входных наборов аргументов,На фиг.1 представлена Функциональ", ная схема систолической структуры,на Фиг.2 - схема ячейки; на фиг.3схема элемента свертки; на Фиг,4схема потоков данных для систолической структуры в исходном состоянии;на Фиг.5 - временная диаграмма сигналов на управляющих входах структуры,35Систолическая структура содержит(Фиг,1) матрицу пш ячеек 1 п эле -ментов 2 свертки, 2 ш элементов ИЛИ 3,первую группу 4 п информационных входов, вторую группу 5 ш информационных 40двухразрядных входов, группу бп информационных к.-разрядных выходов,первый 7 и второй 8 управляющие вхо"ды, первую 9 ш,. вторую 10 ш и третью11 Е группы управляющих входов стрУктуры, первый информационный вход 12ячейки 1, второй информационныйдвухразрядный вход 13 ячейки 1, второй информационный выход 14 ячейки 1,.первый информационный двухразрядныйвыход 15 ячейки 1, выход 16 результата ячейки 1, тактовый вход 17 ячейки 1, группу 18 ш .информационных входов элемента 2 свертки, информационный 1-разрядный выход 19 элемента2 свертки, тактовый вход 20 элемента2 свертки, первую группу 21 ш-тактовых входов элемента 2 свертки, вто"рую группу 22 ш-тактовых входов элетах 2 свертки. Начиная с (п + ш. - 1)- го цикла работы предлагаемой структуры, на выходах 6 -6 п группы инфрр 1 вГ мационных Е-разрядных (Е=- , гдеозначает округление до ближайшего целого в большую сторону) выходов структуры на каждом цикле работы вы" числяется значение логической функщи от очередного входного набора аргументов. 1 з,п . Ф-лы, 5 ил ., 3 табл.мента 2 свертки, третью группу 23Ы-тактовых входов элемента 2 свертки,Ячейка 1 предназначена для выполнения элементарнои операции пересечения компоненты входного набора аргументов логической функции с компонентой одного куба кубического покрытияэтой Функции.Элемент 2 свертки (ЭС) предназначен для формирования результата вычисления логической Функции на соответствующих входных наборах ее аргументов.Ячейка 1 (Фиг.3) содержит Э-триггеры 24-26, элемент 27 неравнозначности и элемент И 28,ЭС 2 (фиг.3) содержит группу шКЗТ-триггеров 29, группу ш элементовИ 30 .с открытым коллектором, Е-разрядный регистр 31 и резистор 32,Структура работает следующим образом.Вычисление логической Функции вструктуре происходит в результатевыполнения ряда операций над минимальным кубическим покрытием (Р- илик-покрытием) этой Функции.Э-покрытие (Й-покрытие) функции- это представленная в кубическойФорме минимальная дизъюнктивная нормальная Форма (ХДНФ) прямой функции(инверснои Функции ф ) .ХДНФ прямой Функции ( (инверснойФункции ф ) содержит все наборы, накоторых Функция принимает значениелогической "1" (логического "0"). П-покрытие (К-покрытие) состоитиз ш (в) кубов, число которых равночислу импликант ИДНФ прямой функции(3) На фиг,4 величина сдвига в циклахобозначена с,После поступления на вход 4 первой группы 4 и информационных входов структуры последней компоненты1 набора Ь;= (1,11),На втором такте второго цикла результат выполнения операций (3) в ячейке 1 с координатами (1.1) и (1.2) записываются в первый ЭС 2, а результат выполнения операции (3) в ячейке 1 с координатами (2.1) записына следующем цикле на указанный вход 10поступает первая компонента 1+" набора Ь;,х=1-;и. вается во второй ЭС 2,После этого фронт выпЬлняемыхопераций перемещается к ячейке 1 скоординатами (3.1), (2.2) и (1.3),и, таким образом, продолжается волна 15 вычислений, бегущая вниз по матрицеячеек 1. В течение первых и циклов в ячейке 1 с координатами (1,1) по-очередно получены результаты выполнения следующих операций: 11 пс 1, ф 1 пс 1, ф 1 пс 1, ффф1 пс 1,л, (4)ь Тем самым на первом такте п-гоцикла закончено выполнение операциипересечения всехкомпонент набора Ь 1с компонентами куба й Эд-покрытия,Общий результат выполнения операциипересечения набора Ь.с кубом й,формируется в первом ЭС 2 на второмтакте п-го циклаНа первом такте (и+1)-го цикла,вячейке 1 с координатами (1,2) закончено выполнение операции пересечениявсех компонент набора Ь с компонентами куба Й 0 д-покрытия.На первом такте (п+в)-го циклав ячейке 1 с координатами (1,а) закончено выполнение операции пересечения всех компонент набора Ь с кубом с 1,п 0-покрытия. Общий Результатер врвыполнения операции пересечения набора Ь с кубом йл формируется в перЛ)вом ЭС 2 на втором такте (и+а)-гоцикла.На третьем такте (п+ш)-го циклана первом выходе Ь, группы 6 и ин"формационных Ы-разрядных выходовстоуктуры получен окончательныйрезультат выполнения операции пересечения набора Ь 1 с Р-покрытием,сформированный в соответствии ссоотношением (1),На выходе Ь в укаэанный моментвремени значение логической "1" (лоНа первом такте первого цикла рабо ты первый ЭС 2 устанавливаетсяв.сходное. состояние, а на втором тактепо первому входу 18 группы 18 а информационных входов результат (2)записывается в первый ЭС 2. 45На первом такте второго цикла работы компонента 1, набора Ь поступает на вход 12 ячейки 1 с координатами(1.2), а на входы 12 ячеек 1 с координатами (1.1) и (2.1) поступают компо250 кенты соответственно, и 1 (1 1 гПосле циклического сдвига в матри.це ячеек 1 на входы 13 ячейки 1 скоординатами (1.1), (1,2) и (2,1)поступают соответствующие компонен 55ты Вц -покрытия. В итоге на первомтакте второго цикла выполняются следующие, операции: Таким образом, в течение всего времени работы структуры на первую группу 4 п информационных входов структуры параллельно поступают20 входные наборы аргументов логической функции еПроцесс вычисления в матрице ячеек 1 начинается с активизации первой ячейки 1 первой строки, т.е. ячейки 1 с координатами (1.1) .На первом такте первого цикла ра, боты на вход 12 ячейки 1 поступает компонента 1 набора Ь 1, а также происходит циклический сдвиг сверху вниз по столбцам содержимого матрицы ячеек. Вследствие этого сдвига на вход 13 ячейки 1 с координатами (1,1) поступает компонента й Э-покрытия и на выходе 16 ячейки 1 получает ся результат выполнения операции1, пй (2)гического "О") соответствует значению логической функции ы Р -покПрытие которой записано в матрицу ячеек 1, на входном наборе Ь.При дальнейшей работе структуры 5на третьем такте (п+ш), (и+ш+1) (2 п+ш)-го циклов на выходах Ь ЬУ У,Ьгруппы 6 п информационныхК-разряднык выходов структуры поочередно получены результаты операции 10 пересечения с 01,-покрытием входных наборов соответственно Ь,ЬЬ,Значения логической Функции Ч) напоследующих вхбдных наборах аргументов появляются на каждом цикпе поо чередно на выходах группы 6 и информационных 1 с-разрядных выходов структуры в последовательности, показанной на Фиг.4.Значение Е определяется по формуле 20где означает округление до ближайшего целого в большую сторону.25Ячейка 1 работавт следующнм образом.На первом такте каждого цикла повходу 13 в В-триггеры 25 и 26 записи"вается очередная компонента д"(г " ) З 0.Ч ЧйО-покрытия (К,1-покрытия), а вЭ-триггер 24 - очередная компонепта1; набора Ь.1Поскольку значениями компонент кубов й,;- (г;) могут быть символы иэ 35алфавита О, 1, х, для представлениякомпоненты й," (г, ) в двоичном алЧзФавите необходимо два разряда (табл.2),Поэтому на первом такте. каждогоцикла в Э-триггер 25 и в Р-триггер 1026 записываются значения соотввтвтвеня и,ной; (г 1 ) иа; .(г;).После окончания записи соответствующей информации в Р-триггеры 24-26выполняется операция пересечения компоненты Й, (г, ) с компонентой 1;Поскольку значениями компоненты 13могут быть только символы О и 1,в ячейке 1 укаэанная операция пересечения выполняется согласно табл.З, 50В ячейке 1 реализована следующаяФункция Е;(1; пй пй )О(1; пс 1" пй" ) =.- Д а)р Е = (1;пг пг; )0(1 пг пг, )=11 Я 11- (1; г) пг." для К-покрытия,Функция Е, которая реализуется спомощью элемента 27 неравнозначностии элемента И 28, принимает значениелогической "1" (логического "О") приналичии пустого (непустого) пересечения компоненты 1 с компонентамии1 Вр (гв 11 я)В конце первого такта каждого цикла значение Функции реализуется навыходе 16 ячейки 1ЭС 2 работает следующим образом.На первом такте первого цикла посигналу, поступающему по входу 21первой группы 21 ш тактовых входов,первый КБТ-триггер 29 устанавливается в нулевое состояние.На первом такте каждого последующего цикла поочередно устанавливаются в нулевое состояние второй КБТтриггер 29, третий КБТ-триггер 29,ш-й КБТ-триггер 29.Через каждые и циклов КБТ-триг еры 29 снова установлены в нулевоесостояние в укаэанной последователь"ности.В Я -й КБТ-"триггер 29 -го ЭС 2в конце первого т.акта каждого циклапо группе 18 ш информационных входовпоступает результат операции пересечения компоненты 1 с компонентой д3 о(г" ,) от ячейки 1 с координатамиОнаходящейся в-й строке и в Ц -мстолбце матрицы ячеек 1 (= 1-;и,0 = 1-,ш),Указанный результат поступает на3-вход КЗТ-триггера 29, и при наличиипустого пересечения компоненты 1с компонентой .Й (г; К) соответствующий КЗТ- триггер 29 устанавливаетсяв единичное состояние, Б-вход КБТ-.триггера 29 является синхронным, изапись в КЗТ-триггер 29 осуществляется во втором такте каждого цикла поприходу тактового сигнала на вход 20. На втором такте и-го цикла в первом КЗТ-триггере 29 первого ЭС 2 формируется результат операции пересечения всех компонент набора Ь с компонентами куба Й 1 Рд -покрытия. При пустом (непустом) йересечении набора Ь, с кубом Й первый КБТ-триггер 29 первого ЭС 2 находится. в единичном (нулевом) состоянии.На втором такте (п+1)-го цнкпа во втором КБТ-триггере 29 первого ЭС 2 Формируется результат операции пересечения набора Ь с кубом д О -покрытия аналогичным образом.45 50 На втором такте (и+ш)-го циклав ш-м КБТ-триггере 29 первого ЭС 2формируется результат операции пере"сечения набора Ь 1 с кубом Эя-покры 5тия.Окончательный вывод о результатахоперации пересечения набора Ь, сО -покрытием согласно соотношения(1 т модно сделать после анализа Результатов операций пересечения набора Ь 1 со всеми кубами Р -покрытия,Поэтому до получения результатаоперации пересечения набора Ь кубом д. необходимо сохранять результаты операций пересечения набора Ьс предыдущими кубами Ря-покрытия.С этой целью на третьем такте и,(и+1)(и+ш)-го циклов по сигналам поступающим на Второй группе 2022;в тактовых входов, происходит передача инверсного содержимого соответственно первого КБТ-.триггера 29,второго КБТ-триггера 29ш-гоКБТ-триггера 29 через элементы И 30 25в первый триггер регистра 31. Приналичии в указанные моменты временихотя бы одного КБТ-триггера 29 в нулевом состоянии первый триггер регистра 31 по Б-входу устанавливается, в единичное состояние.Следовательно, на третьем такте(и+ш)-го цикла в первом триггеререгистра 31 Формируется значение логической Функции 10(Ь ) согласно со35отношения (1): единичное (нулевое)состояние первого триггера регистра31 свидетельствует о том, что навходном наборе Ь, Функция (у принимает единичное (нулевое) значение.Начиная с (и+1)-го и по 2 и-йцикл в первом КБТ"триггере 29 Форми-руется результат операции пересечения набора Ь,с кубом Й Эд -покрытия. На третьем такте 2 п-го циклаэтот результат из первого КБТ-триггера 29 передается через первый элемент И 30 в регистр 31.Если2 псп+ш - 1 (5)тогда на третьем такте 2 и-го циклаинверсное содержимое первого КБТ-триггера 29 записано во второй триггеррегистра 31,На третьем такте (2 п + 1)(2 п + ш - 1)-го циклов во второйтриггер регистра 31 записано инверсное содержимое соответственно второгош-. го КБТ-триггеров 29. Если неравенство (5) не выполня-. ется, тогда, начиная с 2 п-го цикла, информация от КБТ-триггеров 29 снова записывается в первый триггер регистра 31, поскольку в этом случае регистр 31 состоит из одного триггера. В общем случае регистр 31 содержит 1 с 0 с = - ) тригг.еров.Таким образом, в регистре 31 первого,ЭС 2 с интервалом в и циклов формируются значения Функции Элементы И 30 являются элементами с открытым коллектором, что позволяет вместе с резистором 32 реализовать на их выходах схему ИОНТАЖНОЕ ИЛИ.Работа ячеек 1 и ЭС 2 осуществляется под воздействием управляющих сигналов, На Фиг.5 показана последовательность появления управляющих сигналов на управляющих входах 8-11 после начала работы структуры до 3 х (ш + п - 1)-го такта работы структу-". ры для случая 1 с = 2,Формула из обр ет ения,1. Систолическая структура для вычисления логических функций, содержащая матрицу ячеек из и строк и ш столбцов, причем и информационньх входов первой группы структуры соединены с первыми информационными входами первых из ш последовательно соединенных ячеек каждой. строки матрицы, первые информационные выходы ячеек первой строки которой подключены к вторым информационным входам первых из ипоследовательно соединенных ячеек каждого столбца матрицы, отличающаяся тем, что, с целью повышения быстродействия при вычислении логических функций из последовательностей входных наборов аргументов, в нее введены п элементов свертки, 2 ш элементов ИЛИ, причем первые информационные выходы и вторые информационные входы всех ячеек являются двухразрядными, входы первого и второго разрядов каждого из ш информационных входов второй группы структуры соединены с первыми входами соответственно первого и второго элементов ИЛИ соответствующего столбца,1654809 Таблица 1 25 Компонента а Компонета Ь; О О х х Таблиц мееюеежиеееееееее е еачение компонент убов а (; )для оказател и е х Обозначениекомпонентпосле кодирования И1)ф,ю )11 Р,1 йчр аьг.) (г31 Й,) (воичн код компонент вторые входы первого и второго эле - ментов ИЛИ которого соединены с выходами одноименных разрядов первого информационного выхода и-й ячейки этого же столбца, выходы первого и второго элементов ИЛИ каждого столбца матрицы соединены соответственно с входами первого и второго разрядов второго информационного входа первой ячейки этого же столбца, выходы результата ячеек х-й (х 1-и) строки матрицы соединены с ш информационными входами группы х-го элемента свертки (х = 1-,и), 1 с-разрядные выходы которых являются К-разрядными1 щГ(1 с =-) выходами структуры, первый3 пи второй управляющие входы которой соединены соответственно с тактовыми входами ячеек матрицы и элементов свертки, ж управляющих входов первой .и второй групп структуры подключены к соответствующим ш тактовым входам одноименных групп элементов свертки, 1 с управляющих входов третьей группы структуры подключены к тактовым вхо- дам третьей группы элементов свертки.2, Структура по п,1, о т л и ч а .- ю щ а я с я тем, что каждая ячейка матрицы содержит три В-триггера, элемент неравнозначности и элемент И, выход которого является выходом ячей/ ки, первый информационный вход кото; рой соединен с .О-входом первого Исходное обозначение компонент ЪО-триггера, прямой выход которого со -единен с первым входом элемента не-,равнозначности и вторым информационным выходом ячейки, прямой выход второго О-триггера соединен с вторымвходом элемента неравнозначности и свходом первого разряда первого информационного выхода ячейки, прямойвыходтретьего Э-триггера соединен спервым входом элемента И и входомвторого разряда первого информационного выхода ячейки, выход элементанеравнозначности соединен с вторымвходом элемента И, Р-входы второгои третьего П-триггеров соединены свходами. соответственно первого и второго разрядов второго информационного входа ячейки, синхровходы всехО"триггеров соединены с тактовым входом ячейки.