Асоцијативна меморија

Меморија којом се може приступити помоћу податка, добила је назив од енг. скраћенице Content-addressable memory (скраћено CAM), је посебна врста рачунарске меморије која се користи у одређеним апликацијама за претраживање веома високим брзинама. Такође је познат као асоцијативна меморија и упоређује улазне податке претраге са табелом сачуваних података и враћа адресу одговарајућих података. ^[1]

Контексно-адресибилна меморија се често користи у мрежним уређајима где убрзава рад основних информација за прослеђивање и табелe рутирања . Ова врста асоцијативне меморије се такође користи у кеш меморији. У асоцијативној кеш меморији, адреса и податак се чувају један поред другог. Када се адреса подудара, одговарајући податак се преузима из кеш меморије.

Историја

Дадли Ален Бак (енгл. Dudley Allen Buck) је 1955. године измислио концепт меморије која се може адресирати на податак. Бак је заслужан за идеју о јединици за препознавање . ^[2]

Хардверски асоцијативни низ

За разлику од стандардне рачунарске меморије, меморије са случајним приступом (енг. random-access memory, скраћно RAM), у којој корисник даје меморијску адресу, а RAM враћа податак ускладиштен на тој адреси, CAM је дизајниран тако да корисник даје податак, а CAM претражује њену целу меморију да видите да ли је таj податак ускладиштен негде у меморији. Ако је задати податак пронађен, CAM враћа листу једне или више меморијских адреса на којима је податак пронађен. Дакле, CAM је хардверска идеја онога што би се у софтверском смислу назвало асоцијативним низом .

Сличан концепт се може наћи у јединици за препознавање података, коју је предложио Дадли Ален Бак (енгл. Dudley Allen Buck) 1955. ^[3]

Стандарди

Главна дефиниција интерфејса за CAM и друге мрежне претраживаче наведена је у споразуму о компатиблиности под називом Look-Aside Interface (ЛА-1 и ЛА-1Б) који је развио Network Processing Forum . ^[4] Бројне уређаје који су у складу са споразумом о компатиблиности произведени су Integrated Device Technology, Cypress Semiconductor, ИБМ, Broadcom и других компанија. OIF је 11. децембра 2007. објавио уговор о интерфејсу за серијски поглед са стране (енг. serial lookaside - SLA).^{[тражи се извор]}

Полупроводничке имплементације

CMOS бинарна CAM ћелија која се састоји од 6T SRAM ћелије плус 4 упоредна транзистора. Када се подаци на линијама за претрагу (eнг. search lines - SL) разликују од података ускладиштених у ћелији кроз битне линије (енг. bit lines - BL), линија подударања (енг. match line - ML) ће бити повучена на масу да би указала на неусклађеност. Ако ниједна ћелија на линији подударања не указује на неусклађени бит, линија подударања ће остати високо на нивоу напона напајања да би означила подударање речи. Обе линије за претрагу могу да се држе на логичкој '0' као услов претраживања који није битан. Линије за претрагу и битне линије могу се спојити у један пар линија података.

CAM је много бржи од RAM-а у апликацијама за претраживање података. Међутим, CAM има недостатака у погледу трошкова. Трошкови су одређени бројем транзистора који су потребни да би се направило интегрисано коло. За разлику од RAM чипа, који има једноставне ћелије за складиштење, сваки појединачни меморијски бит у потпуно паралелном CAM-у мора имати сопствено повезано коло за поређење да би се открило подударање између ускладиштеног и улазног бита. Поред тога, резултати подударања из сваке ћелије у речи података морају да се комбинују да би се добио потпун сигнал подударања података. Додатна кола повећавају физичку величину и трошкове производње CAM чипа. Додатна кола такође повећавају потрошњу електричне енергије пошто је свако коло за поређење активно у сваком циклусу такта. Сходно томе, CAM се користи само у специјализованим апликацијама где се брзина претраживања не може постићи коришћењем јефтинијих чипова. Једна успешна рана имплементација била је General Purpose Associative Processor IC and System. ^[5]

Почетком 2000-их неколико полупроводничких компанија, укључујући Cypress, IDT, Netlogic, Sibercore, ^[6] и MOSAID, представило је CAM производе намењене мрежним апликацијама. Ови производи су били означени као мрежни претраживачи (енгл. Network Search Engines - NSE), акцелератори мрежног претраживања (енгл. Network Search Accelerators - NSA) и процесори засновани на знању (енгл. Knowledge-based Processors - KBP), али су у суштини били CAM са специјализованим интерфејсима и функцијама оптимизованим за умрежавање. Тренутно Broadcom нуди неколико KBP производа. ^[7]

