псевдоассоциативный процессор

Формула изобретения

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

Описание изобретения к патенту

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

Известны ассоциативные процессоры (АП), содержащие ассоциативное запоминающее устройство (АЗУ) с доступом по строкам запоминающей матрицы и по битовым срезам, каждый из которых содержит одноименные биты всех строк. В АП также входят буфер ввода-вывода, регистр компаранда, регистры хранения ответов (маркеры), логика сравнения битов компаранда с битовыми срезами и блок управления (контроллер), который осуществляет адресацию строк и срезов, управляет чтением и записью АЗУ и операциями сравнения. Подобные процессоры и входящие в них АЗУ описаны в литературе [1, 2, 3].

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

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

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

В предлагаемом техническом решении роль АЗУ играют два блока памяти с адресным доступом, один из которых играет роль памяти строк, а второй - роль памяти срезов. Память строк преобразуется в память срезов (или наоборот) путем транспонирования, после которого битовые срезы становятся доступными как обычные слова.

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

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

Рассмотрим пример транспонирования запоминающей матрицы, содержащей 16 24-битных (3-байтовых) слов. В табл. 1 показана структура матрицы и ее обобщенное представление, где а_ij, b_ij, c_ij, d_ij, f_ij, g_ij - биты восьмерок байтов А, В, С, D, F, G соответственно. В табл. 2 показана структура транспонированной матрицы, состоящей из транспонированных восьмерок байтов А^T, В^T , С^T, D^T, F^T, G^T. Матрица содержит 24 16-битных среза.

Схема предлагаемого процессора приведена на фиг.1, где 1 - буфер ввода-вывода, 2 - первый блок памяти, 3 - второй блок памяти, 4 - схема транспонирования, 5 - регистр компаранда, 6 - блок схем сравнения, 7 - блок регистров маркеров, 8 - контроллер.

Блок 6 осуществляет сравнение битов компаранда с битовым срезом по числу двоичных разрядов среза.

Первый блок памяти 2 подключен через буфер 1 к внешней шине процессора. Байтовый выход блока 2 через схему 4 соединен с байтовым входом блока 3, байтовый выход которого соединен через схему 4 с байтовым входом блока 2. Срезный выход блока 3 соединен с первым входом блока 6, второй вход которого подключен к выходу регистра 5, выход блока 6 соединен с входом блока маркеров 7, первый выход которого соединен с входом записи срезов блока памяти 3, а второй выход блока 7 соединен с входом контроллера 8, выходы которого соединены с управляющими входами блоков 2, 3, 4, 6 соответственно.

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

Выполнение этих операций аналогично их выполнению в обычных ассоциативных процессорах и поэтому подробно не рассматривается.

Более детально рассмотрим схему транспонирования (фиг.2) и порядок ее работы. Схема содержит 64-битный регистр 10 с целью сдвига на 8 битов влево, 64-битный регистр 11 с целью сдвига на 1 бит влево, мультиплексор 9 и демультиплексор 12. Входы мультиплексора соединены с байтовыми выходами первого и второго блоков памяти соответственно, а выходы демультиплексора - с байтовыми входами этих блоков. Выход мультиплексора 9 соединен с входом младшего байта регистра 10, выход которого соединен с входом регистра 11. Вход демультиплексора 12 соединен с выходами старших битов байтов регистра 11 (биты 7, 15, 23, 31, 39, 47).

Работу схемы рассмотрим для случая передачи с транспонированием из блока памяти 2 в блок памяти 3. Байты очередной восьмерки байтов из блока 2 через мультиплексор 9 поступают в младший байт регистра 11 и с помощью сдвигов на 8 бит заполняют этот регистр. После этого содержимое регистра 10 передается в регистр 11, а в регистр 10 загружается следующая восьмерка байтов. Байт, сформированный из левых битов байтов регистра 11, через демультиплексор 12 передается в блок памяти 3, после чего выполняется сдвиг регистра 11 на 1 бит влево. Затем выводится следующий байт и т. д. Совмещение ввода и вывода позволяет выполнять транспонирование практически за то же время, что и обычный побайтовый обмен с задержкой на время загрузки одной восьмерки байтов.

Передача с транспонированием из блока памяти 3 в блок 2 выполняется аналогичным образом.

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

Литература:

1. Компьютеры на СБИС: Кн. 2. - Пер. с япон. - М.: Мир, 1988. Стр. 272.

2. Майерс Г. Архитектура современных ЭВМ: Кн. 2. - Пер. с англ. - М.: Мир,1985. Гл.19.

3. Озкарахан Э. Машины баз данных и управление базами данных. Пер. с англ. - М.: Мир, 1989, §5.2, 5.3, 6.3 (прототип, с.288, рис. 6.19).