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

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

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

1. Асоциативни операции върху числа

Към асоциативните операции върху числа, изпълнявани паралелно във всяка клетка на запомнящото устройство, се отнасят операциите за проверка на отношение: равно; по-малко; по-голямо; между. Формулирани като отделни изпълними в АЗУ операции, те се наричат:

· "Асоциативно търсене на по-голямо" ;

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

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

· "Асоциативно търсене на минимално" ;

· "Асоциативно търсене в интервал (между)" ;

· "Асоциативно търсене на следващото по-голямо” ;

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

За организиране на тези операции в логическата структура на АЗУ, освен показаните на фигура 4.4.1 логически възли, са необходими още няколко допълнителни такива. Необходимостта от тези възли се обосновава със съответните алгоритми, които ще бъдат разгледани по-долу. Тези възли са:

1. Допълнителни регистри за маски на паметта Рг.М1 и Рг.М2, имащи дължината на асоциативния признак, т.е. те са n-разрядни ;

2. Специални регистри за маски Рг.М3 и Рг.М4, имащи същата дължина, т.е. n-разрядни ;

3. Допълнителен регистър за асоциативния признак Рг.А, с дължината на асоциативния признак, т.е. n-разряден;

4. Двоичен брояч за организиране на цикли Бр.Ц, чиято дължина се определя от формулата

чийто аргумент М е обемът на запомнящия масив на АЗУ ;

5. Тригер Трг.EQ за назначаване (стартиране) на операция "Контрол на асоциацията за съвпадение" и на операция "Контрол на асоциацията за несъвпадение".

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

A) Операции “Асоциативно търсене на по-голямо (по-малко)”

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

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

Тук са изразени съвместени и текстово алгоритмичните последователности за проверка на двете отношения - по-голямо и алтернативното по-малко:

1. Извършва се последователна (циклична) проверка на разрядите на аргумента отляво надясно (от старшите към младшите) до срещане на цифра нула (единица), която се нарича целева ;

2. Образува се нов аргумент, в който целевият бит е заменен с обратната си стойност - единица (нула) ;

3. Образува се нова маска, която маскира всички разряди на аргумента, стоящи отдясно на целевия разряд.

Изказаното може да се изрази чрез следната схема:

4. Изпълнява се операция контрол на асоциацията по новия асоциативен признак (аргумент) и всички получени в запомнящия масив съвпадения се фиксират в регистъра на съвпаденията Рг.С (вижте фигура 4.4.1) ;

5. Възстановява се първоначалната стойност в целевия разряд - нула (единица) ;

6. Повтарят се действията от пункт 1., при което за целеви разряд се избира онзи със следващата по-младша нула (единица). Запазвайки разрядите на аргумента, стоящи отляво на новия целеви бит, с подходяща маска (пункт 3), се повтарят действията от пункт 2. до пункт 5 ;

7. Описаният в горния пункт цикъл завършва след анализ и на най-младшия разряд на аргумента. В резултат на тези действия всички думи в запомнящия масив, които удовлетворяват отношението по-голямо (по-малко) са вече отбелязани с единица в регистъра на съвпаденията Рг.С.

На следващата фигура 4.4.1.1 е представена блок-схемата на микропрограмата (алгоритъма) на операция "Асоциативно търсене на по-голямо".

Фиг. 4.4.1.1. Микропрограма на операция "Асоциативно търсене на по-голямо"

В самото начало се предполага, че асоциативният признак (числото, с което ще се сравнява съдържанието на всяка клетка) и маската са записани във входните регистри на АЗУ. Логично е да се разбира, че маската М в този случай трябва да бъде съставена само от единици - (Рг.М)=111...11. Но маската може да бъде и друга, т.е. да съдържа и нулеви битове, с което от изходното число могат да се формират други по-малки стойности.

В брояча на циклите Бр.Ц се зарежда числото n, което изразява броя на разрядите на аргумента и на клетките в запомнящия масив. Регистрите на специалните маски се установяват в състояние минус 0, т.е. (1000…00) единица в най-левия разряд и нули във всички останали разряди.

Ако съдържанието в старшия (n-1)-ви разряд на аргумента, съвпада с инверсията на съдържанието в едноименния разряд на маската М2, то този разряд е целеви. В зависимост от това, колко пъти се повтарят действията в тялото на цикъла, може да се определи номера на всеки целеви разряд.

След обработване на открития целеви разряд, или ако текущият не е целеви, се попада в общия клон на тялото на цикъла, където се извършва циклическо изместване (ротация) на маската М2 и аргумента А. С новата стойност на маската М2 се търси следващият целеви разряд.

