Ассоциативное параллельное вычислительноеустройство

Союз Советских Социалистических РеспубликЗависимое от авт. свидетельства М аявлено 27,Ъ.1969 ( 1333139/18-24 Кл, 42 птз, 7 38 соединением заявки МПК 6 061 738УЛК 681.142.65(088.8 Приоритет Комитет по делам зобретений и открытийпубликовано 03.Х 11.1970, Бю ата опубликования описани четень Лс 36 и Совете Министров СССР97 Авторизобретения А, Чуди елемеханики (технической кибернетики) нститут автомати аявитель АССОЦИАТИ ВНОЕ ПАРАЛЛ ЕЛ ЬНОЕ ВЫЧ ИСЛ И ТЕЛУСТРОЙСТВО ми необходимо в данный момент провести операцию. Остальные операнды в это время хранятся в ячейках более дешевой памяти.Блок-схема ассоциативного процесса пред ставлена на чертеже.Устройство содержит матрицу 1 ассоциативной памяти, группу ассоциативны ячеек 2, ярлыковую ассоциативную ячейку 3, рабочую ассоциативную ячейку 4, рабочие триггеры 0 5 - 9, согласующий триггер 10 ячейки, схемулогики 11 ячейки, схему логики 12 группы, индикатор 13 совпадения группы, согласующ Й триггер 14, маскирующий регистр 15, в.;одной регистр 1 б, блок 17 контроля последователь ности команд, командный регистр 18, выходной регистр 19. Ассоциативная память вычислительного устройства0 Матрица из У один по команд В одну 25 операнда,нить опера ковую 3 и рядность рабочая 30 триггеров.Устройство может быть использовано для решения групповых арифметических и логических задач.Известно ассоциативное параллельное вычислительное устройство, в котором арифметические операции выполняются параллельно и по словам и по разрядам, а логические операции - только по словам,Предлагаемое устройство отличается тем, что выходы индикаторов совпадения ячеек соединены через схему логики группы со входами индикатора совпадения группы.Это значит, что логические схемы, обеспечивающие обработку данных параллельно и по словам, и по разрядам, используются также при обработке данных параллельно только по словам, При этом уменьшается число внешних выводов, так как шины опроса одни и те же.Кроме того, для повышения эффективности использования матрицы ассоциативных ячеек каждая группа ячеек снабжена самостоятельным каналом связи, соединяющим ее с блоком ячеек распределенной внешней и конструктивно более дешевой памяти, например с произвольной выборкой, а выход согласующего триггера ярлыковой ячейки соединен со входами согласующих триггеров ячеек этой группы. Это позволяет записывать в одну ячейку только ту пару операндов, над которы 1 ассоциативной памяти состоит аковых групп ячеек 2, работающих ам от общей схемы управления. группу ячеек можно записать два над которыми необходимо выполцию. Группа содержит одну ярлык+1 рабочую 4 ячейки, где разоперандов. Как ярлыковая, так и ячейки имеют несколько рабочих Г триггеры 5 и 6 записывают соот288414 Сложение 20 р 1 А 1 в,о ( о 0 0 1 2 3 4 5 6 7 8 40 10 01 1; 0 0 0 0 1 11; 0 0 1 11 45 50 3ветствующий разряд той пары операндов, над которой необходимо провести операцию, три гер 9 отводится год перенос, триггер 8 используется для записи меток, результат операции можно записать в триггер 7 илп в любой пз триггеров 5 плп 6. Крайняя (справа нд чрг- же) ячейка 4 содержит самый младший разряд той пары числ, ндд которымп производится операция, соседняя содержит следуощий, старший, разряд и т. д. Во входнои регистр 16 записывают код опроса. Через усилители этот код сравнивается с их содержанием, Если содержимое ячейки совпадает с содержимым кода опроса, ее индикатор вырабатывает сигнал совпадения, переводя согласующий триггер в активное состояние, и подключает ячейку к шинам записи. Это дает возможность провести запись одновременно во все ячейки, подключившиеся к шинам записи (операцию мультзаписи). Сигнал совпадения вырабатывается только для тех ячеек, для которых справедливо выражение Сс - О, гдеС 1 = (Ас Л, ас) с(А/,а) Я(Вс Л 6) //(ВЛ И)1, (Р 1 Р,Р)/(ЖЛР)1 Ч(ЖЛ Лг)/Я/ "Т/( /,11) . (ИЛИ)=О; А 1, В, Р 1, Яс, Ц - содержимое элементов памяти 4 - 8 с-той ячейки, принадлежащей с-той группе ячеек;а, Ьс, рс, гс, сс - содержимое разрядовпризнака опроса.Ассоциативная память имеет регистр 16, который позволяет наложить на любой разряд маску, исключив таким образом этот разряд из операции сравнения. Обработку данных параллельно во всех ячейках группы используют при выполнении арифметических операций, Одндко некоторые логические операции целесообразно выполнять, манипулируя группами ячеек, Для этого в каждой группе ячеек имеется еще один общий индикатор 18 совпадения группы, который выполняет логическое суммирование сигналов, получаемых на выходах индикаторов совпадения ячеек этой группы, Сигнал совпадения вырабатывается только для тех групп ячеек, для которых справедливо выражен е Сс =О, гдеСс - Сс/Сс/ /Сс/ /Сс/Сс= 0 4Ассоциативная пдмят. позволяет выполнятьгрупповые операции одновременно не во всехее группах, д только в тех, которые были предварительно помечены. Метки записываются в5 триггеры 5 - 9 крайней слева (на чертеже)ячейки, которая называется ярлыковой.Сигнал совпадения на индикаторе совладения любой другой ячейки 4, принадлежащейк с-той группе ячеек, вырабатывается в том10 случае, если ее содержимое совпадает с содержимым кода опроса и содержимое ярлыковойячейки с-той группы совпадает с содержимымкода опроса. Управляющая логика позволяетвыполнять три основные операции: сравнение,15 запись и считывание. Рассмотрим ход ариф.метических операций на примере сложения.вычитания и сдвига,Пусть требуется сложить несколько парсел, записанных в произвольно располокенные группы ячеек ассоцпдгпвной памяти. пд- примерА,+ВА,+ВА,+В,и т. д. Это зна чпт, что слагаемые А, и В записаны в первуюгруппу, слагаемые А; и В;, - в пятую и т. д.Считаем, что группы, в которые записаны пары слагаемых, были предварительно помечены. В триггерах б и б записывают слагаемые 30 А и В, триггер 8 используют для меток и триггер 9 - под перенос Р. Результат Р запишем в триггер 6, т. е. в разрядное поле второго слагаемого.Таблица истинности сложения для 1-того 35 разряда имеет вид: Примечание. А 1 и Вс - содержимое 1-того разряда пары слагаемых, записанных в с-той группе;Р - перенос с предыдущего с - 1-го разряда;и где С 1 =О (см, предыдущее выражение). Схема индикатора совпадения групп упрощается и представляст собой (и+2) входовую схему ИЛИ, так как логические схемы, ооспечивающие срдвне,е содержимого кода опроса одновременно с содержимым всех ячеек, используются и при сравнении кода опроса одновременно с одер.кимым всех групп ячеек памяти. Я -- текущее значение частичной суммы в1-том разряде.60Заметив, что текущее значение частичнойсуммы Рсс отличается от второго слагаемого В только во 2, 3, 6 и 7 комбинациях таблицы, Поэтому процесс сложения заключается в отыскании только тех разрядных групп, кото рые совпадают с комбинациями 2, 3, 6 и 7.При сложении все ячейки, содержимое корых совпадает с содержимым кода опроса, )дключают свои триггеры и разряд переноса соседней слева ячейки к шинам записи. Это ает возможность провести запись во все подгпочившиеся ячейки (операции мультзаписи). лгоритм сложения имеет вид:1) Найти ячейки, имеющиеА= 1, В= О, Р= О; Ц= ОВ эти ячейки провести мультзаппсьВ=.1; Ц=12) Найти ячейки, имеющиеА=1, В=1; Р=О, Ц=ОВ эти ячейки провести мультзаписьО 13) Найти ячейки, имеющиеА=О; В=О; Р=1; Ц=1В эти ячейки провести мультзаписьВ = 1, Р = О; Ц = 14) Найти ячейки, имеющиеАс=О, В=1, Р=1, Ц=ОВ эти ячейки провести мультзаписьВ=О, Р= О; Ц= 1; Рс+ =15) 1-1 айти ячейки, имеющие ВУ=О, Р=1 В эти ячейки провести мультзаписьВ/=1; Р= О6) Найти ячейки, имеющиеВ этп ячейки провести мультзаписьВС = О Рс = О Р+ = 1С ф С ) С7) Найти ячейки, имеющиеР=1Если таких ячеек нет, значит, процесс слокения закончен; если они есть, необходимо ще раз проверить команды 5 - 7.Команды 1 - 3 образуют частичную сумму, команды 4 - 6 доводят все переносы до зазершепия, что выявляется командой 7. Для наихудшего случая с переносами требуется т - 1 повторений шагов 5 - 7, Однако даже когда число обрабатываемых пар очень велико, ожидаемая цепочка переноса меньше т - 1 разрядов. Обычно описанный алгоритм в два - три раза быстрее алгоритма сложения с последовательной обработкой разрядов.Вычи ганнеПусть требуется провести операцию вычитания над несколькими парами чисел, напри- мерА, - ВА-, - В-,А, - В,и т. д.В триггер 5 записывают уменьшаемое АС,в триггер б - вычитаемое с.с, триггер 9 отвоС )дят под заем Р, триггер 8 также используют для меток Ц результат вычитания записывают в триггер 5, т. е. в разрядное поле вычитаемого В.Из таблицы истинности вычитания длятого разряда можно составить следующий алгоритм.1) Найти ячейки, имеющиеА=1, В=О, Р=О; Ц=О 15В эти ячейки провести мультзаггисьВ=1, Ц=1 2) Найти ячейки, имеющие А=1, ф=1, Р=О, Ц= О 20 В этп ячейки провести мультзаписьВ=О, Ц=1 3) Найти ячейки, имеющиеА=О, В=1, Р=О, Ц=ОВ эти ячейки провести мультзаппсь1, с = 1 Р 1- = 1где Р 1+ - заем в соседней слева +1)-йячейке.4) Найти ячейки, имеющиеА = О; В/ -- О; Р = О; Ц = ОВ эти ячейки провести мультзаписьВ = О; Р =- 1 25 Зо 35 5) Найти ячейки, имеющие В=1 в=О, Р- =1 40 В эти ячейки провести мультзаписьВ=1, Р= 1 6) Найти ячейки, имеющие В=1; Р=1 В эти ячейки провести мультзапись Вс= О, Р= О45 50 7) Найти ячейки, имеющиеР 1=Сдвиг 60 В мЗ мОЯПО проводить Операции сдв влево и сдвиг вправо. При вь)полнении операции сдвиг влево ячей 1;и, содержимое которых совпадает с кодом опроса, подключа 65 ют к шинам записи свои триггеры 5 - 9 иЕсли таких ячеек нет, процесс вычитания 55 закончен. Если они есть команды 5 - 7 неооходимо повторить. В наихудшем случае с займами требуется т - 1 раз повторений шагов / )о - с.288414 р 1 гер переноса 9 соседней сгсв51 Сйкп. При ВЫПОЛЧ 1 гг ОПЕР а 11 ИИ С 1 В 1 г гзпваво5 ЧСИК 1 содержимое которых сОвпадасг с кодом Опрбса, подклОчаю 1 шинам записи свои триггеры и триггер переноса 9 соседней справа разрядной группы. Для операции сдвиг влево алгоритм имеет вид: В эти ячейки провести мультзаппсьР =1 В эти ячейки провести гулызаписьА 5= 1 В эти ячейки провести мультзаппсь А=- О, Е 1 7 гтгп гРф 4Л 4 Составитель И, В, ДолгушеваТскред А, А, Камьгшникова Корректор Т. А, Угганег еактор Б. едог Изд, Р,го 47 Заказ 848 Тираж 480ЦНИПП 11 Егмитета по делам изобретений и открытий при СоМосква, Ж, Раушская наб., д. 45 Подписи е Министр гв СССПредмет изобретения 1 ссоцпатпвное 1.1 рь ллельное въчислтелное устройство для выполнения арифметиче 5 ких и логических операций, содержащее вхо,ной, командный и маскирующий регистры, р гистр последовательности команд и матриг ассоциативных ячеек, состоящую из одноро.ных групп ячеек, каждая пз которых содерж: 10 схему логики группы, одну ярлыковую и (и+ 1) рабочую ячейки, причем как ярлыкова так и рабочая ячейки содержат схему логиь ячейки, согласующий и несколько рабоче триггеров, командньгй регистр соединен чер 15 регистр последовательности команд с однимвходами матрицы ассоциат;1 вных ячеек, входной регистр через маскирующий регис 1 соединен с другими входами матрицы асс циативных ячеек, отличагощееся тем, что, 20 целью уменьшения аппаратурных затрат и пвышения эффективности использования ма рицы ассоциативных ячеек, выходы индикат ров совпадения ячеек соединены через схем логики со входами индикатора совпадени 25 группы, а выход согласующего триггера ярльковой ячейки соединен через схему логик ячеек со входами согласуюгцих триггеров р бочих ячеек этой группы.