Устройство для оценки линейного размещения элементов

 

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

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

Известно устройство, предназначенное для моделирования комбинаторных задач проектирования РЭА и АСУ, обеспечивающее возможность оценки текущего размещения при изоморфных преобразованиях (см. а.с. СССР N 1291957, МКИ G 06 F 7/00, 1984). Известное устройство представляет собой полноматричную одномерную среду, каждая ячейка которой содержит блок оценки размещения. Недостатком этого устройства является то, что оно не реализует оценку текущего размещения по какому-либо критерию.

Известно также устройство для оценки размещения, содержащее полноматричную двухмерную однородную среду, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, шину записи матрицы инцидентности исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, первый и второй выходы оценки текущего размещения, информационный выход, вход установки и соответствующие связи между ними (см. а.с. СССР N 1430949, G 06 F 7/00, 15/20, 1987). Недостатками данного устройства являются высокая сложность, обусловленная значительной сложностью блоков подсчета единиц и однородной среды, низкое среднее быстродействие, обусловленное зависимостью времени оценки от конкретного варианта размещения и текущего состояния однородной среды, а также отсутствие возможности подсчета критерия загруженности рабочего поля размещения.

Наиболее близким по технической сущности к предлагаемому изобретению является устройство для оценки линейного размещения элементов (Патент РФ N 2024058, кл. G 06 F 15/419, 1994). Это устройство содержит блок памяти, m идентичных блоков подсчета длины цепи, где m - число цепей, многовходовой сумматор, блок нахождения максимума, вход установки, шину записи матрицы инцидентности исходного гиперграфа, шину адреса, вход сброса, вход синхронизации, вход окончания перестановки, выходы оценки текущего размещения, связанные с выходами блока нахождения максимума и сумматора соответственно, а также соответствующие связи.

Недостатком этого устройства является отсутствие возможности подсчета критерия загруженности рабочего поля размещения.

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

Технический результат достигается тем, что в устройство, содержащее блок памяти, m идентичных блоков подсчета длины цепи, блок нахождения максимума, вход установки, шину записи матрицы инцидентности исходного гиперграфа, шину адреса, вход сброса, вход синхронизации, вход окончания перестановки, первый и второй выходы оценки текущего размещения, причем вход установки соединен со входом управления записью/считыванием блока памяти, шина записи матрицы инцидентности исходного гиперграфа подключена к информационным входам блока памяти, адресные входы которого подключены к шине адреса, к соответствующим входам каждого блока подсчета длины цепи (БПДЦ) подсоединены входы сброса, синхронизации и окончания перестановки, при этом i-й выход блока памяти (i = 1,...,m) подключен к информационному входу i-го БПДЦ, выход которого соединен с i-м информационным входом блока нахождения максимума (БНМ), а выход последнего является первым выходом оценки текущего размещения, введены m идентичных блоков распознавания загрузки (БРЗ), блок подсчета числа единиц (БПЧЕ), сумматор, блок выделения максимума (БВМ), элемент И, вход инициализации, третий выход оценки текущего размещения и выход окончания оценки текущего размещения, причем i-й выход блока памяти подключен к информационному входу i-го БРЗ, к соответствующим управляющим входам каждого БРЗ подсоединены входы сброса, окончания перестановки, инициализации и выход окончания оценки текущего размещения, информационные выходы БРЗ подключены ко входам БПЧЕ, сигнальные же выходы БРЗ подключены ко входам элемента И, выход которого является выходом окончания оценки текущего размещения, выход БПЧЕ соединен с информационными входами сумматора и БВМ, соответствующие управляющие входы которых соединены со входами сброса, синхронизации, окончания перестановки и выходом окончания оценки текущего размещения, при этом выходы сумматора и БВМ являются соответственно вторым и третьим выходами оценки текущего размещения. Каждый БРЗ содержит триггер, первый, второй, третий и четвертый элементы И, счетчик и регистр, причем вход установки триггера в единичное состояние соединен с первыми входами первого и второго элементов И и является информационным входом БРЗ, вторые входы всех элементов И соединены между собой и являются входом инициализации БРЗ, первый вход третьего элемента И является входом признака окончания оценки текущего размещения, первый же вход четвертого элемента И соединен с первым входом установки триггера в нулевое состояние и является входом признака окончания перестановки, вход установки счетчика в нулевое состояние является входом сброса БРЗ, выход триггера является информационным выходом БРЗ, а его сигнальным выходом является выход окончания счета счетчика, соединенный со вторым входом установки триггера в нулевое состояние, при этом вход прямого счета счетчика соединен с выходом первого элемента И, выход второго элемента И соединен со входом обратного счета счетчика, вход параллельной загрузки которого соединен с выходом третьего элемента И, информационные же входы счетчика соединены с соответствующими выходами регистра, информационные входы которого соединены с соответствующими информационными выходами счетчика, вход параллельной загрузки регистра соединен с выходом четвертого элемента И.

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

