УСТРОЙСТВО ДЛЯ ОЦЕНКИ ЛИНЕЙНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ Российский патент 1994 года по МПК G06F15/419 

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

Известно устройство, предназначенное для моделирования комбинаторных задач проектирования РЭА и АСУ, обеспечивающее возможность оценки текущего размещения при изоморфных преобразованиях [1]. Данное устройство представляет собой полноматричную двумерную однородную среду, каждая ячейка которой содержит блок оценки размещения.

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

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

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

Целью изобретения является упрощение устройства и повышение его среднего быстродействия.

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

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

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

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

На фиг. 1 приведена структурная схема устройства; на фиг. 2 и 3 - функциональная схема БПДЦ и временные диаграммы его работы соответственно; на фиг. 4 приведен пример матрицы инцидентности A = a 8 × 6; преобразованная матрица А' приведена на фиг. 5; фиг. 6 иллюстрирует размещение матрицы инцидентности А в блоке памяти; фиг. 7 и 8 даны примеры последовательно-кодированного представления матриц А и А' соответственно.

Устройство содержит блок 1 памяти, m идентичных БПДЦ 2, сумматор 3, блок нахождения максимума, вход 5 установки, шину 6 записи матрицы инцидентности исходного гиперграфа, шину 7 адреса, вход 8 сброса, вход 9 синхронизации, вход 10 окончания перестановки, выходы 11 и 12 оценки текущего размещения, связанные с выходами сумматора 3 и блока 4 нахождения максимума соответственно. Шина 6 подключена к информационным входам блока 1 памяти, адресные входы которого подключены к шине 7 адреса, вход 5 установки соединен с входом управления записью-считыванием блока 1 памяти. К соответствующим входам каждого БПДЦ 2 подсоединены входы сброса 8, синхронизации 9 и окончания перестановки 10, при этом i-й выход блока 1 памяти (i=) подключен к информационному входу i-го БПДЦ 2, выход которого соединен с i-м информационным входом блока и входом i-го слагаемого сумматора 3.

Каждый БПДЦ 2 содержит элемент ИЛИ 13, триггер 14, элемент 15 задержки, счетчик 16, параллельные регистры 17 и 18 хранения. Вход установки триггера 14 в единичное состояние связан с входом параллельной загрузки регистра 17 и является информационным входом БПДЦ. Вход элемента 15 задержки соединен с входом разрешения параллельной загрузки регистра 17 и является синхровходом БПДЦ. Первый вход элемента ИЛИ 13 связан с входом параллельной загрузки регистра 18 и является входом окончания перестановки, второй вход элемента ИЛИ 13 соединен с входами сброса регистров 17 и 18 и служит входом сброса БПДЦ, а выход элемента ИЛИ 13 соединен с входом установки триггера 14 в нулевое состояние и входом сброса счетчика 16. Прямой выход триггера 14 соединен с входом разрешения счета счетчика 16, счетный вход которого связан с выходом элемента 15 задержки. Информационные выходы счетчика подключены к информационным входам регистра 17, выходы которого соединены с информационными входами регистра 18, чьи выходы служат выходом БПДЦ.

