Устройство оценки качества размещения в системах с матричной организацией

Устройство оценки качества размещения в системах с матричной организацией

Иллюстрации

Показать все

Реферат

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

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

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

Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. СССР 1410949, кл. 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-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок оценки качества, содержащий генератор импульсов, первый и второй дешифратор выбора строки, первый и второй мультиплексор выбора элемента, первый и второй дешифратор выбора элемента, первый и второй дешифратор горизонтального модуля, первый и второй дешифратор вертикального модуля, первый и второй счетчик строк, первый и второй счетчик столбца, первый и второй счетчик горизонтального модуля, первый и второй счетчик вертикального модуля, счетчик текущего столбца, триггер режима, матрицу из (i.j) (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей, матрицу (i.j) (i=1, 2,..., m, j=1, 2,..., n) D-триггеров, первую матрицу из (i.j) элементов ИЛИ (i=1, 2,..., m, j=1, 2,..., n), вторую матрицу из (i.j) элементов (i=1, 2,..., m, j=1, 2,..., n) ИЛИ, первый, второй, третий и четвертый элементы И, первую, вторую, третью и четвертую матрицы из (i.j) элементов И, элемент И, причем вход запуска устройства подключен к генератору импульсов, выход которого подсоединен к первым входам первого, второго, третьего и четвертого элементов И и к первому входу элемента И, вторые входы первого и четвертого элементов И подсоединены к инверсному выходу триггера режима, прямой выход которого подключен ко вторым входам второго и третьего элементов И, выходы первого и четвертого элементов И подсоединены к соответствующим счетным входам первого и второго счетчиков горизонтального модуля, выходы второго и третьего элемента И подключены к соответствующим счетным входам первого и второго счетчиков вертикального модуля, входы сброса первого и второго счетчиков вертикального модуля подключены к входу сброса второго счетчика столбца и к счетному входу счетчика текущего столбца, выходы первого и второго счетчиков горизонтального модуля подключены к соответствующим входам первого и второго дешифратора горизонтального модуля, выходы первого и второго счетчиков вертикального модуля подсоединены к соответствующим входам первого и второго дешифратора вертикального модуля, j-й (j=1, 2,..., n) выход первого дешифратора горизонтального модуля соединен с соответствующими вторыми входами первой матрицы из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), j-й (j=1, 2,..., n) выход второго дешифратора горизонтального модуля подключен к соответствующим вторым входам второй матрицы из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), i-й (i=1, 2,..., m) выход первого дешифратора вертикального модуля соединен с соответствующими первыми входами третьей матрицы из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), i-й (i=1, 2,..., m) выход второго дешифратора вертикального модуля соединен с соответствующими первыми входами четвертой матрицы из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), счетный вход первого счетчика строк соединен с выходом переполнения первого счетчика столбца, счетный вход которого подключен к генератору импульсов, установочный вход первого счетчика столбца соединен с выходом первого счетчика строк, с входом первого дешифратора выбора строки и с управляющим входом первого дешифратора выбора элемента, выход первого счетчика столбца соединен с управляющим входом первого мультиплексора выбора элемента, выходы с первого по m-й первого дешифратора выбора строки соединены с соответствующими первыми входами первой матрицы из (i.j) элементов ИЛИ (i=1, 2,..., m, j=1, 2,..., n), выходы которых подсоединены к соответствующим разрешающим входам матрицы из (i.j) D-триггеров (i=1, 2,..., m, j=1, 2,..., n), D-входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы элементов однородной среды, j-е (j=1, 2,..., n) вторые входы первой матрицы из (i.j) элементов ИЛИ (i=1, 2,..., m, j=1, 2,..., n) соединены с входами с первого по n-й второго дешифратора выбора строки, выходы матрицы из (i.j) D-триггеров (i=1, 2,..., m, j=1, 2,..., n) подключены к соответствующим входам первого и второго мультиплексора выбора элемента, разрешающие входы первого мультиплексора выбора элемента и первого дешифратора выбора элемента подключены к инверсному выходу триггера режима, прямой выход которого подсоединен к разрешающим входам второго мультиплексора выбора элемента и второго дешифратора выбора элемента, а также ко второму входу элемента И, управляющий вход второго мультиплексора выбора элемента подсоединен к выходу второго счетчика столбца, управляющий вход второго дешифратора выбора элемента соединен с выходом счетчика текущего столбца, выход переполнения которого подключен к выходу переполнения устройства, вход второго дешифратора выбора строки соединен с выходом второго счетчика строки, счетный вход которого подключен к выходу элемента И и к счетному входу второго счетчика столбца, первый и второй мультиплексор выбора элемента соединены с соответствующим первым и вторым дешифратором выбора элемента, i-е (i=1, 2,..., m) выходы первого дешифратора выбора элемента подсоединены к первым входам первой и второй матриц из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), j-e (j=1, 2,..., n) выходы второго дешифратора выбора элемента подсоединены ко вторым входам третьей и четвертой матриц из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n), выходы первой, второй, третьей и четвертой матрицы из (i.j) элементов И (i=1, 2,..., m, j=1, 2,..., n) объединены с соответствующими входами второй матрицы из (i.j) элементов ИЛИ (i=1, 2,..., m, j=1, 2,..., n), выходы которой подключены к соответствующим счетным входам матрицы из (i.j) счетчиков (i=1, 2,..., m, j=1, 2,..., n) фиксированных модулей, выходы которой соединены с соответствующими (i.j)-ми выходами (i=1, 2,..., m, j=1, 2,..., n) матрицы из (i.j) выходов (i=1, 2,..., m, j=1, 2,..., n) значений интенсивности устройства, вход обнуления устройства подсоединен к R-входу триггера режима.

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

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

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