Алтернативне имплементације

Да би се постигла другачија равнотежа између брзине, величине меморије и цене, неке имплементације опонашају функцију CAM-а користећи стандардну претрагу стабла или хеширање дизајна у хардверу, користећи хардверске трикове као што су копирање података или цевовод (енг. pipelining) да би се убрзале ефективне перформансе. Ови дизајни се често користе у рутерима .^{[тражи се извор]} Лулеа-ов алгоритам (енгл. The Lulea algorithm) је ефикасна имплементација за најдуже претраге, где је потребно подутарање префикса, као што се захтева у табелама рутирања на интернету.

Тернарни CAM

CMOS тернарна CAM ћелија која се састоји од двa 6Т SRAM ћелије плус 4 упоредна транзистора. Нормално супротни логички нивои, '0' и '1' или '1' и '0' биће ускладиштени у две ћелије. За „небрига“ услов „0“ ће бити сачуван у обе ћелије тако да линија подударања (енг. МЛ) неће бити повучена ниско за било коју комбинацију података линије за претрагу (енг. СЛ).

Бинарни CAM је најједноставнији тип CAM-a и користи речи за претрагу података које се у потпуности састоје од 1 и 0 . Тернарни CAM (скраћено TCAM) ^[8] дозвољава непожнато стање подударања X или не води рачуна о једном или више битова у сачуваном податку, додајући тако флексибилност претрази. На пример, сачувана реч „10XX0“ у тернарном CAM-у ће одговарати било којој од четири речи за претрагу „10000“, „10010“, „10100“ или „10110“. Додатна флексибилност претраживања долази уз додатну цену у односу на бинарни CAM, јер интерна меморијска ћелија сада треба да кодира три могућа стања уместо два за бинарни CAM. Ово додатно стање се обично имплементира додавањем бита маске (бит „брига“ или „небрига“) свакој меморијској ћелији.

Примери апликација

Меморија која се може адресирати на садржај се често користи у мрежним уређајима . На пример, када мрежни прекидач прими податак са једног од својих портова, он ажурира интерну табелу са изворном MAC адресом оквира (енг. frame) и портом на који је примљен. Затим тражи одредишну MAC адресу у табели да одреди на који порт оквир (енг. frame) треба да буде прослеђен и шаље га на тај порт. Табела MAC адреса се обично имплементира са бинарним CAM-ом тако да се одредишни порт може пронаћи веома брзо, смањујући кашњење које има сам прекидач (енг. switch).

ТCAM се често користе у мрежним рутерима, где свака адреса има два дела: мрежни префикс, који може да варира у величини у зависности од конфигурације подмреже, и адресу домаћина (енгл. Host), која заузима преостале битове. Свака подмрежа има мрежну маску која одређује који битови адресе су мрежни префикс, а који битови адресe домаћина. Рутирање се извршава помоћу табеле рутирања коју одржава рутер и која садржи сваки познати мрежни префикс одредишта, придружену мрежну маску и информације потребне за усмеравање пакета до тог одредишта. У једноставној софтверској имплементацији, рутер упоређује одредишну адресу пакета који треба да се рутира са сваким уносом у табели рутирања, изводећи конјункцијау са мрежном маском и упоређујући га са мрежним префиксом. Ако су једнаки, одговарајуће информације о рутирању се користе за прослеђивање пакета. Коришћење тернарног CAM-а за табелу рутирања чини процес тражења веома ефикасним. Адресе се чувају помоћу небрига за хост део адресе, тако да тражење одредишне адресе у CAM-у одмах преузима исправан унос за рутирање; и маскирање и поређење врши CAM хардвер. Ово функционише ако:

уноси се чувају по редукцији дужине мрежне маске
хардвер враћа само први одговарајући унос; стога се користи подударање са најдужом мрежном маском ( подударање најдужег префикса). ^[9]

Остале CAM апликације укључују:

Потпуно асоцијативни кеш контролери и бафери за превођење ^[10]
Машине за базе података
Хардвер за компресију података
Вештачке неуронске мреже ^[11]
Системи за спречавање упада
Мрежни процесори
Неколико прилагођених рачунара, као што је Goodyear STARAN, направљено је за имплементацију CAM-а.