Наличие отличительных признаков обуславливает соответствие заявляемого технического решения критерию новизны.

Заявляемое техническое решение соответствует также и критерию "существенные отличия", т.к. не обнаружено решений с признаками, отличающими заявляемое техническое решение от прототипа.

Возможность достижения технического результата изобретения обусловлена следующими предпосылками. Пусть задана некоторая схема C=(M,N), содержащая множество М= {m₁, m₂,..., m_n} элементов, соединенных между собой посредством множества N= {n₁,n₂,...,n_m} цепей. Пусть задано также одномерное дискретное регулярное рабочее поле S, состоящее из множества позиций P={p₁,p₂,...,p_n}, центры которых отстоят друг от друга на единичный интервал длины. Положим, что всякий элемент m_k, где k = 1,...,n, может быть размещен в любой позиции p_j, где j= 1,...,n, без ограничений на размещение других элементов (т.е. без взаимного наложения других элементов). Тогда задачу линейного размещения элементов можно сформулировать как задачу отыскания варианта размещения элементов схемы из множества М на позициях множества P рабочего поля, для которого некоторая целевая функция принимает оптимальное значение. На практике при расчете целевой функции кроме суммарной длины цепей и наибольшей длины цепи, т.е. критериев, используемых в прототипе, широко используется также и критерий загруженности рабочего поля размещения. Наиболее часто данный критерий применяется при размещении элементов коммутации объединительных плат, элементов матричных БИС, логических матриц т.д. Для рассматриваемого случая линейного размещения элементов под загруженностью рабочего поля мы будем понимать максимальное число цепей, имеющихся между какими-либо соседними для данного варианта размещения элементами.

Рассмотрим формальное определение загруженности, полагая, что всякий вариант линейного размещения может быть представлен в следующем виде: π_r= (m_r1,m_r2,...,m_rn) или π_r= (r₁,r₂,...,r_n). Пусть N(T) ⊂ N есть подмножество цепей, инцидентных элементам из подмножества Т = {m_rl, m_r2,...m_rt}, а ω(r₁,r₂,...,r_t) есть общее число цепей, имеющихся между элементами подмножества Т и всеми остальными элементами, принадлежащими подмножеству М\Т. Тогда Если рассматривать перестановку π_r, то ω (r₁,r₂,...,r_t) представляет собой число цепей, имеющихся между элементами m_rt из подмножества Т и m_rt+1 из подмножества М\ Т, которое мы будем называть локальной загруженностью. Загруженность же всего рабочего поля определяется следующим образом: (1) Для определения загруженности рабочего поля может быть использована гиперграфовая математическая модель схемы и соответствующая матричная модель рабочего поля. Гиперграф H = (V,E) представляет собой совокупность множества V = { v₁, v₂, ...,V_n} вершин и множества E = {e₁,e₂,...,e_n} ребер. Для его задания будем использовать матрицу инцидентности где l = 1,... , m, k = 1,...,n, для которой: Каждому элементу m_k схемы ставится во взаимно однозначное соответствие вершина _k гиперграфа, а всякой цепи n₁ схемы - ребро e₁ гиперграфа. При этом, если некоторый контакт элемента m_k принадлежит некоторой цепи n₁, то соответствующая вершина v_k гиперграфа считается инцидентной ребру e₁. Заметим, что здесь мы не учитываем реальных размеров элементов, а стягиваем их в точки - вершины гиперграфа.

