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

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

 

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 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-й И, а также дополнительно введенный блок поиска минимального значения, содержащий группу с первого по восьмой сумматоров, первую группу с первого по восьмой регистров номера вершины, вторую группу с первого по восьмой регистров номера вершины, группу с первого по восьмой SR триггеров режима, группу с первого по восьмой элементов задержки, дешифратор выбора вершины, счетчик номера вершины, группа элементов ИЛИ, блок элементов ИЛИ, сумматор минимального значения, причем тактовый вход устройства подключен к счетному входу счетчика номера вершины, выход которого подключен ко входу дешифратора выбора вершины, выходы с первого по восьмой которого соединены с соответствующими cs-входам первой с первого по восьмой и второй с первого по восьмой группы регистров номера вершины, выход переполнения счетчика номера вершины подключен к выходу переполнения устройства, е-входы первой с первого по восьмой группы регистров номера вершины подключены к соответствующим прямым выходам группы с первого по восьмой SR триггеров режима, обратные выходы которых соединены с соответствующими е-входами второй с первого по восьмой группы регистров номера вершины, соответствующие D-входы которых подключены к выходу блока оперативной памяти и к D-входу первой с первого по восьмой группы регистров номера вершины, выходы которых подключены к соответствующим первым входам группы с первого по восьмой сумматоров, вторые входы которых подключены к соответствующим выходам второй с первого по восьмой группы регистров номера вершины, входы с первого по восьмой установки единицы подключены к соответствующим S-входам группы с первого по восьмой SR триггеров режима, R-входы которых подсоединены к выходу переполнения первой группы с первого по восьмой регистров номера вершины и ко входу группы с первого по восьмой элементов задержки, выход группы с первого по восьмой элементов задержки соединен с соответствующими входами группы элементов ИЛИ, выход группы с первого по восьмой сумматоров подключены к соответствующим входам блока элементов ИЛИ, выход которого подсоединен ко входу сумматора минимального значения, выход которого подсоединен к выходу устройства.

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

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

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

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

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

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

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

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

которое ставит в соответствие каждой подпрограмме один из процессоров.

Минимально значение интенсивности размещения L^* независимо от топологической модели определяется по формуле:

где , – векторы, первый из которых содержит ненулевые элементы матрицы смежности W, расположенные по убыванию, а второй – ненулевые элементы матрицы расстояний D, расположенные по возрастанию; k – порядковый номер элемента; t= - мощность множества дуг графа G. При этом фактическое значение интенсивности размещения всегда либо больше, либо равно L^*, что представляет собой наибольшую частную коммуникационную задержку для заданного отображения β.

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

