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

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

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

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

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

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

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

Техническая задача решается тем, что в устройство для формирования матрицы неполного параллелизма, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок формирования матрицы неполного параллелизма, содержащий матрицу из (i,j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, тактовый генератор, счетчик импульсов стробирования загрузки исходных данных, первый дешифратор номера строба, второй дешифратор номера строки, счетчик номера столбца, первое двухпортовое ОЗУ обработки матрицы входных переменных, второе двухпортовое ОЗУ обработки матрицы выходных переменных, первый D-триггер с инверсным синхровходом, второй D-триггер задержки счета столбцов, третий D-триггер задержки переключения частоты, первый конъюнктор, второй конъюнктор, третий конъюнктор, первый мультиплексор выбора частоты функционирования устройства, дизъюнктор, счетчик номера строки, компаратор сравнения с нулем, первое однопортовое ОЗУ обработки матрицы достижимости, преобразователь кода из параллельного в последовательный, четвертый конъюнктор, преобразователь кода из последовательного в параллельный, четвертый D-триггер, второе однопортовое ОЗУ хранения матрицы неполного параллелизма, пятый D-триггер выработки условия готовности, шестой D-триггер разрешения счета строк, второй мультиплексор, причем информационные входы матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, входы сброса R матрицы из (i.j) (1=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с выходом Q третьего D-триггера задержки переключения частоты, на вход тактового генератора подаются сигналы со входов подачи "питания" и подачи "земли", выход тактового генератора соединен с входами подачи частоты первого двухпортового ОЗУ обработки матрицы входных переменных, второго двухпортового ОЗУ обработки матрицы выходных переменных, счетным входом счетчика номера столбца, синхровходом второго D-триггера задержки счета столбцов, синхровходом третьего D-триггера задержки переключения частоты, первым входом первого мультиплексора выбора частоты функционирования устройства, первым входом второго мультиплексора, входом подачи частоты преобразователя кода из параллельного в последовательный, входом подачи частоты преобразователя кода из последовательного в параллельный, входом подачи частоты первого однопортового ОЗУ обработки матрицы достижимости и выходом синхронизирующей частоты устройства соответственно, вход CLK счетчика импульсов стробирования загрузки исходных данных соединен с входом управления записью устройства, вход CLR счетчика импульсов стробирования загрузки исходных данных соединен с выходом Q четвертого D-триггера, выходы Q1…QK счетчика импульсов стробирования загрузки исходных данных соединены с входами А1…АК первого дешифратора номера строба, выход D1 первого дешифратора номера строба соединен с входом WE первого двухпортового ОЗУ обработки матрицы входных переменных, выход D2 первого дешифратора номера строба соединен с входом WE управления записью/считыванием второго двухпортового ОЗУ обработки матрицы выходных переменных, выход D3 первого дешифратора номера строба соединен с входом WE первого однопортового ОЗУ обработки матрицы достижимости и инверсным синхровходом С первого D-триггера с инверсным синхровходом соответственно, входы А1…АК второго дешифратора номера строки соединены с соответствующими выходами Q1…QK счетчика номера строки, выходы D1…DN второго дешифратора номера строки соединены с соответствующими входами CE1…CEN разрешения синхроимпульса D-триггеров строк матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, входы DIN1…DINM первого двухпортового ОЗУ обработки матрицы входных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i.j) (1=1, 2, …, N, j=1, 2, …, М) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта соединены с соответствующими выходами Q1…QK счетчика номера строки, адресные входы В1…ВК второго порта соединены с соответствующими выходами Q1…QK счетчика номера столбца, выход O1 первого порта первого двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом первого конъюнктора, выход O2 второго порта первого двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом второго конъюнктора, входы DIN[M…1] второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i.j) (i=1, 2, …, М, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика номера строки, адресные входы В1…ВК второго порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика номера столбца, выход O1 первого порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом второго конъюнктора и с первым входом третьего конъюнктора соответственно, выход O2 второго порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом первого конъюнктора и со вторым входом третьего конъюнктора соответственно, вход CLR счетчика номера столбца соединен с выходом Q четвертого D-триггера, выход переполнения ТС счетчика номера столбца соединен с информационным входом второго D-триггера задержки счета столбцов, вход подачи питания Н соединен с информационным входом D первого D-триггера, с информационным входом D четвертого D-триггера, а также с информационным входом D шестого D-триггера соответственно, вход CLR первого D-триггера с инверсным синхровходом соединен с выходом Q четвертого D-триггера, выход Q первого D-триггера с инверсным синхровходом соединен с информационным входом D третьего D-триггера задержки переключения частоты, выход Q второго D-триггера задержки счета столбцов соединен со вторым входом первого мультиплексора выбора частоты функционирования устройства, выход Q третьего D-триггера задержки переключения частоты соединен с коммутирующим входом первого мультиплексора выбора частоты функционирования устройства, со входом СЕ счетчика номера столбца, со входом EN компаратора сравнения с 0, со входом СЕ преобразователя кода из параллельного в последовательный, со входом СЕ преобразователя кода из последовательного в параллельный и с входом D пятого D-триггера выработки условия готовности соответственно, выход первого конъюнктора соединен с первым входом дизъюнктора, выход второго конъюнктора соединен со вторым входом дизъюнктора, выход третьего конъюнктора соединен с третьим входом дизъюнктора, выход первого мультиплексора выбора частоты функционирования устройства соединен с синхровходом CLK счетчика номера строки, с входом LD преобразователя кода из параллельного в последовательный и со вторым входом второго мультиплексора соответственно, выход дизъюнктора соединен с входом А[М…1] компаратора сравнения с 0, вход СЕ счетчика номера строки соединен с выходом Q шестого D-триггера, вход CLR счетчика номера строки соединен с выходом Q четвертого D-триггера, выходы Q1…QK счетчика номера строки соединены с соответствующими адресными входами А1…АК второго однопортового ОЗУ хранения матрицы неполного параллелизма, выход ТС переполнения счетчика номера строки соединен с синхровходом С пятого D-триггера выработки условия готовности, выход ZERO компаратора сравнения с нулем соединен со вторым входом четвертого конъюнктора, входы DIN1…DINM первого однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, вход WE первого однопортового ОЗУ хранения матрицы достижимости соединен с выходом D3 первого дешифратора номера строба, выходы O1…ON первого однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими входами DIN1…DINM преобразователя кода из параллельного в последовательный соответственно, выход DOUT преобразователя кода из параллельного в последовательный соединен с первым входом четвертого конъюнктора, выход четвертого конъюнктора соединен со входом SDIN преобразователя кода из последовательного в параллельный, вход CLR преобразователя кода из последовательного в параллельный соединен с выходом Q четвертого D-триггера, выходы Р1…РМ преобразователя кода из последовательного в параллельный соединены с соответствующими входами DIN1…DINM второго однопортового ОЗУ хранения матрицы неполного параллелизма, синхровход С четвертого D-триггера соединен с входом подачи строба для считывания матрицы неполного параллелизма, вход CLR четвертого D-триггера соединен с входом управления записью устройства, выход Q четвертого D-триггера соединен с входом CLR шестого D-триггера разрешения счета строк, а также с входом clr сброса пятого D-триггера выработки условия готовности соответственно, вход подачи строба для считывания матрицы неполного параллелизма соединен с входом WE второго однопортового ОЗУ хранения матрицы неполного параллелизма, с коммутативным входом второго мультиплексора, а также с синхровходом С четвертого D-триггера соответственно, выходы MNP1…MNPM второго однопортового ОЗУ хранения матрицы неполного параллелизма соединены с соответствующими выходами с 1-го по М-й считывания матрицы неполного параллелизма, выход Q пятого D-триггера выработки условия готовности соединен с выходом готовности устройства.

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

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

В ВС исходный (распараллеливаемый) фрагмент программы задается в следующем виде:

1. Исходный алгоритм (фиг.2а) представляется графом взаимодействия задач: G=<Х,Е>, где Х - множество вершин графа G, вершины x_i∈X которого соответствуют операторам программы, а дуги e_ij∈Е представляют информационные связи (фиг.2б), где N - число операторов последовательной программы.

2. Матрица достижимости , где , , (N - число операторов программы) (фиг.2в) характеризует последовательность выполнения операторов. Она формируется на основе анализа графа G следующим образом: на пересечении i-го и j-го столбца ставится единица, если из i-го оператора можно попасть в j-й. При формировании матрицы достижимости в случае появления условия оно воспринимается как оператор. В этом случае имеет место «агрессивное» исполнение алгоритма (одновременно будут вычисляться обе ветви условия). При этом в процессе выполнения алгоритма, когда переменные условия будут вычислены, заведомо ложная ветвь будет отсечена.

4. Матрица входных переменных , где , , характеризующая присутствие j-й переменной во входном наборе i-го оператора (фиг.2г).

5. Матрица выходных переменных , где характеризующая присутствие j-й переменной в выходном наборе i-го оператора (фиг.2д).

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

F=(Min_ij∧Mout_ji)∨(Min_ji∧Mout_ij)∨(Mout_ij∧Mout_ji).

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

Выявляя информационные зависимости между операторами p_i и p_j программы при Md_i,j=1, получаем матрицу неполного параллелизма (фиг.2е) , где , , отражающую полный набор информационных зависимостей между всеми операторами программы. Матрица неполного параллелизма и матрица параллельной логики являются необходимыми условиями для построения матрицы смежности C_P, определяющей возможности параллельного выполнения операторов программ (Э.А.Трахтенгерц. "Программное обеспечение параллельных процессов", с.26).

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

В отличие от прототипа, где формирование выполняется по двум критериям - суммарной длине ребер и максимальной длине ребра, предлагаемое устройство дополнительно формирует матрицу неполного параллелизма, которая отображает прямые и косвенные информационные связи между операторами фрагмента программы, и с учетом этих зависимостей выделяет информационно-независимые подмножества, которые можно выполнять параллельно на разных процессорах. Так, алгоритм на рис.2б может быть выполнен не последовательно за 7 шагов, а параллельно за 4 (фиг.2ж).

Устройство для формирования матрицы неполного параллелизма (фиг.1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1-2.n подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также блок 47 формирования матрицы неполного параллелизма, содержащий матрицу 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, тактовый 15 генератор, счетчик 16 импульсов стробирования загрузки исходных данных, первый 17 дешифратор номера строба, второй 18 дешифратор номера строки, счетчик 19 номера столбца, первое 20 двухпортовое ОЗУ обработки матрицы входных переменных, второе 21 двухпортовое ОЗУ обработки матрицы выходных переменных, первый 22 D-триггер с инверсным синхровходом, второй 23 D-триггер задержки счета столбцов, третий 24 D-триггер задержки переключения частоты, первый 25 конъюнктор, второй 26 конъюнктор, третий 27 конъюнктор, первый 28 мультиплексор выбора частоты функционирования устройства, дизъюнктор 29, счетчик 30 номера строки, компаратор 31 сравнения с нулем, первое 32 однопортовое ОЗУ обработки матрицы достижимости, преобразователь 33 кода из параллельного в последовательный, четвертый 34 конъюнктор, преобразователь 35 кода из последовательного в параллельный, четвертый 36 D-триггер, второе 37 однопортовое ОЗУ хранения матрицы неполного параллелизма, пятый 38 D-триггер выработки условия готовности, шестой 39 D-триггер разрешения счета строк, второй 46 мультиплексор, причем информационные входы матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы 1 элементов однородной среды, на синхровходы матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных подается сигнал со входа 9 управления записью устройства, входы сброса матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с выходом Q третьего 24 D-триггера задержки переключения частоты, на вход тактового 15 генератора подаются сигналы со входов 44 подачи "питания" и 45 подачи "земли", выход 15 тактового генератора соединен с входами подачи частоты первого 20 двухпортового ОЗУ обработки матрицы входных переменных, второго 21 двухпортового ОЗУ обработки матрицы выходных переменных, счетным входом счетчика 19 номера столбца, синхровходом второго 23 D-триггера задержки счета столбцов, синхровходом третьего 24 D-триггера задержки переключения частоты, первым входом первого 28 мультиплексора выбора частоты функционирования устройства, первым входом второго 46 мультиплексора, входом подачи частоты преобразователя 33 кода из параллельного в последовательный, входом подачи частоты преобразователя 35 кода из последовательного в параллельный, входом подачи частоты первого 32 однопортового ОЗУ обработки матрицы достижимости и выходом 40 синхронизирующей частоты устройства соответственно, вход CLK счетчика 16 импульсов стробирования загрузки исходных данных соединен с входом 9 управления записью устройства, вход CLR счетчика 16 импульсов стробирования загрузки исходных данных соединен с выходом Q четвертого 36 D-триггера, выходы Q1…QK счетчика 16 импульсов стробирования загрузки исходных данных соединены с входами А1…АК первого 17 дешифратора номера строба, выход D1 первого 17 дешифратора номера строба соединен с входом WE первого 20 двухпортового ОЗУ обработки матрицы входных переменных, выход D2 первого 17 дешифратора номера строба соединен с входом WE управления записью/считыванием второго 21 двухпортового ОЗУ обработки матрицы выходных переменных, выход D3 первого 17 дешифратора номера строба соединен с входом WE первого 32 однопортового ОЗУ обработки матрицы достижимости и инверсным синхровходом С первого 22 D-триггера с инверсным синхровходом соответственно, входы А1…АК второго 18 дешифратора номера строки соединены с соответствующими выходами Q1…QK счетчика 30 номера строки, выходы D1…DN второго 18 дешифратора номера строки соединены с соответствующими входами CE1…CEN разрешения синхроимпульса D-триггеров строк матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, М) D-триггеров синхронизации записи входных данных, входы DIN1…DINM первого 20 двухпортового ОЗУ обработки матрицы входных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, М) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта соединены с соответствующими выходами Q1…QK счетчика 30 номера строки, адресные входы В1…ВК второго порта соединены с соответствующими выходами Q1…QK счетчика 19 номера столбца, выход O1 первого порта первого 20 двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом первого 25 конъюнктора, выход O2 второго порта первого 20 двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом второго 26 конъюнктора, входы DIN[M…1] второго 21 двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта второго 21 двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика 30 номера строки, адресные входы В1…ВК второго порта второго 21 двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика 19 номера столбца, выход O1 первого порта второго 21 двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом второго 26 конъюнктора и с первым входом третьего 27 конъюнктора соответственно, выход O2 второго порта второго 21 двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом первого 25 конъюнктора и со вторым входом третьего 27 конъюнктора соответственно, вход CLR счетчика 19 номера столбца соединен с выходом Q четвертого 36 D-триггера, выход переполнения ТС счетчика 19 номера столбца соединен с информационным входом второго 23 D-триггера задержки счета столбцов, вход 44 подачи питания Н соединен с информационным входом D первого 22 D-триггера, с информационным входом D четвертого 36 D-триггера, а также с информационным входом D шестого 39 D-триггера соответственно, вход CLR первого 22 D-триггера с инверсным синхровходом соединен с выходом Q четвертого 36 D-триггера, выход Q первого 22 D-триггера с инверсным синхровходом соединен с информационным входом D третьего 24 D-триггера задержки переключения частоты, выход Q второго 23 D-триггера задержки счета столбцов соединен со вторым входом первого 28 мультиплексора выбора частоты функционирования устройства, выход Q третьего 24 D-триггера задержки переключения частоты соединен с коммутирующим входом первого 28 мультиплексора выбора частоты функционирования устройства, со входом СЕ счетчика 19 номера столбца, со входом EN компаратора 31 сравнения с 0, со входом СЕ преобразователя 33 кода из параллельного в последовательный, со входом СЕ преобразователя кода 35 из последовательного в параллельный и с входом D пятого 38 D-триггера выработки условия готовности соответственно, выход первого 25 конъюнктора соединен с первым входом дизъюнктора 29, выход второго 26 конъюнктора соединен со вторым входом дизъюнктора 29, выход третьего 27 конъюнктора соединен с третьим входом дизъюнктора 29, выход первого 28 мультиплексора выбора частоты функционирования устройства соединен с синхровходом CLK счетчика 30 номера строки, с входом LD преобразователя 33 кода из параллельного в последовательный, а также вторым входом второго 46 мультиплексора соответственно, выход дизъюнктора 29 соединен с входом А[М…1] компаратора 31 сравнения с 0, вход СЕ счетчика 30 номера строки соединен с выходом Q шестого 39 D-триггера, вход CLR счетчика 30 номера строки соединен с выходом Q четвертого 36 D-триггера, выходы Q1…QK счетчика 30 номера строки соединены с соответствующими адресными входами А1…АК второго 37 однопортового ОЗУ хранения матрицы неполного параллелизма, выход ТС переполнения счетчика 30 номера строки соединен с синхровходом С пятого 38 D-триггера выработки условия готовности, выход ZERO компаратора 31 сравнения с нулем соединен со вторым входом четвертого 34 конъюнктора, входы DIN1…DINM первого 32 однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, вход WE первого 32 однопортового ОЗУ хранения матрицы достижимости соединен с выходом D3 первого 17 дешифратора номера строба, выходы 01…ON первого 32 однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими входами DIN1…DINM преобразователя 35 кода из параллельного в последовательный соответственно, выход DOUT преобразователя 33 кода из параллельного в последовательный соединен с первым входом четвертого 34 конъюнктора, выход четвертого 34 конъюнктора соединен со входом SDIN преобразователя 35 кода из последовательного в параллельный, вход CLR преобразователя 35 кода из последовательного в параллельный соединен с выходом Q четвертого 36 D-триггера, выходы P1…РМ преобразователя 35 кода из последовательного в параллельный соединены с соответствующими входами DIN1…DINM второго 37 однопортового ОЗУ хранения матрицы неполного параллелизма, синхровход С четвертого 36 D-триггера соединен с входом 41 подачи строба для считывания матрицы неполного параллелизма, вход CLR четвертого 36 D-триггера соединен с входом 9 управления записью устройства, выход Q четвертого 36 D-триггера соединен с входом CLR шестого 39 D-триггера разрешения счета строк, а также с входом clr сброса пятого 38 D-триггера выработки условия готовности соответственно, вход 41 подачи строба для считывания матрицы неполного параллелизма соединен с входом WE второго 37 однопортового ОЗУ хранения матрицы неполного параллелизма, с коммутативным входом второго 46 мультиплексора, а также с синхровходом С четвертого 36 D-триггера соответственно, выходы MNP1…MNPM второго 37 однопортового ОЗУ хранения матрицы неполного параллелизма соединены с соответствующими выходами 42.1…42.М считывания матрицы неполного параллелизма, выход Q пятого 38 D-триггера выработки условия готовности соединен с выходом 43 готовности устройства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матрица 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных предназначена для синхронизации записи элементов матрицы 1 в первое 20 двухпортовое ОЗУ обработки матрицы входных переменных, второе 21 двухпортовое ОЗУ обработки матрицы выходных переменных и первое 32 однопортовое ОЗУ обработки матрицы достижимости.

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