Исходная (размещаемая) задача (процесс, алгоритм) представляется в виде неориентированного невзвешенного графа G=<X,E>, вершины х_i∈Х которого соответствуют подзадачам (подалгоритмам), а дуги е_ij∈Е⊆Х×Х задают управляющие и/или информационные связи между подзадачами.

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

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

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

где

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

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

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

Сущность предлагаемого критерия поясняется фиг.2. Здесь на фиг.2а и 2б представлены варианты гипотетического размещения графа в МС, а на фиг.2в и 2г показаны соответствующие матрицы инцидентности. Модули МС на фиг.2а и 2б представлены квадратами, в левом верхнем углу которых представлены их номера. Внутри модулей кружками обозначены гипотетические назначенные (размещенные) вершины графа с соответствующими номерами внутри. Пунктирные линии обозначают связи модулей МС, а сплошные линии рядом с пунктирными - гипотетические зафиксированные дуги, инцидентные размещенным (назначенным) вершинам. Из фиг.2а видно, что интенсивность взаимодействия между модулями 1-2, 1-4, а также между модулями 7-8 наибольшая и равна трем. Качество размещения улучшается при варианте размещения, показанном на фиг.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 устройства, а также дополнительно введенный блок 33 оценки качества, содержащий генератор 14 импульсов, первый 15 и второй 16 дешифратор выбора строки, первый 17 и второй 18 мультиплексор выбора элемента, первый 19 и второй 20 дешифратор выбора элемента, первый 21 и второй 24 дешифратор горизонтального модуля, первый 22 и второй 23 дешифратор вертикального модуля, первый 25 и второй 26 счетчик строк, первый 27 и второй 28 счетчик столбца, первый 29 и второй 32 счетчик горизонтального модуля, первый 30 и второй 31 счетчик вертикального модуля, счетчик 49 текущего столбца, триггер 34 режима, матрицу 35.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей, матрицу 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров, первую 38.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицу элементов ИЛИ, вторую 39.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицу элементов ИЛИ, первый 40, второй 41, третий 42 и четвертый 43 элементы И, первую 44.i.j (i=1, 2,..., m, j=1, 2,..., n), вторую 45.i.j (i=1, 2,..., m, j=1, 2,..., n), третью 46.i.j (i=1, 2,..., m, j=1, 2,..., n) и четвертую 47.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов И, элемент 48 И, причем вход 36 запуска устройства подключен к генератору 14 импульсов, выход которого подсоединен к первым входам первого 40, второго 41, третьего 42 и четвертого 43 элементов И и к первому входу элемента 48 И, вторые входы первого 40 и четвертого 43 элементов И подсоединены к инверсному выходу триггера 34 режима, прямой выход которого подключен ко вторым входам второго 41 и третьего 42 элементов И, выходы первого 40 и четвертого 43 элементов И подсоединены к соответствующим счетным входам первого 29 и второго 32 счетчиков горизонтального модуля, выходы второго 41 и третьего 42 элемента И подключены к соответствующим счетным входам первого 30 и второго 31 счетчиков вертикального модуля, входы сброса первого 30 и второго 31 счетчиков вертикального модуля подключены к входу сброса второго 28 счетчика столбца и к счетному входу счетчика 49 текущего столбца, выходы первого 29 и второго 32 счетчиков горизонтального модуля подключены к соответствующим входам первого 21 и второго 24 дешифратора горизонтального модуля, выходы первого 30 и второго 31 счетчиков вертикального модуля подсоединены к соответствующим входам первого 22 и второго 23 дешифратора вертикального модуля, j-й (j=1, 2,..., n) выход первого 21 дешифратора горизонтального модуля соединен с соответствующими вторыми входами первой 44.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов И, j-й (j=1, 2,..., n) выход второго 24 дешифратора горизонтального модуля подключен к соответствующим вторым входам второй 45.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов И, i-й (i=1, 2,..., m) выход первого 22 дешифратора вертикального модуля соединен с соответствующими первыми входами третьей 46.i.j (i=1, 2,....m, j=1, 2,..., n) матрицы элементов И, i-й (i=1, 2,..., m) выход второго 23 дешифратора вертикального модуля соединен с соответствующими первыми входами четвертой 47.i.j (i=1, 2,....m, j=1, 2,..., n) матрицы элементов И, счетный вход первого 25 счетчика строк соединен с выходом переполнения первого 27 счетчика столбца, счетный вход которого подключен к генератору 14 импульсов, установочный вход первого 27 счетчика столбца соединен с выходом первого 25 счетчика строк, с входом первого 15 дешифратора выбора строки и с управляющим входом первого 19 дешифратора выбора элемента, выход первого 27 счетчика столбца соединен с управляющим входом первого 17 мультиплексора выбора элемента, выходы с первого по m-й первого 15 дешифратора выбора строки соединены с соответствующими первыми входами первой 38.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов ИЛИ, выходы которых подсоединены к соответствующим разрешающим входам матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров, D-входы которых подключены к индикаторным выходам соответствующих элементов с первого по n-й столбцов матрицы 1 элементов однородной среды, j-е (j=1, 2,..., n) вторые входы первой 38.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов ИЛИ соединены с входами с первого по n-й второго 16 дешифратора выбора строки, выходы матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров подключены к соответствующим входам первого 17 и второго 18 мультиплексора выбора элемента, разрешающие входы первого 17 мультиплексора выбора элемента и первого 19 дешифратора выбора элемента подключены к инверсному выходу триггера 34 режима, прямой выход которого подсоединен к разрешающим входам второго 18 мультиплексора выбора элемента и второго 20 дешифратора выбора элемента, а также ко второму входу элемента 48 И, управляющий вход второго 18 мультиплексора выбора элемента подсоединен к выходу второго 28 счетчика столбца, управляющий вход второго 20 дешифратора выбора элемента соединен с выходом счетчика 49 текущего столбца, выход переполнения которого подключен к выходу 52 переполнения устройства, вход второго 16 дешифратора выбора строки соединен с выходом второго 26 счетчика строки, счетный вход которого подключен к выходу элемента 48 И и к счетному входу второго 28 счетчика столбца, первый 17 и второй 18 мультиплексор выбора элемента соединены с соответствующим первым 19 и вторым 20 дешифратором выбора элемента, i-е (i=1, 2,..., m) выходы первого 19 дешифратора выбора элемента подсоединены к первым входам первой 44.i.j (i=1, 2,..., m, j=1, 2,..., n) и второй 45.i.j (i=1, 2,..., m, j=1, 2,..., n) матриц элементов И, j-е (j=1, 2,..., n) выходы второго 20 дешифратора выбора элемента подсоединены ко вторым входам третьей 46.i.j (i=1, 2,..., m, j=1, 2,..., n) и четвертой 47.i.j (i=1,2..., m, j=1, 2,..., n) матриц элементов И, выходы первой 44.i.j (i=1, 2,..., m, j=1, 2,..., n), второй 45.i.j (i=1, 2,..., m, j=1, 2,..., n), третьей 46.i.j (i=1, 2,..., m, j=1, 2,..., n) и четвертой 47.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов И объединены с соответствующими входами второй 39.i.j (i=1, 2,....m, j=1, 2,..., n) матрицы элементов ИЛИ, выходы которой подключены к соответствующим счетным входам матрицы 35.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей, выходы которой соединены с соответствующими (i.j)-ми выходами (i=1, 2,..., m, j=1, 2,..., n) матрицы 51.i.j (i=1, 2,..., m, j=1, 2,..., n) выходов значений интенсивности устройства, вход 50 обнуления устройства подсоединен к R-входу триггера 34 режима.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый 15 и второй 16 дешифраторы выбора строки предназначены для выбора строки матрицы 1 (матрицы инцидентности размещаемого графа).