Предлагаемое устройство может использоваться в области проектирования В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 элемент задержки, первый блок элементов ИЛИ 26, причем выходы блока формирования перестановок 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами блока запоминания лучшего варианта 5, сигнализирующий выход блока формирования перестановок 3 соединен с установочным входом триггера 12 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом арифметико–логического устройства 7, выход которого соединен с информационным входом блока запоминания лучшего варианта 5, а выход блока запоминания лучшего варианта 5 соединен с первым информационным входом арифметико–логического устройства 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 18.1 – 18.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом арифметико–логического устройства 7 и с управляющим входом блока формирования перестановок 3, тактовый вход 46 устройства соединен с входом регистра 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 оперативной памяти, выход элемента И 20 соединен со счетным входом счетчика 14 дуг и со входом элемента 47 задержки, выход которого соединен со вторым входом элемента И 23, первый вход которого соединен с выходом элемента 11 сравнения, второй вход элемента И 20 соединен с прямым выходом триггера 12 начала счета, который также соединен со вторым входом элемента И 21, третий вход элемента И 20 соединен с инверсным выходом триггера 13 режима, прямой выход которого соединен с третьим входом элемента И 21, выход элемента И 21 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 13 режима, вход сброса которого подключен к входу 48 установки устройства, вход сброса триггера 12 начала счета подключен к входу 49 установки устройства, 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 поиска минимального значения, содержащий группу 41.1, 41.2,…,41.8 сумматоров, первую 38.i.j (, ) группу регистров номера вершины, вторую 39.i.j (, ) группу регистров номера вершины, группу 40.1, 40.2,…,40.8 SR триггеров режима, группу 42.1, 42.2, …, 42.8 элементов задержки, дешифратор 35 выбора вершины, счетчик 36 номера вершины, группа 37 элементов ИЛИ, блок 52 элементов ИЛИ, сумматор 53 минимального значения, причем тактовый 46 вход устройства подключен к счетному входу счетчика 36 номера вершины, выход которого подключен ко входу дешифратора 35 выбора вершины, выходы с первого по восьмой которого соединены с соответствующими cs-входам первой 38.i.j (, ) и второй 39.i.j (, ) группа регистров номера вершины, выход переполнения счетчика 36 номера вершины подключен к выходу 43 переполнения устройства, е-входы первой 38.i.j (, ) группы регистров номера вершины подключены к соответствующим прямым выходам группы 40.1, 40.2,…,40.8 SR триггеров режима, обратные выходы которых соединены с соответствующими е-входами второй 39.i.j (, ) группы регистров номера вершины, соответствующие D-входы которых подключены к выходу блока 10 оперативной памяти и к D-входу первой 38.i.j (, ) группы регистров номера вершины, выходы которых подключены к соответствующим первым входам группы 41.1, 41.2,…,41.8 сумматоров, вторые входы которых подключены к соответствующим выходам второй 39.i.j (, ) группы регистров номера вершины, входы 44.1, 44.2,…, 44.8 установки единицы подключены к соответствующим S-входам группы 40.1, 40.2,…,40.8 SR триггеров режима, R-входы которых подсоединены к выходу переполнения первой 38.i.j (, ) группы регистров номера вершины и ко входу группы 42.1, 42.2, …, 42.8 элементов задержки, выход группы 42.1, 42.2, …, 42.8 элементов задержки соединен с соответствующими входами группы 37 элементов ИЛИ, выходы группы 41.1, 41.2,…,41.8 сумматоров подключены к соответствующим входам блока 52 элементов ИЛИ, выход которого подсоединен ко входу сумматора 53 минимального значения, выход которого подсоединен к выходу 54 устройства.

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

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

Группа 37 элементов ИЛИ предназначена для объединения единичных сигналов и подачи их на е-вход счетчика 36 номера вершины.

Первая 38.i.j (, ) группа регистров номера вершины служит для выбора вершины гиперкубической системы.

Вторая 39.i.j (, ) группа регистров номера вершины служит для выбора вершины гиперкубической системы.

Группа 40.1, 40.2,…,40.8 SR триггеров режима служит для одного из двух регистров ().

Группа 41.1, 41.2,…,41.8 сумматоров необходима для суммирования кодов с выходов соответствующих регистров , (, ).

Группа 42.1, 42.2, …, 42.8 элементов задержки служит для задержки прохождения тактового импульса с выхода переполнения первой 38.i.j (, ) группы регистров номера вершины на время, достаточное для прохождения единичного сигнала с обратного выхода группы 40.1, 40.2,…,40.8 SR триггеров на соответствующие е-входы второй 39.i.j (, ) группы регистров номера вершины и далее на второй вход группы 41.1, 41.2,…,41.8 сумматоров.

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

Вход 44.1, 44.2,…,44.8 установки единицы предназначена для установки в единицу соответствующих триггеров группы 40.1, 40.2,…,40.8 SR триггеров.

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

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

Элемент 47 задержки служит для задержки прохождения тактового импульса с выхода счетчика 14 дуг на второй вход элемента 23 И.

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

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

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

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

Блок 52 элементов ИЛИ служит для объединения сигналов с соответствующих выходов группы 41.1, 41.2,…,41.8 сумматоров и подачи на вход сумматора 53 минимального значения.

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

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

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

