УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ РАЗМЕЩЕНИЯ В СИСТЕМАХ С ЛИНЕЙНОЙ ОРГАНИЗАЦИЕЙ Российский патент 2008 года по МПК G06F17/50 

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

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

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

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

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

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

Техническая задача решается тем, что в устройство для оценки степени приближения размещения к оптимальному, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, ..., n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен c j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, ..., m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок подсчета суммарной интенсивности обмена, содержащий матрицу D-триггеров сохранения перестановки, тактовый генератор, D-триггер стробирования работы устройства, D-триггер задержки счета строк, D-триггер сброса системы, два конъюнктора, счетчик номера столбца, счетчик номера строки, компаратор сравнения номеров строки и столбца, мультиплексор, счетчик подсчета интенсивности, причем информационные входы матрицы D-триггеров сохранения перестановки соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы D-триггеров сохранения перестановки подается сигнал со входа управления записью устройства, на вход тактового генератора подаются сигналы со входов подачи питания и подачи "земли", выход тактового генератора соединен с первым входом первого конъюнктора, выход D-тригтера стробирования работы устройства соединен со вторым входом первого конъюнктора, к информационному входу D-триггера стробирования работы устройства подведен сигнал со входа подачи питания, на синхровход D-триггера стробирования работы устройства подан сигнал «ЗАПИСЬ» со входа управления записью устройства, вход сброса D-триггера стробирования работы устройства соединен с выходом D-триггера сброса системы, на вход выборки счетчика номера столбца подведен сигнал со входа подачи питания, на счетный вход счетчика номера столбца подан сигнал с выхода первого конъюнктора, на вход сброса счетчика номера столбца подан сигнал с D-триггера сброса системы, выходы счетчика номера столбца соединены с соответствующими входами компаратора сравнения номеров строки и столбца, выход переполнения счетчика номера столбца соединен с синхровходом D-триггера задержки счета строк и с первым входом второго конъюнктора, синхровход D-триггера задержки счета строк подключен к выходу тактового генератора, выход D-триггера задержки счета строк соединен со счетным входом счетчика номера строки, на вход выборки счетчика номера строки подведен сигнал со входа подачи питания, на вход сброса счетчика номера строки подан сигнал с D-триггера сброса системы, выходы с первого по m-й счетчика номера строки соединены с соответствующими входами компаратора сравнения номеров строки и столбца, выход переполнения счетчика номера строки соединен со вторым входом второго конъюнктора, выход второго конъюнктора соединен с информационным входом D-триггера сброса системы и выходом выдачи сигнала окончания обработки перестановки, синхровход D-триггера сброса системы подключен к выходу тактового генератора, первый выход компаратора сравнения номеров строки и столбца подключен к разрешающему входу мультиплексора, на информационные входы мультиплексора поданы соответствующие сигналы с выходов матрицы из D-триггеров сохранения перестановки в порядке возрастания номеров строк и столбцов, причем на адресные входы с первого по n-й поданы соответствующие сигналы со счетных выходов счетчика номера столбца, на адресные входы с (n+1)-го по 2n-й мультиплексора поданы соответствующие сигналы со счетных выходов счетчика номера строки, выход мультиплексора соединен со входом выборки счетчика подсчета интенсивности, счетный вход счетчика подсчета интенсивности подключен к выходу тактового генератора, на вход сброса счетчика подсчета интенсивности подан сигнал с выхода D-триггера сброса системы, выходы счетчика подсчета интенсивности соединены с выходами интенсивности, на синхровход D-триггера сброса системы подаются сигналы с тактового генератора.

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

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

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

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

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

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

