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

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС). Технический результат заключается в расширении арсенала средств того же назначения. Устройство для оценки степени оптимальности размещения в многопроцессорных кубических циклических системах, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с первого по n-й элементов ИЛИ, группу с первого по n-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ. 1 з.п. ф-лы, 10 ил.

 

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС).

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

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

Наиболее близкой к предлагаемому устройству по технической сущности является устройство для формирования субоптимального размещения и его оценки, содержащая блок формирования перестановок, блок постоянной памяти, коммутатор, арифметико-логическое устройство (АЛУ), блок запоминания лучшего варианта, введены дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группа элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, два регистра сдвига, элемент ИЛИ и группу элементов ИЛИ, электронную модель графа (ЭМГ) содержащую m электронных моделей дуги, причем l-я электронная модель дуги (l = 1, 2, …, m) содержит триггер блокировки дуги, регистр веса дуги, регистр блокировки дуги, первый элемент И, второй элемент И, элемент ИЛИ (Патент РФ №2193796, кл. G 06 F 17/10, 7/38, опубл. 27.11.2002, БИ №33).

Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для оценки степени оптимальности размещения в многопроцессорных кубических циклических системах (КЦС).

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

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

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

Сущность изобретения поясняется чертежами, где на фиг. 1 показан пример исходного графа задачи; фиг. 2 показывает пример описания матрицы смежности для исходного графа задачи, показанного на фиг 1; на фиг. 2 показана матрица смежности W, соответствующая графу, представленному на фиг.1; на фиг. 3 представлена матрица расстояний для МС, состоящей из шести процессоров; фиг 4 показывает пример многопроцессорной кубической циклической системы; фиг. 5 представляет циклический вариант представления кубической циклической многопроцессорной системы; фиг. 6 описывает матрицу смежности для циклического фрагмента, представленного на фиг. 5; фиг. 7. показывает матрицу расстояний для циклического фрагмента, представленного на фиг. 5; на фиг. 8.

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

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

Исходная задача (процесс, алгоритм, программа) представляется в виде двунаправленного взвешенного графа G=<Х,E> (фиг. 1), вершины которого соответствуют подзадачам (подалгоритмам, подпрограммам и т.п.), а дуги задают управляющие и/или информационные связи между подзадачами и фактически являются каналами передачи данных. Граф G может быть описан матрицей смежности , где ; – объем передаваемых данных между i-м и j-м процессорным модулем (фиг. 2).

Топологическая модель КЦС (область размещения) задается матрицей расстояний D1. Элементы матрицы расстояний D1 = ||d1_i,j||_n×n для кубической системы образуются по формуле (фиг. 3)

Кубическая циклическая система представляет собой булев куб (q=2) размерности d, каждая из вершин которого вместо одного элемента, что характерно для полного гиперкуба, представляется циклом из d связанных вершин. Каждый из элементов в таком цикле имеет по три двунаправленных канала связи, два из которых подключено к соседним элементам, принадлежащим общему с данным элементом циклу, а третий канал пересекает гиперкуб в одном из d измерений и соединяет рассматриваемый элемент с соответствующим элементом другого цикла.

Для математического описания циклического фрагмента кубической системы (фиг. 5) введем матрицу смежности , где ; – объем передаваемых данных между i-м и j-м процессорным модулем (фиг. 6). Топологическая модель цикла описывается матрицей расстояний для кубической системы образуются по формуле (фиг. 7).

Топология КЦС задается графом , где множество вершин соответствует процессорным модулям, а множество дуг V – межмодульным связям. Множество разбивается на два непересекающихся подмножества , где – множество основных процессоров, – множество циклических фрагментов кубической системы, причем фиксируется Упорядочим множества процессоров P и L в виде матриц и соответственно. Множество представим объединением указанных матриц следующим образом:

(1)

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

, (2)

которое ставит в соответствие каждой подпрограмме один из процессоров (основной либо процессор циклического фрагмента КЦС).