Пример матрицы инцидентности A(π_r)_8×6, π_r= (1,2,3,4,5,6) приведен на фиг. 5. Для моделирования рабочего поля S используется то же матричное представление гиперграфа, что оказывается возможным ввиду одномерности, дискретности и регулярности рабочего поля для рассматриваемого случая. При этом удобным оказывается использование так называемых интервальных диаграмм (см. Абрайтис Л. Б. Автоматизация проектирования топологии цифровых интегральных микросхем. -М.: Радио и связь, 1985. - 200 с., с. 92). Если взять m горизонтальных интервалов, соответствующих m строкам матрицы инцидентности, и разместить в них цепи в порядке их расположения в матрице, то будет сформирована соответствующая интервальная диаграмма. Пример интервальной диаграммы для матрицы A(π_r)_8×6, π_r= (1,2,3,4,5,6), приведенной на фиг. 5, показан на фиг. 6. Здесь же даются все значения локальной загруженности и значение загруженности всего рабочего поля размещения. Так как локальная загруженность каждого межэлементного промежутка определяется как суммарное число пересекающих его цепей, можно записать (2) где
Тогда загруженность всего рабочего поля определяется так
(3)
С учетом вышеизложенного алгоритм определения загруженности рабочего поля на основе матрицы инцидентности может быть сформулирован следующим образом:
1. Выполнить п. 2 - 4 для каждого t= {l,2,.., n-1}.

2. Выполнить п. 3 для каждой цепи h= {1,2,...,m}.

3. Вычислить ω_h(r₁,r₂,...,r_t).
4. Вычислить
5. Определить
6. Конец.

Таким образом, наличие алгоритма определения загруженности рабочего поля подтверждает возможность достижения технического результата предлагаемым устройством. Кроме того, можно показать, что критерий суммарной длины цепей L_Σ(π_r) может быть рассчитан как сумма значений локальной загруженности. Это обусловлено тем, что используется одномерное регулярное дискретное рабочее поле размещения с постоянным шагом. При этом величина ω(r₁,r₂,...,r_t) представляет собой суммарную длину цепей в интервале между позициями t и t+1. Поэтому
(4)
или иначе
(5)
В предлагаемом устройстве используется именно такой способ расчета суммарной длины цепей.

Предлагаемое изобретение поясняется прилагаемыми фигурами, где на фиг.1 приведена структурная схема устройства, на фиг. 2 - функциональная схема блока распознавания загрузки, на фиг. 3 и 4 - временные диаграммы работы устройства в режимах инициализации и оценки размещения соответственно, на фиг. 5 показан пример матрицы инцидентности A(π_r)_8×6, π_r= (1,2,3,4,5,6), а на фиг. 6 приведена соответствующая ей интервальная диаграмма, на фиг. 7 приведен пример матрицы инцидентности A(π_r)_8×6, для перестановки π_r= (2,1,3,6,5,4), на фиг. 8 показано размещение матрицы инцидентности A_8X6 в блоке памяти устройства, на фиг. 9 и 10 приведены примеры разрядно-последовательного представления матрицы инцидентности A(π_r)_8×6 для перестановок π_r= (1,2,3,4,5,6) и π_r= (2,1,3,6,5,4) соответственно.

Устройство содержит блок 1 памяти, m идентичных блоков 2 подсчета длины цепи, блок 3 нахождения максимума, m идентичных блоков 4 распознавания загрузки, блок 5 подсчета числа единиц, сумматор 6, блок 7 выделения максимума, элемент И 8, вход 9 установки, шину 10 записи матрицы инцидентности исходного гиперграфа, шину 11 адреса, вход 12 сброса, вход 13 синхронизации, вход 14 окончания перестановки, вход 15 инициализации, первый 16, второй 17 и третий 18 выходы оценки текущего размещения, а также выход 19 окончания оценки текущего размещения. Причем вход 9 установки соединен со входом управления записью/считывания блока 1 памяти, шина 10 записи матрицы инцидентности соединена с информационными входами блока 1 памяти, адресные входы которого соединены с шиной 11 адреса, к соответствующим управляющим входам каждого БПДЦ 2 присоединены входы 12 сброса, 13 синхронизации и 14 окончания перестановки, а к соответствующим управляющим входам каждого БРЗ 4 присоединены входы 12 сброса, 14 окончания перестановки, 15 инициализации и выход 19 окончания оценки текущего размещения, при этом i-й выход блока 1 памяти (i= 1,..., m) соединен с информационными входами i-го БПДЦ 2 и i-го БРЗ 4, выход же i-го БПДЦ 2 соединен с i-м информационным входом блока 3, а информационный выход i-го БРЗ 4 соединен с i-м входом БПЧЕ 5, сигнальный же выход i-го БРЗ 4 соединен с соответствующим входом элемента И 8, к выходу БПЧЕ 5 подключены информационные входы сумматора 6 и блока 7, соответствующие управляющие входы которых соединены со входом 12 сброса, 13 синхронизации, 14 окончания перестановки и выходом 19 окончания оценки текущего размещения. Выходы блока 3 нахождения максимума, сумматора 6 и блока 7 выделения максимума являются соответственно первым 16, вторым 17 и третьим 18 выходами оценки текущего размещения, выход элемента И 8 является выходом 19 окончания оценки текущего размещения.

