УСТРОЙСТВО ПОИСКА МИНИМАЛЬНОГО ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ В СИСТЕМАХ С ЛИНЕЙНОЙ ОРГАНИЗАЦИЕЙ ПРИ НАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ Российский патент 2008 года по МПК G06F7/00 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-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом первого сумматора, выходы которых соединены с выходом максимальной длины ребра устройства и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, ..., m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок поиска нижней оценки, содержащий генератор импульсов, дешифратор строки, дешифратор фиксируемых дут, мультиплексор выбора элемента, счетчик строк, счетчик столбцов, счетчик последнего фиксированного модуля, счетчик текущего значения расстояния, вычитающий счетчик расстояний, счетчик фиксируемой дуги, группу из m счетчиков фиксируемых дуг, первый и второй элемент сравнения, группу из m RS-триггеров, группу из m блоков элементов запрета, первый и второй триггер режима, группу из m элементов ИЛИ, первый и второй элемент ИЛИ, первый, второй и третий элементы И, элемент задержки, счетчик значения расстояния, причем вход запуска устройства подключен ко входу генератора импульсов, выход которого подключен ко второму входу первого и второго элемента И, первый вход второго элемента И подсоединен к прямому выходу первого триггера режима, инверсный выход которого соединен с первым входом первого элемента И, выход второго элемента И подключен к счетному входу счетчика столбцов, выход которого подключен к управляющему входу мультиплексора выбора элемента, выход переполнения счетчика столбцов подсоединен к счетному входу счетчика строк и к R-входам группы из m RS-триггеров, выход переполнения счетчика строк подсоединен к выходу переполнения устройства, выход счетчика строк подключен ко входу дешифратора строки, выходы с первого по m-й которого подсоединены к соответствующим управляющим входам групп из m блоков элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы элементов однородной среды, выходы группы из m блоков элементов запрета подсоединены к соответствующим входам группы из m элементов ИЛИ, выходы которых подключены к соответствующим S-входам группы из m RS-триггеров, выходы которых подсоединены к соответствующим входам мультиплексора выбора элемента, выход которого подсоединен к R-входу первого триггера режима, S-вход которого подключен к выходу первого элемента ИЛИ, выход первого элемента И подключен ко входу элемента задержки и ко второму входу третьего элемента И, к первому входу третьего элемента И подсоединен прямой выход второго триггера режима, к выходу третьего элемента И подключен счетный вход счетчика текущего значения расстояния, выход которого подсоединен к первому входу первого элемента сравнения, ко второму входу которого подведен выход вычитающего счетчика расстояний, к первому выходу первого элемента сравнения подсоединен R-вход второго триггера режима, второй выход первого элемента сравнения подключен ко второму входу второго элемента ИЛИ, к счетному входу счетчика значения расстояния, ко второму входу первого элемента ИЛИ, к вычитающему входу вычитающего счетчика расстояний и к входу сброса счетчика текущего значения расстояния, S-вход второго триггера режима подведен к первому входу второго элемента ИЛИ, ко второму выходу второго элемента сравнения и к первому входу первого элемента ИЛИ, выход второго элемента ИЛИ подключен к входу сброса счетчика фиксируемой дуги, счетный вход которого подключен к выходу элемента задержки, выход счетчика фиксируемой дуги подключен к первому входу второго элемента сравнения, ко второму входу которого подсоединен выход счетчика значения расстояния, первый выход второго элемента сравнения подключен к счетному входу счетчика последнего фиксированного модуля, выход которого подведен к входу дешифратора фиксируемых дуг, выходы с первого по m-й которого подключены к соответствующим счетным входам группы из m счетчиков фиксируемых дуг, выходы которых подключены к соответствующим выходам из m назначенных модулей устройства.

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

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

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

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

При поиске оптимального (субоптимального) варианта размещения вначале необходим поиск идеальной недостижимой нижней оценки размещения при допущении, что топология исходного графа G и графа связей между модулями линейной топологической модели тождественны. Для нахождения нижней оценки необходимо расположить элементы матрицы А по убыванию своих значений, а элементы матрицы D - по возрастанию. После этого необходимо найти скалярное произведение соответствующих полученных значений.

Минимально возможное значение интенсивности размещения L для орграфа G независимо от топологической модели определяется по формуле:

