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

Формула изобретения

1. Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации, содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с 1-го по n-й элементов ИЛИ, группу 1-го по m-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения первого регистра сдвига соединен с входом второго регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ 1-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу первого элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен с вторым входом первого элемента сравнения и с входом данных блока оперативной памяти, выход первого элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом первого элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом второго элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход второго счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход третьего элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход первого счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, второго счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу второго элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход первого одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2, , m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом второго блока элементов ИЛИ и l-м входом первого блока элементов ИЛИ, l-й выход элемента И группы элементов И с l-го по m-й соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход второго элемента сравнения соединен с входом первого одновибратора, выходы элементов с l-го по n-й ИЛИ подключены к соответствующим входам элементов И l-го по 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) элементов И, первый и второй элементы задержки, первый и второй счетчик инцидентной вершины, первый и второй элементы ИЛИ, причем тактовый вход устройства подключен к счетным входам второго счетчика столбцов, первого счетчика инцидентной вершины и первого счетчика строк, прямой выход триггера режима подключен к разрешающему входу ое первого счетчика строк, выход переполнения которого подсоединен к счетным входам второго счетчика строк и второго счетчика инцидентной вершины, выход переполнения второго счетчика строк подключен к закрывающему входу с второго счетчика инцидентной вершины и к разрешающим входам ое первого счетчика столбцов, второго счетчика столбцов и первого счетчика инцидентной вершины, выход переполнения второго счетчика столбцов соединен со счетным входом первого счетчика столбцов и со входом сброса первого счетчика инцидентной вершины, выход которого подключен к входу первого элемента задержки, выход которого соединен со вторым входом первого элемента ИЛИ, первый вход которого подключен к выходу второго счетчика столбцов, выход переполнения первого счетчика столбцов подключен к выходу переполнения устройства, выход второго счетчика строк подключен ко второму входу второго элемента ИЛИ, первый вход которого подсоединен к выходу второго элемента задержки, вход которого соединен с выходом второго счетчика инцидентной вершины, выход второго элемента ИЛИ подключен к входу первого дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подсоединены к соответствующим вторым входам элементов i.1, i.2, , i.n (i=1, 2, , m) И второй матрицы из (i.j) i/=1, 2, , m; j=1, 2, , n) элементов И, выход первого счетчика строк подсоединен к входу второго дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подключены к соответствующим первым входам элементов 1.j, 2.j, , m.j (j=1, 2, , n) И второй матрицы из (i.j) (i=1, 2, , m; j=1, 2, , n) элементов И, выход первого элемента ИЛИ подключен к входу второго дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим вторым входам элементов 1.j, 2.j, , m.j (j=1, 2, , n) И второй матрицы из (i.j) (i=1, 2, , m; j=1, 2, , n) элементов И, выход первого элемента ИЛИ, выход первого счетчика столбцов соединен с входом первого дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим первым входам элементов i.1, i.2, , 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=j, 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) регистров, выходы элементов из (i.j) (i=1, 2, , m; j=1, 2, , n) матрицы регистров подключены к соответствующим выходам устройства.

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

