Матричный процессор Советский патент 1990 года по МПК G06F15/173 

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

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

ности с блока 7 по шине 15 передается 30 в подлежащую обработке порцию данных

в блок 9 памяти, где фиксируется и передается по линиям 38 в матрицу 10 узлов обработки.

В матрице 10 узлов обработки при помощи блока фиксации обнуления мат- 35 рицы производится оценка активности всего фрагмента. Если массив битов активности фрагмента состоит из одних нулей, фрагмент является неактивным, т.е. обработке не подлежит, если в 40 массиве есть хотя бы один бит активности, фрагмент является активным. Аналогичным образом непрерывно, один за другим, вводятся следующие фрагменты, осуществляются процедура обхо- 45 да окрестности каждого, формирование массива битов активности каждого, оценка активности каждого фрагмента и запись собственно каждого фрагменс последующим выполнением очередного этапа алгоритма обработки одновременно всех упакованных в порцию активных элементов целого ряда фрагментов. Процедура упаковки порции данных складывается из подготовки группы рабочих масок активности данной группы активных фрагментов, масок активных остатков и компоновки порции данных. Подготовка группы масок активных остатков производится следующим образом. Массив битов активности первого фрагмента данной группы активных фрагментов считывается с блока 9 памяти по линиям 38 и вводится в матрицу 10, где элементы данного массива фиксируются в аккумуляторах узлов 75 обработки. Затем считывается массив битов активности второго фрагмента данной

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

в подлежащую обработке порцию данных

с последующим выполнением очередного этапа алгоритма обработки одновременно всех упакованных в порцию активных элементов целого ряда фрагментов. Процедура упаковки порции данных складывается из подготовки группы рабочих масок активности данной группы активных фрагментов, масок активных остатков и компоновки порции данных. Подготовка группы масок активных остатков производится следующим образом. Массив битов активности первого фрагмента данной группы активных фрагментов считывается с блока 9 памяти по линиям 38 и вводится в матрицу 10, где элементы данного массива фиксируются в аккумуляторах узлов 75 обработки. Затем считывается массив битов активности второго фрагмента данной

Изобретение относится к области вычислительной техники, в частности к устройствам для обработки больших массивов данных изображений. Цель изобретения - повышение быстродействия за счет предварительной оценки активности элементов массива информации и исключение из процесса обработки неактивных элементов одновременно с обработкой предыдущей порции активных элементов. Цель достигается тем, что матричный процессор содержит блок 1 ввода-вывода, блок 2 задания формата, двунаправленный коммутатор 3, блок 4 флагментации, блок 5 опережающей подготовки данных , узел 6 сдвига, блок 7 распознования активных элементов кадра, матрицу 8 размером N ^. N, где N - линейный размер обрабатываемого кадра, элементов И, блок 9 памяти, матрицу размером N ^. N узлов обработки, блок 11 буферных повторителей, первый 12 и второй 13 блоки управления. 5 з.п. ф-лы, 18 ил.

та, его массивов значении окрестности 50 группы активных фрагментов и в матрии его массива битов активности в блок 9 памяти. Причем, если в результате определения активности фрагмента выясняется, что он неактивен и обработке не подлежит, блоки 13 и 12 управ- ее ления организуют его пересылку из блока 9 памяти по линиям шины 15 в блок 5 опережающей подготовки данных, а на место его размещения и размещения

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

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

10

15

11153Н6.6

массивов битов активности первого и второго фрагментов с фиксацией резуль - тата в аккумуляторах узлов 75 обработки. После этого с блока 9 памяти считывается массив битов активности третьего активного фрагмента и выполняется конъюнкция его соответствующих значений и значений содержимого аккумуляторов матрицы 10. Результат конъюнкции, являющийся маской активного остатка третьего фрагмента, проверяется на равенство нулю и фиксируется в блоке 9 памяти, после чего в матрице 10 выполняется дизъюнкция соответствующих значений массива битов активности третьего фрагмента и содержимого аккумуляторов, результат которой заносится в аккумуляторы узлов 75. Эта процедура продолжается с четвертым, пятым и т.д. фрагментами аналогичным образом до момента появления критерия достаточности, которым может служить в простейшем случае установленное максимальное число неравных нулю активных остатков, подсчитываемых блоком 13. После достижения критерия достаточности блок 13 приступает к подготовке рабочих масок активности данной группы активных фрагментов, для чего поочередно выполняет функцию неравнозначности элементов массивов битов активности с элементами соответствующих масок остатков данной группы ак12