Пусть – множество всевозможных отображений вида (2). Тогда задача размещения программ в мультикомпьютере будет заключаться в выборе такого отображения , которое соответствует следующему критерию:

, (3)

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

Устройство для оценки степени оптимальности размещения в многопроцессорных кубических циклических системах содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок (БФП), блок 4 постоянной памяти, блок 5 запоминания лучшего варианта (БЗЛВ), коммутатор 6, АЛУ 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, первый элемент 11 сравнения, триггер 12 начала счета, триггер 13 режима, счетчик 17 дуг, дешифратор 14 блокировки дуги, регистр 15 номера дуги, регистр 16 минимального веса, электронную модель 24 графа, группу элементов ИЛИ 18.1 – 18.n, группу элементов И 19.1 – 19.m, первый 20 и второй 21 элементы И, второй блок элементов ИЛИ 22, третий элемент И 23, первый 25, второй 26 элементы задержки, первый блок элементов ИЛИ 27, причем выходы БФП 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами БЗЛВ 5, сигнализирующий выход БФП 3 соединен с установочным входом триггера 12 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом АЛУ 7, выход которого соединен с информационным входом БЗЛВ 5, а выход БЗЛВ 5 соединен с первым информационным входом АЛУ 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 18.1 – 18.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом АЛУ 7 и с управляющим входом БФП 3, тактовый вход 52 устройства соединен с входом регистра 1 сдвига, с тактовым входом БФП 3 и с первыми входами элементов И 20 и 21, выход счетчика 17 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 15 номера дуги, выход блока элементов ИЛИ 22 подключен к первому входу элемента 11 сравнения и к входу данных регистра 16 минимального веса, выход регистра 16 минимального веса соединен с вторым входом элемента 11 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 25 задержки соединен с входом установки регистра 16 минимального веса и с входом установки регистра 15 номера дуги, выход третьего элемента И 23 соединен с синхровходом регистра 16 минимального веса и с синхровходом регистра 15 номера дуги, выход регистра 15 номера дуги соединен с информационным входом дешифратора 14 блокировки дуги, выход переполнения счетчика 17 дуг соединен с разрешающим входом дешифратора 14 блокировки дуги, а также с входом элемента 25 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход элемента И 20 соединен со счетным входом счетчика 17 дуг и со входом элемента 26 задержки, выход которого соединен со вторым входом элемента И 23, первый вход которого соединен с выходом элемента 11 сравнения, второй вход элемента И 20 соединен с прямым выходом триггера 12 начала счета, который также соединен со вторым входом элемента И 21, третий вход элемента И 20 соединен с инверсным выходом триггера 13 режима, прямой выход которого соединен с третьим входом элемента И 21, выход элемента И 21 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 13 режима, вход сброса которого подключен к входу 54 установки устройства, вход сброса триггера 12 начала счета подключен к входу 53 установки устройства, l-й выход дешифратора 8 выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели 24 графа, l-й выход дешифратора 14 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 24 графа, l-й выход веса дуги электронной модели 24 графа соединен с l-м входом блока элементов ИЛИ 22 и l-м входом блока элементов ИЛИ 27, выход элемента И 19.l соединен с l-м управляющим входом электронной модели 24 графа, выход блока элементов ИЛИ 27 соединен со вторым информационным входом АЛУ 7, выходы элементов ИЛИ 18.1 – 18.n подключены к соответствующим входам элементов И 19.1 – 19.m, а также дополнительно введенный блок 34 минимального значения, содержащий ОЗУ1 35, ОЗУ2 36, первый 37 и второй 38 сумматор, первый 39 счетчик адреса строки, первый 40 счетчик адреса столбца, первый 41 промежуточный регистр, второй 42 промежуточный регистр, второй 43 счетчик адреса строки, второй 44 счетчик адреса столбца, первый 45 и второй 46 элемент И, причем тактовый вход 52 устройства подключен к счетному входу первого 40 счетчика адреса столбца, к счетному входу второго 44 счетчика адреса столбца, первому 47 входу второго 46 элемента И и к третьему 48 входу первого 45 элемента И, выход второго 44 счетчика адреса столбца соединен с адресным а2-входом ОЗУ2 36, адресный а1-вход которого подключен к выходу второго 43 счетчика адреса строки, и к D-входу второго 44 счетчика адреса столбца, s-вход которого подсоединен к выходу первого 45 элемента И, первый вход которого подключен к выходу переполнения второго 44 счетчика адреса столбца и к счетному входу второго 43 счетчика адреса строки, е-вход второго 44 счетчика адреса столбца соединен с выходом переполнения первого 39 счетчика адреса строки, выход которого подключен к адресному а1-входу ОЗУ1 35 и к D-входу первый 40 счетчика адреса столбца, выход переполнения которого соединен с первым входом второго 46 элемента И и со счетным входом первого 39 счетчика адреса строки, выход первого 40 счетчика адреса столбца подсоединен к адресному а2-входу ОЗУ1 35, D-выход которого подключен к первому входу первого 37 сумматора, второй вход которого подключен к выходу первого 41 промежуточного регистра и к первому 49 выходу первого 41 промежуточного регистра, вход первого 41 промежуточного регистра подключен к выходу первого 37 сумматора, выход ОЗУ2 36 подключен к первому входу второго 38 сумматора, второй вход которого соединен с выходом второго 42 промежуточного регистра и со вторым 50 выходом второго 42 промежуточного регистра, вход которого подключен к выходу второго 38 сумматора.

