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

Изобретение относится к вычислительной технике, в частности к специализированным процессорам с высокой степенью параллелизма. Спецпроцессор предназначен для решения задачи о выполнимости булевых функций, заданных в конъюнктивной нормальной форме, имеющих N=2^K переменных и М дизъюнкций, в которых использовано L литералов переменных.

Известен спецпроцессор, на основе ассоциативной матрицы, обладающий высокой степенью параллелизма выполнения операций ассоциативного опроса содержимого всех строк матрицы с последующей ассоциативной записью в строки, выделенные по результатам предшествующих ассоциативных опросов (US 3863232, 28.01.1975).

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

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

Известен процессор, специализированный на решении задачи выполнимости булевых функций. Структура спецпроцессора включает цепи обработки дизъюнкций и цепи обработки переменных. Спецпроцессор обладает высокой степенью параллелизма и одновременно оперирует со всеми переменными и всеми дизъюнкциями булевой функции, загруженными в его матрицу (US 7565634, 21.07.2009).

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

Известен высокопараллельный спецпроцессор для решения задач о выполнимости булевых формул, наиболее близкий по своей технической сущности к предлагаемому изобретению и выбранный в качестве прототипа. Данный спецпроцессор содержит устройство управления и процессорный блок, выполненный в виде матрицы. Процессорный блок является устройством параллельной записи и считывания с многоразрядным (2N) адресным входом, входом сброса и одним выходом (RU 2074415 С1 27.02.1997).

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

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

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

Технический результат достигается тем, что предлагаемый спецпроцессор содержит усилитель синхросигнала, вход которого является входом синхронизации спецпроцессора, процессорный блок иерархического уровня N, K+1-разрядный информационный вход которого является информационным входом спецпроцессора, а первый выход является первым выходом спецпроцессора, при этом в спецпроцессор дополнительно введен N-разрядный регистр сдвига, информационный вход которого подключен ко второму выходу процессорного блока иерархического уровня N, вход разрешения записи регистра сдвига является стробирующим входом спецпроцессора, a N-разрядный выход регистра сдвига является вторым выходом спецпроцессора, двухразрядный управляющий вход процессорного блока иерархического уровня N является управляющим входом спецпроцессора, каждый блок иерархического уровня J (J=1, …N) состоит из идентичных первого и второго блоков иерархического уровня J-1, первого элемента «ИЛИ», входы которого подключены к первым выходам первого и второго блоков иерархического уровня J-1, а выход является первым выходом блока иерархического уровня J, первого мультиплексора, первый информационный вход которого подключен ко второму выходу второго блока иерархического уровня J-1, второй информационный вход первого мультиплексора 14 подключен ко второму выходу первого блока иерархического уровня J-1, а управляющий вход первого мультиплексора подключен к первому выходу первого блока иерархического уровня J-1, при этом выход первого мультиплексора является вторым выходом блока иерархического уровня J, управляющий и информационный входы первого и второго блоков иерархического уровня J-1 одновременно являются одноименными входами и блоков иерархического уровня J, младший разряд N-J+1-разрядных входов задания физического адреса первого и второго блоков иерархического уровня J-1 подключен соответственно к потенциалам логического нуля и логической единицы, остальные N-J разрядов первого и второго блоков иерархического уровня J-1 являются N-J-разрядным входом задания физического адреса блока иерархического уровня J, базовый блок иерархического уровня 0 содержит первый RS триггер, выход которого является первым выходом базового блока, вход синхронной установки первого RS триггера подключен к инверсному выходу второго элемента «ИЛИ», входы которого подключены к двухразрядному управляющему входу базового блока, вход синхронного сброса первого RS триггера подключен к выходу первого элемента «И», входы которого подключены к старшему разряду управляющего входа базового блока и выходу второго RS триггера, инверсный выход которого является вторым выходом базового блока, при этом инверсные входы элемента «И» подключены к младшему разряду управляющего входа и к выходу элемента «исключающее ИЛИ», вход синхронного сброса второго RS триггера подключен к выходу второго элемента «И», входы которого подключены к младшему разряду управляющего входа базового блока и выходу элемента «исключающее ИЛИ», входы которого подключены к старшему разряду информационного входа базового блока и к выходу второго мультиплексора, N-разрядный информационный вход которого является входом задания физического адреса базового блока, управляющий вход второго мультиплексора подключен к K младшим разрядам информационного входа базового блока, вход синхронной установки второго RS триггера подключен к выходу третьего элемента «ИЛИ», инверсные входы которого подключены к выходу четвертого элемента «ИЛИ» и к младшему разряду управляющего входа базового блока, входы четвертого элемента «ИЛИ» подключены к выходу второго мультиплексора и к инверсному выходу третьего элемента «И», входы которого подключены к управляющему входу базового блока, входы синхронизации регистра сдвига и всех RS триггеров подключены к выходу усилителя синхросигнала.

