СПЕЦПРОЦЕССОР ДЛЯ ПОИСКА ГАМИЛЬТОНОВЫХ ЦИКЛОВ В ГРАФАХ Российский патент 2014 года по МПК G06F17/00 G06F15/163 

Изобретение относится к вычислительной технике и направлено на построение эффективного спецпроцессора, осуществляющего поиск Гамильтонова цикла в графе, заданном матрицей смежностей, хранящейся в памяти. Для кодирования номеров N вершин графа используется к разрядов, 2^k≥N.

Известны вычислительная система и методы для решения задачи коммивояжера, основанные на поиске Гамильтоновых циклов в графах (US 6904421 B2, 07.01.2005).

Вычислительная система содержит процессор, блоки памяти ОЗУ и ПЗУ, блоки ввода и вывода информации, блок сетевого взаимодействия, резидентные и сменяемые блоки долговременной памяти. Для решения задачи предлагаются быстрые «генетические» алгоритмы, позволяющие получать приближенное решение за ограниченное время.

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

Известна вычислительная система, сконфигурированная для решения с большой скоростью вычислительно сложных NP-полных задач, таких как задача поиска Гамильтоновых циклов в графах, наиболее близкая по своей технической сущности к предлагаемому изобретению и выбранная в качестве прототипа (US 6636840 B1, 21.10.2003).

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

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

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

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

На фиг.1 приведена схема процессорного элемента спецпроцессора.

На фиг.2 представлена общая схема спецпроцессора для поиска Гамильтоновых циклов в графах.

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

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

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