Рассмотрим работу устройства, пояснив предварительно принцип и теоретические предпосылки его функционирования. Пусть задана некоторая схема С=(М, N), содержащая множество М= {m₁, m₂,...,m_n} элементов, соединенных друг с другом некоторым образом посредством множества N= {n₁, n₂,...,n_m} цепей. Пусть задано также одномерное дискретное регулярное монтажное пространство S, содержащее множество Р= {p₁, p₂,...,p_n} позиций, отстоящих друг от друга на единичный интервал длины. Полагают, что каждый элемент mk, k=, может быть размещен в любой позиции Р_j, j=, таким образом, чтобы не создавалось ограничений на размещение других элементов (т.е. чтобы не возникало взаимных наложений элементов), а во всякой позиции Р_j не может быть размещено более одного элемента. Требуется отыскать вариант размещения элементов m₁, m₂, . ..,m_n схемы на позициях Р₁, Р₂,...,Р_n монтажного пространства, имещий оптимальное значение критерия качества. Для оценки качества выбраны два широкораспространенных критерия - суммарная длина цепей и цепь с максимальной длиной. Для решения поставленной задачи с успехом может быть использована гиперграфовая математическая модель схемы и монтажного пространства одновременно. Гиперграф Н=(V,E) представляет собой совокунпость множества V= { v₁, v₂,...,v_n} вершин и множества Е= {e₁, e₂,...,e_m} ребер и задается матрицей инцидентности A = a m × n, причем
a= (k=; l=). Каждому элементу m_k схемы ставится во взаимооднозначное соответствие вершина v_k гиперграфа, а всякой цепи n_l схемы ребро е_lгиперграфа. При этом, если некоторый контакт элемента m_k принадлежит некоторой цепи n_l, то соответствующая вершина v_k гиперграфа считается инцидентной ребру e_l. Абстрагируют от реальных размеров элементов, считая их изолированными точками - вершинами гиперграфа. Пример матрицы инцидентности A = a 8 × 6 приведен на фиг. 4. Для моделирования монтажного пространства S также используется матричное описание гиперграфа, что оказывается возможным ввиду одномерности, дискретности и регулярности монтажного пространства. Считают, что порядковым слева-направо номерам столбцов матрицы инцидентности взаимооднозначно соответствуют позиции Р₁,Р₂,...,Р_n. С учетом того, что всякой вершине гиперграфа взаимооднозначно соответствует некоторый столбец матрицы, всякий вариант р азмещения может быть смоделирован матрицей инцидентности А' , столбцы которой расположены в порядке, соответствующем данному варианту размещения. Пример преобразованной матрицы А' , моделирующей нижеприведенный вариант размещения приводится на фиг. 5:

Рассмотрим теперь используемую в устройстве структуру данных. Если вершинам гиперграфа соответствуют столбцы, а ребрам - строки матрицы инцидентности, то сама матрица размещается в блоке памяти, чтобы всякое слово данных представляло собой некоторый столбец матрицы. При этом каждый элемент матрицы представляется одним битом и хранится в отдельном запоминающем элементе блока памяти. В качестве блока памяти предполагается использование обычного оперативного ЗУ с произвольной выборкой. В целях упрощения изложения допускают, что столбцы матрицы размещаются в блоке памяти в порядке возрастания номеров соответствующих вершин, начиная с нулевого адреса. На фиг. 6 приведен пример такoго размещения матрицы А. Полагают, что аналогично прототипу, варианты размещения формируются некоторым внешним устройством. При этом для задания всякого варианта размещения принята следующая форма: последовательность двоичных кодов, составляющих перестановку, где численное значение всякого кода взаимооднозначно соответствует номеру элемента (для простоты принимают, что значение кода в последовательности равно уменьшенному на единицу номеру соответствующего элемента), а порядковый номер данного кода в последовательности - номеру позиции, в которую размещается данный элемент. Пусть матрица инцидентности загружена в блок памяти, а сам блок памяти переведен в режим чтения. Тогда, если подать некоторую перестановку (последовательность кодов) на адресные входы блока памяти (см. фиг. 6), на его информационных выходах формируется последовательно-кодированное представление загруженной матрицы, соответствующее заданному варианту размещения. В качестве примера на фиг. 7 показано последовательно-кодированное представление матрица А, соответствующее варианту размещения

задаваемого перестановкой <000, 001, 010, 011, 100, 101> на адресных входах блока памяти (здесь веса разрядов двоичных кодов соответствуют схеме 2²2¹2⁰, а символы "<", ">" обозначают кортеж или упорядоченное множество элементов). При этом считывание отдельных слов данных синхронизируется импульсами CLK, поступающими на вход синхронизации. На фиг. 8 приведено последовательно-кодированное представление матрицы А' , эквивалентное преобразованной матрице А' (см. фиг. 5) и соответствующее варианту размещения