ким образом, производится логическое сложение неперекрывающихся активных зон фрагментов данной группы. Области перекрытия активных зон вместе с неактивными зонами отсекаются соответствующими масками активности всех Фрагментов данной группы за исключе- чением первого фрагмента, для которого массив битов активности одновременно является рабочей маской активности, т.е. он не имеет активного остатка. После выполнения процедуры компоновки порции данных блок 13 при помощи матрицы 10 и блока 9 памяти выполняет процедуры данного этапа обработки. Затем, аналогично используя те же рабочие маски активности и матрицу 8, блок 13 поочередно распределяет обработанные зоны фрагментов данной группы записью по соответствующим адресам ячеек блока 9 памяти. Непосредственно после этого блоки 12 и 13 обеспечивают пересылку 25 Фрагментов, прошедших обработку и не имеющих необработанных активных остатков, что характеризуется равенством нулю их масок активных остатков, с блока 9 памяти по линиям шины 15 в блок 5 опережающей подготовки данных, откуда они выводятся в элемент памяти узла 3. Одновременно оставшиеся необработанные активные остатки недообработанных фрагментов подвергаются повторной процедуре упаков20

30

тивных фрагментов в матрице 10 с фик- 35 ки При этом маски этих активных ос- сацией полученных рабочих масок активности в блоке памяти. Далее массив битов активности первого фрагмента поступает из матрицы элементов и по

татков используются как массивы битов активности для оставшихся недорабо тайных фрагментов первой группы. Кроме того, в процессе повторной упаковлиниям 23 в блок 9 памяти. Одновременно ки оставшиеся фрагменты первой группы

но блок 13 осуществляет считывание первого фрагмента с блока 9 памяти по линиям 38 в матрицу 10, где значения его элементов фиксируются в аккумуляторах узлов 75 обработки. При этом элементы считываемого фрагмента, не отмеченные битом активности, не считываются, и вместо них в матрицу 10 поступают нулевые значения. После этого блок 13 осуществляет аналогичное маскирование соответствующей рабочей маской активности считывания с блоков 9 памяти следующего фрагмента данной группы, ввод результата маскирования в матрицу 10, дизъюнкцию его 55 Дят к следующему этапу обработки фрагзначений с соответствующими значениями, содержащимися в аккумуляторах узлов обработки, и фиксацию полученного результата в те же аккумуляторы. Та12

5

ким образом, производится логическое сложение неперекрывающихся активных зон фрагментов данной группы. Области перекрытия активных зон вместе с неактивными зонами отсекаются соответствующими масками активности всех Фрагментов данной группы за исключе- чением первого фрагмента, для которого массив битов активности одновременно является рабочей маской активности, т.е. он не имеет активного остатка. После выполнения процедуры компоновки порции данных блок 13 при помощи матрицы 10 и блока 9 памяти выполняет процедуры данного этапа обработки. Затем, аналогично используя те же рабочие маски активности и матрицу 8, блок 13 поочередно распределяет обработанные зоны фрагментов данной группы записью по соответствующим адресам ячеек блока 9 памяти. Непосредственно после этого блоки 12 и 13 обеспечивают пересылку 5 Фрагментов, прошедших обработку и не имеющих необработанных активных остатков, что характеризуется равенством нулю их масок активных остатков, с блока 9 памяти по линиям шины 15 в блок 5 опережающей подготовки данных, откуда они выводятся в элемент памяти узла 3. Одновременно оставшиеся необработанные активные остатки недообработанных фрагментов подвергаются повторной процедуре упаков0

0

5 ки При этом маски этих активных ос-

ки При этом маски этих активных ос-

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

5

0

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

Полученная совокупность фрагментов является второй группой фрагментов, образующих вторую порцию данных, подлежащих обработке. Аналогичным образом процедуры обработки данного этапа выполняются над всеми фрагментами матрицы данных. Упаковка и обработка оставшихся активных остатков последней группы фрагментов, матрицы данных повторяется до момента их полной обработки, после чего блоки 12 и 13 перехоментов матрицы данных. При этом исходная .информация считывается через соответствующий приемопередатчик 50 или 51 с элемента памяти того узла 2