Предлагаемый спецпроцессор для поиска Гамильтоновых циклов в графах содержит N идентичных процессорных элементов, каждый из которых в своем составе имеет k-разрядный регистр 1, информационный вход которого подключен к выходу k-разрядного первого мультиплексора 2, первый информационный вход которого подключен к выходу второго k-разрядного мультиплексора 3, первый элемент «ИЛИ» 4, входы которого соединены с k-1 старшими разрядами второго информационного входа первого мультиплексора 2; второй 5 и третий 6 элементы «ИЛИ», вход и инверсный вход которых соединены с младшим разрядом второго входа первого мультиплексора 2, кроме того, входы второго 5 и третьего 6 элементов «ИЛИ» подключены в выходу первого элемента «ИЛИ» 4; k-разрядный вычитающий счетчик 7, старшие разряды информационного входа которого соединены с k-1 старшими разрядами второго информационного входа первого мультиплексора 2, а младший разряд упомянутого входа подключен к выходу третьего элемента «ИЛИ» 6; четвертый элемент «ИЛИ» 8, выходы которого подключены к разрядам выхода счетчика 7, а выход соединен с установочным входом первого RS триггера 9, входом первого элемента «И» 10 и входом пятого элемента «ИЛИ» 11, инверсный выход которого соединен с входом сброса первого RS триггера 9 и входом второго элемента «И» 12, другой вход которого подключен к выходу первого RS триггера 9, а выход соединен с первыми входами шестого 13 и седьмого 14 элементов «ИЛИ», в свою очередь выход первого элемента «И» 10 соединен с вторым входом шестого элемента «ИЛИ» 13, входом разрешения счетчика 7 и первым информационным входом третьего мультиплексора 15, выход которого соединен с вторым входом седьмого элемента «ИЛИ» 14, выход которого соединен с входом третьего элемента «И» 16, другой вход которого подключен к выходу второго элемента «ИЛИ» 5, а выход которого соединен с управляющим входом второго мультиплексора 3 и первым входом восьмого элемента «ИЛИ» 17, выход которого соединен с первым входом четвертого элемента «И» 18, выход которого соединен с входом разрешения синхронной записи регистра 1, при этом управляющий вход асинхронной записи регистра 1 и управляющий вход первого мультиплексора 2 соединены с входом асинхронного сброса счетчика 7; пятый элемент «И» 19, вход которого соединен с вторым информационным входом третьего мультиплексора 15, инверсный вход соединен с управляющим входом упомянутого мультиплексора 15, а выход соединен с информационным входом первого D триггера 20, входом синхронной загрузки счетчика 7 и первым входом девятого элемента «ИЛИ» 21, второй вход которого соединен с входом синхронного сброса счетчика 7; шестой элемент «И» 22, входы которого соединены с управляющим входом третьего мультиплексора 15 и выходом первого D триггера 20, а инверсный выход соединен с входом седьмого элемента «И» 23, другой вход которого соединен с входом пятого элемента «ИЛИ» 11 и третьим входом шестого элемента «ИЛИ» 13, а инверсный выход соединен с входом первого элемента «И» 10; восьмой элемент «И» 24, входы которого подключены к выходам второго 5 и шестого 13 элементов «ИЛИ»; первую 25 и вторую 26 группы элементов «И», первые входы которых одновременно подключены к соответствующим разрядами выхода регистра 1, при этом все вторые входы элементов «И» первой 25 группы подключены к выходу первого элемента «И» 10; при этом на вторые информационные входы первых мультиплексоров 2 каждого процессорного элемента заведены k-разрядные индивидуальные константные значения от «0» до «N-1», задающие нумерацию процессорных элементов от «0» до «N-1»; на первый информационный вход второго мультиплексора 3 процессорного элемента с номером «N-1» заведено нулевое значение, а каждый первый информационный вход соответствующего мультиплексора других процессорных элементов подключен к выходу регистра 1 процессорного элемента, имеющего следующий (больший) номер; на вторые информационные входы вторых мультиплексоров 3 процессорных элементов, имеющих минимальный и максимальный номер, заведено нулевое значение, а второй информационный вход второго мультиплексора 3 других процессорных элементов подключен к выходу регистра 1 процессорного элемента, имеющего минимальный номер; вторые входы восьмого 17 и девятого 21 элементов «ИЛИ» процессорного элемента, имеющего максимальный номер подключены к потенциалу логического нуля, а каждые вторые входы упомянутых элементов «ИЛИ» остальных процессорных элементов подключены к выходам восьмого 17 и девятого 21 элементов «ИЛИ» процессорного элемента, имеющего следующий номер; все вторые входы элементов «И» второй группы 26 процессорного элемента, имеющего максимальный номер, подключены к выходу первого элемента «И» 10 процессорного элемента, имеющего минимальный номер, а все вторые входы упомянутой группы элементов «И», как и вторые входы третьего мультиплексора 15 каждого из остальных процессорных элементов, подключены к выходу первого элемента «И» 10 процессорного элемента, имеющего следующий номер; третий вход шестого элемента «ИЛИ» 13 процессорного элемента, имеющего минимальный номер, обнулен, а каждый третий вход упомянутого элемента «ИЛИ» остальных процессорных элементов подключен к выходу восьмого элемента «И» 24 процессорного элемента, имеющего предыдущий номер; выходы регистров 1 всех процессорных элементов вместе составляют первый Nk-разрядный выход 27 спецпроцессора; кроме того, спецпроцессор содержит десятый элемент «ИЛИ» 28, вторые D 29 и RS 30 триггеры, первый вход, информационный вход и вход синхронного сброса которых соединены и являются управляющим входом 31 спецпроцессора, второй вход десятого элемента «ИЛИ» 28 подключен выходу второго RS триггера 30, а выход соединен с входами асинхронного сброса счетчиков 7 всех процессорных элементов, выход второго D триггера 29 соединен с вторым информационным входом третьего мультиплексора 15 процессорного элемента, имеющего максимальный номер, и с инверсным входом девятого элемента «И» 32, вход которого является информационным входом 33 спецпроцессора, а выход соединен с управляющим входом третьего мультиплексора 15 всех процессорных элементов и первыми входами десятого элемента «И» 34, одиннадцатого 35 и двенадцатого 36 элементов «ИЛИ»; третий D триггер 37, информационный вход которого подключен к выходу десятого элемента «И» 34, а выход соединен с вторым входом одиннадцатого элемента «ИЛИ» 35, инверсный выход которого соединен с первым входом одиннадцатого элемента «И» 38, выход которого соединен с входом синхронной установки второго RS триггера 30 и является вторым выходом 39 спецпроцессора, а второй вход, как и второй вход двенадцатого элемента «ИЛИ» 36, подключен к выходу первого элемента «И» 10 процессорного элемента с номером «0», в свою очередь второй вход десятого элемента «И» 34 подключен к выходу первого элемента «И» 10 процессорного элемента с номером «1»; тринадцатый элемент «ИЛИ» 40, инверсный выход которого соединен с третьим входом двенадцатого элемента «ИЛИ» 36, а входы подключены к выходам первых элементов «И» 10 всех процессорных элементов, кроме процессорного элемента с номером «0»; двенадцатый элемент «И» 41, входы которого подключены к инверсным выходам четырнадцатого 42 и пятнадцатого 43 элементов «ИЛИ», причем инверсный выход пятнадцатого элемента «ИЛИ» 43, одновременно является третьим выходом 44 спецпроцессора, а входы упомянутого элемента 43 подключены к выходам четвертых элементов «ИЛИ» 8 каждого из процессорных элементов, в свою очередь входы четырнадцатого элемента «ИЛИ» 42 подключены к выходам вторых элементов «И» 12 всех процессорных элементов, за исключением процессорных элементов имеющих максимальный и минимальный номер; тринадцатый элемент «И» 45, входы которого подключены к выходу и инверсному выходу двенадцатых элементов «ИЛИ» 36 и «И» 41 соответственно, а выход соединен с вторыми входами четвертых элементов «И» 18 каждого из процессорных элементов, кроме процессорного элемента, имеющего максимальный номер; первую 46 и вторую 47 группы элементов «ИЛИ», входы каждого из которых подключены к выходу соответствующего элемента «И» первой 25 или второй 26, соответственно, группы в каждом процессорном элементе, а выходы являются k-разрядными четвертым 48 и пятым 49 выходами спецпроцессора; причем входы синхронизации всех триггеров, регистров и счетчиков спецпроцессора подключены к входу 50 опорной частоты.