задаваемому перестановкой <001, 000, 010, 101, 100, 011>. В процессе формирования преобразованной матрицы не происходит ее физического изменения в блоке памяти. Рассмотрим теперь принцип подсчета критериев качества вариантов размещения. Выделение цепи с максимальной длиной производится аналогично прототипу с помощью блока нахождения максимума. Подсчет суммарной длины цепей реализуется посредством БПДЦ и сумматора. Длина каждой цепи подсчитывается отдельным БПДЦ и, таким образом, длины всех цепей подсчитываются параллельно. Затем они суммируются в сумматоре, а на выходе последнего формируется значение суммарной длины цепей. Проиллюстрируем метод подсчета длины отдельной цепи, воспользовавшись фиг. 7, из которой видно, что всякая цепь представлена в последовательном коде, формирующемся на соответствующем выходе блока памяти. Длина всякой цепи может быть определена путем подсчета числа импульсов CLK, появившихся с момента поступления первого единичного импульса на соответствующий выход блока памяти до поступления последнего такого импульса за время считывания всей матрицы. Длина соответствующей цепи равна при этом уменьшенному на единицу числу таких импульсов. Так, например, для цепи е₁ имеется четыре таких импульса - CLK2, CLK3, CLK4, CLK5 (см. фиг. 7). а ее длина на единицу меньше этого числа и равна трем. В другом варианте размещения (см. фиг. 8) цепь е₁ имеет длину четыре - импульсы CLK1,...,CLK5. Предлагаемое устройство работает следующим образом.

Перед началом работы блок 1 памяти устанавливается по входу 5 установки в режим записи и загружается через шину 6 записи матрицы инцидентности исходного гиперграфа данными о некоторой матрице, при этом используется также шина 7 адреса. По окончании загрузки блок памяти переводится в режим чтения с помощью входа 5 установки, а единичным импульсом на входе 8 сброса все БПДЦ устанавливаются в исходное состояние. Для оценки некоторого варианта размещения соответствующая ему перестановка подается на шину 7 адреса, являясь, таким образом, последовательностью адресов для блока 1 памяти. По каждому такому адресу считывается одно слово данных - столбец матрицы, причем его выдача синхронизирована импульсами СLK по входу 9 синхронизации, как показано на фиг. 3. В процессе считывания матрицы формируется ее последовательно-кодированное представление, а для отдельных цепей формируется их последовательные коды, поступающие в соответствующие БПДЦ. В исходное состояние все БПДЦ приводятся по сигналу на входе 8 сброса, при этом триггер 14, счетчик 16 и регистры 17 и 18 обнуляются, а нулевым потенциалом на входе Е счетчика запрещается счет импульсов. При поступлении данных из блока памяти на информационный вход БПДЦ указанное состояние элементов сохраняется до прихода первого единичного импульса на этот вход. В случае поступления такого импульса триггер 14 переходит в единичное состояние, в регистр 17 по импульсу CLK2 (см. фиг. 3) загружено текущее состояние счетчика, равное в данный момент нулю, а через время задержки элемента 15 тот же импульс CLK2 поступает на счетный вход счетчика и, поскольку его работа теперь, разрешена (единичный потенциал на входе Е), его состояние увеличивается на единицу. При этом время задержки элемента 15 должно быть таким, чтобы импульсы CLK появлялись на счетном входе счетчика не раньше, чем исчезнут на входе Е разрешения параллельной загрузки регистра 17 (таким образом, это время должно быть не меньше длительности импульсов CLK). В дальнейшем всякий раз, когда на информационный вход БПДЦ поступает единичный импульс, в регистр 17 по соответствующему импульсу CLK загружается текущее состояние счетчика, а спустя время задержки элемента 15, увеличивается на единицу состояние счетчика. Таким образом, учитывается, что длина цепи на единицу меньше числа импульсов CLK за указанное выше время. Заметим, что счетчик подсчитывает импульсы СLK независимо от данных на информационном входе БПДЦ, начиная с момента прихода первого единичного импульса на этот вход. В таком режиме устройство функционирует до окончания перестановки, когда на вход 10 поступает соответствующий единичный импульс. По этому сигналу данные из регистра 17, отображающие длину соответствующей цепи, копируются в буферный регистр 18 и поступают на выход данного БПДЦ, а триггер и счетчик обнуляются. Таким образом, БПДЦ подготовлен к обработке следующей цепи. Аналогично функционируют и остальные БПДЦ.