На фиг.1 приведена схема базового блока предлагаемого спецпроцессора.

На фиг.2 раскрыта рекурсивная схема построения блока иерархического уровня J (J=1, …, N) из двух блоков иерархического уровня J-1.

На фиг.3 приведена схема спецпроцессора.

На фиг.4 представлен вариант схемы управления спецпроцессором.

На фиг.5 приведена временная диаграмма, иллюстрирующая функционирование спецпроцессора в совокупности с представленным на фиг.4 вариантом устройства управления.

Предлагаемый спецпроцессор содержит усилитель синхросигнала 1, вход которого является входом 2 синхронизации спецпроцессора, процессорный блок 3 иерархического уровня N, K+1-разрядный информационный вход которого является информационным входом 4 спецпроцессора, а первый выход является первым выходом 5 спецпроцессора, при этом в спецпроцессор дополнительно введен N-разрядный регистр 6 сдвига, информационный вход которого подключен ко второму выходу процессорного блока 3 иерархического уровня N, вход разрешения записи регистра 6 сдвига является стробирующим входом 7 спецпроцессора, а N-разрядный выход регистра 6 сдвига является вторым выходом 8 спецпроцессора, двухразрядный управляющий вход процессорного блока 3 иерархического уровня N является управляющим входом 9 спецпроцессора, каждый блок иерархического уровня J(J=1, …N) состоит из идентичных первого 10 и второго 11 блоков иерархического уровня J-1, первого элемента «ИЛИ» 12, входы которого подключены к первым выходам первого 10 и второго 11 блоков иерархического уровня J-1, а выход является первым выходом 13 блока иерархического уровня J, первого мультиплексора 14, первый информационный вход которого подключен ко второму выходу второго блока 11 иерархического уровня J-1, второй информационный вход первого мультиплексора 14 подключен ко второму выходу первого блока 10 иерархического уровня J-1, а управляющий вход первого мультиплексора 14 подключен к первому выходу первого блока 10 иерархического уровня J-1, при этом выход первого мультиплексора 14 является вторым выходом 15 блока иерархического уровня J, управляющий и информационный входы первого 10 и второго 11 блоков иерархического уровня J-1 одновременно являются одноименными входами 16 и 17 блоков иерархического уровня J, младший разряд N-J+1-разрядных входов задания физического адреса первого 10 и второго 11 блоков иерархического уровня J-1 подключен соответственно к потенциалам логического нуля и логической единицы, остальные N-J разрядов первого 10 и второго 11 блоков иерархического уровня J-1 являются N-J-разрядным входом 18 задания физического адреса блока иерархического уровня J, базовый блок иерархического уровня 0 содержит первый RS триггер 19, выход которого является первым выходом 20 базового блока, вход синхронной установки первого RS триггера 19 подключен к инверсному выходу второго элемента «ИЛИ» 21, входы которого подключены к двухразрядному управляющему входу 22 базового блока, вход синхронного сброса первого RS триггера 19 подключен к выходу первого элемента «И» 23, входы которого подключены к старшему разряду управляющего входа 22 базового блока и выходу второго RS триггера 24, инверсный выход которого является вторым выходом 25 базового блока, при этом инверсные входы элемента 23 «И» подключены к младшему разряду управляющего входа 22 и к выходу элемента «исключающее ИЛИ» 26, вход синхронного сброса второго RS триггера 24 подключен к выходу второго элемента «И» 27, входы которого подключены к младшему разряду управляющего входа 22 базового блока и выходу элемента 26 «исключающее ИЛИ», входы которого подключены к старшему разряду информационного входа 28 базового блока и к выходу второго мультиплексора 29, N-разрядный информационный вход которого является входом 30 задания физического адреса базового блока, управляющий вход второго мультиплексора 29 подключен к K младшим разрядам информационного входа 28 базового блока, вход синхронной установки второго RS триггера 24 подключен к выходу третьего элемента «ИЛИ» 31, инверсные входы которого подключены к выходу четвертого элемента «ИЛИ» 32 и к младшему разряду управляющего входа 22 базового блока, входы четвертого элемента «ИЛИ» 32 подключены к выходу второго мультиплексора 29 и к инверсному выходу третьего элемента «И» 33, входы которого подключены к управляющему входу 22 базового блока, входы синхронизации регистра 6 сдвига и всех RS триггеров подключены к выходу 34 усилителя синхросигнала 1.

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