Сущность предлагаемого критерия минимализации интенсивности обмена поясняется на фиг.2. Здесь на фиг.2а и 2в представлены гипотетические варианты размещения графа, а на фиг.2б и 2г представлены соответствующие матрицы смежности. На фиг.2а и 2в кружками обозначены модули линейной системы, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают частоту обращения друг к другу соответствующих процессов смежных модулей. Из фиг.2а видно, что интенсивность взаимодействия между модулями 1-2 имеет наибольшее значение, а между модулями 3-4 наименьшее. Такой вариант размещения не является оптимальным, так как качество размещения можно улучшить, разместив дуги так, как показано на фиг.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 устройства, а также блок 30 подсчета суммарной интенсивности обмена, содержащий матрицу 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки, тактовый генератор 15, D-триггер 16 стробирования работы устройства, D-тригтер 19 задержки счета строк, D-триггер 25 сброса системы, первый конъюнктор 17 и второй конъюнктор 21, счетчик номера столбца 18, счетчик номера строки 20, компаратор 22 сравнения номеров строки и столбца, мультиплексор 23, счетчик 24 подсчета интенсивности, причем информационные входы матрицы 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки соединены с соответствующими выходами матрицы 1 элементов однородной среды, на синхровходы матрицы 14.i,j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки подается сигнал со входа 9 управления записью устройства, на вход тактового генератора 15 подаются сигналы со входов 26 подачи питания и 27 подачи "земли", выход тактового генератора 15 соединен с первым входом первого конъюнктора 17, выход D-триггера 16 стробирования работы устройства соединен со вторым входом первого конъюнктора 17, к информационному входу D-триггера 16 стробирования работы устройства подведен сигнал со входа 26 подачи питания, на синхровход D-триггера 16 стробирования работы устройства подан сигнал «ЗАПИСЬ» со входа 9 управления записью устройства, вход сброса D-триггера 16 стробирования работы устройства соединен с выходом D-триггера 25 сброса системы, на вход выборки счетчика 18 номера столбца подведен сигнал со входа 26 подачи питания, на счетный вход счетчика 18 номера столбца подан сигнал с выхода первого конъюнктора 17, на вход сброса счетчика 18 номера столбца подан сигнал с D-триггера 25 сброса системы, выходы счетчика 18 номера столбца соединены с соответствующими входами компаратора 22 сравнения номеров строки и столбца, выход переполнения счетчика 18 номера столбца соединен с синхровходом D-триггера 19 задержки счета строк и с первым входом второго конъюнктора 21, синхровход D-триггера 19 задержки счета строк подключен к выходу тактового генератора 15, выход D-триггера 19 задержки счета строк соединен со счетным входом счетчика 20 номера строки, на вход выборки счетчика 20 номера строки подведен сигнал со входа 26 подачи питания, на вход сброса счетчика 20 номера строки подан сигнал с D-триггера 25 сброса системы, выходы с первого по m-й счетчика 20 номера строки соединены с соответствующими входами компаратора 22 сравнения номеров строки и столбца, выход переполнения счетчика 20 номера строки соединен со вторым входом второго конъюнктора 21, выход второго конъюнктора 21 соединен с информационным входом D-триггера 25 сброса системы и выходом выдачи сигнала 28 окончания обработки перестановки, синхровход D-триггера 25 сброса системы подключен к выходу тактового генератора 15, первый выход компаратора 22 сравнения номеров строки и столбца подключен к разрешающему входу мультиплексора 23, на информационные входы мультиплексора 23 поданы соответствующие сигналы с выходов матрицы из 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки в порядке возрастания номеров строк и столбцов, причем на адресные входы с первого по n-й поданы соответствующие сигналы со счетных выходов счетчика 18 номера столбца, на адресные входы с (n+1)-го по 2n-й мультиплексора 23 поданы соответствующие сигналы со счетных выходов счетчика 20 номера строки, выход мультиплексора 23 соединен со входом выборки счетчика 24 подсчета интенсивности, счетный вход счетчика 24 подсчета интенсивности подключен к выходу тактового генератора 15, на вход сброса счетчика 24 подсчета интенсивности подан сигнал с выхода D-триггера 25 сброса системы, выходы счетчика 24 подсчета интенсивности REZ1, REZ2, ..., REZp (p=n(n-1)/2) соединены с выходами 29.1, 29.2, ..., 29.р (p=n(n-1)/2) интенсивности, на синхровход D-триггера 25 сброса системы подаются сигналы с тактового генератора 15.

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

Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач линейного размещения и трассировки.