где ||a_k'||, ||d_k ^'|| - векторы, первый из которых содержит ненулевые элементы матрицы смежности А, расположенные по убыванию, а второй - ненулевые элементы матрицы расстояний D, расположенные по возрастанию; k - порядковый номер элемента; t=|Е| - мощность множества дуг Е. При этом фактическое значение интенсивности размещения всегда либо больше, либо равно L*.

Порядок расчета значения длины L и сущность предлагаемого критерия поясняются на фиг. 2. Здесь на фиг. 2а представлен гипотетический ориентированный граф G с четырьмя вершинами x₁, x₂, x₃, x₄, на фиг.2б изображена матрица смежности для заданного орграфа (i-я строка/столбец матрицы соответствуют вершине x_i графа G), на фиг.2в показана матрица расстояний для линейной модели. На фиг.2г представлен гипотетический вариант размещения для графа G. Здесь на фиг.2г кружками обозначены гипотетические модули, а цифры внутри модулей - их соответствующие номера. Числа над пунктирными линиями обозначают интенсивность передачи информации (взаимодействия процессов, передачи данных) между смежными модулями. На фиг. 2д записаны вектор |a'| и вектора |d'| для линейной топологической организации, а также показан расчет соответствующего значения нижней оценки L* по формуле (1).

Устройство поиска минимального значения интенсивности в системах с линейной организацией при направленной передаче информации (фиг.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 устройства, а также дополнительно введенный блок 20 поиска нижней оценки, содержащий генератор 14 импульсов, дешифратор 15 строки, дешифратор 16 фиксируемых дуг, мультиплексор 17 выбора элемента, счетчик 18 строк, счетчик 19 столбцов, счетчик 21 последнего фиксированного модуля, счетчик 22 текущего значения расстояния, вычитающий 23 счетчик расстояний, счетчик 24 фиксируемой дуги, группу 25.1-25.m счетчиков фиксируемых дуг, первый 26 и второй 27 элемент сравнения, группу 28.1, 28.2, ..., 28.m RS-триггеров, группу 29.1, 29.2, ..., 29.m блоков элементов запрета, первый 30 и второй 31 триггер режима, группу 32.1, 32.2, ..., 32.m элементов ИЛИ, первый 33 и второй 34 элемент ИЛИ, первый 35, второй 36 и третий 38 элементы И, элемент 37 задержки, счетчик 42 значения расстояния, причем вход 39 запуска устройства подключен ко входу генератора 14 импульсов, выход которого подключен ко второму входу первого 35 и второго 36 элемента И, первый вход второго 36 элемента И подсоединен к прямому выходу первого 30 триггера режима, инверсный выход которого соединен с первым входом первого 35 элемента И, выход второго 36 элемента И подключен к счетному входу счетчика 19 столбцов, выход которого подключен к управляющему входу мультиплексора 17 выбора элемента, выход переполнения счетчика 19 столбцов подсоединен к счетному входу счетчика 18 строк и к R-входам группы 28.1, 28.2, ..., 28.m RS-триггеров, выход переполнения счетчика 18 строк подсоединен к выходу 40 переполнения устройства, выход счетчика 18 строк подключен ко входу дешифратора 15 строки, выходы с первого по m-й которого подсоединены к соответствующим управляющим входам групп 29.1, 29.2, ..., 29.m блоков элементов запрета, соответствующие входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, выходы группы 29.1, 29.2, ..., 29.m блоков элементов запрета подсоединены к соответствующим входам группы 32.1, 32.2, ..., 32.m элементов ИЛИ, выходы которых подключены к соответствующим S-входам группы 28.1, 28.2, ..., 28.m RS-триггеров, выходы которых подсоединены к соответствующим входам мультиплексора 17 выбора элемента, выход которого подсоединен к R-входу первого 30 триггера режима, S-вход которого подключен к выходу первого 33 элемента ИЛИ, выход первого 35 элемента И подключен ко входу элемента 37 задержки и ко второму входу третьего 38 элемента И, к первому входу третьего 38 элемента И подсоединен прямой выход второго 31 триггера режима, к выходу третьего 38 элемента И подключен счетный вход счетчика 22 текущего значения расстояния, выход которого подсоединен к первому входу первого 26 элемента сравнения, ко второму входу которого подведен выход вычитающего 23 счетчика расстояний, к первому выходу первого 26 элемента сравнения подсоединен R-вход второго 31 триггера режима, второй выход первого 26 элемента сравнения подключен ко второму входу второго 34 элемента ИЛИ, к счетному входу счетчика 42 значения расстояния, ко второму входу первого 33 элемента ИЛИ, к вычитающему входу вычитающего 23 счетчика расстояний и к входу сброса счетчика 22 текущего значения расстояния, S-вход второго 31 триггера режима подведен к первому входу второго 34 элемента ИЛИ, ко второму выходу второго 27 элемента сравнения и к первому входу первого 33 элемента ИЛИ, выход второго 34 элемента ИЛИ подключен к входу сброса счетчика 24 фиксируемой дуги, счетный вход которого подключен к выходу элемента 37 задержки, выход счетчика 24 фиксируемой дуги подключен к первому входу второго 27 элемента сравнения, ко второму входу которого подсоединен выход счетчика 42 значения расстояния, первый выход второго 27 элемента сравнения подключен к счетному входу счетчика 21 последнего фиксированного модуля, выход которого подведен к входу дешифратора 16 фиксируемых дуг, выходы с первого по m-й которого подключены к соответствующим счетным входам группы 25.1-25.m счетчиков фиксируемых дуг, выходы которых подключены к соответствующим выходам 41.1, 41.2, ..., 41.m назначенных модулей устройства.

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

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

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

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

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

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

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

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

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

Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.

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

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

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

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

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

Дешифратор 15 строки необходим для выбора очередной строки матрицы 1.

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

Мультиплексор 17 выбора элемента служит для подачи информации о наличии дуги в графе G с выходов группы 29.1, 29.2, ..., 29.m блоков элементов запрета на R-вход первого 30 триггера режима.

Счетчик 18 строк служит для накапливания информации о текущей обрабатываемой строке матрицы 1.

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

Блок 20 поиска нижней оценки необходим для формирования минимального значения интенсивности в системах с линейной организацией.

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

Счетчик 22 текущего значения расстояния необходим для хранения количества зафиксированных дуг для текущего значения d'. Например, для d'=1 таких значений (n-1).

Вычитающий 23 счетчик расстояний предназначен для хранения текущего значения расстояния, соответствующего вектору ||d'|| (d'=1, 2, ..., (n-1)).