Использование совокупности существенных признаков изобретения позволяет получить значительный технико-экономический эффект, состоящий в снижении затрат на реализацию устройства и повышении его среднего быстродействия. Для его выявления проводят подробный сопоставительный анализ по сложности и быстродействию между предлагаемым устройством и прототипом. При оценке сложности устройств использована методика Квайна, согласно которой сложность схемы определяется суммарным числом входов составляющих ее логических элементов. При этом цена инверсного входа обычно принимается равной двум (Майоров С. А., Новиков Г.И. Структура электронных вычислительных машин. - Л. : Машиностроение. Ленингр. отдел. 1979. - 384 с., ил. С.237). В соответствии со структурой прототипа его сложность Z_o определяется выражением
Z_o=Z_oc+mZ_Бпе+Z_Бп+Z_Бнм+Z_sм,
где Z_ос - сложность однородной среды;
Z_Бпе - сложность блока подсчета единиц (БПЕ);
Z_Бп - сложность блока памяти;
Z_Бп - сложность блока памяти;
Z_Бнм - сложность блока нахождения максимума (БНМ);
Z_sм - сложность сумматора.

Анализируя структуру однородной среды можно записать
Z_ос=nmZ_эос,
где Z_эос - сложность одного элемента однородной среды;
n - число размещаемых элементов;
m - число цепей.

Из схемы элемента однородной среды следует, что Z_эос ≈ 110 (элементы типа И-ИЛИ раскрывались в отдельные элементы И и ИЛИ; предполагалось, что все триггеры имеют сложность RS-триггеров, равную четырем; сложность блока обработки входной информации подсчитана по схеме, приведенной в авт.св. СССР N 646328, кл. G 06 F 7/00, 1974), тогда
Z_ос ≈ 110 nm.

Так как каждый блок подсчета единиц состоит из nxlog₂n элементарных ячеек, а сложность всякой ячейки равна 10, то
Z_БПЕ=10nlog₂n.

Сложность блока памяти при условии его построения на базе типовых D-триггеров, имеющих сложность девять (Шило В.Л., Популярные цифровые микросхемы: Справочник. - 2-е изд., исправленное. - М.: Радио и связь, 1989, - 352, с., с. 73), можно подсчитать так:
Z_БП=9nm.

Блок нахождения максимума состоит из mlog₂n элементарных ячеек, сложность каждой из них составляет восемь тогда
Z_БНМ = 8mlog₂n.

Рассчитывая сложность сумматора, для простоты полагают, что значения n и m кратны 2^р, где Р ∈ N (N - множество натуральных чисел), что не влияет на достоверность получаемых результатов. Полагают, что данный сумматор, рассчитанный на сложение m слагаемых, построен на основе обычных сумматоров на два слагаемых с использованием ступенчатой структуры. Если обычный сумматор на два слагаемых построен по типу, например, 155ИМ3 (Шило В.Л., Указ. справочник. с. 162), на каждый его разряд в среднем приходится Z¹_sм ≈ 72/4 ≈ 18 единиц сложности. При этом для построения сумматора на m слагаемых требуется К=log₂m ступеней. Исходя из ступенчатой структуры в табл. 1 приводятся требуемая разрядность и число сумматоров на два слагаемых в каждой ступени сумматора на m слагаемых.

Теперь можно подсчитать общую сложность сумматора: n
Здесь 1/2^t ≈ (t-1)/2^t ≈ 1 , что справедливо при числе цепей m порядка нескольких десятков и больше, что обычно выполняется на практике.

Таким образом, сложность прототипа составляет
Z_o = 110nm+m10nlog₂n+9nm+8m log₂n +
+18m (log₂n+1) ≈ m (119n+10n log₂n +
+26 log₂n + 18).

