ВЫСОКОПАРАЛЛЕЛЬНЫЙ СПЕЦПРОЦЕССОР ДЛЯ РЕШЕНИЯ ЗАДАЧ О ВЫПОЛНИМОСТИ БУЛЕВЫХ ФОРМУЛ Российский патент 1997 года по МПК G06F17/00 

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

Как известно, большинство практически важных дискретных и комбинаторных задач допускает решение с помощью некоторого процесса перебора.

Считается, что найти эффективное решение для большинства переборных задач (они называются NP-задачами) принципиально невозможно (Гэри М. Джонсон Д. Вычислительные машины и труднорешаемые задачи, М. Мир, 1982).

Среди NP-задач выделяется подкласс так называемых NP-полных задач. Все NP-задачи за полиномиальное время сводимы друг к другу. Таким образом, научившись эффективно решать какую-нибудь NP-полную задачу, можно эффективно решать все NP-задачи. Среди всех NP-полных задач выделяется задача о выполнимости булевых формул. Фундаментальная теорема Кука (Кук С.А. Сложность процедур вывода теорем, Кибернетический сборник, овая серия, Выпуск 12, М. Мир, 1975) устанавливают NP-полноту этой задачи, а NP-полнота всех остальных задач доказывается полиномиальным сведением к задаче о выполнимости булевых формул. Можно сказать, что эта задача естественным образом содержит в себе все NP-задачи.

Задача о выполнимости булевых формул формулируется следующим образом:
Дано: n булевых переменных x₁, x₂, x_n и С - множество мощности К дизъюнкций от этих переменных.

СD₁(x₁, x₂,x_n), D₂(x₁, x₂,x_n), D_к(x₁, x₂,x_n)}
Заметим, что некоторые дизъюнкции фактически могут зависеть от меньшего, чем n числа переменных. Каждая дизъюнкция имеет вид: e₁+e₂+.+e_n, где e_i либо тождественно равна 0 (если рассматриваемая дизъюнкция фактически не зависит от переменной х_i), либо является литералом от x_i. Каждый литерал от х_i имеет вид либо x_i, либо ^{^}x_i. Здесь и далее 0 логический нуль, "+" знак логического сложения, "^" знак логического отрицания.

Требуется определить, существуют ли выполняющие множество С наборы значений переменных x₁, x₂,x_n, т.е. такие наборы а₁, a₂,a_n значений этих переменных, что для любого j:
D_j(a₁, a₂,a_n) 1 a_j∈{0,1}. Здесь и далее 1 - логическая единица. Если такие наборы существуют, требуется найти хотя бы один из них.

Известен процессор, состоящий из арифметико-логического устройства (АЛУ), устройства управления (УУ), оперативной памяти (ОП), устройства ввода-вывода (УВВ) и постоянной памяти (ПП) (Каган Б.М. Электронные вычислительные машины и системы, М. Энергоатомиздат, 1985).

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

едостатком рассмотренной универсальной структуры процессора является невозможность ее использования при большой размерности задачи, т.к. число М машинных тактов, необходимых для решения задачи о выполнимости булевых формул от n булевых переменных, в общем случае равно К*2ⁿ, где К некоторое (достаточно большое) число. При n порядка нескольких десятков М становится неприемлемо большим.

Частично указанные недостатки устранены в высокопараллельном процессоре МРР (Massively Parallel Processor) фирмы Goodyear Aerospace (США), состоящем из: процессорной матрицы (ПМ), представляющей собой массив из 16384 процессорных элементов (ПЭ), каждый из которых является последовательно-поразрядным процессором, снабженным собственной локальной памятью объемом 1024 бита; устройства управления процессорной матрицей (УУПМ); переходной памяти (ПП) для буферизации и перекомпоновки данных; интерфейсной системы (ИС) для управления потоками данных, к которой подключается ведущая машина (HOST-машина) (СуперЭВМ. Аппаратная и программная реализация. Под. ред. С.Фернбаха, М. Радио и связь, 1991, гл.10, разделы 10.1 10.3, с. 215 - 246).

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

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

Технический результат поставленной задачи достигается тем, что в высокопараллельном спецпроцессоре для решения задачи о выполнимости булевых формул, состоящем из процессорной матрицы, устройства управления и интерфейса предлагается i-й (i 1,2n) адресный вход процессорной матрицы соединить с i-м управляющим выходом устройства управления, вход сброса процессорной матрицы соединить с выходом сброса устройства управления, выход процессорной матрицы соединить с сигнальным входом устройства управления, вход запуска которого соединить с выходом запуска интерфейса, j-й (j=1,m) выход чтения устройства управления соединить с j-м входом чтения интерфейса, p-й (p 1,2+2(log₂(L)} +2{ log₂(m)} +{log₂(n)}x} обозначает наименьшее целое, большее или равное х) вход загрузки устройства управления соединить с p-м выходом загрузки интерфейса, вход сброса устройства управления соединить с выходом сброса интерфейса, вход записи устройства управления соединить с выходом записи интерфейса, первый второй и третий выходы решения устройства управления соединены с первым, вторым и третьим входами решения интерфейса, соответственно, в состав процессорной матрицы включить идентичных блока записи и считывания, дешифратор адреса блока, входовой каскад элементов И, причем i₁-й (i₁ 1, 2n₁) вход дешифратора адреса блока сделать i₁-м адресным входом процессорной матрицы, k₁-й (k₁ 1,) выход дешифратора адреса блока соединить с разрешающим входом k₁-го блока записи и считывания, i₂-й (i₂ 1,2n₂) вход адреса строки каждого блока записи и считывания соединить с i₂+2n₁-м адресным входом процессорной матрицы, i₃-й (i₃ 1,2n₃) вход адреса столбца каждого блока записи и считывания соединить с i₃ + 2n₁+2n₂-м адресным входом процессорной матрицы, вход сброса каждого блока записи и считывания соединить с входом сброса процессорной матрицы, выход k₁-го (k₁ 1,) блока записи и считывания соединить с k₁-м входом входового каскада элементов И, выход которого соединить выходом процессорной матрицы, при этом каждый блок записи и считывания содержит матрицу запоминающих ячеек, дешифратор адреса строки, дешифратор адреса столбца, n₂-входовых каскадов элементов И, входовый главный каскад элементов И, 2n₂ ключей, выполненных в виде элементов И с двумя входами, причем k₂-й (k₂ 1,) выход дешифратора адреса строки соединить с первыми входами выборки всех запоминающих ячеек k₂-й строки матрицы запоминающих ячеек, k₃-й (k₃ 1,) выход дешифратора адреса столбца соединить с вторыми входами выборки всех запоминающих ячеек k₃-го столбца матрицы запоминающих ячеек, первый вход i₂-го (i₂ 1,2n₂) ключа соединить i₂-м входом адреса строки блока записи и считывания, второй вход каждого ключа соединить с разрешающим входом блока записи и считывания, i₂-й (i₂ 1,2n₂) вход дешифратора адреса строки соединить с выходом i₂-го ключа, i₃-й (i₃ 1,2n₃) вход дешифратора адреса столбца соединить с i₃-м входом адреса столбца блока записи и считывания, вход сброса каждой из запоминающих ячеек соединить с входом сброса блока записи и считывания, выход k₃-й запоминающей ячейки k₂-го ряда матрицы запоминающих ячеек соединить с k₃ входом k₂-го каскада элементов И, выход k₂-го каскада элементов И соединить с k₂-м входом входового главного каскада элементов И, выход которого соединить выходом блока записи и считывания, в состав каждой запоминающей ячейки включить запоминающий элемент и логический элемент И с двумя входами, причем первый и второй входы логического элемента И соединить с первым и вторым входами выборки запоминающей ячейки, выход элемента И соединить с входом записи единицы запоминающего элемента, вход записи нуля запоминающего элемента соединить с входом сброса запоминающей ячейки, прямой выход запоминающего элемента соединить выходом запоминающей ячейки; дешифраторы адресов блока, строк и столбцов выполнить в виде параллельных адресных дешифраторов, имеющих 2^N выходов и 2N адресных входов (N=n₁, n₂, n₃ для дешифраторов блока, адреса строки и адреса столбца соответственно), по одному независимому входу для нулевого и для единичного значения каждого двоичного разряда адреса, в состав 2^N-входового (N n₁, n₂, n₃) каскада элементов И включить 2^N-1 элементов И с двумя входами, расположенных на N уровнях, при этом на I-м (I 1, N) уровне расположить 2^N-I элементов, входы каскада с номерами 2k₁-1 и 2k₁ (k₁ 1,2^N-1) соединить с входами элемента И с номером k₁ первого уровня, выходы элементов И с номерами 2k_I-1 и 2k_I (k 1,2^N-I) I-го уровня соединить с входами элемента И номер k_I I+1-го уровня, выход одного элемента И N-го уровня сделать выходом всего каскада; в состав устройства управления включить блок выбора дизъюнкций, блок адресации, m+1 разрядный счетчик циклов по модулю 2^m+1, блок элементов И, m+1 разрядный регистр номера последнего цикла, блок ИЛИ-Е, блок переключателей, первый и второй определители порядка дизъюнкций, блок элементов ИЛИ, блок синхронизации, элемент ИЛИ с двумя входами, причем выход j-го (j 1,m+1) разряда регистра номера последнего цикла соединить с 2j-1-м входом блока элементов И, выход j-го разряда счетчика циклов соединить с 2j-входом блока элементов И с 2(m+1) входами, выход блока элементов И с 2(m+1) входами соединить с первым выходом решения устройства управления и с первым входом элемента ИЛИ, выход j-го (j 1,m) разряда счетчика циклов соединить с j-м управляющим входом блока выбора дизъюнкций, l-й (l 1,L), выход которого соединить с l-м входом блока переключателей и с l-м входом блока ИЛИ-Е, выход блока ИЛИ-Е соединить с вторым выходом решения устройства управления и с вторым входом элемента ИЛИ, l-й выход блока переключателей соединить с l-м входом первого определителя порядка дизъюнкций, L+l+1-й выход блока переключателей соединить с l-м, входом второго определителя порядка дизъюнкций, L+1-й выход блока переключателей соединить с L+1-м входом первого определителя порядка дизъюнкций, 2L+2-й выход блока переключателей соединить с L+1-м входом второго определителя порядка дизъюнкций, l-е выходы первого и второго определителей порядка дизъюнкций соединить, соответственно, с 2l+1-м и 2l-м входами блока элементов ИЛИ, l-й выход которого соединить с 1-м управляющим входом блока адресации, i-й (i 1,2n, n n₁ + n₂ + n₃), управляющий выход которого соединить с i-м управляющим выходом устройства управления, сигнальный выход первого определителя порядка дизъюнкций соединить с первым входом блока синхронизации, сигнальный выход второго определителя порядка дизъюнкций соединить с вторым входом блока синхронизации, третий вход блока синхронизации соединить с сигнальным входом устройства управления, четвертый вход блока синхронизации соединить с входом запуска устройства управления, пятый вход блока синхронизации соединить с выходом логического элемента ИЛИ, первый выход блока синхронизации соединить с третьим выходом решения устройства управления, второй выход блока синхронизации соединить с L+1-м входом блока переключателей, третий выход блока синхронизации соединить с L+2-м входом блока переключателей, четвертый выход блока синхронизации соединить со счетным входом счетчика циклов и с выходом сброса устройства управления, p₁-й вход (p₁ 1,log₂(m)}) загрузки регистра номера последнего цикла соединить с p₁-м входом загрузки устройства управления, q₂ 1,log₂(m)} +log₂(L)}+1) вход загрузки блока выбора дизъюнкций соединить с p₂-м (p₂ q₂+{log₂(m)}) входом загрузки устройства управления, q₃-й (q₃ 1,log₂(n)} +log₂(L)}+1), вход загрузки блока адресации соединить с p₃-м (p₃ q₃ + 2*{log₂(m)} +log₂(L)}+1) входом загрузки устройства управления, входы сброса блока выбора дизъюнкций, блока адресации, счетчика циклов и регистра номера последнего цикла соединить с входом сброса устройства управления, входы записи блока выбора дизъюнкций, блока адресации и регистра номера последнего цикла соединить с входом записи устройства управления, в состав блока выбора дизъюнкций включить m инверторов, дешифратор адреса схемы, дешифратор адреса ячейки и L схем выбора, причем j-й (j 1,m) управляющий вход блока выбора дизъюнкций соединить с 2j-1-ми управляющими входами всех схем выбора и с входом j-го и инвертора, выход которого соединить с 2j-ми управляющими входами всех схем выбора, выход l-й (l=1,L) схемы выбора соединить с l-м выходом блока выбора дизъюнкций, q₄-й (q₄ 1,log₂(L)}) вход загрузки блока выбора дизъюнкций соединить с q₄-м входом дешифратора адреса схемы, 1-й выход которого соединить с разрешающим входом 1-й схемы выбора, q₅-й (q₅log₂(L)}+1,log₂(m)}+{log₂(L)}+1), вход загрузки блока выбора дизъюнкций соединить с q₅-{log₂(L)}-м входом дешифратора адреса ячейки, j₁-й (j₁ 1,2m) выход которого соединить с j₁-ми входами выборки всех схем выбора, входы сброса и записи каждой схемы выбора соединить с входами сброса и записи блока выбора дизъюнкций, в состав каждой схемы выбора включить 2m запоминающих элементов, 2m элементов И с двумя входами, 2m элементов И с тремя входами, m элементов ИЛИ с тремя входами, элемент И-Е, блок элементов И, причем в каждой схеме выбора прямой выход 2j-1-го (j=1,m) запоминающего элемента соединить с первым входом j-го элемента ИЛИ, прямой выход 2j-го запоминающего элемента соединить с первым входом 2j-1-го элемента И с двумя входами, инверсный выход 2j-го запоминающего элемента соединить с первым входом 2j-го элемента и с двумя входами, второй вход 2j-1-го элемента И с двумя входами соединить с 2j-1-м управляющим входом схемы выбора, второй вход 2j-го элемента И с двумя входами соединить с 2j-м управляющим входом схемы выбора, выходы 2j-1-го и 2j-го элементов И с двумя входами соединить с вторым и третьим входами j-го элемента ИЛИ, выход j-го элемента ИЛИ соединить с j-м входом блока элементов И, выход которого соединить с выходом схемы выбора, прямые выходы первого и второго запоминающих элементов соединить с первым и вторым входами элемента И-Е, выход которого соединить с m+1-м входом блока элементов И, вход записи единицы j₁-го (j₁ 1,2m) запоминающего элемента соединить с выходом j₁-го элемента И с тремя входами, входы записи нуля всех запоминающих элементов соединены с входом сброса схемы выбора, первый вход j₁-го элемента И с тремя входами соединить с j₁-м входом выборки схемы выбора, вторые входы всех элементов И с тремя входами соединить с разрешающим входом схемы выбора, третьи входы всех элементов И с тремя входами соединить с входом записи схемы выбора; в состав блока адресации включить дешифратор адреса схемы, дешифратор адреса ячейки, n n₁ + n₂ + n₃ схем адресации, причем l-e (l 1,L) управляющие входы всех схем адресации соединить с l-м управляющим входом блока адресации, первый и второй выходы i-й (i 1,n) схемы адресации соединить с 2i-1-м и 2i-м выходами блока, q₆-й (q₆ 1,log₂(n)}) вход загрузки блока адресации соединен с q₆-м входом дешифратора адреса схемы, i-й выход которого соединить с разрешающим входом i-й схемы выбора, q₇-й (q₇log₂(n)}+1,log₂(n)}+log₂(L)}+1), вход загрузки блока адресации соединить с q₇-{log₂(n)}-м входом дешифратора адреса ячейки, l₁-й (l₁ 1,2L), выход которого соединить с l₁-ми входами выборки всех схем адресации, входы сброса и записи каждой схемы адресации соединить с входами сброса и записи блока адресации, в состав каждой схемы адресации включить 2L запоминающих элементов, два блока элементов ИЛИ с L входами каждый, 2L ключей, выполненных в виде элементов И с двумя входами, 2L элементов И с тремя входами, причем прямые выходы 2l-1-го и 2l-го (l=1,L) запоминающих элементов, соединить с первыми входами 2l-1-го и 2l-го ключей, вторые входы 2l-1-го и 2l-го ключей соединить с l-м управляющим входом схемы адресации, выходы всех нечетных ключей соединить с входами первого блока элементов ИЛИ, выходы всех четных ключей соединить с входами второго логического блока ИЛИ, выходы первого и второго логических блоков ИЛИ соединить с первым и вторым выходами схемы адресации, вход записи единицы l₁-го (l₁ 1, 2L) запоминающего элемента соединить с выходом l₁-го элемента И с тремя входами, входы записи нуля всех запоминающих элементов соединить с входом сброса схемы адресации, первый вход l₁-го элемента И с тремя входами соединить с l₁-м входом выборки схемы адресации, вторые входы всех элементов И с тремя входами соединены с разрешающим входом схемы адресации, третьи входы всех элементов И с тремя входами соединить с входом записи схемы адресации.