Начало работы инициируется подачей сигнала START (фиг.5) на управляющий вход 31 спецпроцессора. Этот сигнал вызывает запись в регистры 1 физических номеров, константно заведенных на вторые входы первых мультиплексоров 2 процессорных элементов. После окончания сигнала START происходит запись физического номера в счетчик 7 процессорного элемента, имеющего максимальный номер, этот процессорный элемент становится ведущим. Содержимое регистра 1 ведущего процессорного элемента является номером (ROW) строки считываемого из памяти элемента матрицы смежностей графа. Содержимое регистра 1 процессорного элемента, физический номер которого по модулю N меньше на единицу, является номером (COL) столбца считываемого из памяти элемента матрицы смежностей графа. На следующем такте содержимое счетчика 7 ведущего процессорного элемента уменьшается на единицу.

Первая группа 46 элементов «ИЛИ» вместе с первыми группами 25 элементов «И» процессорных элементов являются информационной частью k-разрядного мультиплексора, посредством которого из номеров вершин записанных в регистрах 1 процессорных элементов на четвертом выходе 48 спецпроцессора, формируется номер (ROW) строки для обращения к матрице смежностей хранимой в памяти. В свою очередь вторая группа 47 элементов «ИЛИ» вместе со вторыми группами 26 элементов «И» процессорных элементов являются информационной частью k-разрядного мультиплексора, посредством которого на пятом выходе 49 спецпроцессора формируется номер (COL) столбца матрицы смежностей.

Если код выбранного элемента матрицы смежности соответствует отсутствию связи между вершинами графа, декодер подает сигнал логической единицы на информационный вход 33 спецпроцессора. Это приводит к тому, что на выходе девятого элемента «И» 32 вырабатывается сигнал BREAK=1, что приводит к циклическому сдвигу содержимого регистров 1 по процессорным элементам, номера которых меньше номера ведущего процессорного элемента. При этом ведущий процессорный элемент сохраняет свой статус. Циклический сдвиг по выбранному подмножеству процессорных элементов организуется при соответствующем управлении вторыми мультиплексорами 3 процессорных элементов.

Если выбранный элемент матрицы содержит код смежности вершин графа, то осуществляется запись физического номера в счетчик 7 ведомого процессорного элемента, в результате чего он становится ведущим. Исключение составляет процессорный элемент с физическим номером «0» - в его счетчик 7 всегда записывается единица, что достигается посредством первого 4 и третьего 6 элементов «ИЛИ».

В графе DC временной диаграммы, на фиг.5, проиллюстрированы состояния счетчиков 7 процессорных элементов по тактам работы спецпроцессора.

