Устройство для формирования субоптимального размещения и его оценки

Устройство для формирования субоптимального размещения и его оценки

Реферат

 

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

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании радиоэлектронной аппаратуры (РЭА), автоматизированных систем управления (АСУ) и средств электронной вычислительной техники (СЭВТ).

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а. с. N 1291957 СССР, кл. G 06 F 7/00, опубл. 23.02.87, БИ 7).

Недостатком указанного элемента является узкая область применения, обусловленная ограниченным числом критериев оценки степени оптимальности размещения.

Наиболее близкой к предлагаемому устройству по технической сущности является аппаратная модель для размещения элементов схемы в линейку, содержащая блок формирования перестановок, блок постоянной памяти, коммутатор, арифметико-логическое устройство (АЛУ), блок запоминания лучшего варианта, электронную модель графа (ЭМГ), два регистра сдвига, элемент ИЛИ и группу элементов ИЛИ (В.М. Курейчик, В.М. Глушань, Л. И. Щербаков. Комбинаторные аппаратные модели и алгоритмы в САПР. - М.: "Радио и связь", 1990. - С. 58-59).

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

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

Техническая задача решается тем, что в устройство для формирования субоптимального размещения и его оценки, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, электронную модель графа, группу элементов ИЛИ, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом арифметико-логического устройства, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом арифметико-логического устройства, выход переполнения первого регистра сдвига соединен с входом второго регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й (где n - количество вершин) подключены к первым и вторым входам элементов группы элементов ИЛИ с первого по n-й соответственно, выход переполнения второго регистра сдвига соединен с управляющим входом арифметико-логического устройства и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом первого регистра сдвига и с тактовым входом блока формирования перестановок, 1-й выход веса дуги электронной модели графа (l =1, 2, ..., m, где m - количество дуг) соединен с 1-м входом первого блока элементов ИЛИ, выход первого блока элементов ИЛИ соединен со вторым информационным входом арифметико-логического устройства, дополнительно введены дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группа элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, причем выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход второго блока элементов ИЛИ подключен к первому входу первого элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом первого элемента сравнения и с входом данных блока оперативной памяти, выход первого элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом первого элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом второго элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом первого элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход второго счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход третьего элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход первого счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу первого счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, второго счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу первого счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к пятому входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к третьему входу установки устройства, вход сброса триггера задания топологии подключен к четвертому входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен ко второму входу установки устройства, выход регистра длины связей подключен ко второму входу второго элемента сравнения и к первому входу вычитателя, первый вход второго элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход первого одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к первому входу установки устройства, l-й выход веса дуги электронной модели графа (l = 1, 2, ..., m) соединен с l-м входом второго блока элементов ИЛИ, выход второго элемента сравнения соединен с входом первого одновибратора, выход вычитателя соединен с выходом длины связей устройства, l-й выход дешифратора выбора дуги соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, выход l-го элемента группы элементов И соединен с l-м управляющим входом электронной модели графа, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, тактовый вход устройства соединен с первыми входами первого и второго элементов И, выходы элементов группы элементов ИЛИ с первого по n-й подключены к соответствующим входам соответствующих элементов группы элементов И.

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

Общие особенности изобретения состоят в следующем.

Предлагаемое устройство аналогично прототипу используется при моделировании комбинаторных задач проектирования РЭА. Устройство позволяет размещать невзвешенные графы в линейную топологическую модель (размещение в линейку). Дополнительно, в соответствии с заявляемой технической задачей, устройство может применяться при проектировании АСУ и СЭВТ для размещения взвешенных графов, представляющих сети алгоритмов (программных модулей), в линейной и кольцевой моделях и оценивать степень близости сформированного размещения к оптимальному.

