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

ЗМІСТ

ВСТУП………………………………………………………….………….… 3

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

2. Пам'ять з повним паралельним асоціативним доступом ………………. 9

3. Пам'ять з неповним паралельним асоціативним доступом………… …..10

4. Пам'ять з послідовним асоціативним доступом……………………….... 11

5. Пам'ять з частково асоціативним доступом ……………………………...12

ВИСНОВКИ………………………………………………………..………… 14

ЛІТЕРАТУРА………………………………………………............................ 15

ВСТУП

Пам'ять з асоціативним доступом (асоціативна пам'ять) широко використовується в сучасних комп'ютерах. Даній темі присвячено ряд робiт вiтчизняних та закордонних вчених. Найбільш вагомий внесок зробили А. Мельник, В. В. Воєводін, Б. А. Головкін, К. Дж. Тербер, P. Agrawal, V. Janakiram, G. Pathak та інші.

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

Мета задачi: виходячи з актуальності теми, метою дослідження є комплексна оцінка організації пам'яті з асоціативним доступом.

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

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

Пам'ять з асоціативним доступом включає:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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