При однобитной кодировке элементов матрицы смежностей графа, представленной на фиг.3, декодер отсутствия связности вершин является инвертором. В матрице, представленной на фиг.4, отсутствие связности вершин кодируется нулем, а связность единицей.

Выработка единичного уровня сигнала (NEW_H) на втором выходе 39 спецпроцессора свидетельствует об обнаружении Гамильтонова цикла в обрабатываемом графе. Искомый цикл, заданный последовательностью номеров вершин графа, в регистрах 1 процессорных элементов и присутствующих на первом Nk-разрядном выходе 27 спецпроцессора фиксируется в регистре, фиг.3. С Nk-разрядного выхода (HC) этого регистра найденный цикл может быть считан.

Для обеспечения корректности заложенного в спецпроцессор алгоритма перебора вариантов в такте, на котором обнулены выходы первых элементов «И» 10 всех процессорных элементов, выполняется компенсирующий сдвиг по регистрам 1. Этот сдвиг выполняется по процессорным элементам, номера которых меньше номера процессорного элемента, на выходе второго элемента «И» 12 которого в данном такте установлена единица. Состояние выхода упомянутого элемента определяется состояниям первого RS триггера 9 и приоритетной цепочкой, образованной первым 10, седьмым 23, восьмым 24 элементами «И» и шестым элементом «ИЛИ» 13 всех процессорных элементов.

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

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

Сигналом NEW_H о нахождении Гамильтонова цикла в графе является единичный уровень сигнала на выходе одиннадцатого элемента «И» 38 (являющегося вторым выходом спецпроцессора 39).

Исчерпание всех возможных вариантов обхода вершин графа устанавливается обнулением вычитающих счетчиков 7 всех процессорных элементов. При этом на инверсном выходе пятнадцатого элемента «ИЛИ» 43 (являющегося третьим выходом спецпроцессора 44) формируется сигнал END единичного уровня.

Состояние выхода упомянутого элемента определяется состояниям первого RS триггера 9 и приоритетной цепочкой, образованной первым 10, седьмым 23, восьмым 24 элементами «И» и шестым элементом «ИЛИ» 13 всех процессорных элементов.

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

Состояние выхода (СТ) счетчика числа тактов (фиг.3) на момент установления единичного уровня сигнала (END) на третьем выходе 44 спецпроцессора позволяет оценить, как время нахождения Гамильтонова цикла, так и время, за которое спецпроцессор определяет отсутствие искомого цикла в заданном графе.

Каждый из представленных на фиг.4 графов A, B, C, D, E, F, G, H отличается от предшествующего добавлением одного ребра. При этом число тактов необходимых для того, чтобы убедиться в отсутствии Гамильтонова цикла, возрастает. Для варианта A имеющего 9 ребер число циклов равно 94 (Time=94), а для варианта G с пятнадцатью ребрами (Time=677).

Вариант H графа, содержащий 16 ребер имеет Гамильтоновы циклы, первым из которых найден цикл HC=76054321, ребра которого выделены. Для отыскания упомянутого цикла потребовалось 10 тактов работы спецпроцессора. Для варианта H приведена таблица смежностей графа.

Изобретение относится к вычислительной технике и направлено на построение эффективного спецпроцессора, осуществляющего поиск Гамильтонова цикла в графе, заданном матрицей смежностей, хранящейся в памяти. Техническим результатом является увеличение скорости решения задачи отыскания Гамильтонова цикла в графе за счет параллельной работы процессорных элементов и уменьшение используемого объема памяти до величины, необходимой для хранения матрицы смежностей вершин обрабатываемого графа, за счет обращения в память только за информацией о смежности обрабатываемой пары вершин графа. Спецпроцессор для поиска Гамильтоновых циклов в графах содержит N идентичных процессорных элементов, каждый из которых состоит из регистра, 3-х мультиплексоров, вычитающего счетчика, 9 элементов «ИЛИ», 8 элементов «И», 2-х групп элементов «И», RS триггера и D триггера, 6 элементов «ИЛИ», две группы элементов «ИЛИ», 5 элементов «И», RS триггер и два D триггера. 5 ил.