Ако анализираният текущ бит е целеви, чрез поразрядната дизюнкция на аргумента и маската М3 се постига инвертиране на стойността на целевия бит. Специалната маска М3 се измества в регистър Рг.М3 логически надясно на един разряд при всяко повторение на тялото на цикъла.

Новата маска М се получава според пункт 3 с помощта на специалната маска М4, която извлича старшите разряди на маската М1 чрез поразрядната им конюнкция. Регистърът на специалната маска Рг.М4 измества своето съдържание надясно аритметически.

Операцията контрол на асоциацията по новия асоциативен признак според пункт 4, се стартира със запис на единица в тригер Трг.EQ. В резултат на тази операция, в регистъра на съвпаденията Рг.С се фиксират резултатите от текущото асоциативно търсене, при което обаче новополучените несъвпадения не бива да разрушават запомнените на предидущите моменти съвпадения. От това следва да се направи извода, че съдържанието на регистъра на съвпаденията е функция както от входните сигнали, така и от само себе си.

Възстановяването на стойността на целевия разряд според пункт 5 се постига чрез поразрядната конюнкция с отрицанието на маската в Рг.М3.

Процесът се повтаря толкова пъти, колкото са разрядите на аргумента и клетките. След излизане от цикъла, в регистъра на съвпаденията са отбелязани всички думи, за които е установено търсеното отношение. Отново трябва да се обърне внимание на това, че не всички верни отношения се установяват едновременно, т.е. тези които са установени първи, в началните проходи на цикъла, следва да се съхраняват до края.

Алгоритъмът завършва с установяване на асоциативния признак и маската в Рг.АП и Рг.М.

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

Б) Операция “Асоциативно търсене в интервал (между)”

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

Като се имат в предвид алгоритмите, представени съвместно чрез последователността на пункт А), не е трудно да се дефинира следният алгоритъм за операция "Асоциативно търсене в интервал":

1. Записва се долната граница на интервала (R) в регистъра на асоциативния признак Рг.АП, в качеството й на аргумент ;

2. Изпълнява се операция "Асоциативно търсене на по-голямо". В резултат на тази операция, в регистъра на съвпаденията Рг.С се получават единици, които маркират онези клетки от запомнящия масив на АЗУ, чието съдържание е число по-голямо от показания аргумент R ;

3. Полученото в Рг.С съдържание се изпраща в регистъра на областта за търсене Рг.ОТ, за временно съхранение. Освен това съдържанието на Рг.ОТ от този момент нататък може да се използва за ограничаване на множеството клетки при изпълнението на следващата асоциативна операция ;

4. Записва се горната граница на интервала (Q) в регистъра на асоциативния признак Рг.АП, в качеството й на нов аргумент за следващата операция ;

5. Изпълнява се операция "Асоциативно търсене на по-малко". Тази операция се изпълнява по отношение на всички клетки на АЗУ (или само на разрешените), като в резултат на нея в регистъра на съвпаденията Рг.С се отбелязват с единица всички числа по-малки от Q ;

6. Изпълнява се поразрядна конюнкция между съдържанието на регистъра на съвпаденията и регистъра на областта за търсене

Рг.С := (Рг.С) Ç (Рг.ОТ) ,

при което в Рг.С остават единиците само в онези разряди, които съответствуват на клетки, чието съдържание е число, лежащо в интервала (R,Q).

В) Операция ”Асоциативно търсене на максимално (минимално)”

Тъй като понятията максимално и минимално са алтернативни, тук, както и в пункт А), ще бъде разгледан съвместния алгоритъм на двете операции.

За тази операция в регистъра на маската Рг.М първоначално се зарежда пълноразрядно разрешение М:=111...11, а в регистъра на асоциативния признак (аргумент) се зарежда нула: А:=000...00. Алгоритъмът се изразява със следната последователност:

1. Извършва се последователна проверка на разрядите на аргумента отляво надясно, до срещане на целеви разряд. Понятието целеви разряд беше определено в пункт 1 на алгоритъма на операция “Асоциативно търсене на по-голямо” ;

2. Формира се нов аргумент, като стойността на целевия разряд се обръща в противоположната, т.е. от нула в единица (от единица в нула). Разрядите, стоящи вдясно от целевия разряд, се маскират по схемата:

3. Изпълнява се операцията контрол на асоциацията по новия асоциативен признак, като получените в схемите за сравнение сигнали, се фиксират в регистъра на съвпаденията Рг.С ;

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

5. Повтаря се пункт 1, като се търси следващия целеви бит, в посока надясно от текущо обработения ;

6. Повтарят се действията от пункт 2 до пункт 4 ;

