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

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

Иллюстрации

Показать все

Реферат

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

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

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

Наиболее близким к предлагаемому устройству по технической сущности является устройство для формирования матрицы неполного параллелизма, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход, вход установки, блок формирования матрицы неполного параллелизма (патент РФ 2421804, кл. G06F17/50, опубл. 20.06.2011, Бюл. №17).

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

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

Техническая задача решается тем, что в устройство для оценки размещения по критериям суммарной длины ребер и максимальной длины ребра, содержащее матрицу из 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-триггеров синхронизации записи входных данных, матрицу из (i.j) (i=1,2,…,N, j=1,2,…,M) элементов ИЛИ, тактовый генератор, умножитель частоты, счетчик импульсов стробирования загрузки исходных данных, первый дешифратор номера строба, второй дешифратор номера строки, третий дешифратор номера столбца, счетчик номера строки, счетчик номера столбца, первый элемент ИЛИ формирования сигнала сброса счетчика номера строки, второй элемент ИЛИ формирования сигнала сброса счетчика номера столбца, первое однопортовое ОЗУ хранения матрицы выходных переменных, второе однопортовое ОЗУ хранения матрицы входных переменных, сдвиговый регистр, третий элемент ИЛИ формирования сигнала сброса сдвигового регистра, первый конъюнктор, элемент сравнения с нулем, первый регистр хранения номера столбца матрицы выходных переменных, второй регистр хранения номера столбца матрицы выходных переменных, первый D-триггер, первый элемент И-НЕ, первый мультиплексор выбора номера столбца, второй мультиплексор выбора номера столбца, третье однопортовое ОЗУ хранения транспонированной матрицы достижимости, четвертое однопортовое ОЗУ хранения транспонированной матрицы входных переменных, четырехпортовое ОЗУ хранения транспонированной матрицы выходных переменных, четвертый элемент ИЛИ, второй элемент И, второй D-триггер, элемент сравнения для формирования сигнала готовности результата, пятое однопортовое ОЗУ хранения матрицы неполного параллелизма, причем информационные входы матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, на вход тактового генератора подаются сигналы со входов H и L устройства, выход тактового генератора соединен c входом умножителя частоты, с входом подачи частоты счетчика номера строки, с входом подачи частоты счетчика номера столбца, с входами подачи частоты первого однопортового ОЗУ хранения матрицы входных переменных, второго однопортового ОЗУ хранения матрицы выходных переменных, третьего однопортового ОЗУ хранения транспонированной матрицы достижимости, четвертого однопортового ОЗУ хранения транспонированной матрицы входных переменных, первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных, пятого однопортового ОЗУ хранения матрицы неполного параллелизма, выходом CLK устройства, выход CLK2 умножителя частоты соединен с синхровходом сдвигового регистра, сигнал STROB входа управления записью устройства соединен с синхровходом счетчика номера строба, выход счетчика номера строба соединен с входом дешифратора номера строба, первый выход дешифратора номера строба STB_IN1 соединен c входом разрешения записи второго однопортового ОЗУ хранения матрицы входных переменных и первым входом первого элемента ИЛИ, второй выход дешифратора номера строба STB_IN2 соединен c входом разрешения записи четвертого однопортового ОЗУ хранения транспонированной матрицы входных переменных, первым входом второго элемента ИЛИ, входом выбора первого мультиплексора выбора номера столбца, третий выход дешифратора номера строба STB_OUT1 соединен c входом разрешения записи первого однопортового ОЗУ хранения матрицы выходных переменных и вторым входом первого элемента ИЛИ, четвертый выход дешифратора номера строба STB_OUT2 соединен c входом разрешения записи первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных, вторым входом второго элемента ИЛИ, входом выбора второго мультиплексора выбора номера столбца, пятый выход дешифратора номера строба STB_MD соединен c входом разрешения записи третьего однопортового ОЗУ хранения транспонированной матрицы достижимости и третьим входом второго элемента ИЛИ, шестой выход дешифратора номера строба STB_MNP соединен c третьим входом первого элемента ИЛИ, синхровходом второго D-триггера, выход SBRR первого элемента ИЛИ соединен с входом очистки счетчика номера строки, первым входом третьего элемента ИЛИ, выход SBRC второго элемента ИЛИ соединен с входом сброса счетчика номера столбца, выход счетчика номера строки соединен с входом дешифратора номера строки, первым входом элемента сравнения, адресными входами первого однопортового ОЗУ хранения матрицы выходных переменных, второго однопортового ОЗУ хранения матрицы входных переменных, пятого однопортового ОЗУ хранения матрицы неполного параллелизма, выходы дешифратора номера строки соединены с соответствующими первыми входами элементов ИЛИ матрицы D-триггеров, выход счетчика номера столбца соединен с входом дешифратора номера столбца, адресным входом третьего однопортового ОЗУ хранения транспонированной матрицы достижимости, вторым входом первого мультиплексора выбора номера столбца, вторым входом второго мультиплексора выбора номера столбца, выходы дешифратора номера столбца соединены с соответствующими вторыми входами элементов ИЛИ матрицы D-триггеров, выходы элементов ИЛИ матрицы D-триггеров соединены с входами разрешения вывода соответствующих D-триггеров матрицы, входы DIN1…DINM первого однопортового ОЗУ хранения матрицы выходных переменных соединены с соответствующими выходами B11…B1M, B21…B1M, BN1…BNM матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINM второго однопортового ОЗУ хранения матрицы входных переменных соединены с соответствующими выходами B11…B1M, B21…B1M, BN1…BNM матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN третьего однопортового ОЗУ хранения транспонированной матрицы достижимости соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN четвертого однопортового ОЗУ хранения транспонированной матрицы входных переменных соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, выход первого однопортового ОЗУ хранения матрицы выходных переменных соединен с первым входом первого мультиплексора выбора номера столбца, с первым входом второго мультиплексора выбора номера столбца, выход первого мультиплексора выбора номера столбца соединен с адресным входом четвертого однопортового ОЗУ хранения транспонированной матрицы входных переменных, выход второго мультиплексора выбора номера столбца соединен с первым адресным входом первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных, выход второго однопортового ОЗУ хранения матрицы входных переменных соединен с первым входом первого элемента И, выход третьего элемента ИЛИ соединен с входом сброса сдвигового регистра, выход сдвигового регистра соединен со вторым входом первого элемента И и с входами данных первого и второго регистров формирования номера столбца, выход первого элемента И соединен с входом элемента сравнения с нулем, инверсный выход элемента сравнения с нулем соединен с входом разрешения записи первого регистра формирования номера столбца, информационным входом первого D-триггера и первым входом первого элемента И-НЕ, выход первого D-триггера соединен со вторым входом первого элемента И-НЕ, выход первого элемента И-НЕ соединен с входом разрешения записи второго регистра выбора номера столбца, входом сброса первого D-триггера и вторым входом третьего элемента ИЛИ, выход первого регистра формирования номера столбца соединен с третьим адресным входом первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных, выход второго регистра формирования номера столбца соединен со вторым адресным входом первого четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных, выход третьего однопортового ОЗУ хранения транспонированной матрицы достижимости соединен с первым входом второго элемента И, выход четвертого однопортового ОЗУ хранения транспонированной матрицы входных переменных соединен с первым входом четвертого элемента ИЛИ, первый выход первого однопортового ОЗУ хранения транспонированной матрицы выходных переменных соединен со вторым входом четвертого элемента ИЛИ, второй выход первого однопортового ОЗУ хранения транспонированной матрицы выходных переменных соединен с третьим входом четвертого элемента ИЛИ, третий выход первого однопортового ОЗУ хранения транспонированной матрицы выходных переменных соединен с четвертым входом четвертого элемента ИЛИ, выход четвертого элемента ИЛИ соединен со вторым входом второго элемента И, выход второго элемента И соединен с входом данных пятого однопортового ОЗУ хранения матрицы неполного параллелизма, информационный вход второго D-триггера соединен со входом H устройства, выход второго D-триггера соединен с входом разрешения элемента сравнения, второй вход элемента сравнения соединен с входом количества операторов N устройства, выход элемента сравнения соединен с выходом RDY устройства, вход разрешения записи пятого однопортового ОЗУ хранения матрицы неполного параллелизма соединен с входом RW устройства, выход пятого однопортового ОЗУ хранения матрицы неполного параллелизма соединен с выходом MNP устройства.

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

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

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

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

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

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

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

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