В процессе работы предлагаемого спецпроцессора непосредственно используется естественная кодировка булевой функции, представленной в конъюнктивной нормальной форме. Запись функции начинается с маркера, в качестве которого использован восклицательный знак «!». За маркером начала следуют записанные через запятую «,» литералы - номера переменных без знака или со знаком «-», входящих в одну дизъюнкцию. Использование знака «-» означает, что в дизъюнкции используется инверсное значение переменной. Запись переменных, принадлежащих дизъюнкции, заканчивается маркером точка с запятой «;» в случае, если дизъюнкция не является последней, и маркером точка «.», если дизъюнкция является последней в записи функции.

Например, функция

F=(¬X₀+¬X₂+¬X₁+X₃+X₄+¬X₅+X₇)(X₀+X₁+X₂)(X₆+¬X₄+X₅+¬X₃+¬X₇), записывается в эквивалентном виде

!-0,-2,-1,3,4,-5,7;0,1,2;6,-4,5,-3,-7.

Для рассматриваемой булевой функции N=8 (K=3), М=3, L=14.

Спецпроцессор и его устройство управления оперируют со следующей последовательностью K+3-разрядных информационных слов в буферном ОЗУ:

/0!/-0,/-2,/-1,/3,/4,/-5,/7;/0,/1,/2;/6,/-4,/5,/-3/-7./

Информационные слова, имеющие последовательные адреса, разделены маркером «/».

Используемые при записи формулы знаки препинания кодируются следующим образом «!»=>00, «,»=>01, «;»=>10, «.»=>11. Эти двухразрядные коды являются кодами операций базовых блоков спецпроцессора. Коды управления передаются из буферного ОЗУ в базовые блоки. Буферирование осуществляется на двух D триггерах 35, 36. Заметим, что представленный на фиг.4 вариант устройства управления преобразует код 11 в последовательность из двух кодов 10 и 11, эта операция осуществляется с использованием RS триггера 37 и ассоциированных с ним логических элементов.

Значения кодов СОР_М, nX_M, INV_M, выбираемых из буферного ОЗУ по последовательным адресам adr, представлены на временной диаграмме фиг.5. СОР_М является двухразрядным кодом маркеров, использованных при записи булевой функции. nX_M - номера кодированных K разрядами переменных, использованных в дизъюнкциях. Значение INV_M кодируется единицей, если при записи дизъюнкции используется инверсия переменной.

Спецпроцессор имеет 2^N базовых блоков, каждый из которых имеет индивидуальный N-разрядный физический номер на информационном входе второго мультиплексора 29.