Первый 17 и второй 18 мультиплексоры выбора элемента предназначены для подачи с выходов матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров информации о назначенной (размещенной) вершине в (i.j)-м модуле МС.

Первый 19 и второй 20 дешифраторы выбора элемента служит для выдачи информации о размещенной вершине графа G в (i.j)-м модуле (i=1, 2,..., m, j=1, 2,..., n) MC.

Первый 21 и второй 24 дешифраторы горизонтального модуля предназначены для выбора двух вершин, инцидентных зафиксированной в i-й (i=1, 2,..., m) строке МС.

Первый 22 и второй 23 дешифратор вертикального модуля предназначены для выбора двух вершин, инцидентных зафиксированной в j-м (j=1, 2,..., n) столбце МС.

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

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

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

Первый 30 и второй 31 счетчик вертикального модуля необходим для подсчета вершин графа, вертикально зафиксированных в МС.

Счетчик 49 текущего столбца служит для хранения информации о текущем анализируемом столбце матрицы инцидентности.

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

Триггер 34 режима необходим для выбора режима работы блока 33. В нулевом состоянии происходит просмотр горизонтально зафиксированных дуг графа G. В единичном состоянии осуществляется просмотр вертикально зафиксированных дуг графа G.

Матрица 35.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей необходима для хранения информации о зафиксированных вершинах графа G.