В состав блока синхронизации предлагается включить инвертор, два логических элемента И с двумя входами, RS-триггер, три логических элемента ИЛИ с двумя входами, генератор тактовых импульсов, Т-триггер, две линии задержки, причем первый и второй входы блока соединить с первым и вторым входами первого элемента ИЛИ, третий вход блока соединить с вторым входом второго элемента И, первый вход которого соединить с выходом Q RS-триггера, выход первого элемента ИЛИ через первую линию задержки соединить с первым входом первого элемента И, третий вход блока через инвертор соединить с вторым входом первого элемента И, выход первого элемента И соединить с первым выходом блока и с первым входом третьего элемента ИЛИ, выход второго элемента И соединить с вторым входом второго элемента ИЛИ, первый вход которого соединить с четвертым входом блока синхронизации, выход второго элемента ИЛИ соединить с четвертым выходом блока, со счетным входом Т-триггера, с входом R RS-триггера и через вторую линию задержки на половину такта с входом S RS-триггера, выход Т-триггера соединить с третьим выходом блока, четвертый вход блока соединить с входом запуска генератора, выход генератора соединить с вторым выходом блока, пятый вход блока соединить с вторым входом третьего элемента ИЛИ, выход которого соединить с входом остановки генератора.

В состав определителя порядка дизъюнкций предлагается включить L ключей с одним управляющим входом, управляющим выходом, тактовым входом и тактовым выходом, при этом управляющий вход l-го (l 1,L) ключа соединить с l-м входом определителя, управляющий выход l-го ключа соединить с управляющим выходом определителя, тактовый вход первого ключа соединить с L+1-м входом определителя, тактовый вход l-го ключа (l 2,L) соединить с тактовым выходом l+1-го ключа, тактовый выход L-го ключа соединить с сигнальным выходом определителя, в состав каждого из ключей включить RS-триггер, два элемента И с двумя входами каждый, линию задержки на половину машинного такта, при этом управляющий вход ключа соединить с входом S RS-триггера, выход Q RS-триггера соединить с вторым входом второго элемента И, выход RS-триггера соединить с вторым входом первого элемента И, первые входы элементов И соединить с тактовым входом ключа, выход первого элемента И соединить с тактовым выходом ключа, выход второго элемента И соединить с управляющим выходом ключа и через линию задержки с входом R RS-триггера.

В состав блока переключателей с L+2 входами и 2(L+1) выходами предлагается включить инвертор и 2(L+1) ключ, выполненный в виде логического элемента И с двумя входами, причем L+2-й вход блока соединить с первыми входами всех ключей с номерами большими L+1 и с входом инвертора, выход которого соединить с первыми входами всех ключей с номерами, меньшими или равными L+1, l-й (l 1,L, L+1), вход блока соединить с вторыми входами l-го и L+l+l-го ключей, выход l-го ключа (l=1,2L+1, l₁≠L+1)) соединить с l-м выходом блока, выход 2L+1-го ключа соединить с L+2-м выходом блока, выход 2L+2-го ключа соединить с L+1-м выходом блока.

В состав блока элементов ИЛИ с 2L входами и L выходами предлагается включить L элементов ИЛИ с двумя входами, причем 2l-1-й (l 1,L) вход блока соединить с первым входом l-го элемента ИЛИ, 2l-й (l 1,L) вход блока соединить с вторым входом l-го элемента ИЛИ, выход которого соединить с l-м выходом блока.

