-
Ассоциативная память. Реализация и использование. В виде алгоритма / программы написать хэш-функцию хранения сильно разреженной 2d матрицы.
Ассоциативная память – это безадресная память, в которой поиск информации производится по ее ассоциативному признаку.
В ассоциативных запоминающих устройствах в регистр маски записывается слово, разрешающее запрос по всем или только по некоторым разрядам ассоциативного признака, применение маски позволяет сократить или расширить область поиска.
Реализация и использование.
Поиск информации производится параллельно по всем ячейкам путем сравнения запроса с ассоциативным признаком каждой ячейки.
Результат поиска формирует специальная комбинационная схема, вырабатывающая сигналы, оповещающие об отсутствии слов, удовлетворяющих условиям поиска, о наличии только одного слова, о наличии нескольких слов, имеющих такой ассоциативный признак.
После формирования и обработки оповещающих сигналов схемой управления производится считывание необходимой информации. При записи отыскивается свободная ячейка по значению разряда занятости, в первую найденную свободную ячейку записывается информация.
Проверка разряда занятости производится по установке n-го разряда (разряда занятости) маски. При использовании дополнительных комбинационных схем в ассоциативной памяти можно выполнять различные логические операции, определяя максимальное или минимальное число, количество слов, имеющих одинаковый ассоциативный признак и т.д.
Ячейки памяти ассоциативного запоминающего устройства должны быть элементами статической памяти, в ассоциативной памяти обращение производится ко всем ячейкам одновременно и не должно прерываться циклами регенерации.
Ассоциативная память наиболее быстродействующая, но очень дорогая, так как требует введения дополнительно схемы сравнения, позволяющей осуществить поиск, для каждой ячейки памяти. Поэтому такая память обычно не используется в чистом виде, а быстродействующие устройства памяти типа «кэш» обычно выполняются как частично ассоциативные.
В микропроцессорах, например, ассоциативная память (память с выборкой по содержанию) используются в составе кэш-памяти для хранения адресной части команд и операндов исполняемой программы. При этом нет необходимости обращаться к ОЗУ за следующей командой или требуемым операндом, достаточно поместить в регистр ассоциативного признака необходимый адрес и, если искомая информация имеется в кэш памяти, то она сразу будет выдана. Обращение к оперативной памяти будет необходимо лишь при отсутствии требуемой информации в кэш. За счет такого использования кэш сокращается число обращений к ОЗУ, а это позволяет экономить время, так как обращение к кэш требует приблизительно в 10 раз меньше времени, чем обращение к ОЗУ.
В виде алгоритма / программы написать хэш-функцию хранения сильно разреженной 2D матрицы.
Для больших сильно разряженных матриц экономия памяти является очень актуальной проблемой. С такими матрицами можно работать, используя квадратичное повторное хэширование.
Алгоритм:
-
определение максимального размера хэш-таблицы (M) для хранения разряженного массива (значение зависит от максимально возможного количества ненулевых элементов), но не менее
где n
– простое число; -
задание
-
вычисление ключа доступа к элементу хэш-таблицы (хэш-адреса) через пару индексов (i,j), где
по одной из формул:
-
если ячейка свободна или ключ элемента в ней совпадает с исходным ключом, то завершение процесса поиска. Иначе
-
вычисление
-
если
то переход к шагу 4. Иначе (
)
таблица полностью заполнена.