Первоначально в счетчике 36, регистрах 38.i.j, 39.i.j, сумматорах 41.1, 41.2,…,41.8 содержится код нуля («0…0»). SR-триггеры 40.1, 40.2,…,40.8 находятся в единичном состоянии, поэтому на их прямых выходах присутствует единичный потенциал, который подается на е-входы регистров 38.i.j (, ), а на их обратных выходах присутствует нулевой потенциал, поступающий на е-входы регистров 39.i.j (, ), запрещая этим их работу.

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

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

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

Единичный импульс с тактового 46 входа устройства поступает на счетный вход счетчика 36 и по переднему фронту увеличивает его содержимое на единицу до кода единицы («0…01»). Этот код поступает на вход дешифратора 35 и на его первом выходе возбуждается единичный импульс, который поступает на cs-входы регистров 38.1.1 и 39.1.2. Но, в это время е-входе регистра 38.1.1 присутствует единичный импульс с прямого выхода SR-триггера 40.1. В результате в регистр 38.1.1 разрешается запись кода. Поэтому с выхода блока 10 оперативной памяти в регистр 38.1.1 записывается максимальное значение интенсивности. Этот код подается на первый вход сумматора 41.1. После этого на ое-выходе регистра 38.1.1 возбуждается единичный сигнал, который поступает на вход элемента 42.1 задержки и одновременно на R-вход триггера 40.1, устанавливая его в нулевое состояние. В результате на его обратном выходе появляется единичный сигнал, который поступает на е-вход регистра 38.1.2, разрешая его работу. В результате следующий код с выхода 10 оперативной памяти записывается в регистр 39.1.2, который далее поступает на второй вход сумматора 41.1. Таким образом, суммарное значение с выхода сумматора 41.1 подается на первый вход блока 52 элементов ИЛИ и после этого на счетный вход сумматора 53. В нем по переднему фронту накапливается минимальное значение интенсивности размещения. К этому времени единичный сигнал, задержанный элементом задержки 42.1 подается на вход блока элементов ИЛИ 37 и далее поступает на е-вход счетчика 36, разрешая его работу.

Следующий тактовый импульс поступает на счетный вход счетчика 36 и по переднему фронту увеличивает его работу на единицу до кода двойки («0…010»). Этот код с выхода счетчика 36 поступает на вход дешифратора 35, в результате чего на его втором выходе появляется единичный импульс, который поступает на cs-входы регистров 38.2.1 и 39.2.2. В это время на е-входе регистра 38.2.1 присутствует единичный сигнал с прямого выхода SR-SR-триггера 40.2. В результате очередное значение интенсивности заносится в регистр 38.2.1, которое с его выхода подается на первый вход сумматора 41.2. Таким образом, суммарное значение с выхода сумматора 41.2 подается на второй вход блока 52 элементов ИЛИ и после этого на счетный вход сумматора 53. В нем по переднему фронту накапливается минимальное значение интенсивности размещения.

Одновременно единичный импульс с ое-выхода поступает на вход элемента 42.2 задержки и R-вход SR-триггера 40.2, переводя его в нулевое состояние.

Нулевой потенциал с обратного выхода SR-триггера 40.2 подается на е-вход регистра 39.2.2. Таким образом, он открыт для приема кодов, поэтому очередное значение поступает с выхода блока 10 оперативной памяти и сохраняется в регистре 39.2.2. К этому времени единичный потенциал пропускает элементом задержки 42.2, подается на вход блока 37 элементов ИЛИ и далее на е-вход счетчика 36, разрешая этим его работу. К этому времени код, записанный в регистре 39.2.2 подается на второй вход сумматора 41.2. Таким образом, суммарное значение с выхода сумматора 41.2 подается на вход блока 52 элементов ИЛИ и после этого на счетный вход сумматора 53, в которм по переднему фронту накапливается минимальное значение интенсивности размещения. В результате суммарное значение с его выхода подается на ВУУ многопроцессорной гиперкубической системы для принятия решения о дальнейших действиях.

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

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

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

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