Электронная модель 24 графа (фиг.2) содержит m электронных моделей дуги, причем электронная модель 24.l дуги (l = 1, 2, …, m) содержит триггер 28.l блокировки дуги, регистр 29.l веса дуги, регистр 30.l блокировки дуги, первый элемент И 31.l, второй элемент И 32.l, элемент ИЛИ 33.l, причем входы элемента И 31.l соединены с соответствующими входами 56.y и 56.z задания графа устройства (где y и z – номера соответственно начальной и конечной вершины l-й дуги графа), выход элемента И 31.l соединен с синхровходом регистра 29.l веса дуги и с установочным входом триггера 28.l блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги модели 24, вход данных регистра 29.l веса дуги соединен с входом 54.l веса дуги устройства, первый вход элемента ИЛИ 33.l соединен с l-м управляющим входом модели 24, а второй вход элемента ИЛИ 33.l соединен с выходом элемента И 32.l, первый вход которого соединен с прямым выходом триггера 28. l блокировки дуги и с разрешающим входом регистра 30.l блокировки дуги, второй вход элемента И 32.l соединен с l-м входом выбора дуги модели 24, вход сброса регистра 30.l блокировки дуги соединен с входом 55.l сброса устройства, выход регистра 30.l блокировки дуги соединен с l-м выходом веса дуги модели 24, который также соединен с выходом регистра 29.l веса дуги, выход элемента ИЛИ 33.l подключен к разрешающему входу регистра 29.l веса дуги.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Группа элементов И 19.1 – 19.m предназначена для выбора соответствующих дуг графа G по сигналам с элементов ИЛИ 18.1 – 18.n.

Первый и второй элементы И 20 и 21 необходимы для блокировки передачи импульсов с тактового входа 52 устройства.

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

Третий элемент И 23 предназначен для блокировки прохождения импульсов.

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

Первый элемент 25 задержки служит для задержки импульса переполнения.

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

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

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

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

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

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

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

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

Назначение элементов блока 34 минимального значения (фиг. 9) состоит в следующем.

ОЗУ1 35 предназначено для топологического описания КЦС, задаваемой матрицей смежности

