Операционное устройство для процессора с ассоциативной матрицей однородной структуры

Операционное устройство для процессора с ассоциативной матрицей однородной структуры

Реферат

 

Изобретение относится к матричному процессору с однородной структурой или к структуре матрицы ассоциативной обработки с переменной длиной слова, управляемой битами конфигурации, содержащимися в отдельных ассоциативных ячейках. При этом достигается улучшение гибкости применения ассоциативной матрицы благодаря тому, что длина слова может быть произвольно расширена, желаемые функции могут произвольно выполняться внутри матрицы, например, функции пропуска или запрета. Кроме того, исключается необходимость во внешней маске для определенных ячеек, которые должны работать определенным образом. 1 з.п. ф-лы, 25 ил., 7 табл.

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

Битами конфигурации могут обозначаться и другие функции в слове, такие, как запирание или пропуск. Кроме того, любая ассоциативная ячейка в матрице может быть исключена из слова. Матрица содержит также расширенный набор команд, включающих булевское умножение, деление, а также все комбинации одинарной и двоичной точности, сдвига или поворота, левосторонних или правосторонних операций. Матрица ассоциативной обработки по данному изобретению дает особые преимущества при реализации его с использованием больших интегральных схем (БИС) или очень больших интегральных схем (ОБИС), которые позволяют повысить степень универсальности системы без увеличения количества схем и штыревых соединений.

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

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

Если обычный процессор в каждый момент времени оперирует одним элементом данных, то ассоциативный процессор работает со множеством объектов данных одновременно. С этой точки зрения полезно, чтобы объекты данных для каждой отдельной команды были однотипны, с тем чтобы имело смысл использовать один и тот же поток последовательных команд для одновременных операций над этими объектами данных. Процессор такого класса известен под названием SIMD "Одна команда много потоков данных".

Такой ассоциативный процессор может состоять из прямоугольной матрицы из реализованных на БИС однобитовых компьютеров, каждый из которых может иметь память объемом от 2 К до 64 К бит. Эти компьютеры, представляющие собой ячейки однородной структуры, одновременно подчиняются одной команде, однако каждый оперирует своими данными. Эти ячейки могут связываться со своими соседями по всем четырем направлениям, а также с входными и выходными регистрами внешних данных.

Ячейки в строке матрицы ассоциативного процессора могут быть динамически (от одной команды до другой) организованы в произвольное число полей произвольной длины (ограниченной шириной матрицы). После этого каждое поле работает самостоятельно как отдельный компьютер с данной длиной слова, который может выполнять арифметические и логические операции. Эти поля могут либо одновременно подчиняться одной и той же команде, либо быть селективно заперты по программе.

В итоге набор компьютеров с произвольной длиной слова, которые оказываются включенными, выполняют одновременно одинаковые арифметические или логические операции над различными данными. Такой набор компьютеров может быть использован для решения задач, требующих использования матричной арифметики, алгебры, векторных расчетов, обработки изображения, задач поиска и распознавания образа и распознавания речи. Арифметические операции заданной точности при этом могут выполняться как с фиксированной, так и с плавающей запятой. Пропускная способность такого набора процессоров зависит от размера матрицы, длины и количества полей и соотношения матрицы, используемой для конкретной операции. Например, матрица из 128128 ячеек, оперирующая с 2048 восьмибитовыми числами одновременно при тактовой частоте 10 МГц, может выполнять до 4000 миллионов сложений или логических операций в секунду или порядка 1000 миллионов умножений в секунду.

