Базовая структура пословно организованного ассоциативного процессора

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

Итак, параллельность, одновременность в работе — неотъемлемое свойство ассоциативной памяти, что можно пояснить следующим образом:

§ имеется большое число элементов памяти (в примере с кинотеатром — большое число мест);

§ поиск идет по всем элементам сразу (в примере — путем объявления по радио).

Ассоциативным процессором (АП) называют ассоциативное запоминающее устройство, дополненное логикой и микропрограммным управлением [2].

На рисунке 2.15 изображена структура пословно организованного АП. В основе архитектур ассоциативных процессоров с пословной организацией лежит параллелизм на уровне слов, и в большинстве конфигураций обработка слов выполняется последовательно по разрядам. Множество слов образует ассоциативный массив или ассоциативное запоминающее устройство (АЗУ) пословно организованного ассоциативного процессора. Соответственно имеется по одному процессорному элементу (ПЭ) на каждое слово, так что весь разрядный срез может обрабатываться параллельно.

Базовая структура пословно организованного АП содержит следующие подсистемы:

· массив ассоциативной памяти;

· регистр компаранда (компаранд – признак, по которому ведется поиск в АЗУ; он записывается в регистр компарандов, затем пересылается в регистр маски);

· регистр маски (выделяет указанный признак, остальные маскирует);

· регистры хранения ответов;

· регистры (буфер) ввода-вывода АЗУ;

· маска (буфер) вывода слов (последовательно по словам выводит содержимое АЗУ);

· соединительная сеть (используется для логической комбинации полей в данной физической среде);

· контроллер (управляет рассмотренными подсистемами).

 

 

Рисунок 2.16 - Базовая структура пословно организованного

ассоциативного процессора

 

Массив ассоциативной памяти. Этот массив содержит т n -разрядных слов. При нечисловой обработке такая запоминающая матрица размером т x n является удобной средой для отображения двумерных логических структур, таких, как матрицы, файлы и отношения. Каждая строка матрицы, каждая запись файла или каждый кортеж отношения соответствует слову ассоциативного массива. Хотя в таких структурах и допускается переполнение с переносом в следующие слова, типичная характеристика этих систем состоит в том, что каждое слово массива предназначается для одной строки, записи или кортежа соответствующих структур. Это объясняется несколькими причинами. Одной из них являются физические ограничения реализации, связанные с длиной слов. Начиная с некоторой длины слова, в аппаратуре возникает проблема шумов. Другая причина состоит в том, что периферийная аппаратура поиска массива ассоциативной памяти может выполнять одновременно лишь один поиск, если не вводить дорогостоящего дублирующего оборудования.

Другая характеристика этих процессоров состоит в том, что, поскольку операции выполняются в них пословно и поразрядно, они требуют высокой скорости чтения и записи. Это в свою очередь обусловливает выбор в качестве памяти статических запоминающих устройств вместо более медленных, хотя и более емких динамических. С этим типом памяти совместимы слова длиной 256, 1024 и даже 4096 бит (одна ячейка машины баз данных RAP.3 содержит основную память емкостью 2 Мбайт; ячейка в данном случае соответствует отдельному слову АП). При горизонтальных размерах такого порядка требуется вертикальный размер (или параллелизм по словам), соответствующий кардинальному числу (т.е. числу записей файла или кортежей отношения) хранимой в них структуры. Чтобы выполнить соединение двух отношений, каждое из которых содержит 100000 кортежей, потребовался бы 218 АП, имеющий АЗУ емкостью 200000 слов. Но до сих пор ни разу не строились и даже не предлагались машины такого размера [6].