ОЗУ2 36 служит для топологического описания циклического фрагмента кубической системы (фиг. 5) КЦС.

Первый 37 сумматор необходим для объединения сигналов, поступающих с выходов ОЗУ1 35 и регистра 41.

Второй 38 сумматор служит для объединения сигналов, с выхода ОЗУ2 36 и регистра 42, позволяя накапливать сумму интенсивностей размещения в циклически фрагментах кубической системы.

Первый 39 счетчик адреса строки предназначен для подсчета адреса текущей строки КЦС, обрабатываемой в данное время.

Первый 40 счетчик адреса столбца предназначен для подсчета адреса текущего столбца КЦС, обрабатываемой в данное время.

Первый 41 промежуточный регистр необходим для временного хранения значения интенсивности размещения КЦС.

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

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

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

Первый 45 элемент И необходим для объединения и подачи единичного импульса на s-вход второго 44 счетчика адреса столбца.

Второй 46 элемент И необходим для объединения и подачи единичного импульса на s-вход первого 40 счетчика адреса столбца.

Первый 47 вход второго 46 элемента И предназначен для подачи единичного сигнала на его второй вход.

Второй 48 вход первого 45 элемента И служит для подачи единичного импульса на его второй вход.

Первый 49 выход первого 41 промежуточного регистра предназначен для подачи на ВУУ суммарного значения интенсивности размещения в КЦС для принятия решения о дальнейшей реакции устройства.

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

Выход 51 значения устройства предназначен для подачи сигнала ВУУ о завершении работы устройства.

Тактовый 52 вход устройства служит для подачи на устройства тактовых импульсов генератора тактовых импульсов.

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

Первоначально в ОЗУ1 35 содержится матрица смежности КЦС, в ОЗУ2 36 хранится матрица смежности циклического фрагмента КЦС. В счетчиках 39 и 43 хранится значение единицы («0…01»). В счетчиках 40 и 44 содержится код значения нуля («0…00»). В регистрах 41 и 42 хранится код значения ноль.

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

Задача размещения невзвешенных графов с топологической моделью в виде линейки решается в устройстве аналогично прототипу. В данном случае работает только так называемая «верхняя» часть схемы, в которую входит ЭМГ 24, регистры 1 и 2, группа элементов ИЛИ 18.1 – 18.n, группа элементов И 19.1 – 19.m, блок элементов ИЛИ 27, а также БФП 3, блок 4 постоянной памяти, БЗЛВ 5, коммутатор 6 и АЛУ 7.

Регистр 1 и регистр 2 последовательно выбирают пары вершин по мере поступления импульсов с входа 52 устройства. Сигналы выбранной пары вершин проходят через два соответствующих элемента группы элементов ИЛИ 18.1 – 18.n и далее формируют единичный сигнал на выходе соответствующего элемента И группы 19.1 – 19.m (допустим элемента 19.l). Единичный сигнал с элемента И 19.l поступает на элемент ИЛИ 33.l (модели 24.l дуги) и, попадая далее на разрешающий вход (oe) регистра 29.l, разрешает тем самым появление данных (веса l-й дуги) на выходе этого регистра. Поскольку размещаемый граф невзвешен, в регистре 29.l содержится либо код «00…01» либо код «00…00» (отсутствие дуги). Будем считать данный код ненулевым. Код «00…01» с выхода регистра 29.l поступает на блок элементов ИЛИ 27 и далее через него – в АЛУ 7. В это же время блок 3 формирования перестановок определяет для выбираемых вершин позиции, а АЛУ 7 вырабатывает команду определения расстояния между позициями, в которые следует поместить выбранные вершины графа. Это расстояние определяется по формуле . Одновременно в АЛУ 7 происходит и накопление суммарной длины связей L. Подсчет суммарной длины связей для текущего варианта размещения завершается, когда на выходе переполнения регистра 2 появляется сигнал переполнения. Одновременно этот же сигнал поступает на БФП 3, подготавливая его к формированию новой перестановки.

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

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