Спецпроцессор для поиска Гамильтоновых циклов в графах, характеризующийся тем, что содержит N идентичных процессорных элементов, каждый из которых в своем составе имеет k-разрядный регистр 1, информационный вход которого подключен к выходу k-разрядного первого мультиплексора 2, первый информационный вход которого подключен к выходу второго k-разрядного мультиплексора 3, первый элемент «ИЛИ» 4, входы которого соединены с k-1 старшими разрядами второго информационного входа первого мультиплексора 2; второй 5 и третий 6 элементы «ИЛИ», вход и инверсный вход которых соединены с младшим разрядом второго входа первого мультиплексора 2, кроме того, входы второго 5 и третьего 6 элементов «ИЛИ» подключены в выходу первого элемента «ИЛИ» 4; k-разрядный вычитающий счетчик 7, старшие разряды информационного входа которого соединены с k-1 старшими разрядами второго информационного входа первого мультиплексора 2, а младший разряд упомянутого входа подключен к выходу третьего элемента «ИЛИ» 6; четвертый элемент «ИЛИ» 8, выходы которого подключены к разрядам выхода счетчика 7, а выход соединен с установочным входом первого RS триггера 9, входом первого элемента «И» 10 и входом пятого элемента «ИЛИ» 11, инверсный выход которого соединен с входом сброса первого RS триггера 9 и входом второго элемента «И» 12, другой вход которого подключен к выходу первого RS триггера 9, а выход соединен с первыми входами шестого 13 и седьмого 14 элементов «ИЛИ», в свою очередь, выход первого элемента «И» 10 соединен с вторым входом шестого элемента «ИЛИ» 13, входом разрешения счетчика 7 и первым информационным входом третьего мультиплексора 15, выход которого соединен с вторым входом седьмого элемента «ИЛИ» 14, выход которого соединен с входом третьего элемента «И» 16, другой вход которого подключен к выходу второго элемента «ИЛИ» 5, а выход которого соединен с управляющим входом второго мультиплексора 3 и первым входом восьмого элемента «ИЛИ» 17, выход которого соединен с первым входом четвертого элемента «И» 18, выход которого соединен с входом разрешения синхронной записи регистра 1, при этом управляющий вход асинхронной записи регистра 1 и управляющий вход первого мультиплексора 2 соединены с входом асинхронного сброса счетчика 7; пятый элемент «И» 19, вход которого соединен с вторым информационным входом третьего мультиплексора 15, инверсный вход соединен с управляющим входом упомянутого мультиплексора 15, а выход соединен с информационным входом первого D триггера 20, входом синхронной загрузки счетчика 7 и первым входом девятого элемента «ИЛИ» 21, второй вход которого соединен с входом синхронного сброса счетчика 7; шестой элемент «И» 22, входы которого соединены с управляющим входом третьего мультиплексора 15 и выходом первого D триггера 20, а инверсный выход соединен с входом седьмого элемента «И» 23, другой вход которого соединен с входом пятого элемента «ИЛИ» 11 и третьим входом шестого элемента «ИЛИ» 13, а инверсный выход соединен с входом первого элемента «И» 10; восьмой элемент «И» 24, входы которого подключены к выходам второго 5 и шестого 13 элементов «ИЛИ»; первую 25 и вторую 26 группы элементов «И», первые входы которых одновременно подключены к соответствующим разрядам выхода регистра 1, при этом все вторые входы элементов «И» первой 25 группы подключены к выходу первого элемента «И» 10; при этом на вторые информационные входы первых мультиплексоров 2 каждого процессорного элемента заведены k-разрядные индивидуальные константные значения от «0» до «N-1», задающие нумерацию процессорных элементов от «0» до «N-1»; на первый информационный вход второго мультиплексора 3 процессорного элемента с номером «N-1» заведено нулевое значение, а каждый первый информационный вход соответствующего мультиплексора других процессорных элементов подключен к выходу регистра 1 процессорного элемента, имеющего следующий (больший) номер; на вторые информационные входы вторых мультиплексоров 3 процессорных элементов, имеющих минимальный и максимальный номер, заведено нулевое значение, а второй информационный вход второго мультиплексора 3 других процессорных элементов подключен к выходу регистра 1 процессорного элемента, имеющего минимальный номер; вторые входы восьмого 17 и девятого 21 элементов «ИЛИ» процессорного элемента, имеющего максимальный номер, подключены к потенциалу логического нуля, а каждые вторые входы упомянутых элементов «ИЛИ» остальных процессорных элементов подключены к выходам восьмого 17 и девятого 21 элементов «ИЛИ» процессорного элемента, имеющего следующий номер; все вторые входы элементов «И» второй группы 26 процессорного элемента, имеющего максимальный номер, подключены к выходу первого элемента «И» 10 процессорного элемента, имеющего минимальный номер, а все вторые входы упомянутой группы элементов «И», как и вторые входы третьего мультиплексора 15 каждого из остальных процессорных элементов, подключены к выходу первого элемента «И» 10 процессорного элемента, имеющего следующий номер; третий вход шестого элемента «ИЛИ» 13 процессорного элемента, имеющего минимальный номер, обнулен, а каждый третий вход упомянутого элемента «ИЛИ» остальных процессорных элементов подключен к выходу восьмого элемента «И» 24 процессорного элемента, имеющего предыдущий номер; выходы регистров 1 всех процессорных элементов вместе составляют первый Nk-разрядный выход 27 спецпроцессора; кроме того, спецпроцессор содержит десятый элемент «ИЛИ» 28, вторые D 29 и RS 30 триггеры, первый вход, информационный вход и вход синхронного сброса которых соединены и являются управляющим входом 31 спецпроцессора, второй вход десятого элемента «ИЛИ» 28 подключен выходу второго RS триггера 30, а выход соединен с входами асинхронного сброса счетчиков 7 всех процессорных элементов, выход второго D триггера 29 соединен с вторым информационным входом третьего мультиплексора 15 процессорного элемента, имеющего максимальный номер, и с инверсным входом девятого элемента «И» 32, вход которого является информационным входом 33 спецпроцессора, а выход соединен с управляющим входом третьего мультиплексора 15 всех процессорных элементов и первыми входами десятого элемента «И» 34, одиннадцатого 35 и двенадцатого 36 элементов «ИЛИ»; третий D триггер 37, информационный вход которого подключен к выходу десятого элемента «И» 34, а выход соединен с вторым входом одиннадцатого элемента «ИЛИ» 35, инверсный выход которого соединен с первым входом одиннадцатого элемента «И» 38, выход которого соединен с входом синхронной установки второго RS триггера 30 и является вторым выходом 39 спецпроцессора, а второй вход, как и второй вход двенадцатого элемента «ИЛИ» 36, подключен к выходу первого элемента «И» 10 процессорного элемента с номером «0», в свою очередь, второй вход десятого элемента «И» 34 подключен к выходу первого элемента «И» 10 процессорного элемента с номером «1»; тринадцатый элемент «ИЛИ» 40, инверсный выход которого соединен с третьим входом двенадцатого элемента «ИЛИ» 36, а входы подключены к выходам первых элементов «И» 10 всех процессорных элементов, кроме процессорного элемента с номером «0»; двенадцатый элемент «И» 41, входы которого подключены к инверсным выходам четырнадцатого 42 и пятнадцатого 43 элементов «ИЛИ», причем инверсный выход пятнадцатого элемента «ИЛИ» 43 одновременно является третьим выходом 44 спецпроцессора, а входы упомянутого элемента 43 подключены к выходам четвертых элементов «ИЛИ» 8 каждого из процессорных элементов, в свою очередь, входы четырнадцатого элемента «ИЛИ» 42 подключены к выходам вторых элементов «И» 12 всех процессорных элементов за исключением процессорных элементов, имеющих максимальный и минимальный номер; тринадцатый элемент «И» 45, входы которого подключены к выходу и инверсному выходу двенадцатых элементов «ИЛИ» 36 и «И» 41 соответственно, а выход соединен с вторыми входами четвертых элементов «И» 18 каждого из процессорных элементов, кроме процессорного элемента, имеющего максимальный номер; первую 46 и вторую 47 группы элементов «ИЛИ», входы каждого из которых подключены к выходу соответствующего элемента «И» первой 25 или второй 26, соответственно, группы в каждом процессорном элементе, а выходы являются k-разрядными четвертым 48 и пятым 49 выходами спецпроцессора; причем входы синхронизации всех триггеров, регистров и счетчиков спецпроцессора подключены к входу 50 опорной частоты.