Ассоциативные вычислительные машины

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

SELECT имя FROM сотрудники WHERE возраст < 30 AND зарплата > 10000.

Здесь имена служащих выбираются из базы данных не по адресу, а по содержимому полей "возраст" и "зарплата". Этот способ адресации называется ассоциативной адресацией.

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

В ассоциативных вычислительных машинах ассоциативная адресация реализуется с помощью ассоциативного запоминающего устройства (АЗУ) – см. рис. 3, где РгАП - регистр ассоциативных признаков; РгМ - регистр маски; РгИА - регистр индикаторов адреса. В АЗУ могут быть и другие элементы, наличие и функции которых определяются способом использования АЗУ.

Рис. 3. Структура ассоциативного запоминающего устройства.

Выборка информации из ассоциативного запоминающего устройства происходит по следующей схеме (принято, что разрядность ячеек запоминающего массива равна m и в исходном состоянии все разряды регистра индикаторов адреса имеют значение «1»).

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

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

3. Производится сравнение содержимого первого разряда всех ячеек запоминающего массива с содержимым первого разряда маскированного вектора признаков. Если содержимое первого разряда ячейки с номером не совпадает с содержимым первого разряда регистра ассоциативных признаков, то соответствующий этой ячейке разряд регистра индикаторов адреса устанавливается в состояние «0».

4. Аналогично производится сравнение второго разряда всех ячеек запоминающего массива с содержимым второго разряда регистра ассоциативных признаков. И т.д. до исчерпания всех разрядов. В результате в регистре индикаторов адреса в состоянии «1» останутся те разряды, которые соответствуют ячейкам запоминающего массива, содержащим информацию, совпадающую с записанной в маскированном векторе признаков.

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

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

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

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

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

Наиболее характерным представителем группы ассоциативных вычислительных машин является система STARAN (США). В отличие от рассмотренной выше схемы ассоциативной памяти, ассоциативная память STARAN является ассоциативной памятью с многомерным доступом , т. е. в нее можно обратиться как поразрядно, так и пословно. Каждому слову памяти в системе соответствует процессорный элемент.