9.3.1. Організація та типи пам'яті з асоціативним доступом

Пам'ять з асоціативним доступом (або асоціативна пам'ять) широко використову­ється в сучасних комп'ютерах. У першу чергу за принципом пам'яті з асоціативним до­ступом побудовано запам'ятовуючі пристрої кеш пам'яті більшості комп'ютерів. Крім того, за принципами пам'яті з асоціативним доступом побудовано буферну пам'ять в конвеєрних процесорах, зокрема це буфер попередньої вибірки команд, буфер впоряд­кування і т. д. Асоціативна пам'ять ефективна також для побудови пристроїв для вико­нання операцій числового пошуку (min, max, сортування і т. д.).

Пам'ять з асоціативним доступом передбачає зберігання разом із даними і їх ознаки, в ролі якої може бути і саме дане. Дані вибираються з такої пам'яті на основі збігу їх ознак із заданою. Тому цю пам'ять іще називають пам'яттю, що адресується за вмістом або за да­ними. Ядро пам'яті з асоціативним доступом приведене на рис. 9.7. На рис. 9.15 приведена детальніша структура одного з варіантів побудови пам'яті з асоціативним доступом.

322

Ця пам'ять включає:

• масив регістрів для зберігання N m-розрядних слів, в кожному з яких частина розрядів зайнята ознаками, а іншу частину розрядів займає службова інформація;

• регістр асоціативної ознаки, куди поміщається код шуканої інформації (ознака пошуку). Розрядність цього регістра зазвичай є меншою чи рівною довжині слова п;

• схему порівняння на збіжність, яка використовується для проведення паралель­ного або послідовного порівняння бітів ознак пошуку всіх слів, що зберігаються, з від­повідними бітами асоціативної ознаки пошуку, і вироблення сигналів збігу;

• регістр збігів, в якому кожному регістру масиву пам'яті відповідає один розряд, в який заноситься одиниця, якщо всі розряди ознаки слова відповідного регістра спів­пали з однойменними розрядами асоціативної ознаки пошуку;

• регістр маски, який дозволяє заборонити порівняння певних бітів;

• пристрій керування, який на основі зовнішніх сигналів керування здійснює за­пис асоціативної ознаки пошуку до відповідного регістра, встановлює маску в регістрі маски, та на основі даних порівняння на збіжність з регістра збігів здійснює зчитування даних із регістрів асоціативної пам'яті, а також запис до них вхідних даних.

При зверненні до пам'яті з асоціативним доступом, спочатку сигналами з блоку ке­рування розряди регістра маски, які не повинні враховуватися при пошуку інформа­ції, встановлюються в нульові значення, і всі розряди регістра збігів встановлюються в одиничний стан. Після цього в регістр асоціативної ознаки заноситься код шуканої інформації (ознака пошуку) і починається її пошук, в процесі якого схема порівняння на збіжність одночасно порівнює перший біт ознак даних всіх регістрів пам'яті, з першим бітом асоціативної ознаки пошуку. Ті схеми, які зафіксували неспівпадіння, формують сигнал, що переводить відповідний біт регістра збігів у нульовий стан. Так само відбува­ється процес пошуку і для решти незамаскованих бітів ознаки пошуку.

323

У результаті, одиниці зберігаються лише в тих розрядах регістра збігів, які відповіда­ють регістрам, де знаходиться шукана інформація. Конфігурація одиниць в регістрі збі­гів використовується в якості адрес, за якими проводиться зчитування даних із пам'яті.

Внаслідок того, що результати пошуку можуть мати кілька варіантів, вміст регістра збігів подається на пристрій керування, де формуються сигнали сповіщення про резуль­тати порівняння, а саме про те, що шукана інформація не знайдена, міститься в одному чи кількох регістрах. Тому, при зчитуванні спочатку проводиться аналіз результатів по­рівняння. Потім, при наявності інформації про те, що шукана інформація не знайдена, зчитування відміняється, при повідомленні, що шукана інформація міститься в одному регістрі, зчитується слово, на яке вказує одиниця в регістрі збігів, а при повідомленні, що шукана інформація міститься в кількох регістрах, скидається найстарша одиниця в регістрі збігів і витягується відповідне їй слово. Шляхом повторення цієї операції по­слідовно зчитуються всі слова.

Запис у пам'ять з асоціативним доступом проводиться без вказівки конкретної адре­си, в перший вільний регістр. Для пошуку вільного регістра виконується операція зчи­тування, в якій не замасковані тільки службові розряди, що показують, як давно прово­дилося звернення до кожного регістра, і вільним вважається або порожній регістр, або той, який найдовше не використовувався.

Головна перевага пам'яті з асоціативним доступом визначається тим, що час пошуку інформації залежить тільки від числа розрядів в ознаці пошуку і швидкості опиту роз­рядів, і не залежить від числа регістрів пам'яті.

Разом з тим, ця пам'ять також має ряд недоліків, до основних з яких слід віднести наступні:

• Необхідність двократного звернення до однієї комірки пам'яті при записі і при зчитуванні числа в два рази сповільнює взаємодію пристроїв комп'ютера з пам'яттю з асоціативним доступом в порівнянні з варіантом пам'яті, в якій можливе лише одне звернення.