Логический блок ИЛИ с L входами предлагается выполнить в виде p-уровневого (p [log₂L]) каскада элементов ИЛИ, причем, на первом уровне расположить [L/2] элементов ([] обозначает целую часть числа), на q-м (q 1,p) уровне расположить s(q) элементов ИЛИ, при этом s(q+1)=[s(q)/2] все кроме последних элементы ИЛИ всех уровней должны иметь по два входа, последний элемент первого уровня должен иметь два входа, если L четное, и три входа, если L нечетное, последний элемент q + 1-го уровня должен иметь два входа, если s(q) четное, и три входа, если s(q) нечетное, 2l₁-й и 2l₁-1-й (l₁ 1,[L/2]) входы блока соединить с входами L₁-го элемента ИЛИ первого уровня, если L нечетно, то последний вход блока соединить с третьим входом последнего элемента ИЛИ первого уровня, выходы 2l_q и 2l_q-1-го (l_q 1,[s(q)/2] элементов ИЛИ q-го уровня соединить с входами l_q-го элемента q+1-го уровня, если s(q) нечетно, то выход последнего элемента q-го уровня соединить с третьим входом последнего элемента q+1-го уровня, выход элемента последнего уровня соединить с выходом блока.

Логический блок И с N входами (N L+1) предлагается выполнить в виде p-уровневого (p [log₂ N] каскада элементов И, причем, на первом уровне расположить [N/2] элементов ([ обозначает целую часть числа), на q-м (q 1,p) уровне расположить s(q) элементов И, при этом s(q+1)=[s(q)/2] все кроме последних элементы И всех уровней должны иметь по два входа, последний элемент первого уровня должен иметь два входа, если N четное, и три входа, если N нечетное, последний элемент q + 1-го уровня должен иметь два входа, если s(q) четное, и три входа, если s(q) нечетное, 2l₁-й и 2l₁-1-й (l 1,[N/2] входы блока соединить с входами 1₁-го элемента И первого уровня, если N нечетно, то последний вход блока соединить с третьим входом последнего элемента И первого уровня, выходы 2l_q-го и 2l_q-1-го (l 1,[s(q)/2]) элементов ИЛИ q-го уровня соединить с входами l_q-го элемента q+1-го уровня, если s(q) нечетно, то выход последнего элемента q-го уровня соединить с третьим входом последнего элемента q+1-го уровня, выход элемента последнего уровня соединить с выходом блока.

В состав логического блока ИЛИ-Е с L входами предлагается включить логический блок ИЛИ c L входами и инвертор, при этом выход логического блока ИЛИ с L входами соединить с входом инвертора, выход которого соединить с выходом блока ИЛИ-Е.

а фиг.1 изображена функциональная схема спецпроцессора для решения задач о выполнимости булевых формул; на фиг.2 функциональная схема процессорной матрицы; на фиг.3 функциональная схема блока параллельной записи и считывания; на фиг.4 функциональная схема запоминающей ячейки; на фиг.5 - функциональная схема параллельного адресного дешифратора с 2n входами и 2n выходами (n= 2); на фиг.6 функциональная схема 2^N-входового каскада элементов И; на фиг. 7 функциональная схема устройства управления; на фиг.8 - функциональная схема блока выбора дизъюнкций; на фиг.9 функциональная схема схемы выбора; на фиг. 10 функциональная схема блока адресации; на фиг.11 - функциональная схема схемы адресации; на фиг.12 функциональная схема блока синхронизации; на фиг. 13 функциональная схема определителя порядка дизъюнкций; на фиг.14 функциональная схема ключа определителя порядка дизъюнкций; на фиг.15 функциональная схема блока переключателей; на фиг.16 - функциональная схема блока элементов ИЛИ устройства управления; на фиг.17 - функциональная схема логического блока элементов ИЛИ; на фиг.18 - функциональная схема логического блока элементов И; на фиг. 19 функциональная схема логического блока ИЛИ-Е.

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

Процессорная матрица 1 имеет 2n адресных входов 4, вход 5 сброса и один выход 6.

Устройство управления имеет вход запуска 7, сигнальный вход 8, 2+2{ log₂(L)}+2{log₂(m)} +{log₂(n)}входов 9 загрузки (гдеx} обозначает наименьшее целое большее или равное х), вход 10 сброса, вход 11 записи, 2n управляющих выходов 12, три выхода решения 13, 14, 15, m выходов чтения 16 и выход сброса 17.

При этом i-й (i 1,2n) адресный вход 4_i процессорной матрицы 1 соединен с i-м управляющим выходом 12_i устройства 2 управления, вход 5 сброса процессорной матрицы 1 соединен с выходом 17 сброса устройства 2 управления, выход 6 процессорной матрицы 1 соединен с сигнальным входом 8 устройства 2 управления.

Вход 7 запуска устройства 2 управления соединен с выходом 18 запуска интерфейса 3, j-й (j 1,m) выход 16_j чтения устройства 2 управления соединен с j-м входом 19_j чтения интерфейса 3, p-й (p 1,2+2{log₂(L)}+2{log₂(m)}+{ log₂(n)} ), вход 9_p загрузки устройства 2 управления соединен с p-м выходом 20_p загрузки интерфейса 3. Вход 10 сброса устройства 2 управления соединен с выходом 21 сброса интерфейса 3, вход 11 записи устройства 2 управления соединен с выходом 22 записи интерфейса 3, первый 13, второй 14 и третий 15 выходы решения устройства 2 управления соединены с первым 23, вторым 24 и третьим 25 входами решения интерфейса, соответственно.

Процессорная матрица 1 (фиг.2) содержит:
идентичных блоков 26 записи и считывания с входами 27 адреса строки, входами 28 адреса столбца, разрешающим входом 29, входом сброса и одним выходом 30;
дешифратор 31 адреса блока с 2n₁ входами и выходами 32;
-входовый каскад 33 элементов И.

При этом i₁-й (i₁ 1,2n₁) вход дешифратора 31 адреса блока является i₁-м адресным входом устройства 1 параллельной записи и считывания, k₁-й (k₁ 1,) выход дешифратора 31 адреса блока соединен с разрешающим входом 29 k₁-го блока .

i₂-й (i₂ 1,2n₂) вход адреса строки каждого блока 26 записи и считывания соединен с i₂+2n₁-м адресным входом устройства 1 параллельной записи и считывания.

i₃-й (i₃ 1,2n₃) вход адреса столбца каждого блока 26 соединен с i₃+2n₁+2n₂-м адресным входом устройства параллельной записи и считывания 1.

Вход сброса каждого блока 26 соединен с входом сброса 5 процессорной матрицы 1.

Выход 30 k₁-го (k₁ 1,) блока 26 соединен с k₁-м входом - входового каскада 33 элементов И, выход которого является выходом 6 процессорной матрицы 1.

Каждый блок 26 записи и считывания (фиг.3) содержит:
матрицу запоминающих ячеек 35;
дешифратор 36 адреса строки с 2n₂ входами 37 и выходами 38;
дешифратор 39 адреса столбца с 2n₃ входами 40 и выходами 41;
n₂-входовых каскадов 42 элементов И
-входовый главный каскад 43 элементов И;
2n₂ ключей 44, выполненных в виде элементов И с двумя входами.

При этом k₂-й (k₂ 1,) выход дешифратора 36 адреса строки соединен с первыми входами 45 выборки всех запоминающих ячеек k₂-й строки матрицы запоминающих ячеек, k₃-й (k₃ 1,) выход дешифратора 39 адреса столбца соединен с вторыми входами 46 выборки всех запоминающих ячеек k₃-го столбца матрицы запоминающих ячеек.

Первый вход i₂-го (i₂ 1,2n₂) ключа соединен с i₂-м входом адреса строки блока, второй вход каждого ключа 44 соединен с разрешающим входом 29 блока.

i₂-й (i₂= 1,2n₂) вход дешифратора 36 адреса строки соединен с выходом i₂-го ключа , i₃-й (i₃ 1,2n₃) вход дешифратора 39 адреса столбца соединен с i₃-м входом адреса столбца блока.

Вход 47 сброса каждой из запоминающих ячеек соединен с входом 34 сброса блока 26 записи и считывания, выход k₃-й запоминающей ячейки k₂-го ряда матрицы запоминающих ячеек соединен с k₃-м входом k₂-го каскада элементов И, выход k₂-го каскада элементов И соединен с k₂-м входом -входового главного каскада 43 элементов И, выход которого является выходом блока 26 записи и считывания.

Каждая запоминающая ячейка 35 (фиг.4) содержит:
запоминающий элемент 50;
логический элемент И 51 с двумя входами.

При этом первый и второй входы логического элемента И 51 соединены с первым 45 и вторым 46 входами выборки запоминающей ячейки 35, выход элемента И соединен с входом записи единицы запоминающего элемента 50, вход записи нуля запоминающего элемента 50 соединен с входом 47 сброса запоминающей ячейки 35. Прямой выход запоминающего элемента является выходом запоминающей ячейки 35.

Дешифраторы адресов блока, строк и столбцов (фиг.5) выполнены в виде параллельных адресных дешифраторов, имеющих 2^N выходов 52 и 2N адресных входов 53 (N n₁, n₂, n₃ для дешифраторов блока, адреса строки и адреса столбца соответственно), по одному независимому входу для нулевого и для единичного значения каждого двоичного разряда адреса.

2^N-входовый (фиг. 6) (N n₁, n₂, n₃) каскад элементов И содержит 2^N-1 элементов И 54 с двумя входами, расположенных на N уровнях, при этом на I-м (I= 1,N) уровне имеется 2^N-I элементов, входы каскада (k₁ 1, 2^N-1) соединены с входами элемента И первого уровня, выходы элементов И (k₁ 1,2^N-I) I-го уровня соединены с входами элемента И I+1-го уровня, выход одного элемента И 54_N,1 N-го уровня является выходом 56 всего каскада.

Устройство 2 управления содержит (фиг.7):
блок 57 выбора дизъюнкций с m управляющими входами 58, входом 59 сброса, входом 60 записи,log₂(m)}+{log₂(L)}+1 входом 61 загрузки и L выходами 62;
блок 63 адресации с m управляющими входами 64, входом 65 сброса, входом 66 записи,log(L)}+{log(n)}+1 входом 67 загрузки и 2n выходами 68;
m+1-разрядный счетчик 69 циклов по модулю 2^m+1 c m+1 выходом 70 и счетным входом 71;
блок элементов И 72 с 2(m+1) входами 73 и выходом 74;
m+1-разрядный регистр 75 номера последнего цикла с m+1 выходом 76, log₂(m)} входами 77 загрузки, входом записи и входом сброса;
блок ИЛИ-Е 78 с L входами 79 и выходом 80;
блок 81 переключателей с L+2 входами 82 (l=1,L), 83, 84 и 2(L+1) выходом 85;
первый 86 и второй 87 определители порядка дизъюнкций c L+1 входом 88, L управляющими выходами 89, сигнальным выходом 90;
блок 91 элементов ИЛИ с 2L входами 92 и L выходами 93;
блок 94 синхронизации с пятью входами 95-99 и четырьмя выходами 100-103;
элемент ИЛИ 104 с двумя входами.

При этом выход 76_j j-го (j 1,m+1) разряда регистра 75 номера последнего цикла соединен с 2j-1-м входом 73_2j-1 блока элементов И 72. Выход 70_j j-го разряда счетчика 69 циклов соединен с 2j-м входом 73_2j блока элементов И 72.

Выход 74 логического блока И 72 соединен с первым выходом 13 решения устройства 2 управления и с первым входом элемента ИЛИ 104.

Выход 70_j j-го (j 1,m) разряда счетчика циклов 69 соединен с j-м управляющим входом 58_j блока 57 выбора дизъюнкций, l-й (l 1,L) выход 62_l которого соединен с l-м входом 82 блока 81 переключателей и с l-м входом 79_l блока ИЛИ-Е 78.

Выход 80 блока ИЛИ-Е 78 соединен со вторым выходом 14 решения устройства 2 и со вторым входом элемента ИЛИ 104.

l-й (l 1.L) выход 85_l блока 81 переключателей соединен с l-м входом 88_l первого определителя 86 порядка дизъюнкций. L+l+1-й выход 85_L+l+1 блока 81 переключателей соединен с l-м входом 88_l второго определителя 87 переключателей соединен с L+1-м входом 88_L+1 первого определителя 87 порядка дизъюнкций. 2L+2-й выход 85_2L+2 блока 81 переключателей соединен с L+1-м входом 88 второго определителя 86 порядка дизъюнкций.

l-е выходы 89_l первого 86 и второго 87 определителей порядка дизъюнкций соединены соответственно с входами 92_2l-1 и 92_2l блока 91 элементов ИЛИ, l-й выход 93_l которого соединен с l-м управляющим входом 64_l блока 63 адресации 63, i-й (i 1,2n n n₁ + n₂ + n₃) выход 68_i которого соединен i-м управляющим выходом 12_i устройства 2 управления.

Сигнальный выход 90 первого определителя 86 порядка дизъюнкций соединен с первым входом 95 блока 94 синхронизации, сигнальный выход 90 второго определителя 87 порядка дизъюнкций соединен со вторым входом 96 блока 94 синхронизации.

Третий вход 97 блока 94 синхронизации соединен с сигнальным входом 8 устройства 2 управления.

Четвертый вход 98 блока 94 синхронизации соединен с входом 7 запуска устройства 2 управления.

Пятый вход 99 блока 94 синхронизации соединен с выходом логического элемента ИЛИ 104.

Первый выход 100 блока 94 синхронизации соединен с третьим выходом 15 решения устройства 2 выбора адресов ячеек.

Второй выход 101 блока 94 синхронизации соединен с L+1-м входом 83 блока 81 переключателей.

Третий выход 102 блока 94 синхронизации соединен с L+2-м входом 84 блока 81 переключателей.

Четвертый выход 103 блока синхронизации 94 соединен со счетным входом 71 счетчика 69 циклов и с выходом 17 сброса устройства 2 управления.

p₁-й вход (p₁ 1,log₂(m)}) загрузки регистра 75 номера последнего цикла соединен с p₁-м входом загрузки устройства 2 выбора адресов ячеек. q₂-й (q₂ 1,log₂(m)}+{log₂(L)+1) вход загрузки блока 57 выбора дизъюнкций соединен с p₂-м (p₂ q₂ +log₂(m)}) входом загрузки устройства 2 управления, q₃-й (q₃ 1,log₂(n)}+{log₂(L)}+1) вход загрузки блока 63 адресации соединен с p₃-м (p₃ q₃+2*{log₂(m)}+{log₂(L)}+1) входом загрузки устройства 2 выбора адресов ячеек.

Входы сброса блока 57 выбора дизъюнкций, блока 63 адресации, счетчика 69 циклов и регистра 75 номера последнего цикла соединены со входом 10 сброса устройства 2 управления.

Вход 60 записи блока 57 выбора дизъюнкций, вход 66 записи блока 63 адресации и вход записи регистра 75 номера последнего цикла соединены со входом 11 записи устройства 2 управления.