Размещаемый объект (это может быть электрическая схема, сеть алгоритмов и т. д. ) представляется в виде орграфа G = <X, U>, вершины х_i Х которого соответствуют элементам схемы или алгоритмам, а дуги e_ijEXX задают связи между элементами (алгоритмами). Граф G задается матрицей смежности (n - количество вершин), элементы которой образуются по правилу где w_i,j может представлять количество связей между элементами схемы, объем данных, передаваемых от i-го к j-му алгоритму, интенсивность взаимодействия алгоритмов и т.д.

Топологическая модель для размещения (область размещения) в свою очередь задается матрицей расстояний D. Элементы матрицы расстояний для кольцевой модели образуются по формуле d_i,j = (j - i + n )mod n, а для линейной модели - по формуле d_i,j = |i-j|.Критерием оптимальности размещения является минимум суммарной длины L межэлементных связей орграфа G при его размещении в заданной модели с учетом весов его дуг. Минимально возможная длина связей L* для орграфа G независимо от топологической модели определяется по формуле где векторы, первый из которых содержит ненулевые элементы матрицы смежности А, расположенные по убыванию, а второй - ненулевые элементы матрицы расстояний D, расположенные по возрастанию; k - порядковый номер элемента; m = |E|n²-n - мощность множества дуг Е (количество дуг). Фактическая длина связей L для найденного размещения орграфа G всегда либо больше, либо равна длине L*, и степень оптимальности размещения можно определить по формуле = L - L*. (2) Порядок расчета значения длины L* и сущность предлагаемого критерия поясняются фиг. 2. Здесь на фиг. 2а представлен гипотетический орграф G с четырьмя вершинами х₁, х₂, х₃, x₄ (веса w_i,j указаны числами рядом с соответствующими дугами е_ij), на фиг. 2б изображена матрица смежности для заданного орграфа (i-я строка/столбец матрицы соответствуют вершине х_i+1 графа G), на фиг. 2в показана матрица расстояний для кольцевой топологической модели, а на фиг. 2г - для линейной. Фиг. 2д и 2е поясняют порядок формирования предельных вариантов размещения (для которых ) для кольца и для линейки соответственно. На фиг. 2ж записаны векторы и векторы для кольца и для линейки, а также показан расчет соответствующих им значений длины связей L* по формуле (1).