Счетчик 24 фиксируемой дуги служит для подсчета количества модулей, в которых должна быть зафиксирована дуга графа G для текущего значения d'. Например, для d'=3 таких модулей должно быть 3.

Группа 25.1-25.m счетчиков фиксируемых дуг необходима для подсчета количества зафиксированных дуг графа G. Эта группа моделирует в предлагаемом устройстве линейную топологическую модель.

Первый 26 элемент сравнения необходим для сравнения значений, содержащихся в счетчике 22 текущего значения расстояния и счетчике 23 расстояний. В нем происходит сравнение количества зафиксированных дуг для текущего значения d'.

Второй 27 элемент сравнения предназначен для проверки количества зафиксированных модулей для текущего значения d', Например, для d'=3 дуга должна быть зафиксирована в трех модулях линейной топологической системы.

Группа 28.1, 28.2, ..., 28.m SR-триггеров служит для хранения информации о наличии дуги между соответствующими инцидентными вершинами.

Группа 29.1, 29.2, ..., 29.m блоков элементов запрета предназначена для блокировки поступления значений от элементов с 1-й по m-ю строк матрицы 1 на соответствующие элементы группы 32.1, 32.2, ..., 32.m элементов ИЛИ.

Первый 30 триггер режима предназначен для выбора режима работа блока 20 поиска нижней оценки. Когда он находится в единичном состоянии, происходит выбор очередной дуги графа (т.е. выбор очередного элемента матрицы смежности). Если триггер 30 режима находится в нулевом состоянии, то устройство находится в состоянии фиксации дуги графа.

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

Группа 32.1, 32.2, ..., 32.m элементов ИЛИ необходима для объединения сигналов с выходов первой группы 29.1, 29.2, ..., 29.m блоков элементов запрета соответственно.

Первый 33 элемент ИЛИ служит для объединения сигналов с первого выхода второго 27 элемента сравнения и со второго выхода первого 26 элемента сравнения.

