Последната актуализация на този раздел е от 2020 година.

 

§ 4.4  Логическа структура на запомнящи устройства с асоциативен достъп - Associative Memory

 

 

      Практическите нужди са по-разнообразни от възможностите, които могат да предоставят разгледаните вече запомнящи устройства. На ред е да разгледаме структурата и функционирането на така наречените асоциативни запомнящи устройства.

      За да изясним смисъла на асоциативния достъп нека се спрем на основната задача на всяка информационна система, а именно търсене на информация в базата от данни, отговарящи на определен шаблон (признак). И по-конкретно - нека е необходим достъп в един масив от информация за хора, по тяхната възраст (например 25 години) и пол (например жени). Търсенето в масива от данни изявява онези негови елементи, които при сравнение с така зададените признаци и техните стойности, имат съответствие. В посочения пример, възрастта и полът се явяват признаци на данните. Достъпът до елементи от масива е разрешен само ако те имат предявените признаци, т.е. наистина се отнасят до жени на 25 год. Казаното може да се обобщи така: достъп получават онези клетки от паметта, чието съдържание в най-голяма степен съответства (прилича) на предявената на входа информация. Или още – достъп се получава до онези клетки, които успеят да осъществят асоциативна връзка със стойностите на входните признаци. Не бива да забравяме, че достъпът е необходим за да бъде изпълнена основна за запомнящото устройство операция – четене или запис на данни.

      Критерият на асоциативната връзка като степента на съответствие или още прилика, технически трудно получава стойност, тъй като понятия като “много прилича на … “, “малко прилича на …”, “това най-прилича на онова” и т.н. са твърде субективни и размити. Ето защо в техниката се работи с двете крайности – съвпадение и несъвпадение. Приема се, че ако два набора от данни съвпадат, те си приличат в максимална степен и обратно, ако не съвпадат – не си приличат. Така в асоциативното запомнящо устройство достъпът се основава на откритото съвпадение. Читателят вероятно вече усеща, че осъществяването на достъп до клетка от паметта е свързано със специфични предварителни действия, които се наричат асоциативно търсене, или още търсене по асоциативен признак. В резултат на това търсене, което по същество представлява сравнение на предявения на входа на ЗУ набор от признаци със съдържанието на всяка клетка от запомнящия му масив, изявилите се съвпадения маркират съответните клетки. Така маркираните като възможни за достъп клетки представляват резултата от асоциативното търсене. За съжаление този резултат не винаги е еднозначен и не винаги е възможен, откъдето следват проблеми с изпълнението на основните операции. По-долу на фигура 4.4.1 е представена обобщена логическа структура на асоциативно запомнящо устройство, в което ще разгледаме предложеното решение на току що споменатите проблеми.

 

Фиг. 4.4.1.  Логическа структура на асоциативно запомнящо структура

 

      Това, на което искаме да обърнем внимание веднага, е това, че в горната структура няма адресна шина. Самата логическата структура съдържа следните логически възли:

·         Запомнящ масив ЗМ от М на брой n-битови клетки ;

·         Регистър на асоциативния признак Рг.АПр – n-битов ;

·         Регистър на маската Рг.М – n-битов ;

·         Регистър на съвпаденията Рг.С – М-битов ;

·         Регистър на областта за търсене Рг.ОТ – М-битов ;

·         Схема за избор на първия срещнат СИ ;

·         Схема на вътрешното управление СВУ.

 

      Преди да се изпълни основна операция потребителят трябва да извърши инициализация на запомнящото устройство. В случая тя се свежда до зареждане със съответната информация на вътрешните регистри. В регистър Рг.АПр се зарежда асоциативния признак, който представлява n-битова двоична комбинация. Тази двоична комбинация може да бъде структурирана и да се интерпретира като набор от определени подполета (признаци). В този смисъл, всеки отделен бит от нея може да се интерпретира като самостоятелен двоичен признак. Всеки признак, независимо от разрядността му, има определен за потребителя смисъл. Ако за сравнение може да бъде използван всеки бит на асоциативния признак, то запомнящото устройство се нарича с пълна (произволна) асоциация, в противен случай то се нарича с частична асоциация.

      Актуалният за поредното асоциативно търсене асоциативен признак може да се структурира на второ ниво с помощта на маската, която потребителят подбира и зарежда в Рг.М. В зависимост от двоичните разряди, маската е в състояние да пропусне или не всеки отделен бит от асоциативния признак. Маскирането е поразрядна логическа конюнкция между едноименните битове на маската и асоциативния признак и по тази причина изходът на регистъра на маската в горната структура е подведен срещу този на Рг.АПр . Освен това маската се разпространява във вътрешността на запомнящия масив, където маскира съдържанието на всяка негова клетка. Това е необходимо, защото асоциативният признак и съдържанието на отделните клетки трябва да се подлагат на сравнение при еднакви условия. Маскираното съдържание на всяка отделна клетка се сравнява с маскирания асоциативен признак и в резултат се формира стойността на сигнала “Съвпадение”. Такъв сигнал генерира всяка клетка на запомнящия масив. Получените стойности на тези сигнали се записват в регистъра на съвпаденията Рг.С. Кодировката на тези сигнали е следната:

                                                        (4.4.1)

      Възможностите за съдържанието на регистъра на съвпаденията са три:

