АССОЦИАТИВНОЕ ПАРАЛЛЕЛЬНОЕ ВЫЧИСЛИТЕЛЬНОЕУСТРОЙСТВО Советский патент 1970 года по МПК G06F7/38 

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

Пзвестио ассоциативное параллельное вычислительное устройство, в котором apифJмeтические операции выполняются параллельно и по словам и по разрядам, а логические операции- только по словам.

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

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

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

Устройство содержит матрицу 1 ассоциативной памяти, группу ассоциативных ячеек 2, ярлыковую ассоциативную ячейку 5, рабочую ассоциативную ячейку 4, рабочие триггеры

5 - 9, согласующий триггер 10 ячейки, схему логики 11 ячейки, схему логики 12 группы, ппдикатор 13 совпаденпя группы, согласующий триггер 14, маскирующий регистр 15, в.чодно регистр 16, блок 17 контроля последовательности команд, командный регистр 18, выходной регистр 19.

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

20

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

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

ветствующий разряд той пары операндов, над которой необходимо провести операцию, триггер 9 отводится под перенос, триггер 8 используется для записи .меток, результат операпии можно записать в триггер 7 или н любой из триггеров 5 или 6. Крайияя (справа па чергеже) ячейка 4 содержит самый младш51Й разряд той пары чисел, над которыми пропзводится операция, соседняя содержит следующий, старший, разряд и т. д. Во входной регистр 16 записывают код опроса. Через усилители этот код сравнивается с их содержанием. Если содержимое ячейки совпадает с содержимым кода опроса, ее индикатор вырабатывает сигнал совнадения, переводя согласуюпдий триггер в активное состояние, и подключает ячейку к шинам записи. Это дает возможность провести запись одновременно во все ячейки, подключившиеся к шинам записи (операцию мультзаниси). Сигнал совт1адения вырабатывается только для те.х ячеек, для которых справедливо выражение О, где

