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

QD 00 СЛ

сл

31499

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

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

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

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

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

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

Блок 5 модификации адреса содержит (фиг, 13) с первого по третий сумматоры 18-20, первый 21 и второй 22 регистры, первый 23 и второй 24 мультиплексоры, первый 25 и второй 26 сумматоры по модулю два.

Фрагмент таблицы размещения элементов запоминающего массива по модулю для N 16 содержит (фиг, 4) верхний левый угол таблицы размещения дпя N 16, Цифры 3 клетках - это номера модулей памяти, в которые попадают соответствующие элементы запоминаемого массива. Квадраты размером 16x16 элементов, обведенные двойной линией, называются полями. Квадраты размером 4x4, обведенные жирной линией, называются участками. Жирными линиями выделены одна строка и один квадрат, произвольно расположенные на таблице, которые рассматриваются в качестве примеров.

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

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

Мультиплексоры 23 и 24 управляются сигналами В и В, причем, если эти сигналы равны нулю, то на выход проходят сигналы с нижних входов

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

Мультиплексоры MS в блоках 7 и 8 пропускают на выход нижний входной сигнал (RAS2, CAS2), если управляю- i щий сигнал (YR или YC) равен нулю, и верхний, если равен единице. Узлы 10 и 13 1 льтиплексоров по своим информационным связям идентичны и представляют собой старшие п/2 ярусов п-СШЕ сети. Оба блока предназначены для выполнения диадной перестановки: третий - над всем словом, четвертый - над двумя группами разрядов входного слова. Определяется какая группа коммутационных элементов управляется кодом какая кодом 0//П, где знак а//Ь, обозначает что число а берется по модулю b, Коммутация на группы производится блоком 12 мультиплексоров (по табл. 6) в зависимости от состояния входных сигналов с, о( ,

Устройство предназначено для хранения двумерных массивов слов с возможностью одновременной выборки группы слов, представляющих собой пра- извольно расположенное на массиве окно или фрагмент строки, Дпя простоты будем считать, что все слова однобитовые. Переход к словам большей раз- рядности осуществляется путем параллельного соединения подобных устойств, причем блок управления может быть один на все устройства. Блок памяти содержит 2 N модулей памяти емкостью 2 бит, где г 2 та; m 1,2,3,..., Каждый модуль имеет г/2 адресных входов, по которым в два

Координата I

Хп , ,. 1, -Xuii / Адрес поля по I Адрес в поле

0

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

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

0

состоящей из 2

модулей объ- р

9 бит, будет V 2 бит. Будем рассматривать двумер0

памяти, 5 емом 2 2

ную запоминающую среду, имеющую форму квадрата и размер 2 .2 , . Для задания произвольного элемента на массиве необходимо задать U/2-разряд- ный код адреса координаты I и U/2 разрядный код адреса координаты Jt

Разделим весь двумерный массив на квадраты из Ы + N элементов, которые будем называть полями, Поле разделим на участки размером п к п элементов (фиг. 4), Будем записывать координаты произвольного элемента массива одним и-разрядным словом, называемым адресом элемента массива:

5

0

Координата 3