Референце

^ „K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006.” (PDF). Архивирано (PDF) из оригинала 2007-03-15. г.
^ TRW Computer Division. (1963). First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.
^ TRW Computer Division Архивирано август 5, 2011 на сајту Wayback Machine, 1963, p. 17.
^ Look-Aside (LA-1B) Interface Implementation Agreement (PDF), 2004-08-04
^ Stormon, C. D.; Troullinos, N. B.; Saleh, E. M.; Chavan, A. V.; Brule, M. R.; Oldfield, J. V. (децембар 1992). „C. Stormon, N. Troullinos, E. Saleh, A. Chavan, M. Brule and J. Oldfield, "A general-purpose CMOS associative processor IC and system", IEEE Micro, vol. 12, no. 6, pp. 68-78, December 1992.”. IEEE Micro. 12 (6): 68—78. doi:10.1109/40.180249.
^ „Sibercore Technologies - Silicon Solutions for Cyberspace”. Архивирано из оригинала 2003-04-19. г.
^ „16nm Heterogeneous Knowledge-Based Processors (KBPs)”. Архивирано из оригинала 2017-05-19. г.
^ Hucaby, David (2004). CCNP BCMSN Exam Certification Guide: CCNP Self-study. ISBN 9781587200779.
^ Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005
^ Smith, Alan Jay (септембар 1982). „Cache Memories” (PDF). Computing Surveys. 14 (3): 473—530. doi:10.1145/356887.356892. Архивирано из оригинала (PDF) 03. 04. 2022. г. Приступљено 3. 4. 2022. „The TLB is a small associative memory which maps virtual to real addresses.”
^ Hinton, Geoffrey E. (1984). „Distributed representations”. Архивирано из оригинала 02. 05. 2016. г. Приступљено 08. 02. 2023.

Литература

Anargyros Krikelis, Charles C. Weems (editors) (1997). Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2.
US 6823434, Hannum et al., "System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state", published 2004
Pagiamtis, K.; Sheikholeslami, A. (2006). „Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey” (PDF). IEEE Journal of Solid-State Circuits. 41 (3): 712—727. Bibcode:2006IJSSC..41..712P. S2CID 11178331. doi:10.1109/JSSC.2005.864128.
Stormon, C.D.; Troullinos, N.B.; Saleh, E.M.; Chavan, A.V.; Brule, M.R.; Oldfield, J.V.; A general-purpose CMOS associative processor IC and system, Coherent Research Inc., East Syracuse, NY, USA, IEEE Micro, Dec. 1992, Volume: 12 Issue:6.

Спољашње везе

[1] „K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006.” (PDF). Архивирано (PDF) из оригинала 2007-03-15. г.

[2] TRW Computer Division. (1963). First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.

[3] TRW Computer Division Архивирано август 5, 2011 на сајту Wayback Machine, 1963, p. 17.

[4] Look-Aside (LA-1B) Interface Implementation Agreement (PDF), 2004-08-04

[5] Stormon, C. D.; Troullinos, N. B.; Saleh, E. M.; Chavan, A. V.; Brule, M. R.; Oldfield, J. V. (децембар 1992). „C. Stormon, N. Troullinos, E. Saleh, A. Chavan, M. Brule and J. Oldfield, "A general-purpose CMOS associative processor IC and system", IEEE Micro, vol. 12, no. 6, pp. 68-78, December 1992.”. IEEE Micro. 12 (6): 68—78. doi:10.1109/40.180249.

[6] „Sibercore Technologies - Silicon Solutions for Cyberspace”. Архивирано из оригинала 2003-04-19. г.

[7] „16nm Heterogeneous Knowledge-Based Processors (KBPs)”. Архивирано из оригинала 2017-05-19. г.

[8] Hucaby, David (2004). CCNP BCMSN Exam Certification Guide: CCNP Self-study. ISBN 9781587200779.

[9] Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005

[10] Smith, Alan Jay (септембар 1982). „Cache Memories” (PDF). Computing Surveys. 14 (3): 473—530. doi:10.1145/356887.356892. Архивирано из оригинала (PDF) 03. 04. 2022. г. Приступљено 3. 4. 2022. „The TLB is a small associative memory which maps virtual to real addresses.”

[Hinton,_Geoffrey_E_19842-11] Hinton, Geoffrey E. (1984). „Distributed representations”. Архивирано из оригинала 02. 05. 2016. г. Приступљено 08. 02. 2023.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]