Второй 34 элемент ИЛИ необходим для объединения сигналов со второго выхода первого 26 элемента сравнения и со второго выхода второго 27 элемента сравнения.

Первый 35, второй 36 и третий 38 элементы И предназначены для блокировки поступления на их выходы импульсов с выхода генератора 14 импульсов.

Элемент 37 задержки служит для задержки тактового импульса с выхода генератора 14 импульсов на время, достаточное для установления в счетчике 22 текущего значения расстояния нового кода, сравнения его в первом 26 элементе сравнения и появления на одном из его выходах единичного импульса, свидетельствующего о результате сравнения.

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

Выход 40 переполнения устройства служит для подачи информации о переполнении счетчика 18 номера строки, что одновременно является сигналом о завершении работы блока 20.

Выходы 41.1, 41.2, ..., 41.m назначенных модулей необходимы для подачи ВУУ соответствующих кодов значений интенсивности для каждого модуля линейной топологической модели.

Счетчик 42 значения расстояния служит для хранения текущего значения d'.

Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.

Первоначально в матрице 1 элементов однородной среды содержится исходный вариант размещения, соответствующий матрице смежности исходного графа. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Группа 28.1-28.m SR-триггеров находится в состоянии логического нуля, в группе 25.1-25.m счетчиков фиксируемых дуг, содержатся коды нулей («00...00»), первый 30 триггер режима находится в состоянии логической единицы, второй триггер режима находится в состоянии логического нуля, в счетчике 24 фиксируемой дуги содержится код нуля («00...00»), в счетчике 19 столбцов и счетчике 18 строк хранятся коды единицы («00...01»). Код единицы с выхода счетчика 18 строк поступает на вход дешифратора 15, поэтому на его первом выходе присутствует единый сигнал, который подаются на соответствующие управляющие входы первого блока 29.1 элементов запрета, обеспечивая прохождение на их выходы сигналов с индикаторных выходов элементов первой строки матрицы 1. Эти сигналы проходят через группу 32.1-32.m элементов ИЛИ и поступают на соответствующие S-входы группы 28.1-28.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. В счетчике 21 последнего фиксированного модуля содержится код числа единица («00...01»), так как нагрузка первой фиксируемой дуги в линейной системе будет на модуле 2 (фиг.1г). В вычитающем 23 счетчике расстояний содержится код числа (n-1). В счетчике 22 текущего значения расстояния содержится код нуля, так как на начальном этапе не было зафиксировано ни одной дуги. Второй 31 триггер режима находится в состоянии логической единицы, поэтому единичный потенциал поступает на первый вход второго 36 элемента И. В счетчике 42 значения расстояния хранится код числа единицы.

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

Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1, 2, ..., n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы первого сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.

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

Работа предлагаемого устройства делится на два этапа. Если триггер 30 режима находится в состоянии логической единицы, то на прямом его выходе присутствует единичный потенциал, который подается на первый вход элемента 36 И. На инверсном выходе триггера 30 режима в это время присутствует нулевой потенциал, который присутствует на первом входе элемента 35 И, что запрещает появление импульса на его выходе. В этом режиме устройство работает в режиме выбора очередной дуги матрицы смежности триггер 30 режима находится в состоянии логического нуля, то устройство находится в режиме фиксации выбранной дуги. В этом случае на первом входе элемента 36 И присутствует нулевой потенциал с прямого выхода триггера 30 режима, что запрещает появление сигналов на его выходе. Тогда на инверсном выходе триггера 30 режима присутствует единичный потенциал, который поступает на первый вход элемента 35 И, что разрешает поступление сигналов на его выход.

Первый тактовый импульс с выхода генератора 14 импульсов на вторые входы 35 и 36 И. Так как на первом входе элемента 35 И присутствует нулевой потенциал с инверсного выхода триггера 30, то единичный импульс на его выходе не появляется. Так как на первом входе элемента 36 И присутствует единичный потенциал с прямого выхода триггера 30 режима, то на выходе элемента 36 И возбуждается единичный импульс, который подается на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое на единицу, устанавливая в нем код числа два («00...010»). Код числа два с входа счетчика 19 подается на управляющий вход мультиплексора 17 и разрешает прохождение на его выход сигнала с выхода триггера 28.2, в случае, если он установлен в единичное состояние. Этот сигнал с выхода мультиплексора 17 подается на R-вход триггера 30, который устанавливается в нулевое состояние. Следовательно, на его прямом выходе появляется нулевой потенциал, который поступает на первый вход элемента 36 И, и запрещает появление на его выходе единичных импульсов. На инверсном выходе триггера 30 появляется единичный потенциал, который подается на первый вход элемента 35 И, и разрешает появление на его выходе единичных сигналов.