13153М66

3, в котором зафиксирован резульпредыдущего этапа обработки.

осле выполнения всех этих этапов ботки результирующая информация, дящаяся, например, в элементе 9 ти, выводится на блок 1 ввода-вы.

от тр ре гр вы ст ма со вх эл вх ст ма ти ны че ны ра ко фе по вт фо об ще со

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

0

5

0

5

ответственно к первому, второму и третьему управляющим входам блока опережающей подготовки данных, первая группа из п2 информационных входов- выходов которого подключена соответственно к первой группе из п2 информационных входов-выходов узла сдвига, соответственно к п2 информационным входам-выходам распознавания активных элементов кадра, соответственно к п2 входам матрицы элементов И и соответственно к первой группе из п2 информационных входов - выходов блока памяти, вторая группа из п2 информационных входов - выходов которого подключена соответственно к п2 информационным входам-выходам матрицы узлов обработки, выходы с первого по п2-и которой подключены к входам блока буферных повторителей, выход которого подключен к входам режима первого и второго блоков управления, вторые информационные входы-выходы которых объединены и подключены к управляющему входу-выходу матричного процессора, вторая группа из (N2 - п2),

0

0

где N - линейный размер фрагмента обрабатываемого кадра с окрестностью, информационных входов-выходов блока опережающей подготовки данных подключена соответственно к второй группе из (N2 - п2) информационных входов- . выходов узла сдвига, третья группа из N информационных входов-выходов

5 узла сдвига объединена с четвертой и пятой группами no N информационных входов-выходов в каждой узла сдвига и подключена соответственно к шестой группе из N информационных входов-выходов узла сдвига, выходы с первого по п2-и матрицы элементов И-подключены соответственно к информационным . входам с первого по п2-и блока памяти, второй и третий выходы второго

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

10

му управлючцмм пходом второй группы блока памяти.

15

20

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

го подключен к второму управляющему входу первого приемопередатчика первой группы, четвертый управляющий вход блока подключен к управляющему входу второго приемопередатчика второй группы и к входу второго элемента НЕ, выход которого подключен к второму управляющему входу второго приемопередатчика первой группы, пя30

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

тый управляющий вход блока подключен 35 блока подключены соответственно к

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

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

5 формационному входу-выходу блока, з. Процессор по п.1, о т л и ч

5

0

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

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

0

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

из (N2 - п2) информационных входов- выходов узла сдвига подключена соответственно к второй группе из (N2 - п2) информационных входов-выходов блока, третья группа из п информационных

I I

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

мая группа () информационных

входов-выходов узла сдвига объединена соответственно с восьмой группой из

/N - IK

информационных входов-выходов

узла сдвига и подключена соответствен20 ционного элемента (р-1)-й строки q-ro столбца матрицы, третьи информационные входы-выходы коммутационных эле,N -.IK но к (--у--) выходам третьего ключа,

девятая группа из () информацией- ментов первой строки с (™-- + 1)-го

2„ 25 по (

ных входов-выходов узла сдвига объе динена соответственно с десятой группой

+ п)-го столбца матрицы подключены соответственно к п информационным входам-выходам третьей группы матрицы, первые информационные входы- дов узла сдвига и подключена соответст-30 вшоды коммутационных элементов пер/N - IK из --z--) информационных входов-выхоCN - п венно к () выходам четвертого

/N п ключа, одиннадцатая группа из -)

информационных входов-выходов узла сдвига объединена соответственно с

/N - nv

двенадцатой группой из --s--J информационных входов-выходов узла сдвига

,N - гк 40 столбца с (--:--+ |)-й по (-- --+ п)-ю и подключена соответственно к (-- -}2I

выходам первого ключа, тринадцатая

группа из () информационных входов-выходов узла сдвига объединена соответственно с четырнадцатой группой из (--;--) информационных входовстрок матрицы подключены соответственно к N информационным вкодам- выходам пятой группы матрицы, четвер- АГ тые информационные входы-выходы коммутационных элементов N-й строки с

N - п

+1)-го по ()-й столбцов

матрицы подключены соответственно выходов узла сдвига и подключена со- 50 к п информационным входам-выходам

