Устройство для формирования адресов элементов матриц

К АВ Мвй СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК ГОСУДАРСТВЕННОЕПАТЕНТНОЕВЕДОМСТВО СССР (ГОСПАТЕНТ СССР АНИЕ ИЗОБ СКОМУ СВИДЕТЕЛЬ(71) Центральное конструкторское бюро "Алмаз"(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ЭЛЕМЕНТОВ МАТРИЦ(57) Изобретение относится к вычислительной технике, в частности к устройствам, выполняющим адресацию матричных операндов для параллельнойпамяти, состоящей из М листов (блоков), Цельюизобретения является расширение функциональныхвозможностей устройства за счет обеспечения работы с многомодульной памятью. Цепь достигает(19) Я 3 (11) 1839252 А 2- ь ся тем, что в устройство, содержащее регистр 1, дешифратор 2, сумматор 3, элемент И 4, регистр 5, ПЗУ 6, введены блок 7 синхронизации, дешифратор 8, элемент И 9, элемент ИЛИ 10, группа из М элементов И 11, где М - количество адресуемых модулей памяти, группа из М реверсивных счетчиков 12, группа из М элементов ИЛИ 13, группа из М блоков 14 памяти и блок 15 распределения адресов. Сущность изобретения заключается в обеспечении формирования адресов для параллельной памяти, состоящей из М листов (блоков). Изобре- . тение может быть использовано в любом специализированном или универсальном вычислителе параллельных данных без специальных средств сопряжения. 1 з,п.ф-лы 6 ил.Изобретение относится к вычислительной технике, в частности к устройствам. выполняющим адресацию матричныхоперандов для параллельной памяти, состоящей из М листов (блоков). 5Известны устройства для параллельного формирования адресов памяти (авт,св,СССР М 1337898, кл, 6 06 Г 9/36, 16,01,85,й 1196867, кл. О 06 Е 9/36, 04.06.84). Этиустройства имеют следующие недостатки: 10адресация элементов массива всегда начинается с первого адреса первого листа (блока) параллельной памяти, отсутствуетфункциональная возможность формирования адресов для элементов транспонированных матриц, необходимо хранениемаксимального индекса размерности массива,Наиболее близким.к заявляемому потехнической сущности и достигаемому положительному эффекту является принятоеза прототип устройство для формированияадресов элементов матрицы (авт. св. СССРМ 1425667, кл. 6 Об Р 12/06, 19.02,87). содержащее ПЗУ, два регистра, дешифратор, 25сумматор, элемент И. Данное устройствопредназначено для адресации операндов,представляющих собой матрицы заданнойразмерности и признака транспонирования, Недостатком его является отсутствие ЗОвозможности формирования адресов матричных операндов для параллельной памяти.Целью изобретения является расширение функциональных возможностей устройства для формирования адресов элементовматриц.Цель достигается тем, что в устройстводля формирования адресов элементов матриц введены блок синхронизации, второй 40дешифратор, второй элемент И, элементИЛИ, группа из М элементов И, где М -количество адресуемых модулей памяти,группа из М реверсивных счетчиков, группаиз М элементов ИЛИ, группа из М блоков 45памяти и блок распределения адресов, причем информационный вход К-го блока памяти (К = 1 М) соединен с выходом заданияадреса ячейки блока распределения адресов, выход задания номера модуля которого 50соединен с входом второго дешифратора,К-й выход которого соединен с входом выборки К-го блока памяти группы и входомразрешения работы К-го реверсивного счетчика группы, выходы которого поразрядно 55соединены с адресными входами К-го блокапамяти группы и с соответствующими входами К-го элемента ИЛИ группы, выход К-гоблока памяти группы является К-м информационным выходом устройства, входы разрещения чтения всех блоков памяти группы обьединены и соединены с выходом второго элемента И. первый вход которого соединен с выходом признака окончания цикла блока распределения адресов, второй вход второго элемента И соединен с выходом элемента ИЛИ, К-й вход которого соединен с выходом К-го элемента ИЛИ группы, с первым входом К-го элемента И группы и является К-м управляющим выходом устройства, вход запуска блока синхронизации объединен с входом задания размерности М группы адресов блока распределения адресов и подключен к входу задания команды устройства, информационный вход блока распределения адресов соединен с выходом сумматора и является (М+1)-м информационным выходом устройства, первый выход блока синхронизации подключен к первому входу первого элемента И и к входу синхронизации второго регистра, второй выход блока синхронизации подключен к третьему входу второго элемента И, вторые входы элементов И группы объединены и подключены к третьему выходу блока синхронизации, выход К-го элемента И группы соединен с информационным входом К-го реверсивного счетчика группы.Блок распределения адресов содержит постоянную память, первая группа разрядов адресного входа которой является информационным входом блока распределения адресов, вторая группа разрядов адресного входа объединена с управляющим входом и является входом задания размерности М группы адресов блока распределения адресов, первая и вторая группы разрядов информационного выхода являются выходами задания адреса ячейки и номера модуля блока распределения адресов соответственно, последний разряд информационного выхода является выходам признака окончания цикла блока распределения адресов,Сущность изобретения заключается в обеспечении формирования адресов для параллельной памяти, состоящей из М листов (блоков),Техническое решение соответствует критерию "новизна", так как отличается от прототипа наличием новых элементов и их связей с другими элементами схемы.Техническое решение соответствует критерию "существенные отличия", так как не найдены технические решения, содержащие совокупность признаков. изложенных в отличительной часи формулы изобретения.На фиг, 1 изображена функциональная схема устройства; на фиг. 2 - пример выполнения блока сверхоперативной памяти; нафиг, 3 - функциональная схема блока синхронизации; на фиг. 4 - пример кодирования блока распределения адресов; на фиг. 5 - пример реализации второго дешифратора блока синхронизации; на фиг. 6 - функциональная схема блока распределения адресов,В состав устройства для формирования адресов элементов матриц (фиг. 1) входят регистр 1, дешифратор 2, сумматор 3, элемент И 4, регистр 5, ПЗЧ б, блок 7 синхронизации, второй дешифратор 8, второй элемент И 9, элемент ИЛИ 10, группа из М элементов 11, группа из М реверсивных счетчиков 12, группа из М элементов ИЛИ 13, группа иэ М блоков 14 памяти и блок 15 распределения адресов.Информационный вход К-го блока 14 памяти (К = 1,14) соединен с выходом 16 задания адреса ячейки блока 15 распределения адресов, Выход 17 задания номера модуля блока распределения адресов соединен с входом второго дешифратора 8, К-й выход 18 которого соединен с входом выборки К-го блока 14 памяти и входом разрешения работы К-го реверсивного счетчика 12, Выходы 19 К-го реверсивного счетчика 12 поразрядно соединены с адресными входами К-го блока 14 памяти и с соответствующими входами К-го элемента ИЛИ 13.Выход К-го блока 14 памяти является К-м информационным выходом 20 устройства. Входы разрешения чтения всех блоков памяти обьединены и соединены с выходом 21 второго элемента И 9, первый вход которогосоединен с выходом признака окончания цикла блока 15 распределения адресов. Второй вход второго элемента И 9 соединен с выходом элемента ИЛИ 10, К-й вход которого соединен с выходом К-го элементаИЛИ 13, с первым входом К-го элемента И 11 и является К-м управляющим выходом 22 устройства, Вход 23 запуска блока 7 синхронизации обьединен с входом задания размерности М группы адресов блока 15распределения адресов и подключен к входу задания команды устройства. Информационный вход 24 блока распределения адресов соединен с выходом сумматора 3 и является (М+1)-м выходом устройства, Первый выход 25 блока 7 синхронизации подключен к первому входу первого элемента И 4 и к входу синхронизации второго регистра 5, Второй выход 26 блока синхронизацииподключен к третьему входу второго элемента И 9. Вторые входы элементов И 11 обьединены и подключены к третьему выходу 27 блока 7 синхронизации, Выход К-гоэлемента И 11 соединен с информационнымвходом К-го реверсивного счетчика 12.5 10 15 20 25 ЗО 35 40 55 Устройство работает следующим образом.Исходная информация для формирования параллельных адресов содержится в операнде(Аа)(пз, п)ТР) ч 1 М) ч (-.эап). где А - базовый адрес;а) - смещение относительно базового адреса;в - количество строк матрицы;и - количество столбцов матрицы;Тр- признак транспортирования матрицы;М - количество листов параллельной памяти;Г зап - команда запуска.Устройство, получив этот операнд, осуществляет последовательную загрузку пачки адресов иэ М элементов в модули На фиг, 2 блок 14 памяти выполнен на БИС серии 1802 ИР 1, которая является регистром общего назначения на 64 бита. Данная БИС предназначена для реализации сверхоперативных запоминающих устройств радиоэлектронной аппаратуры и содержит 16 четырехразрядных регистров,В состав блока 7 синхронизации (фиг. 3) входит задающий генератор 28, дешифратор 29, счетчик 30, дешифратор 31, четыре элемента И 32, Выход задающего генератора 28 соединен с первым входом 1-го элемента И 32( = 2, 3,4). Вход дешифратора 29 соединен с шиной 23, выход - с вторым входом первого элемента И 32, выход которого соединен с входом счетчика 30. Выход счетчика 30 соединен с входом дешифратора 31, )-й выход которого Ц = 1, 2, 3) соединен с вторым входом 1-го элемента И 32. Выход -го элемента И 32 соединен с е-м выходом блока 7 синхронизации (щ = 25, 26, 27).На фиг. 5 показан пример реализации дешифратора 31 блока 7 синхронизации на ПЗУ, в котором используется микоосхема серии 556 РТ 4.Блок 15 распределения адресов (фиг, 6) содержит постоянную память 33, Первая группа разрядов адресного входа является информационным входом 24 блока распределения адресов, Вторая группа разрядов адресного входа блока распределения адресов объединена с управляющим входом 23 и является входом задания размерности М группы адресов. Первая 16 и вторая 17 группы разрядов информационного выхода постоянной памяти 36 являются выходами задания адреса ячейки и номера модуля соответственно. Последний разряд информационного выхода постоянной памяти 36 является выходом признака окончания цикла блока распределения адресов, 18392525 10 15 20 25 30 35 40 45 50 55 сверхоперативной параллельной памяти 14 и дальнейшее параллельное считывание пачки этих адресов из блоков 14 на адресные выходы 20 устройства, Блоки 14 выполнены в виде стеков,На вход 24 блока 15 распределения адресов информации поступает в виде последовательности адресов (а), 1 = (О, (т х и) - 1, с произвольным порядком следования в зависимости от признака Тр. На вход 23 этого блока поступает значение модуля М, На выходе блока 15 последовательно генерируются адреса 0 (фиг. 4);0 = а;(гпоб М),Старшие разряды 0 представляют собой адрес Гр элемента матрицы (а) в листе параллельной памяти, состоящей из М листов, младшие разряды 0 являются порядковым номером листа 1, в котором элемент матрицы аь 1= О, 1 - (т хп) - 1, 1 = 0,1 , гп х п)М) - 1, где символ ( ) означает целую часть от деления.При решении определенного класса задач, например работа с транспортированными матрицами. данные, соответствующие адресам аь при считывании (записи) из параллельной памяти могут оказаться в одних и тех же листах, Таким образом возникает конфликтная ситуация; параллельное считывание в пределах пачки адресов М произвести за один такт невозможно. Но тем не менее предлагаемое устройство позволяет выходить из таких ситуаций, хотя и с некоторой потерей эффективности, так как считывание (запись) производится не за один такт.Модуль стека блока 14 выбран равным длине пачки адресов М, что необходимо в критических ситуациях, когда вся информация пачки (М) адресов распределена в одном листе параллельной памяти. При выборке адресов из стека первым считывается последний записанный туда адрес, затем все остальные в порядке уменьшения адресов указателя стека, выполненного на реверсивном счетчике,Цикл работы устройства начинается с прихода на шину 23 кода команды (А(ав, п)Тр) ч (М) ч (П,зап) (фиг, 1), Дешифратор 2, приняв код команды запуска Л,зап, выдает сигнал разрешения на первый вход элемента И 4, на второй вход которого поступает сигнал разрешения с третьего выхода ПЗУ б. Дешифратор 29 блока 7 синхронизации, получив Лзап, выдает разрешающий уровень на второй вход элемента И 32, который начинает пропускать импульсы тактовой частоты, которые затем по шине 26 поступают нэ третий вход элемента И 9. Полученным с выхода И 9 сигналом записи информации (щ, и) и (Тр) из шины 23 записывается в регистр 1, с выхода которого затем поступает на первый вход ПЗУ 6, на второй вход которого поступает нулевая информация с выхода регистра 5, На первом выходе ПЗУ б формируется код адреса ао первого элемента матрицы. По тактовому импульсу кода адреса ао записывается в регистр 5. С выхода регистра 5 код ао поступает на второй вход ПЗУ 6 и на второй вход сумматора 3, на первом входе которого находится код А. На выходе 16 сумматора 3 формируется код смещенного адреса А + ао первого элемента матрицы, который поступает на информационный вход блока 15, на входе 23 задания модуля которого присутствует код признака (М), В блоке 15 закодированы последовательности адресов по аос 1 М (фиг. 4). На выходе 16 блока 15 появляется код 1 о старших разрядов адреса эо первого элемента, на выходе 17 - код )О младших разрядов адреса ао первого элемента: с 1 о = (А+ ао)аоб М.Код 1 О поступает на все входы блоков 14, а код /о - на вход дешифратора 8. На одном из выходов дешифратора 8 в зависимости от кода )о появляется сигнал, по фронту которого один из реверсивных счетчиков 12 увеличивает свое состояние на единицу. С выхода реверсивного счетчика 12 код состояния. определяющий адрес стека, поступает на адресный вход соответствующего блока 14, в который по входу ЧЧВ спадом сигнала 1 О записывается код 1 о адреса.Затем аналогично формируются адреса следующих элементов аз первой группы (А + аз), (Я = 1, 2, , М), На выходе блока 15 генерируются соответствующие им адреса цз. При формировании адресов с 1 з в пределах пачки М может случиться, что на выходе кода младших разрядов )э блока 15 и раз (иМ) появится код индекса одного и того же листа, следовательно, состояние соответствующего счетчика 12 также увеличивается на и,8 соответствующий блок 14 сверхоперативной памяти записывается и адресов 1, это же количество адресов не попадает в другие блоки 14. После того. как все адреса пачки М уложатся в блоки 14, с третьего выхода блока 15 приходит сигнал разрешения на первый вход элемента И 9, нэ второй входе которого находится сигнал разрешения с выхода элемента ИЛИ 10, С выхода 26 блока 7 синхронизации поступает импульс считывания на третий вход элемента И 9, с выхода которого сигнал считывания параллельно поступает на входы считывания блоков 14. С выходов блоков 14 параллельно в шину20 адресов считывается (М - и + 1)= 4. а 5 з=3,аб= 1, а 12 а 5= 15,сумматора 3 го массива м рмируютсярицы адресов первой пачки М. На М - и + 1 выходах дешифратора 8 находятся номера листов, соответствующих пачке адресов б. Затем с выхода 27 блока 7 синхронизации появляется импульс счета, который через элементы И 11 поступает на вычитающие входы реверсивных счетчиков 12. На вторые входы элементов И 11 поступают разрешающие сигналы с выходов элементов ИЛИ 13. Сигнал разрешения на второй вход 5-го элемента И 11 поступает с выхода Я-го элемента ИЛИ только в том случае, когда состояние Я-го реверсивного счетчика 12 не равно нулю. Если имелось равномерное распределение адресов (т.е, и = 1), то на выходах всех реверсивных счетчиков 12 появятся нулевые состояния, и, как следствие, с выхода элемента ИЛИ 10 снимается сигнал разрешения. Если распределение адресов в блоках 14 неравномерное (п Ф 1), то на втором входе элемента И 9 продолжает находиться сигнал разрешения. С выхода 26 блока 7 синхронизации на входы блоков 14 проходит сигнал считывания и с выходов этих блоков выдается следующая серия адресов из первой пачки М. Так продолжается до тех пор, пока все адреса не считаются из блоков 14. Когда этопроизойдет, с второго входа элемента И 9 снимается сигнал разрешения. Формирование следующих пачек М адресов производится аналогично до тех пор, пока не сформируется последняя пачка адресов М, в которой присутствует адрес последнего элемента аь Когда это произойдет, с второго выхода ПЗУ 16 приходит сигнал конца цикла, который устанавливает регистры 1, 5 в нулевое состояние, а на третьем выходе ПЗУ б формируется сигнал, разрешающий прием следующей команды. Если по каким-либо причинам необходимо прекратить формирование адресов, достаточно с шины 23 снять команду запуска.узап.Рассмотрим вариант формирования адресов матрицы для операндаСчитывание адресов производится зари шага;1 шаг -- - 02 03 04 052 шаг - 10 11 12 13 14 153 шаг 20 21 22 23 24 25Матрица транспонирована, т.е. Т р=1 4 8 5 9 6 10 7 1 13 14 15 На выходе ПЗУ б сформ элементов матрицы ао = О, а 1= 4, а 2 = 8, аз ==6, ав = 9, ат = 13, ав = 2, ад 30 а 1 = 14, а 12 = 3, а 1 з = 7, ам На выходе 24 сумматора адреса с учетом смещения Ао = 2, А 1 = б, А 2 = 10 А 5 7, А 6 = 11, А 7 = 15, А 8 = 4 35 А 11 = 16, А 12 = 5, А 1 з = 9, А 14 На выходе блока 15 и появляются адреса по вобб Ао = 02, А 1 = 10, А 2 = 14,1, А 6 = 15, А 7 = 23, А 8 О, А 1 = 24, А 12 = 05, А 25-й шаОК О 45 3 4 5 10 11 - - 1402 03дим, что возникла конфликтная ситув лист 2 записались значения адресов2, счетчик 12-2 фиксирует в двоичномостояние 0010, и при обращении клисту адреса считываются в два этапа:рвый этап: 10, 11, 22, 03, 14, - ;орой этап: - . - , 02, - , - , - .й шаг 0 ация;02 и 2кодеэтому вт 2- й 4. Ао =- 2, А 1 = 3, А 2 = 4, Аз = 5, Ал = б. А 5 = =7, Аб = 8, А 7 = 9, Ав = 10, Ад =- 11, А 1 о = 12, А 11 = 13, А 12 = 14, Агз = 15, Аи = 16, А 15 = 17.На выходе блока 15 последовательно 5 появляются адреса (фиг, 4).Ао = 02, А 1 = 03, А 2 = 04, АЗ = 05, А 4 = 10, А 5= 11, А 5= 12, А 7 = 13, Ав = 14, Ад.= 15, А 1 о = 20, А 11 = 21, А 12 = 22, А 1 з = 23, А 14 = 14, А 15 = 25. 10 В листах блока 14 адреса распределяются следующим образом:ЬЬ1839252 12 скому предложеование, показавю эффективностьанных. во СССР6; 9/34, 198 Возникла конфликтная ситуация: в лист 4 записались значения адресов 04 и 24, на на счетчике 12-4 будет состояние 0010. и и ри обращении к этому листу адреса также считываются в два этапа: первый этап: 20, - ; 12, 23, 24, 15;второй этап: - , - . - . - , 04, - .3-й шаг Здесь также адреса 05 и 25 записались один лист 5, на счетчике 12-5 будет состоние 0010, и при обращении к этому листу дреса считываются в два этапа;первый этап: - , 21. - , 13, - , 25; второй этап; 2, - , - , - , - , 05 Формирование адресов для других знаений (гп, и), (А), (а), (М), (Тр) производится налогично,Использование изобретения позволяет формировать адреса матриц произвольного рмула изобретения 1, УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ АДРЕСОВ ЭЛЕМЕНТОВ МАТРИЦ по авт, св, й 1425667, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения работы и с многомодульной памятью, в него введены блок синхронизации, второй дешифратор, второй элемент И, элемент ИЛИ, группа из М элементов И, где М - количество адресуемых модулей памяти, группа из М реверсивных счетчиков, группа из М элементов ИЛИ, группа из М блоков памяти и блок распределения адресов, причем информационный вход К-го блока памяти (К = 1, ., М) соединен.с выходом задания адреса ячейки блока распределения адресов, выход задания номера модуля которого соединен с входом второго дешифратора, К-й выход которого соединен с входом выборки К-го блока памяти 5 группы и входом разрешения работы К-го реверсивного счетчика группы, выходы которого поразрядно соединены с адресными входами К-го блока памяти группы и с соответствующими входами К-го элемента 5 ИЛИ группы, выход К-го блока памяти группы является К-м информационным выходом устройства, входы разрешения чтения всех блоков памяти группы объединены и соединены с выходом второго размера с учетом признака транспортирования для параллельной памяти, состоящей из произвольного количества М независимых листов, При этом устройством с некото рой потерей эффективности устраняютсяконфликтные ситуации, когда элементы массивов при параллельном считывании (записи) могут оказаться в одних и тех же листах.10 Поскольку исходное размещение матриц в памяти должно. быть линейным: либопо строкам, либо по столбцам, то практически это означает возможность записи исходного матричного выражения с 15 небольшим количеством транспонированных матриц,По данному техниче нию проведено модели шее достаточно высоку при работе с массивами д (56) Авторское свидетель М 1425667, кл,б 06 Е 12/ элемента И, первый вход которого соединен с выходом признака окончания цикла 0 блока распределения адресов, второй входвторого элемента И соединен с выходом элемента ИЛИ, К-й вход которого соединен с выходом К-го элемента ИЛИ группы, с первым входом К-го элемента И группы и 5является К-м управляющим выходом устройства, вход запуска блока синхронизации объединен с входом задания размерности М группы адресов блока распределения адресов и подключен к входу задания команды устройства, информаци онный вход блока распределения адресовсоединен с выходом сумматора и является (М + 1)-м информационным выходом уст ройства, первый выход блока синхронизации подключен к первому входу первого элемента И и к входу синхронизации второго регистра, второй выход блока синхронизации подключен к третьему входу 0 второго элемента И, вторые входы элементов И группы объединены и подключены к третьему выходу блока синхронизации, вы. ход К-го элемента И группы соединен с информационным входом К-го реверсивного 5 счетчика группы.2, Устройство по п,1, отличающеесятем, что блок распределения адресов содержит постоянную память, первая группа разрядов адресного входа которой является информационным входом блока распределения адресов, вторая группа разрядов адресного входа которой объединена с управляющим входом и является входом за.дания размерности М группы адресов бло ка распределения адресов, первая и вторая группы разрядов информационного выхода постоянной памяти являются выходами задания адреса ячейки и номера модуля блока распределения адресов соответственно, последний разряд информационного выхода постоянной памяти яв ляется выходом признака окончания циклаблока распределения адресов,1839252 В Фиг Редактор Т. Юрчи Тираж Подписное НПО "Поиск" Роспатента113035, Москва, Ж, Раушская наб 4/5 Заказ 3407 изводственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина. 101 оставител ехред М