Блоки 2.1-2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.

Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.

Сумматор 4 предназначен для суммирования n двоичных кодов.

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

Вход 6 записи устройства служит для записи матрицы, представляющей размещаемую схему (граф).

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

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

Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу текущий вариант размещения из матрицы 1 заносится в блок 5 памяти и в матрицу 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки, а также поступает на информационные входы мультиплексора 23.

Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.

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

Информационный выход 12 устройства необходим для выдачи варианта размещения, находящегося в блоке 5 памяти, на ВУУ.

Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.

Матрица 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров сохранения перестановки предназначена для запоминания значений матрицы 1 по синхросигналу со входа 9 («ЗАПИСЬ») от ВУУ.

Тактовый генератор 15 задает частоту обработки поступившей перестановки.

D-триггер 16 стробирования работы устройства необходим для выработки строба работы READY. Данный строб устанавливается в 1 (активность) высоким уровнем сигнала «ЗАПИСЬ» и сбрасывается сигналом сброса системы REZSYS.

Первый конъюнктор 17 запрещает выдачу тактовых импульсов на счетчик 6 столбцов при низком уровне сигнала READY.

Счетчик 18 номера столбца управляет перебором столбцов матрицы 1. Он выбран всегда, что обеспечивается подачей сигнала высокого уровня Н с выхода 27, сбрасывается по приходу высокого уровня сигнала сброса системы REZSYS на вход CLR. Выходы Q₀...Q_n содержат информацию о текущем номере обрабатываемого столбца. При переполнении счетчика на выход ТС выдается соответствующий сигнал.

D-триггер 19 задержки счета строк задерживает сигнал переполнения счетчика 18 номера столбца на один такт частоты, подаваемой с тактового генератора 15. Это необходимо для того, чтобы обрабатывались последние элементы столбцов.

Счетчик 20 номера строки управляет перебором строк матрицы 1. Он выбран всегда, что обеспечивается подачей сигнала высокого уровня Н с выхода 27, сбрасывается по приходу высокого уровня сигнала сброса системы REZSYS на вход CLR. Выходы Q₀...Q_n содержат информацию о текущем номере обрабатываемого столбца. При переполнении счетчика на выход ТС выдается соответствующий сигнал.

Второй конъюнктор 21 отвечает за формирование сигнала готовности оценки размещения OUT. Этот сигнал становится активным при одновременном переполнении счетчиков 18 и 20. Он может использоваться каким-либо другим внешним устройством для считывания оценки размещения из данного устройства.

Компаратор 22 сравнения номеров строки и столбца сравнивает текущий номер столбца и текущий номер строки матрицы 1. Если номер столбца больше, то активируется сигнал СВ, иначе сигнал RB.

Мультиплексор 23 обеспечивает коммутацию элементов матрицы 1, подаваемых на информационные входы, на выход в зависимости от информации, поступающей на адресные входы мультиплексора. Адрес определяется текущими значениями строки и столбца. Вход Е разрешает работу мультиплексора. В данной схеме мультиплексор работает при условии, что текущий номер столбца больше текущего номера строки (по высокому уровню сигнала СВ).

Счетчик 24 подсчета интенсивности осуществляет подсчет количества тактовых импульсов, которые успевают прийти на счетный вход С, когда с выхода мультиплексора 23 приходит высокий уровень. Это количество равно числу единиц, находящихся выше главной диагонали матрицы 1. Счетчик находится в рабочем состоянии, когда на вход выборки СЕ приходит высокий уровень. Сброс осуществляется по сигналу сброса системы REZSYS.