Задача оценки степени близости сформированного размещения к оптимальному решается следующим образом (в данном случае работает только «нижняя» часть схемы, включающая дешифраторы 8 и 14, элемент 11 сравнения, счетчики 17, 9 и блок 10 оперативной памяти, регистры 15 и 16, триггеры 12, 13, блок элементов ИЛИ 22, элементы И 20, 21 и 23, элементы 25, 26).

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

Первый тактовый импульс проходит через элемент И 20, откуда этот импульс поступает на счетный вход счетчика 17 и передним фронтом устанавливает его в значение «00…01». Код с выхода счетчика 17 поступает на вход данных регистра 15 и на вход дешифратора 8, инициируя появление единицы на его первом выходе. Эта единица поступает на второй вход элемента И 32.1 (модели 24.1). Если на первом входе элемента 32.1 присутствует единица (триггер 28.1 находится в единичном состоянии), то на выходе элемента 32.1 появляется единичный сигнал выбора дуги. С выхода элемента И 32.1 этот сигнал проходит через элемент ИЛИ 33.1, поступает на разрешающий вход регистра 29.1 и открывает его выход. В результате вес дуги с регистра 29.1 проходит через блок элементов ИЛИ 22, откуда попадает на первый вход элемента 11 сравнения, на втором входе которого присутствует код из регистра 16 (первоначально «11…1»). Если код с блока элементов ИЛИ 22 (вес выбранной дуги) меньше уже имеющегося в регистре 16, на выходе элемента 11 образуется единичный сигнал. Этот единичный сигнал поступает на первый вход элемента И 23 и обеспечивает прохождение тактового импульса с элемента И 20, задержанного на элементе 26 задержки. Импульс с элемента И 23 поступает на синхровходы регистра 15 и регистра 16 и по переднему фронту записывает в них значение с выхода счетчика 17 (номер текущей дуги) и код веса выбранной дуги с блока 22 (как минимальный на данный момент) соответственно. В случае присутствия на выходе элемента 11 нуля, элемент И 23 заблокирован и поэтому импульс с элемента 26 задержки не поступает на синхровходы регистров 15 и 16.

Очередной тактовый импульс аналогично проходит через элемент И 20, снова попадает на счетный вход счетчика 17 и увеличивает значение этого счетчика до «00…010». С выхода счетчика 17 код снова попадает на дешифратор 8, чем вызывает появление единицы на его втором выходе. Эта единица аналогично поступает в модель 24.1.2 взвешенной дуги, и со второго выхода веса дуги модели 24 на блок элементов ИЛИ 22 поступает код веса второй дуги. Если такая дуга существует, то соответствующий ей код попадает на первый вход элемента 11 сравнения, на второй вход которого поступает с регистра 16 вес, записанный на предыдущих шагах. Если новый вес меньше предыдущего, то единичный сигнал, свидетельствующий об этом, поступает на первый вход элемента И 23 и пропускает через него импульс с элемента 26 задержки. С выхода элемента И 23 импульс снова попадает на синхровходы регистров 15 и 16 и по переднему входу записывает в регистр 16 новый вес дуги (вес второй дуги), а в регистр 15 значение счетчика 17 как номер дуги с наименьшим на данный момент весом.