Описание изобретения к патенту

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 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), содержащее первый регистр сдвига, второй регистр сдвига, блок формирования перестановок (БФП), блок постоянной памяти, блок запоминания лучшего варианта (БЗЛВ), коммутатор, АЛУ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, первый и второй счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, первый элемент сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, второй элемент сравнения, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, электронную модель графа, группу с l-го по n-й элементов ИЛИ, группу l-го по m-й элементов И, первый и второй элементы И, второй блок элементов ИЛИ, третий элемент И, первый и второй одновибраторы, первый, второй и третий элементы задержки, первый блок элементов ИЛИ, причем выходы БФП соединены с соответствующими входами блока постоянной памяти и соответствующими входами БЗЛВ, сигнализирующий выход БФП соединен с установочным входом триггера начала счета, выходы блока постоянной памяти соединены с соответствующими входами коммутатора, выход которого соединен с входом АЛУ, выход которого соединен с информационным входом БЗЛВ, а выход БЗЛВ соединен с первым информационным входом АЛУ, выход переполнения регистра сдвига соединен с входом регистра сдвига, выходы первого и второго регистров сдвига с первого по n-й подключены к первым и вторым входам элементов ИЛИ l-го по n-й соответственно, выход переполнения регистра сдвига соединен с управляющим входом АЛУ и с управляющим входом БФП, тактовый вход устройства соединен с входом регистра сдвига, с тактовым входом БФП и с первыми входами первого и второго элементов И, выход счетчика дуг соединен с входом дешифратора выбора дуги и входом данных регистра номера дуги, выход блока элементов ИЛИ подключен к первому входу элемента сравнения и к входу данных регистра минимального веса, выход регистра минимального веса соединен со вторым входом элемента сравнения и с входом данных блока оперативной памяти, выход элемента задержки соединен с входом установки регистра минимального веса и с входом установки регистра номера дуги, выход третьего элемента И соединен с синхровходом регистра минимального веса и с синхровходом регистра номера дуги, выход регистра номера дуги соединен с информационным входом дешифратора блокировки дуги, выход переполнения счетчика дуг соединен с разрешающим входом дешифратора блокировки дуги, а также с входом элемента задержки, первым счетным входом реверсивного счетчика ячеек и входом записи блока оперативной памяти, выход первого элемента И соединен со счетным входом счетчика дуг и со входом элемента задержки, выход которого соединен со вторым входом третьего элемента И, первый вход которого соединен с выходом элемента сравнения, второй вход первого элемента И соединен с прямым выходом триггера начала счета, который также соединен со вторым входом второго элемента И, третий вход первого элемента И соединен с инверсным выходом триггера режима, прямой выход которого соединен с третьим входом второго элемента И, выход второго элемента И соединен со вторым счетным входом реверсивного счетчика ячеек, выход которого подключен к адресному входу блока оперативной памяти, выход которого подключен к первому входу умножителя, выход счетчика расстояний подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу регистра минимальной длины связей и к второму входу вычитателя, выход сумматора подключен к входу данных регистра минимальной длины связей, выход элемента задержки подключен к синхровходу регистра минимальной длины связей, выход второго элемента И и счетный вход счетчика расстояний подключены к входу третьего элемента задержки, выход второго одновибратора подключен к синхровходу счетчика расстояний, выход переполнения которого подключен к счетным входам счетчика топологии, счетчика расстояний и к входу второго одновибратора, выход счетчика топологии подключен к входу счетчика расстояний, вход данных устройства подключен ко входу данных счетчика топологии, синхровход счетчика топологии подключен к входу установки устройства, прямой выход триггера задания топологии подключен к разрешающему входу счетчика топологии, установочный вход триггера задания топологии подключен к входу установки устройства, вход сброса триггера задания топологии подключен к входу установки устройства, выход переполнения реверсивного счетчика ячеек подключен к установочному входу триггера режима, вход сброса которого подключен к входу установки устройства, выход регистра длины связей подключен ко второму входу элемента сравнения и к первому входу вычитателя, первый вход элемента сравнения подключен к выходу АЛУ и входу данных регистра длины связей, выход одновибратора подключен к синхровходу регистра длины связей, вход сброса триггера начала счета подключен к входу установки устройства, l-й выход дешифратора выбора дуги (l=1, 2, , m) соединен с l-м входом выбора дуги электронной модели графа, l-й выход дешифратора блокировки дуги соединен с l-м входом блокировки дуги электронной модели графа, l-й выход веса дуги электронной модели графа соединен с l-м входом блока элементов ИЛИ и l-м входом блока элементов ИЛИ, l-й выход элемента И группы элементов И с l-го по m-й соединен с l-м управляющим входом электронной модели графа, выход блока элементов ИЛИ соединен со вторым информационным входом АЛУ, выход элемента сравнения соединен с входом первого одновибратора, выходы элементов с l-го по n-й ИЛИ подключены к соответствующим входам элементов И l-го по 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) матрицы элементов И, первый и второй элементы задержки, первый и второй счетчик инцидентной вершины, первый и второй элементы ИЛИ, причем тактовый вход устройства подключен к счетным входам второго счетчика столбцов, первого счетчика инцидентной вершины и первого счетчика строк, прямой выход триггера режима подключен к входу ое первого счетчика строк, выход переполнения которого подсоединен к счетным входам второго счетчика строк и второго счетчика инцидентной вершины, выход переполнения второго счетчика строк подключен к закрывающему входу с второго счетчика инцидентной вершины и к разрешающим входам ое первого счетчика столбцов, второго счетчика столбцов и первого счетчика инцидентной вершины, выход переполнения второго счетчика столбцов соединен со счетным входом первого счетчика столбцов и со входом сброса первого счетчика инцидентной вершины, выход которого подключен к входу первого элемента задержки, выход которого соединен со вторым входом первого элемента ИЛИ, первый вход которого подключен к выходу второго счетчика столбцов, выход переполнения первого счетчика столбцов подключен к выходу переполнения устройства, выход второго счетчика строк подключен к первому входу второго элемента ИЛИ, первый вход которого подсоединен к выходу второго элемента задержки, вход которого соединен с выходом второго счетчика инцидентной вершины, выход второго элемента ИЛИ подключен к входу первого дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подсоединены к соответствующим вторым входам элементов i.1, i.2, , i.n (i=1, 2, , m) И, выход первого счетчика строк подсоединен к входу второго дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подключены к соответствующим первым входам элементов 1.j, 2.j, , m.j (l=1, 2, , n) И, выход первого элемента ИЛИ подключен к входу второго дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим вторым входам элементов 1.j, 2.j, , m.j (j=1, 2, , n), выход первого счетчика столбцов соединен с входом первого дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим первым входам элементов i,1, i,2, , i,j (i=1, 2, , m), выходы из (i.j) (j=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) регистров, выходы элементов из (i.j) (i=1, 2, , m, j=1, 2, , n) матрицы регистров подключены к соответствующим выходам устройства.