Устройства ассоциативной памяти, именуемые иногда "Память, адресуемая по содержанию", достаточно широко известны и организуются в ассоциативном процессоре таким образом, что арифметические операции могут выполняться на одном или многих хранящихся в этой памяти цифровых словах одновременно. Такие ассоциативные процессоры описаны в патенте США N 4068305. Как показано в патенте США N 4296475, такая адресуемая по содержанию память организована словами, и предприняты попытки сокращения количества контактных штырьков, необходимых для использования такой памяти. Связь между определенными битами слова команды и ранее установленными флажками (от триггеров состояния, например) используется в тех случаях, когда процессор данных выполняет команды по условию путем создания в словах команды битов маскирования для того, чтобы отвергать один или более битов связи. Это описано в патенте США N 4010452. B патенте США N 4044338 описана ассоциативная память с отдельными ассоциативными зонами. Селективная связь схемных элементов с шиной данных, при которой каждый схемный элемент имеет ассоциативный адрес, описана в патенте США N 4188670. В патенте США N 4159538 описана ассоциативная память на БИС, в которой число контактных штырьков уменьшено за счет совместного использования определенного набора штырьков входными данными, выходными данными и маскировочной информацией. Ассоциативная память с последовательным доступом описана в патенте США N 4153943. Устройство ассоциативной памяти для сравнения между определенными пределами описано в патенте США N 3845465. Матричный процессор, процессорные элементы которого организованы в прямоугольную матрицу, описан в патенте США N 3979728. Мультиплексирование аналоговых сигналов описано в патенте США N 3654394 "Ключ на полевом транзисторе, в частности, для мультиплексирования". В патентной заявке США N 452596, поданной С. Мортоном 23 декабря 1982 г. под названием "Восстановление импеданса для быстрого переноса", описано однородное суммирующее устройство с динамической конфигурацией.

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

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

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

Такой мультиплексор может быть реализован на интегральных схемах с МОП-транзисторами или ДМОП-транзисторами (дополняющими) и может быть динамически организован таким образом, чтобы исключать неисправную или ненужную обрабатывающую ячейку из работы. При этом обеспечивается минимальная задержка в процессе сбора обрабатывающих ячеек. Все это обеспечивает повышение надежности, гибкости и быстродействия обрабатывающей матрицы. Длина слова может быть произвольно увеличена и достигнута максимальная скорость вычисления, причем для компенсации ячеек, отказавших в процессе изготовления или эксплуатации, могут быть предусмотрены запасные ячейки.

Цель настоящего изобретения состоит в улучшении гибкости при использовании ассоциативных процессоров.

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

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

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

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

На фиг. 1 дана блок-схема ассоциативного процессора; на фиг. 2 чип ассоциативного процессора и связи между обрабатывающими ячейками; на фиг. 3 - основные горизонтальные связи между соседними обрабатывающими ячейками; на фиг. 4 вертикальные связи между обрабатывающими ячейками; на фиг. 5 все связи обрабатывающей ячейки; на фиг. 6 структура сдвига одного слова; на фиг. 7 структура сдвига сдвоенного слова; на фиг. 8 использование слоя; на фиг. 9 схема магистрали общей логической команды в чипе ассоциативного процессора; на фиг. 10 схема логической матрицы, программируемой логическо-арифметической командой ячейки; на фиг. 11 схема арифметического ядра обрабатывающей ячейки; на фиг. 12 линейная матрица поперечных горизонтальных мультиплексоров; на фиг. 13 потоки данных в поперечных горизонтальных мультиплексорах; на фиг. 14 детальная схема поперечного горизонтального мультиплексора; на фиг. 15 упрощение схемы управляющего сигнала; на фиг. 16a схема вентиля передачи; на фиг. 16b эквивалентная схема с сосредоточенными элементами схемы по фиг. 16a в состоянии проводимости; на фиг. 17 упрощенная эквивалентная схема последовательности вентилей передачи; на фиг. 18 использование маршрута сигнала в ассоциативном процессоре, выполняющем команду сложения; на фиг. 19 использование маршрута сигнала в ассоциативном процессоре, выполняющем арифметическо-логическую команду сдвига вправо; на фиг. 20 использование маршрута сигнала в ассоциативном процессоре, выполняющем пропуск поля в промежуточной части операции слова; на фиг. 21 использование маршрута сигнала в ассоциативном процессоре, выполняющем знаковую операцию; на фиг. 22 использование маршрута сигнала в ассоциативном процессоре, выполняющем команду поворота влево; на фиг. 23 использование маршрута сигнала в ассоциативном процессоре, выполняющем команду поворота влево с удвоенной точностью; на фиг. 24 использование маршрута сигнала в ассоциативном процессоре, выполняющем промежуточную команду умножения с фиксированной запятой; на фиг. 25 использование маршрута сигнала в ассоциативном процессоре, выполняющем команду деления с фиксированной запятой.