.

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

Выявляя информационные зависимости между операторами p_i и p_j программы при Md_i,j=1 получаем матрицу неполного параллелизма (фиг.2д) MNP=, где , , отражающую полный набор информационных зависимостей между всеми операторами программы.

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

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

Матрицы входных и выходных переменных, а также матрица достижимости отображаются однородной средой, содержащей 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 устройства, а также блок 52 ускоренного вычисления матрицы неполного параллелизма, содержащий матрицу 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, матрицу из (i.j) (i=1,2,…,N, j=1,2,…,M) элементов ИЛИ, тактовый генератор 15, умножитель частоты 16, счетчик импульсов стробирования загрузки исходных данных 17, первый дешифратор номера строба 18, второй дешифратор номера строки 20, третий дешифратор номера столбца 23, счетчик номера строки 19, счетчик номера столбца 22, первый элемент ИЛИ 21 формирования сигнала сброса счетчика номера строки, второй элемент ИЛИ 24 формирования сигнала сброса счетчика номера столбца, первое однопортовое ОЗУ 26 хранения матрицы выходных переменных, второе однопортовое ОЗУ 27 хранения матрицы входных переменных, сдвиговый регистр 28, третий элемент ИЛИ 25 формирования сигнала сброса сдвигового регистра 28, первый конъюнктор 29, элемент сравнения с нулем 30, первый регистр хранения номера столбца 33 матрицы выходных переменных, второй регистр хранения номера столбца 39 матрицы выходных переменных, первый D-триггер 34, первый элемент И-НЕ 35, первый мультиплексор 31 выбора номера столбца, второй мультиплексор 32 выбора номера столбца, третье однопортовое ОЗУ 36 хранения транспонированной матрицы достижимости, четвертое однопортовое ОЗУ 37 хранения транспонированной матрицы входных переменных, четырехпортовое ОЗУ 38 хранения транспонированной матрицы выходных переменных, четвертый элемент ИЛИ 40, второй элемент И 41 , второй D-триггер 42, элемент сравнения 43 для формирования сигнала готовности результата, пятое однопортовое ОЗУ 44 хранения матрицы неполного параллелизма, причем информационные входы матрицы 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-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, на вход тактового генератора 15 подаются сигналы со входов H 50 и L 51 устройства 52, выход тактового генератора 15 соединен c входом умножителя частоты 16, с входом подачи частоты счетчика номера строки 19, с входом подачи частоты счетчика номера столбца 22, с входами подачи частоты первого однопортового ОЗУ 26 хранения матрицы входных переменных, второго однопортового ОЗУ 27 хранения матрицы выходных переменных, третьего однопортового ОЗУ 36 хранения транспонированной матрицы достижимости, четвертого однопортового ОЗУ 37 хранения транспонированной матрицы входных переменных, первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных, пятого однопортового ОЗУ 44 хранения матрицы неполного параллелизма, выходом CLK 49 устройства 52, выход CLK2 умножителя частоты 16 соединен с синхровходом сдвигового регистра 28, сигнал STROB входа управления записью устройства 52 соединен с синхровходом счетчика номера строба 17, выход счетчика номера строба 17 соединен с входом дешифратора 18 номера строба, первый выход дешифратора 18 номера строба STB_IN1 соединен c входом разрешения записи второго однопортового ОЗУ 27 хранения матрицы входных переменных и первым входом первого элемента ИЛИ 21, второй выход дешифратора 18 номера строба STB_IN2 соединен c входом разрешения записи четвертого однопортового ОЗУ 37 хранения транспонированной матрицы входных переменных, первым входом второго элемента ИЛИ 24, входом выбора первого мультиплексора 31 выбора номера столбца, третий выход дешифратора 18 номера строба STB_OUT1 соединен c входом разрешения записи первого однопортового ОЗУ 26 хранения матрицы выходных переменных и вторым входом первого элемента ИЛИ 21, четвертый выход дешифратора 18 номера строба STB_OUT2 соединен c входом разрешения записи первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных, вторым входом второго элемента ИЛИ 24, входом выбора второго мультиплексора 32 выбора номера столбца, пятый выход дешифратора 18 номера строба STB_MD соединен c входом разрешения записи третьего однопортового ОЗУ 36 хранения транспонированной матрицы достижимости и третьим входом второго элемента ИЛИ 24, шестой выход дешифратора 18 номера строба STB_MNP соединен c третьим входом первого элемента ИЛИ 21, синхровходом второго D-триггера 42, выход SBRR первого элемента ИЛИ 21 соединен с входом очистки счетчика 19 номера строки, первым входом третьего элемента ИЛИ 25, выход SBRC второго элемента ИЛИ 24 соединен с входом сброса счетчика 22 номера столбца, выход счетчика 19 номера строки соединен с входом дешифратора 20 номера строки, первым входом элемента сравнения 43, адресными входами первого однопортового ОЗУ 26 хранения матрицы выходных переменных, второго однопортового ОЗУ 27 хранения матрицы входных переменных, пятого однопортового ОЗУ 44 хранения матрицы неполного параллелизма, выходы дешифратора 20 номера строки соединены с соответствующими первыми входами элементов ИЛИ матрицы 14 D-триггеров, выход счетчика 22 номера столбца соединен с входом дешифратора 23 номера столбца, адресным входом третьего однопортового ОЗУ 36 хранения транспонированной матрицы достижимости, вторым входом первого мультиплексора 31 выбора номера столбца, вторым входом второго мультиплексора 32 выбора номера столбца, выходы дешифратора 23 номера столбца соединены с соответствующими вторыми входами элементов ИЛИ матрицы 14 D-триггеров, выходы элементов ИЛИ матрицы 14 D-триггеров соединены с входами разрешения вывода соответствующих D-триггеров матрицы 14, входы DIN1…DINM первого однопортового ОЗУ 26 хранения матрицы выходных переменных соединены с соответствующими выходами B11…B1M, B21…B1M, BN1…BNM матрицы 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINM второго однопортового ОЗУ 27 хранения матрицы входных переменных соединены с соответствующими выходами B11…B1M, B21…B1M, BN1…BNM матрицы 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN третьего однопортового ОЗУ 36 хранения транспонированной матрицы достижимости соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN четвертого однопортового ОЗУ 37 хранения транспонированной матрицы входных переменных соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, входы DIN1…DINN первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных соединены с соответствующими выходами B11…BN1, B12…BN2, B1M…BNM матрицы 14 из (i.j) (i=1,2,…,N, j=1,2,…,M) D-триггеров синхронизации записи входных данных, выход первого однопортового ОЗУ 26 хранения матрицы выходных переменных соединен с первым входом первого мультиплексора 31 выбора номера столбца, с первым входом второго мультиплексора 32 выбора номера столбца, выход первого мультиплексора 31 выбора номера столбца соединен с адресным входом четвертого однопортового ОЗУ 37 хранения транспонированной матрицы входных переменных, выход второго мультиплексора 32 выбора номера столбца соединен с первым адресным входом первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных, выход второго однопортового ОЗУ 27 хранения матрицы входных переменных соединен с первым входом первого элемента И 29, выход третьего элемента ИЛИ 25 соединен с входом сброса сдвигового регистра 28, выход сдвигового регистра 28 соединен со вторым входом первого элемента И 29, и с входами данных первого 33 и второго 39 регистров формирования номера столбца, выход первого элемента И 29 соединен с входом элемента сравнения с нулем 30, инверсный выход элемента сравнения с нулем 30 соединен с входом разрешения записи первого регистра 33 формирования номера столбца, информационным входом первого D-триггера 34, и первым входом первого элемента И-НЕ 35, выход первого D-триггера 34 соединен со вторым входом первого элемента И-НЕ 35, выход первого элемента И-НЕ 35 соединен с входом разрешения записи второго 39 регистра выбора номера столбца, входом сброса первого D-триггера 34 и вторым входом третьего элемента ИЛИ 25, выход первого регистра 33 формирования номера столбца соединен с третьим адресным входом первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных, выход второго 39 регистра формирования номера столбца соединен со вторым адресным входом первого четырехпортового ОЗУ 38 хранения транспонированной матрицы выходных переменных, выход третьего однопортового ОЗУ 37 хранения транспонированной матрицы достижимости соединен с первым входом второго элемента И 41, выход четвертого однопортового ОЗУ 37 хранения транспонированной матрицы входных переменных соединен с первым входом четвертого элемента ИЛИ 40, первый выход первого однопортового ОЗУ 38 хранения транспонированной матрицы выходных переменных соединен со вторым входом четвертого элемента ИЛИ 40, второй выход первого однопортового ОЗУ 38 хранения транспонированной матрицы выходных переменных соединен с третьим входом четвертого элемента ИЛИ 40, третий выход первого однопортового ОЗУ 38 хранения транспонированной матрицы выходных переменных соединен с четвертым входом четвертого элемента ИЛИ 40, выход четвертого элемента ИЛИ 40 соединен со вторым входом второго элемента И 41, выход второго элемента И 41 соединен с входом данных пятого однопортового ОЗУ 44 хранения матрицы неполного параллелизма, информационный вход второго D-триггера 42 соединен со входом H 50 устройства 52, выход второго D-триггера 42 соединен с входом разрешения элемента сравнения 43, второй вход элемента сравнения 43 соединен с входом количества операторов N 48 устройства 52 , выход элемента сравнения 43 соединен с выходом RDY 45 устройства 52, вход разрешения записи пятого однопортового ОЗУ 44 хранения матрицы неполного параллелизма соединен с входом RW 47 устройства 52, выход пятого однопортового ОЗУ 44 хранения матрицы неполного параллелизма соединен с выходом MNP 46 устройства 52.