Электронная модель графа содержит 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= w_{ij N×N}, где N=n²=|Х|; w_ij - объем передаваемых данных между i-м и j-м процессорным модулем.

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

- множество модулей МС, организованных в матрицу |U|=N=n, где 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в устраняет эту проблему и одновременно является нижней оценкой размещения. Минимизация суммарного объема передаваемых данных важна для уменьшения общего времени выполнения задачи.

Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации (фиг.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) матрицы элементов И, первый 73 и второй 74 элементы задержки, первый 75 и второй 76 счетчики инцидентной вершины, первый 77 и второй 78 элементы ИЛИ, причем тактовый вход 57 устройства подключен к счетным входам второго 62 счетчика столбцов, первого 75 счетчика инцидентной вершины и первого 71 счетчика строк, прямой выход триггера 23 режима подключен к входу ое первого 71 счетчика строк, выход переполнения которого подсоединен к счетным входам второго 60 счетчика строк и второго 76 счетчика инцидентной вершины, выход переполнения второго 60 счетчика строк подключен к закрывающему входу с второго 76 счетчика инцидентной вершины и к разрешающим входам ое первого 61 счетчика столбцов, второго 62 счетчика столбцов и первого 75 счетчика инцидентной вершины, выход переполнения второго 62 счетчика столбцов соединен со счетным входом первого 61 счетчика столбцов и со входом сброса первого 75 счетчика инцидентной вершины, выход которого подключен к входу первого 73 элемента задержки, выход которого соединен со вторым входом первого 77 элемента ИЛИ, первый вход которого подключен к выходу второго 62 счетчика столбцов, выход переполнения первого 61 счетчика столбцов подключен к выходу 72 переполнения устройства, выход второго 60 счетчика строк подключен к первому входу второго 78 элемента ИЛИ, первый вход которого подсоединен к выходу второго 74 элемента задержки, вход которого соединен с выходом второго 76 счетчика инцидентной вершины, выход второго 78 элемента ИЛИ подключен к входу первого 64 дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подсоединены к соответствующим вторым входам элементов 70.i.1, 70.i.2, , 70.i.n (i=1, 2, , m) И, выход первого 71 счетчика строк подсоединен к входу второго 65 дешифратора горизонтально зафиксированных дуг, выходы с l-го по m-й которого подключены к соответствующим первым входам элементов 70.1.j, 70.2,j, , 70.m.j (j=1, 2, , n) И, выход первого 77 элемента ИЛИ подключен к входу второго 67 дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим вторым входам элементов 69.1.j, 69.2.j, , 69.m.j (j=1, 2, , n), выход первого 61 счетчика столбцов соединен с входом первого 66 дешифратора вертикально зафиксированных дуг, выходы с первого по m-й которого подсоединены к соответствующим первым входам элементов 69.i,1, 69.i,2, , 69.i,j (i=1, 2, , m), выходы элементов 69.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) И подключены к соответствующим вторым входам элементов 68.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) сумматоров, вторые входы которых подключены к выходу блока 10 оперативной памяти, выходы матрицы 59.i.j (i=1, 2, , m; j=1, 2, , n) сумматоров соединены с D-входами 63.i.j (i=1, 2, , m; j=1, 2, , n) регистров, выходы элементов 63.i.j (i=1, 2, , m; j=1, 2, , n) матрицы регистров подключены к соответствующим выходам устройства.

