Ассоциативное параллельное вычислительноеустройство
И Е 288414
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
Зависимое от авт. свидетельства ¹
Заявлено 27.Ъ .1969 (№ 1333139/18-24) с присоединением заявки ¹
Приоритет
Опубликовано 03.XII.!970, Бюллетень ¹ 36
Дата опубликования описания 11.11.1971
Кл. 42m3, 7/38
МПК 6 06f 7/38
УДК 681.142.65(088.8) Комитет по делам изобретений и открытий при Совете Министров
СССР
Автор изобретения
А. А, Чудин
Институт автоматики и телемеханики (технической кибернетики) Заявитель
АССОЦИАТИВНОЕ ПАРАЛЛЕЛЬНОЕ ВЫЧИСЛИТЕЛЬНОЕ
УСТРОЙСТВО
Устройство может быть использовано для решения групповых арифметических и логических задач.
Известно ассоциативное параллельное вычислительное устройство, в котором арифметические операции выполняются параллельно и по словам и по разрядам, а логические операции — только по словам.
Предлагаемое устройство отличается тем, что выходы индикаторов совпадения ячеек соединены через схему логики группы со входами индикатора совпадения группы.
Это значит, что логические схемы, обеспечивающие обработку данных параллельно п по словам, и по разрядам, используются также при обработке данных параллельно только по словам. При этом уменьшается число внешних выводов, так как шины опроса одни и те же.
Кроме того, для повышения эффективности использования матрицы ассоциативных ячеек каждая группа ячеек снабжена самостоятельным каналом связи, соединяющим ее с блоком ячеек распределенной внешней и конструктивно более дешевой памяти, например с произвольной выборкой, а выход согласующего триггера ярлыковой ячейки соединен со входами согласующих триггеров ячеек этой группы. Это позволяет записывать в одну ячейку только ту пару операндов, над которыми необходимо в данный момент провести операцию. Остальные операнды в это время хранятся в ячейках более дешевой памяти.
Блок-схема ассоциативного процесса пред5 ставлена на чертеже.
Устройство содержит матрицу 1 ассоциативной памяти, группу ассоциативны. . ячеек 2, ярлыковую ассоциативную ячейку 8, рабочую ассоциативную ячейку 4, рабочие триггеры
10 5 — 9, согласующий триггер 10 ячейки, схему логики 11 ячейки, схему логики 12 группы, 1I}iдпкатор 18 совпадения группы, согласующ п1 триггер 14, маскирующий регистр 15, входно1> регистр 1б, блок 17 контроля последователь15 ности команд, командный регистр 18, выходной регистр 19.
Ассоциативная память вычислительного устройства
Матрица 1 ассоциативной памяти состоит из A одинаковых групп ячеек 2, работающих по командам от общей схемы управления.
В одну. группу ячеек можно записать два
25 операнда, над которыми необходимо выполнить операцию. Группа содержит одну ярлыковую 3 и n+ 1 рабочую 4 ячейки, где разрядность операндов. Как ярлыковая, так и рабочая ячейки имеют несколько рабочих
30 триггеров. F триггеры 5 и б записывают соот288414
3 ветствующий разряд той пары операндов, над которой необходимо провести операцию, три. гер 9 отводится г>од перенос, триггер 8 используется для записи меток, результат операции можно записать в триггер 7 илп в любой пз триггеров 5 плп 6. Крайняя (справа и» ч«рг«же) ячейка 4 содержит самый младший разряд TQH пары чис«л, ныд которым.» производится операция, соседняя содержит следующий, старший, разряд и ". д. Во входнои регистр 16 записывают код опроса. Через усилители этот код сравнивается с их содержанием.
Если содержимое ячейки совпадает с содержимым кода опроса, ее индикатор вырабатывает сигнал совпадения, переводя согласующий триггер в активное состояние, и подключает ячейку к шинам записи. Это дает возможность провести запись одновременно во все ячейки, подключившиеся к шинам записи (операцию мультзаписи) . Сигнал совпадения вырабатывается только для тех ячеек, для которых справедливо выражение С вЂ” — О, J где
С/ = ((А1 Q а ) g/ (А / / а>)) /((B t1р, о>) / х1(Bt Л 5)) 1(р1Л1 )х р, Л "))V((R1,, Л ) V (R Ð ")) х) (МЯ ) . (Б 1 х i>)) = О;
А1, В, Р1, Р г, Ц вЂ” содержимое элементов памяти 4 — 8 i-той ячейки, принадлежащей >-той группе ячеек; а>, b>, р1, rr, l1 — содержимое разрядов признака опроса.
Ассоциативная память имеет регистр 15, который позволяет наложить на любой разряд маску, исключив таким образом этот разряд из операции сравнения.
Обработку данных параллельно во всех ячейках группы используют при выполнении арифметических операций. Однако некоторые логические операции целесообразно выполнять, манипулируя группами ячеек. Для этого в каждой группе ячеек имеется еще один оощий индикатор 18 совпадения группы, который выполняет логическое суммирование сигналов, получаемых на выходах индикаторов совпадения ячеек этой группы. Сигнал совпадения вырабатывается только для тех групп ячеек, для которых справедливо выражен е
С =О, где, х1,, ... V С1;1..., .," V," - = 0 г и где С1 = О (см. предыдущее выражение) .
Схема индикатора совпадения групп упрощается и представляст собой (n->-2) --- входовую схему «ИЛИ», так как логические схемы, об«спечивающие сравнен..е содержимого кода опроса одновременно с содержимым всех ячеек, используются и при сравнении кода опроса одновременно с содер.>кимым всех групп ячеек памяти.
Ассоциативная пымят. позволяет выполнять групповые операции одновременно не во всех ее группах, ы только в тех, которые был.t предварительно помечены. Метки записываются B триггеры 5 — 9 крайней слева (на чертеже) ячейки, которыя называется ярлыковой.
Сигнал совпадения на индикаторе совпадения любой другой ячейки 4, принадлежащей к i-той группе ячеек, вырабатывается в том
10 случае, если ее содержимое совпад; åò с содержимым кода опроса и содержимое ярлыковой ячейки -той группы совпадает с содержимым кода опроса. Управляющая логика позволяет выполнять три основные операции: сравнение, 15 запись и считывание. Рассмотрим ход арифметических операций на примере сложения. вычитания и сдвига, Сложение
20 р1
А/
BJt о (о
О О
2
4
6
40
1 О
О 1
1; 0
1, О
О 1
1 1
О
О
О
50
Примечание. А1 и B>t — содержимое /-того разряда пары слагаемых, записанных в -той группе;
>о/ — перенос с предыдущего j — 1-го разряда;
R — — текущее значение частично суммы в
j-том разряде.
Заметив. что текущее значение частичной суммы R, отличается от второго слагаемого
В1 только во 2, 3, 6 и 7 комбинациях таблицы. Поэтому процесс сложения заключается в отыскании только тех разрядных групп, кото65 рые совпадают с комбинациями 2, 3, 6 и 7.
Пусть требуется сложить несколько пар сел, записанных в произвольно располо>кенные группы ячеек ассоциативной памяти. например А,+B,,А,+В„...At+B,и т. д. Это зна25 чпт, что слагаемые А, и В записаны в первую группу, слагаемые А.- и В;, — в пятую и т. д.
Считаем, что группы, в которые записаны пары слагаемых, были предварительно помечены. B триггерах 5 и 6 записывают слагаемые
30 А и В, триггер 8 используют для меток и триггер 9 — под перенос P. Результат R запишем в триггер 6, т. е. в разрядное поле второго слагаемого.
Таблица истинности сложения для j-того
35 разряда имеет вид:
288414
При сложении все ячейки, содержимое ко рых совпадает с содержимым кода опроса, подключают свои триггеры и разряд переноса соседней слева ячейки к шинам записи. Это ает возможность провести запись во все поддючившиеся ячейки (операции мультзаписи). .лгоритм сложения имеет вид:
1) Найти ячейки, имеющие
А/= 1, В = 0, Р = О; Ц= О
В эти ячейки провести мультзапнсь
В =.1; LJ=1
2) Найти ячейки, имеющие
А/=1, В/=1; Р =О, Ц=О
В эти ячейки провести мультзапись
B — О Ц
3) Найти ячейки, имеющие
А/ = О; В/ = О; PJ = 1; Lyf 1
В эти ячейки провести мультзапись
В =1, =0; Ц=1
4) Найти ячейки, имеющие
А =О, В/= 1, Р = 1, Ц=О
В эти ячейки провести мультзапись
Bi=0, Pi=0; Ц=1; Р + =1
5) 1-1айти ячейки, имеющие
B)=O, Ц=1
В этн ячейки провести мультзапись
В/= 1; PJ= О
6) Найти ячейки, имеющие
Bi=1; PJ=1
В этн ячейки провести мультзапись
BJ=О PJ=О PJ+ =1
7) Найти ячейки, имеющие
Р}= 1
Если таких ячеек нет, значит, процесс слокения закончен; если они есть, необходимо ще раз проверить команды 5 — 7.
Команды 1 — 3 обра=.óþò частичную сумму, команды 4 — 6 доводят все переносы до зазершения, что выявляется командой 7. Для наихудшего случая с переносами требуется и — 1 повторений шагов 5 — 7. Однако даж когда число обрабатываемых пар очень велико, ожидаемая цепочка переноса меньше т — 1 разрядов. Обычно описанный алгоритм в два — три раза быстрее алгоритма сложения с последовательной обработкой разрядов.
Вычи ганне
Пусть требуется провести операцию вычитания над несколькими парами чиаел, например
А, — В„А-, — В-„....А,— В, и т. д.
В триггер б записывают уменьшаемое AJ, в триггер б — вычитаемое В, триггер 9 отво5
1 дят под «заем» Р, триггер 8 также использу.ют для меток LJ результат вычитания записывают в триггер б, т. е. в разрядное поле вычитаемого В.
Из таблицы истинности вычитания для того разряда можно составить следующий алгоритм.
1) Найти ячейки, имеющие
А /= 1, В /= О, = 0 Ц =
В эти ячейки провести мультзаггись
В = 1, LJ = 1
2) Найти ячейки, имеющие
А/=1, P/=1, Р =О, Ц=О
В этн ячейки провести мультзапись
Bi =0, Li= 1
3) Найти ячейки, имеющие
А/=О, В/= 1, Pj=0, Ц=О
В этн ячейки провести мультзаппсь
LJ=1 PJ- =1
t l где PJ,+ — «заем» в соседней слева (j+1)-й ячейке.
4) Найти ячейки. имеющие
А = О; В/= О; Р(= О; Ц=О
В этн ячейки провести мультзапись
В/= О; PJ,=- 1
Зо
5) Найти ячейки, имеющие
Р =o, Р - =1
В эти ячейки провести мультзапись
В! 1, Pi=1
6) 1!айти ячейки, имеющие
В =1; Р =1
В этн ячейки провести мультзапись
В =0, PJ О
50
7) Найти ячейки, имеющие
PJ 1
Сдвиг
В АЗУ можно проводить операц н «сдвиг влево» и «сдвиг вправо». При вь по".ненни операции «сдвиг влево:: ячейки, содержимое которых совпадает с кодом опроса, подключа65 ют к шинам записи свои триггеры 5 — 9 и
Если таких ячеек нет, процесс вычитания
55 закончен. Если они есть команды 5 — 7 неооходнмо повторить. В наихудшем случае с займами требуется т — 1 раз повторений шагов
7 о — /.
288414
11редмет изобретения
1) Найти ячейки, имеющие
А = 1 г
B эти ячейки провести мультзаппсь
Р +1 = 1
2) Найти ячейки, и>мекнцие
А/= О, Р = 1
В эти ячейки провести мулыгза, 1псь
А = 1
3) Найти ячейки, имеющие
А/=1, Р =О
В эти ячейки провести мультзапись
Л
<ДДфЯф 4< ф
1 и — — — <1
Составитель И. В. Долгушева
Рc. Iai<òор Б. Б. Федогов Тсхред А. А, Камь<шникова К<>ррект,>р Т. А, Уманеи
Изд. № 47 Заказ 84,, 8 Тираж 480 Подписное
Ц1-1И11П11 V<>.,<итета по делам изобретений и открытий при Совете Министр >в С(СР
Москва, Ж-35, Раушская наб., д. 4:5
Типография, пр. Сапунова, 2
i pIIi pep переноса 9 cocc,iней c,!C 1а я ейкп. Пр<1
BbIIio <и< 1< ип 0 i ipp апни <<< .<в<1c >,<<и а во . я i III
1 у
1 (1
1
1 ! >
1 !
1(—
< <
1 1 <
1
1 1ссоцпатпвное 1:ар е 1;Ie;IbHOe въ<числптел ное устройство для выполнения арифметиче
5 ких и логических операций, содержащее вхо, ной, командный и маскирующий регистры, р гистр последовательности команд и матриг ассоциативных ячеек, состоящую из одноро. ных групп ячеек, каждая пз которых содерж:
10 схему логики группы, одну ярлыковую и (п+1) рабочую ячейки, причем как ярлыкова так и рабочая ячейки содержат схему логив ячейки, согласующий и несколько рабоче триггеров, команднь>й регистр соединен чер<
15 регистр последовательности команд с одним входами матрицы ассоциат;1вных ячеек, входной регистр через маскирующий регист соединен с другим11 входами матрицы асс< циативных ячеек, отличагощееся тем, что, 20 целью уменьшения аппаратурных затрат и п< вышения эффективност" использования ма рицы ассоциативных ячеек, выходы индикат< ров совпадения ячеек соединены через схем логики со входами индикатора совпадени
25 группы, а выход согласующего триггера ярль ковой ячейки соединен через схему логик ячеек со входами согласующих триггеров р бочих ячеек этой группы.