1. Введение Обработка данных в показанном на фиг. 1 ассоциативном процессоре выполняется на матрице NM. Размер матрицы не является существенным для данного изобретения, хотя чем матрица больше, тем больше пропускная способность. Матрица NM благодаря динамической компенсированности ассоциативного процессора может одинаково хорошо оперировать с N числами по M битов каждое, 2N числами по M/2 битов каждое, 4N числами по M/4 битов каждое или с любой другой комбинацией, имеющей такое же общее количество битов. Кроме того, такая матрица может работать и с меньшим общим количеством битов, хотя при этом будут использованы не все ячейки матрицы.

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

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

Слова могут формироваться из ячеек, расположенных на различных чипах. При этом верхний предел размера слова по существу не ограничивается. Ячейки, расположенные по краям чипа, работают так же, как остальные, поскольку для работы каждой ячейки не существенно, где находится соседняя ячейка на этом же чипе или же на другом. Не существенно также, находится ли другой чип в той же строке или в другой. На фиг. 3 показаны горизонтальные связи между ячейками, состоящие из пяти арифметических соединений линии переноса, линии ALU, линии MQ, линии цикла и линии состояния.

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

Работа каждой ячейки такой матрицы определяется двумя факторами. (1) Существуют управляющие биты, которые посылаются ко всем ячейкам, и предполагается, что таких битов 32. Эти биты подаются извне чипа и делятся на 24 бита управления маршрутом данных, пять битов управления состоянием, 2 бита управления регистром данных памяти и один бит запирания. Биты управления маршрутом данных включают 6 битов команды, которые выбирают арифметическую или логическую операцию или операцию сдвига или конфигурации, которая должна быть выполнена над словом.

(2) Существуют биты конфигурации, которые хранятся в многопортовой памяти с произвольным доступом в каждой ячейке. Три из этих битов дешифрируются для идентификации, среди прочего, LSS, ISS и MSS в слове. Всего в каждой ячейке содержится 7 битов конфигурации, 3 горизонтальные маски ALUP (арифметическологический единичный процессор), 3 вертикальные маски AIP и маска восстановления импеданса.

Как показано на фиг. 11, каждая ячейка состоит из 64 ячеек памяти с произвольным доступом, причем каждая такая ячейка содержит один бит. Эта память является многопортовой памятью с произвольным доступом, которая с точки зрения арифметического и логического блока имеет два выхода A и B. 6-битовый адрес считывания (R ADDP) выбирает одну ячейку, в то время как 6-битовый адрес считывания-записи (R/W ADDP) выбирает другую ячейку. Если результат должен быть записан в память, то адрес считывания-записи специфицирует как один из источников, так и место назначения данных.

Концептуально многопортовая память с произвольным доступом делится на верхнюю и нижнюю половины. Нижние 32 ячейки считаются памятью пользователя и не имеют специальных характеристик. Верхние 32 ячейки считаются системной памятью и имеют множество специальных характеристик.

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

Соединения чипа, а также между ячейками в общем показаны на фиг. 2. Подробности горизонтальных соединений между двумя ячейками показаны на фиг. 3, а вертикальных соединений между двумя ячейками на фиг. 4. Эти соединения реализуются вне зависимости от того, находятся ли эти ячейки на одном или на различных чипах. Все соединения одной ячейки показаны на фиг. 5.