Так происходит до тех пор, пока на выходе переполнения счетчика 17 не появится сигнал (импульс) переполнения, сигнализирующий о том, что все дуги просмотрены и наименьший вес содержится в регистре 16, а номер соответствующей дуги – в регистре 15. При этом счетчик 17 сбрасывается в нулевое состояние, а сигнал переполнения одновременно поступает на вход записи блока 10 оперативной памяти на элемент 25 задержки и первый счетный вход счетчика 9. По заднему фронту сигнала переполнения счетчик 9 увеличивает свое значение до «00…01». В результате в блок 10 оперативной памяти по адресу «00…01» заносится минимальный вес дуги с регистра 16. Сигнал переполнения от счетчика 17 одновременно поступает на разрешающий вход дешифратора 14, обеспечивая выбор его выхода в зависимости от кода, подаваемого с выхода регистра 15. Сигнал с выбранного выхода дешифратора 14 (например, l-го) поступает на вход сброса триггера 28.l модели 24.l, устанавливая его в нулевое состояние (обеспечивается блокировка l-й дуги для следующих циклов работы устройства). К тому времени, когда минимальный вес дуги уже записан в блок 10 оперативной памяти, сигнал переполнения с выхода элемента 25 задержки поступает на входы установки (S) регистров 15 и 16 и устанавливает эти регистры в исходное состояние «11…1». Текущий цикл работы устройства завершается.

Следующий импульс, проходящий через элемент И 20, заставляет устройство снова работать по вышеописанному алгоритму. В регистре 16 сохраняется наименьший вес дуги без учета заблокированных в предыдущих циклах дуг. При выборе дешифратором 8 незаблокированной дуги устройство работает так, как описано выше. Когда дешифратор 8 выбирает уже заблокированную дугу, сигнал с выхода дешифратора 8 не проходит через элемент И 32.l (на прямом выходе триггера 28.l присутствует ноль). В то же время сигнал с прямого выхода триггера 28.l поступает на разрешающий вход регистра 30.l. В результате нулевой код (записанный в этот регистр с входа 55.l) с выхода регистра 30.l поступает через блок элементов ИЛИ 22 на первый вход элемента 11 сравнения и, будучи заведомо меньше любого другого кода, находящегося в регистре 16, обеспечивает нулевой сигнал на выходе элемента 11 и блокировку элемента 23.

При повторном появлении сигнала переполнения на счетчике 17 происходит увеличение значения счетчика 9 до кода «00…010». Сигнал переполнения поступает на вход записи блока 10 оперативной памяти и записывает туда по адресу «00…010» код веса дуги с выхода регистра 16 из счетчика 9. Таким образом, происходит последовательная запись в блок 10 оперативной памяти весов дуг графа G по возрастанию соответствующих значений. Так происходит до тех пор, пока счетчик 9 не выдаст сигнал переполнения. Этот сигнал поступает на установочный S-вход вход триггера 13, устанавливает его в единицу и тем самым разрешает прохождение тактовых импульсов через элемент И 21, запрещая их прохождение через элемент И 20. Сам счетчик 9 реверсивно переводится из суммирующего в вычитающий. С этого момента начинается поиск нижней оценки размещения в матричных системах при направленной передаче информации. Задача подсчета минимально возможной длины L^* решается так же, как в прототипе и поэтому здесь не рассматривается.

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

Первоначально аналогично описанному выше принципу «отрабатывает» верхняя часть схемы так, чтобы в блоке 10 оперативной памяти содержались дуги графа G, расположенные в порядке убывания значений своих весов. Как видно из фиг. 4 при назначении дуг на процессоры матричной системы в первую очередь следует назначать дуги с наибольшими значениями весов. Следовательно, при выборе из блока 10 оперативной памяти, первой выбранной дугой будет дуга с наибольшим значением веса, а последней – с наименьшим.

Очередной тактовый импульс со входа 52 поступает на входы 47 и 48 блока 34 оценки степени оптимальности размещения. Далее единичные импульсы подаются на счетные входы счетчиков 40 и 44, но так как на разрешающем входе счетчика 44 не присутствует единичного потенциала, то увеличения его содержимого не происходит. Также этот импульс подается на вторые входы элементов 47 и 48, разрешая их работу. А в счетчике 40 происходит увеличение содержимого по переднему фронту на единицу до кода двойки («0…010»). Этот код с выхода счетчика 40 поступает на адресный вход а2 ОЗУ1 35. В это время с выхода счетчика 39 на адресный вход а1 ОЗУ1 35 уже поступил код адреса ячейки памяти («0…01»). В результате, из ОЗУ1 выбирается значение матрицы смежности, которое соответствует объему передаваемых данных между двумя процессорами основных процессоров КЦС.