Назначение элементов и блоков устройства (фиг.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 в первое 26 однопортовое ОЗУ хранения матрицы выходных переменных, второе 27 однопортовое ОЗУ хранения матрицы входных переменных, третье 36 однопортовое ОЗУ хранения транспонированной матрицы достижимости, четвертое 37 однопортовое ОЗУ хранения транспонированной матрицы входных переменных и первое 38 четырехпортовое ОЗУ хранения транспонированной матрицы выходных переменных.

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

Умножитель частоты 16 служит для генерации тактовых сигналов CLK2 устройства ускоренного вычисления матрицы неполного параллелизма.

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

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

Cчетчик 19 номера строки предназначен для перебора соответствующих адресов содержимого ячеек первого 26 однопортового ОЗУ хранения матрицы выходных переменных, второго 27 однопортового ОЗУ хранения матрицы входных переменных, пятого 44 однопортового ОЗУ хранения матрицы неполного параллелизма. Счетчик 19 сбрасывается по приходу высокого уровня сигнала с выхода первого 21 элемента ИЛИ.

Второй 20 дешифратор номера строки предназначен для выработки сигналов CR[N..1] для разрешения загрузки данных из матрицы 14 D-триггеров.

Первый 21 элемент ИЛИ предназначен для формирования сигнала сброса счетчика 19 номера строки в зависимости от номера строба, поступающего на его входы с выхода дешифратора 18.

Cчетчик 22 номера столбца предназначен для перебора соответствующих адресов содержимого ячеек третьего 36 однопортового ОЗУ хранения транспонированной матрицы достижимости, четвертого 37 однопортового ОЗУ хранения транспонированной матрицы входных переменных, первого 38 четырехпортового ОЗУ хранения транспонированной матрицы выходных переменных. Счетчик 22 сбрасывается по приходу высокого уровня сигнала с выхода второго 24 элемента ИЛИ.

Третий 23 дешифратор номера столбца предназначен для выработки сигналов CC[M..1] для разрешения загрузки данных из матрицы 14 D-триггеров.

Второй 24 элемент ИЛИ предназначен для формирования сигнала сброса счетчика 22 номера столбца в зависимости от номера строба, поступающего на его входы с выхода дешифратора 18.

Третий 25 элемент ИЛИ предназначен для формирования сигнала сброса сдвигового регистра 28.

Первое 26 однопортовое ОЗУ хранения матрицы выходных переменных размером N*M (N – число операторов обрабатываемого фрагмента программы, М – число входных переменных на этом участке) предназначено для операций с элементами матрицы Mout входных переменных. Запись данных, поступающих на входы DIN1.. DINM ОЗУ 26, производится по единичному уровню на входе разрешения записи WE, считывание данных осуществляется по нулевому уровню входа разрешения записи WE. Операции чтения/записи тактируются с помощью импульсов, поступающих на вход CLK подачи частоты ОЗУ 26.

Второе 27 однопортовое ОЗУ хранения матрицы входных переменных размером N*M (N – число операторов обрабатываемого фрагмента программы, М – число входных переменных на этом участке) предназначено для операций с элементами матрицы Min входных переменных. Запись данных, поступающих на входы DIN1.. DINM ОЗУ 27, производится по единичному уровню на входе разрешения записи WE, считывание данных осуществляется по нулевому уровню входа разрешения записи WE. Операции чтения/записи тактируются с помощью импульсов, поступающих на вход CLK подачи частоты ОЗУ 27.

Сдвиговый регистр 28 предназначен для формирования входного значения для элемента И 29. При поступлении единичного сигнала на вход RES регистра происходит его сброс в единичное значение. Сдвиг производится по положительному фронту на входе CLK сдвигового регистра 28.

Первый элемент И 29 производит операцию побитовой конъюнкции значений, поступающих на его входы. На первый вход элемента И 29 поступает текущая строка матрицы входных переменных. На второй вход элемента И 29 поступает выходное значение сдвигового регистра 28.

Элемент 30