Пять связывающих чипы линий арифметических сигналов позволяют словам связывать различные чипы. Линии "ALU влево", "перенос влево", "MQ влево", "цикл влево" и "состояние влево", отходящие от самого левого столбца чипа, обычно подходят к правой стороне самого правого столбца чипа, который является левым в той же строке или, если чип находится в самом левом столбце матрицы, то к правой стороне самого правого чипа в матрице, строкой выше. Эти же сигналы от чипа, находящегося в левом краю верхней строки матрицы, обычно подводятся к правой стороне самого правого чипа матрицы в нижней строке.

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

Способ выполнения команды конкретной ячейкой зависит от типа слоя, в котором эта ячейка установлена. Разделение слоев в слои показано на фиг. 8, а использование пяти реализуемых слоев, которые выбираются битами трех горизонтальных масок ALUP, осуществляется следующим образом: неактивный заставляет ячейку замораживать свою память и делает ее невидимой по горизонтали; горизонтальный пропуск заставляет ячейку становиться невидимой по горизонтали, но допускает обновление ее памяти. Слой горизонтального пропуска полезен в тех случаях, когда требуется скопировать бит в несколько слоев, например, для расширения знака.

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

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

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

ISS промежуточный значащий слой. Все соединения специфицируются командой, например, ввод (carri IN) выходит из слоя вправо, в вывод (carry out) входит в слой слева.

Одиночные биты, логические уровни могут быть слоем типа LSS. Арифметические команды и команды поворота, требующие слов, состоящих по меньшей мере из двух битов, могут быть LSS и MSS, а также могут иметь любое число ISS.

3. Основные блоки аппаратных средств.

3.1 Магистраль команд.

Магистраль команд состоит из общей логическо- командной магистрали, показанной на фиг.9, а также из логическо-командной ячейки PLA, показанной на фиг.10, 29 сигналов управления ALUP должны стабилизироваться непосредственно перед падающим фронтом тактового импульса ALUP. Таким образом, для установления этих сигналов имеется время, составляющее большую часть длительности первого тактового импульса.

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

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

Показанные на фиг.2 три бита горизонтальной маски ALUP управляют PLA, и поэтому следует с осторожностью относиться к изменению маски, поскольку изменение маски влияет на выполнение команды, а результат задерживается на один тактовый период. На чип могут подаваться либо неиспользуемые сигналы управления состоянием, либо команда конфигурации, которая не зависит от маски и может следовать за изменением маски.

3.2 Многопортовая память с произвольным доступом.

Показанная на фиг. 11 многопортовая память с произвольным доступом емкостью в 64 слова концептуально делится на две половины, нижняя половина или половина пользователя включает память общего назначения без специальных входов или выходов. Верхняя, или системная половина, имеет множество специальных входов и выходов и выполняет множество специальных функций. Пример присвоения адреса показан в табл. 1. Ко всем из этих битов имеется доступ для записи и считывания внутри ячейки.

Эта память имеет три порта. Два выходных порта RAM A и RAM B адресуются адресом считывания и адресом считывания/записи соответственно. RAM A проходит ко входу ALU "A", а RAM B ко входу ALU "B". Выходной порт BIN также адресуется адресом записи/считывания.

Операция типа: A OPERATION B__ B читается "операция B переходит к B" и может быть выполнена в течение одного цикла. Операция над содержимым A, выбираемым адресом считывания, совершается только с помощью B, выбираемым адресом считывания/записи, а результат условно хранится в B. Загружается или не загружается B, зависит от сигналов отпирания ALUP, отпирания (enable) памяти и отпирания памяти состояния, что будет описано далее.

Эти операции включают исчерпывающий набор арифметических и логических команд, а также команд сдвига и поворота. Структуры сдвига одного слова показаны на фиг. 6, а структуры сдвига сдвоенного слова показаны на фиг.7. Набор команд сведен в табл. 3-6.