Матрица 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров служит для хранения информации о текущем варианте размещения (матрицы инцидентности).

Первая 38.i.j (i=1, 2,..., m, j=1, 2,..., n) матрица элементов ИЛИ необходима для объединения сигналов с выходов первого 15 и второго 16 дешифратора выбора строки с последующей подачей на соответствующие разрешающие входы триггеров матрица 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров.

Вторая 39.i.j (i=1, 2,..., m, j=1, 2,..., n) матрица элементов ИЛИ служит для объединения сигналов с выходов первой 44.i.j (i=1, 2,..., m, j=1, 2,..., n), второй 45.i.j (i=1, 2,..., m, j=1, 2,..., n), третьей 46.i.j (i=1, 2,..., m, j=1, 2,..., n) и четвертой 47.i.j (i=1, 2,..., m, j=1, 2,..., n) матриц элементов И соответственно с последующей их подачей на соответствующие счетные входы матрицы 35.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей.

Первый 40, второй 41, третий 42 и четвертый 43 элементы И необходимы для блокировки поступления импульсов с выхода генератора 14 импульсов.

Первая 44.i.j (i=1, 2,..., m, j=1, 2,..., n), вторая 45.i.j (i=1, 2,..., m, j=1, 2,..., n), третья 46.i.j (i=1, 2,....m, j=1, 2,..., n) и четвертая 47.i.j (i=1, 2,....m, j=1, 2,..., n) матрицы элементов И необходимы для блокировки поступления сигналов с выходов первого 19 и второго 20 дешифраторов выбора элемента.

