1499355 - Запоминающее устройство с параллельным произвольным доступом к строкам и окнам данных

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

Иллюстрации

Показать все

Реферат

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах с параллельной обработкой информации, а также в качестве регенерационной памяти в полутоновых и графических растровых дисплеях. Цель изобретения - расширение функциональных возможностей устройства за счет дополнительного формата обращения в виде строк. Поставленная цель достигается тем, что устройство содержит блок 1 памяти, блок 2 входных данных, блок 3 выходных данных, блок 4 управления, блок 5 модификации адреса, блок 6 деления на группы, блоки 7 и 8 мультиплексоров. 3 з.п.ф-лы, 14 ил.

СОЮЗ СОНЕТСНИХ

РЕСПУБЛИН (51)4 С 06 F 12/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

AO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР (21) 4276428/24-24 (22) 06.07.87 (46) 07.08.89. Вял. и- 29 (71) Ленинградский электротехнический институт им. В.И. Ульянова (Ленина) (72) В,В, Каверзнев и E.À. Метлицкий (53) 681. 325(088. 8) (56) Патент США N 4051551, кл. G 06 F 13/00, 1977. Патент Великобритании В 2092785, кл. G 06 F.-.13/00, 1982. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С ПАРАЛЛЕЛЬ11ЫМ ПРОИЗВОЛЬНЫМ ДОСТУПОМ К СТРОКАМ И ОКНАМ ДАННЫХ (57) Изобретение относится к вычислиАф7РС

„.SUÄÄ 1499355 А1

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

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

Даэюе

3 1499355

Цель изобретения вЂ” расширение функциональных возможностей устройства за счет дополнительного формата обращения в виде строк, На фиг, 1 изображена структурная схема устройства; на фиг, 2 вЂ” схема блока деления на группы; на фиг. 3вЂ” схема блока управления; на фиг. 4вЂ” фрагмент таблицы размещения элементов запоминаемого массива IIO модулям блока памяти для N = 16; на фиг. 5вЂ” блок мультиплексоров, коммутационные 20 элементы которого соединены по правилу соединения и-CUBE сети, на фиг. 6 вЂ” схема подключения управляющих входов блока мультиплексоров при ярусном управлении; на фиг, 7 вЂ” 15 подключение управляющих входов блока мультиплексоров для получения линейного сдвига входного слова; на фиг,8вЂ” фрагмент устрожтва, содержащий схему блока управления мультиплексорами 30 и подключение управляющих входов блока входных данных; на фиг. 9 - схема разбиения управляющих входов двух ярусов мультиплексоров; на фиг. 10связи, осуществляемые блоками входных 35 и выходных данных при выборке строки; на фиг. 11 вЂ” связи, осуществляемые блоками входных и выходных данных при выборке квадратного окна; на фиг. 12 вЂ” временная диаграмма работы, 40 устройства; на фиг. 13 вЂ” фрагмент устройства, содержащий схему блока. модификации адреса и схему блока памяти; на фиг, 14 вЂ” фрагмент устройства, содержащий схемы блока деления 45 на группы, первого и второго блоков мультиплексоров и блока памяти.

Устройство содержит блок 1 памяти, блок 2 входных данных, блок 3 выходных данных, блок 4 Управления, 50 блок 5 модификации адреса, блок 6 деления на группы, первый 7 и второй 8 блоки мультиплексоров.

Блок 6 деления на группы содержит (фиг. 2) первый преобразователь 9 кодов, первый узел 10 мультиплексоров, второй преобразователь 11 кодов, второй узел 12 мультиплексоров и третий узел 13 мультиплексоров.

Блок 4 управления содержит (фиг. 3)первый преобразователь 14 кодов, группу сумматоров 15 по модулю два, второй преобразователь 16 кодов и узел 17 мультиплексоров.

Блок 5 модификации адреса содержит (фиг. 13) с первоro по третий сумматоры 18-20, первый 21 и второй 22 регистры, первый 23 и второй 24 мультиплексоры,первый 25 и второй 26 сумматоры по модулю два, Фрагмент таблицы размещения элементов запоминающего массива по модулю для N = 16 содержит (фиг. 4) верхний левый угол таблицы размещения для N = 16. Цифры в клетках вЂ” это номера модулей памяти, в которые попадают соответствующие элементы запоминаемого массива. Квадраты размером

lбхlб элементов, обведенные двойной линией, называются полями. Квадраты размером 4х4, обведенные жирной линией, „называются участками. Жирными линиями выделены одна строка и один квадрат, произвольно расположенные на таблице, которые рассматриваются в качестве примеров.

Коммутационные элементы узла мультиплексоров соединены по правилу соединения и-СОВЕ сети . Имеющиеся 16 входов и 16 выходов, обозначены соответственно буквами Ч и 11, В нижней части показан один коммутационный элемент с информационными входами ч v и с информационными выходами v,þ,, В зависимости от состояния управляющего сигнала С-входы коммутируются на выход либо прямо, либо перекрестно.