Это значение с D-выхода ОЗУ1 35 поступает на первый вход сумматора 37, на втором входе которого присутствует нулевое («0…00») значение с выхода регистра 41. В результате суммарное значение поступает на вход регистра 41, где происходит его запись, которое далее подается на второй вход сумматора 37.

Очередной тактовый импульс поступает со входа 52 на входы 47 и 48 блока 34 оценки степени оптимальности размещения. Аналогично единичный импульс поступает на счетный вход счетчика 40, где по переднему фронту происходит увеличение его содержимого до кода тройки («0…011»). Этот код подступает на вход а2 ОЗУ1 35. где в это время на его входе а1 присутствует единицы с выхода счетчика 39. В результате, код значения интенсивности из матрицы смежности с выхода ОЗУ1 35 подается на первый вход сумматора 37, где на втором его входе уже присутствует код с выхода регистра 41. В результате код суммарного значения записывается в регистре 41.

Так продолжается до тех пор, пока на выходе переполнения счетчика 40 не появится единичный потенциал, что одновременно означает, что первая строка матрицы смежности обработана и следует переходить к анализу ее второй строки. Поэтому единичный импульс с выхода счетчика на первый вход элемента 46 И и на счетный вход счетчика 39, в котором по переднему фронту происходит увеличение содержимого на единицу до кода двойки («0…010»). Этот код с выхода счетчика 39 поступает на вход а1 ОЗУ1 35 и на D-вход счетчика 40. В это время на втором входе элемента 46 И уже присутствует единичный импульс с выхода 52 устройства. Поступивший код на D-вход счетчика 40 устанавливает в нем начальный код значения двойки. В результате единичный потенциал с выхода элемента 46 И подается на s-вход счетчика 40, разрешая запись кода двойки в счетчике 40. В результате следующий тактовый импульс увеличит его содержимое до кода тройки и этим выберет третий столбец матрицы смежности.

Так продолжается до тех пор, пока на выход переполнения счетчика 39 не появится единый импульс, который означает, что оценка для основных процессоров КЦС завершена и далее происходит подсчет для циклических фрагментов кубической системы. Поэтому, единичный потенциал с выхода переполнения счетчика 39 подается на e-вход счетчика 44, тем самым разрешая его работу.

Очередной тактовый импульс подается на вход 48 устройства и далее на счетный вход счетчика 44, увеличивая его значение по переднему фронту на единицы до кода значения единицы («0…01»). Этот код поступает на адресный а2 вход ОЗУ2 36, на адресном а1 входе которого присутствует код значения единицы. Этот код также поступает на D-вход счетчика 44, устанавливая в нем стартовый код значения единицы.

Следующий тактовый импульс снова подается счетный вход счетчика 44, устанавливая в нем код двойки («0…010»), поступает на адресный вход а2, выбирая тем самым второй столбец матрицы смежности циклических фрагментов кубической системы. В это время на его адресном а1 входе присутствует код значения единицы с с выхода счетчика 43. Таким образом, значение очередного кода из матрицы смежности циклических фрагментов кубической системы поступает на первый вход сумматора 38, на втором входе которого в это время присутствует код нуля с выхода регистра 42. В результате суммирования суммарное значение подается на вход регистра 42, где происходит его запись.

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

В результате, когда на выходе переполнения счетчика 43 появится единичный импульс, это означает, что на выходе 49 присутствует суммарное значение интенсивности основных процессоров КЦС. Одновременно на выходе 50 присутствует суммарное значение интенсивности циклических фрагментов кубической системы, которое подается на ВУУ для принятия решение о дальнейших действиях хост-системы.

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

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

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