Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании ВС.
Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. СССР 1291957, кл. G 06 F 7/00, опубл. 23.02.87, БИ №7).
Недостатком указанного элемента является узкая область применения, обусловленная отсутствием средств для оценки качества (степени оптимальности) размещения по критериям суммарной длины ребер и максимальной длины ребра.
Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа; вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. СССР 1410949, кл. G 06 F 7/00, 15/20, опубл. 15.10.88, БИ №38).
Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для оценки качества размещения по критерию максимальной загрузки канала между соседними (смежными) модулями.
Технической задачей изобретения является расширение области применения устройства за счет введения средств для оценки текущего варианта размещения по критерию максимальной загрузки канала между смежными модулями.
Техническая задача решается тем, что в устройство для оценки степени удаленности размещения от оптимального, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1,2,...,n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1,2,...,m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок оценки степени загрузки каналов, содержащий первый и второй генераторы импульсов, первый и второй дешифраторы выбора строки, дешифратор выбора единичного значения, дешифратор выбора элемента, мультиплексор выбора элемента, дешифратор загрузки канала, первый и второй элементы сравнения, m счетчиков загрузки канала, первую и вторую группы m элементов ИЛИ, первую группу m триггеров, первую и вторую группу m элементов запрета, счетчик текущего столбца, группу m элементов И, третью группу m элементов ИЛИ, вторую группу m триггеров, первый и второй счетчики строк, первый и второй счетчики столбцов, первый и второй элементы ИЛИ, элемент задержки, счетчик следующего столбца, причем первый выход первого генератора импульсов соединен с разрешающим входом дешифратора выбора элемента, а второй выход первого генератора импульсов подключен к счетному входу второго счетчика столбцов, информационный выход которого подключен к управляющим входам дешифратора выбора элемента и мультиплексора выбора элемента, выход переполнения второго счетчика столбцов подсоединен к счетному входу второго счетчика строк и к соответствующим входам сброса первой группы с 1-го по m-й триггеров, выход второго счетчика строк соединен с входом второго дешифратора выбора строки и с установочным входом второго счетчика столбцов, выходы с 1-го по m-й второго дешифратора выбора строки соединены с соответствующими управляющими входами второй группы с 1-го по m-й элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с 1-го по m-й столбцов матрицы 1 элементов однородной среды, выходы второй группы с 1-го по m-й элементов запрета соединены с соответствующими входами второй группы с 1-го по m-й элементов ИЛИ, выходы которых подключены к соответствующим S-входам первой группы с 1-го по m-й триггеров, выходы которых подключены к соответствующим входам мультиплексора, выход которого соединен с соответствующим входом дешифратора выбора элемента, выходы которого подключены к соответствующим вторым входам первой группы с 1-го по m-й элементов ИЛИ, выходы которых соединены с соответствующими входами группы счетчиков с 1-го по m-й загрузки канала, выходы которых подключены к соответствующим выходам с 1-й по m-й загрузки каналов устройства, вход запуска устройства соединен с входом первого генератора импульсов, выход переполнения второго счетчика строк подключен к входу второго генератора импульсов, выход которого соединен со вторым входом второго элемента ИЛИ, первый вход которого подключен к входу сброса счетчика текущего столбца и к первому выходу второго элемента сравнения, второй выход которого соединен с управляющим входом дешифратора загрузки канала и к входу элемента задержки, выход которого подключен к входу счетчика текущего столбца, выход которого подсоединен к первому входу второго элемента сравнения и к входу дешифратора загрузки канала, установочный вход счетчика текущего столбца подключен к выходу счетчика следующего столбца, счетный вход которого соединен с первым выходом первого элемента сравнения, с входом сброса первого счетчика столбцов, со счетным входом первого счетчика строк и с соответствующими входами сброса второй группы с 1-го по m-й триггеров, второй выход первого элемента сравнения подключен к разрешающему входу дешифратора выбора единичного значения, вход которого подключен к выходу первого счетчика столбцов, ко второму входу первого элемента сравнения и ко второму входу второго элемента сравнения, первый вход первого элемента сравнения соединен с выходом первого счетчика строк и с входом первого дешифратора выбора строки, выходы которого подключены к соответствующим управляющим входам первой группы с 1-го по m-й элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с 1-го по n-й столбцов матрицы 1 элементов однородной среды, выходы первой группы с 1-го по m-й элементов запрета соединены с соответствующими входами второй группы с 1-го по m-й элементов ИЛИ, выходы которых подключены к соответствующим S-входам второй группы с 1-го по m-й триггеров, выходы которых соединены с соответствующими вторыми входами группы с 1-го по m-й элементов И, первые входы которых подключены к соответствующим выходам дешифратора выбора единичного значения, выходы группы с 1-го по m-й элементов И подключены к соответствующим входам первого элемента ИЛИ, выход которого подсоединен к разрешающему входу дешифратора загрузки канала, выходы которого подключены к соответствующим первым входам первой группы с 1-го по m-й элементов ИЛИ, выход переполнения первого счетчика строк подключен к выходу переполнения устройства, выход второго элемента ИЛИ подсоединен к счетному входу первого счетчика столбцов.
Сущность изобретения поясняется чертежами, где на фиг.1 изображена функциональная схема устройства для оценки степени удаленности размещения от оптимального; фиг.2 поясняет сущность оценки размещения по критерию максимальной загрузки канала между смежными модулями.
Общие особенности изобретения состоят в следующем.
Предлагаемое устройство может использоваться в области проектирования ВС, например, при размещении процессов. Устройство позволяет оценивать степень удаленности размещения от оптимального.
Исходный (размещаемый) процесс представляется в виде направленного графа или гиперграфа, заданного соответствующей матрицей смежности. Строки и столбцы матрицы отмечаются номерами вершин графа. На пересечении i-й строки и j-го столбца ставится единица, если i-ю и j-ю вершину соединяет дуга, направленная из вершины i в вершину j, и ноль - в противном случае.
Матрица смежности отображается однородной средой, содержащей m×n элементов (где m и n - число процессов). Функционирование однородной среды аналогично прототипу. При поступлении сигнала от внешнего устройства управления (ВУУ) происходит моделирование перестановки пары строк матрицы смежности (что соответствует перестановке двух вершин графа, то есть фактически двух процессов, и получению нового размещения). После очередной перестановки предлагаемое устройство вычисляет значения критериев оценки и выдает указанные значения ВУУ. Последнее анализирует принятые значения и либо фиксирует полученное размещение как более оптимальное (если значения критериев улучшают ранее найденные значения), либо игнорирует его.
В отличие от прототипа, где оценка выполняется по двум критериям - суммарной длине ребер и максимальной длине ребра, предлагаемое устройство дополнительно реализует оценку по критерию максимальной загрузки канала между смежными модулями. В области ВС под каналом понимается интенсивность обмена информацией между двумя соседними модулями (процессами) системы. В этом случае минимизация степени загрузки канала важна с точки зрения уменьшения общего времени выполнения задачи.
Сущность предлагаемого критерия поясняется фиг.2. Здесь на фиг.2а представлен вариант гипотетического исходного размещения, а фиг.2б задает матрицу смежности для исходного размещаемого графа. Фиг.2в описывает вариант размещения после перестановки модулей 2 и 3, а фиг.2г отображает соответствующую ему матрицу смежности. На фиг.2а и 2в кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают степени загрузки канала между смежными модулями. Из фиг.2а видно, что канал между модулями 2-3 и 3-4 имеет наибольшую загрузку. Качество размещения улучшается при перестановке местами модулей 2 и 3 (фиг.2в). В этом случае качество размещения улучшается и для остальных пар модулей. Максимальная степень загрузки канала при этом уменьшается. Тем самым при применении предлагаемого устройства в ВС - уменьшается общее время выполнения задачи.
Устройство для оценки степени удаленности размещения от оптимального (фиг.1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1 - 2.n подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j=1,2,...,n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1,2,...,m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 42 оценки степени загрузки каналов, содержащий первый 14 и второй 20 генераторы импульсов, первый 15 и второй 18 дешифраторы выбора строки, дешифратор 16 выбора единичного значения, дешифратор 17 выбора элемента, мультиплексор 19 выбора элемента, дешифратор 21 загрузки канала, первый 22 и второй 23 элементы сравнения, группу 24.1-24.m счетчиков загрузки канала, первую 25.1-25.m и вторую 26.1-26.m группы элементов ИЛИ, первую группу 27.1-27.m триггеров, первую 28.1-28.m и вторую 29.1-29.m группы элементов запрета, счетчик 30 текущего столбца, группу 31.1-31.m элементов И, третью группу 32.1-32.m элементов ИЛИ, вторую группу 33.1-33.m триггеров, первый 34 и второй 35 счетчики строк, первый 36 и второй 37 счетчики столбцов, первый 38 и второй 39 элементы ИЛИ, элемент 40 задержки, счетчик 41 следующего столбца, причем первый выход первого генератора импульсов 14 соединен с разрешающим входом дешифратора 17 выбора элемента, а второй выход первого генератора 14 импульсов подключен к счетному входу второго счетчика 37 столбцов, информационный выход которого подключен к управляющим входам дешифратора 17 выбора элемента и мультиплексора 19 выбора элемента, выход переполнения второго счетчика 37 столбцов подсоединен к счетному входу второго счетчика 35 строк и к соответствующим входам сброса первой группы 27.1-27.m триггеров, выход второго счетчика 35 строк которого соединен с входом второго дешифратора 18 выбора строки и с установочным входом второго счетчика 37 столбцов, выходы с 1-го по m-й второго дешифратора 18 выбора строки соединены с соответствующими управляющими входами второй группы 29.1-29.m элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы второй группы 29.1-29.m элементов запрета соединены с соответствующими входами второй группы 26.1-26.m элементов ИЛИ, выходы которых подключены к соответствующим S-входам первой группы 27.1-27.m триггеров, выходы которых подключены к соответствующим входам мультиплексора 19, выход которого соединен с соответствующим входом дешифратора 17 выбора элемента, выходы которого подключены к соответствующим вторым входам первой группы 25.1-25.m элементов ИЛИ, выходы которых соединены с соответствующими входами группы счетчиков 24.1-24.m загрузки канала, выходы которых подключены к соответствующим выходам 45.1-45.m загрузки каналов устройства, вход 44 запуска устройства соединен с входом первого генератора 14 импульсов, выход переполнения второго счетчика 35 строк подключен к входу второго генератора 20 импульсов, выход которого соединен со вторым входом второго элемента 39 ИЛИ, первый вход которого подключен к входу сброса счетчика 30 текущего столбца и к первому выходу второго элемента 23 сравнения, второй выход которого соединен с управляющим входом дешифратора 21 загрузки канала и к входу элемента 40 задержки, выход которого подключен к входу счетчика 30 текущего столбца, выход которого подсоединен к первому входу второго элемента 23 сравнения и к входу дешифратора 21 загрузки канала, установочный вход счетчика 30 текущего столбца подключен к выходу счетчика 41 следующего столбца, счетный вход которого соединен с первым выходом первого элемента 22 сравнения, с входом сброса первого счетчика 36 столбцов, со счетным входом первого счетчика 34 строк и с соответствующими входами сброса второй группы 33.1-33.m триггеров, второй выход первого элемента 22 сравнения подключен к разрешающему входу дешифратора 16 выбора единичного значения, вход которого подключен к выходу первого счетчика 36 столбцов, ко второму входу первого элемента 22 сравнения и ко второму входу второго элемента 23 сравнения, первый вход первого элемента 22 сравнения соединен с выходом первого счетчика 34 строк и с входом первого дешифратора 15 выбора строки, выходы которого подключены к соответствующим управляющим входам первой группы 28.1-28.nm элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы первой группы 28.1-28.m элементов запрета соединены с соответствующими входами второй группы 32.1-32.m элементов ИЛИ, выходы которых подключены к соответствующим S-входам второй группы 33.1-33.m триггеров, выходы которых соединены с соответствующими вторыми входами группы 31.1-31.m элементов И, первые входы которых подключены к соответствующим выходам дешифратора 16 выбора единичного значения, выходы группы 31.1-31.m элементов И подключены к соответствующим входам первого элемента 38 ИЛИ, выход которого подсоединен к разрешающему входу дешифратора 21 загрузки канала, выходы которого подключены к соответствующим первым входам первой группы 25.1-25.m элементов ИЛИ, выход переполнения первого счетчика 34 строк подключен к выходу 43 переполнения устройства, выход второго элемента 39 ИЛИ подсоединен к счетному входу первого счетчика 36 столбцов.
Назначение элементов и блоков устройства для оценки степени удаленности размещения от оптимального (фиг.1) состоит в следующем.
Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач размещения.
Блоки 2.1 - 2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.
Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.
Сумматор 4 предназначен для суммирования п двоичных кодов.
Блок 5 памяти предназначен для хранения наилучшего на данный момент варианта размещения.
Вход 6 записи устройства служит для записи матрицы, представляющей размещаемый граф.
Вход 7 управления перестановкой столбцов устройства предназначен для приема сигнала от ВУУ о перестановке столбцов.
Вход 8 управления перестановкой строк устройства предназначен для приема сигнала от ВУУ о перестановке строк.
Вход 9 управления записью устройства необходим для приема сигнала "Запись" от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.
Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.
Выход 11 суммарной длины ребер устройства необходим для выдачи значения суммарной длины ребер на ВУУ.
Информационный выход 12 устройства необходим для выдачи варианта размещения, находящегося в блоке 5 памяти, на ВУУ.
Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.
Первый 14 и второй 20 генераторы импульсов предназначены для формирования импульсных последовательностей, синхронизирующих работу блока 42 оценки степени загрузки каналов.
Первый 15 и второй 18 дешифраторы выбора строки служат для выбора очередной строки матрицы 1 (матрицы смежности размещаемого графа).
Дешифратор 16 выбора единичного значения необходим для управления выбором из матрицы 1 модулей, лежащих в нижнем треугольнике и имеющих единичное значение.
Дешифратор 17 выбора элемента служит для выдачи информации о загрузке канала между модулями, которым соответствует верхний треугольник матрицы смежности на соответствующий элемент 25.i группы 25.1-25.m элементов ИЛИ с последующей подачей на соответствующий счетчик 24.i группы 24.1-24.m счетчиков загрузки канала.
Мультиплексор 19 выбора элемента предназначен для подачи с выходов триггеров 27.1-27.m информации о загрузке канала между модулями, которым соответствует верхний треугольник матрицы смежности, на вход дешифратора 17 выбора элемента.
Дешифратор 21 загрузки канала служит для выдачи информации о загрузке канала между модулями, которым соответствует нижний треугольник матрицы смежности на соответствующий элемент 25.i группы 25.1-25.m элементов ИЛИ с последующей подачей на соответствующий счетчик 24.i группы 24.1-24.m счетчиков загрузки канала.
Первый элемент 22 сравнения необходим для сравнения номера текущего, выбранного столбца, хранящегося в 1-м счетчике 36 столбцов с номером текущей выбранной строки, содержащегося в первом счетчике 34 строк. Элемент сравнения имеет два выхода: первый (верхний) выход инициализируется тогда, когда результат сравнения отрицательный, в противном случае - второй (нижний) выход, что соответствует положительному результату сравнения.
Второй элемент 23 сравнения служит для проверки равенства единице разности значений счетчика 30 текущего столбца и первого счетчика 36 столбца. Первый (верхний) выход счетчика активен тогда, когда результат сравнения отрицателен, а второй (нижний) выход - когда результат сравнения положителен.
Группа 24.1-24.m счетчиков загрузки канала служат для накапливания информации о загрузке канала между соответствующими смежными модулями.
Первая группа 25.1-25.m элементов ИЛИ предназначена для объединения сигналов с выходов дешифратора 21 загрузки канала и дешифратора 17 выбора элемента соответственно.
Вторая группа 26.1-26.m элементов ИЛИ необходима для объединения сигналов с выходов группы элементов 29.1-29.m запрета соответственно.
Первая группа 27.1-27.m триггеров необходима для хранения информации о загрузке канала между соответствующими модулями, которым сопоставляется верхний треугольник матрицы смежности.
Первая группа 28.1-28.m элементов запрета предназначена для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 на соответствующие элементы ИЛИ 32.1-32.m.
Вторая группа 29.1-29.m элементов запрета предназначены для блокировки поступления значений от элементов с первой по m-ю строк матрицы 1 на соответствующие элементы ИЛИ 26.1-26.m.
Счетчик 30 текущего столбца с коэффициентом пересчета N служит для подсчета столбцов, начиная с номера j=i+1 с циклическим переносом до номера j, где i - это номер строки, a j - номер столбца, причем нижнего треугольника матрицы смежности. Модули i и j соединяет направленная дуга, например, модули 3 и 2 на фиг.2. Из фиг, 2 очевидна необходимость применения такого счетчика.
Группа 31.1-31.m элементов И служит для блокировки передачи импульсов с соответствующих выходов группы триггеров 33.1-33.m.
Третья группа 32.1-32.m элементов ИЛИ необходима для объединения сигналов с выходов первой группы 28.1-28.m элементов запрета соответственно.
Вторая группа 33.1-33.m триггеров необходима для хранения информации о загрузке канала между соответствующими модулями, которым сопоставляется нижний треугольник матрицы смежности.
В первом 34 и втором 35 счетчиках строк содержится информация о текущей обрабатываемой строке матрицы 1.
Первый 36 счетчик столбцов необходим для подсчета номеров обрабатываемых столбцов в текущей строке нижнего треугольника матрицы 1.
Второй 37 счетчик столбцов предназначен для подсчета номеров обрабатываемых столбцов в текущей строке верхнего треугольника матрицы 1.
Первый элемент 38 ИЛИ служит для объединения сигналов с выходов группы 31.1-31.m элементов И.
Второй элемент 39 ИЛИ предназначен для объединения сигналов с первого выхода второго элемента сравнения 23 и со второго генератора 20 импульсов.
Элемент 40 задержки необходим для задержки импульса со второго выхода второго элемента 23 сравнения на время, достаточное для прохождения значения с выхода счетчика 30 текущего столбца на дешифратор 21 загрузки канала и появления на одном из его выходов, единичного сигнала.
Счетчик 41 следующего столбца предназначен для подачи в счетчик 30 номера следующего после текущего значения столбца. Из фиг.2 видно, что, например, для дуги из модуля 3 в модуль 2 загрузка канала для модуля 3 значения не имеет (модуль 3 - это источник дуги), а имеет для модуля 4, то есть фактически номер строки плюс единица.
Блок 42 оценки степени загрузки каналов необходим для оценки степени удаленности размещения от оптимального между смежными модулями.
Выход 43 переполнения устройства служит для подачи информации о переполнении первого счетчика 34 номера строки, что одновременно является сигналом о завершении работы блока 42.
Вход 44 запуска устройства необходим для подачи сигнала запуска генератора 14 импульсов от ВУУ.
Выходы 45.1-45.m загрузки каналов устройства предназначены для выдачи ВУУ соответствующих кодов загрузки канала между смежными модулями для данного варианта размещения.
Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.
Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. В счетчиках 24.1-24.m содержится нулевой код. 1-я группа 27.1-27.m и 2-я группа 33.1-33.m триггеров находятся в состоянии логического нуля. В первом счетчике 34 содержится код "00...010", во втором счетчике 35 содержится код "00...01", а в счетчиках 30 и 41 - код "0...011". На втором выходе первого 15 и первом выходе второго 18 дешифраторов выбора строки присутствуют единичные сигналы, которые подаются на соответствующие управляющие входы 2-го блока 28.2 и 1-го блока 29.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов второй и первой строк матрицы 1 соответственно. В первом 36 и втором 37 счетчиках столбцов содержатся нули.
Предлагаемое устройство предназначено для оценки размещения по критериям суммарной длины ребер, максимальной длины ребра и критерию максимальной загрузки канала между смежными модулями, а также для решения задачи трассировки. Задача трассировки решается в матрице 1 так же, как и в прототипе, и поэтому здесь не рассматривается.
Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1,2,...,n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал "Запись") на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.
Оценка размещения по критерию максимальной загрузки канала между смежными модулями происходит следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 42 оценки степени загрузки каналов.
Появление единичного потенциала на входе 44 запуска устройства запускает генератор 14 импульсов (в данном случае работает только "нижняя" части схемы, включающая генератор 14 импульсов, дешифраторы 17 и 18, мультиплексор 19, счетчики 24.1-24.m, первую 25.1-25.m и вторую 26.1-26.m группы элементов ИЛИ, группу триггеров 27.1-27.m, группу 29.1-29.m блоков элементов запрета, счетчики 35 и 37). В результате на втором выходе генератора 14 появляется импульс, а на первом выходе генератора он появится с задержкой в половину такта. Импульс со второго выхода генератора 14 импульсов поступает на счетный вход счетчика 37 и по переднему фронту увеличивает его содержимое на единицу. В результате там будет содержаться код "00...01".
Сигналы с индикаторных выходов элементов первой строки матрицы 1 поступают на элементы ИЛИ 26.1-26.m, т.к. блок 29.1 элементов запрета открыт. Если на выходах элементов ИЛИ 26.1-26.m присутствуют единицы, то они поступают на соответствующие S входы триггеров 27.1-27.m и устанавливают их в единичное состояние. К этому времени на выходе счетчика 37 уже присутствует код "00...01", который поступает на управляющий вход мультиплексора 19 и дешифратора 17, разрешая прохождение сигнала с триггера 27.1. Если он находится в единичном состоянии, соответствующий сигнал поступает на вход дешифратора 17. При появлении на его разрешающем входе сигнала с первого выхода генератора 14 импульсов сигнал с выхода мультиплексора 19 проходит через элемент ИЛИ 25.1 на вход счетчика 24.1 загрузки каналов и по заднему фронту увеличивает его на единицу. В результате в счетчике будет содержаться код "00...01".
Новый импульс на втором выходе генератора 14 импульсов поступает на счетный вход счетчика 37 и по переднему фронту устанавливает в нем код двойки ("00...010"). Код "00...010" поступает на управляющие входы мультиплексора 19 и дешифратора 17. Появление импульса с первого выхода генератора 14 импульсов на разрешающих входах мультиплексора 19 и дешифратора 17 пропускает сигнал с выхода триггера 27.2 на элемент ИЛИ 25.2, а затем на вход счетчика 24.2. В результате в нем по заднему фронту будет установлен код "00...01".
Так происходит до тех пор, пока на выходе переполнения счетчика 37 не появится сигнал переполнения. Этот сигнал поступает на счетный вход счетчика 35 строки и по переднему фронту увеличивает в нем код до "00...010" и одновременно обнуляет все триггеры 27.1-27.m. Код "00...010" с выхода счетчика 35 поступает на вход дешифратора 18, и на втором его выходе появляется единичный сигнал. Этот сигнал обеспечивает прохождение сигналов с индикаторных выходов второй строки матрицы 1 через блок 29.2 2-й группы 29.1-29.m элементов запрета на элементы ИЛИ 26.1-26.m. Одновременно код с выхода счетчика 35 поступает на установочный вход счетчика 37, устанавливая его начальное состояние в "00...010".
Следующий тактовый импульс со второго выхода генератора 14 импульсов по переднему фронту увеличивает содержимое счетчика 37 до значения "00...011". Код числа три с выхода счетчика 37 поступает на управляющие входы мультиплексора 19 и дешифратора 17. Сигналы с индикаторных выходов второй строки матрицы 1 проходят через соответствующие элементы запрета 29.3, через элемент ИЛИ 26.3 второй группы 26.1-26.m элементов ИЛИ и устанавливают триггеры 27.1-27.m, на входы которых поступили единичные импульсы, в единичное состояние.
При поступлении импульса с первого выхода генератора 14 импульсов на разрешающий вход дешифратора 17 сигнал с выхода триггера 27.3 проходит через элемент ИЛИ 25.3, после чего поступает на вход счетчика 24.3 загрузки каналов и увеличивает его содержимое по заднему фронту на единицу.
Так продолжается до тех пор, пока на выходе переполнения 2-го счетчика 35 строк не появится единичный импульс переполнения, свидетельствующий о том, что закончилась работа "нижней" части схемы и начинается работа "верхней" части, которая включает в себя генератор 20 импульсов, дешифраторы 15, 16 и 21, группу элементов 28.1-28.m запрета, группу элементов ИЛИ 32.1-32.m, группу триггеров 33.1-33.m, группу элементов И 31.1-31.m, счетчики 30, 34 и 36, элементы сравнения 22 и 23, элементы ИЛИ 38, 39, элемент задержки 40, счетчик 41. В "нижнюю" часть схемы также входит группа элементов ИЛИ 25.1-25.m и группа счетчиков 24.1-24.m, которые участвуют в работе как "нижней"; так и "верхней" частей схемы.
Импульс с выхода переполнения счетчика 35 запускает генератор импульсов 20, на выходе которого появляется импульс, который поступает через элемент ИЛИ 39 на счетный вход первого счетчика 36 столбцов и по переднему фронту увеличивает в нем состояние до кода "0...01". В это время в счетчике 34 содержится код двойки ("0...010"), который поступает на вход дешифратора 15, что вызывает появление на его втором выходе единичного импульса. Это обеспечивает прохождение сигналов с индикаторных выходов второй строки матрицы 1 через элементы запрета 28.2 на соответствующие входы группы элементов ИЛИ 32.1-32.m, с выхода которых они поступают на соответствующие S-входы группы триггеров 33.1-33.m и устанавливает их в единичное состояние.
Код "0...01" с выхода счетчика 36 поступает на вход дешифратора 16, на второй вход элемента сравнения 22 и на второй вход элемента сравнения 23. Код числа два ("0...010") с выхода счетчика 34 уже поступил на первый вход элемента сравнения 22. На втором выходе элемента 22 сравнения появится единичный импульс, так как результат сравнения будет положительным. Положительный импульс поступит на разрешающий вход дешифратора 16, обеспечивая тем самым появление импульса на одном из выходов. Дешифратор 16 выбора единичного значения по коду "0...01" инициирует единичный импульс на своем первом выходе, который попадает на первый вход элемента И 31.1 группы элементов И 31.1-31.m. В случае наличия на выходе триггера 33.1 единичного сигнала он поступает на второй вход элемента И 31.1. В случае наличия двух единиц на входе элемента И 31.1 на его выходе появится единичный сигнал, который поступит на элемент ИЛИ 38. В этом случае на его выходе появится единичное значение, которое попадает на разрешающий вход дешифратора 21 загрузки канала, разрешая прохождение импульсов на его выходы.
Так как в счетчике 30 содержится код тройки ("0...011"), который с выхода уже поступил на первый вход элемента 23 сравнения. На втором входе уже присутствует код единицы ("0...01") с выхода счетчика 36. Результат сравнения будет положительным, потому что разность значений не равна единице, следовательно, на втором выходе элемента 23 сравнения будет положительный импульс, который поступает на вход элемента 40 задержки и на управляющий вход дешифратора 21. Код тройки с выхода счетчика 30 поступит на вход дешифратора 21 и возбудит на его третьем выходе положительный импульс, который пройдет через элемент 25.3 ИЛИ, поступит на вход счетчика 24.3 загрузки канала и по заднему фронту увеличит его содержимое на единицу.
К этому времени элемент 40 задержки уже пропустит положительный импульс на вход счетчика 30 и по переднему фронту увеличит его значения до кода четверки ("0...0100"). Через промежуток времени, достаточный для установки в счетчике 30 нового значения (кода "0...0100"), этот код появляется на его выходе и поступает на первый вход элемента 23 сравнения и на вход дешифратора 21. На втором входе элемента 23 сравнения присутствует код единицы. В результате сравнения результат будет положительным, поэтому на втором выходе появится импульс, который поступит на вход элемента 40 задержки, и на управляющий вход дешифратора 21, разрешая появление на его четвертом выходе импульса. Этот импульс проходит через элемент 25.4 ИЛИ, поступает на вход счетчика 24.4 и по заднему фронту увеличивает его содержимое на единицу.
Так происходит до тех пор, пока результат сравнения во втором элементе 23 сравнения не будет отрицательным. Такая ситуация возникнет в том случае, когда в счетчике 30 текущего столбца будет установлен код двойки ("0...010"). В результате на первом выходе элемента 23 сравнения появится единичный импульс, который поступит на вход сброса счетчика 30 и на первый вход второго элемента ИЛИ 39. В результате в счетчике 30 установится начальное значение счетчика, то есть код тройки ("0...011").
Единичный импульс с первого входа элемента ИЛИ 39 пройдет на счетный вход счетчика 36 и по переднему фронту увеличит его значение до кода двойки ("0...010"), который поступит на второй вход элемента 22 сравнения. На первом его входе присутствует код числа два. В результате сравнения на первом выходе элемента 22 сравнения появится единичный импульс, так как результат сравнения будет отрицательным. Этот импульс поступит на счетный вход счетчика 34, по переднему фронту увеличивая его значение до кода тройки ("0...011"). Тот же импульс поступает на счетный вход счетчика 41, увеличивая его значения до кода четверки ("0...0100"). Этот код поступит на установочный вход счетчика 30 и установит его начальное значение равным четырем ("0...0100"). Положительный импульс со второго выхода элемента 22 сравнения так же поступает на вход сброса счетчика 36 и сбрасывает его значение в ноль.
Новый тактовый импульс поступает на второй вход элемента ИЛИ 39, а далее на счетный вход счетчика 36, увеличивая его значение по переднему фронту на единицу. Таким образом, в нем будет установлен код единицы ("0...01"). Этот код поступает на второй вход элемента 22 сравнения, на первом входе которого уже присутствует код тройки с выхода счетчика 34. Одновременно тот же код поступит на вход дешифратора 15, инициализируя тем самым единичное значение на его третьем выходе. В результате значения третьей строки матрицы 1 будут записаны во второй группе триггеров 33.1-33.m. Результат сравнения в элементе 22 сравнения будет положительным, поэтому на втором его выходе появится положительный единичный импульс. Этот импульс разрешит появление на первом выходе дешифратора 16 единичного импульса, так как на его входе уже поступил код единицы с выхода счетчика 36. Этот импульс поступает на первый вход элемента И 31.1. Если в триггере 33.1 присутствует единица, то на выходе элемента И 31.1 появится единичный импульс, который пройдет через элемент ИЛИ 38 на разрешающий вход дешифратора 21, разрешая тем самым прохождение сигналов на его выходы.
В это время на первом входе элемента 23 сравнения присутствует код четверки ("0...0100"), а на его втором входе - код единицы. Результат сравнения будет положительным, и на втором выходе элемента 23 сравнения появится единичный импульс, который поступит на вход элемента задержки 40 и управляющий вход дешифратора 21, разрешая возбуждение на его четвертом выходе единичного сигнала. Этот сигнал пройдет через элемент ИЛИ 25.4 на вход счетчика 24.4 и увеличит его содержимое по заднему фронту на единицу.
К этому времени с выхода элемента задержки 40 импульс поступит на вход счетчика 30 и по переднему фронту увеличит его содержимое на единицу. В результате в нем будет содержаться код единицы, так как счетчик 30 имеет коэффициент пересчета N.
Так происходит до тех пор, пока на выходе переполнения первого счетчика 34 строк не появится единичный импульс, свидетельствующий об окончании процесса оценки размещения по критерию максимальной загрузки канала между смежными модулями. В счетчиках 24.1-24.m к этому моменту появятся соответствующие значения загрузки для каждого модуля.
Таким образом, предлагаемое устройство для оценки степени удаленности размещения от оптимального обеспечивает возможность оценки текущего варианта размещения как по критериям суммарной длины ребер и максимальной длины ребра, так и по предложенному критерию максимальной загрузки канала между смежными модулями. Тем самым обеспечивается расширение функциональных возможностей устройства и, следовательно, области его целесообразного применения.
Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании ВС. Техническим результатом изобретения является расширение области применения устройства за счет введения средств для оценки текущего варианта размещения по критерию максимальной загрузки канала между смежными модулями. Указанный результат достигается за счет того, что устройство содержит матрицу из m строк и n столбцов элементов однородной среды, блок нахождения максимума, сумматор, блок памяти, m блоков подсчета единиц, блок оценки степени загрузки каналов, содержащий два генератора импульсов, два дешифратора выбора строки, дешифратор выбора единичного значения, дешифратор выбора элемента, мультиплексор выбора элемента, дешифратор загрузки канала, два элемента сравнения, m счетчиков загрузки канала, две группы m элементов ИЛИ, две группы m элементов запрета, счетчик текущего столбца, группу m элементов И, третью группу m элементов ИЛИ, две группы m триггеров, два счетчика строк, два счетчика столбцов, два элемента ИЛИ, элемент задержки, счетчик следующего столбца. 2 ил.
Устройство для оценки степени удаленности размещения от оптимального, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1,2,...,n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен c j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1,2,...,m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, отличающееся тем, что в него дополнительно введен блок оценки степени загрузки каналов, содержащий первый и второй генераторы импульсов, первый и второй дешифраторы выбора строки, дешифратор выбора единичного значения, дешифратор выбора элемента, мультиплексор выбора элемента, дешифратор загрузки канала, первый и второй элементы сравнения, m счетчиков загрузки канала, первую и вторую группы m элементов ИЛИ, первую группу m триггеров, первую и вторую группу m элементов запрета, счетчик текущего столбца, группу m элементов И, третью группу m элементов ИЛИ, вторую группу m триггеров, первый и второй счетчики строк, первый и второй счетчики столбцов, первый и второй элементы ИЛИ, элемент задержки, счетчик следующего столбца, причем первый выход первого генератора импульсов соединен с разрешающим входом дешифратора выбора элемента, а второй выход первого генератора импульсов подключен к счетному входу второго счетчика столбцов, информационный выход которого подключен к управляющим входам дешифратора выбора элемента и мультиплексора выбора элемента, выход переполнения второго счетчика столбцов подсоединен к счетному входу второго счетчика строк и к соответствующим входам сброса первой группы с 1-го по m-й триггеров, выход второго счетчика строк соединен с входом второго дешифратора выбора строки и с установочным входом второго счетчика столбцов, выходы с 1-го по m-й второго дешифратора выбора строки соединены с соответствующими управляющими входами второй группы с 1-го по m-й элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с 1-го по n-й столбцов матрицы 1 элементов однородной среды, выходы второй группы с 1-го по m-й элементов запрета соединены с соответствующими входами второй группы с 1-го по m-й элементов ИЛИ, выходы которых подключены к соответствующим S-входам первой группы с 1-го по m-й триггеров, выходы которых подключены к соответствующим входам мультиплексора, выход которого соединен с соответствующим входом дешифратора выбора элемента, выходы которого подключены к соответствующим вторым входам первой группы с 1-го по m-й элементов ИЛИ, выходы которых соединены с соответствующими входами группы счетчиков с 1-го по m-й загрузки канала, выходы которых подключены к соответствующим выходам с 1-й по m-й загрузки каналов устройства, вход запуска устройства соединен с входом первого генератора импульсов, выход переполнения второго счетчика строк подключен к входу второго генератора импульсов, выход которого соединен со вторым входом второго элемента ИЛИ, первый вход которого подключен к входу сброса счетчика текущего столбца и к первому выходу второго элемента сравнения, второй выход которого соединен с управляющим входом дешифратора загрузки канала и к входу элемента задержки, выход которого подключен к входу счетчика текущего столбца, выход которого подсоединен к первому входу второго элемента сравнения и к входу дешифратора загрузки канала, установочный вход счетчика текущего столбца подключен к выходу счетчика следующего столбца, счетный вход которого соединен с первым выходом первого элемента сравнения, с входом сброса первого счетчика столбцов, со счетным входом первого счетчика строк и с соответствующими входами сброса второй группы с 1-го по m-й триггеров, второй выход первого элемента сравнения подключен к разрешающему входу дешифратора выбора единичного значения, вход которого подключен к выходу первого счетчика столбцов, ко второму входу первого элемента сравнения и ко второму входу второго элемента сравнения, первый вход первого элемента сравнения соединен с выходом первого счетчика строк и с входом первого дешифратора выбора строки, выходы которого подключены к соответствующим управляющим входам первой группы с 1-го по n-й элементов запрета, информационные входы которых подключены к индикаторным выходам соответствующих элементов с 1-го по m-й столбцов матрицы 1 элементов однородной среды, выходы первой группы с 1-го по m-й элементов запрета соединены с соответствующими входами второй группы с 1-го по m-й элементов ИЛИ, выходы которых подключены к соответствующим S-входам второй группы с 1-го по m-й триггеров, выходы которых соединены с соответствующими вторыми входами группы с 1-го по m-й элементов И, первые входы которых подключены к соответствующим выходам дешифратора выбора единичного значения, выходы группы с 1-го по m-й элементов И подключены к соответствующим входам первого элемента ИЛИ, выход которого подсоединен к разрешающему входу дешифратора загрузки канала, выходы которого подключены к соответствующим первым входам первой группы с 1-го по m-й элементов ИЛИ, выход переполнения первого счетчика строк подключен к выходу переполнения устройства, выход второго элемента ИЛИ подсоединен к счетному входу первого счетчика столбцов.
| Устройство для оценки размещения элементов | 1987 |
|
SU1430949A1 |