7. Повтаря се пункт 5 и пункт 6, докато изборът на целеви разряд стане невъзможен.

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

В резултат на така изпълнения алгоритъм в регистъра на асоциативния признак Рг.АП се оказва число, което е равно на максималната (минималната) стойност в АЗУ.

На фигура 4.4.1.2 е представена блок-схемата на алгоритъма за търсене на максимална стойност. В нея първоначално се предполага, че в регистъра на аргумента Рг.АП са записани нули, а в регистъра на маската Рг.М са записани единици.

Фиг. 4.4.1.2. Микропрограма на операция "Асоциативно търсене на максимум"

Г) Операция “Асоциативно търсене на следващото по-голямо (по-малко)”

В алгоритъма, който ще бъде представен тук, отново се съдържат две операции, тъй като става дума за две алтернативни отношения. Операцията "Търсене на следващото по-голямо" може да се определи още по следния начин - да се намери най-малкото, измежду всички по-големи от предложеното. Операция "Търсене на следващото по-малко" може да се определи по аналогичен начин така - да се намери най-голямото, измежду всички по-малки от предложеното.

Последните две определения са твърде удачни, тъй като в тях прозира алгоритъмът за всяка от операциите. По същество той се изразява чрез следната последователност:

1. Изпълнява се операция "Асоциативно търсене на по-голямо (по-малко)" по начина описан в пункт А) ;

В резултат на тази операция, в регистъра на съвпаденията Рг.С се отбелязват всички клетки, чието съдържание е число по-голямо (по-малко) от аргумента.

2. Изпълнява се операция "Асоциативно търсене на минимална (максимална) стойност", но в областта ограничена от вече отбелязаните като верни в пункт 1 отношения. Това означава, че съдържанието на Рг.С, получено в резултат на предидущата операция (пункт 1), се използва от Рг.ОТ за ограничаване на областта за търсене, при изпълнение на втората операция, т.е. съдържанието на Рг.С се явява начална стойност за Рг.ОТ.

В резултат на тези две операции, изпълнени при указаните условия, в регистъра на съвпаденията Рг.С могат да се получат няколко (или поне една) единици. Тези единици съответствуват на онези клетки, чието съдържание удовлетворява изказаните отношения.

2. Асоциативно логическо търсене

Вече беше обяснена операцията наречена контрол на асоциацията. Тази операция се извършва във всяка клетка като поразрядно сравнение, при което ако всички поразрядни сравнения фиксират съвпадение, се говори за равенство. В този смисъл формирането на сигналите за съвпадение

които по същество са резултат от операцията контрол на асоциацията, може да се интерпретира като логическа операция “И”, т.е. "Асоциативно търсене на логическо съвпадение".

Подбирайки подходящи стойности за разрядите на маската, могат да бъдат организирани още операции "Логическо търсене ИЛИ, НЕ, НЕ-И, НЕ-ИЛИ".

При операция ИЛИ фиксираните съвпадения трябва да бъдат за онези клетки, в които разрядите, съдържащи нули, съвпадат с нулите на съответните разряди на аргумента (но не и обратно).

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

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

3. Асоциативно търсене чрез броене

Съществуват две основни операции за поразрядно преброяване. Първата операция "Преброяване", преброява единиците (или нулите) в думата, съдържаща се в дадена клетка на паметта, достъпът до която е бил осъществен по асоциативния признак.

Втората операция "Преброяване със запис", преброява разрядите, в които има единици (или нули), извършва запис в клетката и освен това, полученото в брояча число изпраща на изход в данновия регистър на АЗУ.

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

Операцията "Търсене по количество еднакви битове" единици (или нули), преброява единиците (или нулите) във всички клетки на запомнящия масив. След това отбелязва със съвпадение онези клетки, чието съдържание има зададения брой единици (нули). За целта изборът на признаците се осъществява по съдържанието на брояча. Преброяването на единиците (нулите) и запомнянето на техния брой във всяка клетка се извърша с операция "Преброяване със запис", след която се изпълнява операцията "Контрол на асоциацията".

Възможно е да се организират операции "Търсене по максимум (минимум) единици (нули)".

Търсенето по признак от този вид - максимум или минимум единици (или нули) е подобно на това в операция "Търсене по количество". Разликата е в това, че в случая не се интересуваме от съвпаденията, а от стойностите, измежду които трябва да се открие максималната или минималната. За целта се изпълняват две известни вече операции : "Преброяване със запис", а след това "Търсене на максимално". Последната операция беше представена в пункт 4.4.1, в буква В).

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

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

ГЛАВА 5: ОРГАНИЗАЦИЯ НА ПРОЦЕСОРА