Счетчик 16 импульсов стробирования загрузки исходных данных управляет перебором стробов загрузки трех разных типов исходных данных: матриц входных Min и выходных Mout переменных, а также матрицы достижимости Md. По приходу высокого уровня сигнала на вход clr счетчика 16 осуществляется его сброс. Счет происходит по приходу импульсов на счетный вход CLK счетчика 16. Выходы 2 содержат информацию о текущем номере строба STROB.

Первый 17 дешифратор номера строба, исходя из выходных данных счетчика 16, поступающих на его входы А1 и А2, выбирает строб загрузки одной из матриц (Min, Mout или Md), составляющих начальные данные, выдавая его на одну из выходных линий D1…D3.

Второй 18 дешифратор номера строки, исходя из выходных данных счетчика 30 номера строки, поступающих на входы А1…АК, , выбирает строку одной из загружаемых в данный момент матриц (Min, Mout или Md) и выдает соответствующие строкам матрицы 14 стробы CE1…CEN с выходов D1…DN.

Счетчик 19 номера столбца предназначен для перебора соответствующих адресов содержимого ячеек первого 20 двухпортового ОЗУ обработки матрицы входных переменных и второго 21 двухпортового ОЗУ обработки матрицы выходных переменных. Счет импульсов, поступающих на счетный вход CLK счетчика 19, происходит, когда с выхода Q третьего 24 D-триггера на вход разрешения счета СЕ счетчика 19 номера столбца приходит высокий уровень, показывающий, что загрузка исходных данных завершена. Счетчик 19 сбрасывается по приходу высокого уровня сигнала с выхода Q четвертого 36 D-триггера выработки условия готовности на вход clr. Выходы Q₁…Q_I, где , а М - количество входных переменных, содержат информацию о текущем номере обрабатываемого столбца. При перевороте счетчика 19 на выход ТС выдается соответствующий сигнал STB.