D-триггер 25 сброса системы задерживает сигнал OUT на один такт частоты, подаваемой с тактового генератора 15. Выходной сигнал REZSYS является сигналом общего сброса блока 30 подсчета суммарной интенсивности обмена, в том числе счетчиков 18, 20, 24 и триггера стробирования работы устройства 16.

На вход Н 26 подается питание, вход L 27 - "земля".

Сигнал с выхода OUT 28 дает возможность внешним устройствам считывать значения интенсивности.

По выходам 29.1...29.р, где р=n(n-1)/2, устройство выдает значение интенсивности.

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

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

На вход 9 приходит сигнал «ЗАПИСЬ» от ВУУ, свидетельствующий о том, что новая перестановка записана в элементы матрицы 1. Если «ЗАПИСЬ»=0, то сигналы с генератора 15 блокируются первым конъюнктором 17. Если «ЗАПИСЬ»=1, то информация из матрицы 1 переписывается в матрицу из 14.i.j (i=1, 2, ..., n, j=1, 2, ..., m) D-триггеров и поступает на информационные входы мультиплексора 23. При этом с выхода D-триггера 16 на вход первого конъюнктора 17 приходит высокий уровень сигнала, и сигнал строба работы системы READY устанавливается в единицу. Импульсы с генератора 15 начинают проходить через первый конъюнктор 17 на счетный вход счетчика 18.

Первый импульс, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным единице (COLUMN=1). На выходе ТС счетчика 18 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. Значение COLUMN=1 приходит на компаратор 22 и сравнивается с текущим значением номера строки (ROW=0). В результате сравнения сигнал СВ становится активным и разрешает работу мультиплексора 23. Значения адресных сигналов (ROW0=0, ROW1=0, ..., ROWm=0; COLUMN0=1, COLUMN1=0, ..., COLUMNn=0) обеспечивают коммутацию с выходом мультиплексора 23 значения B₁₂. Уровень на выходе мультиплексора 23 определяет, пройдет ли на счетный вход счетчика 24 текущий импульс с генератора 15. Если данный уровень высокий, то счетчик 24 срабатывает, увеличивая значение интенсивности на 1.

Второй импульс, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным двум (COLUMN=2). На выходе ТС счетчика 18 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=2 и ROW=0. В результате сравнения сигнал СВ остается активным и разрешает работу мультиплексора 23. Значения адресных сигналов (ROW0=0, ROW1=0, ..., ROWm=0; COLUMN0=0, COLUMN1=1, ..., COLUMNn=0) обеспечивают коммутацию с выходом мультиплексора 23 значения В₁₃. От уровня на выходе мультиплексора 23 зависит, пройдет ли на счетный вход счетчика 24 текущий импульс с генератора 15. Если данный уровень высокий, то счетчик 24 срабатывает, увеличивая значение интенсивности на 1. Так происходит до прихода n-го импульса.

Импульс n, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным n (COLUMN=n). Выход ТС счетчика 18 становится равным единице, на информационный вход D-триггера 19 передается высокий уровень. На выходе ТС счетчика 18 высокий уровень, но на выходе ТС счетчика 20 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=n и ROW=0. В результате сравнения сигнал СВ остается активным и разрешает работу мультиплексора 23. Значения адресных сигналов (ROW0=0, ROW1=0, ..., ROWm=0; COLUMN0=1, COLUMN1=1, ..., COLUMNn=1) обеспечивают коммутацию с выходом мультиплексора 23 значения В_1n. От уровня на выходе мультиплексора 23 зависит, пройдет ли на счетный вход счетчика 24 текущий импульс с генератора 15. Если данный уровень высокий, то счетчик 24 срабатывает, увеличивая значение интенсивности на 1.