Рассчитаем теперь сложность Z₁ предлагаемого устройства, в соответствии со структурой которого имеют
Z₁ = Z¹_Бп + mZ_Бпдц + Z_Бнм + Z_sм,
где Z¹_Бп - сложность блока памяти предлагаемого устройства;
Z_Бпдц - сложность блока подсчета длины цепи.

Как укаазано выше, предполагается использоваться блок памяти типа ЗУ с произвольным доступом статического типа, в качестве запоминающего элемента которого используются RS-триггеры (Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990. - 304 с.: ил. с. 215). Очевидно, что
Z¹_Бп=Z_м3э+Z_доп,
где Z_мзэ - сложность матрицы запоминающих элементов блока памяти;
Z_доп - сложность устройства управления, дешифрации адреса и ввода-выхода блока памяти.

Так как матрица запоминающих элементов содержит nxm RS-триггеров, Z_мзэ = =4nm. Принимают, что Z_доп ≈ 3 x Zмзэ, тогда имеют
Z¹_Бп ≈ 16 nm.

Подсчитывая сложность БПДЦ, можно записать, что (см. фиг. 2)
Z_Бпдц = Z_или + Z_Rs + Z + Z_ст + 2 x Z_RG,
где Z_или - сложность логического элемента ИЛИ (равна двум);
Z_Rs - сложность RS-триггера (равна четырем);
Z - сложность элемента задержки (принимают равной десяти);
Z_ст - сложность счетчика;
Z_RG - сложность регистра.

Учитывая, что максимальная длина цепи может достигать n-1, число выходов счетчика и соответственно число разрядов регистров должны быть не менее log₂(n-1). Пусть счетчик построен по схеме двоичного синхронного счетчика, аналогичной, например, схеме счетчика 555 ИЕ 18 (Шило В.А. Указ. справочник, с. 99), но с асинхронным сбросом. Полагают, что многоразрядный счетчик строится путем объединения нужного количества таких четырехразрядных счетчиков. На каждый разряд счетчика приходится в среднем около 100/4=25 единиц сложности, где 100 - общая сложность счетчика. Тогда
Z_ст ≈ 25 log₂(n-1).

Принимают, что на каждый разряд параллельного регистра приходится не более 13 единиц сложности, что справедливо для обычных регистров-защелок на базе D-триггеров, и тогда
Z_RG ≈ 13 log₂(n-1);
Z_Бпдц ≈ 2+4+10+25 log₂(n-1)+
+26 log₂(n-1) ≈ 16+51 log₂(n-1).

С учетом полученных выражений для Z_бнм и Z_sм имеют
Z₁ ≈ 16nm+m (16+51 log₂(n-1))+
+8m log₂n+18m (log₂n+1) ≈ m(16n+
+26log₂n+51 log₂ (n-1)+34).

Сравнивая сложность прототипа и предлагаемого устройства, определяют значения коэффициента Т= Z_o/Z₁ для различных n, приведенных в табл. 2. С учетом выражений для Z_o и Z₁ записывают выражение для коэффициента Т, показывающего во сколько раз прототип сложнее предлагаемого устройства:
T =
Приведенные в табл. 2 результаты показывают, что сложность прототипа значительно превосходит сложность предлагаемого устройства. Сравнивая схемы обоих устройств можно заметить, что для реализации схемы прототипа требуется гораздо больше межэлементных связей (в основном за счет большой насыщенности связей между однородной средой и блоками подсчета единиц). Более того можно показать, что построение устройства для оценки размещения по схеме прототипа на основе однородной среды нецелесообразно при наличии предложенного подхода. Это следует из того, что сложность лишь одной из составных частей прототипа, введенной для реализации функции оценки размещения, а именно блоков подсчета единиц, оказывается выше, чем всего предлагаемого устройства. Этот вывод подтверждается результатами соответствующих расчетов, приведенных в табл. 3.