Блок 57 выбора дизъюнкций (фиг.8) содержит:
m инверторов 105;
дешифратор 106 адреса схемы сlog₂(L)} входами 107 и L выходами 108;
дешифратор 109 адреса ячейки сlog₂(m)}+1 входом 110 и 2m выходами 111;
L схем 112 выбора с 2m управляющими входами 113, 2m входами 114 выборки, разрешающим входом 115, входом 116 сброса, входом 117 записи и одним выходом.

При этом j-й (j 1,m) управляющий вход 58_j блока 57 выбора дизъюнкций соединен с 2j-1-ми управляющими входами 113_2j-1 всех схем 112 выбора и с входом j-го инвертора 105_j, выход которого соединен с 2j-ми управляющими входами 113_2j всех схем 112 выбора.

Выход l-й (l 1,L) схемы 112_l выбора соединен с l-м выходом 62_l блока 57 выбора дизъюнкций.

q₄-й (q₄ 1,log₂(L)}) вход загрузки блока 57 выбора дизъюнкций соединен с q₄-м входом дешифратора 106 адреса схемы, l-й выход 108_l которого соединен с разрешающим входом 115 l-й схемы 112_l выбора, q₅-й (q₅ log₂(L)} +1,log₂(m)}+{log₂(L)}+1) вход загрузки блока 57 выбора дизъюнкций соединен с q₅-{log₂(L)}-м входом дешифратора 109 адреса ячейки, j-й (j 1,2m) выход 111 которого соединен с j-ми входами 114_j выборки всех схем 112 выбора. Входы сброса 116 и записи 117 каждой схемы 112 выбора соединены с входами сброса 59 и записи 60 блока.

Каждая схема выбора 112 (фиг.9) содержит:
2m запоминающих элементов 118;
2m элементов И 119 с двумя входами 120, 121;
2m элементов И 122 с тремя входами 123, 124, 125;
m элементов ИЛИ 126 с тремя входами 127, 128, 129;
один элемент И-Е 130 с двумя входами 131, 132;
блок элементов И 133 с m+1 входом 134.

При этом прямой выход 135 2j-1-го (j= 1,m) запоминающего элемента 118_2j-1 соединен с первым входом 127 j-го элемента ИЛИ 126_j, прямой выход 135 2j-го запоминающего элемента 118_2j соединен с первым входом 120 2j-1-го элемента И 119_2j. Инверсный выход 136 2j-го запоминающего элемента 118_2j соединен с первым входом 120 2j-го элемента И 119_2j.

Второй вход 121 2j-1-го элемента И 119_2j-1 соединен с 2j-1-м управляющим входом 113_2j-1 схемы 112 выбора. Второй вход 121 2j-го элемента И 119_2j соединен с 2j-м управляющим входом 113_2j схемы 112 выбора.

Выходы 2j-1-го 119_2j-1 и 2j-го 119_2j элементов И соединены со вторым 128 и третьим 129 входами j-го элемента ИЛИ 126.

Выход j-го элемента ИЛИ 126_j соединен с j-м входом 134_j логического блока И 133, выход которого соединен с выходом схемы 112 выбора.

Прямые выходы 135 первого 118₁ и второго 118₂ запоминающих элементов соединены с первым 131 и вторым 132 входами элемента И-Е 130, выход которого соединен с m+1-м входом логического блока И 133.

Вход записи единицы 137 j₁-го (j₁ 1,2m) запоминающего элемента 118_j1 соединен с выходом j₁-го элемента И 122_j1. Входы записи нуля 138 всех запоминающих элементов 118 соединены с входом сброса 116 схемы 112 выбора.

Первый вход 123 j₁-го элемента И 122_j1 соединен с j₁-м входом выборки 114_j1 схемы 112 выбора, вторые входы 124 всех элементов И 122 соединены с разрешающим входом 115 схемы 112 выбора, третьи входы 125 всех элементов И 122 соединены с входом записи 117 схемы 112 выбора.

Блок 63 адресации (фиг.10) содержит:
дешифратор 139 адреса схемы сlog₂(n)} входами 140 и n n₁ + n₂ + n₃ выходами 141;
дешифратор 142 адреса ячейки сlog₂(L)}+1 входом 143 и 2L выходами 144;
n схем 145 адресации с L управляющими входами 146, 2L входами 147 выборки, разрешающим входом 148, входом сброса 149, входом записи 150 и двумя выходами 151, 152.

При этом l-е (l 1,L) управляющие входы 146_l всех схем 145 адресации соединены с l-м управляющим входом 64_l блока 63 адресации.

Первый 151 и второй 152 выходы i-й (i 1,n) схемы 145 адресации соединены с 2i-1-м и 2i-м выходами 68_2i-1 и 68_2i блока 63, q₆-й (q₆ 1,log₂(n)}) вход загрузки блока 63 адресации соединен с q₆-м входом дешифратора 139 адреса схемы, i-й выход 141_i которого соединен с разрешающим входом 148 i-й схемы 145_i адресации. q_q7-й (q₇log₂(n)}+1,log₂(L)}+1) вход загрузки блока 63 адресации соединен с q₇-{log₂(n)}-м входом дешифратора 142 адреса ячейки, l₁-й (l₁ 1,21) выход которого соединен с l₁-ми входами выборки всех схем 145 адресации. Входы сброса 149 и записи 150 каждой схемы 145 адресации соединены с входами сброса 65 и записи 66 блока 63.

Каждая схема 145 адресации (фиг.11) содержит:
2L запоминающих элементов 153;
два логических блока ИЛИ 154 с L входами 155 каждый;
2L ключей 156, выполненных в виде элементов И с двумя входами 157, 158;
2L элементов И 159 с тремя входами 160, 161, 162.

При этом прямые выходы 163 2l-1-го 153_2l-1 и 2l-го 153_2l (l 1,L) запоминающих элементов соединены с первыми входами 157 2l-1-го 156_2l-1 и 2l-го 156_2l ключей соответственно. Вторые входы 158 2l-1-го 156_2l-1 и 2l-го 156_2l ключей соединены с l-м управляющим входом 146_l схемы 145 адресации.

Выходы всех нечетных ключей 156 соединены с входами 155 первого логического блока ИЛИ 154, выходы всех четных ключей 156 соединены с входами 155 второго логического блока ИЛИ 154. Выходы первого 154 и второго 154 логических блоков ИЛИ соединены с первым 151 и вторым 152 выходами схемы 145 адресации.

Вход 164 записи единицы l₁-го (l 1,2L) запоминающего элемента соединен с выходом i-го элемента И с тремя входами, входы 165 записи нуля всех запоминающих элементов 153 соединены с входом сброса 149 схемы 145 адресации.

Второй вход 161 l₁-го элемента И соединен с l₁-м входом выборки схемы 145 адресации, первые входы 160 всех элементов И 159 соединены с разрешающим входом 148 схемы 145 адресации, третьи входы 162 всех элементов И 159 соединены с входом 150 записи схемы 145 адресации.

Блок 94 синхронизации содержит (фиг.12):
инвертор 166;
два логических элемента И 167, 168 с двумя входами 169, 170 и 171, 172 каждый;
RS-триггер 173;
три логических элемента ИЛИ 174, 175, 176 с двумя входами 177, 178; 179, 180 и 181, 182 каждый;
генератор тактовых импульсов 183 с входом запуска 184 и входом остановки 185;
Т-триггер 186 со счетным входом 187;
две линии задержки 188 и 189.

При этом, первый 95 и второй 96 входы блока 94 соединены с первым 177 и вторым 178 входами первого элемента ИЛИ 174, третий вход 97 соединен со вторым входом 172 второго элемента И 168, первый вход 171 которого соединен с выходом Q RS-триггера 173.

Выход первого элемента ИЛИ 174 через первую линию задержки 188 соединен с первым входом 169 первого элемента И 167.

Третий вход 97 блока 94 через инвертор 166 соединен с вторым входом 170 первого элемента И 167. Выход первого элемента И 167 соединен с первым выходом 100 блока 94 и с первым входом 181 третьего элемента ИЛИ 176.

Выход второго элемента И 168 соединен со вторым входом 180 второго элемента ИЛИ 175, первый вход 179 которого соединен с четвертым входом 98 блока синхронизации 94.

Выход второго элемента ИЛИ 175 соединен с четвертым выходом 103 блока 94, со счетным входом 187 Т-триггера 186, с входом R RS-триггера 173 и через вторую линию задержки 189 с входом S RS-триггера 173.

Выход Т-триггера 186 соединен с третьим выходом 102 блока 94.

Четвертый вход 98 блока 94 соединен с входом 184 запуска генератора 183. Выход генератора 183 соединен с вторым выходом 101 блока 94.

Пятый вход 99 блока 94 соединен с вторым входом 182 третьего элемента ИЛИ 176, выход которого соединен с входом 185 остановки генератора 183.

Каждый из двух определителей порядка дизъюнкций 86, 87 (фиг.13) содержит L ключей 190 с управляющим входом 191, управляющим выходом 192, тактовым входом 193 и тактовым выходом 194.

При этом, управляющий вход 191 l-го (l 1,L) ключа 190_l соединен с l-м входом 88_l определителя. Управляющий выход 192 l-го ключа 190_l соединен с l-м управляющим выходом 89_l определителя. Тактовый вход 193 первого ключа 190 соединен с L+1-м входом 88_L+1 определителя. Тактовый вход 193 l₁-го ключа (l₁ 2,L) соединен с тактовым выходом 194 l₁-1-го ключа . Тактовый выход 194 L-го ключа 190 соединен с сигнальным выходом 90 определителя.

Каждый из ключей 190 содержит (фиг.14):
RS-триггер 195;
два элемента И 196, 197 с двумя входами 198, 199 и 200, 201 соответственно;
линию 202 задержки на половину машинного такта.

При этом, управляющий вход 191 ключа соединен с входом S RS-триггера 195. Выход Q RS-триггера 195 соединен с вторым входом 201 второго элемента И 197. Выход RS-триггера 195 соединен с вторым входом 199 первого элемента И 196. Первые входы 198 и 200 элементов И 196 и 197 соединены с тактовым входом 193 ключа.

Выход первого элемента И 196 соединен с тактовым выходом 194 ключа. Выход второго элемента И 197 соединен с управляющим выходом 192 ключа и через линию задержки 202 с входом R RS-триггера 195.

Блок переключателей 81 (фиг.15) содержит:
инвертор 203;
2(L+1) ключ 204, выполненный в виде логического элемента И с двумя входами 205, 206.

При этом L+2-й вход 84 блока 81 соединен с первыми входами 205 всех ключей (l L+2,2L+2) и с входом инвеpтора 203, выход которого соединен с первыми входами 205 всех ключей 204_l (l 1,L+1).

l-й вход 82_l (l 1.L) блока 81 соединен с вторыми входами 206 l-го и L+1+l-го ключей 204_l и 204_L+l+1.

L+1-й вход 83 блока 81 соединен с вторыми входами 206 L+1-го и 2L+2-го ключей 204_L+1 и 204_2L+2.

Выход l-го ключа (l₂ ≠ 1,2L+1, l L + 1) соединен с l₂ выходом блока 81.

Выход L+1-го ключа 204_L+1 соединен с 2L+2-м выходом 85_2L+2 блока 81.

Выход 2L+2-го ключа 204_2L+2 соединен с L+1-м выходом 85_L+1 блока 81.

Блок 91 элементов ИЛИ (фиг. 16) содержит L элементов ИЛИ 207 с двумя входами 208, 209.

При этом, 2l-1-й (l 1,L) вход 92_2l-1 блока 91 соединен с первым входом 208 l-го элемента ИЛИ 207_l, 2l-й (l 1,L) вход 92_2l блока 91 соединен с вторым входом 209 l-го элемента ИЛИ 207_2l, выход которого соединен с l-м выходом 93 блока 91.