Устройство для формирования субоптимального размещения и его оценки (фиг. 1) содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок (БФП), блок 4 постоянной памяти, блок 5 запоминания лучшего варианта (БЗЛВ), коммутатор 6, АЛУ 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, счетчик 11 топологии, первый 12 и второй 13 счетчики расстояний, умножитель 14, сумматор 15, регистр 16 минимальной длины связей, первый элемент 17 сравнения, вычитатель 18, триггер 19 начала счета, триггер 23 режима, триггер 24 задания топологии, регистр 25 длины связей, второй элемент 26 сравнения, счетчик 27 дуг, дешифратор 28 блокировки дуги, регистр 29 номера дуги, регистр 30 минимального веса, электронную модель 31 графа, группу элементов ИЛИ 32.1 - 32. n, группу элементов И 33.1 - 33.m, первый 34 и второй 35 элементы И, второй блок элементов ИЛИ 36, третий элемент И 37, первый 41 и второй 42 одновибраторы, первый 43, второй 44 и третий 45 элементы задержки, первый блок элементов ИЛИ 46, причем выходы БФП 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами БЗЛВ 5, сигнализирующий выход БФП 3 соединен с установочным входом триггера 19 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом АЛУ 7, выход которого соединен с информационным входом БЗЛВ 5, а выход БЗЛВ 5 соединен с первым информационным входом АЛУ 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 32.1 - 32.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом АЛУ 7 и с управляющим входом БФП 3, тактовый вход 57 устройства соединен с входом регистра 1 сдвига, с тактовым входом БФП 3 и с первыми входами элементов И 34 и 35, выход счетчика 27 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 29 номера дуги, выход блока элементов ИЛИ 36 подключен к первому входу элемента 17 сравнения и к входу данных регистра 30 минимального веса, выход регистра 30 минимального веса соединен с вторым входом элемента 17 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 43 задержки соединен с входом установки регистра 30 минимального веса и с входом установки регистра 29 номера дуги, выход третьего элемента И 37 соединен с синхровходом регистра 30 минимального веса и с синхровходом регистра 29 номера дуги, выход регистра 29 номера дуги соединен с информационным входом дешифратора 28 блокировки дуги, выход переполнения счетчика 27 дуг соединен с разрешающим входом дешифратора 28 блокировки дуги, а также с входом элемента 43 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход элемента И 34 соединен со счетным входом счетчика 27 дуг и со входом элемента 44 задержки, выход которого соединен со вторым входом элемента И 37, первый вход которого соединен с выходом элемента 17 сравнения, второй вход элемента И 34 соединен с прямым выходом триггера 19 начала счета, который также соединен со вторым входом элемента И 35, третий вход элемента И 34 соединен с инверсным выходом триггера 23 режима, прямой выход которого соединен с третьим входом элемента И 35, выход элемента И 35 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход которого подключен к первому входу умножителя 14, выход счетчика 13 расстояний подключен к второму входу умножителя 14, выход которого подключен к первому входу сумматора 15, второй вход которого подключен к выходу регистра 16 минимальной длины связей и к второму входу вычитателя 18, выход сумматора 15 подключен к входу данных регистра 16 минимальной длины связей, выход элемента 45 задержки подключен к синхровходу регистра 16 минимальной длины связей, выход элемента И 35 и счетный вход счетчика 12 расстояний подключены к входу элемента 45 задержки, выход одновибратора 42 подключен к синхровходу счетчика 12 расстояний, выход переполнения которого подключен к счетным входам счетчика 11 топологии, счетчика 13 расстояний и к входу одновибратора 42, выход счетчика 11 топологии подключен к входу счетчика 12 расстояний, вход 51 данных устройства подключен ко входу данных счетчика 11 топологии, синхровход счетчика 11 топологии подключен к входу 52 установки устройства, прямой выход триггера 24 задания топологии подключен к разрешающему входу счетчика 11 топологии, установочный вход триггера 24 задания топологии подключен к входу 49 установки устройства, вход сброса триггера 24 задания топологии подключен к входу 50 установки устройства, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 23 режима, вход сброса которого подключен к входу 48 установки устройства, выход регистра 25 длины связей подключен ко второму входу элемента 26 сравнения и к первому входу вычитателя 18, первый вход элемента 26 сравнения подключен к выходу АЛУ 7 и входу данных регистра 25 длины связей, выход одновибратора 41 подключен к синхровходу регистра 25 длины связей, вход сброса триггера 19 начала счета подключен к входу 47 установки устройства, l-й выход дешифратора 8 выбора дуги (l = 1, 2, ...,m) соединен с l-м входом выбора дуги электронной модели 31 графа, l-й выход дешифратора 28 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 31 графа, l-й выход веса дуги электронной модели 31 графа соединен с l-м входом блока элементов ИЛИ 36 и l-м входом блока элементов ИЛИ 46, выход элемента И 33.l соединен с l-м управляющим входом электронной модели 31 графа, выход блока элементов ИЛИ 46 соединен со вторым информационным входом АЛУ 7, выход элемента 26 сравнения соединен с входом одновибратора 41, выходы элементов ИЛИ 32.1 - 32.n подключены к соответствующим входам элементов И 33.1 - 33.m, выход вычитателя 18 соединен с выходом 53 длины связей устройства.

