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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

Сущность изобретения поясняется чертежами, где на фиг.1 изображена функциональная схема устройства поиска нижней оценки размещения в полносвязных матричных системах (МС) при однонаправленной передаче информации; фиг.2 поясняет сущность использования электронной модели графа; фиг.3 иллюстрирует принцип работы блока 58 формирования нижней оценки в полносвязных МС при однонаправленной передаче информации; фиг.4. поясняет принцип работы предлагаемого устройства.

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

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

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

МС отображается однородной средой, которой ставится в соответствие топологическая модель в виде графа H=<U,V>, где

- множество модулей МС, организованных в матрицу , где n является количеством модулей МС и количеством вершин графа G, V - множество межмодульных связей.

Размещение графа G в МС Н будем задавать в виде отображения:

где , , !

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

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

Принцип поиска нижней оценки размещения иллюстрируется на фиг.4. Здесь на фиг.4а представлен гипотетический граф G из 9 вершин, а на фиг.4б соответствующая ему матрица смежности W. На фиг 4в, 4г показаны гипотетические варианты размещения дуг графа в МС. Модули МС представлены квадратами, в левом верхнем углу которых представлены их номера, пунктирные линии обозначают связи модулей МС, сплошные линии показывают гипотетические зафиксированные дуги. При поиске нижней оценки размещения предполагается, что топологии исходного графа G и графа связей Н между модулями тождественны. То есть при вычислении нижней оценки, дуги графа G с наибольшим весом назначаются на самые короткие маршруты в графе Н, не обращая внимания на ограничения, накладываемые фактическими связями между задачами. Полученное суммарное значение интенсивности является нижней оценкой размещения. В случае «реального» варианта размещения его качество будет тем лучше, чем его суммарное значение интенсивности будет ближе к минимальной нижней оценке. Поэтому при размещении задач (алгоритмов, процессов, данных) необходимо стремится к этому значению. Из фиг.4г видно, что такой вариант размещения не является нижней оценкой, так как в нем например на модули 1-2 и 4-7 назначены по две дуги графа, что ведет к неизбежному увеличению объема передачи данных между этими модулями. Вариант размещения на фиг 4в устраняет эту проблему и одновременно является нижней оценкой размещения. Минимизация суммарного объема передаваемых данных важна для уменьшения общего времени выполнения задачи. Следовательно, при проектировании устройства фактически необходимо просматривать матрицу смежности графа G, не обращая внимания на связи и последовательно назначать дуги на модули матрицы Н.

Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации (фиг.1) содержит первый регистр 1 сдвига, второй регистр 2 сдвига, блок 3 формирования перестановок (БФП), блок 4 постоянной памяти, блок 5 запоминания лучшего варианта (БЗЛВ), коммутатор 6, АЛУ 7, дешифратор 8 выбора дуги, реверсивный счетчик 9 ячеек, блок 10 оперативной памяти, счетчик 11 топологии, первый 12 и второй 13 счетчики расстояний, умножитель 14, сумматор 15, регистр 16 минимальной длины связей, первый элемент 17 сравнения, вычитатель 18, триггер 19 начала счета, триггер 23 режима, триггер 24 задания топологии, регистр 25 длины связей, второй элемент 26 сравнения, счетчик 27 дуг, дешифратор 28 блокировки дуги, регистр 29 номера дуги, регистр 30 минимального веса, электронную модель 31 графа, группу элементов ИЛИ 32.1-32.n, группу элементов И 33.1-33.m, первый 34 и второй 35 элементы И, второй блок элементов ИЛИ 36, третий элемент И 37, первый 41 и второй 42 одновибраторы, первый 43, второй 44 и третий 45 элементы задержки, первый блок элементов ИЛИ 46, причем выходы БФП 3 соединены с соответствующими входами блока 4 постоянной памяти и соответствующими входами БЗЛВ 5, сигнализирующий выход БФП 3 соединен с установочным входом триггера 19 начала счета, выходы блока 4 постоянной памяти соединены с соответствующими входами коммутатора 6, выход которого соединен с входом АЛУ 7, выход которого соединен с информационным входом БЗЛВ 5, а выход БЗЛВ 5 соединен с первым информационным входом АЛУ 7, выход переполнения регистра 1 сдвига соединен с входом регистра 2 сдвига, выходы регистров 1 и 2 с первого по n-й подключены к первым и вторым входам элементов ИЛИ 32.1-32.n соответственно, выход переполнения регистра 2 сдвига соединен с управляющим входом АЛУ 7 и с управляющим входом БФП 3, тактовый вход 57 устройства соединен с входом регистра 1 сдвига, с тактовым входом БФП 3 и с первыми входами элементов И 34 и 35, выход счетчика 27 дуг соединен с входом дешифратора 8 выбора дуги и входом данных регистра 29 номера дуги, выход блока элементов ИЛИ 36 подключен к первому входу элемента 17 сравнения и к входу данных регистра 30 минимального веса, выход регистра 30 минимального веса соединен с вторым входом элемента 17 сравнения и с входом данных блока 10 оперативной памяти, выход элемента 43 задержки соединен с входом установки регистра 30 минимального веса и с входом установки регистра 29 номера дуги, выход третьего элемента И 37 соединен с синхровходом регистра 30 минимального веса и с синхровходом регистра 29 номера дуги, выход регистра 29 номера дуги соединен с информационным входом дешифратора 28 блокировки дуги, выход переполнения счетчика 27 дуг соединен с разрешающим входом дешифратора 28 блокировки дуги, а также с входом элемента 43 задержки, первым счетным входом реверсивного счетчика 9 ячеек и входом записи блока 10 оперативной памяти, выход элемента И 34 соединен со счетным входом счетчика 27 дуг и со входом элемента 44 задержки, выход которого соединен со вторым входом элемента И 37, первый вход которого соединен с выходом элемента 17 сравнения, второй вход элемента И 34 соединен с прямым выходом триггера 19 начала счета, который также соединен со вторым входом элемента И 35, третий вход элемента И 34 соединен с инверсным выходом триггера 23 режима, прямой выход которого соединен с третьим входом элемента И 35, выход элемента И 35 соединен со вторым счетным входом реверсивного счетчика 9 ячеек, выход которого подключен к адресному входу блока 10 оперативной памяти, выход которого подключен к первому входу умножителя 14, выход счетчика 13 расстояний подключен к второму входу умножителя 14, выход которого подключен к первому входу сумматора 15, второй вход которого подключен к выходу регистра 16 минимальной длины связей и к второму входу вычитателя 18, выход сумматора 15 подключен к входу данных регистра 16 минимальной длины связей, выход элемента 45 задержки подключен к синхровходу регистра 16 минимальной длины связей, выход элемента И 35 и счетный вход счетчика 12 расстояний подключены к входу элемента 45 задержки, выход одновибратора 42 подключен к синхровходу счетчика 12 расстояний, выход переполнения которого подключен к счетным входам счетчика 11 топологии, счетчика 13 расстояний и к входу одновибратора 42, выход счетчика 11 топологии подключен к входу счетчика 12 расстояний, вход 51 данных устройства подключен ко входу данных счетчика 11 топологии, синхровход счетчика 11 топологии подключен к входу 52 установки устройства, прямой выход триггера 24 задания топологии подключен к разрешающему входу счетчика 11 топологии, установочный вход триггера 24 задания топологии подключен к входу 49 установки устройства, вход сброса триггера 24 задания топологии подключен к входу 50 установки устройства, выход переполнения реверсивного счетчика 9 ячеек подключен к установочному входу триггера 23 режима, вход сброса которого подключен к входу 48 установки устройства, выход регистра 25 длины связей подключен ко второму входу элемента 26 сравнения и к первому входу вычитателя 18, первый вход элемента 26 сравнения подключен к выходу АЛУ 7 и входу данных регистра 25 длины связей, выход одновибратора 41 подключен к синхровходу регистра 25 длины связей, вход сброса триггера 19 начала счета подключен к входу 47 установки устройства, l-й выход дешифратора 8 выбора дуги (l=1, 2, …, m) соединен с l-м входом выбора дуги электронной модели 31 графа, l-й выход дешифратора 28 блокировки дуги соединен с l-м входом блокировки дуги электронной модели 31 графа, l-й выход веса дуги электронной модели 31 графа соединен с l-м входом блока элементов ИЛИ 36 и l-м входом блока элементов ИЛИ 46, выход элемента И 33.l соединен с l-м управляющим входом электронной модели 31 графа, выход блока элементов ИЛИ 46 соединен со вторым информационным входом АЛУ 7, выход элемента 26 сравнения соединен с входом одновибратора 41, выходы элементов ИЛИ 32.1-32.n подключены к соответствующим входам элементов И 33.1-33.m, выход вычитателя 18 соединен с выходом 53 длины связей устройства, а также дополнительно введенный блок 58 формирования нижней оценки, содержащий матрицу 59.i.j (i=1, 2, …, m; j=1, 2, …, n) сумматоров, первый 71 и второй 60 счетчики строк, первый 61 и второй 62 счетчик столбцов, матрицу 63.i.j (i=1, 2, …, m; j=1, 2, …, n) регистров, первый 64 и второй 65 дешифраторы горизонтально зафиксированных дуг, первый 66 и второй 67 дешифраторы вертикально зафиксированных дуг, матрицу 68.i.j (i=1, 2, …, m; j=1, 2, …, n) элементов ИЛИ, первую 69.i.j (i=1, 2, …, m; j=1, 2, …, n) и вторую 70. i.j (i=1, 2, …, m; j=1, 2, …, n) матрицу элементов И, первый 78 элемент ИЛИ, RS-триггер 79 запрета, второй 92 элемент ИЛИ, третий 80 и четвертый 81 счетчик строк, третий 82 счетчик инцидентной вершины, первый 89 и второй 90 элемент И, причем вход 75 устройства подключен к S-входу RS-триггера 79 запрета, R-вход которого подсоединен к выходу переполнения первого 61 счетчика столбцов, прямой выход RS-триггера 79 запрета подключен ко второму входу второго 90 элемента И, а также к первому входу первого 89 элемента И, инверсный выход RS-триггера 79 запрета подключен к е-входам третьего 80 и четвертого 81 счетчика строк, а также к е-входу третьего 82 счетчика инцидентной вершины, с-вход которого подсоединен к выходу переполнения третьего 80 счетчика строк и к r-входу четвертого 81 счетчика строк, выход переполнения третьего 82 счетчика инцидентной вершины подсоединен к выходу 93 переполнения устройства, тактовый 57 вход устройства подсоединен к счетному входу четвертого 81 счетчика строк, ое-вход которого подсоединен к прямому выходу триггера 23 режима, выход переполнения четвертого 81 счетчика строк подключен к счетному входу третьего 80 счетчика строк и счетному входу третьего 82 счетчика инцидентной вершины, первый вход второго 92 элемента ИЛИ подключен к выходу первого 71 счетчика строк, выход переполнения которого подсоединен к счетному входу второго 60 счетчика строк, выход переполнения которого соединен с разрешающими входами первого 61 и второго 62 счетчика столбцов, выход переполнения которого подсоединен к счетному входу первого 61 счетчика столбцов, счетный вход второго 62 счетчика столбцов соединен с тактовым 57 входом устройства, выход второго 62 счетчика столбцов подключен к входу второго 67 дешифратора вертикально зафиксированных дуг, выход первого 61 счетчика столбцов соединен с входом первого 66 дешифратора вертикально зафиксированных дуг, ое-вход первого 71 счетчика строк подключен к выходу первого 89 элемента И, второй вход которого соединен с прямым выходом триггера 23 режима, тактовый 57 вход устройства подключен к первому входу второго 90 элемента И, выход которого соединен со счетным входом первого 71 счетчика строк, выход третьего 80 счетчика строк соединен с первым входом первого 78 элемента ИЛИ, второй вход которого подключен к выходу третьего 82 счетчика инцидентной вершины, третий вход первого 78 элемента ИЛИ соединен с выходом второго 60 счетчика строк, выход первого 78 элемента ИЛИ подключен ко входу первого 64 дешифратора горизонтально зафиксированных дуг, выходы с первого по n-й которого соединены с соответствующими вторыми входами групп (70.1.1, 70.2.1, …, 70.m.1), (70.2.1, 70.2.2, …, 70.m.2),…, (70.m.1, 70.m.2, …, 70.m.n) второй 70.i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы элементов И, выходы с первого по n-й второго 65 дешифратора горизонтально зафиксированных дуг соединены с соответствующими первыми входами групп (70.1.1, 70.1.2, …, 70.1.n), (70.2.1, 70.2.2, …, 70.2.n), …, (70.m.1, 70.m.2, …, 70.m.n) второй 70.i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы элементов И, выходы с первого по n-й второго 67 дешифратора вертикально зафиксированных дуг соединен с соответствующими вторыми входами групп (69.1.1, 69.1.2, …, 69.1.n), (69.2.1, 69.2.2, …, 69.2.n), …, (69.m.1, 69.m.2, …, 69.m.n) элементов первой 69.i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы элементов И, выходы с первого по n-й первого 66 дешифратора вертикально зафиксированных дуг подключен к соответствующим первым входам групп (69.1.1, 69.2.1, …, 69.m.1), (69.2.1, 69.2.2, …, 69.m.2), …, (69.m.1, 69.m.2, …, 69.m.n) элементов первой 69.i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы элементов И, выход элементов 69.i.j (i=1, 2, …, m; j=1, 2,…, n) И первой 69. i.j (i=1, 2, …,m; j=1, 2, …, n) матрицы элементов И подключен к первому входу элемента 68. i.j (i=1, 2, …, m; j=1, 2, …, n) ИЛИ матрицы 68. i.j (i=1, 2, …, m; j=1, 2, …, n) элементов ИЛИ, соответствующие вторые входы которых подключены к выходам элементов 70.i.j (i=1, 2, …, m; j=1, 2, …, n) И второй 70. i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы элементов И, выходы элементов 68.i.j (i=1, 2, …, m; j=1, 2, …, n) ИЛИ матрицы 68. i.j (i=1, 2, …, m; j=1, 2, …, n) элементов ИЛИ подсоединены к соответствующим разрешающий ое-входам 63.i.j (i=1, 2, …, m; j=1, 2, …, n) матрицы 63. i.j (i=1, 2, …, m; j=1, 2, …, n) регистров, выходы которых подключены к соответствующим первым входам элементов 59. i.j (i=1, 2,…,m; j=1, 2,…, n) матрицы 59.i.j (i=1, 2, …, m; j=1, 2, …, n) сумматоров, ко вторым входам которых подключен выход блока 10 оперативной памяти, выходы элементов 59.i.j (i=1, 2, …m; j=1, 2, …, n; матрицы 59. i.j (i=1, 2, …, m; j=1, 2, …, n) сумматоров подсоединены к соответствующим D-входам матрицы 63.i.j (i=1, 2, …, m; j=1, 2, …, n) регистров, выход четвертого 81 счетчика строк соединены с третьим входом второго 92 элемента ИЛИ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Регистр 16 минимальной длины связей хранит значение минимально возможной длины связей L^∗ для заданного графа (на фиг.1 не показан).

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

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

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

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

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

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

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

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

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

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

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

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

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