Импульс n+1, поступивший на вход счетчика 18, вызывает переворот этого счетчика (COLUMN=0). Этот импульс становится причиной изменения выходного значения D-триггера 19 с 0 на 1, и вызванный импульс поступает на счетный вход счетчика 20, увеличивая его значение с 0 на 1 (ROW=1). На выходе ТС счетчика 18 низкий уровень, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=0, ROW=1. В результате сравнения сигнал СВ низким уровнем запрещает работу мультиплексора 23. На выходе мультиплексора 23 низкий уровень, что запрещает работу счетчика 24.

Импульс n+2, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным единице (COLUMN=1). На выходе ТС счетчика 18 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=1 и ROW=1. В результате сравнения сигнал СВ низким уровнем запрещает работу мультиплексора 23. На выходе мультиплексора 23 низкий уровень, что запрещает работу счетчика 24.

Импульс 2n, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным n (COLUMN=n). Выход ТС счетчика 18 становится равным единице, на информационный вход D-триггера 19 передается высокий уровень. На выходе ТС счетчика 18 высокий уровень, но на выходе счетчика 20 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=n и ROW=1. В результате сравнения сигнал СВ остается активным и разрешает работу мультиплексора 23. Значения адресных сигналов (ROW0=1, ROW1=0, ..., ROWm=0; COLUMN0=1, COLUMN1=1, ..., COLUMNn=1) обеспечивают коммутацию с выходом значения В_2n. От уровня на выходе мультиплексора 23 зависит, пройдет ли на счетный вход счетчика 24 текущий импульс с генератора 15. Если данный уровень высокий, то счетчик 24 срабатывает, увеличивая значение интенсивности на 1.

Импульс m(n-1), поступивший на вход счетчика 18, вызывает переворот этого счетчика (COLUMN=0). Этот импульс становится причиной изменения выходного значения D-триггера 19 с 0 на 1, что создает импульс, увеличивающий значение счетчика 20 с m-1 на m (ROW=m). На выходе ТС счетчика 18 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS-0. На компаратор 22 приходят значения COLUMN=0, ROW=m. В результате сравнения сигнал СВ низким уровнем запрещает работу мультиплексора 23. На выходе мультиплексора 23 низкий уровень, что запрещает работу счетчика 24.

Импульс m(n-1)+1, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным единице (COLUMN=1). На выходе ТС счетчика 18 низкий уровень, следовательно, на выходах конъюнкторов 17 и 21 также присутствует низкий уровень и сброса системы не происходит: REZSYS=0. На компаратор 22 приходят значения COLUMN=1 и ROW=m. В результате сравнения сигнал СВ низким уровнем запрещает работу мультиплексора 23. На выходе мультиплексора 23 низкий уровень, что запрещает работу счетчика 24.

Импульс m*n-й, поступивший на вход счетчика 18, увеличивает его значение на 1, и оно становится равным n (COLUMN=n). Вследствие переполнения на выходе ТС счетчика 18 высокий уровень. На компаратор 22 приходят значения COLUMN=n и ROW=m. В результате сравнения сигнал СВ низким уровнем запрещает работу мультиплексора 23. На выходе мультиплексора 23 низкий уровень, что запрещает работу счетчика 24. На следующем импульсе генератора 15 переполняется и счетчик 20, что дает высокий уровень на выходе второго конъюнктора 21, по которому другое устройство, принимающее из данного устройства значение интенсивности, может осуществить считывание значения интенсивности, установившегося на счетчике 24. На информационный вход D-триггера 25 поступает высокий уровень, который при следующем импульсе с генератора 15 вызовет сброс блока 30 подсчета суммарной интенсивности обмена, который будет ждать следующей активизации сигнала «ЗАПИСЬ».

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