Системная половина многопортовой памяти с произвольным доступом обеспечивает доступ к различным линиям входа выхода, а также к битам управления конфигурацией и состоянием. Эти биты используются следующим образом: 3.2.1. MQ Бит MQ, множитель/частное используется при выполнении команд умножения, деления, а также сдвига и поворота сдвоенного слова. Доступ к этому биту может осуществляться независимо от адресов считывания и считывания-записи через линию MO.

3.2.2. MDR MDR регистр данных памяти связывает ячейку с внешней памятью. Доступ к этому регистру может осуществляться независимо от адресов считывания/записи и считывания через линию внешней памяти и управляется двумя сигналами управления MDR "направление" и "строб".

3.2.3. Регистр состояния Биты "перенос", "отрицательный", "нулевой" и "переполнение" составляют регистр состояния. Входами к каждому биту является шина ALU D, которая используется при выборе бита адресом считывания/записи и другими источниками, выбранными командой PLA. Запись в эти ячейки управляется отдельно от записи в ячейки, выбираемые адресом считывания/записи. Такое независимое управление осуществляется по линиям отпирания памяти.

Входами к битам регистра состояния для арифметической и логической команд являются: бит переноса вывод ALU, отрицательный бит ALUD BUS, нулевой бит мультиплексор состояния влево/вправо, бит переполнение переполнение ALU. Бит "нулевой", фактически бит "ненулевой" называется также триггером состояния и используется всеми зависящими от данных командами, такими, как уплотнение и деление и, следовательно, его значения изменяются от команды и команде. Триггер нуля является инвертированным, поскольку арифметическая и логическая команды являются действительными, когда результат является ненулевым.

3.2.4. Стойкое переполнение (Sticky Over flow).

Бит стойкого переполнения управляется отдельно от регистра состояния. Он реализует логическую операцию ИЛИ между собой и переполнением ALU и может быть использован для текущей проверки наличия или отсутствия состояния ошибки. Обычно загружается, когда действительным становится младший значений бит слова, например, последний цикл последовательности умножения.

3.2.5. Шина и линия Четыре регистра, а именно: регистры горизонтальной шины, вертикальной шины, линии вверх и линии вниз обеспечивают вход и выход ячейки. Каждый регистр может загружаться от шины или линии, имеющей такое же название, и наоборот, каждая шина или линия может непосредственно управляться от одноименного регистра. Кроме того, эти регистры обеспечивают выполнение трехадресных операций, а именно A PLUS B__C, где C один из регистров. Любой из этих битов может загружаться из ALUD BUS независимо от адреса считывания/записи. Эти регистры могут также быть обойдены, т.е. шина или линия могут быть непосредственно соединены со входом ALU, а содержимое этих регистров остается неизменным. Такой прямой ввод наряду с прямым выводом из ALU обеспечивает накопление результатов от строки к строке, что называется "бортовая операция", которая будет разъяснена далее. Эти регистры управляются функцией ввода/вывода и сигналами выбора ввода/вывода, которые являются частью управляющих сигналов линии данных.

3.2.6. Маска восстановления импеданса Маска восстановления импеданса используется пятью арифметическими линиями для сведения к минимуму времени распределения сигналов в чипе. Эта маска не имеет специальных входов и должна обеспечить уменьшение выдержки в чипе на 50 Использование маски восстановления импеданса в линии переноса описано в ранее поданной заявке Мортона N 452592 от 23 декабря 1982 г.

3.2.7. Горизонтальная маска ALUP Три горизонтальных маски ALUP организуют ячейки в слова. См. "Типы слоев".