Первое 20 двухпортовое ОЗУ обработки матрицы входных переменных размером N*M (N - число операторов обрабатываемого фрагмента программы, М - число входных переменных на этом участке) предназначено для операций с элементами матрицы Min входных переменных. Запись данных, поступающих на входы DIN1…DINM ОЗУ 20, производится по единичному уровню на входе разрешения записи WE, считывание портов А[К…1] и B[K…1], , осуществляется по нулевому уровню входа разрешения записи WE с выходов O1 и O2 соответственно. Операции чтения/записи тактируются с помощью импульсов, поступающих на вход CLK подачи частоты ОЗУ 20.

Второе 21 двухпортовое ОЗУ обработки матрицы выходных переменных размером N*M (N - число операторов обрабатываемого фрагмента программы, М - число входных переменных на этом участке) предназначено для операций с элементами матрицы Mout выходных переменных. Запись данных, поступающих на входы DIN1…DINM ОЗУ 21, производится по единичному уровню на входе разрешения записи WE, считывание портов А[К…1] и B[K…1] - по нулевому уровню входа разрешения записи WE с выходов O1 и O2 соответственно. Операции чтения/записи тактируются с помощью импульсов, поступающих на вход CLK подачи частоты ОЗУ 21.

Первый 22 D-триггер с инверсным синхровходом С, информационным входом D, входом сброса С вырабатывает сигнал, свидетельствующий о том, что загрузка исходных данных в ОЗУ 20, ОЗУ 21, а также в первое 32 однопортовое ОЗУ завершена, и выдает его на выход Q.