Логический блок ИЛИ 154 с L входами (фиг.17) выполнен в виде p-уровневого (plog₂L} гдеx} обозначает наименьшее целое большее или равное х) каскада элементов ИЛИ, причем, на первом уровне расположено [L/2} элементов ИЛИ ([ обозначает целую часть числа), на q-м (q 1,p) уровне расположено s(q) элементов ИЛИ.

При этом, s(q + 1) [s(q)/2] Все, кроме последних, элементы ИЛИ всех уровней имеют по два входа, последний элемент первого уровня имеет два входа, если L четное, и три входа, если L нечетное. Последний элемент q + 1-го уровня имеет два входа, если s(q) четное, и три входа, если s(q) нечетное, 2l-й и 2l-1-й (l 1,[L/2]) входы блока являются входами l-го элемента ИЛИ первого уровня. Если L нечетно, последний вход блока является третьим входом последнего элемента ИЛИ первого уровня.

Выходы 2l-го и 2l-1-го (l 1,[s(q)/2]) элементов ИЛИ q-го уровня являются входами l-го элемента q+1-го уровня. Если s(q) нечетно, выход последнего элемента q-го уровня является третьим входом последнего элемента q+1-го уровня. Выход элемента последнего уровня является выходом блока.

Логический блок И 133 с N L + 1 входами (фиг.18) выполнен в виде уровневого (plog₂N} гдеx} обозначает наименьшее целое большее или равное х) каскада элементов И, причем, на первом уровне расположено [N/2] элементов И ([ обозначает целую часть числа), на q-м (q 1,p) уровне расположено s(q) элементов И.

При этом, s(q+1) [s(q)/2] Все, кроме последних, элементы И всех уровней имеют по два входа, последний элемент первого уровня имеет два входа, если N четное, и три входа, если N нечетное. Последний элемент q+1-го уровня имеет два входа, если s(q) четное, и три входа, если s(q) нечетное, 2l-й и 2l-1-й (l 1,[N/2]) входы блока являются входами l-го элемента ИЛИ первого уровня. Если N нечетно, последний вход блока является третьим входом последнего элемента ИЛИ первого уровня.

Выходы 2l-го и 2l-1-го (l 1,[s(q)/2]) элементов И q-го уровня являются входами l-го элемента q+1-го уровня. Если s(q) нечетно, выход последнего элемента q-го уровня является третьим входом последнего элемента q+1-го уровня. Выход элемента последнего уровня является выходом блока.

Блок ИЛИ-Е 78 с L входами (фиг.19) содержит блок элементов ИЛИ 154 с L входами и инвертор. При этом, выход логического блока ИЛИ с L входами соединен с входом инвертора, выход которого является выходом блока 78.

Работа спецпроцессора. Последовательность решения задачи.

Если дизъюнкция D фактически не зависит от переменной z, будем говорить, что переменная z является безразличной для дизъюнкций D.

абор a₁, a₂,a_n значений переменных будем называть невыполняющим для некоторой дизъюнкции D, если
D(a₁, a₂,a_n) 0.

Очевидно, что для каждой дизъюнкции ее невыполняющий набор определен с точностью до безразличных для данной дизъюнкции переменных. Кроме того, невыполняющий набор для множества дизъюнкций равен объединению невыполняющих наборов для отдельных дизъюнкций этого множества. По этой причине проще находить невыполняющие наборы, чем выполняющие.

Для каждой дизъюнкции D_j и каждой переменной z_i определим функцию St(D_j, z_i), которую назовем статусом переменной x в дизъюнкции D:
St(D_j, z_i) 0, если z_i входит в D в виде литерала z_i.

St(D_j, z_i) 1, если z_i входит в D в виде литералаz_i.

St(D_j, z_i)= *, если z_i безразличная переменная для D.

Здесь и далее * специальный символ, знак логического отрицания.

Очевидно, что если в качестве значения каждой переменной брать ее статус в дизъюнкции D (при этом символ * означает, что можно брать любое значение данной переменной, как 0 так и 1), то получится один из невыполняющих данную функцию наборов. Т.е.

D(St(D, z_i), St(D, z₂),St(D, z_n)) 0
апример, если имеются 4 переменные z₁, z₂, z₃, z₄ и дизъюнкция D имеет вид: z₂ +z₄, то переменные z₁ и z₃ являются безразличными для D.

St(D, z₁) *, St(D, z₂) 0, St(D, z₃) *, St(D, z₄) 1
евыполняющими являются следующие наборы переменных:
z₁ 0, z₂ 0, z₃ 0, z₄ 1;
z₁ 0, z₂ 0, z₃ 1; z₄ 1;
z₁ 1, z₂ 0, z₃ 0, z₁ 1;
z₁ 1, z₂ 0, z₃ 1, z₄ 1;
Легко видеть, что количество невыполняющих наборов равно 2^n-r, где r количество безразличных для рассматриваемой дизъюнкции переменных.

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

Будем называть работу спецпроцессора при данном фиксированном поднаборе b_j} циклом, соответствующим поднаборуb_j} При этом, цикл с двоичным номером b₁b₂.b_m+1 соответствует поднабору b₁, b₂,b_m значений переменных у₁, y₂,y_m. евыполняющим на данном цикле поднабором переменных первого типа называется такой поднабор, который вместе с текущим поднабором значений переменных второго типа дает невыполняющий набор значений переменных.

Для каждого фиксированного поднабора b₁.b_m значений переменных второго типа и для каждой из рассматриваемых дизъюнкций D₁, D_l все поднаборы а₁,a_n значений переменных x₁,x_n первого типа рассматривают параллельно, среди них выделяют и запоминают невыполняющие на данном цикле поднаборы.

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

Очевидно, что поднабор b₁, b₂,b_m значений переменных y₁, y₂, y_m будет невыполняющим для дизъюнкцийD} в том и только том случае, когда для любого j выполняется одно из двух условий:
St(D_l, y_j) * или St(D_l, y_j) b_j.

При данном фиксированном поднабореb_j} значений переменных y_j, на решение задачи о нахождении невыполняющих все множество дизъюнкций поднаборовa_i} переменных x_i могут влиять только те дизъюнкции D_l, для которых поднаборb_j} является невыполняющим. Будем называть такие дизъюнкции действующими для данного поднабораb_j} Соответственно, можно говорить о действующих на данном цикле дизъюнкциях.

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

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

Для этого фиксируют текущий поднабор значений переменных второго типа и разделяют переменные первого типа на два подтипа. Переменные первого подтипа рассматривают параллельно, второго последовательно. При этом учитывают только действовавшие на последнем цикле дизъюнкции. Т.е. снова решают задачу о выполнимости булевых формул, но с меньшим числом дизъюнкций и переменных. Процедура повторяется до тех пор пока выполняющий набор не будет определен однозначно.

Если после рассмотрения всех поднаборов второго типа решение не найдено, делают вывод об отсутствии решения.

Спецпроцессор работает в двух режимах:
1. Режим загрузки (подготовительный) (см. ниже работу устройства управления).

2. Основной режим.

В начале работы основного режима Host-машина через выход 18 интерфейса 3 выдает на вход 7 запуска устройства 2 управления единичный импульс запуска основного режима, после чего процессорная матрица начинает работу в первом цикле основного режима. (Режим загрузки при этом удобно рассматривать как нулевой цикл основного режима).

Процессорная матрица работает только в основном режиме. Она предназначена для:
1. Выбора всех поднаборов значений переменных первого типа, которые являются невыполняющими на данном цикле. Т.е. вместе с текущим поднабором значений переменных второго типа дают невыполняющий множество дизъюнкций набор.

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

Адрес каждой запоминающей ячейки процессорной матрицы имеет вид где a_j (j 1,n₁+n₂+n₃), принимают значения 0 или 1. При этом, двоичное число a₁,, называемое первой частью адреса, соответствует номеру блока, в котором находится запоминающая ячейка, двоичное число , называемое второй частью адреса, соответствует номеру ряда, в котором находится запоминающая ячейка, двоичное число , называемое третьей частью адреса, соответствует номеру запоминающей ячейки в ряду. Ячейке с адресом

ставят в соответствие поднабор

значений переменных x₁,x_n первого типа. Если D_r дизъюнкция, чей порядковый номер среди действующих на данном цикле дизъюнкций равен l, то на l-м тексте цикла записывают единицы в те ячейки, адреса которых соответствуют невыполняющим дизъюнкцию D_r поднаборам. Разряды адресов этих ячеек соответствуют статусам переменных в дизъюнкции D_r. Если St(x_i, D_r) 1, то i-е разряды адресов ячеек, соответствующих невыполняющим поднаборам, содержат единицы. Если St(x_i, D_r) 0, то i-е разряды адресов ячеек, соответствующих невыполняющим поднаборам, содержат нули. Если St(x_i, D_r) * то i-е разряды адресов ячеек, соответствующих невыполняющим поднаборам, содержат как нули, так и единицы.

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

В начале очередного цикла на вход 5 сброса процессорной матрицы 1 поступает сигнал сброса, который устанавливает в нуль все запоминающие ячейки 35 всех блоков 26 записи и считывания. а l-м такте рассматриваемого цикла (где l порядковый номер дизъюнкции D_r среди действующих на данном цикле дизъюнкций) на адресные входы устройства 1 сигналы поступают по следующему правилу:
если St(D_r, x_i) 1, на вход 4_2i устройства 1 поступает единица, а на адресный вход 4_2i-1 поступает нуль;
если St(D, x) 0, на адресный вход 4_2i поступает нуль, а на адресный вход 4_2i-1 поступает единица;
если St(D, x) *, на оба адресные входа 4_2i и 4_2i-1 поступают единицы.

Сигналы поступают на все входы (i_o 1,2n) одновременно. Сигналы с входов (i₁ 1.2n₁), соответствующих первой части адреса, поступают на входы дешифратора 31 адреса блока.

Параллельный дешифратор 31 адреса блока производит параллельную дешифровку адресов всех тех блоков , которые содержат ячейки, соответствующие невыполняющим дизъюнкцию D_r поднаборам значений переменных первого типа. С выходов дешифратора 31, соответствующих этим блокам, на разрешающие входы 29 блоков 26 поступают единицы.

Сигналы с входов (i₂ 1,2n₂) устройства 1, соответствующих второй части адреса, поступают параллельно на входы адреса строки всех блоков 26.

Рассмотрим работу блока с номером k₁ (k₁ 1,) (фиг.3). Если существует хотя бы один невыполняющий поднабор, первая часть адреса которого равна k₁, на разрешающий вход 29 блока поступает единица, отпирающая все ключи 44. Вследствие этого разряды вторых частей адресов невыполняющих поднаборов поступают на входы (i₂ 1,2n₂) параллельного дешифратора 36 адреса строки.

После срабатывания дешифратора 36 с его выходов , соответствующих вторым частям адресов невыполняющих поднаборов, единицы поступают на входы 45 тех ячеек 35, которые находятся в рядах, соответствующих невыполняющим поднаборам (фиг.3).

Сигналы с входов (i₃ 1,2n₃) устройства 1 параллельно поступают на входы адреса столбца всех блоков 26 параллельной записи и считывания.

Внутри каждого блока сигналы поступают на входы параллельного дешифратора 39 адреса столбца.

После срабатывания дешифратора 39 с его выходов 41, соответствующих третьим частям адресов невыполняющих поднаборов, единицы поступают на входы 46 запоминающих ячеек, соответствующих невыполняющим поднаборам (фиг.4).

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

Таким образом, на l-м такте ко всем запоминающим ячейкам, в которые были записаны единицы на предыдущих тактах, добавляются ячейки, соответствующие невыполняющим дизъюнкцию D_r наборам.

Содержимое запоминающего элемента 50 каждой запоминающей ячейки (k₂ 1,) непрерывно подается на вход каскада элементов И 42, на выходе которого единица появляется только в том случае, если на все входы 48 подаются единицы.