Изобретение относится к области цифровой вычислительной техники и может быть использовано для моделирования комбинаторных задач при проектировании вычислительных систем. Техническим результатом является расширение области применения устройства за счет формирования размещения в системах с линейной организацией по критерию минимизации интенсивности обмена данными между модулями решаемой задачи. Устройство содержит матрицу из m строк и n столбцов элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, блок подсчета суммарной интенсивности обмена, содержащий матрицу D-триггеров сохранения перестановки, тактовый генератор, D-триггеры стробирования работы устройства, задержки счета строк, сброса системы, конъюнкторы, счетчики номера столбца и номера строки, компаратор, мультиплексор, счетчик подсчета интенсивности. 2 ил.

Устройство для оценки степени приближения размещения к оптимальному, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, ..., n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен c j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, ..., m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, отличающееся тем, что в него дополнительно введен блок подсчета суммарной интенсивности обмена между модулями вычислительной системы, содержащий матрицу D-триггеров сохранения перестановки, тактовый генератор, D-триггер стробирования работы устройства, D-триггер задержки счета строк, D-триггер сброса, формирующий сигнал "сброс" элементов устройства, два конъюнктора, счетчик номера столбца, счетчик номера строки, компаратор сравнения номеров строки и столбца, мультиплексор, счетчик подсчета интенсивности, предназначенный для подсчета интенсивности обмена между модулями вычислительной системы, причем информационные входы матрицы D-триггеров сохранения перестановки соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы D-триггеров сохранения перестановки подается сигнал со входа управления записью устройства, на входы тактового генератора поступают сигналы питания и "земля", выход тактового генератора соединен с первым входом первого конъюнктора, выход D-триггера стробирования работы устройства соединен со вторым входом первого конъюнктора, к информационному входу D-триггера стробирования работы устройства подведен сигнал со входа подачи питания, на синхровход D-триггера стробирования работы устройства подан сигнал "запись" с входа управления записью устройства, вход сброса D-триггера стробирования работы устройства соединен с выходом D-триггера сброса, на разрешающий вход счетчика номера столбца подведен сигнал с входа подачи питания, на счетный вход счетчика номера столбца подан сигнал с выхода первого конъюнктора, на вход сброса счетчика номера столбца подан сигнал с D-триггера сброса, информационные выходы счетчика номера столбца соединены с соответствующими входами компаратора сравнения номеров строки и столбца, выход переполнения счетчика номера столбца соединен с информационным входом D-триггера задержки счета строк и с первым входом второго конъюнктора, синхровход D-триггера задержки счета строк подключен к выходу тактового генератора, выход D-триггера задержки счета строк соединен со счетным входом счетчика номера строки, на разрешающий вход счетчика номера строки подведен сигнал с входа подачи питания, на вход сброса счетчика номера строки подан сигнал с D-триггера сброса системы, выходы с первого по m-й счетчика номера строки соединены с соответствующими входами компаратора сравнения номеров строки и столбца, выход переполнения счетчика номера строки соединен со вторым входом второго конъюнктора, выход второго конъюнктора соединен с информационным входом D-триггера сброса системы и выходом выдачи сигнала окончания обработки перестановки, синхровход D-триггера сброса системы подключен к выходу тактового генератора, выход компаратора сравнения номеров строки и столбца, на котором формируется сигнал в случае, если номер столбца больше, чем номер строки, подключен к разрешающему входу мультиплексора, на информационные входы мультиплексора поданы соответствующие сигналы с выходов матрицы из D-триггеров сохранения перестановки в порядке возрастания номеров строк и столбцов, причем на адресные входы с первого по n-ый поданы соответствующие сигналы со счетных выходов счетчика номера столбца, на адресные входы с (n+1)-го по 2n-й мультиплексора поданы соответствующие сигналы со счетных выходов счетчика номера строки, выход мультиплексора соединен с разрешающим входом счетчика подсчета интенсивности, счетный вход счетчика подсчета интенсивности подключен к выходу тактового генератора, на вход сброса счетчика подсчета интенсивности подан сигнал с выхода D-триггера сброса системы, выходы счетчика подсчета интенсивности соединены с выходами устройства.