Временная. диаграмма работы отобраI жает следующие сигналы. Сигнал YRсигнал управления мультиплексорами в блоке 7, который для каждого модуля памяти определяет, по какому . сигналу RAS1 или RAS2 заносится в модуль памяти первая половина адреса, Сигнал YC вЂ” это сигнал управления мультиплексорами в блоке 8, который определяет, по какому сигналу CAS1 или CAS2 заносится в модуль памяти вторая половина адреса. Сигнал адрес показывает, какая группа разрядов входного адреса в данный момент находится на входах модуля памяти, Мультиплексоры 23 и 24 управляются сигналами В и В, причем, если эти сигналы равны нулю, то на выход проходят сигналы с нижних входов

5 149935 мультиплексора, а если равны 1, то с верхних входов.

Мультиплексоры MS в блоках 7 и 8 пропускают на выхоц нижний входной сигнал (RAS2, CAS2), если управляю5 щий сигнал (YR или YC) равен нулю, и верхний, если равен единице. Узлы 10 и 13 мультиплексоров по своим информационным связям идентичны и представляют собой старшие n/2 ярусов и-C1JBE сети, Оба блока предназначены для выполнения диадной перестановки: третий вЂ” над всем словом, четвертый вЂ” над двумя группами разрядов входного слова. Определяется какая группа коммутационных элементов управляется кодом c(з, а какая кодом е(эо(= (,(о/1+ 1)//и, где знак а//Ъ, обозначает что число а берется по модулю Ъ, Коммутация на группы производится блоком 12 мультиплексоров (по табл. 6) в зависимости от состояния входных-сигналов o(,о(Устройство предназначено для хра- 25 кения двумерных массивов слов с воз можностью одновременной выборки группы слов, представляющих собой произвольно расположенное на массиве окно или фрагмент строки. Для простоты будем считать, что все слова однобитовые, Переход к словам большей раз. рядности осуществляется путем параллельного соединения подобных устройств, причем блок управления может .быть один на все устройства. Блок памяти содержит 2" = И модулей памяти емкостью 2" бит, где r = 2 ш1 m =

1,2,3...,, Каждый модуль имеет 1/2 адресных входов, по которым в два 4р

Координата Л

«h-òi - ° r O

Адрес в поле

-2r "г«

Адрес поля по I Адрес в поле

Адрес в поле можно также разделить 45 на две части:

Ф ll-C >" И/2 с1 cia-s i - ° « «e

Адрес участка по оси I Адрес элемента на участке по оси J

n вЂ” 4. Общин объем памяти V вЂ” 2

2о

2 бит, Такой объем позволяет хранить массив размером 1024 1024

> 1 бит. Соответственно, строка будет состоять из 16 элементов и окно будет

55 размером 4 4 (фиг. 4) . Структура адреса произвольного элемента следующая:

Адрес квадратного окна и строки иэ

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

16 микросхем памяти. Тогда r = 16;

5 6 этала заносится разрядный код адреса, один информационный вход, один информационный выход, вход выбора режима чтения/записи и управляющие входы занесения адреса (RAS, GAS).

Для обеспечения возможности параллельной выборки строк или квадратных окон необходимо разместить элемен гы запоминаемого массива так, чтобы любой выбираемый на массиве блок данных всегда размещался в различных модулях памяти. Если это условие не выполняется, то для какого-то блока даннйх окажется, что два или более элементов запоминаемого массива находятся по разным адресам в одном и том же модуле памяти и для их выборки потребуется несколько циклов обращения, Кроме размещения элементов массива по модулям памяти, необходимо их разместить Ilo соответствующим ячейкам внутри модулей. Общий объем памяти, состоящей из 2 модулей объемом 2" бит, будет V = 2 2 = 2"

2 бит. Будем рассматривать двумерм ную запоминающую среду, имеющую форму квадрата и размер 2 . 2

v,уi нП

Для задания произвольного элемента на массиве необходимо задать U/2-разрядный код адреса координаты I и U/2 разрядный код адреса координаты J, Pазделим весь двумерный массив на квадраты из Ы + N элементов, которые будем называть полями, Поле разделим на участки размером и к и элементов (фиг, 4), Будем записывать координаты произвольного элемента массива одним

П-разрядным словом, называемым адресом элемента массива:

1499355

А е-."н

Адрес Адрес Адрес Адрес поля участка элемен- поля в поле та на участке

ot at

Адрес элеменАдрес участка в та на участке поле

Например, для элемента поля с координатами I = 7, J = 13, номер модуля памяти определится следующим образом: (I//n) лР = (7//4) - = (3) (0011) ч = 1100; J = 13 = 1101N = 1100 + 1101 = 0001 = 1, т.е. элемент массива с этими координатами попадает впервый модуль памяти, Такое размещение элементов данных по модулям памяти, заданное таблицей, в которой числа указывают номер модуля, щ сохраняющего соответствующий элемент запоминаемого массива, представлено на фиг, 3. Эту таблицу размещения легко получить в соответствии с правилом диадных (по модулю 2) переста25 новок для строк всех участков, причем порядок перестановок определяется как J// n (J О, 1,...,1023; п 4):

Элементы запоминаемого массива размещаются по модулям памяти специальным образом. Все элементы полей размещены одинаково. Размещение в поле подчинено следующему правилу: элемент поля с координатами I u J помещается в модуль памяти с номером N: вЂ” двоичные коды чисел N

Ти J; вЂ” модуль числа I по основанию n смещение разрядов кода

I вправо íà n/2 позиций циклически; вЂ” операция поразрядного сложения по модулю два. где N, I, J

J//„ * 2

J//„ = 3

Так как все элементы участка попа- 35 дают в модули памяти с одним и тем же адресом, равным адресу участка, то элемент массива с координатами м ° ° + р и 4 11 fe. э ° ° ° e s Ж о находится в модуле памяти по адресу 40

Адрес

Адреса

00000011

00000100 в модулях

00000001

00000010

000000 11 (Для строки) 00000100

00000101 в модулях

00000011

D0000100

00000011 (Для квадрата) 00000 100 00000 100

Разряды ttt, c(o a ot o(a определяют 55 смещение адреса фигуры (строки или квадрата) относительно начала участ" ка и используются в адресной части устройства для управления, N (I/2 ) вЂ” Ю J/N, Номер модулей

9, 10 11

12, 13, 14, 15

Номера модулей

12, 13 14.

15, 11, 7 эЯ 14 И /я 9 ° ° ° q э (й °

Например, выделенные на фиг. 4 элементы строки и квадрата попадают в ячейки модулей памяти со следующими адресами:

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

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

Пусть 1 1 вЂ” номер линии в шине данных. В качестве основного примем порядок, при котором для двух типов образцов (квадратные окна и строки) ин- 2р дексы номеров линий будут нумероваться слева направо и сверху вниз, начиная с нуля, Например, для N = 16

1ь 11 1 1з

14 25

18 1 9 l

4т l,ç 1н 11 для квадратного окна и

10 1 1 1 21 gl wl sl pl 11 е 9 э п 4 qg и ю для строки. Если элементы выбираемого блока данных попадают в модули памяти с номерами, равными номерам ли-. ний шины данных, то такой порядок модулей в выбираемом блоке называется каноническим. При перемещении рамки .окна или строки по таблице размещения в них получаются порядки, отличные от канонического. Для восстановления порядка при чтении и записи необходимо произвести упорядочение данных. 4

Для этих целей в устройстве используются блоки 2 и 3 и блок 4 управления.

Коммутационные элементы, составляющие блоки мультиплексоров для упоP «« H ». «e HH T« o -45 вилу соединения n-CUBE сети (фиг, 5), В нижней части показан базовый коммутационный элемент и два состояния коммутации в зависимости от значения . управляющего сигнала, Будем называть входы и выходы коммутационных элементов, по которым осуществляется перестановка, информационными. На вход сети подается входной вектор V

v, 1 в vN. ° ° ° v)vo э которыйт прохо

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

w,w так, что W = p(V), где p(V) функция перестановки, Будем считать, что индексы компонент векторов V u W возрастают слева направо (фиг. 5) . Ряд коммутационнь» элементов сети называется ярусом.

Сеть состоит из n -= 1оя,М ярусов,. которые нумеруются по порядку. Если все управляющие сигналы коммутационных элементов яруса одинаковы, то сеть реализует диадные перестановки входного вектора, На фиг, 6 показано, как соединяются управляющие входы коммутационных элементов для управления диадными сдвигами. Всего существует

N различных диадных перестановок, причем нулевой ярус осуществляет перестановку элементов в парах, первый ярус вЂ” пар элементов в четверках, второй ярус вЂ” четверок элементов в восьмерках и т.д. Остальные диадные перестановки осуществляются при совместном включении нескольких ярусов сети. Ha n-CUBE сети легко осуществляются также перестановки типа линейного циклического сдвига, при этом поярусное управление уже недостаточно.

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

1-й ярус на две группы (коммутационные элементы О, 2, 4, 6 и т.д, первая группа и 1, 3, 5, 7 и т,д, вторая группа), 2 вЂ” и ярус на четыре группы (коммутационные элементы О, 4, 8 и т.д, первая группа,l, 5, 9 и т,д. вторая группа, 2, 6, 10 и т,д. третья группа и 3, 7, 11 и т,д. четвертая группа), Коммутационные элементы последнего яруса управляются по отдельности. Всего получается N-1 групп. Таким образом, для управления линейным циклическим сдвигом необходимо и-разрядному коду числа сдвигов поставить в соответствие (N-1)-разрядный управляющий код, который управляет коммутационными элементами всех групп, Для этих целей служит третий преобразователь 14 кодов в блоке управления блоками мультиплексоров данных (фиг, 3 и 8), Значения управляющего кода для любого сдвига можно получить непосредственно по

1499355

12 схеме и-С!)ВЕ сети, определив состояние коммутационных элементов для каждого сдвига. Если пронумеровать по порядку слева направо управляющие входы перечисленных групп коммутационных элементов и записать значения управляющих сигналов для каждого сдвига, получится табл. 1 (для !1

) 6), значений управляющих кодов для

5 реализации линейных циклических сдвигов вправо на п-CUBE сети на 16 входов.

Таблица 1

Номер яруса перестановочной сети личина нейнего о(клического вига

Значения управляющих сигналов

0 1 2 3 4 5 6 7 8 9 1011121314

2 3 4 5 6 7 8 9 10 ll 12 )3 14 15

О 0 О О

О 1 О О

О 1 1 О

О 1 1

1 1 1 1

I 1 1 I

1 1 1 l

О l )

О 0 1 1

О О О

О О О О

1 О О. О

1 0 0 О ! О О О

1 О О 0

0 О О

О О О

1 О О

1 1 О

1 1 1

1 l 1

1 1 1

I 1 1

О 1

О О 1

О О О

l быть преобразован в дополнительный код .

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

Значения управляющих кодов для реализации диадных сдвигов íà n-CUBE сети на 16 входов приведены в табл,2.

Таблица приведена для сдвига вправо. Так как сдвиг вЂ” циклический, то легко перейти от правого сдвига к левому. Сдвиг влево на i позиций соот- 40 ветствует сдвигу вправо íà N-i позиций. Поэтому, если сдвиг необходимо. осуществить влево, код сдвига должен

Таблица 2

Номер яруса перестановочной сети

Величина диадного сдвига

1 2

Состояние управляющих сигналов

О 1 2 3 4 5 6 7 8 9 10. )l 12 13 14

О О О О О О О О О О О О О О О О 000

I О О О О О О О О О О О О О 0 0 001

О О

0 1

1 О

0 О

1 1

0 1

1 О

0 0

1 1

О 1

1 О

О О

1 1

О 1

1 О с

О О О О

0 Г О О

1 1 1 О

1 1 1 1

О 1 1 1

О О 1 1

1 0 О 1

1 0 О О

О 0 0 О

О 1 О О

1 1 1 О

1 1 1

О 1 1 1

0 О 1 1

1 0 О )

1 О О О

О О О

0 О 0

О 1 О

0 О О

О О О

0 0 0

О О 0

1 О О

1 1 1 ! 1 1

1 1. 1

1 1 . 1

1 1 1

1 1

1 1 1

0 1 1

00!

0 1 1

I 00

1 0

1 1 О

111

00 1

О I )

101

1 1 1

l 499355

Продолжение табл.2

Номер яруса перестановочной сети

Величина диадно го сдвига

0 1 2 3

Состояние управляющих сигналов

О I 2 3 4 5 6 7 8 9 10 11 12 13 I4!

О О О

О 0 О

0 О О

О О О

О О 0

1 1 1

Описание управления сетью можно представлять также матрицей n < Н/2, 30 элементы которой позиционно соответствуют положению коммутационных элементов в сети и определяют для них значения управляющих сигналов, Такая матрица дает наглядное представление

:о коммутации элементов сети и может быть легко получена иэ соответствую,шего управляющего кода (табл, 1 и 2), Например, описание управления сетью при реализации сдвига входной после- 4р довательности вправо на 9 элементов имеет вид:

1 1 1 1 1 l 1

1 О 1 О 1 0 1 0

МЪ = 1 О О 0 1 0 0 0 45

О 1 1 1 1 1 1 1

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

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

Эта композиция определяется как сумма по модулю два управляющих кодов соответствующих линейного и диадного сдвигов, Так, если линейный сдвиг описывается матрицей М„„ c38s а диадный вЂ” Мч а, то матрица управления

М < P к" обеспечивающая упорядочение последовательности элементов строки на сети, определяется так: . (стра ки) (утро ки1 (crposu)

M M ч.сав О+ М у.о.сэв

Пример. Рассмотрим выборку выделенной на фиг, 4 строки. Ее адрес определяется кодом (табл. 31.

Таблица 3

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 .1 0 кода адреса

Значения разряда кода адреса О О О О О О 1 О 1 1 0 О 0 О О 0 0 1 О 1

О 1 1 0

1 1 1 0

О О О 1

1 0 О 1

О 1 1 1

1 1 1 1

0 О О О

1 О О О

0 1 1 О

1 1 1 0

О 0 О 1

1 0 0 1

О 1 1

1 1 1

0 0 0 О

О 0 О О

1 1 0

1 1 О

1 1 1 0

О О О 1

О О О l

0 0 О 1

О О О 1

1 1 1 1

1 I 1 1

1 1 1 .1

1 1 1 1

О О 0 О

0 0 О 0

О О 0 0

О 0 0 0

0 О 0 0

О О О 0

1 1 1 1

1 I 1 1

1 1 1

1 1 1 I

1 1 1 1

1 1 1

0 О 1 О

О О 1 l

0 100

010 l

0111

1000 °

100!

1 О 1 1

1 100

1 1 О 1

1 l 1 О

1 l 1 1

1499355. тельно начала поля и на 3 позиции (,(«,1„= 11) по I относительно начала участка. Как следует из таблицы размещения (фиг. 4), элементы строки размещены в следующих модулях памяти (табл. 4)., l

Таблица 4

Элемент в строке .(линии шины данных) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Модуль памяти в котором размещен элемент

9 10 11 4 5 6 7 0 1 2 3 12 13 14 15 8

Табл. 4 отражает перестановку дан- бираемую строку при чтении, необходиных при записи строки в память. Для 35 мо реализовать обратную перестановку того чтобы правильно упорядочить вы- (табл, 5), Т а б л и ц а 5

Модуль памяти 0 1 2 3 4 5 6 7 8 9 10 ll 12 13 14 15

Линии шины данных (элемента в строке) 7 8 9 10 3 4 5 6 15 О 1 2 ll 12 13 14

l 1 1 1 1 1 I 1

000 1000 1

1 1 100000

Полученное описание управления сетью

1 1 1 1 1 1 1 1

0 1 0 1 0 1 0 1

I 1 1 0 1 1 1 0

0 0 0 1 I 1 1

50 у,л.сЭв

Матрица М v s Э формируется ис- ходя из того, что строка смещена относительно начала участка на три позиции (с(„ с(„ = !1). При этом необходимо учесть, что при формировании таблицы размещения на фиг. 4 использовались диаднйе сдвиги для групп по

Адрес поля по I Адрес поля по 3

Адрес участка в Адрес участка поле по I в поле по J

Адрес элемента Адрес элемента

5 на участке по Т на участке по J

Указанная строка смещена на 5 позиций (o(y a(g,,= 010! ) no 3

В соответствии с правилом формиро- 15 вания управления сетью образуем матрицы М„„ а, и М „в,агав ° Так как строка сдвинута от начала поля на 5 позиций вправо, для восстановления порядка данных необходимо их сдвинуть на 5 40 позиций влево. Сдвигу влево на 5 позиций соответствует сдвиг вправо на

16-5 = 11 позиций. Таким образом, по

BxoAHoM7 KollY с(с(а(, о1, = 0 10 1 (ppIIDJI нительный к нему 1011) на выходе пре-45 образователя 14 кодов (фиг. 8) появится код, соответствующий матрице управления сетью (см. табл, I):

4 элемента. Следовательно, общий диадный сдвиг имеет величину 12 (код

1100) и соответствующая матрица

М „11 а определяется табл. 2:

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

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

При выборке произвольно расположенного окна для получения правильного порядка элементов необходимо также выполнять композицию перестановок: линейные циклические сдвиги, кратwe п; линейные сдвиги íà I 2,...,n-l. поэицию в группах иэ п элементов, со18

1499 355

1О

15 (окна! у.п.еде ставляющих строки квадратного фраг- мента (окна); диадные перестановки для компенсации диадных сдвигов; присутствующих в таблице размещения. Как и в случае выборки строки, для управления перестановочной сетью формируется матрица управления в виде (окноi) (окн» I (о к»»!

= М..с в Мв.огв

Матрица М с.ое определяется следующим образом. При смещении окна относительно положения опорного участка по оси Л линейные сдвиги элементов происходят внутри строк (п строк из и элементов), Такие сдвиги выполняются на и/2 младших ярусах перестановочной сети, которым в матрице управления Мп.e3s соответствуют первые

Ф о!Е о(с(Ы c(1 <" )g 4(g о(1 о

О 0 О 0 0 О 1 1 1 1

Разряды о(, 4 = 11 и о(п,о= 11 указывают на то, что окно сдвинуто относительно опорного участка соответственно на три позиции вправо и на три позиции вниз, Чтобы восстановить порядок элементов, необходимо реализовать компенсирующие сдвиги, Сдвиг окна влево на три элемента соответствует циклическому сдвигу внутри строк (элементов данных, поступающих на группы линий шины данных (0,1,2,3); (4э5э617);(8э9, 1Оэ 111 ;(12ь !ЗА 14э 15)) на один элемент вправо. Следовательно, строки 0 и 1 матрицы формируют по коду управления, соответствующему сдви- 40 гу вправо на 1 разряд (табл. 1). При этом рассматриваются только те разряды кода управления, которые связаны с нулевым и первым ярусами сети.

Сдвигу окна на три позиции вверх соответствует сдвиг на одну позицию вниз. Так как одной позиции в данном случае соответствует целая строка, то это эквивалентно циклическому сдвигу вправо на 4 элемента, Следовательно, строки 2 и 3 матрицы М „g а формиру50 ются по коду управления, соответствующему сдвигу вправо на 4 разряда (табл, 1), И в этом случае рассматриваются те разряды кода управления, 55 которые связаны с вторым и третьим ярусами сети, Таким образом, в соответствии с кодом et о!, = 11 и о1„ Ы„= 11 при обп/2 строк (О, 1,...,n/2-1) . При смещении окна по оси I линейных сдвиг происходит на величину, кратную п (в соответствии с количеством элементов в строке). Сдвиги, кратные выполняются на сети старшими п/2 ярусами, и в матрице Г! „ „. им соответствуют строки n/2, п/2+1...п-1, Отсюда следует, что матрица М „,а для управления сетью при выборке окна формируется для первых n/2 строк по величине смещения окна относительно опорного участка по 3, а для последних n/2 строк вЂ” по величине смещения по I. Например, квадратный фрагмент, вьделенный на фиг. 4, имеет адрес, соответствующий положению левого верхнего его элемента (табл.6).

Таблица-6 (9 ф 7 о(6 я 4 Э и 1 о

0 О. О О О О 1 1 1

1 ращении к блоку данных в виде квадратного фрагмента преобразователь 14 кодов вьдает управляющие сигналы, формирующие матрицу управления:

1 1 1 1 1 1 1 1

1 О 1 О 1 О 1 О

1 1 1 1 1 1 1 1

1 1 1 1 О О 0 0

Величина диадного сдвига определяется положением опорного участка в поле по координате J, т.е, разрядами

a(„ „ ...,o(>! кода адреса. В таблице размещения реализован одномерный диадный сдвиг для групп иэ и элементов, поэтому для компенсации диадного сдвига используются старшие п/2 ярусов сети. Старший (n-1)-й ярус управляется (п-1)-м разрядом адреса (о(), (n-2)-й ярус вЂ” (n-2)-м разрядом (о1„ ) и т,д. Это справедливо для всех участков. Однако произвольно адресуемое окно может располагаться так, что попадает сразу на два участка по оси J, В таком случае для разных частей окна, а значит, и для разных частей сети должны реализовываться различные диадные сдвиги, Для модулей памяти, попадающих на опорный участок, величина диадного сдвига

DS1 определяется разрядами

» н-1 <" н ° ° ° о/п(о ° а для следующего участка кодом

nS2 - (Ы„, „,,, ZÄ«Ä)//

""- »-1 о и-2 " h l 2

l 499355

00 01 . 10 11

? >уппы коммут ацио нны элементов яруса

DS) DS1 DS1 DS1

DS I DSI DS 1 DS2

DS1 DSI DS2 DS2

DS1 DS2 DS2 DS2

0 0 О О О 0 О 0

О О О О О О О 0

1 О О О 1 О О О

1 О О О 1 О О 0

20 (омно)

y.D, 038 фв а

О 1 1 1 О 1 1 1

Такое п авление сетью обес и

30 у р. печ вает упорядочение элементов блока данных (фиг, 11), приведенное в табл.8 (при записи) и 9 (при чтении).

Т а блица 8

Линии шины данных

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

3 12 14 14 15 О 1 2 11 4 5 6 7 8 9 10

Модуль памяти

Таблица 9

Модуль памяти

О 1 2 3 4 5 6 7 8 9 )О 11 12 13 14 15

4 4

Линии лины данных 5 6 7 О 9 10 1! 12 13 14 15 8 1 2 3 4

Рассмотрим работу адресной части устройства. К адресной части устройства относится блок 5 модификации адреса, блок 6 деления на группы, О первый 7 и второй 8 блоки мультиплексоров и адресные входы модулей памяти. Как следует из описания размещения информации по модулям памяти, при

Нетрудно заметить, что существует и вариантов сочетаний DS I и DS2 при управлении частями старших и/2 ярусов сети, Они определяются величиной смещения окна относительно опорного участка по J, т.е. разрядами A/t-...,., с(кода адреса, Для

N 16 варианты сочетаний сдвигов для групп элементов 2-го и 3-ro ярусов сети представлены в табл. 7.

Таблица 7

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

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

Управление различными группами коммутационных элементов выполняется преобразователем 16 и узлом 17 мультиплексоров, Теперь можно сформировать матрицу (eкно(!

М а для рассмотренного примера выборки окна, положение которого задано на фиг, 4, Величина диадного сдвига для модулей памяти 3, 15, 11, 7 определяется размерами о(з Ы кода адреса, т,е. DSI = Il а дпя остальных элементов окна DS2 = (11+01)//4

О. В соответствии с кодом Ы, а(и типом обращения (окно) преобразователь 16 кодов выдает управляющий код

1000 на вход узла 17 мультиплексоров, с выхода которого снимается код управления 2-м и 3-м ярусами сети, соответствующий матрице .

Окончательно управление перестановками в рассматриваемом примере имеет вид: выборке произвольно расположенного квадрата модули памяти можно разделить на две группы, адреса которых по оси J отличаются на "+1", и на две группы, адреса которых по оси I отличаются тоже на "+I". В некоторых микросхемах памяти для сокращения числа адресных входов полный адрес

1499 35

22 выбираемого слова заносится в дваэтапа: сначала заносится одна полови-. на адреса (по сигналу RAS) а затем вторая половина .(по сигналу CAS), В устройство вводятся по два сигнала занесения первой половины адреса (RAS1 и RAS2) и по два вЂ” второй (СА$1 и CAS2). Эти сигналы смещены во времени один относительно другого, Для каждого модуля памяти на один цикл обращения коммутируются два сигнала из этой четверки (по одному из каждой пары) в зависимости от управляющих сигналов YR и УС, вырабатываемых в блоке деления на группы, Непосредственно коммутация сигналов RAS1 или

RAS2 и СА$1 или CAS2 осуществляется соответственно первым и вторым блоками.мультиплексоров адреса, Если по 2р сигналу RASl занести разряды адреса, относящиеся к координате J, s часть модулей памяти, затем прибавить к этой части разрядов +1 и занести по-. лученный адрес в оставшиеся модули 25 памяти по сигналу RAS2, то после проведения аналогичной операции с занесением разрядов адреса, относящихся к координате I, по сигналaM GAS 1 и

CAS2, требуемые адреса будут полнос- 30 тью занесены в модули памяти, Временная диаграмма операции занесения адреса представлена на фиг. 12.

Сигналы YR u YC не изменяют своего значения .в течение времени занесения

;адреса, Время 1, - время удержания адреса (разряды еС-, вЂ : е() определяется иэ конкретных характеристик микросхемы памяти. Время t вЂ” время, необходимое для выполнения операции прибав- 40 ления .+1 н получения адреса где а(-1- o(, = otI â€”: o(о +1. Минимальное время между сигналами RAS1 и RAS2 равно сумме времен t, + t Аналогичная картина имеет место и для сигна- 45 лов САБ1 и CAS2; t . - время удержания адреса; t вЂ” время его модификации.

Таким образом, эа счет удлинения цикла обращения к памяти на величину

+ + t 3+ t 4 обеспечивается воз1 можность отказаться от необходимости иметь у каждого модуля памяти свой сумматор, Для режима работы, в котором выбираемые данные не имеют смещения QTHoсительнО участка мОжнО дпя 55 ускорения йроцесса выборки отказаться от четырехтактной системы занесения адреса, а испольэовать обычную двухтактную по укороченной временной,диаграмме. Модификация адреса (прибавление +1 к определенной части разрядов и их коммутация на адресные вхо- ды модулей памяти) осуществляется в блоке 5 модификации адреса, Адресные входы модулей памяти подключены к адресной шине специальным образом, r h

2 вЂ” вЂ” разрядный адрес (где 2 вЂ” объем модулей памяти) поступает к модулям памяти в виде трех шин Q, Х, У, Разг u рядность шины Q = вЂ” вЂ” вЂ” (где N =

2 2

2 вЂ” число используемых модулей памяти) ° К этой шине параллельно подключаются все старшие разряды адресных входов модулей памяти, Разрядность шин Х и У равна n/2. Шины Х, У и S связаны следующим сйособом:

У=X@S ч @

Yn g-1 е Y„1<-<» î - ь(1-1

Э Б (1-,, Х hl1 2 О Хh/2-1» XoВ 0 где S вЂ” код типа обращения.

При этом и/2 младших разрядов адреса модулей памяти подключаются к шинам

Х и У по следующему правилу: если (п-1)-й разряд в номере модуля памяти равен О, то вход а h11- модуля памяти подключается к (n/2-1)-му разряду шины Х, т.е. к Х „,, „, а если этот разряд в номере модуля равен 1, то к (и/2-1)-му разряду шины У, т.е. к У „ „ и т.д, Такое диадное соединение адресных входов позволяет при выборке строк подавать на разные группы из п модулей памяти адреса, перебирающие все значения в и/2 ипадших разрядах. Это требование можно проверить по адресам выделенной на и фиг, 4 строки, В разрядах а,а (- 2) на адресных входах модулей памяти следующие адреса:

Номер модулей памяти а,а о

8, 9, 10, 11 0 1

1 0

12, 13, 14, 15 0 0

Таким образом, если S = 11...1, то все адреса в группах вЂ” различные. При

S = --00...0 получим, что У = К+00...0=

= Х и во всех модулях одни и те же адреса, Рассмотрим процедуру занесения адреса в модули памяти на приме" р ах, Выборка квадрата с адресом

OOOOOOlll1OOOOOO111 деленного на фиг. 4. Код S в этом

1499355

40 режиме равен 00, следовательно, зна" чения адреса в разрядах а а на всех модулях одинаковы, Перед началом выборки состояние управляющих сигналов мультиплексоров В = 0 и В, = О, что означает, что открыт канал для нижних (на фиг. 13) шин мультиплексоров 23 и 24, В этом состоянии

° (э 1 7 ofg dg 4g o(a(000000 1 1, Так как 0

S 00, то этот адрес попадет без изменения на все модули памяти, т.е. аэа а а»а эа <а„а 0000001 !.

Схема деленйя на группы выделяет

MOplIJIH IIcIMIITH 3, 15, 1 1, 7, для KOTO 15 рых этот адрес заносится по сигналу

RASl. После занесения адреса через время t (фиг. 12) появляется сигнал +1 к разряду о(и а(з»a(g = 00000100, 20 который по сигналу RAS2 заносится в остальные модули памяти. После этого происходит изменение сигнала BII = 0 на во= l u

a = ОООООО!1, Схема деления модулей на группы выделяет модули 3, 12, 13, !4, для которых этот код заносится по сигналу CAS1. Затем через время t> прихо" дит сигнал +1 к (17, который иэменя- jp ет состояние выхода íà е(,з вЂ . « =

= 00000100 и этот код эаноситск по сигналу CAS2 в оставшиеся модули памяти. Таким образом, в модули памяти заносятся следующие коды адреса:

Номер модулей Код адреса памяти

3 0000001100000011

15, 11, 7 0000010000000011

12э 1Зе 14 0000001100000 100

О, l, 2, 4, 5, 6, 8, 9, 10 0000010000000100.

Соответствие этих адресов требуеьым для выборки квадрата проверяется по таблице на фиг. 4.

Выборка строки с адресом

О О О О О О 1 О 1 1 О О О О О О О. 1 О 1 °

Если при выборке квадрата может быть четыре различных адреса в модулях то при выборке произвольно расположенной строки адрес по оси Х один и тот же для всех модулей, а по оси J могут быть .два адреса в разрядах a(4 a(и всегда различные адреса II Раэрядах (,(,„ Изменение адреса55 в разрядах ю(at выполняется за счет диадного способа соединения адресных входов модулей памяти, а в разрядах a(y а(» вЂ” за счет деления на

24 группы и занесения адреса IIo ocu J в два такта. В этом режиме код $

11, В О, В, 1 и + 1 прибавляется к разряду g„(g»). Так как при выборке строк разряды а(,,с(„,..., a(ale принимают вполне определенные значения в зависимости от значения разрядов o(« a(qy то они и подаются на адресные шины. Поэтому сначала

Ыз уа((а(5 » < д <(= 00000011 который попадает на адресные входы модулей памяти:

,Номер модулей Код адреса памяти

gt 1, 2, 3 00000011

-00000010

8, 9, 1О, 11 00000001

12, 13, 14, 15 00000000

Группа деления на модули выделяет следующие модули; 9, 10, 11, 4, 5, 6, 7, О, 1, 2; 3 для которых занесение происходит по сигналу RASI. После это" го произойдет прибавление +1 к разряду «»:

e(00000111 который попадает на модули памяти в следующем виде:

Номер модулей Код адреса памяти

О, ° 0, 3 0000011!

8, 9, 10, 11 00000101

12, 13, 14, 15 00000100

Этот код заносится в модули памяти с номерами 12, 13, 14, 15, 8, После этого В становится равным 1, à S QO. В результате на все модули памяти подается код

+ (= n0O000 10.

Окончательно можно записать:

Номер Модулей Код адреса памяти

9, 10, ll 0000001000000001

4, 5, 6, 7 0000001000000010

О, 1, 2, 3 0000001000000011

12, 13 14 15, 8 0000001000000101

Эти адреса соответствуют выделенной строке, Рассмотрим деление на группы с одинаковым адресом, Блок 6 деления на группы предназначен для деления модулей памяти на две группы, адреса, которых по оси J отличаются на +1, и на две группы, адреса которых по оси I отличаются на +1, На выходе схемы деления на группы имеем N линий YR управления блоком 7 мульти25

1499355

Входной код

Выходной код

0 1 2 3 4 5 6 7 8 9,10 !1 12 13 14 15

1 1 1 1 1 1 1 1 1 1 I 1 1

0 1 1 1 О 1 I 1 О I 1 О

О О 1 1 О О 1 1 О О 1 I „..0

О О О 1 О О О I О О О 1 0

1 1 1

I I 1

О 1 1

О 0 1

Т а б л и ц а 11

Выходной код

Входной код

О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 1 1 1 l 1 1 1 1 1 1

О О О О 1 1 1 -! 1 1 1

О О О О О О О О i I 1

0 О О О О О О О О 0 О

1 1 1 1

1 1 1 1 1

0 1 1 1 1

11 на п групп, как и при упорядочении данных, где каждая иэ групп проиэво55 дит перестановки среди входов сети, номера которых соответствуют номерам модулей памяти в столбцах квадрата, и каждая. такая группа управляется отплексоров и 11 линий YC управления-блоком 8 мультиплексоров (фиг. 14).

Те линий, на которых пр

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

Патент 1499355