Элемент 48 И служит для блокировки поступления импульса с выхода генератора 14 импульсов.

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

Вход 50 обнуления служит для подачи от ВУУ сигнала, устанавливающего триггер 34 режима в нулевое состояние.

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

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

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

Первоначально в матрице 1 элементов однородной среды содержится вариант размещения, соответствующий матрице инцидентности графа Н МС. Все триггеры в блоке 5 памяти находятся в состоянии логического нуля. Триггеры матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров находится в состоянии, соответствующим матрице инцидентности W. Триггер 34 режима находится в состоянии логического нуля. Поэтому на прямом его выходе присутствует нулевой сигнал, который поступает на второй вход элемента 48 И, и запрещает прохождение сигналов на его выход. Тот же нулевой сигнал с прямого выхода триггера 34 подается на вторые входы второго 41 и третьего 42 элемента И, и также запрещает прохождение сигналов на их выходы. Нулевой сигнал с прямого выхода триггера 34 поступает на разрешающие входы второго 20 дешифратора и второго 18 мультиплексора выбора элемента и запрещает прохождение сигналов на их выходы. На инверсном выходе триггера 34 присутствует единичный сигнал, который подается на разрешающие входы первого 17 мультиплексора и второго 19 дешифратора, разрешая их работу. Единичный сигнал с инверсного выхода триггера 34 подается на входы первого 40 и четвертого 43 элемента И, и разрешает прохождение импульсов с выхода генератора 14 импульсов. Во втором 26 счетчике строк содержится код нудя («00...00»). В счетчике 27 содержится значение, соответствующее коду единицы («00...01»). В счетчике 28 содержится код, соответствующий значению единицы. В первом счетчике 25 строк содержится код значения один («00...01»). Код единицы с выхода счетчика 25 поступает на вход дешифратора 15 и на установочный вход первого 27 счетчика столбца, устанавливая в нем значение, равное единице. На первом выходе дешифратора 15 выбора строки появляется единичный сигнал, который подается через первые входы элементов 38.1.j (j=1, 2,..., n) ИЛИ на разрешающие входы триггеров 37.1. j (j=1, 2,..., n) матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров (выбирается первая строка матрицы 1). В результате на соответствующих выходах 37.1. j (j=1, 2,..., n) D-триггеров появляются единичные импульсы, которые поступают на соответствующие импульсы, которые поступают на соответствующие входы первого 17 мультиплексора выбора элемента. В счетчиках 29 и 30 содержаться коды, соответствующие значению нуля («00...00), в счетчиках 31 и 32 содержаться коды числа один («00...01»). В счетчиках матрицы 35.i.j (i=1, 2,..., m, j=1, 2,..., n) счетчиков фиксированных модулей содержаться коды нулей («00...00»). В счетчике 49 текущего столбца содержится код единицы.

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

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

Задача оценки качества размещения в системах с матричной организацией решается следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Эти сигналы через элементы 38.i.j (i=1, 2,....m, j=1, 2,..., n) ИЛИ первой 38.i.j (i=1, 2,..., m, j=1, 2,..., n) матрицы элементов ИЛИ поступают на входы 35.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров. В результате в них устанавливаются коды, соответствующие матрице инцидентности графа Н МС. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 33 оценки качества.