С выхода каскада элементов И сигнал поступает на k₂-й вход каскада 43 (фиг.3). Если на все входы 49 подаются единицы, на выходе 30 каскада элементов И 43 появляется 1. С выхода 30 блока (k₁ 1,) сигнал поступает на вход каскада элементов И 33 (фиг.2), на выходе 6 которого единица появляется в случае, если все поднаборы значений переменных первого типа оказались невыполняющими на данном цикле.

Устройство управления предназначено для:
1. Определения в ходе выполнения очередного цикла действующих на следующем цикле дизъюнкций.

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

Интерфейс 3 предназначен для связи HOST-машины с устройством 2 выбора адресов ячеек.

Работа устройства управления в режиме загрузки.

Перед началом загрузки устройства 2 на его вход 10 сброса через выход 21 сброса интерфейса 3 подается сигнал сброса, который затем поступает на входы сброса блока 57 выбора дизъюнкций, блока 63 адресации, регистра 75 номера последнего цикла и счетчика 69 циклов. Вследствие этого во все запоминающие ячейки блока 57 выбора дизъюнкций, блока 63 адресации и регистра 75 номера последнего цикла заносятся нули, во все запоминающие ячейки счетчика 69 циклов заносятся единицы. Таким образом в счетчике 69 оказывается записанным число 11.1, представляющее из себя -1 в дополнительном коде.

После этого в запоминающие ячейки блока 57 выбора дизъюнкций заносятся значения статуса переменных второго типа в каждой из дизъюнкций. В запоминающие ячейки блока 63 адресации заносят разряды адресов ячеек, соответствующих невыполняющим наборам переменных первого типа, для всех дизъюнкций. В регистр 75 номера последнего цикла заносят номер последнего рабочего цикла, равный 2^m, где m количество переменных второго типа, рассматриваемых в задаче.

Запись данных в блоки 57 и 63 происходит по следующим правилам:
Пусть L число рассматриваемых в задаче дизъюнкций.

Для всех 1<= L_o:
Если j-ая переменная второго типа Y_j не входит в дизъюнкцию D_l, в 2j-1-й запоминающий элемент 118_2j-1 1-й схемы 112_l выбора блока 57 выбора дизъюнкций записывают 1, в 2j-й запоминающий элемент 118_2j 1-й схемы 112_l выбора блока 57 выбора дизъюнкций ничего не записывают.

Если j-тая переменная второго типа Y_j входит в дизъюнкцию D_l в виде литерала Y_j (без отрицания), в 2j-1-й запоминающий элемент 118_2j-1 1-й схемы 112_l выбора блока 57 выбора дизъюнкций и в 2j-й запоминающий элемент 118_2j 1-й схемы 112_l выбора блока 57 ничего не записывают.

Если j-я переменная второго типа у входит в дизъюнкцию D в виде литерала y_j (с отрицанием), в 2j-1-й запоминающий элемент 118_2j-1 1-й схемы 112_l выбора блока 57 выбора дизъюнкций ничего не записывают, в 2j-й запоминающий элемент 118_2j 1-й схемы 112_l выбора блока 57 записывают 1.

Для всех 1>L_o:
В первый и второй запоминающие элементы 118₁ и 118₂ 1-й схемы выбора 112_l блока 57 выбора дизъюнкций записывают 1.

Работа устройства управления в основном режиме.

Регистр 75 номера последнего цикла хранит номер последнего цикла (число 2^m).

Счетчик 69 циклов содержит номер текущего цикла, уменьшенный на единицу.

а r-м цикле происходит обработка поднабора значений переменных y₁, y₂, y_j, соответствующего числу r-2 и подготовка к обработке поднабора значений переменных y₁, y₂,y_j, соответствующего числу r-1. улевым циклом считается режим загрузки. Так как последние m разрядов числа -1 в дополнительном коде совпадают с разрядами числа 2^m-1, на первом цикле обрабатывается поднабор значений переменных y₁, y₂,y_j, соответствующий числу 2^m-1.

аходящееся в счетчике циклов число r-1 поразрядно поступает на нечетные входы логического блока И 72 и на управляющие входы 58 блока 57 выбора дизъюнкций. а четные входы логического блока 72 поступают значения разрядов регистра номера последнего цикла. В случае совпадения значения счетчика циклов с номером последнего цикла на выходе блока И, который соединен с первым выходом 13 решения устройства 2 управления, появляется единица, означающая, что задача не имеет решения. Через элемент ИЛИ 104 единица поступает также на вход 99 блока 94 синхронизации и останавливает его работу.

а управляющих входах 62 блока 57, соответствующих действующим на r+1-м цикле дизъюнкциям, появляются единицы, на остальных управляющих выходах 62 - нули. Эти значения поступают на входы 79 блока 78 ИЛИ-Е и на входы 82_l (l 1, L) блока 81 переключателей. Если ни одна из дизъюнкций не является действующей на r+1-м цикле, на выходе 80 блока ИЛИ-Е, который соединен с вторым выходом 14 решения устройства 2 выбора адресов ячеек, появляется единица, означающая, что поднабор значений переменных второго типа, соответствующий содержимому счетчика циклов, вместе с любым поднабором значений переменных первого типа дает решение задачи.

В этом случае через элемент ИЛИ 104 единица поступает также на вход 99 блока 94 синхронизации и останавливает его работу.

Блок 81 переключателей может находиться в двух состояниях нулевом и первом, номера которых определяются значениями сигнала, поступающего на вход 84 блока 81 с выхода 102 блока 94 синхронизации.

В нулевом состоянии l-й (l 1,L) вход 82_l блока 81 соединяется с l-м выходом 85_l, а через него с l-м входом 88_l определителя 86. Вход 83 блока соединяется с 2L+2-м выходом 85_2L+2, а через него с L+1-м входом 88_L+1 определителя 87.

В единичном состоянии l-й вход 82_l блока 81 соединяется с 1+L+1-м выходом 85_l+L+1, а через него с l-м входом 88_l определителя 87. Вход 83 блока соединяется с L+1-м выходом 85_L+1, а через него с L+1-м входом 88_L+1 определителя 86.

Положим для определенности, что на рассматриваемом цикле блок переключателей находится в нулевом состоянии.

Тогда первый определитель 86 порядка дизъюнкций действует в режиме загрузки, а второй определитель 87 порядка дизъюнкций действует в режиме работы.

а управляющие входы 88_l (l 1,L) определителя 86, соответствующие действующим на r+1-м цикле дизъюнкциям, с выходов 85 блока 81 поступают единицы, после чего в триггеры 195 ключей 190 (фиг.13, 14) определителя 86. соответствующих действующим на r+1-м цикле дизъюнкциям, заносятся единицы.

Работа устройств 57, 78, 81 и 86 происходит асинхронно.

Работа устройства 87 происходит синхронно тактовым импульсам, поступающим от блока 94. Тактовые импульсы с выхода 101 блока 94 синхронизации поступают на L+1-й вход 83 блока 81 переключателей, а оттуда на тактовый вход 88 определителя 87. Каждый тактовый импульс беспрепятственно проходит через те ключи 190, в триггер 195 которых (фиг.14, 13) не занесены единицы, т.е. через те ключи, которые не соответствуют действующим на данном цикле дизъюнкциям. Как только тактовый импульс доходит до ключа 190, соответствующего очередной действующей на данном цикле дизъюнкции, он не проходит на вход следующего ключа, а поступает на выход 192 данного ключа и на вход линии 202 задержки. С входа 192 ключа 190 единица поступает на выход 89 определителя 87, соответствующий очередной действующей на данном цикле дизъюнкции.

С выхода линии задержки 202 задержанный на половину такта импульс поступает на вход R триггера 195 и записывает в него нуль. Следующий тактовый импульс беспрепятственно проходит через ключ 190 и движется до следующего ключа, соответствующего действующей дизъюнкции.

После того, как все ключи 190, соответствующие действующим дизъюнкциям, пройдены, тактовые импульсы поступают на выход 90 определителя 87, а оттуда
на вход 96 устройства 94, сигнализируя о том, что определитель 87 закончил работу.

Таким образом, если на r-м цикле действует l_r дизъюнкция, то r-й цикл включает в себя l_r машинных тактов. Если дизъюнкция D_s является действующей на r-м цикле и порядок ее действия равен l_s(l_s∈1,....L),, то на l_s такте r-го цикла на k-й выход 89_k определителя 87 поступает единица, которая через блок 91 элементов ИЛИ попадает на k-й управляющий вход 64_k блока 63 адресации, вследствие чего блок 63 выдает единицы с выходов 68, соответствующих разрядам адресов ячеек, соответствующих невыполняющим дизъюнкцию D_s поднаборам значений переменных x₁, x₂,x_n.

До тех пор, пока хотя бы в одной из запоминающих ячеек устройства 2 параллельной записи и считывания записан нуль, с выхода 6 устройства 1 на сигнальный вход 8 устройства 2 и далее на вход 97 блока 94 сигнализации продолжает поступать нуль.

Если во всех запоминающих ячейках устройства 2 оказываются записаны единицы (т.е. если все поднаборы значений переменных первого типа оказались на данном цикле невыполняющими и дальнейшая работа в данном цикле не имеет смысла), с выхода 6 устройства 1 на сигнальный вход 8 устройства 2 и далее на вход 97 блока 94 поступает единица. Если с момента начала цикла прошло время, достаточное для того, чтобы в триггеры 195 ключей 190 определителя 86, соответствующих действующим на r+1-м цикле дизъюнкциям, записались единицы, блок 94 инициирует выполнение следующего цикла. Для этого он:
1. Выдает с выхода 103 единичный сигнал на счетный вход 71 счетчика 69 циклов (после чего счетчик увеличивает свое значение на единицу) и на выход 17 сброса устройства 2. С выхода 17 единица попадает на вход 5 сброса устройства 1, что приводит к обнулению всех его запоминающих ячеек.

2. Меняет свое значение сигнала на выходе 102 на противоположное, что приводит к изменению на противоположное состояние блока 81 переключателей.

Если после поступления на вход 96 единицы, сигнализирующей, что определитель 87 закончил работу, на вход 97 блока 94 в течение времени, необходимого для завершения срабатывания устройства 1, продолжает поступать нуль, это означает что среди поднаборов значений переменных первого типа есть хоть один выполняющий. Блок 94 выдает на выход 100 единичный сигнал, поступающий затем на выход 15 устройства 2, и прекращает работу.

Остановка блока 94 происходит также в случае поступления единицы на вход 99.

Работа блока 94 синхронизации.

При поступлении единицы на вход 98 блока 94 происходит запуск генератора 183 тактовых импульсов, срабатывает элемент ИЛИ 175 и блок 94 приступает к синхронизации выполнения первого цикла:
Генератор 183 выдает на выход 101 блока 94 тактовые импульсы.

С выхода элемента ИЛИ 175 единица поступает на вход Т-триггера 186, переводя его в противоположное состояние, на вход R RS-триггера 173, на вход линии задержки 189 и через выход 103 блока 94 на счетный вход счетчика 69, увеличивая его значение на 1, и на выход 17 устройства 2, а оттуда на вход 5 очистки устройства 1.

При поступлении сигнала на вход R RS-триггера 173 в триггер заносится нуль, поступающий затем на вход 171 элемента И 168 и запирающий его.

Линия задержки 189 задерживает сигнал на время, необходимое для загрузки определителя дизъюнкций. После этого единица поступает на вход S RS-триггера 173. В триггер заносится единица, поступающая затем на вход 171 элемента И 168 и отпирающая его.