f(ulj.( i-ii--i n d

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

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

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

, с(п-1 , ct п-г

ПП

d hii-i I ч

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

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

d hii-i I ч

п 4. Общий объем памяти V 2 2 бит. Такой объем позволяет хранить массив размером 1024 1024 1 бит. Сортветствелно, строка буце Р состоять из 16 элементов и окно будет размером 4 4 (фиг. 4). Структура адреса произвольного элемента следующая:

fn И C/g...

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

участке

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

N . (1/2)

© J/N,

N, I, J - двоичные коды чисел N,

I и :j; I//h - модуль числа I по осно„ ванию п;

- смещение разрядов кода I вправо на п/2 позиций циклически; ф - операция поразрядного

сложения по модулю два.

J// О

J/A

Так как все элементы участка попа- дают в модули памяти с одним и тем же адресом, равным адресу участка, то элемент массива с координатами

0/19 ...«,+ , /м .t. находится в модуле памяти по адресу

Разряды d/j, с(, и с/, /в определяют смещение адреса фигуры (строки или квадрата) относительно начала участка и используются в адресной части устройства для управления.

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

j//,

J//n

... с l(l:

« ... .

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

(Дпя строки)

(Для квадрата)

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

914

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

Пусть номер линии в шине данных, В качестве основного примем порядок, при котором для двух типов об

разцов (квадратные окна и строки) ин-20 вый ярус - пар элементов в четверках.

дексы номеров линий будут нумероваться слева направо и сверху вниз, начиная с нуля. Например, для N 16

Ь Ч 1.3

Ч Ч Ь

Ig ItO lii

4i ta f4 -IS для квадратного окна и

Iol,l,l3l4l 5l l,l,l9l,.lttl,4,4.5

ДЛЯ строки. Если элементы выбираемо- го блока данных попадают в модули памяти, с номерами, равными номерам линий шины данных, то такой порядок модулей в выбираемом блоке называется каноническим. При перемещении рамки окна или строки по таблице размещения в них получаются порядки, отличные от -канонического. Для восстановления порядка при чтении и записи необходимо произвести упорядочение данных, Для этих целей в устройстве используются блоки 2 и 3 и блок 4 управления.

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

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

превращаясь в вектор W w

10

так,

что W p(V), где p(V) - функция перестановки.

Будем считать, что индексы компонент векторов V и W возрастают слева направо (фиг. 5), Ряд коммутационных элементов сети называется ярусом. Сеть СОСТ9ИТ из п logjN ярусов,, которые нумеруются по порядку. Если все управляющие сигналы коммутацион- . ньк элементов яруса одинаковы, то сеть реализует диадные перестановки входного вектора. На фиг, 6 показано, как соединяются управляющие входы комму- тационных элементов для управления диадными сдвигами. Всего существует N различных диадных перестановок, причем нулевой ярус осуществляет , перестановку элементов в парах, пер0

25

35

ЗО Q

.

50

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

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

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

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

ОООрООООООООООО О 000 1000000000000000 001

управляющих сигналов для каждого сдвига, получится табл. I (для W 16),значений управляющих кодов для реализации линейных циклических сдвигов вправо на п-СШЕ сети на 16 входов..

Таблица 1

I . .:

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

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

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

Таблица 2

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

М,

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

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

0

5

0

5

Q

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

(строки)(строки)(строкм)

М ,, М w.caa ® М у.о.сЭй

Пример, Рассмотрим выборку

выделенной на фиг. 4 строки. Ее адрес определяется кодом (табл, З). Таблица 3

15

I в

I

-1

1499355

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

Указанная строка смещена на 5 по- зиций («{j ,о 0101) по л относиМодуль памяти, в котором размещен элемент 91011

5670123 12 13 14 15 8

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

ТаблицаЗ

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

Линии шины данных (элемента в строке)

789 10 3456 15 О 1

В соответствии с правилом формиро- вания управления сетью образуем матрицы М,эдИ М,, д.. Так как строка сдвинута от начала поля на 5 позиций вправо, для восстановления порядка данных необходимо их сдвинуть на 5 позиций влево. Сдвигу влево на 5 позиций соответствует сдвиг вправо на. 16-5 11 позиций. Таким образом, по входному коду c(j c( (дополнительный к нему 1011) на выходе пре- образователя 14 кодов (фиг. 8) появится код, соответствующий матрице управления сетью (см. табл. 1):

М

у. л.сЗв

Матрица М , j,3g формируется исходя из того, что строка смещена относительно начала участка на три позиции ( о(,,оС„ П). При этом необходимо учесть, что при формировании таблицы размещения на фиг. 4 использовались диадние сдвиги для групп по

16

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

Таблица 4

И 12 13 14

4 элемента. Следовательно, общий ди- адный сдвиг имеет величину 12 (код 1 100) и соответствующая матрица УТ)сдъ определяется табл. 2:

00000000 00000000 11111111 .11111111. Теперь можно определить управление сетью в виде

(строки)

М

iB.cae

jj 5

0

5

Гстрвки) (стреки) (стрвкм)

v м„. .., , .,,

ул-сЭв S.J.

1 1

1 О

1111

о 10 1

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

При выборке произвольно расположенного окна для получения правильного порядка элементов необходимо также выполнять композицию перестановок: линейные циклические сдвиги, кратные п; линейные сдвиги на 1,2,...,п- ПОЗИ1ЩЮ в группах из п элементов, составляющих строки квадратного фрагмента (ркна) диадные перестановки для компенсации диадных сдвигов-, присутствующих в таблице размещения. Как и в случае выборки строки, для управления перестановочной сетью формируется матрица управления в виде

(ОКМО.) fe

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

Разряды о(,о(„ 11 ис,, 11 указывают на то, что окно сдвинуто относительно опорного участка соответственно на три позиции вправо и на три позиции вниз. Чтобы восстановить порядок элементов, необходимо реализовать, компенсирующие сдвиги. Сдвиг окна влево на три элемента соответствует циклическому сдвигу внутри строк (элементов данных, поступающих на группы линий Ш-1НЫ данных (0,1,2,3); (4,5,6,7);(8,9,10,11); (12,13,14,15)) на ОДИН элемент вправо,Следовательно, строки О и 1 матрицы формируют по коду управления, соответствующему сдвигу вправо на 1 разряд (табл, 1). При этом рассматриваются только те разряды кода управления, которые связаны с нулевым и первым ярусами сети.

Сдвигу окна на три позиции вверх соответствует сдвиг на одну позицию вниз. Так как одной позиции в данном случае соответствует целая строка, то это эквивалентно циклическому сдвигу вправо на 4 элемента. Следовательно, строки 2 и 3 матрицы М,, д сЗв ются по коду управления, соответствующему сдвигу вправо на 4 разряда (табл, 1). И в этом случае рассматриваются те разряды кода управления, которые связаны с вторым-и третьим ярусами сети,;

Таким образом, в соответствии с ; кодом «/1о(„ II и of,, «, 11 при обп/2 строк (О, 1,...,п/2-1). При смещении окна по оси I линейных сдвиг происходит на величину, кратную t (в соответствии с количеством элементов в строке). Сдвиги, кратные г выполняются на сети старшими п/2 ярусами, и в матрице М в соответствуют строки п/2, П/2+1,..,,п-1,

Q Отсюда следует, что матрица М .са для управления сетью при выборке окна формируется для первых п/2 строк по величине смещения окна относительно oj opHoro участка по J, а для по5 следних п/2 строк - по величине смещения по I, Например, квадратный фрагмент, выделенный на фиг. 4, имеет адрес, соответствую1ций положению левого верхнего его элемента (табл.6), Таблица-6

0

М

5

0

5

0

5

I

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

.1 1 1 1 1 1 1 Г

lORHql 10101010 V.A.C38 11111111

. 1 1 10000 Величина диадного сдвига определяется положением опорного участка в .поле по координате J, т.е. разрядами о(„.,, .,, ,c/f,/2 кода адреса. В таблице размещения реализован одномерный, ди- ;адный сдвиг для групп из п элементов, поэтому для компенсации диадного с. сдвига используются старшие п/2 ярусов сети. Старщий (п-|)-й ярус управляется (п-1)-м разрядом адреса (o(h.i) ()--й ярус - (п-2)м разрядом (о((,-г) т.д. Это справедливо для всех участков. Однако произвольно адресуемое окно может располагаться так, что попадает сразу на два участка по оси J, В таком случае для разных частей окна, а значит, и для разных частей сети должны реализовываться различные диадные сдвиги. Лля модулей памяти, попадающих на опорный участок, величина диадного сдвига DS 1 определяется разрядами

DS 1 tf. d ,,, «0/4 , а для следующего участка кодом DS2 (, ..., )//

/ п-1 f( n-l

, (

ЪП

191499355

Нетрудно заметить, что существует п вариантов сочетаний DS1 и D92 при управлении частями старших п/2 ярусов сети. Они определяются величиной смещения окна относительно опорного участка по J, т.е. разрядами к /t-i ,, о кода адреса. Для N 16 варианты сочетаний сдвигов для групп элементов 2-го и 3-го ярусов сети представлены в табл. 7, Таблица

10

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

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

Линии шины

данных О 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 67 8 9 10

,I

Таблица9

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

Линии ЛИНЫ

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

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

0

5

20

Теперь можно сформировать матрицу (окнл; V. сЗв рассмотренного примера

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

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

0

М

(ОКН«/

О О О О

О О О О

О О О

О

О О

1

1

о о о о

о о о о

Окончательно управление перестановками в рассматриваемом примере имеет вид:

1 1 1

01 О

1I 1 000

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

Таблица 8

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

211499355

выбираемого слова заносится в два этапа: .сначала заносится одна полови-.

на адреса (по сигналу RAS), а затем вторая половина (по сигналу CAS). В устройство вводятся по два сигнала

занесения первой половины адреса

(RAS1 и RAS2) и по два - второй (CAS и CAS2), Эти сигналы смещены во времени один относительно другого. Для каждого модуля памяти на один цикл обращения коммутируются два сигнала из этой четверки (по одному из каждо пары) в зависимости от управляющих сигналов YR и YC, вырабатываемых в блоке деления на группы. Непосредственно коммутация сигналов RAS1 или RAS2 и CAS 1 или CAS2 осуществляется соответственно первым и вторым блоками мультиплексоров адреса. Если по сигналу RAS1 занести разряды адреса, относящиеся к координате J, в часть модулей памяти, затем прибавить к этой части разрядов +1 и занести полученный адрес в остав1чиеся модули памяти по сигналу RAS2, то после проведения аналогичной операции с занесением разрядов адреса, относящихся к координате I, по сигналам CAS 1 и CAS2, Tpe6yef ie адреса будут полностью занесены в модули памяти,

Временная диаграмма операции занесения адреса представлена на фиг, 12 Сигналы YR и YC не изменяют своего значения в течение времени занесения ;адреса. Время t, - время удержания адреса (разряды е( ) определяется из конкретных характеристик микросхемы памяти. Время ti - время, необхо-

димое для выполнения операции прибав- Q проверить по адресам вьщеленной на ления.+ 1 и получения адреса / о где в/о т +1, Минимальное время между сигналами RAS1 и RAS2 равно сумме времен t, + t. Аналогичфиг. 4 строки, В разрядах а,ад(-

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

ная картина имеет место и для сигна- д лов CAS1 и CAS2; tj - время удержания адреса; t,. - время .его модификации. Таким образом, за счет удлинения цикла обращения к памяти на величину

Ч Ч- Ч t4

обеспечивается воз-.

50

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

грамме. Модификация адреса (прибавление +1 к определенной части разрядов и их коммутация на адресные входы модулей памяти) осуществляется в блоке 5 модификации адреса. Адресные входы модулей памяти подключены к адресной шине специальным образом,

- - разрядный адрес (где 2 - объем

модулей памяти) поступает к модулям памяти в виде трех шин Q, X, У. Разл г п , ., рядность шины Q - - - (.где N

-2 - число используемых модулей

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

или

© S

п(1- п(г-1

, ... ,Y о Хц/1-, ®

h/2-l

ыг-г ® Xh,j.j, .. . ,Хр® Sj ,

где S - код типа обращения.

5 При этом п/2 младших разрядов адреса модулей памяти подключаются к шинам X и У по следующему правилу: если (п-1)-й разряд в номере модуля памяти равен О, то вход а п/2-7 модуля па0 мяти подключается к (п/2-1)-му разряду шины X, т,е. к X f,/., , а если этот разряд в номере модуля равен 1, то к (п/2-1)-му разряду шины У, т.е. .-1 и т.д. Такое диадное соединение адресных входов позволяет при выборке строк подавать на разные группы из п модулей памяти адреса, перебирающие все значения в п/2 младших разрядах. Это требование можно

5

проверить по адресам вьщеленной на

фиг. 4 строки, В разрядах а,ад(- 2)

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

Номер модулей памяти 8, 9, 10, 1101

4, 5, 6, 710

О, 1, 2, 311

12, 13, 14, 1500

Таким образом, если S .11..,1, то все адреса в группах - различные. При S 00..,О получим, что У Х+00,,.0 X и во всех модулях одни и те же адреса. Рассмотрим процедуру занесения адреса в модули памяти на примерах.

Выборка квадрата с адресом 00000011110000001111, выделенного на фиг. 4. Код S в этом

23149935524

режиме равен 00, следовательно, зна- группы и занесения адреса по оси J

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

в два такта, В зтом режиме код S 11, BO О, В| 1 и 1 прибавля- ется к разряду (). Так как при выборке строк разряды «(„-,, „. , ,,,, / h/i принимшот вполне определенные значения в зависимости от значения разрядов /,, ffio , то они и подаются rfgrfj 7 « 5- 4 эе 2 00000011, Так на адресные шины. Поэтому сначала S 00, то этот адрес попадет без « э « t fi ю 00000011,

изменения на все модули памяти, т,е, ; а а а а взаja,aо 00000011, Схема деления на группы выделяет модули памяти 3, 15, 11, 7, дпя кото- 5 рых этот адрес заносится по сигналу RAS1, После занесения адреса через время ty (фиг, 12) появляется сигнал + к разряду e(j к

dq -у 0 2-00000100,20

который по сигналу RAS2 заносится в остальные модули памяти. После этого происходит изменение сигнала В О на В о 1 и

п , is 4 i3 tt 000000 Схема деления модулей на группы

вьщеляет модули 3, 12, 13, 14, для которых этот код заносится по сигналу CAS1, Затем через время t приходит сигнал + к of(5L, который иЗменя- 30

который попадает на адресные входы модулей памяти:

Код адреса

00000011 00000010 00000001 00000000

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

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

памяти

30000001100000011

00000100000000 И 0000001100000ЮО

Код адреса

00000 111 00000110 00000101 00000100

35

40

45

15, 11, 7

12, 13, 14

О, 1, 2, 4,

5, 6, 8, 9,10 0000010000000100, Соответствие этих адресов требуемым для выборки квадрата проверяется по таблице на фиг, 4,

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

0000001 01 1 ооооооо;Го 1 ,

Если при выборке квадрата может быть четыре различных адреса в модулях то при выборке произвольно расположенной строки адрес по оси I один и тот же для всех модулей, а по оси J мопгт быть -два адреса в разрядах eij «(, и всегда различные адреса в разрядах «(fiyt Изменение адреса, в разрядах о(в( вьтолняется за счет диадного способа соединения адресных входов модулей памяти, а в разрядах ef| -f «(4 эа счет деления на

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

памяти

О, 1, 2, 3

4, 5, 6, 7

8, 9, 10, 11

12, 13, 14, 15

Группа деления на модули выделяет следзпощие модули; 9, 10, 11, 4, 5, 6, 7, О, 1, 2j 3, для которых занесение происходит по сигналу RAS1, После это го произойдет прибавление +1 к разря- 25 ду (4 :

,,/,е/, oCg dg 4 fi 000001 . который попадает на модули памяти в следующем виде:

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

памяти

О, 1, 2, 3

4, 5, 6, 7

8,9, 10, 11 12, 13, 14, 15

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

о „- -о( 00000010,

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

Номер 14одулейКод адреса

памяти

9,10, 11 4, 5, 6, 7 О, 1, 2, 3

12, 13, 14, 15,

80000001000000101

Эти адреса соответствуют выделен- -Q ной строке.

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

5

0

0

который попадает на адресные входы модулей памяти:

Код адреса

00000011 00000010 00000001 00000000

Код адреса

00000 111 00000110 00000101 00000100

5

0

5

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

памяти

О, 1, 2, 3

4, 5, 6, 7

8, 9, 10, 11

12, 13, 14, 15

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

,,/,е/, oCg dg 4 fi 000001 . который попадает на модули памяти в следующем виде:

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

памяти

О, 1, 2, 3

4, 5, 6, 7

8,9, 10, 11 12, 13, 14, 15

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

о „- -о( 00000010,

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

Номер 14одулейКод адреса

памяти

9,10, 11 4, 5, 6, 7 О, 1, 2, 3

12, 13, 14, 15,

80000001000000101

Эти адреса соответствуют выделен- Q ной строке.

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

ппексоров и N линий YC управления - блоком 8 мультиплексоров (фиг, 14), Те линий, на которых присутствует сигнал логической единицы, позволяют .принять в модули памяти по сигналам RAS1 и CAS 1 модифицированный адрес, а те, где сигнал логического нуля, - по сигналам RAS2 и CAS2 модифицироваи ный адрес,т.е.адрес,в котором знача-

25

В данном примере выборки квадра- .та код смещения по оси J II и, следовательно, единицы появляются на выходах 3, 7, 11, . Полученный код затем проходит через узел 10 мультиплексоров, представляющий собой старшую половину n-CUBE сети на i входов. В качестве управляющего кода (управление ярусное для компенса1:1ии диадного сдвига в размещении информа- ции) используется код смещения квадрата -по оси I (разряды ) Тзк как в каждых из п входов сети кодовые

комбинации одинаковые, а старшие ярусы сети переставляют сразу группы из fl элементов, то входной и выходной коды сети в этом режиме совпадают. Поэтому по оси J будут следующие групп ы: 3, 7, 11, 15 и 12, О, 4, 8, . 13, 1,5, 9, 14, 2, 6, 10, В модули

35

40

В данном примере о(, lo ходной код следующий:

000 00 О О О О О 0--1 1 1 1, Этот код поступает на вход узла 13 мультиплексоров, который управляется следующим образом. Сеть разбивается

5

26

ния координат больше на +1.При работе памяти с квадратными блоками данных преобразователь 9 кодов преобразует п/2- разря дный входной код (код смещения квадрата относительно опорного участка, разряды ) в код, состоящий из п одинаковьгх групп, в которых входвходной код преобразуется в инверсный нормализованньй единичный код (таблШ), Таблица 10 .

памяти с .номерами 3, 7, П, 15 заносится адрес (разряды, соответствующие оси J) по RА 51, а в оставшиеся - мо- дифищ-грованный (увеличенный на +1) по RAS2. Для деления на группы по оси I используется преобразователь 11 кодов, узел 13 мультиплексоров и узел 12 мультиплексоров. Преобразователь 1 1 кодов преобразует входной п-разрядный код в инверсный нормализованный, В качестве входного кода берется код смещения квадрата по оси I (разряды ) который используется в качестве старших п/2 разрядов входного кода, а младшие п/2 разрядов принимаются нулевыми. Таким образом, получается код, в котором количество нулей равно числу of, о , умноженному на число п (табл. 11).

Таблица 11

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

дельно. Пример такого деления для N 16 показан, на фиг. 9 и 14. J Узел 12 ь ультиплексоров производит коммутацию управляющих сигналов к al j (/з а( +1)// h в соответствии с величиной смещения квадрата по оси J(), как показано в табл. 12.

В рассматриваемом примере смещение квадрата по оси J о/ в(о , 11, (11 + 1 )//4 00. Матрица управляющих сигналов на полусеть следующая:

Го 01

ОО

0О

1I ОО ОО

0О

11

В соответствии с этой матрицей входной код преобразуется:

Номер Входной Выходной код

49935528

входной п-разрядный код смещения начального элемента строки относительно границ поля (разряды cfjof o, of,,) в инверсный нормализованный единичный код. В качестве примера возьмем вы-; деленную на фиг.4 строку с адресом 00000010110000000101. Код смещения «f 2 «С, о 0101. ИнверсJO ный нормализованный единичный код равен О О О О 1 1 1 1 11 1 1 1 11 1. Управляющий код il. Поэтому после прохождения сети этот код преобразуется

1111111101110000. В модули памяти с номерами 9, 10, 11, 4, 5, 6, 7, О, 1, 2, 3 разряды адреса, соответствующие координате J, заносятся по сигналу RAS1, а в оставщиеся - после модификации по сигналу RAS2. В режиме выборки строк модификация адреса в разрядах, соответствующих координате I, не требуется, так как эта часть адреса для

25 всех модулей одинакова. Поэтому занесение второй половины адреса в этом режиме можно производить по одному сигналу CAS 1.

15

20

30

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

код

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

О О О

о о о о о о о о о 1 1 1 1

о о о 1

о о о о о о о о 1 1 1 о

в результате адрес в модули 3, 12, 13, 14 заносится по сигналу CAS1, а в остальные - после модификации по CAS 2.

Рассмотрим работу схемы деления при выборке строк. При выборке строк преобразователь 9 кодов преобразует

30

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

0

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

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

0

29

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

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

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

15

9935530

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

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

25

30

35

5

0

5

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

11

фиг. г

1

16

13

75

17

ЦЗиг.З

1499355 V гГ, ITr TftVy Щ115 ЩЦд TlyVitV it fS

ярус о

9рус1

ярусг.

ЯрусЗ

1/ vfoW vft yiiftitifs

вьиюды

у

,г ТП- 4 J-ft/f Vi

с

рдсО

ToWOTWa a

Ярус1

oWoWoWob ,

вьиоды фиг. 8

йЬггг,

./tfe- «,-sxr в-у,г/-г гг,-Цр-/у,-«

Г г7г-/

.5

входы

Wo

вьиоды фиг. 8

Входы

tppToWO OWO

WOTSWBWo

, I .ц , , , I ,, „, .

ШдаоЬЬЬ

onsussjesroniim

БЬЬ

FT lo WWCKW ol

тщ э тккз

io W№4K:f

111

j

y «tittle

IB

rZm

m

- -«

ffi

ti

3

Bbfxodbf

фиг. 7

I

У5

531

w

r-n5.

Я

Ji i jdn

ф1/г.8

оЪЬ а о аЬ а

о 1 3

о ГТ fТ / SWnr 13 /« „

ЯрусЗ

Ярус г

ярус

ярусз

I rVV

о 1 г 3 ti 5 Б 1 8 9 Ю 11 12 13 7tt 15 Линии шинь/ dff Hb/je

Фиг. ю

влоды

Вшодлг фиг.З

шина 0 f } Vj и У, К, V, V, и V,o VnVnVaUftУ„ Лммы/. JJ J i

VHitr f f f г г г rr Л V tr,bttbi,v VgiftbJ-,v$aiVyt i t i tftf ГИ/г.и

Адрес

фиг.1г

1

фиг. 3

/ /

0%/-./-