Работа блока 33 оценки качества подразделяется на два этапа. На первом этапе происходит просмотр горизонтально зафиксированных дуг и инцидентных им вершин в модулях МС. Например, на фиг.2б это модули 1-2, 2-3, 4-5, 5-6, 7-8 и 8-9. После анализа горизонтально фиксированных дуг происходит анализ вертикально зафиксированных дуг и соответствующих инцидентных им вершин. На фиг.2б это дуги, зафиксированные в модулях 1-4, 4-7, 2-5, 5-8, 3-6 и 6-9. Анализ происходит на основе просмотра соответствующей матрицы инцидентности Н (например, представленной на фиг.2г).

Импульс с выхода генератора 14 импульсов поступает на первый вход элемента 48 И, но так как на его втором входе присутствует нулевой сигнал с прямого выхода триггера 34, на выходе единичный импульс не появляется. Единичный сигнал с выхода генератора 14 импульсов также поступает на счетный вход счетчика 27 и по переднему фронту увеличивает содержимое счетчика 27 до кода двойки («00...010»). Тот же импульс с генератора 14 импульсов поступает на первые входы элементов 40, 41, 42 и 43 И. Так как на втором входе элементов 40 и 43 И присутствует единичный потенциал с инверсного выхода триггера 34, то их выходах появляется единичный импульс, который поступает на счетные входы счетчиков 29 и 32 соответственно. По переднему фронту коды, хранящиеся в них коды увеличиваются на единицу до кодов чисел один («00...01») и два («00...010») соответственно. Коды соответствующих чисел подаются на входы дешифраторов 21 и 24 соответственно. В результате на первом выходе дешифратора 21 и на втором выходе дешифратора 24 возбуждается единичные импульсы, которые поступают на вторые входы элементов 44.i.1 (i=1, 2,..., m) и 45. i.2 (i=1, 2,..., n) И соответственно.

Код числа два с выхода счетчика 27 поступает на управляющий вход мультиплексора 17 и разрешает прохождение единичного сигнала с выхода триггера 37.1.2 на его выход. Так как на разрешающих входах мультиплексора 17 и дешифратора 19 присутствует единичный сигнал, а на управляющем входе дешифратора 19 присутствует код единицы с выхода счетчика 25, то на первом выходе дешифратора 19 появляется единичный сигнал, который подается на соответствующие первые входы элементов 44.1.j (j=1, 2,..., n) и 45.1.j (j=1, 2,..., n) И. Так как на их вторых входах присутствует единичный потенциал, то на выходах элементов 44.1.1 и 45.1.2 И возбуждаются единичные импульсы, которые проходят через элементы 39.1.1 и 39.1.2 ИЛИ и поступают на счетные входы счетчиков 35.1.1 и 35.1.2. В результате хранящиеся в них коды по заднему фронту увеличиваются на единицу до кодов числа один («00...01»).

Очередной тактовый импульс с выхода генератора 14 импульсов подается на первые входы элементов 40, 41, 42 и 43 И, а также на счетный вход счетчика 27, увеличивая его содержимое по переднему фронту на единицу до кода тройки («00...011»). На вторых входах элементов 41 и 42 И присутствует нулевой потенциал с прямого выхода триггера 34. Из-за этого на их выходах не появляется единичный сигнал. На вторых входах элементов 40 и 43 И присутствует единичный сигнал с инверсного выхода триггер 34. Поэтому, на их выходах появляется единичный импульс, который поступает на соответствующие счетные входы счетчиков 29 и 32, которые по переднему фронту увеличивает их содержимое на единицу. В результате в счетчике 29 устанавливаются код двойки («00...010»), а в счетчике 32 - код тройки («00...011»). Соответствующие коды попадают на входы дешифраторов 21 и 24. В результате на втором выходе дешифратора 21 появляется единичный потенциал, который поступает на вторые входы элементов 44.i.2 (i=1, 2,..., m), а на третьем выходе дешифратора 24 также появляется единичный сигнал, который подается на вторые входы элементов 45.i.3 (i=1, 2,..., m). На первых входах элементов 44.1.j (j=1, 2,..., n) и 45.1.j (j=1, 2,..., n) И присутствует единичный потенциал с первого выхода дешифратора 19. В результате на выходах элементов 44.1.2 и 44.1.3 появляются единичные сигналы, которые подаются на счетные входы счетчиков 35.1.2 и 35.1.3, которые по заднему фронту увеличивает их содержимое на единицу. В результате в счетчике 35.1.2 устанавливается код двойки, а счетчике 35.1.3 - код единицы.