Второй 23 D-триггер задержки счета столбцов с синхровходом С, информационным входом D и выходом Q задерживает сигнал переполнения с выхода ТС счетчика 19 номера столбца на один такт частоты CLK, подаваемой с генератора 15. Это необходимо для того, чтобы обрабатывались последние элементы столбцов матриц Min, Mout или Md.

Третий 24 D-триггер задержки переключения частоты с синхровходом С, информационным входом D и выходом Q задерживает на 1 такт частоты CLK сигнал, поступающий с выхода Q D-триггера 22. Это необходимо для корректного начала обработки элементов матрицы достижимости.

Первый 25 конъюнктор служит для конъюнкции информации, поступающей с первого выходного порта O1 ОЗУ 20 и со второго выходного порта O2 ОЗУ 21.

Второй 26 конъюнктор служит для конъюнкции информации, поступающей со второго выходного порта O2 ОЗУ 20 и с первого выходного порта O1 ОЗУ 21.

Третий 27 конъюнктор служит для конъюнкции информации, поступающей с первого выходного порта O1 ОЗУ 21 и со второго выходного порта O2 ОЗУ 21.

Первый 28 мультиплексор выбора частоты функционирования устройства переводит его из этапа записи элементов исходных данных в ОЗУ 20, 21 и 32 на этап формирования матрицы неполного параллелизма, при этом меняя частоту его работы.

Дизъюнктор 29 служит для дизъюнкции информации, поступающей с выходов конъюнкторов 25, 26 и 27.

Счетчик 30 номера строки предназначен для перебора соответствующих адресов содержимого ОЗУ 20, ОЗУ 21, первого однопортового ОЗУ 32 хранения матрицы достижимости, а также дешифрации своих выходных значений дешифратором 18 с целью образования стробов CE[N…1], поступающих на входы разрешения синхроимпульса триггеров матрицы 14.i,j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных. Он выбран с момента поступления первого строб-импульса цепи STROB до завершения считывания матрицы неполного параллелизма внешним устройством - ВУ, сбрасывается по приходу высокого уровня сигнала с выхода Q четвертого 36 D-триггера на вход clr счетчика 30. Выходы Q₀…Q_K содержат информацию о текущем номере обрабатываемой строки. При перевороте счетчика 30 номера строки на его выход ТС выдается соответствующий сигнал R_E.

Компаратор 31 сравнения с 0 осуществляет операцию сравнения значения со входа данных А[М…1] с нулевым и при выполнении равенства выдает на выход ZERO единичный уровень. Работа данного компаратора разрешается, когда с выхода Q D-триггера 24 на его вход разрешения сравнения EN поступает высокий уровень, показывающий, что загрузка исходных данных завершена.