Следующий тактовый импульс с выхода генератора 14 импульсов поступает на вторые входы элементов 35 и 36 И. Так как элемент 36 И закрыт, то на его выходе единичного сигнала не появляется. В свою очередь, так как на первом входе элемента 35 И присутствует единичный потенциал, то на его выходе возбуждается единичный импульс, который подается на элемент 37 задержки и на второй вход элемента 38 И. На первом входе элемента 38 И присутствует единичный потенциал, следовательно, при поступлении единичного сигнала с выхода элемента 35 И. На выходе элемента 38 И появляется единичный сигнал, который подается на счетный вход счетчика 22 и по переднему фронту увеличивает его содержимое до кода единицы («00...01»).

Код с выхода счетчика 22 поедается на первый вход элемента 26 сравнения, на втором входе которого присутствует код (n-1). В результате сравнения результат будет истинным. Следовательно, единичный сигнал возбуждается на первом выходе элемента 26 сравнения, который подается на R-вход триггера 31, устанавливая его в нулевое состояние, поэтому на его выходе появляется нулевой потенциал, который поступает на первый вход элемента 38 И, и тем самым запрещает появление на его выходе сигналов. К этому времени элемент 37 задержки пропускает импульс со своего входа, который подается на счетный вход счетчика 24 и увеличивает его по переднему фронту до кода единицы («00...01»). Этот код подается на первый вход элемента 27 сравнения, на втором входе которого присутствует код единицы с выхода счетчика 42. Результат сравнения будет истинным, поэтому единичный потенциал появится на первом выходе элемента 27 сравнения, который поступит на счетный вход счетчика 21, в котором по переднему фронту увеличивается содержимое на единицу и устанавливается код числа два («00...010»). Код числа два с выхода счетчика 21 поступает на вход дешифратора 16. Так как на его входе присутствует код числа два («00...010»), то на втором его выходе возбуждается единичный импульс, который подается на счетный вход счетчика 25.2 и по заднему фронту увеличивает его содержимое до кода единицы («00...01»). Таким образом происходит фиксация первой дуги графа.