При поступлении единицы на первый 95 или второй 96 входы блока срабатывает элемент ИЛИ 174 и выдает единицу на вход линии задержки 188. По прошествии времени, необходимого для записи единиц в ячейки устройства 1 и для срабатывания каскадов элементов И этого устройства, единица с выхода линии задержки 188 поступает на вход 169 элемента И 167. Если в это время на вход 97 блока 94 продолжает поступать нуль, с выхода инвертора 166 на второй вход 170 элемента И 167 поступает единица, элемент 167 срабатывает и выдает единицы на выход 100 устройства 94 и на вход 181 элемента ИЛИ 176. С выхода элемента ИЛИ 176 сигнал поступает на вход 185 остановки генератора 183. Остановка генератора 183 происходит также и при поступлении единицы на вход 99 блока 94.

Если элемент И 168 открыт, то при поступлении единицы на вход 97 блока 94 он срабатывает, единица поступает на вход 180 элемента ИЛИ 175, в результате чего блок 94 приступает к синхронизации выполнения очередного цикла.

Работа блока 57 выбора дизъюнкций.

С j-того входа 58_j блока 57 значение j-го разряда содержимого счетчика поступает на 2j-i-е входы 113_2j-1 всех схем выбора 112 и через инвертор 105_m на 2j-е входы 113_2j всех схем выбора 112.

Если j-тая переменная Y_j не входит в l-ю дизъюнкцию D_l, единица, записанная в триггер 118_2j-1 схемы выбора 112_l поступает на вход элемента ИЛИ 126, на выходе которого единица появляется независимо от того, какое значение поступило на входы 113_2j-1 и 113_2j.

Если j-я переменная Y_j входит в l-ую дизъюнкцию D_l, и, следовательно, в триггере 118_2j-1 содержится нуль, то единица появляется на выходе элемента ИЛИ 126_j только в случае, если она появляется на выходе элемента И 119_2j-1 или элемента И 119_2j, что имеет место, когда содержимое триггера 118_2j совпадает со значением, поступившим на вход 58_j блока 57. (Если значение, поступившее на вход 58_j, равно 1 и содержимое триггера 118_2j равно 1, срабатывает элемент 119_2j-1. Если значение, поступившее на вход 58_j, равно 0 и содержимое триггера 118_2j равно 0, срабатывает элемент 119_2j).

Единица на выходе элемента И 133 схемы выбора 112_l (а, следовательно, и на l-м выходе 62_l блока 57 выбора дизъюнкций) появляется в том и только том случае, когда для всех j на выходах элементов И 126_j появляются единицы. Т. е. переменная Y_j либо не входит в дизъюнкцию D, либо ее значение b_j, рассматриваемое на данном цикле, входит в невыполняющий дизъюнкции D_l набор, иными словами, когда дизъюнкция D_l является действующей на данном цикле.

Если дизъюнкция D_l вообще не рассматривается, то (и только в этом случае) в оба триггера 118₁ и 118₂ записывается единица. Элемент И-Е 130 выдает нуль на вход 134 элемента И 133, и единица на k-м выходе 62_l блока 57 выбора дизъюнкций не появляется ни в каком случае.

Работа блока 63 адресации.

а очередном такте работы спецпроцессора единица поступает на вход 64_l блока 63 адресации, соответствующий рассматриваемой на данном такте дизъюнкции D_l, а оттуда на входы 146_l всех схем адресации 145. При этом, открываются все 2l-ые и 2l-1-е ключи 156_2l-1 и 156_2l всех схем адресации 145, и содержимое 2l-х и 2l-1-х запоминающих элементов 153_2l-1 и 153_2l всех схем адресации через блоки 154 элементов ИЛИ параллельно поступает на выходы 151, 152 всех схем адресации и через них на выходы 68 блока 63 адресации. И

Изобретение относится к области вычислительной техники, в частности к высокопараллельным специализированным процессорам. Задачей предлагаемого изобретения является создание высокопараллельного спецпроцессора, способного осуществлять параллельный перебор большого количества вариантов с максимально возможной скоростью путем увеличения степени параллелизма (посредством упрощения процессорного элемента до одной ячейки) и снижения до одного количества машинных тактов, требующихся процессорному элементу для рассмотрения одного варианта. Для решения поставленной задачи в высокопараллельном спецпроцессоре для решения задач о выполнимости булевых формул, состоящем из процессорной матрицы, устройства управления и интерфейса, процессорная матрица выполнена в виде устройства параллельной записи и считывания с 2n адресными входами, входом сброса и одним выходом, устройство управления выполнено в виде устройства выбора адресов ячеек с входом запуска, сигнальным входом, 2+2{ log₂(L)} +2{log₂(m)}+{log₂(n)}, (где {x} обозначает наименьшее целое, большее или равное х) входами загрузки, входом сброса, входом записи, 2n управляющими выходами, тремя выходами решения, m выходами чтения и одним выходом сброса. 9 з.п. ф-лы, 20 ил.