шестой группы матрицы, третьи информационные входы-выходы коммутационных элементов первой строки столбцов

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

55

с (--г + п + Ото по N-й подключены соответственно к седьмой группе

из (5) информационных BxofloBwBbixoN - и

2

Л

ri второй управляющий

вход узла подключен к управляющим входам остальных коммутационных элементов матрицы, первый информационный вход-выход коммутационного элемента Кй строки 1-го столбца матрицы (где К 1, .... И; 1 2, ..., N) подключен к второму информационному входу- выходу коммутациосрто элемента К-й строки (1-1)-го столбца матрицы, третий информационный вход-выход коммутационного элемента р-й строки q-ro столбца матрицы, (где р 2, ..., N; q 1, ..., N) подключен к четвертому информационному входу-выходу коммутационного элемента (р-1)-й строки q-ro столбца матрицы, третьи информационные входы-выходы коммутационных эле+ п)-го столбца матрицы подвого столбца с (--г-- + 1)-и по (j + п)-ю строк матрицы подключены

соответственно к п информационным входам-выходам четвертой группы матрицы, вторые информационные входы- выходы коммутационных элементов N-ro

строк матрицы подключены соответственно к N информационным вкодам- выходам пятой группы матрицы, четвер- тые информационные входы-выходы коммутационных элементов N-й строки с

N - п

+1)-го по ()-й столбцов

55

с (--г + п + Ото по N-й подключены соответственно к седьмой группе

из (5) информационных BxofloBwBbixoдив матрицы, первые информационные входы-выходы коммутационных элементов первого столбца с первой по

/N - гк

подключены соответственно

к восьмой группе из (--г--) информационных входов-выходов матрицы, третьи информационные входы-выходы коммутационных элементов первой строки

1/N - Пч .

столбцов с первого по (-)и подключены соответственно к девятой ,N тырнадцатой группе из

N - ч,

инфор10

моционных входов-выходов матрицы, пятые информационные входы-выходы коммутационных элементов i-й строки j-ro столбца матрицы подключены соответственно к первой группе из пг информационных входов-выходов матрицы, а пятые информационные входы-выходы остальных коммутационных элементов матрицы подключены соответственно к второй группе из (N2 - пг) информационных входов-выходов матрицы, при этом каждый коммутационный элемент матрицы содержит мультиплексор, демультиплек- сор и триггер, причем в каждом коммутационном элементе матрицы первый информационный вход-выход коммутационного элемента подключен к первому выходу демультиплексора и к первому информационному входу мультиплексора, второй информационный вход-выход коммутационного элемента подключен к (- о) информационных входов-выходов второму выходу демультиплексора и вто. .,рому информационному входу мультиматрицы, четвертые информационныеv ч MJ 3

группе из

() 2

информационных вхо15

дов-выходов матрицы, первые информационные входы-выходы коммутационных элементов первого столбца строк с

(

N - п

20

+ п + 1)-й по N-ю подключены

соответственно к десятой группе из

входы-выходы коммутационных элементов

,N N-й строки с (

п

+ п + 1) -го по N-й

столбцов подключены соответственно к

/N - Пч

одиннадцатой группе из --z--) информационных входов-выходов матрицы, вторые информационные входы-выходы коммутационных элементов N-го столбца

строк с первой по (--г--)-ю подключены соответственно к двенадцатой групi

пе из (--:--) информационных входов- выходов матрицы, четвертые информационные входы-выходы коммутационных элементов N-й строки столбцов с первого по (--г--)-и подключены соответственно к тринадцатой группе из

(K.I.S)

V 2

30

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

45

матрицы, вторые информационные входы- выходы коммутационных элементов матрицы, вторые информационные входы- выходы коммутационных элементов N-ro

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

,N - п

+ п

+ 1)-и по N-ю

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

N - ч,

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

0

5

0

5

0

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

76

Фиг.З

s Mu

I . 1

(

ьтгг

. . .

.IJJL

95

и

а

cs

г

j

W «

Cvl

фА

t§

vo «ч

i

I

J,

лч л А ч

V

Са 0&

rs

Л

кtr

сг

СППф

М

9L

9L

Ч

9L

99M«l

I

i

ТЛИ v tФиг.16

фиг.17

Фиг. 18