Электронная модель 31 графа (фиг. 1) содержит m электронных моделей дуги, причем электронная модель 31.l дуги (l = 1, 2, ..., m) содержит триггер 20. l блокировки дуги, регистр 21.l веса дуги, регистр 22.l блокировки дуги, первый элемент И 38.l, второй элемент И 39.l, элемент ИЛИ 40.l, причем входы элемента И 38. l соединены с соответствующими входами 56.у и 56.z задания графа устройства (где у и z - номера соответственно начальной и конечной вершины l-й дуги графа), выход элемента И 38.l соединен с синхровходом регистра 21.l веса дуги и с установочным входом триггера 20.l блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги модели 31, вход данных регистра 21.l веса дуги соединен с входом 54.l веса дуги устройства, первый вход элемента ИЛИ 40.l соединен с l-м управляющим входом модели 31, а второй вход элемента ИЛИ 40.l соединен с выходом элемента И 39.l, первый вход которого соединен с прямым выходом триггера 20.l блокировки дуги и с разрешающим входом регистра 22.l блокировки дуги, второй вход элемента И 39. l соединен с l-м входом выбора дуги модели 31, вход сброса регистра 22.l блокировки дуги соединен с входом 55.l сброса устройства, выход регистра 22. l блокировки дуги соединен с l-м выходом веса дуги модели 31, который также соединен с выходом регистра 21.l веса дуги, выход элемента ИЛИ 40.l подключен к разрешающему входу регистра 21.l веса дуги.

Назначение элементов и блоков устройства (фиг.1) состоит в следующем.

Первый и второй регистры 1 и 2 сдвига необходимы для реализации последовательного перебора пар вершин орграфа G.

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

Блок 4 постоянной памяти хранит двоичные коды номеров позиций.

Блок 5 запоминания лучшего варианта служит для запоминания лучшего на настоящий момент варианта размещения.

Коммутатор 6 обеспечивает последовательное списывание из блока 4 кодов номеров выбираемых позиций для передачи их в АЛУ 7.

Арифметико-логическое устройство 7 необходимо для определения расстояния между позициями, в которые помещены выбранные вершины графа, и расчета длины связей L для формируемого варианта размещения. Данное устройство способно определять расстояния между позициями как для взвешенных графов, так и для невзвешенных.

Дешифратор 8 выбора дуги вместе со счетчиком 27 дуг предназначены для выбора из ЭМГ 31 дуги с номером, записанным в счетчике 27.

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

Блок 10 оперативной памяти служит для хранения весов w_i,j, дуг орграфа G в порядке возрастания их значений.

Счетчик 11 топологии необходим для подсчета и передачи счетчику 12 количества обрабатываемых элементов вектора с заданным значением (для кольцевой топологической модели общее число таких элементов постоянно и составляет n, для линейной это число уменьшается от n-1 для d'_k=1 до 1 для d'_k = n-1).

Первый счетчик 12 расстояний и второй счетчик 13 расстояний предназначены для организации перебора в возрастающем порядке ненулевых элементов матрицы расстояний D (таким образом на выходе счетчика 13 формируется вектор ).

Умножитель 14 необходим для умножения веса дуги из блока 10 оперативной памяти на расстояние между позициями топологической модели (элемент вектора ) из счетчика 13 расстояний.

Сумматор 15 предназначен для суммирования значений с умножителя 14 и регистра 16.

Регистр 16 минимальной длины связей хранит значение минимально возможной длины связей L* для заданного графа.

Первый элемент 17 сравнения служит для сравнения веса текущей дуги с наименьшим на данный момент весом, записанным в регистре 30.

Вычитатель 18 служит для нахождения степени оптимальности размещения по формуле (2). Значение L* поступает с выхода регистра 16 минимальной длины связей, L поступает с выхода регистра 25 длины связей.

Триггер 19 начала счета служит для индикации перехода из режима формирования размещения в режим его оценки.

Триггер 23 режима служит для хранения признака текущей операции. Если триггер 23 установлен в ноль - это означает запись весов дуг по возрастанию в блок 10 оперативной памяти, а в единицу - нахождение минимально возможной длины L* по формуле (1).

Триггер 24 задания топологии предназначен для задания вида топологической модели: если триггер 24 установлен в единицу - это означает выбор линейной модели, в ноль - кольцевой модели.