С/ (Л/ Л аО V (Al Л «0 V (В1Л Ы V

V (В1 л ы V (Pi Л Р} V (Pi Л/01V {(Щ л п) V (/л п} V () у (Liл 0;

л/, 5/ , я/, , L/ - содерлсимое элементов памяти 4 - 8 1-той ячейки, принадлежаш.ей /-той группе ячеек;

, Ы, pi, г , 1 - содержимое разрядов признака опроса.

Ассоциативная память имеет регистр 15, который позволяет наложить на любой разряд маску, исключив таким образом этот разряд из операции сравнения. Обработку данных параллельно во всех ячейках группы используют при выполнении арифметических операций. Однако некоторые логические операции целесообразно выполнять, манипулируя группами ячеек. Для этого в каждой группе ячеек имеется еще один общий индикатор 13 совпадения группы, который выполняет логическое суммирование сигналов, получаемых на выходах индикаторов совпадения ячеек этой группы. Сигнал совнадения вырабатывается только для тех групп ячеек, для которых справедливо выражение С/ 0, где Q ClV V C/V VCr СГ О и где (см. предыдущее выражение). Схема индикатора совпадения групп упрощается и представляет собой (п + 2)-входовую схему «ИЛИ, так как логические схемы, обеспечивающие cpaBneii.ie содержимого кода опроса одновременно с содержимым всех ячеек, используются и при сравшепии кода опроса одновременно с содержимы.м всех групп ячеек памяти.

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

Сигнал совпадения на индикаторе совпадения любой другой ячейки 4, принадлежащей к г-той группе ячеек, вырабатывается в том

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

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

Сложение

Пусть требуется сложить несколько пар п;сел, записанных в произвольно расположенные группы ячеек ассоппативпой памяти. лпример 5;, Aj-f jSj,... Л,+-б(И т. д. Это значит, что слагаемые Л1 и б| записаны в нервую группу, слагаемые А и В-, - в пятую и т. д. Считаем, что группы, в которые записаны пары слагаемых, были предварительно помечены. В триггерах 5 к 6 записывают слагаемые Л и В, триггер 8 используют для меток и триггер 9-под перенос Р. Результат R запишем в триггер 6, т. е. в разрядное поле второго слагаемого.

Таблица истинности сложения для /-того разряда имеет вид: Примечание. Л/ н S/ - содержимое /-того разряда пары слагае.мых, записанных в г-той группе; р/ - перенос с предыдущего /-1-го разряда;/ /--текущее значение частичной суммы в /-том разряде. Заметив, что текущее значение частичной суммы отличается от второго слагаемого Bi только во 2, 3, 6 и 7 комбинациях таблицы. Поэтому процесс сложения заключается в отыскании только тех разрядных групп, которые совпадают с комбинациями 2, 3, 6 и 7. При сложении все ячейки, содержимое ко)рых совпадает с содержимым кода опроса, здключают свои триггеры и разряд переноса соседней слева ячейки к шинам записи. Это ает возможность провести запись во все подлючившиеся ячейки (операции мультзаписи) .лгоритм сложения имеет вид: 1)Найти ячейки, имеющие , 5/ О, Pj 0; L/ 0 В эти ячейки провести мультзапись 2)Найти ячейки, имеющие , Я/ 0, 1{ 0 В эти ячейки провести мультзапись Ц, Я/+ 1 3)Найти ячейки, имеющие L{ В эти ячейки провести мультзапись , P{ Q; 4)Найти ячейки, имеющие , В{, , Ц 0 в эти ячейки провести мультзапись , , 5)Найти ячейки, имеющие 5/ О, В эти ячейки провести мультзапись Р{ 0 6)Найти ячейки, имеющие , В эти ячейки провести мультзанись j5/ 0; Я/ 0; Р{+ 1 7)Найти ячейки, имеющие Если таких ячеек нет, значит, процесс сло кения закончен; если они есть, необходим ;ще раз проверить команды 5 - 7. Команды 1-3 образуют частичную сумму команды 4 - 6 доводят все переносы до за вершения, что выявляется командой 7. Дл наихудшего случая с переносами требуетс т-1 повторений шагов 5 - 7. Однако даж когда число обрабатываемых пар очень вели ко, ожидаемая цепочка переноса меньщ т - I разрядов. Обычно описанный алгоритм в два-три раза быстрее алгоритма сложени с последовательной обработкой разрядов. Вычитание А,-В,; A,-B,,....At-Bi в триггер 5 записывают уменьшаемое AJ, триггер 6 - вычитаемое Bi, триггер 9 отвот под «заем Р/, триггер 8 также использудля меток Ц результат вычитания запивают в триггер 5, т. е. в разрядное поле вытаемого В. Из таблицы истинности вычитания для /го разряда можно составить следующий алритм. 1)Найти ячейки, имеющие , В{ 0, Р1 0; 1{ 0 В эти ячейки провести мультзапись , 2)Найти ячейки, имеющие , , Р1 0, L{ 0 В эти ячейки провести мультзапись , 3)Найти ячейки, имеющие А/ггО, , Р{ 0, L/ 0 В эти ячейки провести мультзапись , Р{ 1, где Р - «заем в соседней слева (/-|-l)-ii ейке. 4)Найти ячейки, имеющие Л| 0; Я/ 0; L{ 0 В эти ячейки провести мультзапись В{ 0; 5)Найти ячейки, имеющие 5/ 1; Р/ 0, Р/+ 1 В эти ячейки провести мультзапись BJ.l, 6)Найти ячейки, имеющие В эти ячейки провести мультзапись В{ 0, P{ Q 7)Найти ячейки, имеющие Р{ Если таких ячеек нет, процесс вычитания кончен. Если они есть команды 5 - 7 необднмо повторить, в наихудшем случае с зайами требуется m-1 раз повторений шагов - 7. В АЗУ можно проводить операции «сдв1;г

триггер переноса 9 соседней слеза ячейки.При выполнении операции «сдвиг вправо ячейки, содер к 1:лое которых совпадает с кодом опроса, подключают к шниам записи свои триггеры и триггер переноса 9 соседней справа разрядной группы. Для операции «сдвиг влево алгоритм имеет вид:

1)Найти ячейки, имеющие

А1

В эти ячейки провести мультзаппсь Я/+ 1

2)Найти ячейки, имеющие

,

В эти ячейки провести мультзапись

3)Найти ячейки, 1меющие

,

В эти ячейки провести мультзаиись Af-0.

8 П р е д .м е т изобретения

Ассоциативное гг.рс лдельное вычислител ное устройство для выполнения арифметиче

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

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

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

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

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

г--- - -- -п; , ,, .ь .ЗПшЙШШШЩ аишйши D: I :VT, -ч -i ( йММ;й|уГ-7: и;