3.2.8. Вертикальные маски ALUP Три вертикальные маски ALUP управляют потоком информации по линиям вверх и вниз. Маски 0 и 1 дешифрируются для управления информацией, подводимой к строке, а маска 2 выбирает данные, которые выводятся из строки (см. табл. 2). Если вертикальная маска 2 действительна, то выход ALU может стать выходом из строки, а использование команды прямого ввода позволяет этому выходу стать входом ALU следующей строки. Эти операции являются многострочными или "бортовыми". Таким образом, множество строк может оперировать данными, накопленными поперек строк. Таким образом, сумма данных от всех строк может быть вычислена в одном цикле. Кроме того, данные могут перемещаться вверх и вниз в соответствии с выбором, который осуществляется сигналами выбора ввода/вывода.

3.3. Арифметический и логический блок Арифметический и логический блок (ALU) выполняет семь арифметических, семь логических и две постоянные функции. Эти функции отражены в табл. 3 и в первых семи командах в табл. 4. Эти функции явно выполняются логическими командами и некоторыми из арифметических команд и неявно выполняются другими командами.

3.4. Горизонтальные линии данных Между соседними ячейками имеется пять основных горизонтальных линий данных. Эти линии, а именно ALU, "перенос", MQ "цикл" и "состояние" поддерживают арифметические операции. Эти линии являются существенными для работы чипа и обеспечивают возможность реализации произвольной длины слова, перекрытия диапазона от множества слов в одном чипе до множества чипов на одно слово. Эти линии выводятся из чипа из каждой строки с левой стороны самого левого столбца и с правой стороны крайнего правого столбца, четыре из этих линий, а именно ALU, MQ, "цикл" и "состояние" являются двунаправленными, а их работа зависит от поперечных горизонтальных мультиплексоров. Линия переноса является однонаправленной и описана в патентной заявке Мортона "Восстановление импеданса для распределения быстрого переноса".

Основной проблемой обеспечения произвольной длины слова является проблема связи противоположных концов слова между собой. В обычных ЭВМ с фиксированной длиной слова младший значащий слой связан со старшим значением слоев одним проводом. Это соединение используется для операций с одиночным словом, таких, как поворот, и операций со сдвоенным словом, таких, как умножение и деление. Один 16-ти битовый чип ассоциативного процесса может потребовать сотен проводов, если каждый возможный старший значащий слой непосредственно связывать с каждым возможным младшим значащим слоем. Произвольной является не только длина слова, но и положение слова в последовательности ячеек. Проблема осложняется также тем, что необходимо обеспечить возможность соединения произвольного количества чипов ассоциативного процесса в матрицу различных размеров. Число возможных соединений при этом оказывается очень большим.

3.4.1. Поперечный горизонтальный мультиплексор Поперечный горизонтальный мультиплексор перемещает бит из ячейки к ее левому или правому соседу или перемещает бит от левого или правого соседа к другому соседу, обходя ячейку. Таким образом, последовательность ячеек может быть произвольно разделена в слова путем выбора некоторых мультиплексоров для связи битов в группы, образующие собственно слова, а мультиплексоров в других ячейках для формирования граничных битов, т.е. в младшем и старшем значащих слоях, разделяющих слова. Команда PLA использует горизонтальные маски ALUP, которые идентифицируют типы слоев, а также коды команды для надлежащего управления различными горизонтальными мультиплексорами.

Поперечные горизонтальные мультиплексоры в основном реализуются в виде интегральных схем с МОП-транзисторами и ДМОП-транзисторами. Настоящее изобретение направлено на использование таких устройств в матрице. При этом облегчается связь между тремя соседними устройствами (см. фиг. 12). Сигнал "влево" от поперечного горизонтального мультиплексора, расположенного в середине, т. е. ячейки М, проходит к контакту "вправо" ячейки М+1, а сигнал "вправо" от ячейки М проходит к контакту "влево" ячейки М-1.