Каждый БРЗ 4 (фиг. 2) содержит триггер 20, первый 21, второй 22, третий 23 и четвертый 24 элементы И, счетчик 25 и регистр 26, причем вход установки триггера 20 в единичное состояние соединен с первыми входами первого 21 и второго 22 элементов И и является информационным входом БРЗ 4, вторые входы всех элементов И соединены между собой и являются входом инициализации БРЗ 4, первый вход третьего элемента И 23 является входом признака окончания оценки текущего размещения, первый же вход четвертого элемента И 24 соединен с первым входом установки в нулевое состояние триггера 20 и является входом признака окончания перестановки, вход установки в нулевое состояние счетчика 25 является входом сброса БРЗ 4, выход триггера 20 является информационным выходом БРЗ 4, а его сигнальным выходом является выход окончания счета счетчика 25, соединенный со вторым входом установки триггера 20 в нулевое состояние. При этом вход прямого счета счетчика 25 соединен с выходом элемента И 21, выход элемента И 22 соединен со входом обратного счета счетчика 25, вход параллельной загрузки которого соединен с выходом элемента И 23, информационные же входы счетчика 25 соединены с соответствующими выходами регистра 26, информационные входы которого соединены с соответствующими информационными выходами счетчика 25, а вход параллельной загрузки регистра 26 соединен с выходом элемента И 24.

Рассмотрим принцип действия и динамику работы устройства. Исходная матрица инцидентности размещается в блоке памяти таким образом, что обеспечивается параллельный доступ ко всем элементам некоторого столбца матрицы, являющегося разрядным срезом (см. фиг. 8). С учетом того, что цепи схемы, соответствующие строкам матрицы инцидентности, выступают в качестве подлежащих обработке слов данных (например, при подсчете длины цепи), такую структуру можно рассматривать как разрядно-последовательную пословно-параллельную. При этом каждый элемент матрицы представлен одним битом. В качестве блока памяти используется обычное ОЗУ с произвольной выборкой, включающее дешифратор адреса (см. фиг. 8).

В целях упрощения изложения положим, что столбцы матрицы размещаются в блоке памяти, начиная с нулевого адреса в порядке возрастания их номеров. Варианты размещения аналогично прототипу формируются вне устройства. При этом для задания вариантов размещения принята следующая форма: последовательность двоичных кодов, где численное значение любого кода взаимно однозначно соответствует номеру элемента, а порядковый номер данного кода в последовательности - номеру позиции, в которую размещается данный элемент. Поскольку в вычислительной технике используются значения, включая нулевое, то примем, что значение кода в последовательности равно уменьшенному на единицу номеру соответствующего элемента. Если такую последовательность кодов (вариант размещения) подать на адресные входы блока памяти, то на выходах последнего будет сформировано соответствующее разрядно-последовательное представление матрицы. На фиг. 9 и 10 приведены примеры разрядно-последовательного представления матрицы инцидентности A(π_r)_8×6 для перестановок π_r= (1,2,3,4,5,6) и π_r= (2,1,3,6,5,4) соответственно (фактически на адресные входы блока памяти поступают двоичные эквиваленты перестановок, в данном случае (000,001,010,011,100,101) и (001,000,010,101,100,011)). При этом поступление каждого кода последовательности и, соответственно, считывание каждого разрядного среза синхронизируется импульсами CLK, поступающими на вход 13 синхронизации. Подчеркнем, что в процессе формирования разрядно-последовательного представления матрицы независимо от перестановки не происходит физического преобразования матрицы в блоке памяти.