Электронная модель 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 веса дуги.

Назначение элементов и блоков устройства (фиг.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 количества обрабатываемых элементов вектора d _k с заданным значением (для кольцевой топологической модели общее число таких элементов постоянно и составляет n, для линейной - это число уменьшается от n-l для d^' _k=l до l для d _k=n-l).

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

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

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

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

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

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

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

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

Триггер 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, представляющего размещаемый объект (фиг.2).

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

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

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

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

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

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

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

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

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

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

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

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

Матрица 59.i.j (i=1, 2, , m; j=1, 2, , n) сумматоров предназначена для суммирования и последующей записи в соответствующую матрицу 63.i.j (i=1, 2, , m; j=1, 2, , n) регистров кодов значений интенсивности дуг, назначенных на соответствующие пары процессоров.

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

Первый 61 и второй 62 счетчик столбцов служат для хранения номера строки и столбца, в которых будет производится фиксация дуг графа G в столбцах МС.

Матрица 63.i.j (i=1, 2, , m; j=1, 2, , n) регистров предназначена для хранения суммарных кодов значений интенсивности дуг, назначенных на данную пару процессоров в строках и столбцах МС.

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

Первый 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) матриц элементов И с последующей подачей на разрешающие входы матрицы 63.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) матрица элементов И предназначена для объединения сигналов с последующей подачей на соответствующие входы 68.i.j (i=1, 2, , m; j=1, 2, , n) элементов ИЛИ и дальнейшим его поступлением на соответствующие разрешающие входы ое матрицы 63.i.j (i=1, 2, , m; j=1, 2, , n) регистров.

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

Первый 73 и второй 74 элементы задержки предназначены для задержки поступления кода с выхода первого 75, второго 76 счетчика инцидентной вершины соответственно.

Первый 75 и второй 76 счетчик инцидентной вершины служит для хранения кода вершины, инцидентной текущей выбранной дуге графа G, подлежащей фиксации.

Первый 77 и второй 78 элемент ИЛИ необходимы для пропуска кодов на вход второго 67 дешифратора вертикально зафиксированных дуг, а также на вход первого 64 дешифратора горизонтально зафиксированных дуг соответственно.

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

Первоначально в регистрах 29, 30 содержатся значения «11 1». В счетчиках 27, 9 содержится нулевой код. Триггеры 19 и 23 находятся в состоянии логического нуля. Триггеры 20.l модели 31.l, l=1, 2, , m, находятся либо в состоянии логической единицы, либо в состоянии логического нуля (что определяется соответственно наличием или отсутствием l-й дуги в графе). В регистрах 21.l содержатся либо значения весов соответствующих дуг, либо нулевые коды (если соответствующие дуги отсутствуют в исходном графе). Если размещается граф с невзвешенными дугами, то регистры 21.l содержат либо коды «00 01» либо нулевые коды. Запись информации о размещаемом графе осуществляется путем подачи комбинаций сигналов на входы 56.1- 56.n устройства и весов дуг на входы 54.l устройства. Появление единичных сигналов на входах 56.i-1 и 56.i означает наличие в графе дуги e_i-l,i (вес этой дуги подается на вход 54 соответствующей модели дуги). В счетчике 71 установлен код нуля, в счетчике 60 - код двойки («0 10»), в счетчике 61 содержится значение единицы, а в счетчике 62 - код нуля («0 00»). В счетчике 76 хранится код единицы («0 01»), а в счетчике 75 - код единицы («0 01»).

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