Первое 32 однопортовое ОЗУ обработки матрицы достижимости размером N*M предназначено для операций с элементами матрицы достижимости. Запись данных, поступающих на входы DIN1…DINM ОЗУ 32, производится по единичному уровню на входе разрешения записи WE данного ОЗУ, считывание его порта А[К…1] осуществляется с выхода O1 по нулевому уровню на входе WE. Операции в ОЗУ 32 тактируются с помощью импульсов, поступающих на вход подачи частоты CLK.

Преобразователь 33 кода из параллельного в последовательный служит для организации побитной конъюнкции элементов матрицы достижимости с соответствующими им результатами значений F. Значение в параллельном коде поступает на входы DIN1…DINM преобразователя 33 и загружается по импульсам SYN с выхода мультиплексора 28, поступающим на вход загрузки LD данного преобразователя. Преобразование, тактируемое импульсами на входе частоты CLK преобразователя 33, осуществляется при наличии высокого уровня сигнала с выхода Q D-триггера 24 на входе разрешения частоты СЕ данного преобразователя. Сбрасывается преобразователь 33 по приходу высокого уровня сигнала с выхода Q четвертого 36 D-триггера на вход clr данного преобразователя. Данные в последовательном коде поступают с выхода преобразователя 33 DOUT.

Четвертый 34 конъюнктор служит для конъюнкции информации, поступающей с выхода DOUT преобразователя 33 кода из параллельного в последовательный и с выхода ZERO компаратора 31.

Преобразователь 35 кода из последовательного в параллельный формирует строки матрицы неполного параллелизма Md для записи во второе 37 однопортовое ОЗУ хранения матрицы неполного параллелизма. Преобразование, тактируемое импульсами на входе частоты CLK преобразователя 35, осуществляется при наличии высокого уровня сигнала с выхода Q D-триггера 24 на входе разрешения частоты СЕ данного преобразователя. Сбрасывается преобразователь 35 по приходу высокого уровня сигнала с выхода Q четвертого 36 D-триггера на вход clr данного преобразователя. Данные в последовательном коде поступают на вход SDIN преобразователя 35, преобразованные данные в параллельном коде могут быть считаны с выходов Р1…РМ.

Четвертый 36 D-триггер с информационным входом D, входом сброса clr и выходом Q служит для сброса шестого 39 D-триггера разрешения счета строк, а также генерирует сигнал STB общего сброса системы.

Второе 37 однопортовое ОЗУ хранения матрицы неполного параллелизма размером N*M предназначено для хранения элементов матрицы неполного параллелизма. Запись данных, поступающих на входы DIN1…DINM ОЗУ 37, производится по единичному уровню на входе разрешения записи WE данного ОЗУ, считывание порта А осуществляется с выхода O1 по нулевому уровню на входе WE. Операции в ОЗУ 37 тактируются с помощью импульсов, поступающих на вход подачи частоты CLK.

Пятый 38 D-триггер выработки условия готовности с синхровходом С, информационным входом D, входом сброса clr и выходом Q формирует сигнал RDY готовности матрицы неполного параллелизма для ВУ.

Шестой 39 D-триггер разрешения счета строк с синхровходом С, информационным входом D, входом сброса clr и выходом Q формирует сигнал RE разрешения счета счетчика 30 номера строки.

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

Вход 41 строба считывания выходных данных служит для подачи ВУ строба для считывания матрицы неполного параллелизма из ОЗУ 41.

Выходы 42.1…42.М выходных данных используются для передачи данных к ВУ.

Выход 43 признака наличия результата предназначен для оповещения ВУ о готовности результата.

Вход 44 подачи питания и выход 45 подачи "земли" служат для подачи "питания" Н и "земли" L соответственно на устройство для формирования матрицы неполного параллелизма 47.

Второй мультиплексор 46 служит для переключения с частоты записи ОЗУ 37 на частоту считывания, используемую при обмене с внешним устройством.

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

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

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

Запись входных данных из элементов матрицы однородной среды 1 в соответствующие триггеры матрицы 14 происходит по импульсам, приходящим со входа 9. При описании работы устройства будем считать, что положительный фронт первого из четырех импульсов цепи STROB совпадает положительным фронтом первого импульса тактовой частоты CLK на выходе генератора 15. Каждый из этих импульсов соответствует процедурам записи из элементов однородной среды в соответствующие триггеры матрицы 14 элементов матриц входных переменных, выходных переменных, матрицы достижимости и окончанию загрузки входных данных соответственно, то есть при первом импульсе STROB и CLK происходит запись из элементов однородной среды в триггеры матрицы 14 элементов матрицы входных переменных. При этом сбрасывается D-триггер 36, выход Q D-триггера 39 становится равным 1, что разрешает работу счетчика 30. По приходу первого импульса STROB выход счетчика 16 становится равным 1 и на выходе D1 дешифратора 17 формируется строб STB_IN. Значение STB_IN становится равным 1, поэтому двухпортовое ОЗУ 20 начинает работать в режиме записи. На выходе счетчика 30 появляется единица, на триггеры 1.1-1.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов СЕ 1=1, и в двухпортовое ОЗУ 21 записывается по первому адресу первая строка матрицы входных переменных.

На втором такте CLK выход счетчика 30 становится равным двум, на триггеры 2.1-2.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов СЕ2=1 и в двухпортовое ОЗУ 20 записывается по второму адресу вторая строка матрицы входных переменных. Так продолжается до тех пор, пока значение счетчика 30 не станет равным N.

На N-м такте CLK выход счетчика 30 становится равным N, на триггеры N.1-N.M матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов СЕМ=1, и в двухпортовое 20 ОЗУ записывается по N-му адресу N-я строка матрицы входных переменных. Матрица входных переменных записалась в двухпортовое ОЗУ 21. По отрицательному фронту N-го импульса значение STROB со входа 9 становится равным 0.

N+1-й импульс CLK совпадает с приходом второго импульса STROB со входа 9, по которому происходит запись из элементов однородной среды в элементы матрицы 14 элементов матрицы выходных переменных. Выходное значение счетчика 16 становится равным 2, поэтому на выходе дешифратора 17 формируется строб STB_OUT, при этом двухпортовое ОЗУ 21 начинает работать в режиме записи. Выход счетчика 30 становится равным единице, на триггеры 1.1-1.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов CE1=1, и в двухпортовое ОЗУ 22 записывается по первому адресу первая строка матрицы выходных переменных Mout.