Перед началом работы блок 1 памяти устанавливается по входу 9 в режим записи и через шину 10 записи в него загружается матрица инцидентности исходного гиперграфа. После окончания загрузки матрицы блок 1 памяти по входу 5 переводится в режим чтения. Теперь путем подачи на вход 15 инициализации низкого уровня (логического нуля) устройство переводится в режим инициализации. В процессе инициализации формируются исходные данные, необходимые для основного рабочего режима, а именно определяется разветвленность C_h каждой цепи, представляющая собой число инцидентных данной цепи элементов. Таким образом, разветвленность h-й цепи может быть найдена как число единичных элементов в соответствующей строке матрицы инцидентности, т.е.

Определение разветвленности для всех цепей осуществляется одинаково с помощью блоков 4₁...4_m распознавания загрузки (см. фиг. 2) следующим образом. Единичным импульсом на входе 12 сброса обнуляется счетчик 25, а низкий уровень на входе 15 инициализации разрешает счетчику 25 только прямой счет, а регистру 26 - параллельную загрузку. При подаче на адресную шину 11 блока 1 памяти произвольной кодовой последовательности, содержащей адреса всех элементов без повторений (для простоты положим, что π_r= (1,2,3,4,5,6)), на выходе блока 1 памяти будет формироваться соответствующее разрядно-последовательное представление матрицы инцидентности. При этом разрядно-последовательное представление h-й цепи будет иметься на информационном входе соответствующего БРЗ. Все единичные импульсы, соответствующие единичным элементам h-й строки, будут подсчитываться счетчиком 25 и по приходу сигнала окончания перестановки на вход 14 счетчик 25 будет содержать значение C_h. Данный процесс наглядно представлен диаграммами, приведенными на фиг. 3, где в качестве примера используется первая строка матрицы A(π_r)_8×6, приведенной на фиг. 5, для перестановки π_r= (1,2,3,4,5,6). В данном примере С₁ = 3 и именно таковым является содержимое счетчика 25 по приходу сигнала на вход 14 окончания перестановки. По этому сигналу производится запись содержимого счетчика 25 в регистр 26 и, таким образом, в этом регистре сохраняется значение разветвленности соответствующей цепи. По этому же сигналу триггер 20 устанавливается в нулевое состояние. На этом процесс инициализации заканчивается. При этом в регистре h-го БРЗ будет содержаться значение разветвленности h-й цепи, а на информационных и сигнальных выходах всех БРЗ будет низкий уровень.