Задача размещения невзвешенных графов с топологической моделью в виде линейки решается в устройстве аналогично прототипу. В данном случае работает только так называемая «верхняя» часть схемы, в которую входит ЭМГ 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 дуги) и, попадая далее на разрешающий вход (ое) регистра 21.l, разрешает тем самым появление данных (веса 1-й дуги) на выходе этого регистра. Поскольку размещаемый граф не взвешен, в регистре 21.l содержится либо код «00 01» либо код «00 00» (отсутствие дуги). Будем считать данный код ненулевым. Код «00 01» с выхода регистра 21.l поступает на блок элементов ИЛИ 46 и далее через него - в АЛУ 7. В это же время блок 3 формирования перестановок определяет для выбираемых вершин позиции, а АЛУ 7 вырабатывает команду определения расстояния между позициями, в которые следует поместить выбранные вершины графа. Это расстояние определяется по формуле d_i,j=|i-j|. Одновременно в АЛУ 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, расположенные в порядке убывания значений своих весов. Как видно из фиг.4, при назначении дуг на процессоры матричной системы в первую очередь следует назначать дуги с наибольшими значениями весов. Следовательно, при выборе из блока 10 оперативной памяти, первой выбранной дугой будет дуга с наибольшим значением веса, а последней - с наименьшим.

Очередной тактовый импульс со входа 57 поступает на счетные входы счетчиков 62, 71 и вход элемента 35 И. В результате импульс проходит на вычитающий вход реверсивного счетчика 9 и по переднему фронту уменьшает значение на единицу. В результате полученный код подается на адресный вход А блока 10 оперативной памяти и на выходе появляется значение веса дуги с максимальным весом. Счетчик 62 закрыт, так как на его разрешающем входе ое не присутствует единичного сигнала. На разрешающем входе ое счетчика 71 присутствует единичный импульс с прямого выхода триггера 23, поэтому счетчик 71 открыт, и, следовательно, его содержимое увеличивается на единицу по переднему фронту до кода единицы (0 01»). Код единицы поступает на вход дешифратора 65 и на его первом выходе появляется единичный сигнал, который поступает на первые входы элементов 70.1.1, 70.1.2, , 70.1.n. К этому моменту с выхода счетчика 60 код числа два поступил на первый вход элемента 78 ИЛИ. Код числа единица с выхода счетчика 76 подался на вход элемента 74 задержки. Единичный импульс с выхода элемента 78 ИЛИ поступает на вход дешифратора 64 и на его втором выходе появляется единичный импульс, который подается на вторые входы элементов 70.1.2, 70.2.2, , 70.m.2 И. Таким образом, на двух входах элемента 70.1.2 И появляются единичные сигналы, в результате чего на его выходе появляется единичный импульс, который поступает на второй вход элемента 68.1.2 ИЛИ и далее на разрешающий вход регистра 63.1.2. В результате код, хранящийся в регистре 63.1.2, подается на первый вход сумматора 59.1.2. К этому моменту на втором его входе присутствует вес дуги с выхода блока 10 оперативной памяти. В результате суммирования полученное число подается на D-вход регистра 63.1.2 и сохраняется там.

К этому моменту элемент задержки 74 пропускает на второй вход элемента 78 ИЛИ код единицы с выхода счетчика 76. Это значение подается на вход дешифратора 64, на первом выходе которого появляется единичный импульс, который поступает на вторые входы элементов 70.1.1, 70.2.1, , 70.m.1 И. В это время на вторых входах элементов 70.1.1, 70.1.2, , 70.1.n И присутствует единичный сигнал. В результате на двух входах элемента 70.1.1 И появляются единичный импульс, в результате чего на его выходе появляется единичный сигнал, который подается на разрешающий вход ое регистра 63.1.1. В итоге с его выхода код, хранящийся в нем, подается на первый вход сумматора 59.1.1. На втором его входе присутствует вес дуги с выхода блока 10 оперативной памяти. Полученная сумма с выхода сумматора 59.1.1 поступает на D-вход регистра 63.1.1. В результате в него записывается значение интенсивности (объема данных, управляющей информации и т.п.), инцидентных фиксируемой дуге. Таким образом фиксируется значение интенсивности первой дуги графа G в МС (на фиг.4в - это дуга из модуля 1 в модуль 2 МС).