На N+2-м такте CLK выход счетчика 30 становится равным двум, на триггеры 2.1-2.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов CE2=1, и в двухпортовое ОЗУ 21 записывается по второму адресу вторая строка матрицы входных переменных. Так продолжается до тех пор, пока значение счетчика 30 не станет равным N.

На 2N-м такте CLK выход счетчика 30 становится равным N, на триггеры N.1-N.M матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов CEN=1, и в двухпортовое ОЗУ 21 записывается по N-му адресу N-ная строка матрицы выходных переменных. Матрица выходных переменных записалась в двухпортовое ОЗУ 21 обработки матрицы выходных переменных. По отрицательному фронту 2N-го импульса значение STROB со входа 9 становится равным 0.

2N+1-й импульс CLK совпадает с приходом второго импульса STROB со входа 9, по нему происходит запись из элементов однородной среды в элементы матрицы 14 элементов матрицы достижимости. Выходное значение счетчика 16 становится равным 3, поэтому на выходе дешифратора 17 формируется строб STB_MD, при этом однопортовое ОЗУ 32 начинает работать в режиме записи. Выход счетчика 30 становится равным единице, на триггеры 1.1-1.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов СЕ 1=1, и в однопортовое ОЗУ 32 записывается по первому адресу первая строка матрицы достижимости.

На 2N+2-м такте CLK выход счетчика 30 становится равным двум, на триггеры 2.1-2.М матрицы 14 приходят с выхода дешифратора 18 разрешения синхроимпульсов СЕ2=1, и в двухпортовое ОЗУ 32 записывается по второму адресу вторая строка матрицы достижимости. Так продолжается до тех пор, пока значение счетчика 30 не станет равным N.

На 3N-м такте CLK выход счетчика 30 становится равным N, на триггеры N.1-N.M матрицы 14 приходят разрешения синхроимпульсов CEN=1, в двухпортовое ОЗУ 32 записывается по N-му адресу N-я строка матрицы достижимости. Матрица достижимости записалась в двухпортовое ОЗУ 32. По отрицательному фронту 2N-го импульса значение STROB становится равным 0.

3N+1-й импульс CLK совпадает с приходом четвертого импульса STROB, выходное значение счетчика 16 становится равным 4, строб STB_MD становится равным 0. При этом выходное значение IMP D-триггера 22 становится равным 1, что разрешает работу компаратора 31, преобразователей кодов 33 и 35. ОЗУ 20, 21 и 32 начинают работать в режиме считывания. Выход счетчика 30 становится равным 1, выход счетчика 19 остается в 1. Мультиплексор 28 коммутирует на выход SYN 3N+1 импульс частоты CLK. По нему из двухпортового 32 ОЗУ в преобразователь 33 кода из параллельного в последовательный считывается первая строка матрицы достижимости, а N-й бит из нее поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выходов O1 и O2 считывается первая строка матрицы входных переменных, а из двухпортового 21 ОЗУ с выходов O1 и O2 считывается первая строка матрицы выходных переменных. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 31 с нулевой и результат сравнения поступает на второй вход четвертого конъюнктора 34. Результат конъюнкции с выхода четвертого конъюнктора 34 записывается в преобразователь 35 кода из последовательного в параллельный как N-й бит первого слова.

На 3N+2-м такте CLK выходное значение BEG D-триггера 24 становится равным 1, что разрешает работу счетчика 19. На выход мультиплексора 28 начинает коммутироваться частота С_Е с выхода D-триггера 23. Значение счетчика 19 становится равным 2. По 3N+2-му импульсу CLK N-1-й бит первой строки матрицы достижимости из преобразователя 33 кодов из параллельного в последовательный поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается первая строка матрицы входных переменных, а с выхода O2 - вторая строка. Из двухпортового 21 ОЗУ с выхода O1 считывается первая строка матрицы выходных переменных, а с выхода O2 - вторая строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 31 с нулевой и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как N-1-й бит первого слова.

Значение счетчика 19 при 4N импульсе становится равным N. 1-й бит из первой строки матрицы достижимости из преобразователя 33 кодов из параллельного в последовательный поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается первая строка матрицы входных переменных, а с выхода O2 - N-я строка. Из двухпортового 21 ОЗУ с выхода O1 считывается первая строка матрицы выходных переменных, а с выхода O2 - N-я строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой, и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как 1-й бит. На выходе SYN счетчика 19 появляется 1. Значение входа RW для считывания матрицы неполного параллелизма внешним устройством равно 0, поэтому однопортовое 37 ОЗУ работает на запись. Так как RW=0, импульс SYN появляется на выходе мультиплексора 28 и инициирует считывание слова по адресу, соответствующему номеру обрабатываемой строки матрицы достижимости - первому, из преобразователя кода 35 из последовательного в параллельный в однопортовое 37 ОЗУ.

Выходное значение счетчика 19 при 4N+1 импульсе CLK становится равным единице. На выходе С_Е D-триггера 23 появляется 1. Так как BEG=1, то мультиплексор 28 коммутирует на выход SYN импульс С_Е. Значение счетчика 19 становится равным двум. Из однопортового 32 ОЗУ в преобразователь 33 кода из параллельного в последовательный считывается вторая строка, а N-й бит из второй строки матрицы достижимости поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается вторая строка матрицы входных переменных, а с выхода O2 - первая строка. Из двухпортового 21 ОЗУ с выхода O1 считывается вторая строка матрицы выходных переменных, а с выхода O2 - первая строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как N-й бит второго слова.

Значение счетчика 19 при 4N+2 импульсе становится равным 2. N-1-й бит из второй строки матрицы достижимости из преобразователя 33 кода из параллельного в последовательный поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выходов O1 и O2 считывается вторая строка матрицы входных переменных, а из двухпортового 21 ОЗУ с выходов O1 и O2 считывается вторая строка матрицы выходных переменных. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F-IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как N-1-й бит второго слова.

