Устройство поиска нижней оценки размещения в гибридных многопроцессорных системах при направленной передаче информации Российский патент 2022 года по МПК G06F17/16 G06F15/163 

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 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-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, второй элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров и с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход блока оперативной памяти соединен с входом группы модулей оперативной памяти гибридной многопроцессорной системы, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, и с входом группы процессоров гибридной многопроцессорной системы, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выходы элементов с первого по n-й ИЛИ подключены к соответствующим входам элементов с первого по m-й И, а также дополнительно введенный блок содержит первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами блока запоминания лучшего варианта, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом блока запоминания лучшего варианта, а выход блока запоминания лучшего варианта соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров и с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выходы элементов с первого по n-й ИЛИ подключены к соответствующим входам элементов с первого по m-й И, а также дополнительно введенный блок нижней оценки, содержащий группу с первого по n-й модулей оперативной памяти гибридной многопроцессорной системы, группу (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы, группу с первого по n-ю промежуточных сумматоров, общий сумматор, причем группа с первого по n-й модулей оперативной памяти гибридной многопроцессорной системы соединена с соответствующими D-входами группы (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы, соответствующие oe-входы подключены к тактовому входу устройства, выходы группы (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы подсоединены к соответствующим входами группы с первого по n-й промежуточных сумматоров, выходы которых подключен к соответствующим входам общего сумматора гибридной многопроцессорной системы, выход которого соединен с выходом устройства.

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

Сущность изобретения поясняется чертежами, где на фигуре 1 и 3 представлено устройство поиска нижней оценки размещения в гибридных многопроцессорных системах при направленной передаче информации. на фигуре 2 показан пример реализации взвешенного графа G исходной гипотетической задачи для которой должен быть выполнен поиск нижней оценки размещения. В данном случае граф G представляется в виде классической матрицы смежности в соответствии с понятиями теории графов и модули 31.1.1 и 31.1.2 представляют ячейки матрицы смежности с координатами (1.1) и (1.2). Остальные ее ячейки представляются аналогично.

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

Главная особенность гибридной архитектуры, подобной многопроцессорным системам класса NUMA (nonuniformmemory access) – неоднородный доступ к памяти, т.е. к памяти других модулей. Архитектура NUMA является MPP (массивно-параллельной) архитектурой, где в качестве отдельных вычислительных элементов берутся SMP (cимметричная многопроцессорная архитектура) узлы. Доступ к памяти и обмен данными внутри одного SMP-узла осуществляется через локальную память узла, а к процессорам другого SMP-узла тоже есть доступ, но более медленный и через более сложную систему адресации.

Исходная задача описывается графом G=<X,E>, где – множество вершин графа G, вершины которого соответствуют задачам, а взвешенные дуги описывают связи между задачами и задают объёмы данных m_ij (в байтах) предаваемых при обмене между задачами. Граф G представляется матрицей смежности где m_ij – вес дуги e_ij.

Многопроцессорная система представляется топологической моделью в виде графа H=<P,V>, где – множество идентификаторов процессорных модулей, организованных в матрицу |P|_n×n, где мощность - число процессорных модулей; V – множество межмодульных связей.

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

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

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

Устройство для поиска нижней оценки размещения в гибридных многопроцессорных системах при направленной передаче информации содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок, блок 4 постоянной памяти, блок 5 запоминания лучшего варианта, коммутатор 6, АЛУ 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, первый элемент 11 сравнения, триггер 12 начала счета, триггер 13 режима, счетчик 14 дуг, дешифратор 15 блокировки дуги, регистр 16 номера дуги, регистр 17 минимального веса, электронную модель 24 графа, группу элементов ИЛИ 18.1 – 18.n, группу элементов И 19.1 – 19.m, первый 20 и второй 21 элементы И, второй блок элементов ИЛИ 22, третий элемент И 23, первый 25 элемент задержки, второй 41 элемент задержки, первый блок элементов ИЛИ 26, причем выходы блока формирования перестановок 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами блока запоминания лучшего варианта 5, сигнализирующий выход блока формирования перестановок 3 соединен с установочным входом триггера 12 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом АЛУ 7, выход которого соединен с информационным входом БЗЛВ 5, а выход блока запоминания лучшего варианта 5 соединен с первым информационным входом АЛУ 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 18.1 – 18.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом АЛУ 7 и с управляющим входом блока формирования перестановок 3, тактовый вход 40 устройства соединен с входом регистра 1 сдвига, с тактовым входом блока формирования перестановок 3 и с первыми входами элементов И 20 и 21, выход счетчика 14 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 16 номера дуги, выход блока элементов ИЛИ 22 подключен к первому входу элемента 11 сравнения и к входу данных регистра 17 минимального веса, выход регистра 17 минимального веса соединен с вторым входом элемента 11 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 25 задержки соединен с входом установки регистра 17 минимального веса и с входом установки регистра 16 номера дуги, выход третьего элемента И 23 соединен с синхровходом регистра 17 минимального веса и с синхровходом регистра 16 номера дуги, выход регистра 16 номера дуги соединен с информационным входом дешифратора 15 блокировки дуги, выход переполнения счетчика 14 дуг соединен с разрешающим входом дешифратора 15 блокировки дуги, а также с входом элемента 25 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход блока 10 оперативной памяти соединен с входом группы 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы, выход элемента И 20 соединен со счетным входом счетчика 14 дуг и со входом элемента 41 задержки, выход которого соединен со вторым входом элемента И 23, первый вход которого соединен с выходом элемента 11 сравнения, второй вход элемента И 20 соединен с прямым выходом триггера 12 начала счета, который также соединен со вторым входом элемента И 21, третий вход элемента И 20 соединен с инверсным выходом триггера 13 режима, прямой выход которого соединен с третьим входом элемента И 21, и с входом группы (36.1.1, 36.1.2, 36.1.3, 36.1.4), (36.2.1, 36.2.2, 36.2.3, 36.2.4), (36.3.1, 36.3.2, 36.3.3, 36.3.4), ..., (36.q.1, 36.q.2, 36.q.3, 36.q.4),..., (36.n.1, 36.n.2, 36.n.3, 36.n.4) процессоров гибридной многопроцессорной системы, выход элемента И 21 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 13 режима, вход сброса которого подключен к R-входу 42 установки устройства, вход сброса триггера 12 начала счета подключен к входу 43 установки устройства, l-й выход дешифратора 8 выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели 24 графа, l-й выход дешифратора 15 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 24 графа, l-й выход веса дуги электронной модели 24 графа соединен с l-м входом блока элементов ИЛИ 26, выход элемента И 29.l соединен с l-м управляющим входом электронной модели 24 графа, выход блока элементов ИЛИ 26 соединен со вторым информационным входом АЛУ 7, выходы элементов ИЛИ 18.1 – 18.n подключены к соответствующим входам элементов И 19.1 – 19.m, а также дополнительно введенный блок 34 нижней оценки, содержащий группу 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы, группу (36.1.1, 36.1.2, 36.1.3, 36.1.4), (36.2.1, 36.2.2, 36.2.3, 36.2.4), (36.3.1, 36.3.2, 36.3.3, 36.3.4), ..., (36.q.1, 36.q.2, 36.q.3, 36.q.4),..., (36.n.1, 36.n.2, 36.n.3, 36.n.4) процессоров гибридной многопроцессорной системы, группу 37.1, 37.2,..., 37.n промежуточных сумматоров, общий 38 сумматор, причем группа 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы соединена с соответствующими D-входами группы (36.1.1, 36.1.2, 36.1.3, 36.1.4), (36.2.1, 36.2.2, 36.2.3, 36.2.4), (36.3.1, 36.3.2, 36.3.3, 36.3.4), ..., (36.q.1, 36.q.2, 36.q.3, 36.q.4),..., (36.n.1, 36.n.2, 36.n.3, 36.n.4) процессоров гибридной многопроцессорной системы, соответствующие oe-входы подключены к тактовому 40 входу устройства, выходы группы (36.1.1, 36.1.2, 36.1.3, 36.1.4), (36.2.1, 36.2.2, 36.2.3, 36.2.4), (36.3.1, 36.3.2, 36.3.3, 36.3.4), ..., (36.q.1, 36.q.2, 36.q.3, 36.q.4),..., (36.n.1, 36.n.2, 36.n.3, 36.n.4) процессоров гибридной многопроцессорной системы подсоединены к соответствующим входами группы 37.1, 37.2,..., 37.n промежуточных сумматоров, выходы которых подключен к соответствующим входам общего 38 сумматора гибридной многопроцессорной системы, выход которого соединен с выходом устройства.

Устройство по п.1, отличающееся тем, что электронная модель 24 графа содержит m электронных моделей дуги, причем электронная модель 27.l дуги (l = 1, 2, …, m) содержит триггер 28.l блокировки дуги, регистр 29.l веса дуги, регистр 30.l блокировки дуги, первый элемент И 31.l, второй элемент И 32.l, элемент ИЛИ 33.l, причем входы элемента И 31.l соединены с соответствующими входами 39.y и 39.z задания графа устройства (где y и z – номера соответственно начальной и конечной вершины l-й дуги графа), выход элемента И 31.l соединен с синхровходом регистра 29.l веса дуги и с установочным входом триггера 28.l блокировки дуги, вход сброса которого соединен с l-м входом блокировки дуги модели 24, вход данных регистра 29.l веса дуги соединен с входом 44.l веса дуги устройства, первый вход элемента ИЛИ 33.l соединен с l-м управляющим входом модели 24, а второй вход элемента ИЛИ 33.l соединен с выходом элемента И 32.l, первый вход которого соединен с прямым выходом триггера 28.l блокировки дуги и с разрешающим входом регистра 30.l блокировки дуги, второй вход элемента И 32.l соединен с l-м входом выбора дуги модели 24, вход сброса регистра 30.l блокировки дуги соединен с входом 45.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 выбора дуги вместе со счетчиком 14 дуг предназначены для выбора из ЭМГ 24 дуги с номером, записанным в счетчике 14.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый элемент 25 задержки служит для задержки импульса переполнения со счетчика 14 дуг на время, достаточное для обеспечения блокировки дуги дешифратором 15 и записи минимального веса из регистра 17 в блок 10 оперативной памяти.

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

Электронная модель 27.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 нижней оценки состоит в следующем.

Группа 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы предназначена для хранения и передачи кодов значений интенсивности в соответствующие процессоры системы.

Группа (36.1.1, 36.1.2, 36.1.3, 36.1.4), (36.2.1, 36.2.2, 36.2.3, 36.2.4), (36.3.1, 36.3.2, 36.3.3, 36.3.4), ..., (36.q.1, 36.q.2, 36.q.3, 36.q.4),..., (36.n.1, 36.n.2, 36.n.3, 36.n.4) процессоров гибридной многопроцессорной системы необходима для выполнения задач, выполняемых в гибридной системе (q=1...n).

Группа 37.1, 37.2,..., 37.n промежуточных сумматоров служит для суммирования значений интенсивности в каждой отдельной группе (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы.

Общий 38 сумматор гибридной многопроцессорной системы предназначен для общего суммирования значений интенсивности, получаемых из групп (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы с последующей их подачей на ВУУ для принятия решения о возможных дальнейших действиях системы.

Вход 39 задания графа устройства предназначен для получения устройством исходного графа задачи.

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

Второй 41 элемент задержки служит для задержки сигнала с выхода элемента 20 И на второй вход элемента 23 И.

R-вход 42 установки устройства предназначен для подачи единичного импульса на R-вход триггера 13 режима.

Вход 43 установки устройства предназначен для подачи единичного импульса на R-вход триггера 12 начала счета.

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

Вход 45 сброса устройства служит для подачи сигнала на R-вход регистра 30 блокировки дуги.

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

Первоначально в группу (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы не поступило заданий для выполнения. В группе 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы находятся копии данных из блока 10 оперативной памяти. При этом хранящиеся в них данные подаются на соответствующие D-входы групп (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы, но запись в них не происходит, так как их ое-входах не присутствует единичного импульса. Тогда при работе устройства, при считывании очередного кода из групп 35.1, 35.2,..., 35.n модулей оперативной памяти гибридной многопроцессорной системы, во всех их модулях содержимое уменьшается на единицу.

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

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

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

Единичный импульс с тактового 40 входа устройства поступает на ое-вход процессора 36.1.1 и этим разрешает прием данных из модуля оперативной памяти 35.1, которые с его выхода поступают на соответствующий вход промежуточного сумматора 37.1. Соответственно, содержимое в группе 35.1, 35.2,..., 35.n модулей оперативной памяти уменьшается на единицу и очередное значение интенсивности вновь поступает на D-входы группы (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы.

Следующий тактовый импульс поступает на ое-вход процессора 36.2.1 разрешает запись в него кода значения интенсивности из модуля 35.2 оперативной памяти. Этот код подается на D-вход процессора 36.2, откуда он поступает на первый вход промежуточного 37.2 сумматора. Аналогично содержимое группы 35.1, 35.2,..., 35.n модулей оперативной памяти уменьшается на единицу и очередное значение интенсивности поступает на D-входы группы (36.q.1, 36.q.2, 36.q.3, 36.q.4) процессоров гибридной многопроцессорной системы.

Так продолжается до тех пор, пока в процессор 36.n.1 не будет записан очередной код, который поступит на первый вход промежуточного 37 сумматора.

Следующий тактовый импульс подается на ое-вход процессора 36.2.1 и аналогично описанному выше принципу происходит запись кода значения интенсивности в процессор с последующим его поступлением на второй вход сумматора 37.1. Соответственно, модулей 35.1, 35.2,..., 35.n оперативной памяти уменьшается на единицу. Так продолжается для всех 36.1.2, 36.2.2., ..., 36.n.2 процессоров с аналогичной подачей соответствующих кодой на вторые входы группы 37.1, 37.2,..., 37.n промежуточных сумматоров.

Повторные действия происходят процессоров (36.1.3, 36.2.3, ..., 36.n.3) и (36.1.4, 36.2.4, ..., 36.n.4).

Как только на всех входах группы 37.1, 37.2,..., 37.n промежуточных сумматоров появятся коды значений интенсивности, полученные суммы, показывающие значения нижней оценки размещения для соответствующего процессора гибридной многопроцессорной системы. Для получения суммарного значения данной величины, коды величины нижней оценки размещения каждого процессора многопроцессорной системы поступают на соответствующие входы общего 38 сумматора. Полученная сумма подается с его выхода на ВУУ для принятия решения о дальнейших действиях.

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

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

1. Устройство для поиска нижней оценки размещения в гибридных многопроцессорных системах при направленной передаче информации, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, первый элемент сравнения, триггер начала счета, триггер режима, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу элементов с первого по n-й ИЛИ, группу элементов с первого по m-й И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый элемент задержки, второй элемент задержки, первый блок элементов ИЛИ, причем выходы блока формирования перестановок соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход блока формирования перестановок соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход блока запоминания лучшего варианта соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы регистров и с первого по n-й подключены к первым и вторым входам элементов ИЛИ соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом блока формирования перестановок, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом блока формирования перестановок и с первыми входами элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход блока оперативной памяти соединен с группой модулей оперативной памяти гибридной многопроцессорной системы, выход элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом элемента И, третий вход элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом элемента И, и с входом группы процессоров гибридной многопроцессорной системы, выход элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l = 1, 2, …, m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ, выход элемента И соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выходы элементов с первого по n-й ИЛИ подключены к соответствующим входам элементов с первого по m-й И, отличающееся тем, что в него дополнительно введен блок нижней оценки, содержащий группу с первого по n-й модулей оперативной памяти гибридной многопроцессорной системы, группу (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы, группу с первого по n-ю промежуточных сумматоров, общий сумматор, причем группа с первого по n-й модулей оперативной памяти гибридной многопроцессорной системы соединена с соответствующими D-входами группы (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы, соответствующие oe-входы подключены к тактовому входу устройства, выходы группы (1.1, 1.2, 1.3, 1.4), (2.1, 2.2, 2.3, 2.4), (3.1, 3.2, 3.3, 3.4), ..., (q.1, q.2, q.3, q.4),..., (n.1, n.2, n.3, n.4) процессоров гибридной многопроцессорной системы подсоединены к соответствующим входам группы с первого по n-й промежуточных сумматоров, выходы которых подключен к соответствующим входам общего сумматора гибридной многопроцессорной системы, выход которого соединен с выходом устройства.

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