Регистр 25 длины связей предназначен для хранения значения длины связей L для наилучшего варианта размещения, сохраненного в БЗЛВ 5.

Второй элемент 26 сравнения предназначен для сравнения значения длины связей L лучшего на данный момент варианта размещения из регистра 25 с текущей длиной связи.

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

Регистр 29 номера дуги служит для хранения номера дуги с минимальным весом, выбранной в текущем цикле работы устройства.

Регистр 30 минимального веса необходим для хранения значения минимального на данный момент веса дуги.

Группа элементов ИЛИ 32.1 - 32.n необходима для объединения соответствующих сигналов с регистров 1 и 2.

Группа элементов И 33.1 - 33.m предназначена для выбора соответствующих дуг графа G по сигналам с элементов ИЛИ 32.1 - 32.n.

Первый и второй элементы И 34 и 35 необходимы для блокировки передачи импульсов с тактового входа 57 устройства на элементы и блоки, обеспечивающие упорядочение весов дуг графа в блоке 10 и подсчет значения длины связей L* соответственно.

Второй блок элементов ИЛИ 36 необходим для подключения веса текущей дуги к элементу 17 сравнения и регистру 30.

Третий элемент И 37 предназначен для блокировки прохождения импульсов на входы синхронизации регистров 29 и 30.

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

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

Первый элемент 43 задержки служит для задержки импульса переполнения со счетчика 27 дуг на время, достаточное для обеспечения блокировки дуги дешифратором 28 и записи минимального веса из регистра 30 в блок 10 оперативной памяти.

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

Третий элемент 45 задержки обеспечивает задержку импульса, поступающего на регистр 16 минимальной длины связей, на время, достаточное для подсчета и добавления очередного слагаемого формулы (1) умножителем 14 и сумматором 15.

Первый блок элементов ИЛИ 46 необходим для подачи в АЛУ 7 веса текущей дуги.

Электронная модель 31.l дуги служит для моделирования l-й дуги орграфа G, l = 1, 2, ..., m.

Триггер 20.l блокировки дуги служит для выдачи сигнала блокировки повторного выбора соответствующей дуги во время работы устройства.

Регистр 21.l веса дуги и регистр 22.l блокировки дуги предназначены для хранения веса текущей дуги и нулевого кода соответственно. Регистры 21.l и 22.l имеют выходы с тремя состояниями; перевод выходов в третье (высокоимпедансное) состояние обеспечивается соответственно единичным и нулевым сигналом на входах разрешения (ое).

Первый элемент И 38. l необходим для формирования сигнала наличия l-й дуги в графе.

Второй элемент И 39.l служит для формирования сигнала выбора/блокировки дуги.

Элемент ИЛИ 40.l служит для объединения сигналов с элемента И 39.l и с элемента И 33.l.

Рассмотрим работу предлагаемого устройства.

Первоначально в регистрах 29, 30 и 25 содержатся значения "11...1". В регистре 16 и счетчиках 27, 9 содержится нулевой код. Триггеры 19 и 23 находятся в состоянии логического нуля; состояние триггера 24 либо нулевое, что соответствует топологии кольца, либо единичное, что соответствует топологии линейки. Значение с прямого выхода триггера 24 подается на разрешающий вход счетчика 11 и если это значение - единица, то работа счетчика 11 разрешена, а если ноль, то работа запрещена (на выходе счетчика 11 будет константный код). Первоначально в счетчике 11 хранится код общего числа обрабатываемых элементов матрицы расстояний D (его запись осуществляется со входа 51 устройства по импульсу со входа 52 устройства). В счетчиках 12, 13 содержатся нулевые значения. Триггеры 20.l модели 31.l, l = 1, 2, ..., m, находятся либо в состоянии логической единицы, либо в состоянии логического нуля (что определяется соответственно наличием или отсутствием l-й дуги в графе). В регистрах 21. l содержатся либо значения весов соответствующих дуг, либо нулевые коды (если соответствующие дуги отсутствуют в исходном графе). Если размещается граф с невзвешенными дугами, то регистры 21.l содержат либо коды "00. . . 01", либо нулевые коды. Запись информации о размещаемом графе осуществляется путем подачи комбинаций сигналов на входы 56.1 - 56.n устройства и весов дуг на входы 54.l устройства. Появление единичных сигналов на входах 56. i-1 и 56.i означает наличие в графе дуги е_i-1,i (вес этой дуги подается на вход 54 соответствующей модели дуги).

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