·         Съдържа само нули, което означава, че няма съвпадения. В този случай основната операция, която е заявена към запомнящото устройство се оказва невъзможна за изпълнение. Последствията от това зависят от конфигурацията, в която участва асоциативното запомнящо устройство;

·         Съдържа само една единица, което означава, че има само едно съвпадение. В този случай става достъпна клетката, генерирала съвпадението и заявената основна операция извършва трансфер на данни спрямо нея;

·         Съдържа няколко единици. Тази ситуация е най-сложна, тъй като възниква проблемът за избор. От всичките възможни за достъп клетки е необходимо да бъде избрана само една, в която да се извърши основната операция.Критериите, по които може да се извърши избор могат да бъдат различни, но обикновено се изхожда от предположението, че след като няколко клетки са подали сигнали за съвпадение, то най-вероятно е без значение коя от тях ще извърши трансфера на данни. Не е без значение и фактът, че това разбиране води до синтез на една от най-икономичните схеми за избор – схемата на първия срещнат.

      Изборът на клетка за извършване на трансфера може да се осъществи върху цялото съдържание на Рг.С, но логическата структура от фигура 4.4.1 предлага на потребителя допълнително удобство в лицето на регистъра на областта за търсене Рг.ОТ. Както се вижда от фигурата, съдържанието на този регистър маскира съдържанието на регистъра на съвпаденията, в резултат на което, схемата за избор СИ ще осъществи избор само върху пропуснатите от маската съвпадения. Маската се съставя от потребителя, който ако зареди този регистър само с единици ще означава, че желае търсене в целия запомнящ масив, а ако например зареди регистъра с редуващи се нула и единица ще означава, че желае търсене в клетки само с нечетни номера (1, 3, 5, и т.н.).

      Схемата за избор СИ, която има М входа и М изхода, може да се възприема като комбинационен преобразовател на входната комбинация в унитарен код (комбинация, съдържаща само една единица) по правилото първият срещнат или нито един. Изходните линии от схемата за избор се подават в качеството си на разрешаващи сигнали към запомнящия масив ЗМ. Тук специално следва да подчертаем, че запомнящият масив не е RAM памет, неговите клетки се разрешават от схемата за избор, а не от адресен дешифратор, както е в RAM паметта.

      Както вече обърнахме внимание по-горе, предварителните действия, които нарекохме асоциативно търсене, могат да имат и самостоятелно значение за определяне на състоянието на запомнящото устройство. В този смисъл като самостоятелна тази операция се нарича “Контрол на асоциацията”. Изпълнението на тази операция ще дава на потребителя не самите резултати от асоциативното търсене, а представа за състоянието на устройството при конкретния асоциативен призна и конкретната маска, по което може да се съди за съдбата на бъдещата основна операция. Основните признаци (флагове) за състоянието на ЗУ могат да бъдат разпознати чрез следните логически функции:

1.       F0 – сигнал за отсъствие на думи в ЗМ, които удовлетворяват условията на търсенето:

                                                                  (4.4.2)

2.       F1 – сигнал за наличие на едно съвпадение:

            (4.4.3)

3.       F2 – сигнал за наличие на повече от едно съвпадения:

                                                                   (4.4.4)

      Операцията контрол на асоциацията може да има две разновидности:

·         "Асоциативен контрол на съвпаденията"  и ;