Значение счетчика 19 при 5N импульсе становится равным N. Значение счетчика 30 равно 2. N-й бит из второй строки поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается вторая строка матрицы входных переменных, а с выхода O2 - N-я строка. Из двухпортового 21 ОЗУ с выхода O1 считывается вторая строка матрицы выходных переменных, а с выхода O2 - N-я строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как первый бит второго слова. На выходе SYN счетчика 19 появляется 1. Значение входа RW для считывания матрицы неполного параллелизма внешним устройством равно 1, поэтому однопортовое 37 ОЗУ работает на запись. Так как RW=0, импульс SYN появляется на выходе мультиплексора 46 и инициирует считывание слова по адресу, соответствующему номеру обрабатываемой строки матрицы достижимости - второму, из преобразователя 35 кода из последовательного в параллельный в ОЗУ 37.

Так происходит до прихода импульса MN+3N+1. Выходное значение счетчика столбцов 19 при MN+3N+1-м импульсе CLK становится равным единице. На выходе С_Е D-триггера 23 появляется 1. Так как BEG=1, то мультиплексор 28 коммутирует на выход SYN импульс С_Е. Значение счетчика 30 становится равным N. Из однопортового 32 ОЗУ в преобразователь 33 кода из параллельного в последовательный считывается N-я строка, a N-й бит из второй строки матрицы достижимости поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается вторая строка матрицы входных переменных, а с выхода O2 - первая строка. Из двухпортового 21 ОЗУ с выхода O1 считывается вторая строка матрицы выходных переменных, а с выхода O2 - первая строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой, и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как N-й бит N-го слова.

Значение счетчика 19 при MN+3N+2-м импульсе становится равным 2. N-1-й бит из N-й строки матрицы достижимости из преобразователя 33 кода из параллельного в последовательный поступает на первый вход четертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выходов O1 и O2 считывается вторая строка матрицы входных переменных, а из двухпортового 21 ОЗУ с выходов O1 и O2 считывается вторая строка матрицы выходных переменных. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как N-1-й бит N-го слова.

Значение счетчика 19 при MN+4N-м импульсе становится равным N. Значение счетчика 30 равно N. N-й бит из второй строки поступает на первый вход четвертого 34 конъюнктора. При этом из двухпортового 20 ОЗУ с выхода O1 считывается вторая строка матрицы входных переменных, а с выхода O2 - N-я строка. Из двухпортового 21 ОЗУ с выхода O1 считывается вторая строка матрицы выходных переменных, а с выхода O2 - N-я строка. При этом при помощи конъюнкторов 25, 26, 27 и дизъюнктора 29 происходит вычисление значения F=IN1*OUT2+IN2*OUT1+OUT1*OUT2. Строка F сравнивается компаратором 32 с нулевой, и результат сравнения поступает на второй вход четвертого 34 конъюнктора. Результат конъюнкции с выхода четвертого 34 конъюнктора записывается в преобразователь 35 кода из последовательного в параллельный как первый бит N-го слова. На выходе ТС счетчика 19 появляется 1. Значение входа RW для считывания матрицы неполного параллелизма внешним устройством равно 1, поэтому однопортовое 37 ОЗУ работает на запись. Так как RW=1, импульс SYN появляется на выходе мультиплексора 44 и инициирует считывание слова по адресу, соответствующему номеру обрабатываемой строки матрицы достижимости - N-му, из преобразователя 35 кода из последовательного в параллельный в однопортовое 37 ОЗУ. Значение на выходе R_E счетчика 30 изменяется на 1, что вызывает появление 1 на выходе RDY D-триггера 38, что свидетельствует о том, что матрица неполного параллелизма сформирована и готова для считывания из однопортового 37 ОЗУ хранения матрицы неполного параллелизма внешним устройством ВУ.

Для того чтобы считать матрицу неполного параллелизма из однопортового 37 ОЗУ, ВУ должно подать уровень нуля на вход RW данного устройства, переводя тем самым однопортовое 37 ОЗУ в режим считывания и коммутируя на его вход CLK частоту с выхода мультиплексора 28, а также синхронизировать частоту своей работы с частотой CLK работы устройства 47. По окончании считывания данных ВУ должно установить RW в 1, что ведет к сбросу счетчиков 16, 19, 30, D-триггера 22 и преобразователей кодов 33 и 35, сбросу D-триггера 39, то есть запрету счета счетчика 30. Происходит возврат устройства 47 в начальное состояние ожидания загрузки исходных данных.

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

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