Задача размещения невзвешенных графов с топологической моделью в виде линейки решается в устройстве аналогично прототипу. В данном случае работает только так называемая "верхняя" часть схемы, в которую входит ЭМГ 31, регистры 1 и 2, группа элементов ИЛИ 32.1 - 32.n, группа элементов И 33.1 - 31. m, блок элементов ИЛИ 46, регистр 25, элемент 26 сравнения, одновибратор 41, а также БФП 3, блок 4 постоянной памяти, БЗЛВ 5, коммутатор 6 и АЛУ 7.

Регистр 1 и регистр 2 последовательно выбирают пары вершин по мере поступления импульсов с входа 57 устройства. Сигналы выбранной пары вершин проходят через два соответствующих элемента группы элементов ИЛИ 32.1 - 32.n и далее формируют единичный сигнал на выходе соответствующего элемента И группы 33.1 - 33.m (допустим элемента 33.l). Единичный сигнал с элемента И 33.l поступает на элемент ИЛИ 40.l (модели 31.l дуги) и, попадая далее на разрешающий вход (ое) регистра 21.l, разрешает тем самым появление данных (веса l-й дуги) на выходе этого регистра. Поскольку размещаемый граф не взвешен, в регистре 21. l содержится либо код "00...01" либо код "00...00" (отсутствие дуги). Будем считать данный код ненулевым. Код "00...01" с выхода регистра 21.l поступает на блок элементов ИЛИ 46 и далее, через него - в АЛУ 7. В это же время блок 3 формирования перестановок определяет для выбираемых вершин позиции, а АЛУ 7 вырабатывает команду определения расстояния между позициями, в которые следует поместить выбранные вершины графа. Это расстояние определяется по формуле d_i,j = |i-j|.Одновременно в АЛУ 7 происходит и накопление суммарной длины связей L. Подсчет суммарной длины связей для текущего варианта размещения завершается, когда на выходе переполнения регистра 2 появляется сигнал переполнения. Одновременно этот же сигнал поступает на БФП 3, подготавливая его к формированию новой перестановки.

Перестановки формируются в пространственно-временной форме, то есть в каждый тактовый момент времени единичный сигнал инициируется только на одном (q-м) выходе БФП 3, а их последовательность задает соответствующую перестановку. Например, перестановка (3 1 2) означает, что первый тактовый импульс появляется на втором выходе БФП, второй - на третьем, третий - на первом. В соответствии с этим из блока 4 постоянной памяти (в блок 4 постоянной памяти заносятся двоичные коды номеров позиций) через коммутатор 6 в АЛУ 7 будут последовательно списываться коды второй позиции, третьей и первой. Это в свою очередь означает, что первая вершина помещается во вторую позицию, вторая в третью и третья в первую. Лучший вариант размещения переписывается в блок 5 и соответствующее ему значение длины связей L - в регистр 25. Появление сигнала на сигнализирующем выходе БФП 3 свидетельствует о том, что все перестановки сформированы, а лучший вариант размещения зафиксирован в БЗЛВ 5.