Очередной тактовый импульс по переднему фронту вызывает сигнал переполнения в счетчиках 27, 29 и 32. Содержимое счетчиков 29 и 32 устанавливается в начальное состояние, то есть в коды нуля («00...00») в счетчике 29 и единицы («00...010») в счетчике 32. Сигнал переполнения с выхода переполнения счетчика 27 попадает на счетный вход счетчика 25 и по переднему фронту увеличивает его содержимое до кода двойки («00...010»). Код числа два с выхода счетчика 25 поступает на вход дешифратора 15 и на установочный вход счетчика 27, устанавливая в нем начальное состояние числа два. Так как на входе дешифратора 15 появляется код числа два, то на втором его выходе возбуждается единичный сигнал, который поступает на первые входы элементов 38.2.j (j=1, 2,..., n) ИЛИ и далее на разрешающие входы 37.2.j (j=1, 2,..., n) матрицы 37.i.j (i=1, 2,..., m, j=1, 2,..., n) D-триггеров (выбирается вторая строка матрицы 1). В результате на соответствующих выходах появляются сигналы, которые поступают на соответствующие входы мультиплексора 17. На разрешающих входах мультиплексора 17 и дешифратора 19 присутствует единичный потенциал с инверсного выхода триггера 34.

Очередной тактовый импульс с выхода генератора 14 импульсов поступает на первые входы элементов 40, 41, 42, 43 и 48 И, на счетный вход счетчика 27 и по переднему фронту увеличивает его содержимое до кода тройки («00...011»). Код числа три с выхода счетчика 27 подается на управляющий вход мультиплексора 17 и пропускает единичный сигнал с выхода триггера 37.2.3 на вход дешифратора 19, Так как на управляющем его входе присутствует код двойки с выхода счетчика 25, то на втором выходе дешифратора 19 возбуждается единичный сигнал, который поступает на первые входы элементов 44.2.j (i=1, 2,..., n) И и элементов 45.2.j (j=1, 2,..., n) И. Единичный сигнал с выхода элементов 40 и 43 И поступает на счетные входы счетчиков 29 и 32, и по переднему фронту увеличивает их содержимое до кодов единицы в счетчике 29 и двойки в счетчике 32. Соответствующие коды проходят на входы дешифраторов 21 и 24 соответственно. В результате на первом выходе дешифратора 21 и на втором выходе дешифратора 24 возбуждаются единичные импульсы, которые поступают на вторые входы элементов 44.i.1 (i=1, 2,..., m) И, и 45.i.2 (i=1, 2,..., m) И. В результате на выходах элементов 44.2.1 и 44.2.2 И появляются единичные импульсы, которые проходят через элементы 39.2.1 и 39.2.2 ИЛИ соответственно, после чего попадают на счетные входы счетчиков 35.2.1 и 35.2.2. В результате по заднему фронту их содержимое увеличивает на единицу.

Так продолжается до тех пор, пока не будут просмотрены все горизонтально зафиксированные дуги МС. Об этом говорит сигнал переполнения, который появляется на выходе переполнения счетчика 25, который подается на