Устройство для формирования матрицы неполного параллелизма, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, отличающееся тем, что в него дополнительно введен блок формирования матрицы неполного параллелизма, содержащий матрицу из (i,j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, тактовый генератор, счетчик импульсов стробирования загрузки исходных данных, первый дешифратор номера строба, второй дешифратор номера строки, счетчик номера столбца, первое двухпортовое ОЗУ обработки матрицы входных переменных, второе двухпортовое ОЗУ обработки матрицы выходных переменных, первый D-триггер с инверсным синхровходом, второй D-триггер задержки счета столбцов, третий D-триггер задержки переключения частоты, первый конъюнктор, второй конъюнктор, третий конъюнктор, первый мультиплексор выбора частоты функционирования устройства, дизъюнктор, счетчик номера строки, компаратор сравнения с нулем, первое однопортовое ОЗУ обработки матрицы достижимости, преобразователь кода из параллельного в последовательный, четвертый конъюнктор, преобразователь кода из последовательного в параллельный, четвертый D-триггер, второе однопортовое ОЗУ хранения матрицы неполного параллелизма, пятый D-триггер выработки условия готовности, шестой D-триггер разрешения счета строк, второй мультиплексор, причем информационные входы матрицы из (i,j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы из (i,j) (1=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, входы сброса R матрицы из (i,j) (1=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с выходом Q третьего D-триггера задержки переключения частоты, на вход тактового генератора подаются сигналы со входов подачи "питания" и подачи "земли", выход тактового генератора соединен с входами подачи частоты первого двухпортового ОЗУ обработки матрицы входных переменных, второго двухпортового ОЗУ обработки матрицы выходных переменных, счетным входом счетчика номера столбца, синхровходом второго D-триггера задержки счета столбцов, синхровходом третьего D-триггера задержки переключения частоты, первым входом первого мультиплексора выбора частоты функционирования устройства, первым входом второго мультиплексора, входом подачи частоты преобразователя кода из параллельного в последовательный, входом подачи частоты преобразователя кода из последовательного в параллельный, входом подачи частоты первого однопортового ОЗУ обработки матрицы достижимости и выходом синхронизирующей частоты устройства соответственно, вход CLK счетчика импульсов стробирования загрузки исходных данных соединен с входом управления записью устройства, вход CLR счетчика импульсов стробирования загрузки исходных данных соединен с выходом Q четвертого D-триггера, выходы Q1…QK счетчика импульсов стробирования загрузки исходных данных соединены с входами А1…АК первого дешифратора номера строба, выход D1 первого дешифратора номера строба соединен с входом WE первого двухпортового ОЗУ обработки матрицы входных переменных, выход D2 первого дешифратора номера строба соединен с входом WE управления записью/считыванием второго двухпортового ОЗУ обработки матрицы выходных переменных, выход D3 первого дешифратора номера строба соединен с входом WE первого однопортового ОЗУ обработки матрицы достижимости и инверсным синхровходом С первого D-триггера с инверсным синхровходом соответственно, входы А1…АК второго дешифратора номера строки соединены с соответствующими выходами Q1…QK счетчика номера строки, выходы D1…DN второго дешифратора номера строки соединены с соответствующими входами CE1…CEN разрешения синхроимпульса D-триггеров строк матрицы из (i,j) (i=1, 2, …, N, j=1, 2, …, М) D-триггеров синхронизации записи входных данных, входы DIN1…DINM первого двухпортового ОЗУ обработки матрицы входных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i,j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта соединены с соответствующими выходами Q1…QK счетчика номера строки, адресные входы В1…ВК второго порта соединены с соответствующими выходами Q1…QK счетчика номера столбца, выход O1 первого порта первого двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом первого конъюнктора, выход O2 второго порта первого двухпортового ОЗУ обработки матрицы входных переменных соединен с первым входом второго конъюнктора, входы DIN[M…1] второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i,j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, адресные входы А1…АК первого порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика номера строки, адресные входы В1…ВК второго порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединены с соответствующими выходами Q1…QK счетчика номера столбца, выход O1 первого порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом второго конъюнктора и с первым входом третьего конъюнктора соответственно, выход O2 второго порта второго двухпортового ОЗУ обработки матрицы выходных переменных соединен с вторым входом первого конъюнктора и со вторым входом третьего конъюнктора соответственно, вход CLR счетчика номера столбца соединен с выходом Q четвертого D-триггера, выход переполнения ТС счетчика номера столбца соединен с информационным входом второго D-триггера задержки счета столбцов, вход подачи питания Н соединен с информационным входом D первого D-триггера с инверсным синхровходом, с информационным входом D четвертого D-триггера, а также с информационным входом D шестого D-триггера разрешения счета строк соответственно, вход CLR первого D-триггера с инверсным синхровходом соединен с выходом Q четвертого D-триггера, выход Q первого D-триггера с инверсным синхровходом соединен с информационным входом D третьего D-триггера задержки переключения частоты, выход Q второго D-триггера задержки счета столбцов соединен со вторым входом первого мультиплексора выбора частоты функционирования устройства, выход Q третьего D-триггера задержки переключения частоты соединен с коммутирующим входом первого мультиплексора выбора частоты функционирования устройства, со входом СЕ счетчика номера столбца, со входом EN компаратора сравнения с 0, со входом СЕ преобразователя кода из параллельного в последовательный, со входом СЕ преобразователя кода из последовательного в параллельный и с входом D пятого D-триггера выработки условия готовности соответственно, выход первого конъюнктора соединен с первым входом дизъюнктора, выход второго конъюнктора соединен со вторым входом дизъюнктора, выход третьего конъюнктора соединен с третьим входом дизъюнктора, выход первого мультиплексора выбора частоты функционирования устройства соединен с синхровходом CLK счетчика номера строки, с входом LD преобразователя кода из параллельного в последовательный, и со вторым входом второго мультиплексора соответственно, выход дизъюнктора соединен с входом А[М…1] компаратора сравнения с 0, вход СЕ счетчика номера строки соединен с выходом Q шестого D-триггера разрешения счета строк, вход CLR счетчика номера строки соединен с выходом Q четвертого D-триггера, выходы Q1…QK счетчика номера строки соединены с соответствующими адресными входами А1…АК второго однопортового ОЗУ хранения матрицы неполного параллелизма и с соответствующими адресными входами А1…АК первого однопортового ОЗУ обработки матрицы достижимости, выход ТС переполнения счетчика номера строки соединен с синхровходом С пятого D-триггера выработки условия готовности, выход ZERO компаратора сравнения с нулем соединен со вторым входом четвертого конъюнктора, входы DIN1…DINM первого однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими выходами В11…В1М, В21…В1М, BN1…BNM матрицы из (i,j) (i=1, 2, …, N, j=1, 2, …, М) D-триггеров синхронизации записи входных данных, вход WE первого однопортового ОЗУ хранения матрицы достижимости соединен с выходом D3 первого дешифратора номера строба, выходы O1… ON первого однопортового ОЗУ хранения матрицы достижимости соединены с соответствующими входами DIN1…DINM преобразователя кода из параллельного в последовательный соответственно, выход DOUT преобразователя кода из параллельного в последовательный соединен с первым входом четвертого конъюнктора, выход четвертого конъюнктора соединен со входом SDIN преобразователя кода из последовательного в параллельный, вход CLR преобразователя кода из последовательного в параллельный соединен с выходом Q четвертого D-триггера, выходы Р1…РМ преобразователя кода из последовательного в параллельный соединены с соответствующими входами DIN1…DINM второго однопортового ОЗУ хранения матрицы неполного параллелизма, синхровход С четвертого D-триггера соединен с входом подачи строба для считывания матрицы неполного параллелизма, вход CLR четвертого D-триггера соединен с входом управления записью устройства, выход Q четвертого D-триггера соединен с входом CLR шестого D-триггера разрешения счета строк, а также с входом CLR сброса пятого D-триггера выработки условия готовности соответственно, вход подачи строба для считывания матрицы неполного параллелизма соединен с входом WE второго однопортового ОЗУ хранения матрицы неполного параллелизма, с коммутативным входом второго мультиплексора, а также с синхровходом С четвертого D-триггера соответственно, выходы MNP1…MNPM второго однопортового ОЗУ хранения матрицы неполного параллелизма соединены с соответствующими выходами с 1-го по М-й считывания матрицы неполного параллелизма, выход Q пятого D-триггера выработки условия готовности соединен с выходом готовности устройства, выход второго мультиплексора соединен с входом подачи частоты CLK второго однопортового ОЗУ хранения матрицы неполного параллелизма.