Значение L в регистре 25 формируется следующим образом. С выхода АЛУ 7 значение длины связей очередного варианта размещения поступает на вход данных регистра 25 и первый вход элемента 26 сравнения. Код с выхода регистра 25 поступает на второй вход элемента 26 сравнения. В первом такте работы в регистре 25 содержится код "11...1", поэтому при первом сравнении в элементе 26 сравнения результат будет положительным и, следовательно, на выходе этого элемента будет единичный сигнал. Единица с выхода элемента 26 сравнения поступает на одновибратор 41 и формирует импульс на его выходе. Данный импульс поступает на синхровход регистра 25 и по заднему фронту заносит в него новое значение длины связей. Последнее снова поступает на второй вход элемента 26 сравнения для сравнения с длиной связей L очередного варианта размещения и т.д., пока в регистре 25 не будет зафиксировано значение наилучшего варианта размещения.

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

Задача оценки степени близости сформированного размещения к оптимальному решается следующим образом (в данном случае работает только "нижняя" часть схемы, включающая дешифраторы 8 и 28, элемент 17 сравнения, счетчики 27, 9, 11, 12 и 13, блок 10 оперативной памяти, регистры 16, 25, 29 и 30, триггеры 19, 23 и 24, умножитель 14, сумматор 15, вычитатель 18, блок элементов ИЛИ 36, элементы И 34, 35 и 37, элементы 43, 44 и 45 задержки и одновибратор 42).

При появлении единичного сигнала на сигнализирующем выходе БФП 3 триггер 19 устанавливается в единицу. Единичный сигнал с прямого выхода триггера 19 поступает на вторые входы элемента И 34 и элемента И 35. Так как триггер 23 режима находится в нулевом состоянии, элемент 35 по-прежнему остается закрытым, а элемент 34 открывается для прохождения тактовых импульсов.

Первый тактовый импульс проходит через элемент И 34, откуда этот импульс поступает на счетный вход счетчика 27 и передним фронтом устанавливает его в значение "00...01". Код с выхода счетчика 27 поступает на вход данных регистра 29 и на вход дешифратора 8, инициируя появление единицы на его первом выходе. Эта единица поступает на второй вход элемента И 39.1 (модели 31.1). Если на первом входе элемента 39.1 присутствует единица (триггер 20.1 находится в единичном состоянии), то на выходе элемента 39.1 появляется единичный сигнал выбора дуги. С выхода элемента И 39.1 этот сигнал проходит через элемент ИЛИ 40.1, поступает на разрешающий вход регистра 21.1 и открывает его выход. В результате вес дуги с регистра 21.1 проходит через блок элементов ИЛИ 36, откуда попадает на первый вход элемента 17 сравнения, на втором входе которого присутствует код из регистра 30 (первоначально "11...1"). Если код с блока элементов ИЛИ 36 (вес выбранной дуги) меньше уже имеющегося в регистре 30, на выходе элемента 17 образуется единичный сигнал. Этот единичный сигнал поступает на первый вход элемента И 37 и обеспечивает прохождение тактового импульса с элемента И 34, задержанного на элементе 44 задержки. Импульс с элемента И 37 поступает на синхровходы регистра 29 и регистра 30 и по переднему фронту записывает в них значение с выхода счетчика 27 (номер текущей дуги) и код веса выбранной дуги с блока 36 (как минимальный на данный момент) соответственно. В случае присутствия на выходе элемента 17 нуля элемент И 37 заблокирован и поэтому импульс с элемента 44 задержки не поступает на синхровходы регистров 29 и 30.

Очередной тактовый импульс аналогично проходит через элемент И 34, снова попадает на счетный вход счетчика 27 и увеличивает значение этого счетчика до "00...010". С выхода счетчика 27 код снова попадает на дешифратор 8, чем вызывает появление единицы на его втором выходе. Эта единица аналогично поступает в модель 31.2 взвешенной дуги и со второго выхода веса дуги модели 31 на блок элементов ИЛИ 36 поступает код веса второй дуги. Если такая дуга существует, то соответствующий ей код попадает на первый вход элемента 17 сравнения, на второй вход которого поступает с регистра 30 вес, записанный на предыдущих шагах. Если новый вес ме