·         "Асоциативен контрол на несъвпаденията".

      Операцията с контрол на несъвпаденията е алтернативна на операцията с контрол на съвпаденията. При нея функциите (4.4.1) се формират с инверсия, т.е. с други думи, ако са изчислени функциите на съвпаденията, може да се твърди, че в същото време е изпълнена асоциацията на несъвпадение. Съответно са възможни операции "Четене" и "Запис" с търсене на съвпадение и операции "Четене" или "Запис" с търсене на несъвпадение.

      Възможни за дефиниране са и други допълнителни операции в помощ на основните. Например операция "Изчистване" изпълнява едновременно нулиране на всички клетки на запомнящото устройство. Операция "Маркировка" извършва едновременно установяване на битовете на заетост на всички клетки. Битът на заетост е допълнителен разряд на всяка клетка и показва дали тя е свободна или заета с активни данни. При наличието на такъв бит алгоритъмът на операция "Запис" е следния: най-напред се открива свободна клетка. За целта се изпълнява операция контрол на асоциацията по специален асоциативен признак, показващ статута на клетката. Ако няма свободни клетки, операцията се отменя поради невъзможност да бъде изпълнена. В останалите случаи тя се изпълнява в избраната клетка, която променя своя статут, като се маркира като заета.

      Чрез операцията "Контрол на асоциацията" е възможно да бъде определен броят на думите в паметта, които удовлетворяват асоциативния признак, без при това да се извличат от клетките техните съдържания, както това би се реализирало във всяко друго запомнящо устройство. На тази основа могат да бъдат реализирани различни задачи, като например получаване отговор на въпроса: Колко са жените на 25 години в целия масив от данни ?

      Ако запомнящите клетки в асоциативното запомнящо устройство се оборудват със съответните комбинационни схеми, в асоциативната памет могат да бъдат изпълнени редица сложни логически обработки на информацията, които обикновено ще изискват определена програмна реализация. Такива обработки могат да бъдат например намирането на максималното (или минималното) число, намиращо се в паметта; намиране на число по-голямо (или по-малко) от дадено число; намиране на всички числа затворени в даден интервал и др., които ще бъдат разгледани тук по-късно. За разлика от паметта с последователен достъп, асоциативната памет при четене не разрушава съдържанието на клетките и то може да бъде четено многократно.

      Ще се спрем на логическия синтез на функцията съвпадение. Логиката на тази функция се определя от (4.4.1), а нейни аргументи са асоциативният признак АП, маската М и съдържанието на клетката от запомнящия масив Q. Всички аргументи са многоразрядни комбинации, което ни дава право да синтезираме тази функция във вид на конюнкцията:

                                                       (4.4.5)

където

са функции на поразрядните съвпадения.

      От своя страна поразрядните съвпадения се представят чрез следната таблица на истинност:

 

АПj

Mj

Qi,j

ci,j

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

 

      От таблицата се вижда, че съвпадение има винаги, когато маската е нула, а в противен случай само ако  АПj=Qi,j.

      След минимизация получаваме следната поразрядна функция:

                                     (4.4.6)

      Обобщавайки получения израз в смисъла на (4.4.5) можем да запишем логическата функция на всяко съвпадение по следния начин:

                                    (4.4.7)

      След синтеза на логическите функции можем да представим логическите схеми на запомнящия елемент и запомнящия масив на асоциативното запомнящо устройство.

 

Фиг. 4.4.2.  Примерна схема на асоциативен запомнящ елемент

 

      В схемата на запомнящия елемент не са показани данновите линии, разрешаващите линии и управляващите линии, които са подобни на тези в запомнящия елемент на RAM паметта например (вижте фигура 4.2.3).

 

Фиг. 4.4.3.  АЗУ с организация 4х4

 

      Както се вижда, уравнение (4.4.5) е реализирано чрез подхода на разпределената логика, което позволява лесно нарастване на размера на клетката. В схемата от фигура 4.4.3 не са показани регистъра за фиксиране на съвпаденията и регистъра на областта за търсене, както и входно-изходните даннови връзки и тяхното управление. Те са пропуснати умишлено, с цел опростяване на схемата, което считаме, че не затруднява читателя, тъй като данновите и разрешаващите връзки са били изобразявани в схемите на предидущи запомнящи устройства, разгледани от нас.

      Схемата за избор има тенденция да се усложнява с нарастване на броя на клетките в АЗУ, но тя лесно може да се реализира на каскаден принцип, което оставяме като задача на читателя.

      Схемата за избор, описана по-горе, има своите алтернативни решения, които ще бъдат разгледани по-късно, във връзка с използването на асоциативното запомнящо устройство като буферно.

      АЗУ, притежаващо възможността да изпълнява множество логически операции, основаващи се различни операции от вида контрол на асоциацията, се превръща в скъпо струваща система, неизгодна за апаратна реализация в големи обеми. Основното достойнство на това устройство е високата скорост на изпълнение на тези операции, която се дължи на апаратния паралелизъм по целия обем на запомнящия масив. Асоциативно запомнящо устройство с голям обем на запомнящия масив може да се построи с известни компромиси (ще бъдат разгледани по-късно) на базата на памет с произволен достъп.

 

 

 

Следващият раздел е:

 

4.4.1  Асоциативни операции – Associative Operations