Младшие K разрядов K+1-разрядного кода на информационном входе 28 базового блока адресуют один из разрядов N-разрядного физического номера. В основном режиме работы спецпроцессора содержимое выбранного разряда nX физического номера сравнивается с INV содержимым старшего разряда K+1-разрядного кода на информационном входе 28 базового блока. Сравнение осуществляется элементом 26 суммирования по модулю два. Если во время действия кода операции «01» на входе 22 базового блока в обрабатываемой дизъюнкции зафиксировано хотя бы одно неравенство, это приводит к сбросу второго RS триггера 24, что запрещает последующий сброс первого RS триггера 19. Если во время действия кода операции «10» второй RS триггер 24 остается установленным и на выходе элемента 26 сравнения присутствует потенциал логического нуля, соответствующий равенству, происходит сброс первого RS триггера 19, и это означает, что кодировка физического номера данного базового блока соответствует невыполняющему набору переменных. Фронт синхросигнала, по которому осуществляется сброс первого RS триггера 19 в базовом блоке с номером 0, на диаграмме фиг.5 отмечен первым курсором. Каждая «правильная» дизъюнкция, в которой переменная может присутствовать либо с инверсией, либо без инверсии, порождает хотя бы один невыполняющий набор. Если в «правильной» дизъюнкции отсутствуют литералы, соответствующие R переменным, такой набор может привести к сбросу первых RS триггеров 19 в 2^R базовых блоках. Булевая функция выполнима, если после ее обработки хотя бы в одном базовом блоке первый RS триггер 19 останется в установленном состоянии.

В каждом из базовых блоков установка второго RS триггера 24 выполняется кодами операции «00» и «10» перед началом обработки каждой дизъюнкции. Установка первого RS триггера 19 инициируется кодом операции «00», который вызывает появление единичного потенциала на инверсном выходе второго элемента «ИЛИ» 21. Код операции «11» переводит второй RS триггер 24 и ассоциированные с ним логические элементы 26, 27, 31, 32 в режим эмуляции D триггера. Этот D триггер осуществляет буферирование информации, поступающей с выхода второго мультиплексора 29 на второй выход 25 базового блока.

В рассматриваемом варианте устройства управления код операции «11» переводит загружаемый счетчик в режим счета. Это приводит к подаче последовательности кодов от 0 до N-1 на информационный вход 4 спецпроцессора, что позволяет передать физический номер базового блока на его второй выход 25. Момент начала считывания выполняющего набора функции в регистр 6 сдвига отмечен на временной диаграмме фиг.5 вторым курсором. Высокий уровень сигнала STROB разрешает запись информации в регистр 6 сдвига.

Первые элементы «ИЛИ» 12 и первые мультиплексоры 14 блоков всех уровней иерархии образуют самонастраивающийся коммутатор-мультиплексор, который осуществляет побитную передачу на информационный вход регистра 6 сдвига выполняющего набора булевой функции. Этим набором является младший физический номер базового блока, среди всех базовых блоков первые RS триггеры 19 которых находятся в установленном состоянии. По завершении работы спецпроцессора код SET на выходе 8 регистра 6 сдвига соответствует выполняющему набору для обработанной булевой функции при условии, что на выходе 5 спецпроцессора установлен уровень логической единицы. В рассмотренном примере выполняющим набором является: X₀=1, X₁=0, X₂=0, X₃=0, Х₄=0, Х₅=0, Х₆=0, Х₇=0. Момент окончания обработки спецпроцессором рассматриваемой булевой функции на временной диаграмме фиг.5 отмечен третьим курсором.

За счет высокой степени параллелизма обработка булевой функции занимает L+N+4 такта.