Следующий тактовый импульс с выхода генератора 14 импульсов поступает на вторые входы элементов 35 и 36 И, но на выходе единичный импульс появляется только у элемента 35 И. Единичный импульс с его выхода подается на вход элемента 37 задержки и на второй вход элемента 38 И, но так как на первом входе элемента 38 И присутствует нулевой уровень, сигнала на его выхода не возбуждается. Когда элемент 37 задержки пропускает импульс на его выход, он поступает на счетный вход счетчика 24 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («00...010»). Этот код поступает на первый вход элемента 27 сравнения, на втором входе которого присутствует код единицы с выхода счетчика 42. Результат сравнения будет ложным, поэтому единичный импульс появляется на втором выходе элемента 27 сравнения. Этот импульс подается на элементы 33, 34 ИЛИ и на S-вход триггера 31, устанавливая его в единичное состояние. Этот потенциал подается на первый вход элемента 38 И. Единичный сигнал проходит через элемент 34 ИЛИ и поступает на вход сброса счетчика 24, устанавливая в нем код нуля. Единичный потенциал со второго выхода элемента 27 сравнения проходит через элемент 33 ИЛИ и подается на S-вход триггера 30, устанавливая его в единичное состояние. Таким образом, прохождение импульсов через элемент 35 И запрещается, а разрешается через элемент 36 И.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на вторые входы элементов 35 и 36 И, но только на выходе элемента 36 И появляется единичный импульс, который поступает на счетный вход счетчика 19 и по переднему фронту увеличивает его содержимое до кода тройки («00...011»). Этот код подается на управляющий вход мультиплексора 17, разрешая прохождение единичного потенциала с выхода триггера 28.3 на выход мультиплексора 17. Этот сигнал подается на R-вход триггера 30 и устанавливает его в нулевое состояние. Таким образом, нулевой потенциал с его выхода поступает на первый вход элемента 38 И и блокирует появление импульсов на выходе. В свою очередь единичный сигнал с инверсного выхода триггера 30 подается на первый вход элемента 35 и разрешает прохождение тактовых импульсов на выход.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на первый вход элемента 35 И, и единичный сигнал появляется на его выходе. Этот единичный сигнал подается на вход элемента 37 задержки и на второй вход элемента 38 И. Так как на его первом входе присутствует единичный потенциал с прямого выхода триггера 31, то на выходе элемента 38 И появляется единичный импульс, который поступает на счетный вход счетчика 22 и по переднему фронту увеличивает его содержимое до кода двойки («00...010»). Этот код поступает на первый вход элемента 26 сравнения, на втором входе которого присутствует (n-1). Результат сравнения будет положительным, поэтому на первом выходе элемента 26 сравнения появится положительный импульс, который подается на R-вход триггера 31 и устанавливает его в нулевое состояние. Таким образом, подача сигналов на счетный вход счетчика 22 блокируется. К этому времени элемент 37 задержки пропускает положительны импульс на счетный вход счетчика 24 и по переднему фронту увеличивает его содержимое до кода единицы («00...01»). Этот код подается на первый вход элемента 27 сравнения, на втором входе которого присутствует код единицы с выхода счетчика 42. Результат сравнения будет положительным и единичный сигнал появляется на первом выходе элемента 27 сравнения. Этот сигнал поступает на счетный вход счетчика 21 и по переднему фронту увеличивает его содержимое на единицу до кода тройки («0...011»). Этот код поступает на вход дешифратора 16, возбуждая на его третьем выходе положительный импульс, который по заднему фронту увеличивает содержимое счетчика 25.3 на единицу до кода единицы. Таким образом, происходит фиксация очередной дуги.

Далее работа устройства продолжается аналогично до тех пор, пока результат сравнения в элементе 26 сравнения не будет отрицательным. Это означает, что все дуги для d'=1 зафиксированы. Следовательно, следующая назначаемая дуга будет иметь значение d'=2, то есть она будет назначаться на два модуля топологической модели (на фиг.2г это дуги, зафиксированные в модулях 1-3 и 2-4). Это означает, что счетчик 22 необходимо сбросить в ноль, а счетчик 23 уменьшить на единицу (количество расстояний для d'=2 может быть n-2). Кроме того, в данном случае следует увеличить счетчик 42 на единицу и установить триггер 30 в единичное состояние. В этом случае единичный сигнал появляется на втором выходе элемента 26 сравнения, который поступает на второй вход элемента ИЛИ 34, на счетный вход счетчика 42, вычитающий вход счетчика 23, вход сброса счетчика 22 и первый вход элемента 33 ИЛИ. В результате этого будут выполняться описанные выше действия. После этого с появлением нового импульса с выхода генератора 14 импульсов работа устройства будет проходить аналогично.

В случае переполнения счетчика 19 на выходе переполнения появляется единичный импульс, который подается на счетный вход счетчика 18 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («00...010»). Этот код поступает на вход дешифратора 15. В результате на втором его выходе появляется единичный сигнал, который проходит на управляющие входы второго 29.2 блока группы 29.1, 29.2, ..., 29.m блоков элементов запрета. В результате на выходы второго 29.2 блока элементов запрета проходят сигналы с индикаторных выходов элементов второй строки матрицы 1. Эти сигналы проходят через группу 32.1-32.m элементов ИЛИ и поступают на соответствующие S-входы группы 28.1-28.m триггеров, устанавливая их в единое состояние при наличии соответствующих единичных сигналов. Содержимое счетчика 19 устанавливается в код единицы («00...01»).

Работа схемы продолжается по описанному выше принципу до тех пор, пока на выходе переполнения 40 счетчика 18 не появится сигнал переполнения. Это означает, что все строки матрицы 1 просмотрены и работа устройства завершена. К этому времени в счетчиках 25.1, 25.2, ..., 25.m будут содержаться значения интенсивностей для каждого модуля линейной системы, которые подаются на ответствующие выходы 41.1, 41.2, ..., 41.m, а они в свою очередь на ВУУ.

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

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

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