Регистр компаранда. В массиве АЗУ могут выполняться различные комбинации операций поиска. Это означает, что можно сравнивать некоторое внешнее значение со всеми словами, хранимыми в АЗУ; можно сравнивать друг с другом два поля во всех словах; наконец, можно сравнивать некоторое поле выбранного слова с полями всех других слов. Но во всех этих случаях компаранд должен быть сначала введен в регистр компаранда, чтобы выполнить массовое сравнение (или сравнение типа SIMD), в котором одно значение сравнивается параллельно со множеством значений. При параллельном сравнении двух полей во всех словах имеет место параллелизм другого типа, и самый эффективный способ этого сравнения состоит в выполнении логической операции или операции вычитания между двумя полями в каждом слове, так что конечный результат является искомым результатом сравнения. Таким образом, хотя данные, т.е. компаранды, в каждом слове различны, операция выполняется параллельно по словам и последовательно по разрядным срезам. Длина регистра компаранда соответствует длине слова АЗУ. В типичном режиме сравнения позиции разрядов компаранда, маски и слов АЗУ соответствуют друг другу. В общем случае в таком соответствии нет необходимости, поскольку можно направить некоторое поле компаранда для сравнения с полем, расположенным в другой области АЗУ..

Регистр маски. Регистр маски можно рассматривать как простой фильтр или селектор разрядов регистра компаранда. С помощью регистра маски указывается поле регистра компаранда, которое служит действительным компарандом. Все разряды, не входящие в указанный компаранд, маскируются (т.е. соответствующие разряды регистра маски устанавливаются в 0), в то время как разряды, соответствующие полю компаранда, устанавливаются в 1.

Регистры хранения ответов. Обычно каждый регистр хранения ответов представляет собой множество триггеров, образующее одноразрядный двоичный вектор вдоль всего массива АЗУ. Один из этих регистров называется регистром меток (тегов] или отклика и служит для индикации или хранения результатов операций над массивом. Выделенное слово АЗУ, т.е. слово, отмеченное единицей в регистре меток, обычно индицирует успешное окончание поиска или хранит результат логической операции (например, перенос в текущем шаге операции сложения). Второй регистр памяти ответов используется как временная рабочая область (или сверхоперативная память) при обработке данных или реализации логических функций. Третий регистр памяти ответов служит для выбора слов. Он указывает для каждого слова АЗУ, участвует ли оно в подлежащей выполнению операции. Если, например, в массиве АЗУ хранятся файлы А и В и мы хотим выполнить некоторую операцию над одним из этих файлов, то необходимо запретить обработку всех слов другого файла путем установки в 0 всех разрядов регистра выбора слов, соответствующих второму файлу.

Регистры (или буфер) ввода-вывода АЗУ. Эти регистры играют роль буфера при передаче данных в АЗУ или из него. Манипулирование данными может относиться к одному слову или распространяться на весь массив. Последнее происходит обычно при загрузке и разгрузке АЗУ. В этом случае самое важное — выполнить эту операцию как можно быстрее. В самом деле, поскольку объем АЗУ относительно небольшой по сравнению с объемом подлежащих обработке данных, такие операции потребуется выполнять очень часто, и при этом массив АЗУ не должен долго бездействовать в ожидании ввода и вывода данных. Поэтому используются специальные интерфейсы ввода-вывода, такие, как диски с фиксированными головками и барабаны, в которых каждая головка (т.е. тракт) предназначается для одного слова АЗУ. Если массив АЗУ состоит из 256 слов, такой интерфейс обеспечивает параллельный канал шириной 256 бит, имеющий полосу пропускания в 256/8 = 32 раза большую, чем полоса стандартного последовательного по байтам канала ввода-вывода.

Маска (буфер) вывода слов. Этот буфер используется для последовательного по словам вывода содержимого АЗУ. Возможность маскирования позволяет выбирать отдельные поля по тому же принципу, что и в регистре маски.

Соединительная сеть. В рассматриваемом классе ассоциативных процессоров соединительная сеть используется для логических комбинаций полей в данной физической среде, чтобы можно было выполнить требуемые операции. Иначе говоря, соединительная сеть эмулирует на двумерном массиве АЗУ более сложные виды межпроцессорных соединений. Например, при обработке изображений или геометрических фигур возможна работа с сеточными структурами, где необходимо соединение каждого элементами с четырьмя ближайшими соседями. Может потребоваться также сеть «идеальной тасовки» для сортировки, вычисления полиномов и т. д.

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