• Ця пам'ять має досить складну організацію, яка вимагає забезпечення доступу до кожної комірки з входу та виходу пам'яті або з об'єднаного входу-виходу пам'яті, причому при зчитуванні необхідно проводити порівняння заданої ознаки з ознаками даних в регістрах пам'яті, а також забезпечити пошук даних, ознаки яких співпали із за­даною. Це вимагає великих затрат на елементи доступу та сповільнює роботу пам'яті.

• При створенні на основі пам'яті з асоціативним доступом багатоканальної (ба-гатопортової) пам'яті необхідно забезпечувати одночасний доступ із кожного каналу до кожної комірки пам'яті, з одночасним порівнянням всіх ознак у комірках із шуканими ознаками, а також забезпечити пошук даних, ознаки яких співпали із заданою, що є про­блематичним завданням, особливо при великих об'ємах пам'яті.

Базуючись на концепції асоціативного пошуку можна побудувати цілу низку струк­тур пам'яті з асоціативним доступом. Конкретна структура визначається тим, як поєд­нані наступні чотири основні елементи її організації:

• вид пошуку інформації;

• спосіб зчитування інформації при множинних збігах;

• спосіб запису інформації;

• варіант порівняння ознак.

324

У кожному конкретному Застосуванні пам'яті з асоціативним доступом завдання по­шуку інформації може формулюватися по різному.

При простому пошуку, який був розглянутий вище, потрібен повний збіг всіх розрядів ознаки пошуку з однойменними розрядами ознак слів, що зберігаються в регістрах пам'яті.

При складному пошуку можуть ставитись наступні завдання:

■ Пошуку слів із максимальним або мінімальним значенням ознаки. При цьому бага­ тократна вибірка з пам'яті слова з максимальним або мінімальним значенням ознаки (з вик­ люченням його з подальшого пошуку), по суті, є впорядкованою вибіркою інформації.

■ Пошук слів, ознака яких порівняно з асоціативною ознакою пошуку є найближ­чим більшим або меншим значенням. Ця операція також забезпечує проведення впо­рядкованої вибірки інформації.

■ Знаходження слів, чисельне значення ознаки в яких є більшим або меншим за­ даної величини. Подібний підхід дозволяє вести пошук слів з ознаками, що лежать все­ редині або поза заданими межами.

Очевидно, що реалізація складних методів пошуку вимагає внесення відповідних змін у структуру пам'яті з асоціативним доступом.

Важливим питанням є організація зчитування з пам'яті з асоціативним доступом інформації, коли з асоціативною ознакою пошуку співпадають ознаки декількох слів. У цьому випадку застосовується один із двох підходів: використовується ланцюг черговос­ті або проводиться опитування. Використання ланцюга черговості дозволяє проводити зчитування слів у порядку зростання номера регістра пам'яті незалежно від величини асоціативних ознак. При проведенні опитувань впорядковуються ті розряди, які були замасковані, і не брали участі в пошуку. В іншому варіанті для цих цілей виділяються спеціальні розряди регістрів.

Істотні відмінності в структурі пам'яті з асоціативним доступом можуть бути пов'я­зані з вибраним принципом запису інформації. Раніше був описаний варіант із записом у незайнятий регістр з найменшим номером. На практиці застосовуються й інші спо­соби, наприклад, за співпадінням ознак, за чергою та інші. Найскладнішим є запис із сортуванням інформації на вході пам'яті з асоціативним доступом за величиною озна­ки слова. Тут місцеположення регістра, куди буде поміщене нове слово, залежить від співвідношення ознаки записуваного слова і ознак слів, що вже зберігаються в пам'яті з асоціативним доступом.

При побудові пам'яті з асоціативним доступом вибирають один з чотирьох варіан­тів порівняння ознак, тобто організації перегляду вмісту пам'яті: паралельно за всіма словами, послідовно за всіма словами, паралельно за всіма розрядами, послідовно за всі­ма розрядами. Ці варіанти можуть комбінуватися. Названі чотири варіанти порівнян­ня ознак визначають принципи побудови схеми порівняння на збіжність. Відповідно до цих принципів, може бути запропоновано кілька типів організації пам'яті з асоціа­тивним доступом. У пам'яті з повним паралельним асоціативним доступом одночасно порівнюються всі розряди ознак всіх слів пам'яті (так званий одночасний пошук по сло­ву). Це найшвидша та найскладніша з точки зору затрат обладнання структура пам'яті з асоціативним доступом. Можливе порівняння не всіх розрядів ознак слів пам'яті, а по частинах, аж до порозрядного порівняння, коли одночасно порівнюються з бітом асоці­ативної ознаки пошуку по одному біту ознаки кожного слова (так званий порозрядний

325

пошук). Це буде структура пам'яті з неповним паралельним асоціативним доступом та з послідовною обробкою розрядів ознак слів. Можливе також проведення порівняння одночасно ознак не всіх слів, а по групах. Тоді це буде структура пам'яті з послідовним асоціативним доступом із порозрядним та паралельним порівнянням.

Розглянемо названі чотири основні типи організації пам'яті з асоціативним досту­пом детальніше.