Изобретение относится к вычислительной технике, в частности к специализированным процессорам с высокой степенью параллелизма. Технический результат заключается в снижении сложности спецпроцессора за счет упрощения структуры процессорного блока, в расширении функциональных возможностей за счет снятия ограничений на число дизъюнкций в булевой функции и в повышении скорости решения задачи о выполнимости булевых функций за счет отказа от этапа предварительной настройки спецпроцессора. Спецпроцессор содержит усилитель синхросигнала, N-разрядный регистр сдвига, процессорный блок иерархического уровня N, состоящий из блоков иерархического уровня J (J=1, …N), каждый из которых состоит из идентичных первого и второго блоков иерархического уровня J-1, первого элемента «ИЛИ» и первого мультиплексора, и базового блока иерархического уровня 0, содержащий первый и второй RS триггеры, второй, третий и четвертый элементы «ИЛИ», первый, второй и третий элементы «И», элемент «исключающее ИЛИ», второй мультиплексор. 5 ил.

Высокопараллельный спецпроцессор для решения задачи о выполнимости булевых формул, характеризующийся тем, что содержит усилитель синхросигнала, вход которого является входом синхронизации спецпроцессора, процессорный блок иерархического уровня N, K+1-разрядный информационный вход которого является информационным входом спецпроцессора, а первый выход является первым выходом спецпроцессора, при этом в спецпроцессор дополнительно введен N-разрядный регистр сдвига, информационный вход которого подключен ко второму выходу процессорного блока иерархического уровня N, вход разрешения записи регистра сдвига является стробирующим входом спецпроцессора, а N-разрядный выход регистра сдвига является вторым выходом спецпроцессора, двухразрядный управляющий вход процессорного блока иерархического уровня N является управляющим входом спецпроцессора, каждый блок иерархического уровня J (J=1, …N) состоит из идентичных первого и второго блоков иерархического уровня J-1, первого элемента ИЛИ, входы которого подключены к первым выходам первого и второго блоков иерархического уровня J-1, а выход является первым выходом блока иерархического уровня J, первого мультиплексора, первый информационный вход которого подключен ко второму выходу второго блока иерархического уровня J-1, второй информационный вход первого мультиплексора 14 подключен ко второму выходу первого блока иерархического уровня J-1, а управляющий вход первого мультиплексора подключен к первому выходу первого блока иерархического уровня J-1, при этом выход первого мультиплексора является вторым выходом блока иерархического уровня J, управляющий и информационный входы первого и второго блоков иерархического уровня J-1 одновременно являются одноименными входами и блоков иерархического уровня J, младший разряд N-J+1-разрядных входов задания физического адреса первого и второго блоков иерархического уровня J-1 подключен соответственно к потенциалам логического нуля и логической единицы, остальные N-J разрядов первого и второго блоков иерархического уровня J-1 являются N-J-разрядным входом задания физического адреса блока иерархического уровня J, базовый блок иерархического уровня 0 содержит первый RS триггер, выход которого является первым выходом базового блока, вход синхронной установки первого RS триггера подключен к инверсному выходу второго элемента «ИЛИ», входы которого подключены к двухразрядному управляющему входу базового блока, вход синхронного сброса первого RS триггера подключен к выходу первого элемента «И», входы которого подключены к старшему разряду управляющего входа базового блока и выходу второго RS триггера, инверсный выход которого является вторым выходом базового блока, при этом инверсные входы элемента «И» подключены к младшему разряду управляющего входа и к выходу элемента «Исключающее ИЛИ», вход синхронного сброса второго RS триггера подключен к выходу второго элемента «И», входы которого подключены к младшему разряду управляющего входа базового блока и выходу элемента «Исключающее ИЛИ», входы которого подключены к старшему разряду информационного входа базового блока и к выходу второго мультиплексора, N-разрядный информационный вход которого является входом задания физического адреса базового блока, управляющий вход второго мультиплексора подключен к K младшим разрядам информационного входа базового блока, вход синхронной установки второго RS триггера подключен к выходу третьего элемента «ИЛИ», инверсные входы которого подключены к выходу четвертого элемента «ИЛИ» и к младшему разряду управляющего входа базового блока, входы четвертого элемента «ИЛИ» подключены к выходу второго мультиплексора и к инверсному выходу третьего элемента «И», входы которого подключены к управляющему входу базового блока, входы синхронизации регистра сдвига и всех RS триггеров подключены к выходу усилителя синхросигнала.