Очередной тактовый импульс поступает со входа 57 на входы элемента 35 И и счетные входы счетчиков 62 и 71. В результате значение, хранящееся в реверсивном счетчике 9, уменьшается на единицу и значение, хранящееся в нем, подается на адресный вход А блока 10 оперативной памяти. В результате на выходе блока 10 оперативной памяти появляется очередной код веса дуги графа G. Счетчик 62 закрыт из-за отсутствия сигнала на входе ое. Так как на входе ое счетчика 71 присутствует единичный сигнал с прямого выхода триггера 23, то сигнал, поступивший на счетный вход счетчика 71, увеличивает его содержимое на единицу до кода двойки («0 010»). Этот код поступает на вход дешифратора 65 и на его втором выходе появляется единичный сигнал, который подается на первые входы элементов 70.2.1, 70.2.2, , 70.2.n И. К этому времени в счетчике 60 все еще хранится значение кода числа два. Этот код проходит на первый вход элемента 78 ИЛИ и далее на вход дешифратора 64. В результате на его втором выходе появляется единичный сигнал, который подается на вторые входы элементов 70.1.2, 70.2.2, , 70.m.2 И. В итоге на обоих входах элемента 70.2.2 И появляются единичные сигналы. В результате чего на его выходе появляется единица, поступающая на разрешающий вход ое регистра 63.2.2. На его выходе появляется хранящийся в нем код, который поступает на первый вход сумматора 63.2.2, на втором входе которого присутствует код веса дуги графа G с выхода блока 10 оперативной памяти. В результате суммарное значение поступает для записи на D-вход регистра 63.2.2.

К этому моменту элемент 74 задержки уже пропустил тактовый импульс на второй вход элемента 78 ИЛИ, который поступает на вход дешифратора 64. Код единицы на входе дешифратора 64 возбуждает единичный сигнал на первом его выходе. Этот сигнал поступает на вторые входы элементов 70.1.1, 70.2.1, , 70.m.1 И. В результате на выходе элемента 70.2.1 И появляется единичный сигнал, который через элемент 68.2.1 ИЛИ подается на разрешающий вход ое регистра 63.2.1 и код, хранящийся в нем, подается на первый вход сумматора 59.2.1. На втором его входе присутствует значение веса дуги графа G с выхода блока 10 оперативной памяти. Сумма с выхода сумматора 59.2.1 поступает на D-вход регистра 63.2.1 для сохранения. Таким образом фиксируется вторая дуга графа G.

Так продолжается до тех пор, пока на выходе переполнения счетчика 71 не появится сигнала переполнения. Это означает, что фиксация в первой «колонке» строк МС закончена и необходимо продолжать фиксацию во второй «колонке» МС. Сигнал переполнения с выхода переполнения счетчика 71 подается на счетные входы счетчиков 60 и 76, устанавливая в счетчике 60 код числа три («0 011»), а в счетчике 76 - код двойки («0 010»). Счетчик 71 сбрасывается в код единицы.

Далее работа продолжается аналогично описанному выше принципу до тех пор, пока на выходе переполнения счетчика 60 не появится единичного импульса. Это означает, что фиксация дуг графа G в горизонтальной ориентации МС закончена. Например, на фиг.4в - это дуги, зафиксированные в модулях МС 1-2, 4-5, 7-8, 2-3, 5-6, 8-9. Следовательно, на следующем этапе работы схемы необходима фиксация дуг в вертикальной ориентации МС. Единичный импульс с выхода переполнения счетчик 60 подается на закрывающий вход с счетчика 76 и запрещает его дальнейшую работу. Импульс с выхода переполнения счетчика 60 также поступает на разрешающие входы счетчиков 61, 62 и 75, разрешая их работу.

Очередной тактовый импульс поступает на вход элемента 35 И, на счетные входы счетчиков 62 и 75. Вследствие подачи импульса на вход элемента 35 И новое значение веса дуги графа G с выхода блока 10 оперативной памяти поступает в блок 58 формирования нижней оценки. Этот же тактовый импульс, поступивший на счетные входы счетчиков 62 и 75, увеличивает содержащиеся в них коды на единицу и устанавливает в счетчике 62 код единицы, а в счетчике 75 - код двойки («0 010»). Код единицы с выхода счетчика 62 подается на первый вход элемента 77 ИЛИ и далее на вход дешифратора 67. Код двойки с выхода счетчика 75 поступает на вход элемента задержки 73. Так как на вход дешифратора 67 подался код единицы, на первом его выходе возбуждается единичный импульс, который поступает на вторые входы элементов 69.1.1, 69.1.2, , 69.1-n И. Код единицы с выхода счетчика 61 поступает на вход дешифратора 66, в результате чего на его первом выходе появляется единичный импульс, который поступает на первые входы элементов 69.1.1, 69.2.1, , 69.m.1 И. В результате этого на обоих входах элемента 69.1.1 И появляются единичные сигналы, а значит на его выходе инициируется единичный сигнал, который проходит на первый вход элемента 68.1.1 ИЛИ и далее на разрешающий ое вход регистра 63.1.1. В результате этого значение с его выхода поступает на первый вход сумматора 59.1.1, на втором выходе которого присутствует код веса дуги графа G с выхода блока 10 оперативной памяти. Суммарное значение с выхода сумматора 59.1.1 поступает на D-вход регистра 63.1.1 и записывается там.