Для сравнения быстродействия прототипа и предлагаемого устройства определяют и сравнивают между собой величины Т_о и Т₁, обозначающие времена, требуемые прототипу и предлагаемому устройству соответственно для нахождения всех значений длин отдельных цепей, соответствующих текущему варианту размещения, поскольку дальнейшая обработка в обоих устройствах идентична и поэтому, требует одинакового времени. В соответствии со структурой прототипа
Т_о=t_oc+t_бпе,
где t_oc - время формирования варианта размещения в однородной среде и выдачи данных о цепях в блок подсчета единиц;
t_бпе - время подсчета числа единиц (т.е. длины цепи) в БПЕ.

Можно записать
t_oc=t_фвp+t_доп,
где t_фвр - время формирования варианта размещения в однородной среде;
t_доп - время фиксации варианта размещения в однородной среде и выдачи данных о цепях в блоке подсчета единиц.

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

Для расчета t_эос обратимся к схеме элемента однородной среды и описанию работы однородной среды в режиме изоморфных преобразований в подрежиме перестановки строк. При этом задержка всякого промежуточного (транзитного) элемента однородной среды определяется задержкой блока обработки входной информации, равной 3τ (авт.св. СССР N 646328), где τ - задержка одного стандартного вентиля, и задержкой элемента 3И-НЕ14. Тогда t_эос=4τ и, следовательно t_фвр ≈ 4(n-1) τ.

По завершении формирования варианта размещения его необходимо зафиксировать путем переписи в триггеры (для строк, участвующих в обмене), что потребует не менее чем 3τ времени. Затем формируются данные о цепях на индикаторных выходах элементов среды. Соответствующее время определяется задержкой при прохождении инициализирующего сигнала (единичные потенциалы на входах элементов первой строки и на входах элементов последней строки) через какую-либо из двух n-элеметных цепочек и задержкой элемента 2ИЛИ-НЕ в конце цепочек. Таким образом
t_доп ≈ 3τ + nτ + τ ≈ (n+4) τ ;
t_oc ≈ 4(n-1) τ+(n+4) τ ≈ 5n τ.

Для определения t_БПЕ необходимая размерность блока подсчета единиц составляет nlog₂n ячеек. При этом с учетом того, что задержка данных в каждой ячейке равна 3τ при распространении по вертикали и τ по горизонтали, можно записать
t_БПЕ ≈ (3n+log2n) τ.

Тогда искомое время
Т_о ≈ 5n τ +(3n+log₂n) τ ≈ (8n+log₂n) τ .

Рассчитаем теперь время Т₁ для предлагаемого устройства, предположив, что в блоке памяти размещена матрица инцидентности, а блок находится в режиме считывания. Так как для оценки всякого варианта размещения требуется считать всю матрицу, содержащую n слов, то
Т₁=max {t_БП, t_БПДЦ} x n.

где t_БП - время выборки адреса блока памяти;
t_БПДЦ - время обработки в БПДЦ.

Как видно из выражения для Т₁, берется максимальная из указанных величин, что обусловлено тем, что БПДЦ не комбинационное устройство в отличие от блока подсчета единиц прототипа. Для определения tбп на базе типовой схемы ЗУПВ статического типа обращают к книге Пухальского Г.И. и др. с. 215. Можно записать t_БП=t_ДС+t_I/o, где t_I/o - задержка данных на элементах ввода-вывода; t_ДС - время дешифрации адреса. Принимают t_ДС=5 τ, t_I/o≈2 τ, тогда t_БП= 7 τ . Для подсчета t_БПДЦ достаточно определить время параллельной загрузки регистра 17, определяющее минимальное время удержания данных на информационном входе БПДЦ. Время загрузки регистров обычно не превышает 7τ и, таким образом
Т₁ ≈7n τ
Сравнивают быстродействие обоих устройств, для чего определяют значения коэффициентов S=To/T1 для различных n (см. табл. 4), при этом
S = .