Основной рабочий режим, т. е. режим оценки размещения, активизируется единичным уровнем на входе 15 инициализации. При этом для счетчика 25 разрешаются обратный счет и параллельная загрузка, а параллельная загрузка регистра 26 блокируется элементом И 24. После этого устройство готово к приему на адресную шину 11 кодовой последовательности, соответствующей оцениваемому варианту размещения. Формирование разрядно-последовательного представления матрицы инцидентности для данного варианта размещения происходит так же, как и в режиме инициализации. Определение загруженности рабочего поля происходит следующим образом. До прихода на информационный вход БРЗ первого единичного сигнала его состояние не изменяется, а на информационном и сигнальном выходах БРЗ поддерживается низкий уровень (см. фиг. 4). По приходу на информационный вход БРЗ первого единичного сигнала он, поступая на вход установки в единичное состояние триггера 20, устанавливает его в единичное состояние. Этот же сигнал поступает на вход обратного счета счетчика 25 и уменьшает его содержимое на единицу. Аналогично процесс обработки повторяется при поступлении на информационный вход БРЗ очередного единичного сигнала за тем лишь исключением, что состояние триггера 20 уже не изменяется. При поступлении на информационный вход БРЗ последнего единичного сигнала, а для h-го БРЗ таких сигналов будет C_h, содержимое счетчика 25, уменьшаясь на единицу, становится равным нулю. При этом на его выходе окончания счета формируется единичный уровень, который, поступая на второй вход установки триггера 20 в нулевое состояние, устанавливает его в это состояние (см. фиг. 4), что соответствует окончанию обработки данной цепи. Одновременно единичный уровень с сигнального выхода БРЗ поступает на соответствующий вход элемента И 8, который срабатывает по окончании обработки всех цепей (для показанного на фиг. 4 случая все цепи оканчиваются по синхроимпульсу CLK5). На выходе элемента И 8 формируется единичный уровень, свидетельствующий об окончании оценки текущего размещения, который появляется и на входах признака окончания оценки текущего размещения всех БРЗ. Этот же единичный уровень поступает через элемент И 23 на вход параллельной загрузки счетчика 25, в результате чего содержимое регистра 26 копируется в счетчик 25 (для h-го БРЗ копируется значение C_h разветвленности h-й цепи). Как только содержимое счетчика 25 становится отличным от нуля, на его выходе окончания счета снова устанавливается нулевой уровень, в связи с чем на выходе элемента И 8 восстанавливается нулевой уровень (см. фиг. 4). На этом оканчивается обработка сформированного варианта размещения с помощью БРЗ, а сами эти блоки оказываются подготовленными к обработке очередного варианта размещения. Данные, полученные на информационном выходе БРЗ, интерпретируются следующим образом. Для цепи h на момент CLKt на информационном выходе h-го БРЗ формируется значение ω_h(r₁,r₂,...,r_t). Таким образом, если данные на информационных выходах всех БРЗ рассматривать совместно, то они соответствуют разрядно-последовательному представлению интервальной диаграммы матрицы для текущего варианта размещения. Для нахождения значения ω(r₁,r₂,...,r_t) в соответствии с (2) необходимо просуммировать сигналы на информационных выходах всех БРЗ на момент времени CLKt. В связи с тем, что суммированию подлежат булевы значения, для их суммирования может быть использован блок 5 подсчета числа единиц, на выходе которого и формируется значение ω(r₁,r₂,...,r_t), соответствующее моменту времени CLKt. Для нахождения загруженности рабочего поля d(π_r) в соответствии с (1) используется блок 7 выделения максимума. По сигналу на входе 12 сброса этот блок подготавливается к работе, данные на информационном входе фиксируются с учетом синхроимпульсов CLKt на входе 13 синхронизации. Таким образом, блок 7 выделения максимума, имея на своем входе последовательность значений ω(r₁,r₂,...,r_t), для t= 1,2,...,n-1 выделяет максимальное из них, которое в соответствии с (1) является значением загруженности рабочего поля d(π_r) и выдает его на свой выход. По приходу на соответствующие управляющие входы блока 7 сигнала окончания перестановки либо сигнала окончания оценки текущего размещения блок 7 подготавливается к приему очередной последовательности данных.

Для определения суммарной длины цепей L_Σ(π_r) в соответствии с (4) используется накапливающий сумматор 6. По сигналу на входе 12 сброса сумматор подготавливается к работе, данные на его информационном входе фиксируются с учетом синхроимпульсов CLKt на входе 13 синхронизации. Таким образом, в, сумматоре 6 накапливается сумма значений ω(r₁,r₂,...,r_t) для t= 1,2,.,n-l и по окончании оценки текущего размещения, т.е. после поступления сигнала окончания оценки текущего размещения на выходе 19 либо сигнала окончания перестановки на входе 15 на выходе сумматора будет сформировано значение суммарной длины цепей L_Σ(π_r), a сам сумматор подготавливается к приему очередной последовательности данных. Для нахождения наибольшей длины цепи используются блоки 2₁, 2₂, . ..,2_m подсчета длины цепи и блок 3 нахождения максимума. Каждый такой блок определяет длину соответствующей цепи, после чего блоком 3 нахождения максимума из них выделяется наибольшее значение, которое выдается на первый выход 16 оценки текущего размещения. Описанный процесс оценки аналогичным образом осуществляется для любого варианта размещения.

Использование совокупности существенных признаков изобретения позволяет расширить функциональные возможности устройства для оценки линейного размещения элементов за счет обеспечения возможности подсчета критерия загруженности рабочего поля размещения. Кроме того, предлагаемое устройство предоставляет потенциальную возможность повышения средней производительности при оценке размещения за счет использования сигнального выхода 19 окончания оценки текущего размещения. При появлении на этом выходе единичного сигнала внешнее устройство формирования вариантов размещения (перестановок) может прервать текущую перестановку и начать формирование следующей. Еще одним преимуществом предлагаемого устройства является исключение из состава устройства многовходового сумматора, являющегося сложным и медленно действующим элементом, за счет использования метода подсчета суммарной длины цепей на основе выражения (4), что позволяет использовать сумматор накапливающего типа.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10