Буферное запоминающее устройство с произвольной выборкой двумерного фрагмента Советский патент 1988 года по МПК G06F12/00 

4 4

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

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

.Изобретение относится к запоминающим устройствам и может быть использовано в системах с произвольным доступом к двумерным данным, например в .процессорах коррекции геометричесг кик искажений изображения. Цель изобретения - увеличение производительности буферного запоминающего устройства при обработке двумерных данных. Буферное запо.минающее устройство содержит блок 1 памяти адреса,блок 2 v управления флагами сравнения, блок 3 преобразования адреса, коммутатор 4 адреса, блок 5 памяти данных, регистр 6 входных данных, блок 7 управления. Устройство позволяет существенно сокi (Л

1 .

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

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

На фиг.1 изображена функциональная схема буферного запоминающего устройства с,произвольной выборкой двумерного фрагмента; на фиг.2 - функциональная схема блока памяти адреса; на фиг.3 - блок управления флагами сравнения; на фиг.4 - блок маскирования и циклического сдвига флагов сравнения; на фиг.5 - блок преобразования адреса; на фиг.6 - блок памяти данных; на фиг,7 - блок циклического сдвигателя выходных данных; на фиг.8 .- конфигурация окрестностей двумерного фрагмента данньк; на фиг.9 - нумерация элементов двумерного фрагмента.

Буферное запоминающее устройство содержит блок 1 памяти адреса, блок 2 управления флагаки сравнения, блок 3 преобразования адреса, коммутатор 4 адреса, блок 5 памяти данных, регист 6 входных данных, блок 7 управления, вход 8 полного адреса фрагмента, вход 9 готовности адреса фрагмента, выход 10 готовности выходных данных, информационный выход 11 устройства, адресный выход 12 устройства, выход .13 готовности адреса сегмента, выход 14 готовности входных данных, информационный вход .1 5, вход 1 6 стробиро- вания регистра 6, вход 17 записи в

5

0 5 0

блок -1, вход 18 записи в блок 2 управления флагами сравнения, вход 19 стробирования дешифратора блока 2 управления флагами сравнения, выход 20 статуса блока 2 управления флагами сравнения, вход 21 записи в модули памя.ти блока 5 памяти данных, ин- формационньй вход 22 блока 5, вход 23 управления коммутатором блока 3 преобразования адреса, вход 24 стробирования -адресного регистра блока 3 преобразования адреса, второй выход 25 блока 1, вход 26 разрешения записи блока 1, выход 27 адреса сегмента, адресный вход 28 блока 5, второй и третий выходы 29 30 блока 2, второй информационньш вход 31 коммутатора 4, вход 32 управления коммутатором 4, вход 33 чтения блока 5 памяти данных.

Блок 1 памяти, адреса содержит четыре группы сумматоров 34 адреса, четыре модуля 35 памяти, четыре схемы 36 сравнения адреса и данных в модулях 35 памяти.

Блок 2 управления флагами сравнения содержит узел 37 маскирования и циклического сдвига флагов сравнения, четырехразрядный регистр 38 флагов, приоритетный шифратор 39, дешифратор 40, выходы 41 маскированных флагов сравнения.

Узел 37 маскирования и циклического сдвига флагов сравнения содержит пе.рвый и второй входные схемы 42 и 43 сдвига первого каскада, входную схему 44 сдвига второго каскада, выходную схему 45 сдвига первого кас- када, первый и второй выходные схемы 46 и 47 сдвига второго каскада, элементы И 48,...,51, элементы НЕ 52 и 53, элементы ИЛИ 54 и 55.

10

15

20

Блок 3 преобразования адреса содержит первый и второй сумматоры 56 и 57 адреса, сумматор 58 приращений адреса, коммутатор 59, регистр 60 адреса, регистр 61 длины строки.

Блок 5 памяти данных содержит шестнадцать групп сумматоров 62 адреса, шестнадцать модулей 63 памяти, узел 6А циклического сдвига выходных данных.

Узел 64 циклического сдвига выходных данных содержит четыре схемы 65 сдвига первого каскада и групповую схему 66 сдвига второго каскада.

Буферное запоминающее устройство с произвольной выборкой двумерного фрагмента работает следующим образом.

На вход 8 поступают Р разрядов, где ,jM+log2N, задающие полный адрес элемента двумерной матрицы данных размерностью , на адресные входы блока 1 поступают разряды первой координаты, где ,..,,log М- -1 , и разряды, второй координаты, где ,... ,log,.|N-1 , на первый вход . коммутатора 4 поступают младшие разряды m первой координаты, где i« 0,,..,, и младшие разряды п j

второй координаты, где 1 0log K-1, причем емкость блока 5 памяти -, данных составляет (), элементов, На управляющий вход блока 2 поступают разряды тд,т,,тп П(у,п,,,п полного адреса фрагмента.

Перед началом работы по сигналу начальной установки осуществляется обнуление всех ячеек памяти .блока 1 памяти адреса. После этого буферное запоминакщеё устройство готово к работе. Внейнее задающее устройство устанавливает адрес двумерного фрагмента на входе 8 и генерирует сигнал готовности адреса по входу 9. На сумматоры 34 (фиг-. 2) каждого из четы25

4

параллельно, В схемах 36 сравнения блока 1 старшие разряды полного ад са с данными в соответствующем мод ле памяти, адресуемом младшими раз рядами полного адреса сегмента. Ра ряды четырехразрядного выхода 25 блока Г (флаги сравнения) для восс новления порядка расположения флаго искаженного использованием функций (8) поступают на первый и второй входные схемы 42 и 43 сдвига перво каскада блока 2 и затем на выходную схему 44 сдвига первого каскада, В схемах 42 и 43, управляемых разрядо т полного адреса памяти, осуществл ется циклический сдвиг внутри груп флагов по два в каждой группе, во втором каскаде (схема 44)управляемом разрядом п I полного адреса пам ти, циклический сдвиг групп. Как сл дует из фиг.8 для организации произ вольной выборки фрагмента из блока может .потребоваться загрузка-от одн го до четырех сегментов, что опреде ляется положением элемента а,

mn внут

сегмента. Поэтому четырехразряд1й й код признаков сравнения пЪсле корре тировки положения данных поступает на выход узла 37. На базе элементов И 48,...,51, НЕ 52 и 53, ИЛИ 54 реа лизуются функции 10. Элементы И 48, 49,50 осуществляют собственно маски рование соответствующих флагов срав нения, запрещая выборку ненужных 35 сегментов из памяти исходного изобра жения. Маскирование флагов сравнени осуществляется .разрядами mj,, m, Пд, п,- полного адреса памяти.

Выходами узла 37 маскирования и циклического сдвига флагов сравнени являются два четьфехразрядных выход сигналы разрешения записи в модули памяти блока 1 (выход 26) и флаги сравнения, модифицированные схемой

40

рех модулей 35 памяти поступают млад- 45 маскирования (выходы 41). Для коршие разряды, а также разряды т-, полного адреса памяти, на сумматоры 62 каждого из шестнадцати модулей 63 памяти блока 5 через коммутатор 4 поступают младшие разряды, а также раз- РЯДЫ ШВ, т, .По, п,, полного . На выходах сумматоров 34 блока 1 устанавливаются полные адреса четырех сегментов 1-4 (фиг.8), в которых-могут располагаться элементы фрагмента на выходах адресных сумматоров 62 блока 5 собственно адреса элементов фрагмента. Выборка данных из модулей памяти блоков 1 и 5 осуществляется

0

5

0

784

5

4

параллельно, В схемах 36 сравнения блока 1 старшие разряды полного адреса с данными в соответствующем модуле памяти, адресуемом младшими разрядами полного адреса сегмента. Разряды четырехразрядного выхода 25 блока Г (флаги сравнения) для восстановления порядка расположения флагов искаженного использованием функций (8) поступают на первый и второй входные схемы 42 и 43 сдвига первого каскада блока 2 и затем на выходную схему 44 сдвига первого каскада, В схемах 42 и 43, управляемых разрядом т полного адреса памяти, осуществляется циклический сдвиг внутри групп флагов по два в каждой группе, во втором каскаде (схема 44)управляемом разрядом п I полного адреса памяти, циклический сдвиг групп. Как следует из фиг.8 для организации произвольной выборки фрагмента из блока 5 может .потребоваться загрузка-от одного до четырех сегментов, что определяется положением элемента а,

mn внутри

сегмента. Поэтому четырехразряд1й й код признаков сравнения пЪсле корректировки положения данных поступает на выход узла 37. На базе элементов И 48,...,51, НЕ 52 и 53, ИЛИ 54 реализуются функции 10. Элементы И 48, 49,50 осуществляют собственно маскирование соответствующих флагов сравнения, запрещая выборку ненужных 5 сегментов из памяти исходного изображения. Маскирование флагов сравнения осуществляется .разрядами mj,, m, Пд, п,- полного адреса памяти.

Выходами узла 37 маскирования и циклического сдвига флагов сравнения являются два четьфехразрядных выхода: сигналы разрешения записи в модули памяти блока 1 (выход 26) и флаги сравнения, модифицированные схемой

0

ректной записи в модули памяти блока 1 старших разрядов полных адресов сегментов в схемах 45,.,.,47 сдвига (фиг.4) осуществляется обрат50 ная корректировка положения разрядов кода флагов сравнения. В схеме 45, управляемой разрядом ш полного ад- , реса памяти, меняется положение двух групп по два разряда кода флагов,

55 в схемах 46, 47, управляемых разрядом П), изменяется положение разрядо внутри групп.

Через промежуток времени t, необходимый для установки сигналов

10

разрешения записи (на входе 26) в модули памяти блока 1, установки кода флагов на входах регистра 38, установки данных на вьпсодах данных блока 5, блок 7 управления генерирует сигнал записи по входу 17 в модули памяти блока 1 и сигнал записи по входу 18 в регистр 38 флагов. В состав приоритетного шифратора 39 (фиг.З) кроме собственно шифратора входит схема ИЛИ, входы которой подключены к выходам регистра флагов. Блок 7 управления анализирует состояние входа 20, являющегося выходом 15 указанного элемента ИЛИ, и, если запросов на загрузку сегментов нет, устанавливает сигнал на выходе 10 готовности данных на выходе 11. Если необходима эагрузка сегментов, блок 20 7 управления снимает сигнал чтения данных из блока 5 по входу 33,переключает коммутатор 4 адреса сигналом на входе 32 в положение, обеспечивающее прохождение на адресные суммато- 25 ры блока 5 разрядов с линии 31, переключает коммутатор 59 адреса сигналом с входи 23 так, чтобы выходы суммато14447846

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

После установки адреса сегмента, в регистре 60 и запроса к памяти исходного изображения на линии 13 блок 7 управления анализирует состояние линии 14 готовности данных. Когда на входе 15 устанавливаются истинные данные, что сопровождается изменением состояния линии 14, блок 7 управления генерирует строб записи данных на линии 21 в модули памяти блока 1. Данные с выхода 15. через регистр 6 поступают на вход 22 блока 5. На адресные сумматоры блока 5 по входу 28 поступают младн ие разряды полного адреса сегмента, причем разряды адреса, соответствующие разрядам Шо ш,,

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

35

ров 56 и 57 были подключены к входам регистра 60, стробирует адрес первого 30 отказаться от корректировки положет загружаемого сегмента в выходной ре- ния данных на входе блока 5 памяти гистр 60 адреса сигналом с входа 24 и генерирует запрос к памяти исходного изображения на линии 13. Адрес .Загружаемого сегмента, содержащийся в регистре 60, формируется из адреса базового сегмента Ь( , генерируемого адресными сумматорами первого модуля памяти блока 1, Полньй адрес базового сегмента на линии 27., разделенный на адреса по п.ервой координате и адреса по второй координате, подключен к первым входам соответственно сумматоров 56 и 57. Полный адрес сегмента с вькода сумматоров через коммутатор 59 поступает на вход регистра 60. Выданных.

Одновременно со стробом записи в блок 5 блок 7 управления стробирует вькоды дешифратора 40 (фиг.З) сигналом на линии 19. По заднему фронту этого импульса осуществляется сброс флага в регистре 38, соответствующего загруженному сегменту. После этого 40 устройство управления анализирует состояние линии 20. Если в регистре 38 флагов имеются установленные в единицу разряды, то процесс считывания сегментов продолжается до обнуления регистра 38 флагов, что будет зафиксировано изменением состояния линии 20, Когда все необходимые сегменты загружены, устройство управления переключает коммутатор 4 в положение, обеспечивающее прохождение на адресный вход 28 сигналов с входа 8, запускает цикл чтения бл.ока 5 сигналом на линии 38 и через промежуток времени, необходимый для считывания данных, устанавливает сигнал готовности данных на линии 10.

4В

ходы регистра 38 флагов подключены к входам приоритетного шифратора в следующем порядке убывания приоритета; флаг сегмента Ь - : .,, флаг сегмента bj j.,, флаг сегмента b i-i,-J4 флаг сегмента Ь- . Соответственно коды, генерируемые приоритетным шифратором для каждого флага, являющегося старшим в какой-то момент времени, следующие: 11,10,01,00. Старший разряд выходного кода приоритетного шифратора поступает на вход вычитания единицы сумматора 56, а младший - на

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

отказаться от корректировки положет ния данных на входе блока 5 памяти

отказаться от корректировки положет ния данных на входе блока 5 памяти

данных.

Одновременно со стробом записи в блок 5 блок 7 управления стробирует вькоды дешифратора 40 (фиг.З) сигналом на линии 19. По заднему фронту этого импульса осуществляется сброс флага в регистре 38, соответствующего загруженному сегменту. После этого устройство управления анализирует состояние линии 20. Если в регистре 38 флагов имеются установленные в единицу разряды, то процесс считывания сегментов продолжается до обнуления регистра 38 флагов, что будет зафиксировано изменением состояния линии 20, Когда все необходимые сегменты загружены, устройство управления переключает коммутатор 4 в положение, обеспечивающее прохождение на адресный вход 28 сигналов с входа 8, запускает цикл чтения бл.ока 5 сигналом на линии 38 и через промежуток времени, необходимый для считывания данных, устанавливает сигнал готовности данных на линии 10.

В реальной системе данные в памяти исходного изображения располагаются линейно строка за строкой, что

714А478Ч

объясняется физическим устройством

м

средств ввода/вывода изображений,Для работы с линейной организацией данных в состав блока 3 преобразования адреса введены сумматор 58 приращений адреса и регистр 61 длины строки, предполагается также использование 32- разрядной шины данных. В этом случае адрес сегмента, генерируемый на ли- НИИ 27, является адресом первых четырех элементов-сегмента, лежащих в одной строке. Адреса элементов сегмента, расположенных в других строках, можно получить последовательным суммированием длины строки и составляющей адреса сегмента по второй координате. При этом составляющая адреса по первой координате зафиксирована. Полученные данные последовательно записываются в регистры 6 входных данных и затем параллельно перегружаются в модули памяти блока 5

контроль за данными, содержаписмися в

хГредтагаемое устройство буферной 25 блоке памяти данных (БД) в четырех

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

мерного фрагмента ориентировано на

последовательную обработку потока

фрагментов размером 4x4 элемента.

Данные извлекаются из памяти исходно- ЗО вольному адресу. В зависимости от

го изображения ,в устройство буферной адреса возможна загрузка от одного

памяти и записываются в память выход- до четырех сегментов. Их количество

ного изображения, генерируемого обра- определяется функциями маскирования

батывающим процессором. При использо- флагов сравнения старших разрядов

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

В БД с помощью шестнадцати пар сумматоров и блока циклического сдвиметоду кубической свертки (2), Данные, получаемые процессором свертки.

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

леи памяти реализована произвольная выборка фрагмента 4x4 элемента вида

т-1, h-1 tvi-i,n кы,п+1 m.l,

50

A(m,n)

tn, л-1

3n,n S m,

(n,

;(1)

ЮТСЯ в выходн-ую память. Для записи одного элемента .данных изображения необходимо считать шестнадцать элементов данных из памяти исходного изображения. При достаточно высоком быстродействии входного и выходного процессоров скорость извлечения данных ограничивает производительность системы в целом. Предлагаемое устрой- где m,n - индексы, определяющие адрес ство буферной памяти позволяет пони- фрагмента, причем О и О in ; Р, зить частоту обращений к памяти ис- аv - центральный элемешг фрагмента.

, m+i,

, n-i

friil, n- 1 m+t,h tn, n+1 ,h

ХОДКОГО изображения, a также повысить скорость обработки за счет эффектив-, ной буферизации данных.

o g

Память исходнЬго изображения емкостью элементов, а также памяц. блока запоминающих устройств данных емкостью LKP элементов (M,N,L и Р - степени числа 2) разбиваются на сегменты элемента. В памяти исходноR М N

го изображения содержится , а в

L Р

буферной памяти т т сегментов, Сег- 4 4

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

L Р

(БА) содержит т х т ячеек памяти (по 44

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

35

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

, в

леи памяти реализована произвольная выборка фрагмента 4x4 элемента вида

где m,n - индексы, определяющие адре фрагмента, причем О и О in ; Р, аv - центральный элемешг фрагмента.

т-1, h-1 tvi-i,n кы,п+1 m.l,

- индексы, определяющие ад а, причем О и О in ; Р нтральный элемешг фрагмент

0

A(m,n)

tn, л-1

3n,n S m,

(n,

;(1)

где m,n - индексы, определяющие адрес фрагмента, причем О и О in ; Р, аv - центральный элемешг фрагмента.

, m+i,

, n-i

friil, n- 1 m+t,h tn, n+1 ,h

При линейной организации памяти, когда данные в памяти располагаются строка за строкой, адреса элементюв.

образующих квадратную матрицу (1), можно представить следующим образом A(m-bi,n+j)P(m-«-i)-f(n+j), (2) где i и j - целые числа, изменяющиеся в пределах: , -1 j 2; Р - длина строки; тип- координаты центрального

элемента.

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

m ) 4

СИМВОЛ,

П

+ , (3)

обозначающий one- остатка от

рацию взятия

деления; номер модуля памяти

(О о 15).

элементов массива в модуопределяются формулой

А (т, п) - -

Р m п 4 4 4

(4)

символ, обозначающий операцию взятия целой части

деления.

Таким образом, положение элемента массива в памяти определяется номером модуля памяти и адресом внутри модуля, вычисляемым по формулам (3) и (4), Для распределения элементов массива, определяемого формулой (3), элементы фрагмента (1) при любых тип таких, что :L и .п Р, будут находиться в разных модулях памяти.

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

(5)

где А

а

А ,- номера модулей памяти.

0

5

0

5

Пример распределения двумерного массива по модулям представлен в табл,1. Здесь показано расположение фрагмента в памяти для , и Р ,

Использование функции (3) приводит к нарушению естественного расположения элементов фрагмента, извлекаемого иэ памяти. Обозначим элементы фрагмен-; та цифрами от О до 15 в соответствии с фиг,9, Тогда функцию перестановки данных можно описать, как в табл,2.

Блок, реализующий описанную в табл,2 функцию перестановки, показан на фиг, 7. Первый каскад осуществляет циклический сдвиг внутри четырех групп.данных и управляется разрядами п. и:.т1 полного адреса памяти (функ- 01 в табл,2), второй каскад осу0

ция

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

Пусть MxN - размерность массива данных, хранящегося в памяти исходного изображения, L х Р - размерность массива данных, хранящегося в БД бу-г ферного запоминающего устройства, Разрядность шины полного адреса памяти двумерного фрагмента (1) можно представить выражением

11

м

NS

Ap(log - +log,p) + (log,J+log,|)A,(6)

где Ар - разрядность шины адреса. Выражение в первых круглых скобках представляет старшие разряды полного адреса памяти, во вторьпс - разряды адреса сегмента в БД, содержащего центральный элемент ai матрицы (1). Цифрой Д представлены разряды Шс,,т ), По, HI, адресующие элемент а внутри сегмента. Старшие разряды полного адреса памяти запоминаются в БА, длина слова которого равна

D + logj-

где Т - добавочный двоичный разряд

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

адресная шина БА содержит

двоичных разрядов. l°gl

го, что в БД осуществляется фрагмента с переходом через сегмента, в состав адресной

i входят также разряды -т. у, т,, Элементы фрагмента (1) могут нахог.

По,- п

в одном, двух или четырех сег- 40 Двумерного массива данных по четырем

ментах, С целью параллельной проверки на предмет наличия или отсутствия требуемых сегментов в БД, в БА организована двумерна.я выборка фрагмента 2x2 элемента вида

bi-1.

b,-..

)

b

. Jb:

(7)

где i,j - индексы, определяющие ад- 50

pec фрагмента, причем

О i.7 4

центральный элемент фрагмента.

L 4

Элементы массива размерностью Р

т распределены по четырем модулям

44478412

памяти в соответствии с функцией распределения

(i,j) 2 + ,

(8)

где (i,j) - номер модуля О-« о( 3 .

Адреса элементов массива в модулях памяти определяются формулой

A(iJ) - .

Адресные функции для параллельного доступа к фрагменту имеют вид

Ao(i.j)

20

где

памяти блока БА. В модуле памяти А 0 БА хранятся старшие разряды адресЬв сегментов,

i „ J

удовлетворяющие условию т 2

в модуле А, - удовлетворяющие условию

1 J

1 , 5 1 , в модуле А ,j - удовлет0,

воряющие условию О,

1, в мо35

дуле Aj - удовлетворяющие условию

i-i.i-o.

Пример распределения элементов

5

0

6

модулям памяти представлен в табл.3. Здесь также показано расположение Фрагмента в памяти для ,

и Так же, как и в памяти данных, использование функции (8) приводит к зависимости порядка расположения выходных данных модулей памяти A(,,AI, А и АЗ от адреса извлекаемых сегментов. Однако в отличие от схемы, перестановки данных, используемой в БД, корректировке подвергается порядок следования флагов сравнения данных в модулях памяти и старших разрядов адресов сегментов, генерируемых соответствующими адреснйми сумматорами. Блок, реализующий функцию перестановки флагов сравнения, представляет собой двухкаскадный циклический

314

сдвигатеЛь. Первый каскад осуществляет циклический сдвиг внутри двух групп флагов сравнения (по два в каждой группе) и управляется разрядом п, полного адреса памяти, второй каскад осуществляет циклический сдвиг самих групп флагов и управляется разрядом тп 4 полно го адреса памяти.

На фиг.8 изображены девять сег- ментов, обозначенных цифрами 1...9, в которых могут располагаться элементы фрагмента (1), если элемент а „ находится в центральном сегменте 5, Из рисунка видно, что при и п.. 0 элементы фрагмента (1) могут находиться в сегментах 1,2,4,5, при т., 1 п 0- в сегментах 4,5,7,8, при , п 1 - в сегментах 5,6,8,9. Для выборки из БА данных о требуемых сегментах в адресные функции каждого модуля памяти введены разряды m , и n,i. Адресные функции для модулей па

мяти БА принимают вид

(9)

где

памяти.

На фиг.86 изображены четыре сегмента двумерной матрицы данных,обозначенные цифрами 1-4, в которых могут находиться элементы фрагмента (1) с учетом модифицированных адресных функций (9). Внутренний квадрат ограничивает местоположение центрального элемента а „, вн ешний -.границы фрагмента (1) при изменении положения а. в заданных пределах. В зави ПШ

симости от положения центрального элемента требуется загрузка разного количества сегментов, что определяется табл.4, и табл.4 для каждой кодовой комбинации разрядов Щд,т,,

п

о

п.

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

F1 (m(,vm,) (пр vh,);

1П.П 1 Ш

1

(10V

о l

i;

которые определяют необходимость загрузки в БД соответствующих сегментов.

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

5

0

5

0

5

0

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

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

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

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

выходы первого и второго сумматоров

адреса р-и группы соединены с адресным входом р-го модуля памяти, где Р 1,..,,4, выходы первого и второго сумматоров адреса первой группы явля- ются первым и вторым- составляющими первого выхода блока, вход .чтения блока соединен с входами чтения всех модулей памяти, выход р-го модуля памяти соединен с первым входом р-й

О

ю 15 0 25

ЗО ,, Q g

0

-

55

841 6

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

сигналов 6, О, -1 и -1 соответственно .

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

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

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

171Д44784

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

к входу логического уровня сигнала -(-2 блока, где ж 4,8,12,16 и ,...,16 .

6, Устройство по ПП.1 и 3, о т « личающееся тем, что узел маскирования и циклического сдвига флагов сравнения содержит две входные схемы, сдвига первого каскада, входную схему сдвига второго каскада, выходную схему первого каскада, две выходные схемы сдвига второго каскада, два элемента НЕ, два .элемента ИЛИ и четыре элемента И, причем первый и второй информационные входы первой входной схемы сдвига первого каскада соединены с первым и вторым разрядами- информационного входа узла соответственно, первый и второй информационные мяти и узел циклического сдвига, вхо- 20 входы второй входной схемы сдвига

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

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

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

35

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

сдвига, входы первого слагаемого первого и второго сумматоров адреса . всех групп соединены со старшими разрядами по первой и второй координатам адресного входа блока соответ- 40 Д соответственно, первый и второй

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

первых сумматоров адреса а-й группы и вторых -сумматоров адреса б-й группы подключены к входу логического уровня сигнала -1 блока, где а 1,5,9,13 и ,...,4, входы второго слагаемого первых сумматсэров адресов в-й группы и вторых сумматоров адреса г-й группы подключены к входу логического уровня сигнала О блока, где ,6,10,14 и ,...,8, входы второго слагаемого первых сумматоров адреса д-й группы и: вторых сумматоров адреса е-й группы подключены к входу логического уровня сигнала ,+1 блока, где ,7,11,15 и- е 9,. .,, 12, входы второго слагаемого первых сумматоров адреса ж-й группы и вторых сумматоров адреса з-й- группы подклю50

5Е

4

чены

18

к входу логического уровня сигнала -(-2 блока, где ж 4,8,12,16 и ,...,16 .

6, Устройство по ПП.1 и 3, о т « личающееся тем, что узел маскирования и циклического сдвига флагов сравнения содержит две входные схемы, сдвига первого каскада, входную схему сдвига второго каскада, выходную схему первого каскада, две выходные схемы сдвига второго каскада, два элемента НЕ, два .элемента ИЛИ и четыре элемента И, причем первый и второй информационные входы первой входной схемы сдвига первого каскада соединены с первым и вторым разрядами информационного входа узла соответстпервого каскада соединены с третьим и четвертым разрядами информационного входа узла соответственно, выходы первой и второй входных схем сдвига первого каскада соединены с информационными входами входной схемы сдвига

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

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

Д соответственно, первый и второй

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

о у 3 4 5 б 7 cf 5 / // /2 /5 / /5

д У 3

6

5 66

67

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

1Q сдвига второго каскада и выходной схемы сдвига первого каскада.

Т а б л и ц а 1

21

с/

1444784

22 Таблица 2

ТаблицаЗ

0 У 2- 5

б л и ц а 4

Фиг,

/п

т

Фиг. 8

Фиг.9