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

.08.89. Вялнградскийитут им. В 29 сэлектр оте И. Ульяно е Е.А. Метли 4051551,977.итании В 2982.УСТРОЙСТВО1 М ДОСТУПО 92785,ПАРАЛК СТРОосится к вычислиГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫПРИ ГННТ СССР(54) ЗАПОМИНАЮЩЕЕЛЕЛЬКИ ПРОИЗ ВОЛЬВКАМ И ОКНАМ ДАННЫХ(57) Изобретение о ельной технике и может быть испол зовано в вычислительных системах с параллельной обработкой информации, а также в качестве регенерационной памяти в полутоновых и графических растровых дисплеях. Цель изобретения - расширение функциональных возможностей устройства за счет дополнительного формата обращения в виде строк, Поставленная цель достигается тем, что устройство содержит блок 1 памяти, блок 2 входных данных, блок 3 выходных данных, блок 4 управления, блок 5 модификации адреса, блок 6 деления на группы, блоки 7 и 8 мультиплексоров. 3 з.п. ф-лы, 14 ил.12 табл. а319 1499355 20 уппы коммут ацио нныэлементовяруса 00 01 1 О 081 081 Р 81 081 РЯ П 81 081 082 Р 81 081 082 РЯ 2 РЯ 1 П 82 082 082 0 0 0 0 0 0 0 0а 0 О 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 Окоммутационных приведен на Фиг. старших яруса ентов сети и дея .компенсации попадании окна перест римере м ев а0111011 01111000 е Такое управлени т упорядочение .эл ных (фиг, 11), при при записи) и 9 ( сетью обеспечиваментов блока данеденное в табл.8ри чтении). ными группаминтов выполняет 1 б и узлом 17 абли Линии шиныданных 0 2 114 9 Т абл Модуль памяти 3 4 5 1 12 13 14 15 4 4 1 2 3 4нии линынных 11 12 13 14 15 7 0 9 1Рассмо положенногоможно раздееса которых "+1", и на рых по оси 1В некоторых сокращения олный адрес адресной ой части у 5 модифика ия на груп блоки муль ды модулей писания ра дулям памя трим работ а. К адрес сится блок лок 6 деле и второй 8 дресные вх едует из мации по м стиройустройствства отноадреса, бпервый 7соров и ати, Как слния инйор ф 5) иплек- памя- мещеи, при Нетрудно заметить, что существует и вариантов сочетаний П 81 и 082 при управлении частями старших п/2 ярусов сети, Они определяются величиной смещения окна относительно5 опорного участка по Л, т.е. разрядами (я/,., с кода адреса, Для Н16 варианты сочетаний сдвигов для групп элементов 2-го и 3-го ярусов сети представлены в табл. 7.Таблица 7 Пример разбиенияэлементов на группы9, где показаны двакоммутационных элемление их на группы длдиадного сдвига прина два участка.Управление разликоммутационных элемся преобразователеммультиплексоров,Модуль памяти 3 12 14 14 15 Теперь можно сформировать матрицу (фкню)М в а для рассмотренного примера выборки окна, положение которого задано на фиг, 4, Величина диадного сдвига для модулей памяти 3, 15, 11, 7 определяется размерами св Ы кода адреса, т,е. РЯ = 11, а дпя остальных элементов окна П 82 = (11+01)//4О. В соответствии с кодом Ы, а( и типом обращения (окно) преобразователь 16 кодов выдает управляющий код 1000 на вход узла 17 мультиплексоров, с выхода которого снимается код управления 2-м и 3-м ярусами сети, соответствующий матрице Окончательно управлновками в рассматриваеимеет вид: 0 11 12 13 14 15 6 7 8 9 1 О выборке произвольно расквадрата модули памятилить на две группы, адрпо оси Л отличаются надве группы, адреса котоотличаются тоже на "+"микросхемах памяти длячисла адресных входов пвыбираемого слова заносится в два"этапа: сначала заносится одна полови-.на адреса (по сигналу КАЯ), а затемвторая половина .(по сигналу САЯ). Вустройство вводятся по два сигналазанесения первой половины адреса(ВА 81 и ВА 82) и по два - второй (САЯ 1и СА 82). Эти сигналы смещены во времени один относительно другого, Длякаждого модуля памяти на один циклобращения коммутируются два сигналаиз этой четверки (по одному из каждойпары) в зависимости от управляющихсигналов УК и УС, вырабатываемых в 15блоке деления на группы, Непосредственно коммутация сигналов ВА 81 илиВАЯ 2 и САЯ 1 или СА 82 осуществляетсясоответственно первым и вторым блокамн.мультиплексоров адреса, Если по 20сигналу КА 81 занести разряды адреса,относящиеся к координате 3, в частьмодулей памяти, затем прибавить кэтой части разрядов +1 и занести по-.лученный адрес в оставшиеся модули 25памяти по сигналу ВА 82, то после проведения аналогичной операции с занесением разрядов адреса, относящихсяк координате 1, по сигналам САЯ 1 иСА 82, требуемые адреса будут полностью занесены в модули памяти,Временная диаграмма операции занесения адреса представлена на фиг. 12.Сигналы УК и УС не изменяют своегозначения .в течение времени занесения;адреса, Время 1, - время удержанияадреса (разряды е(., в : Ы ) определяетсяиэконкретных характеристик микросхе 1 ы памяти. Время- время, необходимое для выполнения операции прибавления .+1 н получения адресагде ю(1- ю(, = Ы 7 + о( +1. Минимальноевремя между сигналами КА 81 и КА 82равно сумме времен С 1 + й, Аналогичная картина имеет место и для сигналов СА 81 и СА 82; й. - время удержанияадреса; й- время его модификации.Таким образом, эа счет удлинения цикла обращения к памяти на величину+ С, ++ С обеспечивается воз 1можность отказаться от необходимостииметь у каждого модуля памяти свойсумматор, Для режима работы, в котором выбираемые данные не имеют смещения относительно участка, можно дпяускорения йроцесса выборки отказатьсяот четырехтактной системы занесенияадреса, а испольэовать обычную двухтактную по укороченной временной.диаграмме, Модификация адреса (прибавление +1 к определенной части разрядов и их коммутация на адресные вхо-ды модулей памяти) осуществляется вблоке 5 модификации адреса, Адресныевходы модулей памяти подключены к адресной шине специальным образом,г г2-- разрядный адрес (где 2 - объеммодулей памяти) поступает к модулямпамяти в виде трех шин Я, Х, У, Разг ирядность шины Ч = --- (где М =2 2ь2 - число используемых модулейпамяти). К этой шине параллельноподключаются все старшие разряды адресных входов модулей памяти, Разрядность шин Х и У равна и/2. Шины Х,У и Я связаны следующим сйособом:У = Х 9 Яч фуь(1-1 е п(ф- эео - Хь(1-19 8(- Хь(О Хь(у 1 е еФрб 0где Я - код типа обращения,При этом и/2 младших разрядов адресамодулей памяти подключаются к шинамХи У по следующему правилу: если(и)-й разряд в номере модуля памятиравен О, то вход а (г., модуля памяти подключается к (и/2-1)-му разряду шины Х, т,е. к Х (,, а еслиэтот разряд в номере модуля равен 1,то к (и/2-1)-му разряду шины У, т.е.к У (и т,д, Такое диадное соединение адресных входов позволяет привыборке строк подавать на разныегруппы из и модулей памяти адреса,перебирающие все значения в и/2 ипадших разрядах. Это требование можнопроверить по адресам выделенной наифиг, 4 строки, В разрядах а,а (-2)на адресных входах модулей памятиследующие адреса:Номер модулей памяти а,а о8, 9, 10, 11 0 11 012, 13, 14, 15 0 0Таким образом, если Я = 111, товсе адреса в группах - различные. При8 = 000 получим, что У = К+000== Х и во всех модулях одни и те жеадреса, Рассмотрим процедуру занесения адреса в модули памяти на приме"рах,Выборка квадрата с адресом11, вделенного на фиг, 4. Код Я в этом23 1499355 25 40 режиме равен 00, следовательно, зна"чения адреса в разрядах а а на всехмодулях одинаковы, Перед началом выборки состояние управляющих сигналовмультиплексоров В = 0 и В, = О,что означает, что открыт канал длянижних (на фиг. 13) шин мультиплексоров 23 и 24, В этом состояниифзф 1 фч абеке( юо( 00000011, Так как ОЯ00, то этот адрес попадет безизменения на все модули памяти, т.е.а.,аааа за а а00000011.Схема деленйя на группы выделяетмодули памяти 3, 15, 1 1, 7, для которых этот адрес заносится по сигналуВАЯ 1. После занесения адреса черезвремя(фиг. 12) появляется сигнал +1 к разрядуиаэ о = 00000100, 20который по сигналу ВАЯ 2 заносится востальные модули памяти. После этогопроисходит изменение сигнала В = 0на во= 1 иада 1 с(, в( н, а(, а(, а,- 00000011,Схема деления модулей на группывыделяет модули 3, 12, 13, 4, длякоторых этот код заносится по сигналу САЯ 1. Затем через время э прихо"дит сигнал +1 к ( который изменяет состояние выхода на ю(,з в . ф( == 00000100 и этот код эаноситса посигналу САЯ 2 в оставшиеся модули памяти, Таким образом, в модули памятизаносятся следующие коды адреса:Номер модулей Код адресапамятиЭ 00000011000000111511, 7 000001000000001112, 13, 14 0000001100000100О, 1, 2, 4,5, б, 8, 9, 10 0000010000000100.Соответствие этих адресов требуеиамдля выборки квадрата проверяется потаблице на фиг. 4.45Выборка строки с адресом00000010110000000.101.Если при выборке квадрата можетбыть четыре различных адреса в модулях, то при выборке произвольнорасположенной строки адрес по оси 1один и тот же для всех модулей, а пооси Л могут быть два адреса в разрядах Ыэ М и всегда различные адреса в разрядах фэЫз. Изменение адресав разрядах фвыполняется за счетдиадного способа соединения адресных входов модулей памяти, а в разрядах Ые - за счет деления на 24группы и занесения адреса по оси Лв два такта. В этом режиме код Я11, ВО, В,1 и + 1 прибавляется к разряду д( ). Так как привыборке строк разряды а(а принимают вполне определенныезначения в зависимости от значенияразрядов о аю, то они и подаютсяна адресные шины. Поэтому сначалаЫ,г,г (,+ С= ОООООО 1,который попадает на адресные входымодулей памяти:",Номер модулей Код адресапамяти.000000108, 9, 1 О, 11 0000000112, 13, 14, 15 00000000Группа деления на модули выделяетследующие модули; 9, 10, 11, 4, 5, 6,7, О, 1, 2; 3, для которых занесениепроисходит по сигналу ВАЯ 1, После это"го произойдет прибавление +1 к разряду фе:э И а с а( с( и о(д = 00000 1 1 1который попадает на модули памяти вследующем виде;Номер модулей Код адресапамятиО, 1, 3 0000011000001108, 9, 10, 11 000000112, 13, 14, 15 00000100Этот код заносится в модули памятис номерами 12, 13, 14, 15, 8, Послеэтого В становится равным 1, а Я щЦО, В результате на все модули памяти подается код+= 000000 О.Окончательно можно записать:Номер Модулей Код адресапамяти9, 10, 11 00000010000000014, 5, 6, 7 0000001000000010О, 1, 2, 3 000000100000001112, 3, 14, 15,8 0000001000000101Эти адреса соответствуют выделенной строке.Рассмотрим деление на группы содинаковым адресом, Блок 6 деленияна группы предназначен для делениямодулей памяти на две группы, адреса,которых по оси Л отличаются на +,и на две группы, адреса которых пооси 1 отличаются на +1, На выходесхемы деления на группы имеем Б линий УК управления блоком 7 мульти25 1499355 26 плексоров и 11 линий УС управления - блоком 8 мультиплексоров (фиг. 14). Те линий, на которых присутствует сигнал логической единицы, позволяют ,принять в модули памяти по сигналам ВАЯ и САЯ модифицированный адрес, а те, где сигнал логического нуля, по сигналам КАБ 2 и СА 82 модифицированный адрес,т,е,адрес,в котором значе- А Входнойкод Выходной код0 1 2 3 4 5 6 7 8 9 ,10 1 12 13 14 15 00 01 О 11 1 1 1 1 1 11 1 11 1 0 1 1 1 0 11 01 0 0 0 1 1 0 0 1 1 0 О 1.,0 0 0 0 1 0 0 0 1 0 О О 1 0 1 1 11 1 0 1 1 0 0 1 В данном примере выборки квадра/,та код смещения по оси Л ( Ы = 11и, следовательно, единицы появляются, на выходах 3, 7, 11, 45, Полученныйкод затем проходит через узел 10мультиплексоров, представляющий собойстаршую половину и-САВВ сети на ивходов, В качестве управляющего кода(управление ярусное для компенсациидиадного сдвига в размещении информации) используется код смещения квадрата по оси 1 (разряды е(1,е,)Таккак в каждых иэ и входов сети кодовыекомбинации одинаковые, а старшие ярусы сети переставляют сразу группы из 35элементов, то входной и выходнойкоды сети в этом режиме совпадают,Поэтому по оси Л будут следующиегруппы: 3, 7, 1 1, 1 5 и 12, О, 4, 8,13, 1, 5, 9, 14, 2, 6, 10, В модули 40 Таблица 11 Выходной код Входнойкод 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 11 1 1 1 1 1 0 0 0 0 1 1 11 1 1 0 0 0 0 0 0 .0 0 1 1 1 О 0 0 0 0 0 0 0 0 0 0 1 1 11 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 00 11 10 11 на п групп, как и при упорядоченииданных, где каждая иэ групп проиэво 55дит перестановки среди входов сети,номера которых соответствуют номераммодулей памяти в столбцах квадрата, икаждая. такая группа управляется отВ данном примере Ы, 1 = 11 и выходной код следующий:00000000000"1 111, Этот код поступает на вход узла 13 мультиплексоров, который управляется следующим образом, Сеть разбивается ния координат больше на + 1, При работе памяти с квадратными блоками данных преобразователь 9 кодов преобразует и/2- разрядный входной код (код смещения квадрата относительна опорного участка, разряды о,а(р) в код, состоящий из и одинаковых групп, в которых Вход- входной код преобразуется в инверсный нормализованный единичный код (табл 10),Таблица 10 памяти с .номерами 3, 7, 11, 15 заносится адрес (разряды, соответствующиеоси 3) по РЛ 51, а в оставшиеся - модифицированный (увеличенный на +1)по ВАБ 2, Для деления на группы пооси 1 используется преобразователь 11кодов, узел 13 мультиплексоров иузел 12 мультиплексоров. Преобразователь 11 кодов преобразует входнойи-разрядный код в инверсный нормализованный, В качестве входного кодаберется код смещения квадрата по оси1 (разряды Ы Ы,), который используется в качестве старших п /2 разрядоввходного кода, а младшие п/2 разрядовпринимаются нулевыми, Таким образом,получается код, в котором количествонулей равно числу Ы Ы, умноженному на число п (табл, 11), 271499 35528дельно. Пример такого деления дляВ = 16. показан, на фиг. 9 и 14.Узел 12 мультиплексоров производиткоммутацию управляющих сигналов МэАи о(э а = (сэ а +1)// ь в соответствии/ э 2 5с величиной смещения квадрата по осиЛ(с Ы), как показано в табл. 12,Таблица 12 10Управляющие сигналы Смещение 0 1 2 3 4 5 6 7 э э фэ эз фэ ээ э э 0 0 01 0 1 1 ф( т а фх ф0(4С(у 0( 15 0 0 0 0 0 0 1 1 0 0 О 0 .0 0 1 1 25 В соответствии с этой матрицей входной код преобразуется:Номер Входной Выходнойкод код0 О 01 0 О2 0 03 0 14 0 05 0 06 О 07 . 0 08 0 09 0 010 0 011 0 О12 1 113 1 114, 1 115 1 0В результате адрес в модули 3, 12,13, 14 заносится по сигналу СА 81, ав остальные - после модификации поСАЯ 2,Рассмотрим работу схемы деленияпри выборке строк. При выборке строкпреобразователь 9 кодов преобразует 35 40 45 50 55 В рассматриваемом примере смеще ние квадрата по оси Л , 4 = 11, ЫэЫ=11 а( е = (11+1)//4 = 00, Матрица управляющих сигналов на полусеть следующая: входной и-разрядный код смещения начального элемента строки относительно границ поля (разряды е(э Ыо, е,) в инверсный нормализованный единичный код. В качестве примера возьмем выделенную на фиг,4 строку с адресом 00000010110000000 101. Код смещения сэ сЫ, 4,= О 1 О 1, Инверсный нормализованный единичный код ра-. вен 0 0 0 0 1 1 1 1 1 1 1 1 1 11, Управляющий код е,Ы= 1, Поэтому после прохождения сети этот код преобразуется111111101110000, В модули памяти с номерами 9, 10, 11, 4, 5, 6, 7,0, 1, 2, Эразряды адреса, соответствующие координате Л, заносятся по сигналу ВАМ, а в оставшиеся - после модификации по сигналу ВАБ 2. В режиме выборки строк модификация адреса в разрядах, соответствующих координате 1, не требуется, так как эта часть адреса для всех модулей одинакова. Поэтому занесение второй половины адреса в этом режиме можно производить по одному сигналу САЯФормула изобретения1. Запоминающее устройство с параллельным произвольным доступом к строкам и окнам данных, содержащее блок входных данных, блок памяти и блок выходных данных, причем информационные входы устройства подключены соответственно к информационным входам блока входных данных, выходы которого подключены соответственно к информационным входам блока памяти, выходы которого подключены соответственно к информационным входам блока выходных данных, выходы которого подключены соответственно к выходам устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет дополнительного формата обращения в виде строк, в него введены блок модификации адреса, блок деления на группы, блок управления, первый и второй блоки мультиплексоров, при этом с первого по девятый выходы блока модификации адреса подключены соответственно к входам с первого по пятый блока деления на группы, к адресным входам с первого по третий блока памяти и к входу режима блока управления, выхо 4.ды первой и второй групп которого подключены соответственно к управляющим входам блока входных данных и блока выходных данних, первый и второй выходы блока деления на группы5 подключены соответственно к информационным входам первого и второго блоков мультиплексоров, выходы которых подключены соответственно к первому и второму входам записи-чтения блока памяти, адресные входы устройства подключены соответственно к входам блока модификации адреса, входы с первого по четвертый записи-чтения 15 устройства подключены соответственно к первому управляющему входу первого блока мультиплексоров, к второму управляющему входу первого блока мультиплексоров, к первому управляющему 20 входу второго блока мультиплексоров и к второму управляющему входу второго блока мультиплексоров.2. Устройство по г 1, о т л и - ч ающе е с я тем, что блок деле ния на группы содержит первый и второй преобразователи кодов, первый, второй и третий узлы мультиплексоров, причем входы с первого по пятый блока деления на группы подключены 30 соответственно к входам первого и второго преобразователей кодов, к управляющему входу первого узла мультиплексоров, к управляющему и информационному входам второго узла мультиплексоров, выход которого подключен к управляющему входу третьего узла мультиплексоров, выходы первого и вторсга преобразователей, кодов подключены соответственно к информацион ным входам. первого и третьего узлов мультиплексоров, выходы которых подключены соответственно к первому и второму выходам блока деления на группы. 453. Устройство по п, , о т л и - ч а ю щ е е с я тем, что блок управления содержит первый и второй преобразователи кодов, группу сумматоров по модулю два и узел мультиплексоров,50 причем вход режима блока управления подключен к входам первого и второго преобразователей кодов и к управляющему входу узла мультиплексоров, выходы первой группы которого подключе 55 ны соответственна к первым информационным входам сумматоров по модулю два группы, выходы первого преобразователя кодов подключены саатветственна к вторым инфармапианныи входам сумматоров па модулю два гру .пы, выходы второго преобразователя кодовподключены к инфармациснным входам узла мультиплексоров, выходы сумматоров па модулю два группы и выходы второй группы узла мультиплексоров подключены соответственно к первойи второй группам выходов блакэ управления,4. Устройство по п, 1, а т л и ч а ю щ е е с я тем, чта блок модификации адреса содержит первый и второй мультиплексоры, первллй и второйсумматоры по модулю два, первый ивторой регистры, с первого па третиисумматоры, пуичем вход блока модификации адреса подключен к инфармационным входам первого регистра, второго регистра и к первым информационным входам сумматоров с первого па третий, выходы первого сумматора, первого регистра, второго сумматора, третьего сумматора и второго регистра подключены соответственно к первым инФормационным входам первого и второго мультиплексоров, к второму ин - формационному входу первого мультиплексора, к второму и третьему информационным входам второго мультиплексора, выход которого подключен к втарому информационному входу первогомультиплексора, выходы с первого пошестой которого подключены саатветственна к выходам с первого па шестой блока модификации адреса, седьмой и восьмой выходы первого мультиплексора подключены соответственна к первым входам первого и второго сумматоров по модулю два, выходы которых подключены соответственно к седьмомуи восьмому выходам блока модификации адреса, девятый выход первого мультиплексора подключен к девятому выходублока модификации адреса, входы спервого по четвертый режима которогоподключены соответственна к управляющим входам первого и второго мультиплексоров и к вторл 1 м входам, первого и второго сумматоров на модулю два,первый, второй и третий входы приэнака модификации адреса блока модификации адреса подключены соатветственна к вторым информационным входампервого, второго и третьего сумматарав, выход переноса третьего суммата -ра подключен к третьему информационному входу второго сулмэтора,499355 8 РЮы Р 7873% Ю Яру русд Яру 3 4 Лини г 3 Ааль/ЩиУЯцко шины 0 анных2 34 5 б 78 У 703 1499355Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах спараллельной обработкой информации,а также в качестве регенерационнойпамяти в полутоновых н грайическихрастровых дисплеях.Цель изобретения - расширение функциональных воэможностей устройстваза счет дополнительного формата обращения в виде строк,На фиг, 1 изображена структурнаясхема устройства; на фиг, 2 - схемаблока деления на группы; на фиг. 3 - 15схема блока управления; на фиг, 4 -фрагмент таблицы размещения элементов запоминаемого массива по модулямблока памяти для 1 = 16; на йиг. 5 -блок мультиплексоров, коммутационные 20элементы которого соединены по правилу соединения и-С 11 ВЕ сети, нафиг. 6 - схема подключения управляющих входов блока мультиплексоровпри ярусном управлении; на фиг, 7 - бподключение управляющих входов блокамультиплексоров для получения линейного сдвига входного слова; на фиг,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Блок 4 управления содержит (фиг.3).первый преобразователь 14 кодов,группу сумматоров 15 по модулю два,второй преобразователь 16 кодов иузел 17 мультиплексоров.Блок 5 модификации адреса содержит(фиг. 13) с первого по третий сумма"торы 18-20, первый 21 и второй 22 регистры, первый 23 и второй 24 мультиплексоры,первый 25 и второй 26 сумматоры по модулю два,Фрагмент таблицы размещения элементов запоминающего массива по модулю для 1 = 16 содержит (фиг, 4)верхний левый угол таблицы размещения для Н = 16. Цийры в клетках - этономера модулей памяти, в которые попадают соответствующие элементы запоминаемого массива. Квадраты размером16 х 16 элементов, обведенные двойнойлинией, называются полями, Квадратыразмером 4 х 4, обведенные жирной линией, называются участками. Жирными линиями выделены одна строка и одинквадрат, произвольно расположенныена таблице, которые рассматриваютсяв качестве примеров.Коммутационные элементы узла мультиплексоров соединены по правилу соединения и-С 11 ВЕ сети . Имеющиеся 16входов и 16 выходов, обозначены соответственно буквами Ч и У, В нижнейчасти показан один коммутационныйэлемент с информационными входами чр,и с информационными выходами ч,ттВ зависимости от состояния управляющего сигнала С-входы коммутируютсяна выход либо прямо, либо перекрестно.Временная. диаграмма работы отображает следующие сигналы, Сигнал тК -сигнал управления мультиплексорамив блоке 7, который для каждого модуля памяти определяет, по какому .сигналу ЯАЯ или КАЯ 2 заносится в модуль памяти первая половина адреса,Сигнал тС - это сигнал управлениямультиплексорами в блоке 8, которыйопределяет, по какому сигналу САЯ 1или САЯ 2 заносится в модуль памятивторая половина адреса, Сигнал адреспоказывает, какая группа разрядоввходного адреса в данный момент находится на входах модуля памяти,Мультиплексоры 23 и 24 управляются сигналами Во и В, причем, еслиэти сигналы равны нулю, то на выходпроходят сигналы с нижних входов/4 68 писн КНТ СССР по изобретениям и открытияЖ, Раушская наб., д. 4/5 оиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,Заказ 4ВНИИПИ дарственного комите 113035, Москва орректор М. Максимншинец.Ь5 149935 мультиплексора, а если равны 1, то с верхних входов.Мультиплексоры МБ в блоках 7 и 8 пропускают на выхоц нижний входной сигнал (КАЯ 2, САЯ 2), если управляю 5 щий сигнал (УК или УС) равен нулю, и верхний, если равен единице, Узлы 10 и 13 мультиплексоров по своим информационным связям идентичны и представляют собой старшие и/2 ярусов и-С 1 ВЕ сети, Оба блока предназначены для выполнения диадной перестановки: третий - над всем словом, четвертый - над двумя группами раз рядов входного слова. Определяется какая группа коммутационных элементов управляется кодом Ыз , а какая кодом е( о( = (ф+ 1)//и, где знак а//Ъ, обозначает что число а берется по модулю Ъ, Коммутация на группы производится блоком 12 мультиплексоров (по табл, 6) в зависимости от состояния входных сигналов о,о(Устройство предназначено для хра кения двумерных массивов слов с возможностью одновременной выборки группы слов, представляющих собой произвольно расположенное на массиве окно или фрагмент строки. Для простоты будем считать, что все слова однобитовые, Переход к словам большей раз. рядности осуществляется путем параллельного соединения подобных устройств, причем блок управления может .быть один на все устройства. Блок памяти содержит 2" = И модулей памяти емкостью 2" бит, где г = 2 а; ш =1,2,3 Каждый модуль имеет г/2 адресных входов, по которым в два Координата ЛЬ-то Адрес в полеАдрес поля по 1 Адрес в поле Адрес в поле можно также разделить 45 на две части:Ыь-й ". фьп с в/т-,фАдрес участка по оси 1 Адрес элемента на участке по оси Л 50и = 4. Общий объем памяти 7 = 2 ф+ф =2 о2 бит, Такой объем позволяет хранить массив размером 1024 0241 бит. Соответственно, строка будетсостоять из 16 элементов и окно будет 55размером 4 ф 4 (фиг. 4), Структура адреса произвольного элемента следующая: Адрес квадратного окна и строки иэ Н элементов будем задавать адресом верхнего левого элемента фигуры, Примем, что все элементы участка находятся в различных микросхемах памяти, но по одному адресу, равному адресу участка. В качестве примера будем рассматривать память, состоящую из 16 микросхем памяти. Тогда г = 16; 5 6этала заносится разрядный код адреса,один информационный вход, один информационный выход, вход выбора режима чтения/записи и управляющие входызанесения адреса (БАБ, САБ),Для обеспечения возможности параллельной выборки строк или квадратныхокон необходимо разместить элеменгызапоминаемого массива так, чтобы любой выбираемый на массиве блок данныхвсегда размещался в различных модулях памяти. Если это условие не выполняется, то для какого-то блокаданнйх окажется, что два или болееэлементов запоминаемого массива находятся по разным адресам в одном и том же модуле памяти и для их выборки потребуется несколько циклов обращения, Кроме размещения элементов массива по модулям памяти, необходимо их разместить по соответствующим ячейкам внутри модулей. Общий объем памяти, состоящей из 2 модулей объемом 2" бит, будет Ч = 2 2 = 2"2 бит. Будем рассматривать двумерцную запоминающую среду, имеющую форму квадрата и размер 2. 2ит щ Для задания произвольного элемента на массиве необходимо задать П/2-разрядный код адреса координаты 1 и П/2 разрядный код адреса координаты Л.Разделим весь двумерный массив на квадраты из 11 + Б элементов, которые будем называть полями, Поле разделим на участки размером и к и элементов (фиг, 4), Будем записывать координаты произвольного элемента массива одним П-разрядным словом, называемым адресом элемента массива:1499355 фасо- нАдрес Адрес Адрес Адресполя участка элемен- поляв поле та научастке аа( ф 1 эЭ еэ АдресэлеменАдресучастка в та научастке поле где Я, 1, Л Л//ф 2 Л// = 3 5 фазенные наквадрата тка поп ф "фифлопример, выделнты строки иейки модулейресами:ф(ф фЗ фйфиг. 4 эле попадают в следующимими темчастка, то д мамияфА ф/а ф 1"о адо адресу 40 эле мяти мер модуле1 О, 11 00000010 00000010 00000010 00000010 00000010Адреса 00000011 00000011 00000100 4, 5, 6, 7 12 р 1 Зр 14 8 оки Номера модулей 3, 14.1, 72, 4, 5 9, 10 12,15,0 адрат 00000100 00000 100 ф/1 у фе 1 ф И фэ 1 адреса фигурьотно сит ел ьно ьэуются в ад для управле ф, определяют(строки илиначала участресной части В обычной), памябого слови та же лии тот же ил ельной (линей" ному биту люветствует одна анных и одинобъединенных Разрядсмещение ой, непараллти определвсегда сония в лине квадрат а) ка и испо устройств и неско Элементы запоминаемого массива размещаются по модулям памяти специальным образом. Все элементы полей размещены одинаково. Размещение в поле подчинено следующему правилу: элемент поля с координатами 1 и Л помещается в модуль памяти с номером Н: Я(1/2 ) -ЮЛ/Яр- двоичные коды чисел Б,1 иЮ;- модуль числа 1 по основанию и;смещение разрядов кода1 вправо на и/2 позицийциклически;- операция поразрядногосложения по модулю два. к как все элементы уч в модули памяти с одн ресом, равным адресу нт массива с координаф(УФ р гз фифа ф 11 фф.фздится в модуле памяти Например, для элемента поля с координатами 1 = 7, Л = 13, номер модуля памяти определится следующим образом: (1//и) "Р = (7//4) -з = (3)(0011) ч = 1100; Л = 13 = 1101 р0 = 1100 + 1101 = 0001 = 1, т.е. элемент массива с этими координатами попадает впервый модуль памяти, Такоеразмещение элементов данных по модулям памяти, заданное таблицей, в которой числа указывают номер модуля, щ сохраняющего соответствующий элементзапоминаемого массива, представленона фиг, 3. Эту таблицу размещениялегко получить в соответствии с правилом диадных (по модулю 2) переста новок для строк всех участков, причем порядок перестановок определяется как Л//р (Л О, 11023; и 4)е в модулях 00000001 00000010 ОООООО 11 (дп 00000100 00000101 в модулях 00000011 000001009 14993 в один, модулей памяти. Разряды данных при записи и чтении не меняют своего назначения и никакого упорядочения данных не требуется, Как видно из таблицы размещения на фиг,4,5 в памяти с параллельным и многоформатным доступом к данным один и тот же модуль памяти может хранить данные, которые в зависимости от варианта выборки должны поступать на различные линии шины данных. Поэтому между элементами выбираемого блока данных и линиями шины данных заранее определяется взаимно однозначное соответствие.Пусть 11 - номер линии в шине данных. В качестве основного примем порядок, при котором для двух типов образцов (квадратные окна и строки) ин О дексы номеров линий будут нумероваться слева направо и сверху вниз, начиная с нуля, Например, для Я = 161 ь 1 1 1.з14 15 2518 1 9 1 10 1 И1 И 1 114 11для квадратного окна и10 1 1 1 21 Р 41 51 с 1 т 1 щ 1 91 те 1 мд Ри 1 1 к для строки. Если элементы выбираемого блока данных попадают в модули памяти с номерами, равными номерам линий шины данных, то такой порядок модулей в выбираемом блоке называется каноническим. При перемещении рамки .окна или строки по таблице размещения в них получаются порядки, отличные от канонического. Для восстановления порядка при чтении и записи необходимо произвести упорядочение данных. 40 Для этих целей в устройстве используются блоки 2 и 3 и блок 4 управления.Коммутационные элементы, составляющие блоки мультиплексоров для упорядочения данных, соединются по пра вилу соединения и-СЗВЕ сети (фиг, 5). В нижней части показан базовый коммутационный элемент и два состояния коммутации в зависимости от значения . управляющего сигнала, Будем называть входы и выходы коммутационных элементов, по которым осуществляется перестановка, информационными. На вход сети подается входной вектор Чкоторый прохо 55 дя через коммутационные элементы, меняет в соответствии с управляющими сигналами порядок своих компонент, превращаясь в вектор И = ю ч 1 Оът,ч так, что Ч = р(Ч), где р(Ч)функция перестановки,Будем считать, что индексы компонент векторов Ч и Ы возрастают слеванаправо (фиг. 5). Ряд коммутационныхэлементов сети называется ярусом.Сеть состоит из и = 1 о 8 М ярусов которые нумеруются по порядку, Есливсе управляющие сигналы коммутационных элементов яруса одинаковы, то сетьреализует диадные перестановки входного вектора, На фиг, 6 показано, каксоединяются управляющие входы коммутационных элементов для управлениядиадными сдвигами. Всего существуетН различных диадных перестановок,причем нулевой ярус осуществляетперестановку элементов в парах, первый ярус - пар элементов вчетверках,второй ярус - четверок элементов ввосьмерках и т.д, Остальные диадныеперестановки осуществляются при совместном включении нескольких ярусовсети. На и-С 13 ВЕ сети легко осуществляются также перестановки типа линейного циклического сдвига, при этомпоярусное управление уже недостаточно,На фиг, 7 показано, как соединяются управляющие входы коммутационных элементов для управления линейным циклическим сдвигом. Нулевой ярус, как и при диадном сдвиге, управляется одним сигналом, а первый ипоследующие ярусы делятся на группы: 1-й ярус на две группы (коммутационные элементы О, 2, 4, 6 и т.д, первая группа и 1, 3, 5, 7 и т,д, вторая группа), 2 - й ярус на четыре группы (коммутационные элементы О, 4, 8 и т,д, первая группа,1, 5, 9 и т,д.вторая группа, 2, 6, 10 и т,д, третья группа и 3, 7, 11 и т,д. четвертая группа), Коммутационные элементы последнего яруса управляются по отдельности. Всего получается 11-1 групп, Таким образом, для управлениялинейным циклическим сдвигом необходимо и-разрядному коду числа сдвиговпоставить в соответствие (11-1)-разрядный управляющий код, который управляет коммутационными элементами всех групп, Для этих целей служит третий преобразователь 14 кодов в блоке управления блоками мультиплексоров данных (фиг, 3 и 8), Значенияуправляющего кода для любого сдвигаможно получить непосредственно по1499355 12 схеме и-СВЕ сети, определив состояние коммутационных элементов длякаждого сдвига. Если пронумероватьпо порядку слева направо управляющиевходы перечисленных групп коммутационных элементов и записать значения управляющих сигналов для каждого сдвига, получится табл,(для 116), значений управляющих кодов для 5реализации линейных циклических сдвигов вправо на п-СОВЕ сети на 16 входов. Таблица 1 Номер яруса перестановочной сети личинанейнего клическоговига Значения управляющих сигналов 0 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 9 1 О 1112 131 10 11 12 13 14 15 0 0 0 0 0000 0 0 0 0 1 0 0 00 0 1 0 0000 0 00 010О 00 100 1 1 0 1 1 1 1 1 11 1 11 11 1 1 1 1 1 0 1 1 0 00 0 0 0 0 0 0 0 0 О.0 0 0 быть преобразовакод; Таблица приведена для сдвига вправо. Так как сдвиг - циклический, то легко перейти от правого сдвига к левому, Сдвиг влево на д позиций соответствует сдвигу вправо на Б-д позиций. Поэтому, если сдвиг необходимо осуществить влево, код сдвига должен дополнительный Для сети, реализующей 40 циклические сдвигисохр можность выполнения диад Значения управляющих ализации диадных сдвигов сети на 16 входов приведлинейныеняется возных сдвигов одов для рена и-СГВЕны в табл 2 а б л и т аа итаииаиатаии иааиииииаиттаит перестановочной сети омер яр ели чинаиадногодвига Состояние управляющих сигналов 1 2 3 4 8 9 10 11 12 13 0 0 0 0 О0 0 0 0 0 0 0 0 0 0 0 0 0 0 О О ОО 0 0 О 0 0 0 0 О 0 10 1 0 О 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 О 1 1 0 0 1 О 1 0 0 0 О 0 0 0 1 1 О 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 11 1 0 0О 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 11 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 01 0 0 0 1 0 0 0 00 0 0 1 1 0 1 1 О 10 0 1 0 0 0 0 0 0 1 0 0 0 0 0 00 0 1 10 1 1 1 11 1 1 1 1 1 1 1 1 1 1 10 1 1 0 0 1 0 1 О0 110 0 111 1 000 1 001 1 010 1 01 100 1 101 1 110 1 11113 1499355 Продолжение табл.2 Номер яруса перестановочной сети Величина диадногосдвига 0 1 2 Состояние управляющих сигналов 0 1 2 3 4 5 6 7 8 9 10 11 12 13 4 Описание управления сетью можно представлять также матрицей и 1/2, элементы которой позиционно соответствуют положению коммутационных элементов в сети и определяют для них значения управляющих сигналов, Такая матрица дает наглядное представление о коммутации элементов сети и может быть легко получена иэ соответствую,шего управляющего кода (табл, 1 и 2) Например, описание управления сетью при реализации сдвига входной последовательности вправо на 9 элементов имеет вид:1 11 0 1М = 1 0 0М 1Для произвольной строки необходи 30 мо выполнить композицию перестановок:линейного сдвига, определяемого смещением по Л положения строки относительно начала опорного поля, и диадного сдвига, определяемого смещениемпо Т относительно начала опорногоучастка (опорным является поле илиучасток, в который попадает левыйверхний элемент фигуры (строки,.окна), задаваемый ее адресом в массиве)40 Эта композиция определяется как сумма по модулю два управляющих кодовсоответствующих линейного и диадногосдвигов, Так, если линейный сдвигописывается матрицей Мчл.сав, а диад ный Мчз,сьв, то матрица управленияМобеспечивающая упорядочение последовательности элементовстроки на сети, определяется так:. (стра кй) (стро ки ) строкн)М= М ч.сав О Мч.о.эв 50 П р и м е р, Рассмотрим выборкувыделенной на фиг, 4 строки. Ее адресопределяется кодом (табл. 3).Таблица 3 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 Необходимость разных перестанов данных вызвана те тывающая М элемен ратного фрагмента произвольно разме ыполнения разнообк при упорядочении м, что рамка, .охваов строки или квад (окна), может быть щена,Разряд 19кода адреса 432.10 3 12 11 10 9 8 18 17 16 1 Значени разряда кода ад са 0 0 0 00 1 1 000 00 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 11 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 01 0 0 10 0 1 1 1 1 1 1 1 1 1 1 1 1 .1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 О 0 О 0 0 0 1 1 1 1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 00 0 0 О О 0 0 0 0 1 1 1 1 1 1 1 11 1 1 1 1 1 1 010 011 100 1 0110 111 000 00010 011 100 101 110 1111499355 тельно начала поля и на 3 позиции(с(а= 11) по 1 относительно началаучастка. Как следует из таблицы размещения (фиг. 4), элементы строкиразмещены в следующих модулях памяти(табл. 4).,Таблица 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 11 12 13 14 15 Линии шиныданных (элемента в строке) 7 8 9 10 3 4 5 6 15 02 11 12 13 14 1111111 000 1000 1 11100000 Полученное описание управления сетью 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 11 1 1 50 у,л.сЭе Матрица М у в Э формируется ис- ходя из того, что строка смещена относительно начала участка на три позиции ( с( о( = 1), При этом необходимо учесть, что при формировании таблицы размещения на фиг. 4 использовались диаднйе сдвиги для групп по Адрес поля по 1 Адрес поля по Л Адрес участка в Адрес участка поле по 1 в поле по Л Адрес элемента Адрес элемента5на участке по 1 на участке по Л Указанная строка смещена на 5 позиций (с а " = 010) по Л относиВ соответствии с правилом формиро вания управления сетью образуем матрицы Ми Мв Э Так как строка сдвинута от начала поля на 5 позиций вправо, для восстановления порядка данных необходимо их сдвинуть на 5 40 позиций влево. Сдвигу влево на 5 позиций соответствует сдвиг вправо на 16-5 = 11 позиций. Таким образом, по входному коду с(3 ю( 0( 01 0 10 1 (допол нительный к нему 1011) на выходе пре образователя 14 кодов (фиг. 8) появится код, соответствующий матрице управления сетью (см, табл, 1): 1 4 элемента. Следовательно, общий диадный сдвиг имеет величину 12 (код 1100) и соответствующая матрица Му 1, Э опРЕДелЯетсЯ табл. 2; 0 0 0 0 0 0 О 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Теперь можно определить управление сетью в виде отражает работу и входной сети (для записи) и выходной сети (для чтения) (фиг, 10),При выборке произвольно расположенного окна для получения правильного порядка элементов необходимо также выполнять композицию перестановок: линейные циклические сдвиги, кратные и; линейные сдвиги на 1,2ипозицию в группах иэ и элементов, со18 1499 355 10 15 1 ока ( у. (,еде ставляющих строки квадратного фраг- мента (окна); диадные перестановки для компенсации диадных сдвигов; присутствующих в таблице размещения. Как и в случае выборки строки, для управления перестановочной сетью формируется матрица управления в виде(ок (окн аокиМ у М д,сто г(. сааб Матрица М оо определяется следующим образом. При смещении окна относительно положения опорного участкапо оси Л линейные сдвиги элементовпроисходят внутри строк (и строк изи элементов), Такие сдвиги выполняются на и/2 младших ярусах перестановочной сети, которым в матрице управления Мл.ода соответствуют первые Е 7 16 (5 Ф О (2 1 . (о О О О О О О 1 1 1 1 Разряды о(, а,= 11 и с( ц 1,о= 11 указывают на то, что окно сдвинуто относительно опорного участка соответственно на три позиции вправо и на трипозиции вниз, Чтобы восстановить порядок элементов, необходимо реализовать компенсирующие сдвиги, Сдвиг окна влево на три элемента соответствует циклическому сдвигу внутри строк(элементов данных, поступающих нагруппы линий шины данных (0,1,2,3);(4, 5,6, 7);(8, 9, 1 О) 1 ; ( 12, 13, 14, 15на один элемент вправо. Следовательно,строки О и 1 матрицы формируют по коду управления, соответствующему сдвигу вправо на 1 разряд (табл. 1). Приэтом рассматриваются только те разряды кода управления, которые связаныс нулевым и первым ярусами сети.Сдвигу окна на три позиции вверхсоответствует сдвиг на одну позициювниз. Так как одной позиции в данномслучае соответствует целая строка, тоэто эквивалентно циклическому сдвигувправо на 4 элемента, Следовательно,строки 2 и 3 матрицы Мд оЗ ФоРмиру50ются по коду управления, соответствующему сдвигу вправо на 4 разряда(табл, 1), И в этом случае рассматриваются те разряды кода управления,55которые связаны с вторым и третьимярусами сети,Таким образом, в соответствии скодом Ы, о 1, = 11 и ЫЫ= 11 при оби/2 строк (О, 1и/2-1) . При смещении окна по оси 1 линейных сдвиг происходит на величину, кратную и (в соответствии с количеством элементов в строке). Сдвиги, кратные выполняются на сети старшими и/2 ярусами, и в матрице Г , о им соответствуют строки и/2, и/2+1. и, Отсюда следует, что матрица М ,ао для управления сетью при выборке окна формируется для первых и/2 строк по величине смещения окна относительно о 7 орного участка по Л, а для последних и/2 строк - по величине смещения по 1. Например, квадратный фрагмент, выделенный на фиг. 4, имеет адрес, соответствующий положению левого верхнего его элемента (табл,б).Таблица 63 7 О(6 Я 4 Э 2о О О О О О О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 О О О О Величина диадного сдвига определяется положением опорного участка в поле по координате Л, т,е, разрядами с(,о(12 кода адреса, В таблице размещения реализован одномерный диадный сдвиг для групп иэ и элементов, поэтому для компенсации диадного сдвига используются старшие и/2 ярусов сети. Старший (и)-й ярус управляется (и)-м разрядом адреса (с(.,), (и)-й ярус - (и)-м разрядом (о( ) и т,д. Это справедливо для всех участков, Однако произвольно адресуемое окно может располагаться так, что попадает сразу на два участка по оси Л. В таком случае для разных частей окна, а значит, и для разных частей сети должны реализовываться различные диадные сдвиги, Для модулей памяти, попадающих на опорный участок, величина диадного сдвига ЭЯ определяется разрядамиИ = . о 1 о(п(аа для следующего участка кодом032 = ( а, М 2,о 1(2 )//