1. Высокопараллельный спецпроцессор для решения задач о выполнимости булевых формул, состоящий из процессорной матрицы, устройства управления и интерфейса, отличающийся тем, что i-й (i 1, 2n) адресный вход процессорной матрицы соединен с i-м управляющим выходом устройства управления, вход сброса процессорной матрицы соединен с выходом сброса устройства управления, выход процессорной матрицы соединен с сигнальным входом устройства управления, вход запуска которого соединен с выходом запуска интерфейса, j-й (j 1, m) выход чтения устройства управления соединен с j-м входом чтения интерфейса, р-й
(p=1,2+2{log₂(L)}+2{log₂(m)}+{log₂(n)} x} обозначает наименьшее целое, большее или равное х), вход загрузки устройства управления соединен с р-м выходом загрузки интерфейса, вход сброса устройства управления соединен с выходом сброса интерфейса, вход записи устройства управления соединен с выходом записи интерфейса, первый, второй и третий выходы решения устройства управления соединены с первым, вторым и третьим входами решения интерфейса соответственно, при этом процессорная матрица содержит идентичных блока записи и считывания, дешифратор адреса блока, входовой каскад элементов И, причем i₁-й (i₁ 1, 2n₁) вход дешифратора адреса блока является i₁-м адресным входом процессорной матрицы, k₁-й выход дешифратора адреса блока соединен с разрешающим входом k₁-го блока записи и считывания, i₂-й (i₂ 1, 2n₂) вход адреса строки каждого блока записи и считывания соединен с i₂ + 2n₁-м адресным входом процессорной матрицы, i₃-й (i₃ 1, 2n₃) вход адреса столбца каждого блока записи и считывания соединен с i₃ + 2n₁ + 2n₂-м адресным входом процессорной матрицы, вход сброса каждого блока записи и считывания соединен с входом сброса процессорной матрицы, выход k₁-го блока записи и считывания соединен с k₁-м входом -входового каскада элементов И, выход которого является выходом процессорной матрицы, при этом каждый блок записи и считывания содержит матрицу запоминающих ячеек, дешифратор адреса строки, дешифратор адреса столбца, -входовых каскадов элементов И, -входовый главный каскад элементов И, 2n₂ ключей, выполненных в виде элементов И с двумя входами, причем k₂-й выход дешифратора адреса строки соединен с первыми входами выборки всех запоминающих ячеек k₂-й строки матрицы запоминающих ячеек, k₃-й выход дешифратора адреса столбца соединен с вторыми входами выборки всех запоминающих ячеек k₃-го столбца матрицы запоминающих ячеек, первый вход i₂-го (i₂ 1, 2n₂) ключа является i₂-м входом адреса строки блока записи и считывания, второй вход каждого ключа соединен с разрешающим входом блока записи и считывания, i₂-й (i₂ 1, 2n₂) вход дешифратора адреса строки соединен с выходом i₂-го ключа, i₃-й (i₃ 1, 2n₃) вход дешифратора адреса столбца соединен с i₃-м входом адреса столбца блока записи и считывания, вход сброса каждой из запоминающих ячеек соединен с входом сброса блока записи и считывания, выход k₃-й запоминающей ячейки k₂-го ряда матрицы запоминающих ячеек соединен с k₃-м входом k₂-го каскада элементов И, выход k₂-го каскада элементов И соединен с k₂-м входом -входового главного каскада элементов И, выход которого является выходом блока записи и считывания, при этом каждая запоминающая ячейка содержит запоминающий элемент и элемент И с двумя входами, причем первый и второй входы элемента И соединены с первым и вторым входами выборки запоминающей ячейки, выход элемента И соединен с входом записи единицы запоминающего элемента, вход записи нуля запоминающего элемента соединен с входом сброса запоминающей ячейки, прямой выход запоминающего элемента является выходом запоминающей ячейки, дешифраторы адресов блока, строк и столбцов выполнены в виде параллельных адресных дешифраторов, имеющих 2^N выходов и 2N адресных входов (N n₁, n₂, n₃) для дешифраторов блока, адреса строки и адреса столбца соответственно), по одному независимому входу для нулевого и для единичного значения каждого двоичного разряда адреса, 2^N-входовый (N n₁, n₂, n₃) каскад элементов И содержит 2^N 1 элементов И с двумя входами, расположенных на N уровнях, при этом на I-м (I 1, N) уровне имеется 2^N - 1 элемента, входы каскада с номерами 2k₁ 1 и 2k₁ (k₁ 1, 2^N - 1) соединены с входами элемента И с номером к₁ первого уровня, выходы элементов И с номерами 2k₁ 1 и 2k₁ (k₁ 1, 2^N - 1) I-го уровня соединены с входами элемента И номер k₁ I + 1-го уровня, выход элемента И N-го уровня является выходом всего каскада, устройство управления содержит блок выбора дизъюнкций, блок адресации, m + 1-разрядный счетчик циклов по модулю 2^m + 1, блок элементов И, m + 1-разрядный регистр номера последнего цикла, блок ИЛИ-НЕ, блок переключателей, первый и второй определители порядка дизъюнкций, блок элементов ИЛИ, блок синхронизации, элемент ИЛИ с двумя входами, причем выход j-го (j 1, m + 1) разряда регистра номера последнего цикла соединен с (2j 1)-м входом блока элементов И, выход j-го разряда счетчика циклов соединен с 2j-м входом блока элементов И, выход блока элементов И соединен с первым выходом решения устройства управления и с первым входом элемента ИЛИ, выход j-го (j 1, m)разряда счетчика циклов соединен с j-м управляющим входом блока выбора дизъюнкций, l-й (l=1,L) выход которого соединен с l-м входом блока переключателей и с l-м входом блока ИЛИ-НЕ, выход блока ИЛИ-НЕ соединен с вторым выходом решения устройства управления и с вторым входом элемента ИЛИ, l-й выход блока переключателей соединен с l-м входом первого определителя порядка дизъюнкций, L+l+1-й выход блока переключателей соединен с l-м входом второго определителя порядка дизъюнкций, L+1-й выход блока переключателей соединен с L+1-м входом первого определителя порядка дизъюнкций, 2L+2-й выход блока переключателей соединен с L+1-м входом второго определителя порядка дизъюнкций, l-е выходы первого и второго определителей порядка дизъюнкций соединены соответственно с (2l-1)-м и 2l-м входами блока элементов ИЛИ, l-й выход которого соединен с l-м управляющим входом блока адресации, i-й (i 1, 2n, n n₁ + n₂ + n₃) управляющий выход которого соединен с i-м управляющим выходом устройства управления, сигнальный выход первого определителя порядка дизъюнкций соединен с первым входом блока синхронизации, сигнальный выход второго определителя порядка дизъюнкций соединен с вторым входом блока синхронизации, третий вход блока синхронизации соединен с сигнальным входом устройства управления, четвертый вход блока синхронизации соединен с входом запуска устройства управления, пятый вход блока синхронизации соединен с выходом элемента ИЛИ, первый выход блока синхронизации соединен с третьим выходом решения устройства управления, второй выход блока синхронизации соединен с L+1-м входом блока переключателей, третий выход блока синхронизации соединен с L+2-м входом блока переключателей, четвертый выход блока синхронизации соединен со счетным входом счетчика циклов и с выходом сброса устройства управления, р₁-й вход (р₁ 1, log₂(m)} ) загрузки регистра номера последнего цикла соединен с р₁-м входом загрузки устройства управления, q₂-й (q₂=1,log₂(m)}+{log₂(L)}+1) вход загрузки блока выбора дизъюнкций соединен с р₂-м (р₂=q₂+{log₂(m)}) входом загрузки устройства управления q₃-й (q₃=1,log₂(n)}+{log₂(L)}+1 вход загрузки блока адресации соединен с p₃-м (p₃=q₃+2•{log₂(m)}+{log₂(L)}+1) входом загрузки устройства управления, входы сброса блока выбора дизъюнкций, блока адресации, счетчика циклов и регистра номера последнего цикла соединены с входом сброса устройства управления, входы записи блока выбора дизъюнкций, блока адресации и регистра номера последнего цикла соединены с входом записи устройства управления, при этом блок выбора дизъюнкций содержит m инверторов, дешифратор адреса схемы, дешифратор адреса ячейки и L схем выбора, причем j-й (j 1, m) управляющий вход блока выбора дизъюнкций соединен с 2j 1-ми управляющими входами всех схем выбора и с входом j-го инвертора, выход которого соединен с 2j-ми управляющими входами всех схем выбора, выход l-й (l=1, L)схемы выбора соединен с l-м выходом блока выбора дизъюнкций, q₄-й (q₄=1, log₂(L)}) вход загрузки блока выбора дизъюнкций соединен с q₄-м входом дешифратора адреса схемы, l-й выход которого соединен с разрешающим входом l-й схемы выбора, q₅-й (q₅=log₂(L)}+1log₂(m)}+{log₂(L)}+1) вход загрузки блока выбора дизъюнкций соединен с q₅-/log₂(L)/-м входом дешифратора адреса ячейки, j₁-й (j₁ 1, 2m) выход которого соединен с j₁-ми входами выборки всех схем выбора, входы сброса и записи каждой схемы выбора соединены со входами сброса и записи блока выбора дизъюнкций, при этом каждая схема выбора содержит 2m запоминающих элементов, 2m элементов И с двумя входами, 2m элементов И с тремя входами, m элементов ИЛИ с тремя входами, элемент И-НЕ, блок элементов И, причем в каждой схеме выбора прямой выход 2j 1-го (j 1, m) запоминающего элемента соединен с первым входом j-го элемента ИЛИ, прямой выход 2j-го запоминающего элемента соединен с первым входом (2j 1)-го элемента И с двумя входами, инверсный выход 2j-го запоминающего элемента соединен с первым входом 2j-го элемента И с двумя входами, второй вход 2j 1-го элемента И с двумя входами соединен с (2j 1)-м управляющим входом схемы выбора, второй вход 2j-го элемента И с двумя входами соединен с 2j-м управляющим входом схемы выбора, выходы (2j 1)-го и 2j-го элементов И с двумя входами соединены с вторым и третьим входами j-го элемента ИЛИ, выход j-го элемента ИЛИ соединен с j-м входом блока элементов И, выход которого соединен с выходом схемы выбора, прямые выходы первого и второго запоминающих элементов соединены с первым и вторым входами элемента И-НЕ, выход которого соединен с (m + 1)-м входом блока элементов И, вход записи единицы j₁-го (j₁ 1, 2m) запоминающего элемента соединен с выходом j₁-го элемента И с тремя входами, входы записи нуля всех запоминающих элементов соединены с входом сброса схемы выбора, первый вход j₁-го элемента И с тремя входами соединен с j₁-м входом выборки схемы выбора, вторые входы всех элементов И с тремя входами соединены с разрешающим входом схемы выбора, третьи входы всех элементов И с тремя входами соединены с входом записи схемы выбора, блок адресации содержит дешифратор адреса схемы, дешифратор адреса ячейки, n n₁ + n₂ + n₃ схем адресации, причем l-е (l=1,L) управляющие входы всех схем адресации соединены с l-м управляющим входом блока адресации, первый и второй выходы i-й (i 1, n) схемы адресации соединены с (2i 1)-м и 2i-м выходами блока, q₆-й (q₆ 1,log₂(n)}) вход загрузки блока адресации соединен с q₆-м входом дешифратора адреса схемы, i-й выход которого соединен с разрешающим входом i-й схемы выбора, q₇-й (q₇=log₂(n)}+1log₂(n)}+{log₂(L)}+1) вход загрузки блока адресации соединен с q₇-/log₂(n)/-м входом дешифратора адреса ячейки, l₁-й (l₁=1,2L) выход которого соединен с l₁-ми входами выборки всех схем адресации, входы сброса и записи каждой схемы адресации соединены с входами сброса и записи блока адресации, при этом каждая схема адресации содержит 2L запоминающих элементов, две группы элементов ИЛИ с L входами каждый, 2L ключей, выполненных в виде элементов И с двумя входами, 2L элементов И с тремя входами, причем прямые выходы 2l-1-го и 2l-го (l=1,L) запоминающих элементов соединены с первыми входами (2l-1)-го и 2l-го ключей, вторые входы (2l-1)-го и 2l-го ключей соединены с l-м управляющим входом схемы адресации, выходы всех нечетных ключей соединены с входами первого блока элементов ИЛИ, выходы всех четных ключей соединены с входами второго блока элементов ИЛИ, выходы первого и второго блоков элементов ИЛИ соединены с первым и вторым выходами схемы адресации, вход записи единицы l₁-го (l₁=1,2L) запоминающего элемента соединен с выходом l₁-го элемента И с тремя входами, входы записи нуля всех запоминающих элементов соединены с входом сброса схемы адресации, первый вход l₁-го элемента И с тремя входами соединен с l₁-м входом выборки схемы адресации, вторые входы всех элементов И с тремя входами соединены с разрешающим входом схемы адресации, третьи входы всех элементов И с тремя входами соединены с входом записи схемы адресации. 2. Спецпроцессор по п.1, отличающийся тем, что блок синхронизации содержит инвертор, два элемента И, RS-триггер, три элемента ИЛИ, генератор тактовых импульсов, Т-триггер, две линии задержки, причем первый и второй входы блока соединены с первым и вторым входами первого элемента ИЛИ, третий вход блока соединен с вторым входом второго элемента И, первый вход которого соединен с Q-выходом RS-триггера, выход первого элемента ИЛИ через первую линию задержки соединен с первым входом первого элемента И, третий вход блока через инвертор соединен с вторым входом первого элемента И, выход первого элемента И является первым выходом блока и соединен с первым входом третьего элемента ИЛИ, выход второго элемента И соединен с вторым входом второго элемента ИЛИ, первый вход которого является четвертым входом блока синхронизации, выход второго элемента ИЛИ соединен с четвертым выходом блока, со счетным входом Т-триггера, с R-входом RS-триггера и через вторую линию задержки с S-входом RS-триггера, выход Т-триггера является третьим выходом блока, четвертый вход блока соединен с входом запуска генератора, выход генератора соединен с вторым выходом блока, пятый вход блока соединен с вторым входом третьего элемента ИЛИ, выход которого соединен с входом остановки генератора. 3. Спецпроцессор по п. 1, отличающийся тем, что определитель порядка дизъюнкций содержит L ключей, при этом управляющий вход l-го (l=1,2L) ключа соединен с l-м входом определителя, управляющий выход l-го ключа соединен с управляющим выходом определителя, тактовый вход первого ключа соединен с L+1-м входом определителя, тактовый вход l-го ключа (l=2,L) соединен с тактовым выходом L-1-го ключа, тактовый выход L-го ключа соединен с сигнальным выходом определителя, причем каждый из ключей содержит RS-триггер, два элемента И, линию задержки на половину машинного такта, при этом управляющий вход ключа соединен с S-входом RS-триггера, Q-выход RS-триггера соединен с вторым входом второго элемента И, выход RS-триггера соединен с вторым входом первого элемента И, первые входы элементов И соединены с тактовым входом ключа, выход первого элемента И соединен с тактовым выходом ключа, выход второго элемента И соединен с управляющим выходом ключа и через линию задержки с R-входом RS-триггера. 4. Спецпроцессор по п.1, отличающийся тем, что блок переключателей содержит инвертор и 2(L+1) ключей, причем L+2-й вход блока соединен с первыми входами всех ключей с номерами, большими L+1 и с входом инвертора, выход которого соединен с первыми входами всех ключей с номерами, меньшими или равными L+1, l-й (l= 1,L, L+1), вход блока соединен с вторыми входами l-го и (l+1)-го ключей, выход l₁-го ключа (l₁=1,2L+1, l₁≠L+1) соединен с l₁-м выходом блока, выход L+1-го ключа соединен с (2L+2)-м выходом блока, выход 2L+2-го ключа соединен с L+1-м выходом блока. 5. Спецпроцессор по п.1, отличающийся тем, что блок элементов ИЛИ содержит L элементов ИЛИ, причем 2l-1-й (l=1,L) вход блока соединен с первым входом l-го элемента ИЛИ, 2l-й (l=1,L) вход блока соединен с вторым входом l-го элемента ИЛИ, выход которого является l-м выходом блока. 6. Спецпроцессор по п.1, отличающийся тем, что группа элементов ИЛИ с L-входами выполнен в схеме адресации в виде p-уровневого p=[log₂L] каскада элементов ИЛИ, причем первый уровень содержит L/2 элементов ИЛИ ([] обозначает целую часть числа), q-й (q 1, p) уровень содержит S (q) элементов ИЛИ, при этом S (q + 1) [S(q)/2] 2l₁-й и (2l₁ - 1)-й (l₁=1,[L/2]) входы группы являются входами l₁-го элемента ИЛИ первого уровня, при L нечетном последний вход группы является третьим входом последнего элемента ИЛИ первого уровня, выходы 2l_q-го и (2l_q 1)-го (l_q 1, [S(q)/2]) элементов ИЛИ q-го уровня являются входами l_q-го элемента ИЛИ q + 1-го уровня, при S(q) нечетном выход последнего элемента ИЛИ q-го уровня является третьим входом последнего элемента ИЛИ q + 1-го уровня, выход элемента ИЛИ последнего уровня является выходом группы. 7. Спецпроцессор по п.1, отличающийся тем, что блок элементов И с N (N= L+1) входами выполнен в виде p-уровневого (p [log₂N]) каскада элементов И, причем первый уровень содержит [N/2] элементов И ([] обозначает целую часть числа), q-й (q 1, p) уровень содержит S(q) элементов И, при этом S (q + 1) [S (q)/2] 2l₁-й и (2l₁ 1)-й (l₁ 1, [N/2]) входы блока являются входами l₁-го элемента И первого уровня, при N нечетном последний вход блока является третьим входом последнего элемента И первого уровня, выходы 2l_q-го и (2l_q 1)-го (l_q 1, [S(q)/2]) элементов И q-го уровня являются входами l_q-го элемента И (q + 1)-го уровня, при S(q) нечетном выход последнего элемента И q-го уровня является третьим входом последнего элемента И (q + 1)-го уровня, выход элемента И последнего уровня является выходом блока. 8. Спецпроцессор по п.1, отличающийся тем, что запоминающий элемент выполнен в виде RS-триггера, S-вход которого является входом записи единицы элемента, R-вход является входом записи нуля, Q-вход прямым выходом элемента, вход инверсным выходом элемента. 9. Спецпроцессор по п.1, отличающийся тем, что вход сброса (m + 1)-го разрядного счетчика циклов по модулю 2^m + 1 соединен с входами записи единицы всех регистров счетчика. 10. Спецпроцессор по п.1, отличающийся тем, что (m + 1)-разрядный регистр номера последнего цикла содержит дешифратор сlog₂(m)} входами (гдех} обозначает наименьшее целое большее или равное х) и m выходами, причем p-й (plog₂(m)} вход дешифратора соединен с p-м входом загрузки регистра, а j-й (j 1, m) выход дешифратора соединен с входом записи единицы j-го разряда регистра.