К этому времени элемент задержки 73 пропустил код двойки с выхода счетчика 75, который проходит через элемент 77 ИЛИ и поступает на вход дешифратора 67. В результате на втором его выходе появляется единичный сигнал, который подается на вторые входы элементов 69.2.1, 69.2.2, , 69.2-n И. В итоге на двух входах элемента 69.2.1 И появляются единичные импульсы, а значит на его выходе возбуждается также единичный сигнал, который через элемент 68.2.1 ИЛИ проходит на разрешающий ое вход регистра 63.2.1, поэтому на его выходе появляется содержащийся в нем код. Это значение подается на первый вход сумматора 59.2.1, на втором входе которого присутствует код веса дуги графа G с выхода блока 10 оперативной памяти. Суммарное значение записывается в регистр 63.2.1, поступив на его D-вход с выхода сумматора 59.2.1. Таким образом происходит запись дуги графа G в вертикальной ориентации в МС. Например, на фиг.4в - это дуга, зафиксированная в модулях 1-4.

Очередной тактовый импульс поступает на счетные входы счетчиков 62 и 75 и по переднему фронту увеличивает их содержимое по переднему фронту на единицу до кода двойки в счетчике 62 и кода тройки в счетчике 75. Код тройки с выхода счетчика 75 подается на вход элемента задержки 73. Код числа два с выхода счетчика 62 поступает на вход дешифратора 67 через элемент ИЛИ 77. На втором выходе дешифратора 67 появляется единичный сигнал, который подается на вторые входы элементов 69.2.1, 69.2.2, , 69.2.n И. Код единицы с выхода счетчика 61 поступает на вход дешифратора 66, на первом выходе которого появляется единичный сигнал, который подается на первые входы элементов 69.1.1, 69.2.1, , 69.m.1 И. В результате из-за наличия на обоих входах элемента 69.2.1 И положительных импульсов, на его выходе появляется положительный сигнал, который поступает через элемент 68.2.1 ИЛИ на разрешающий вход ое регистра 63.2.1 и разрешает появление на выход хранящегося в нем кода. Этот код поступает на первый вход сумматора 59.2.1, на втором входе которого присутствует код веса дуги графа G. В результате суммирования значение с выхода сумматора 59.2.1 поступает на D-вход регистра 63.2.1, где происходит его сохранение.

К этому моменту элемент 73 задержки уже пропустил код тройки на второй элемента ИЛИ 77, откуда он подается на вход дешифратора 67. На третьем его выходе появляется положительный импульс, который поступает на вторые входы элементов 69.3.1, 69.3.2, , 69-3.n И. К этому моменту на первых входах элементов 69.1.1, 69.2.1, , 69.m.1 И присутствует положительный импульс. Следовательно, на выходе элемента 69.3.1 И появляется единичный импульс, который через элемент 69.3.1 ИЛИ подается на разрешающий вход ое регистра 63.3.1 и разрешает появление хранящегося в нем кода на выходе. Этот код поступает на первый вход сумматора 59.3.1, на втором выходе которого присутствует значение веса дуги графа G. Результат суммирования подается на D-вход регистра 63.3.1, где происходит его сохранение. Таким образом происходит фиксация очередной дуги графа G в МС при двунаправленной передаче информации.

Таким образом, работа схемы происходит до тех пор, пока на выходе переполнения счетчика 62 не появится сигнала переполнения. Эта ситуация произойдет в случае, если произойдет попытка установить код числа m в счетчике 62, а в счетчике 75 - код числа m+1. В этом случае сигнал переполнения с выхода счетчика 62 поступит на счетный вход счетчика 61 и вход сброса с счетчика 75, сбрасывая его в исходное состояние единицы («0 01»). Счетчик 62 устанавливается в исходное состояние ноль. Счетчик 61 в результате поступления на его счетный вход единичного сигнала по переднему фронту увеличивает свое значение на единицу до кода двойки («0.010»).

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

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