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

Изобретение относится к устройствам поиска минимального значения интенсивности размещения. Технический результат заключается в расширении области применения устройства за счет введения средств для поиска минимального значения интенсивности размещения в тороидальных системах при направленной передаче информации по критерию минимизации интенсивности процессов и данных. Устройство содержит матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, блок минимального значения, содержащий регистр координаты Z, регистр координаты Y, регистр координаты X, счетчик столбца, счетчик столбца, дешифратор уровня, дешифратор столбца, группу из i.j () триггеров выбора, группу из i.j () сумматоров, первая группа элементов И объединения, вторая группа элементов И, сумматор интенсивности. Входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные выходы элементов i-й строки (i = 1,2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства. 1 з.п. ф-лы, 9 ил.

 

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

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

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

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

Техническая задача решается тем, что в устройство для поиска минимального значения интенсивности размещения в торроидальных системах при направленной передаче информации, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j = 1,2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i = 1,2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок минимального значения, содержащий регистр координаты Z, регистр координаты Y, регистр координаты X, счетчик столбца, счетчик столбца, дешифратор уровня, дешифратор столбца, группу из i.j () триггеров выбора, группу из i.j ()сумматоров, первая группа элементов И объединения, вторая группа элементов И, сумматор интенсивности, причем вход устройства соединен со счетным входом первого счетчика столбца, выход переполнения которого подсоединен к счетному входу второго счетчика столбца, выход первого счетчика столбца соединен со входом дешифратора столбца, выход второго счетчика столбца подключен ко входу дешифратора уровня, выходы с первого по n-й которого соединены с соответствующими вторыми входами элементов И группы из i.j () элементов И, выходы которых подключены к соответствующим вторым входам элементов И группы из i.j () элементов И, первый вход элемента И группы из i.j () элементов И подсоединен к инверсному выходу SR-триггера группы из i.j () SR-триггеров выбора, прямой выход которого соединен с S-входом SR-триггера группы из i.j () SR-триггеров выбора, R-вход которого подключен к ое-выходу регистра координаты Y, выход которого подсоединен ко второму входу сумматора группы из i.j () сумматоров, первый вход которого соединен с выходом регистра координаты Z, ое-выход которого подключен к R-входу триггера группы из i.j () SR-триггеров выбора, S-вход которого подсоединен к прямому выходу триггера группы из i.j () SR-триггеров выбора, обратный выход которого подсоединен к е-входу регистра координаты Y и к первому входу элемента И второй группы из i.j () элементов И, выход которого соединен с s-входом регистра координаты X, D-вход которого подключен к выходу блока оперативной памяти, выход регистра координаты X соединен с третьим входом сумматора группы из i.j () сумматоров, ое-выход регистра координаты X подключен к R-входу SR-триггера группы из i.j () SR-триггеров выбора, S-вход которого подсоединен ко входу установки единицы устройства, прямой выход SR-триггера группы из i.j () SR-триггеров выбора подключен к выходу единицы устройства, обратный выход SR-триггера группы из i.j ()SR-триггеров выбора соединен с е-входом регистра координаты Z и с первым входом элемента И второй группы из i.j () элементов И, выходы с 1-го по n-й дешифратора столбца подсоединены к соответствующим первым входам элементов с 1-го по n-й элементов И первой группы из i.j () элементов И объединения, выходы группы из i.j () сумматоров соединены с соответствующими входами сумматора, выход которого подключен к выходу суммы устройства.

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

Сущность изобретения поясняется чертежами, где на фиг. 1 показан пример исходного графа задачи; фиг. 2 показывает пример описания матрицы смежности для исходного графа задачи, показанного на фиг 1; фиг. 3 показывает пример тороидальной топологической организации вычислительной системы; на фиг. 4 показан пример представления нижнего слоя с соответствующими координатами каждого внутреннего процессорного модуля. Каждый модуль представляется тремя координатами по оси х, y и z. Так вершина р_3,1,1 означает модуль, расположенный в третьем (нижнем) слое с координатами (1,1) соответственно; фиг. 5 и 6 представляют два гипотетических варианта размещения; фиг. 7 представляет устройство для поиска минимального значения интенсивности размещения в тороидальных системах при направленной передаче информации; фиг. 8 показывает электронную модель 31.l графа G; фиг. 9 представляет блок 58 минимального значения интенсивности.

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

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

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

Топологическая модель ТС (область размещения) задается матрицей расстояний D. Элементы матрицы расстояний D = ||d_i,j||_n×n для тороидальной системы образуются по формуле Минимальное значение интенсивности размещения для графа G вычисляется по формуле:

,

(1)

где , – векторы, содержащие ненулевые элементы матрицы W и D, расположенные по убыванию и возрастанию соответственно; k – порядковый номер элемента; m= - мощность множества дуг E.

Для удобства дальнейшего описания будем считать, что однородная среда содержит m×n элементов, при этом m=n (где m и n – число процессов). Функционирование однородной среды аналогично прототипу. При поступлении сигнала от внешнего устройства управления (ВУУ) происходит перестановка двух вершин графа и получение нового варианта размещения. Предлагаемое устройство вычисляет значения критериев оценки и выдает указанные значения ВУУ. Последнее анализирует принятые значения и либо фиксирует полученное размещение как более оптимальное, если значения критериев улучшают ранее найденные значения, либо игнорирует его.

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

Сущность предлагаемого критерия поясняется фиг. 1-5. На фиг. 1 представлен гипотетический направленный граф задачи (программы, алгоритма, процесса), а на фиг. 2 – соответствующая ему матрица смежности.

На фиг. 3 показан пример тора, состоящего из трех слоев с соответствующими координатными осями: Х, Y и Z, а на фиг. 4 пример нижнего (первого) слоя. Здесь процессорные модули обозначены точками с соответствующими им координатами. Так, процессорный модуль означает процессор, расположенный в третьем слое с координатами При поиске минимального значения интенсивности размещения предполагается, что наиболее интенсивно взаимодействующие участки исходной задачи (веса дуг с наибольшим объемом передаваемых данных) назначаются на смежные процессорные модули без учета топологии исходного графa G. Таким образом, реальное значение интенсивности размещения должно быть как можно ближе к ранее найденному минимальному значению.

На фиг. 5 представлен вариант размещения для графа G, представленного на фиг. 1. Данный вариант размещения не является минимальным значением, так как все вершины слоя ТС имеют разные значения степени интенсивности, либо не обладают ими вовсе. Используя (1) получаем количественное значение минимального значения интенсивности:

;

;

.

В примере для вектора приведены только начальные значения, влияющие на коэффициент

Таким образом, при поиске минимального значения интенсивности размещения веса дуг графа G назначаются в порядке убывания соответствующих значений. На фиг. 6 представлен вариант размещения одновременно являющийся минимальным значением интенсивности размещения. При «реальном» размещении (процессов, данных и т.д.), значение интенсивности размещения приближается к минимальному значению. Таким образом можно оценить его качество.

Устройство для поиска минимального значения интенсивности размещения в тороидальных системах (фиг. 7,9) при направленной передаче информации содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1, 2.2,…, 2.n подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j = 1,2, …, n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i = 1,2, …, m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 58 минимального значения, содержащий регистр 59.1.1 координаты Z, регистр 60.1.1 координаты Y, регистр 61.1.1 координаты X, счетчик 62 столбца, счетчик 63 столбца, дешифратор 64 уровня, дешифратор 65 столбца, группу 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, группу 69.i.j () сумматоров, первая 70.i.j () группа элементов И объединения, вторая 71.i.j, 72.i.j, 73.i.j () группа элементов И, сумматор 77 интенсивности, причем вход 57 устройства соединен со счетным входом первого 62 счетчика столбца, выход переполнения которого подсоединен к счетному входу второго 63 счетчика столбца, выход первого 62 счетчика столбца соединен со входом дешифратора 65 столбца, выход второго 63 счетчика столбца подключен ко входу дешифратора 64 уровня, выходы с первого по n-й которого соединены с соответствующими вторыми входами элементов И группы 70.i.j () элементов И, выходы которых подключены к соответствующим вторым входам элементов И группы 71.i.j, 72.i.j, 73.i.j () элементов И, первый вход элемента 71.i.j И группы 71.i.j, 72.i.j, 73.i.j () элементов И подсоединен к инверсному выходу SR-триггера 68.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, прямой выход которого соединен с S-входом SR-триггера 67.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, R-вход которого подключен к ое-выходу регистра 60.1.1 координаты Y, выход которого подсоединен ко второму входу 69.1.1 сумматора группы 69.i.j () сумматоров, первый вход которого соединен с выходом регистра 59.1.1 координаты Z, ое-выход которого подключен к R-входу триггера 66.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, S-вход которого подсоединен к прямому выходу триггера 67.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, обратный выход которого подсоединен к е-входу регистра 60.1.1 координаты Y и к первому входу элемента 73.1.1 И второй 71.i.j, 72.i.j, 73.i.j () группы элементов И, выход которого соединен с s-входом регистра 61.1.1 координаты X, D-вход которого подключен к выходу блока 10 оперативной памяти, выход регистра 61.1.1 координаты X соединен с третьим входом 69.1.1 сумматора группы 69.i.j () сумматоров, ое-выход регистра 61.1.1 координаты X подключен к R-входу SR-триггера 68.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора, S-вход которого подсоединен ко входу 76 установки единицы устройства, прямой выход SR-триггера 66.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора подключен к выходу 75 единицы устройства, обратный выход SR-триггера 66.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора соединен с е-входом регистра 59.1.1 координаты Z и с первым входом элемента 72.1.1 И второй 71.i.j, 72.i.j, 73.i.j () группы элементов И, выходы с 1-го по n-й дешифратора 65 столбца подсоединены к соответствующим первым входам элементов с 1-го по n-й элементов И первой 70.i.j () группы элементов И объединения, выходы 69.1.1 группы 69.i.j () сумматоров соединены с соответствующими входами сумматора 77, выход которого подключен к выходу 78 суммы устройства.

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

Назначение элементов и блоков устройства для поиска минимального значения интенсивности размещения (фиг. 7) в тороидальных системах состоит в следующем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Регистр 59.1.1 координаты Z предназначен для хранения значений весов дуг графа G размещенных по координате Z ТС.

Регистр 60.1.1 координаты Y предназначен для хранения значений весов дуг графа G размещенных по координате Y ТС.

Регистр 61.1.1 координаты X предназначен для хранения значений весов дуг графа G размещенных по координате X ТС.

Первый 62 счетчик столбца служит для выбора столбца активной строки ТС.

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

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

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

Группа 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора необходима для выбора одного из 59.i.j, 60.i.j, 61.i.j регистров координат Z, Y и X соответственно и служат для сохранения информации о загрузке модулей ТС.

Группа 69.i.j () сумматоров предназначена для накопления суммы кодов значений, размещенных в узле ТС.

Первая 70.i.j () группа элементов И объединения служит для объединения кодов, поступающих с выхода дешифратора 65 столбца и инверсных выходов группы 66.i.j, 67.i.j, 68.i.j SR-триггеров выбора.

Вторая 71.i.j, 72.i.j, 73.i.j () группа элементов И необходима для объединения сигналов, поступающих с выхода элемента 70 И объединения.

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

Выход 75 единицы служит для подачи сигнала о единичном значении триггера 66.i.j группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора.

Вход 76 установки единицы необходим для установки в единичное состояние триггера 68.1.1 группы 66.i.j, 67.i.j, 68.i.j () SR-триггеров выбора.

Сумматор 77 интенсивности, предназначен для суммирования частных кодов значений интенсивности размещения.

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

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

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

Первоначально в счетчике 63 содержится код единицы, который поступает на вход дешифратора 64 и на его первом выходе появляется единичный импульс, который поступает на второй вход элемента И 70. В счетчике 62 хранится код нуля («0…00»). В регистрах 59.1.1, 60.1.1, 61.1.1 хранятся коды значений нуля. Триггеры 66.1.1, 67.1.1, 68.1.1 установлены в нулевое состояние. Это значит, что на прямых их выходах присутствует нулевой потенциал, а инверсном – единичный, который поступает на соответствующие е-входы регистров 59.1.1, 60.1.1, 61.1.1, разрешая их работу. Так же этот импульс подается на первые вход элемента 72.1.1 И. Так как на е-входе регистра 59.1.1 присутствует единичный потенциал, то код с выхода 10 блока оперативной памяти поступает на D-входы регистров 59.1.1, 60.1.1, 61.1.1, но запись происходит только в регистр 59.1.1, так как только на его е-входе присутствует единичный поетнециал.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Очередной тактовый импульс с входа 57 поступает на счетный вход счетчика 62 и по переднему фронту увеличивает его содержимое на единицу до кода единицы («0…01»). Этот код поступает на вход дешифратора 65, из-за чего на его первом выходе появляется единичный импульс, который поступает на первый вход элемента 70 И. Так как на его двух входах присутствует единичные импульсы, то на его выходе появляется единичный потенциал, поступающий на второй вход элемента 72.1.1.

В это время, из-за того, что в регистр 59.1.1 был записан код значения интенсивности из блока 10 оперативной памяти, то на его oe-выходе появляется единичный импульс, который поступает на R-вход триггера, переводя его в нулевой состояние. Таким образом, на его прямом выходе появляется нулевой потенциал, на обратном – единичный, который поступает на е-вход регистра 59.1.1, запрещая его работу. Одновременно единичный потенциал с обратного выхода триггера 66.1.1 поступает на первый вход элемента 72.1.1 И. Код значения интенсивности с выхода регистра 59.1.1 поступает на первый вход сумматора 77. Нулевой потенциал с прямого выхода триггера 66.1.1 подается на выход 75 устройства.

В результате на выходе элемента 72.1.1 И появляется единичный сигнал, который поступает на s-вход регистра 60.1.1, разрешая запись в него поступающих кодов. Тогда очередное значение с выхода блока 10 оперативной памяти заносится в регистр 60.1.1. В результате, аналогично принципу, описанному выше, на ое-выходе появляется единичный потенциал, который подается на R-вход триггера 67.1.1 и устанавливает его в нулевое состояние. Из-за этого на его прямом выходе появляется нулевой потенциал, а на инверсном единичный. Единичный сигнал с инверсного выхода триггера 67.1.1 поступает на е-вход регистра 60.1.1, запрещая его работу. Единичный потенциал с прямого выхода триггера 67.1.1 поступает на S-вход триггера 66.1.1, устанавливая его в единичное состояние. Единичный сигнал с инверсного выхода триггера 67.1.1 также поступает на первый вход элемента 73.1.1 И, на втором входе которого присутствует единичный сигнал с выхода элемента 70 И. В результате на выходе элемента 73.1.1 И появляется единичный сигнал, который подается на s-вход регистра 61.1.1, разрешая тем самым запись в него кодов. Таким образом, очередной код с выхода блока 10 оперативной памяти записывается в регистр 61.1.1, в результате чего на его oe-выходе появляется единичный потенциал, поступающий на R-вход триггера 68.1.1, переводя его в нулевое состояние. Тогда, единичный сигнал с его выхода поступает на первый вход элемента 71.1.1 И.

Очередной тактовый импульс поступает на счетный вход счетчика 62 и по переднему фронту увеличивает его работу на единицы до кода двойки («0…010»). Далее аналогично описанному выше принципу код двойки подается на вход дешифратора 65, в результате чего на его втором входе появляется единичный импульс, в результате чего на его втором выходе появляется единичный потенциал. Далее работа схема протекает аналогично. Так происходит до тех пор, пока на выходе переполнения счетчика 62 не появится единичный импульс, свидетельствующие о том, что размещение в первом слое закончено.

Единичный потенциал с выход переполнения счетчика 62 поступает на счетный вход счетчика 63, увеличивая его содержимое по переднему фронту на единицу до кода двойки («0…010»). Этот код подается на вход дешифратора 64, в результате чего на его втором выходе появляется единичный потенциал. Далее размещение протекает аналогично.

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

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

1. Устройство для поиска минимального значения интенсивности размещения в тороидальных системах при направленной передаче информации, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j = 1,2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i = 1,2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, отличающееся тем, что в него дополнительно введен блок минимального значения, содержащий регистр координаты Z, регистр координаты Y, регистр координаты X, счетчик столбца, счетчик столбца, дешифратор уровня, дешифратор столбца, группу из i.j () триггеров выбора, группу из i.j () сумматоров, первая группа элементов И объединения, вторая группа элементов И, сумматор интенсивности, причем вход устройства соединен со счетным входом первого счетчика столбца, выход переполнения которого подсоединен к счетному входу второго счетчика столбца, выход первого счетчика столбца соединен со входом дешифратора столбца, выход второго счетчика столбца подключен ко входу дешифратора уровня, выходы с первого по n-й которого соединены с соответствующими вторыми входами элементов И группы из i.j () элементов И, выходы которых подключены к соответствующим вторым входам элементов И группы из i.j () элементов И, первый вход элемента И группы из i.j () элементов И подсоединен к инверсному выходу SR-триггера группы из i.j () SR-триггеров выбора, прямой выход которого соединен с S-входом SR-триггера группы из i.j () SR-триггеров выбора, R-вход которого подключен к ое-выходу регистра координаты Y, выход которого подсоединен ко второму входу сумматора группы из i.j () сумматоров, первый вход которого соединен с выходом регистра координаты Z, ое-выход которого подключен к R-входу триггера группы из i.j () SR-триггеров выбора, S-вход которого подсоединен к прямому выходу триггера группы из i.j () SR-триггеров выбора, обратный выход которого подсоединен к е-входу регистра координаты Y и к первому входу элемента И второй группы из i.j () элементов И, выход которого соединен с s-входом регистра координаты X, D-вход которого подключен к выходу блока оперативной памяти, выход регистра координаты X соединен с третьим входом сумматора группы из i.j () сумматоров, ое-выход регистра координаты X подключен к R-входу SR-триггера группы из i.j () SR-триггеров выбора, S-вход которого подсоединен ко входу установки единицы устройства, прямой выход SR-триггера группы из i.j () SR-триггеров выбора подключен к выходу единицы устройства, обратный выход SR-триггера группы из i.j () SR-триггеров выбора соединен с е-входом регистра координаты Z и с первым входом элемента И второй группы из i.j () элементов И, выходы с 1-го по n-й дешифратора столбца подсоединены к соответствующим первым входам элементов с 1-го по n-й элементов И первой группы из i.j () элементов И объединения, выходы группы из i.j () сумматоров соединены с соответствующими входами сумматора, выход которого подключен к выходу суммы устройства.

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