На фиг. 13 показаны потоки данных, которые могут иметь место при наличии поперечного горизонтального мультиплексора. Каждый мультиплексор имеет четыре сигнальных узла, из каждого из которых выходит однобитовая линия, а также управляющие коды. Имеется однонаправленный вход данных и однонаправленный выход данных. Линия сигнала "влево" к контакту "вправо" левого соседа, как и линия сигнала "вправо" к контакту "влево" правого соседа, являются двунаправленными. Управляющие входы позволяют выбрать пять потоков данных: 1. от ячейки M к ячейке M+1 линия 1A связывает вход данных с контактом "влево", а линия 2B связывает контакт "вправо" с выходом данных; 2. от ячейки M к ячейке M+1 линия 2A связывает вход данных с контактом "вправо", а линия 2B связывает контакт "влево" с выходом данных; 3. от ячейки М-1 к ячейкам М+1 линия 3 обеспечивает однонаправленное соединение от контакта "вправо" к контакту "влево", а линия 1B обеспечивает соединение контакта "вправо" с выходом данных; 4. от ячейки М+1 к ячейке М-1 линия 4 обеспечивает однонаправленное соединение контакта "влево" с контактом "вправо", а линия 2B обеспечивает соединение контакта "влево" с выходом данных; 5. между ячейками М+1 и М-1 линия 5 обеспечивает двунаправленное соединение между контактами "влево" и "вправо".

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

Поперечный горизонтальный мультиплексор состоит из трех двухвходовых мультиплексоров, двух буферов, имеющих три состояния, и двунаправленного вентиля передачи. Мультиплексор М3 называется "Мультиплексор влево/вправо", поскольку он осуществляет выбор между сигналами влево и вправо. Требуется лишь по одному соединению с левым и правым соседями (см. фиг.14).

Существуют пять управляющих сигналов: "обход", "выбор влево/вправо", "выбор выхода", "стрелка влево" и "стрелка вправо". Логика, показанная на фиг. 15, позволяет использовать только три управляющих сигнала, а сигналы "стрелка влево", "стрелка вправо" и "выбор выхода" вырабатываются из сигнала направления. Использование такой логики предполагалось и выше и обеспечивает протекание входных данных либо вправо, либо влево, но не в оба направления одновременно, а входные данные выходят из входных данных справа и слева, но не из выходных.

Далее используется следующее определение: 1. вентиль передачи вход и выход взаимозаменяемы, между входом и выходом имеет место большой импеданс, если сигнал на линии управления соответствует логическому нулю, и малый импеданс, если сигнал на линии управления соответствует логической единице; 2. буфер выход повторяет вход, малый импеданс по отношению к линии питания или земле имеет место, когда сигнал на линии управления соответствует логической единице, и высокий выходной импеданс, если сигнал на линии управления соответствует логическому нулю; 3. двухвходовый мультиплексор выход Y повторяет вход "0", если сигнал на линии выбора соответствует логическому нулю; выход повторяет вход "1", если сигнал на линии выбора соответствует логической единице.

Далее приводится подробное описание работы поперечного горизонтального мультиплексора.

1. Данные проходят от входа данных к выходу влево: сигнал "обход" на Т1 соответствует логическому нулю. "Выбор влево/ вправо" устанавливается соответствующим логическому нулю для "выбора ввода данных", "стрела влево" устанавливается на логическую единицу, так что контакт "влево" принимает выбранные данные от М1, а "стрела вправо" устанавливается на логический нуль, так что данные могут входить справа. Выбор выхода устанавливается на логическую единицу, так что данные на контакте "вправо" посылаются к выходу данных на М3.

2. Данные проходят от ввода данных к контакту "вправо": то же самое, что в случае 1, за исключением того, что "стрелка вправо" соответствует логической единице, а "стрелка влево" и выбор выхода логическому нулю.

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

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

5. Данные проходят между левой и правой ячейками: сигналы "выбор входа", "выбор выхода" и "выбор приема" не используются. "Стрелка влево" и "стрелка вправо" устанавливаются на логический нуль. "Обход" устанавливается на единицу, так что между контактом "влево" и контактом "вправо" устанавливается двунаправленное соедине