Из табл. 4 следует, что быстродействие предлагаемого устройства несколько выше, чем у прототипа, работающего в указанном выше режиме. Однако предлагаемое устройство позволяет без усложнения и снижения быстродействия оценивать произвольные варианты размещения, причем эти варианты могут следовать в произвольной последовательности. В соответствии с принципом работы прототипа он допускает за одну перестановку получать не произвольный вариант, а вариант с циклическим обменом элементов. Поэтому для получения некоторого произвольного варианта размещения требуется провести ряд таких перестановок, композиция которых дает желаемый вариант. При этом необходимое число таких перестановок определяется текущим вариантом размещения, подлежащим оценке. Это ведет к снижению среднего быстродействия прототипа при оценке произвольных вариантов размещения, порядок следования которых также произволен. Кроме того, происходит усложнение алгоритмов управления однородной средой прототипа при реализации таких вариантов. Необходимо отметить особенность предлагаемого устройства за счет которой отсутствует необходимость введения дополнительного блока памяти для сохранения матрицы инцидентности лучшего варианта размещения. Если для прототипа затруднен контроль непосредственно за текущим вариантом размещения из-за влияния на него текущего состояния однородной среды (т.е. всех предыдущих реализованных вариантов) и оказывается, что проще сохранять матрицу инцидентности лучшего варианта, по которой затем отыскивается сам вариант размещения, то для предлагаемого устройства всякому задаваемому извне варианту размещения однозначно соответствует некоторая преобразованная матрица инцидентности (последовательно-кодированное представление) независимо от ранее оцененных вариантов. Таким образом, для предлагаемого устройства достаточно контролировать саму перестановку, что облегчается благодаря наличию функциональных генераторов перестановок (авт.св. СССР N 1513467, кл. G 06 F 15/20, 1987), каждая перестановка которых однозначно задается ее номером. При этом каждый вариант размещения получает свой, отличный от остальных, номер, который и можно запоминать для лучшего варианта размещения при построении на основе предлагаемого устройства законченного размещателя элементов.

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

1. УСТРОЙСТВО ДЛЯ ОЦЕНКИ ЛИНЕЙНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ, содержащее блок нахождения максимума, сумматор, шину записи матрицы инцидентности исходного гиперграфа, вход установки, первый и второй выходы оценки текущего размещения, соединенные с выходами блока нахождения максимума и сумматора соответственно, отличающееся тем, что, с целью упрощения и повышения среднего быстродействия, оно содержит блок памяти , m идентичных блоков подсчета длины цепи (m - число цепей), шину адреса, вход сброса, вход синхронизации и вход окончания перестановки, причем шина записи матрицы инцидентности исходного гиперграфа подключена к информационным входам блока памяти, адресные входы которого подключены к шине адреса, вход установки соединен с входом управления записью -считыванием блока памяти, входы сброса, синхронизации и окончания перестановки устройства подсоединены к одноименным входам каждого блока подсчета длины цепи, при этом i-й выход блока памяти (i = ) подключен к информационному входу i-го блока подсчета длины цепи, выход которого соединен с i -м информационным входом блока нахождения максимума и входом i-го слагаемого сумматора. 2. Устройство по п.1, отличающееся тем, что каждый блок подсчета длины цепи содержит элемент ИЛИ, триггер, элемент задержки, счетчик, первый и второй параллельные регистры хранения, причем вход установки триггера в единичное состояние соединен с входом параллельной загрузки первого регистра и является информационным входом блока, вход элемента задержки соединен с входом разрешения параллельной загрузки первого регистра и является входом синхронизации блока, первый вход элемента ИЛИ связан с входом параллельной загрузки второго регистра и является входом окончания перестановки блока, второй вход элемента ИЛИ соединен с входами сброса обоих регистров и является входом сброса блока, при этом выход элемента ИЛИ соединен с входом установки триггера в нулевое состояние и входом сброса счетчика, прямой выход триггера соединен с входом разрешения счета счетчика, счетный вход которого соединен с выходом элемента задержки, информационные выходы счетчика подключены к информационным входам первого регистра, выходы которого соединены с информационными входами второго регистра, выходы которого образуют выход блока.