Устройство для формирования матрицы неполного параллелизма

Устройство для формирования матрицы неполного параллелизма

Иллюстрации

Показать все

Реферат

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

Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с.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 до завершения считывания матрицы неполного параллелизма внешним устройством - ВУ, сбрасывается по приходу высокого уровня си