I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   22 ,   N o .   1 A p r i l   202 1 p p.   89 ~ 96   IS S N :   25 0 2 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 22 .i 1 . pp 89 - 96             89       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   A l g o r i t h m i c   T C A M   o n   FPGA   w i t h   d a t a   c o l l i si o n   a p p r o a c h       N gu ye n   Tr i n h ,   A n h   L e   Th i   K i m ,   H u n N gu ye n ,   Li n h   Tr a n   D e pa r t m e n t   o f   E l e c t r o ni c s ,   H o   C hi   M i n C i t y   U ni v e r s i t y   of   T e c hno l o gy ,   VNU - H C M ,   V i e t n a m       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e O c t   20 ,   2020   R e v i s e J a n   6 ,   202 1   A c c e pt e J a n   17 ,   202 1       C o nt e nt   a ddr e s s a b l e   m e m o r y   ( C A M )   a nd  t e r na r y   c o nt e nt   a ddr e s s a bl e   m e m o r y   ( T C A M )   a r e   s p e c i a l i z e h i g h - s pe e m e m o r i e s   f o r   da t a   s e a r c hi ng .   C A M   a nd  T C A M   ha v e   m a ny   a ppl i c a t i o ns   i n   ne t w o r r o ut i n g ,   pa c ke t   f o r w a r di ng   a n I nt e r n e t   da t a   c e n t e r s .   T h e s e   t y pe s   o f   m e m or i e s   h a v e   dr a w b a c ks   o po w e r   di s s i pa t i o a nd   a r e a .   A s   f i e l d - pr o g r a m m a b l e   g a t e   a r r a y   ( F P G A )   i s   r e c e nt l y   be i ng   us e f o r   ne t w o r a c c e l e r a t i o a p pl i c a t i o ns ,   t h e   de m a nd  t o   i n t e g r a t e   T C A M   a nd  C A M   o F P G A   i s   i nc r e a s i ng .   B e c a us e   m o s t   F P G A s   do   n o t   s uppo r t   na t i v e   T C A M   a nd  C A M   ha r dw a r e ,   m e t ho ds   o f   i m pl e m e n t i ng   a l g o r i t hm i c   T C A M   us i ng   F P G A   r e s o ur c e s   h a v e   be e n   pr o po s e t hr o ug r e c e n t   y e a r s .   A l g o r i t hm i c   T C A M   o F P G A   ha v e   t he   a dv a nt a g e s   o f   F P G A s   l o w   p o w e r   c o ns um pt i o a nd  h i g i nt e r g r a t i o s c a l a bi l i t y .   T hi s   p a pe r   pr o po s e s   a   s c a l e a bl e   a l g o r i t hm i c   T C A M   de s i g o F P G A .   T he   d e s i g us e s   m e m o r y   bl oc ks   t o   ne g a t e   po w e r   di s s i pa t i o i s s ue   a nd  da t a   c o l l i s i o t o   s a v e   a r e a .   T he   p a pe r   a l s o   pr e s e nt s   a   d e s i g o f   a   256  104 - b i t   a l g o r i t hm i c   T C A M   o I nt e l   F P G A   C y c l o ne   V ,   e v a l ua t e s   t h e   pe r f o r m a nc e   a nd  a p pl i c a t i o a bi l i t y   o f   t he   d e s i g o l a r g e   s c a l e   a nd   i f u t u r e   de v e l o pm e n t s .     Ke y w or ds :   A l go r i t h m i c   T CA M   F P G A   T CA M   On - c h i p   m e m o r y   T CA M   R A M - b a s e T CA M   S e a r c h   e n g i n e   T hi s   i s   an   ope n   ac c e s s   ar t i c l e   u nde r   t he   C C   B Y - SA   l i c e ns e .     Cor r e s pon di n g   Au t h or :   L i nh  T ra n   D e pa rt m e n t   o f   E l e c t r o n i c s   H o   Ch i   M i nh  Ci t y   U n i v e r s i t y   of   T e c hn o l o g y ,   V N U - H CM   268  L y   T h uo n K i e t   S t r e e t ,   1 D i s t r i c t ,   H o   Chi   M i nh  Ci t y ,   V i e t n a m   E m a i l :   l i nht ra n@ h c m ut . e du. v n       1.   I N TR O D U C TI O N   Co n t e n t   a dd r e s s a b l e   m e m o r y   (CA M )   i s   s pe c i a l   t y p e   of   m e m o r y   w h i c h   s e a r c h   t h e   e nt i r e   da t a b a s e   i o n e   c l oc c y c l e   a n o ut put   t h e   a dd r e s s   i n f o r m a t i o n   o f   t h e   i n put   da t a   [1 - 3].   T h e   a pp l i c a t i o n s   o f   CA M   a r e   r o ut i ng  I nt e rn e t   pa c k a ge ,   c a c h e   m e m o r y   f o r   m i c r o pr o c e s s o r s ,   a rt i f i c i a l   i nt e l l i ge n c e .   A ddi t i o na l l y ,   CA M   a l s o   ha s   a pp l i c a t i o n s   i n   b i o l o gi c a l   r e s e a r c h,   c o m pa r i ng  a n d   m a t c h i n g   D N A   s e que n c e s   [4].   A l t h o ugh  CA M   ha s   m a n y   a dv a n t a ge s   s uc h   a s   be t t e r   s e a r c h i ng  s pe e of   a ddr e s s i ng  da t a   w i t h   s o f t w a r e   o n   m i c r o p r o c e s s o r s ,   i t   c o n s um e s   m o r e   e n e r gy   a n ha s   poo r   i n t e g r a t i o n   s c a l a b i l i t y .   T h e   poo r   i n t e g r a t i o n   s c a l a b i l i t y   i s   c a us e d   by   t h e   n e e ds   of   us i n a   s e pa r a t e m e m o r y   s t r uc t u r e   a n b e i ng  a n   i nd e pe n de n t   IC  c o nn e c t e pe r i p h e ra l l y   t o   t h e   m i c r o pr o c e s s o r s   [5] .     T e rna r y   c o n t e n t   a dd r e s s a b l e   m e m o r y   (T CA M i s   CA M   w i t h   s uppo rt   f o r   t e rn a r y   v a l ue s .   T CA M   c o n s um e s   30  t i m e s   m o r e   m e m o r y   r e s o ur c e s   t ha n   D D R   S R A M   a n d   150  t i m e s   m o r e   po w e r   c o n s um p t i o n   pe r   m e m o r y   b i t   t ha n   S R A M   [5] .   T CA M   ha s   a l w a y s   be e n   a   v i t a l   po i nt   f o r   i m p r o v e m e n t   i di gi t a l   s y s t e m s .   H ow e ve r ,   t h e   de v e l o pm e n t   f o r   T CA M s   i r e c e n t   y e a r s   s e e m s   t o   h a v e   s l o w e dow n .   V e r y - h i g h - s pe e s e a r c h i n g   a ppl i c a t i o n s   s t i l l   r e qu i r e s   t h e   r e f i n e m e n t s   o f   T CA M s   i m a n y   di r e c t i o n s .   In   r e c e nt   h a rdw a r e   a c c e l e r a t i o n   s o l ut i o n s ,   f i e l d - p r o gra m m a b l e   ga t e   a rra y s   (F P G A a r e   c o m m o n l y   us e a s   i t   c a n   b e   de s i gn e qui c kl y   a n up da t e di r e c t l y   o n   i n s t a l l e s y s t e m .   F P G A s   a ppl i c a t i o n s   a r e   i n   a c c e l e r a t i ng  I nt e rn e t   p a c ka ge s   r o ut i n g ,   a rt i f i c i a l   i nt e l l i ge n c e   a n d   b i o l o gi c a l   r e s e a r c h   a n d   D N A   s e que n c e s   [6 7].   T h e s e   a ppl i c a t i o n s   r e qui r e   f a s t   da t a   s e a r c h i ng  h a rdw a r e   s uc h   a s   T CA M   a n CA M .   B e c a us e   m o s t   F P G A s   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   22 ,   N o .   1 A p r i l   20 21   :     89   -   96   90   do   n o t   h a v e   n a t i v e   s uppo r t   f o r   CA M   a n T CA M   ha r dw a r e   o n   t h e i r   r e s o ur c e s ,   m e t h o ds   ha v e   be e n   p r o po s e t us e   e xi s t i n g   F P G A   o n - c h i r e s o ur c e s   s uc a s   m e m o r y   b l o c k s   a n d   l o o k - up  t a b l e s .   S t udi e s   p r o po s e us i n g   i nt e rna l   R A M   b l oc ks   of   F P G A   t o   r e pl a c e   CA M   a n T CA M ,   h o w e ve r ,   w i t t r a de - o ff   fo r   a   l a r ge   a m o u n t   o f   r e s o ur c e s   [5 8].   In   [9]  a l s o   pr o v i de   s c a l e a b l e   a l go r i t hm i c   T CA M   w h i c h   us e s   F P G A   s l i c e s   a s   i t s   m a i r e s o ur c e .   X i l i n x   a l s o   p r e s e nt s   a i nt e l l e c t ua l   p r o pe r t y   c o r e   f o r   i m p l e m e n t i ng  T CA M s   o n   t h e i r   F P G A   [10] .   M e t h o ds   t o   o pt i m i z e   t h e   a m o u n t   o f   r e s our c e s   a n e n e rgy   c o n s um p t i o n   a r e   a l s o   pr o po s e d   [11 - 17] .   G r e e n T C A M   [1 8]  p r o v e t h a t   a l go ri t hm i c   T CA M   i m p r o v e s   pow e r   e ff i c i e n c y   w i t h   r e l i a b i l i t y   o n   t h e   r u l e   s e t .   P s e udo - T CA M   [19]  ha s   s i m pl e   a n u ni f o r m   ha r dw a r e   o r ga ni z a t i o n   f o r   a l l   r ul e s e t s   a n hi g h   t hr o ughput ,   b ut   n e e s pe c i a l   m a pp i n a n d   r e l o c a t i o f o r   upd a t e s .   A l go r i t hm   a i m s   f o r   f a s t   upd a t i n m e n t i o n e i n   [20]  t ra de - o ff   w i t h   pe r f o r m a n c e .   M u l t i - pu m pi n S R A M s   i n   [1 5]  i n c r e a s e s   t h e   o pe r a t i ng  f r e que n c y   of  i n t e rn a l   R A M   b l oc ks   a n d   a l l o w s   m ul t i p l e   a c c e s s   a dv a n t a ge   w i t h   t h e   s a m e   s y s t e m   c l o c k.   W i t h   h i g h - f r e que n c y   de s i gn s ,   i t   i s   d i f f i c ul t   t o   ha v e   a n   i nt e rn a l   R A M   de s i g n   t h a t   run s   t i m e s   f a s t e r   t h a t h e   s y s t e m   [15].   R e s e a r c [17]  s ugge s t s   a   s pe c i a l   w a y   o f   p o s i t i o n i n d a t a ,   b ut   o n l y   r e f e r s   t o   r e p l a c i n CA M   w i t h o ut   m e n t i o ni n h o w   t s uppo r t   t e rna r y   v a l ue   of t e n   s e e n   i c o n t e n t   a dd r e s s a b l e   m e m o r y   w h e us e i n   a f o r e m e nt i o n e a pp l i c a t i o n s .   M ul t i pl e   h a s m a t c h i ng  u ni t   [21]  i s   a l s o   a n   o pt i o t o   i m pl e m e nt   a l go ri t hm i c   T CA M ,   b ut   i t   m e e t s   w i t ha s h i n g   c o l l i s i o n.   T h i s   s t u dy   pr o pos e a n   a l go ri t hm i c   T CA M   s t r uc t u r e   us i n g   R A M   b l oc ks   o n   F P G A ,   w h i c h   w o ul gi v e   t h e   a dv a n t a ge   o f   pow e r   c o n s um p t i o o v e r   o r gi na l   T C A M   c e l l s   [14].   T o   s a v e   m o r e   a r e a ,   da t a   c o l l i s i o m e t h o fo r   CA M s   f r o m   [17]  a r e   us e d.   In   o r de r   t o   s uppo r t   t e rn a r y   v a l ue ,   w e   us e   a ddi t i o n a l   m e m o r y   b l o c k s   s t ruc t u r e s   a n t r a n s f o r m   t e rn a r y   v a l ue   i nt o   m a s k   v e c t o r s .   T h e   a r c hi t e c t u r e   s h o w n   i n   t h e   p a pe r   i s   a i m p r o v e m e n t   f r o m   [1 7]  i n   t h e   t e rm   o f   t e rna r y   m a t c h i ng  f u n c t i o n s .     T h e   r e m a i n de r   o f   t h i s   p a pe r   i s   s t r uc t u r e a s   f o l l ow s .   T h e   s e c o n s e c t i o n   s h o w s   t h e   a l go ri t hm s   a n c a l c ul a t i o n s   t h a t   o r g a n i z e   t h e   da t a b a s e   a n d   r e s o ur c e s   a c c or d i n t o   m a t h e m a t i c a l   c a l c ul a t i o n s .   I n   t h e   t h i r d   s e c t i o n ,   a e xa m pl e   o f   a   256   1 04 - b i t   t e rna r y   c o n t e n t   a dd r e s s a b l e   m e m o r y   o n   F P G A   C y c l o n e   V   i s   pr e s e nt e d.   T h e   f o r t h   s e c t i o n   e s t i m a t e s ,   c a l c u l a t e s   a n e v a l u a t e s   t h e   f e a s i b i l i t y   o l a rg e - s c a l e   i m pl e m e nt a t i o of   t h e   p r o po s e a l go r i t h m   a n f ut u r e   de v e l o pm e n t .   T h e   f i na l   s e c t i o n   d r a w s   c o n c l us i o n s .         2.   TH E   P R O P O S ED   M ET H O D     T a b l e   s h o w s   t h e   b a s i c   da t a b a s e   o f   a   CA M ,   i n c l ud i n r o w s   o f   da t a   s o rt e i o r de r   o f   pri o r i t y .   R ul e   i s   t h e   de f a ul t   r u l e   w h e n   t h e   r e t r i e v e da t a   do e s   n o t   m a t c w i t h   a n y   of   t h e   r e m a i n i ng  r ul e s   i t h e   m e m o r y .   T h a t   t y pi c a l   da t a b a s e   c a n   b e   l o a de i nt o   a   c o n t e n t   a dd r e s s a b l e   m e m o r y   t h a t   s uppo rt s   t e rna r y   v a l ue s   o r   a   c o n t e n t   a dd r e s s a b l e   m e m o r y   t h a t   do e s   n o t   s uppo r t   t h e   t e rna ry   v a l ue s   w i t h   c o n t r o l l e pr e f i e xpa n s i o n   ( CP E ) ,   s i m pl y   s e pa r a t i n t h e   t e rna r y   v a l ue   i nt o   i t s   b i n a r y   v a l ue s .   T hus ,   w i t h   a   c o n t e nt   a d d r e s s a b l e   m e m o r y   t h a t   do e s   n o t   s up po r t   t e rna r y   v a l ue s ,   t h e   de m a n d   f o r   m e m o r y   r e s o ur c e s   i s   e xt r e m e l y   l a r ge .         T a b l e   1 .   E xa m p l e   o f   T CA M s   b a s i c   da t a b a s e   Ru l e   T CA M   Ru l e s   0   x . x . x . x   1   1 1 . x . x . x   2   1 1 . 0 6 . x . x       n   1 1 . 0 6 . 1 9 . 0 7       T h e   e xa m p l e   o f   c o n t r o l l e p r e f i e xpa n s i o n   (CP E i s   s h o w n   i n   [2 2].   W i t h   a   l a r ge   n u m b e r   o f   r ul e s   a n m a n y   a r b i t r a r y   v a l ue s   l i ke   a   F IB   r o ut e r,   us i n CP E   c o n s u m e s   a   huge   a m o unt   o f   r e s o ur c e s .   T o   b ui l a   c o n t e n t   a dd r e s s a b l e   m e m o r y   o n   F P G A ,   t h e   m a i r e s o ur c e   us e i n   t h e   s t udy   i s   i n t e rn a l   R A M   o n   F P G A .   T h e   i n t e rn a l   R A M   m e m o r y   o n   t h e   F P G A   i s   p r o v i de a s   m e m o ry   c e l l s   a s   s h o w n   i n   F i gu r e   1 .   E a c h   m e m o r y   c e l l   s uppo r t s   s t o ri n a   c e r t a i a m o unt   o f   ki l ob i t   o f   da t a .   I nt e l ' s   M 20K   m e m o r y   c e l l   s uppo r t s   20k - b i t   a n X i l i nx  M 9K ,   M 10K   o r   B 36K   a r e   s i m i l a r .   T h e s e   m e m o r y   c e l l s   s uppo r t   t h e   n u m b e r   o f   a ddr e s s   b i t s   a nd  m e m o r y   c e l l   l e n g t h s   t ha t   v a r y   by   t e c h n o l o g y .   H ow e ve r ,   w h e n   us i ng  t o   b ui l c o n t e n t   a dd r e s s a b l e   m e m o r y ,   i t   m us t   b e   n o t e d   t h a t   t h e s e   m e m o r y   c e l l s   do   n o t   s up po r t   t e rna r y   v a l ue s   b ut   o n l y   s upp o r t   b i na r y   v a l ue s .     T o   un de r s t a n t h e   a l go r i t hm ,   f i r s t   w e   n e e t un de r s t a n d   h o w   t h e   c o n t e n t   a d d r e s s a b l e   m e m o r y   w o r ks .   T h e   b a s i c   o pe r a t i o n   o f   a   c o n t e n t   a dd r e s s a b l e   m e m o r y   i s   de pi c t e i n   F i g u r e   2.   T h e   da t a   a s   a   ke y   i s   i n put   i nt o   t h e   c o n t e nt   a dd r e s s a b l e   m e m o r y   a n t h e   o ut put   i s   r e t u rn e d .   T h e   o ut put   i s   t h e   a dd r e s s   of   t ha t   da t a   i n   t h e   c o n t e nt   a dd r e s s a b l e   m e m o r y .   I n   ge n e ra l   c a s e s ,   t h e   r e s ul t   i s   e i t h e r   t h e   da t a   m a t c h e s   a   r u l e   t ha t   i s   i n   t h e   c o n t e n t   a dd r e s s a b l e   m m e m o r y   o r   n o t ,   a nd  t h e   a c t i o n   a ppl y   t o   t h a t   d a t a .   I n   b ui l di n T CA M   m e m o r y   o n   F P G A ,   a s   m e n t i o n e i [7 16],   t h e   b e s t   w a y   t o   r e duc e   t he   a m o u n t   o f   R A M   c o n s um e a n d   o pt i m i z e   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A l gor i t hm i c   T CA M   on   F P G A   w i t da t c o l l i s i on   appr oa c h   ( Nguy e T r i nh )   91   s y s t e m   s pe e i s   t o   c ut   t h e   ke y   i n t o   m a n y   pi e c e s   w i t h   a   c e rt a i n   b i t   l e n g t h   ( m a y   o r   m a y   n o t   b e   e qua l   w i t h   e a c o t h e r).   T h e   m o s t   o pt i m a l   m e t h o [7 16]  i s   a c h i e v e w h e n   t h e   b i t   l e n g t h   o f   t h e   ke y   f r a g m e nt s   i s   t h e   m i n i m u m   a dd r e s s   b i t   l e n gt h   o f   t h e   m e m o r y   c e l l   o n   t h e   F P G A .   F o r   e xa m pl e ,   f o r   Int e l ' s   M 20K   m e m o r y   c e l l ,   t h i s   l e n gt i s   b i t s .   In   t h e   m e t h o i m p l e m e nt e i n   t h e   a l go r i t h m   o f   t hi s   s t udy ,   w e   w i l l   a l s o   c ut   t h e   ke y   i n t o   pi e c e s   t o pt i m i z e   s pe e a n d   r e duc e   m e m o r y   c o n s um pt i o n.               F i gu r e   1 . T y pi c a l   R A M   b l o c c e l l     F i gu r e   2 .   B a s i c   o pe ra t i o n   o f   a   c o nt e nt   a dd r e s s a b l e   m e m o r y       F i gu r e   s h o w s   t h e   ke y   c ut   i n t o   pi e c e s   of   a   c e r t a i n   b i t   l e n g t h.   T h e s e   pi e c e s   a c c e s s   e a c h   pr e de f i n e c e l l   c e l l   a n f o r m   a   v e c t o r   of   r e s ul t s ,   a s   s h o w n   i n   t h e   s t ud y   [17].   H ow e ve r ,   r e s e a r c h   [17]  do e s   n o t   s uppo r t   r u l e s   t ha t   c o nt a i n   t e rna r y   v a l ue s .   O n c e   t h e   v e c t o r   o f   t h e   r e s ul t   w a s   o b t a i n e d ,   t h e y   o n l y   a n a l y z e   a n v e ri fy   i t   t o   pr o duc e   t h e   r e s ul t   o f   t h e   m a t c h i n ke y .   T h e   r e s e a r c h   p r e s e nt e i n   t h i s   pa pe r   m o di f i e s   a n r e o r ga ni z e s   t h e   da t a   c o l l i s i o n   s t ruc t u r e   w h i c h   w a s   pr e s e nt e i n   r e s e a r c h   [ 17].   T h e   m o di f i c a t i o n s   a n a dd i t i o n a l   m o dul e s   a l l o w   r ul e s   t o   us e   t e r na r y   v a l ue s   a n r e duc e   t h e   b ur de n   o CP E   o n   m e m o r y   c o n s um p t i o n.   F i gu r e   s h o w s   t h e   b a s i c   da t a f l ow   of   t hi s   T CA M   s t r uc t u r e .   T h e   da t a   f o l l ow s   m a i s t e ps   t o   a c hi e v e   r e s ul t .           F i gu r e   3 .   T h e   CA M   K e y   i s   c ut   i n t o   p i e c e s   a n d   us e t o   c r e a t e   a   m a t c v e c t o r   a t   t h e   e n d           F i gu r e   4 .   B a s i c   d a t a f l ow   of   s t r uc t u r e       F i gu r e   i l l us t a t e s   t h e   p r o c e s s   o s e t t i n rul e s   i n t o   t h e   m e m o r y .   H e r e   w e   t a ke   a n   e xa m pl e   o f   10 - b i t   r u l e s ,   di v i de i n t o   2 - b i t   pi e c e s .   A   t a b l e   o t h i s   c o n t e n t   a d d re s s a b l e   m e m o r y   c o n s i s t s   of   c e l l s   c o n t a i n i n t w pa r t s ,   t h e   s t a t us   o f   t h e   c e l l   a n t h e   i de n t i f i c a t i o n   n um b e r   ( ID   n u m b e r   o r   ID f o r   t h e   r ul e .   T h e   w a y   t o   w r i t e   t h e   r u l e s   i nt o   t h e   t a b l e   i s   a s   f o l l ow s .   F i r s t ,   t h e   r ul e s   m us t   b e   i n   p r o pe r   f o r m   t o   b e   a dde t t h e   t a b l e .   T h e   a pp r o pri a t e   f o r m   t o   b e   i n c l ude i n   t h e   t a b l e   i s   t h e   rul e s   w i t f r a gm e n t s   c o nt a i n i ng  t w o   a r b i t r a r y   v a l ue   b i t s   t h a t   go   t o ge t h e a s   " **"   o ha v e   n o   a r b i t ra r y   v a l ue s .   If   t h e   r u l e   ha s   f ra gm e n t s   i t h e   f o r m   o f   o n l y   o n e   a r b i t r a r y   v a l ue ,   t h e   r ul e   m us t   b e   s e pa ra t e i nt o   t w o   r ul e s .   T o   put   a   rul e   i n t o   a   t a b l e ,   w r i t e   t h e   r ul e ' s   ID   i n t o   t h e   c e l l ,   r e s pe c t i v e l y ,   w i t h   t h e   a dd r e s s   c o rr e s po n di n g   t o   t h e   v a l ue   o f   t h a t   r u l e   o n   t h e   t a b l e   a n t r a n s f e r   t h e   s t a t e   o f   t h e   c e l l   t o   w r i t t e n.   If   t h e   c e l l   a l r e a dy   h a s   a   r u l e   w r i t t e i f i r s t ,   t h e   c e l l   w i l l   b e   i c o l l i s i o n   s t a t e .   A f t e r   f i n i s hi n g   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   22 ,   N o .   1 A p r i l   20 21   :     89   -   96   92   w r i t i ng  t h e   r u l e s ,   e a c h   c e l l   i n   t h e   t a b l e   h a s   o n e   i n   t hr e e   s t a t e s :   b l a n k ,   f i l l e d,   o r   c o l l i s i o n.   W h e n   w r i t i n a   r ul e ,   i t   i s   n e c e s s a r y   t o   e n s ur e   t h a t   t h e r e   a r e   a t   l e a s t   n   c e l l s   t h a t   d o   n o t   c o l l i de ,   us ua l l y ,   n   o nl y   n e e ds   t o   b e   1.   T r e m o v e   a   r ul e   f r o m   t h e   t a b l e ,   r e m o v e   t ha t   rul e   f r o m   t h e   c e l l   i t   ha s   f i l l e i n,   t h e   c o l l i s i o c e l l   w i l l   r e t u rn   t o   b e   a   n o r m a l   f i l l e c e l l   i f   t h e r e   i s   o nl y   o n e   f i l l   r u l e   l e f t ,   t h e   f i l l e c e l l   w i l l   r e t u rn  t o   b e   a   b l a n k   c e l l .     T o   f i n t h e   a dd r e s s   fo r   a   ke y ,   fe w   m o r e   c o m po n e n t s   a r e   n e e de d.   H ow e ve r ,   a t   t hi s   s t e p,   a   da t a   v e c t o r   c a n   a l r e a dy   b e   fo un t o   m o v e   o n .   F i gu r e   i l l us t ra t e s   h o w   t o   f i n a   ke y   f r o m   t h e   w r i t t e r ul e   d a t a   t a b l e   a n i n   s o m e   i n v a l i c a s e s ,   qu i c kl y   c o n c l ude   t h e   r e s ul t .   B a c a s e s   a r e   p r e di c t a b l e   du r i ng  t a b l e   c o n s t r uc t i o n   a nd  c a b e   pr e ve n t e w i t h   p r o pe r   s o f t w a r e   o pt i m i z a t i o n.   A c c o r di n t o   [16],   f o r   a   t a b l e   w i t h   a d d r e s s e s   a n d   c o n t a i ni n m   r a ndo m   rul e s ,   t h e   c o l l i s i o n   ra t e   f o r   a   c o l um i s   26%.   F o r   z   f ra gm e n t s ,   t h e   r a t e   o f   h a v i n a n   e n t i r e   z - pi e c e   v e c t o r   i s   a l l   i c o l l i de s t a t e   i s   26% ,   t h i s   i s   v e r y   s m a l l   w i t h   a   l o n g   b i t - l e ngt ke y .                     F i gu r e   5 .   S e t t i n g   r ul e s   i n t o   t h e   da t a b a s e   o f   t h e   T CA M     F i gu r e   6 .   S e a r c h i ng  f o r   t h e   m a t c v e c t o r   f r o m   t h e   da t a b a s e       In   t h e   n e xt   s t e p,   t h e   r u l e s   h a v e   be e n   w r i t t e n   i n   t h e   t a b l e .   F or   e a c h   o f   t h e s e   r ul e s ,   w e   h a v e   a   v e c t o r   t h a t   m a rks   t h e   c o r r e s po n di ng  t e rna r y   v a l ue s   (m a s v e c t o r ).   E a c h   b i t   i n   t hi s   v e c t o r   m a r ks   a   f ra gm e nt   of  a r b i t r a r y   v a l ue   **” .   F o r   e a c h   p i e c e   t ha t   c o nt a i n s   a   w ri t t e ID   ( n o t   i n   a n   c o l l i s i o n   s t a t e ),   w e   n e e t o   f i n a   c o r r e s po n di ng  m a s v e c t o r   t o   c o m pa r e .   T h e r e   a r e   m a n y   w a y s   t h a t   c a n   b e   a ppl i e t o   s e a r c h   f o r   c us t o m   v e c t o r s   i n   t h i s   c a s e ,   e a c h   w i t h   d i f f e r e n t   a dv a nt a ge s   a n d i s a dv a nt a ge s   w h e n   a pp l y i n o n   h a rdw a r e .   T h e   m a s v e c t o r s   a n t h e   m a r k i n p r o c e s s   a r e   de s c r i b e i n   F i gu r e   7.   T h e   m a s v e c t o r s   a r e   p r e s e n t e i n   t h e   f i gur e   a s   5 - b i t   b i t   s t ri n gs   w i t e a c h   a s s e r t e d   b i t   r e p r e s e nt   a   m a s ke d   s e gm e nt .             F i gu r e   7 .   M a s v e c t o r s   f r o m   t h e   R ul e   ID   V e c t o r       T h e   fo l l ow i n s t e i s   t o   c o m pa r e   t h e   s e gm e n t s   i n   t h e   m a s ke r u l e   ID   ve c t o r   a n g i v e   t h e   f i n a l   r e s ul t   in c l udi ng  w h e t h e r   t h e   ke y   m a t c h e s   t h e   rul e   da t a b a s e   a n i f   s o ,   t h e   ID   o f   t h e   r ul e .   I n   t h e   c a s e   t h e r e   i s   a   m a t c h,   i t   s t i l l   ha s   t o   go   t hr o ug h   a n o t h e r   m e m o r y   t o   c o n f i rm   a g a i n   a s   [16],   b e c a us e   of   t h e   f a l s e   po s i t i v e   r a t e .   T h e   r e - Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A l gor i t hm i c   T CA M   on   F P G A   w i t da t c o l l i s i on   appr oa c h   ( Nguy e T r i nh )   93   c o n f i r m a t i o n   i s   do n e   b e fo r e   c o m pa r i n g   t h e   p ri o ri t y   o r de r   b e c a us e   i f   c o m pa r e   t h e   p r i o r i t y   f i r s t ,   t h e r e   w i l l   b e   c a s e s   of   f a l s e   po s i t i v e   e l i m i n a t i n g   t rue   po s i t i v e s .   T h e   s t e i s   s h o w n   i F i g u r e   8 .             F i gu r e   8 .   R e - c o n f i r m a t i o n   o f   t h e   v e c t o r   t o   ge t   t h e   c o rr e c t   r e s ul t       T h e   pri o ri t y   i s   i n c l ude i n   t h e   r e c o n f i r m a t i o n   t a b l e   a n w i t h   r u l e s   s e t s   i n   l a r ge   c o n t e nt   a dd r e s s a b l e   m e m o r y   c a n   b e   h i e r a r c hi c a l l y   pr e p r i o ri t i z e b e t w e e n   r e gi o ns   t o   r e duc e   t h e   pr e s s u r e   of   c o m pa ri n p ri o r i t i e s .   A f t e r   c o m pa r i ng  t h e   pri o ri t y   a n ge t t i ng  t h e   hi g h e s t - p ri o ri t y   m a t c h ,   t h e   r e s ul t   i s   t h e   ID   o t h e   r u l e   t h a t   m a t c h e t h e   ke y   o r   s h o w   t h a t   t h e   ke y   d o e s   n o t   m a t c h .   T hi s   ID   i s   us e by   a n   e xt e rna l   da t a   m e m o r y   t o   gui de   f ur t h e r   a c t i o f o r   t h e   pa c ke t   t ha t   t i e s   w i t t h e   ke y .         3.   N U M ER I C A EX P ER I M EN TA TI O N   T h e   a l go ri t hm   i s   b ui l t   o n   F P G A   Cy c l o n e   V   D E - 10  c h i p,   us i ng  F P G A   c h i 5CS X F C6D 6F 31C6 .   T h e   m a i n   m e m o r y   r e s o ur c e   of   t h e   c h i p   i s   M 10K   m e m o r y   un i t .   T h e   m i ni m u m   l e n gt o f   a ddr e s s   b i t   t h e   M 10K   m e m o r y   s uppo r t s   i s   b i t s   (256  40)  f o r   t h e   S i m pl e   D ua l   P o r t   m o de   fo r   i n de pe n de nt   w r i t e   a nd  r e a c o n t r o l .   U s i n t hi s   m o de   e a s e s   t h e   w r i t i n g   p r o c e s s ,   a l l o w s   upda t i n g   t h e   da t a b a s e   i nt o   m e m o r y   w i t h o ut   a f f e c t i n t h e   r e a d i n g   p r o c e s s   t o   s e a r c a nd  r e t ri e v e   da t a   [23]   T h e   m e m o r y   a c c e s s   m e m o r y   s i z e   s e l e c t e fo r   s i m ul a t i o n   a n d   t e s t i ng  o n   K i t   i s   256   1 04 - b i t .   T h e   m i ni m u m   b i t   l e n gt o f   t h e   a d d r e s s   i s   c h o s e n.   T h e   c h o s e n   ke y   l e n gt i s   1 04  b i t s ,   b i t   f r a g m e n t s   t o   m a t c t h e   a dd r e s s   b i t   l e n gt h   o f   t h e   a ddr e s s .   T h e   104 - b i t   l e n g t h   i s   s ui t a b l e   fo r   pra c t i c a l   a ppl i c a t i o n s   us e i n   O pe n F l o w s   5 - t upl e   n e t w o r r o ut e r s   c o n s i s t i ng  o f :   s o ur c e   IP   a dd r e s s   (32 - b i t ),   d e s t i na t i o IP   a d d r e s s   (32 - b i t ),   s o ur c e   p o r t   (16  - b i t ) ,   d e s t i na t i o n   P o rt   (16 - b i t ),   p r o t o c o l   (8 - b i t [24] .   W i t t h e   8 - b i t   f ra g m e nt a t i o n   o pt i o n,   t h e   t o t a l   num b e of   f r a gm e nt s   i t h e   v e c t o r   i s   13   p i e c e s .   F o r   c a l c ul a t i o n   o m e m o r y   r e s o ur c e s ,   256  r u l e s   a n a s s um i ng  w i t p r o pe r   a rra n ge m e n t ,   n o   r u l e   w i t h   a l l   t h e   pi e c e   of   t h a t   r u l e   i n   a   c o l l i s i o n   s t a t e   r e qu i r e s   13  M 10K   m e m o r y   un i t s .   E a c h   u n i t   c o n t a i n s   t h e   i n f o r m a t i o n   o f   pi e c e .   T h e   pi e c e s   i n fo r m a t i o n   c o n s i s t s   o 8   b i t s   t c o n t a i n   t h e   r u l e   ID   a nd  b i t s   t o   i n di c a t e   t h e   s t a t us   o f   t h e   m e m o r y   c e l l ,   s o   10  b i t s   i t o t a l .   W i t 40  d a t a   b i t - l e n g t h   o f   M 10K   m e m o r y ,   i t   i s   po s s i b l e   t h o l a a dd i t i o na l   v e c t o r   f r a gm e n t s   w i t h o ut   c o n s um i n a n y   a ddi t i o n a l   r e s o ur c e s ,   s uppo r t i ng  1 024  rul e s B ut   t s i m pl i f y   t h e   s i m ul a t i o n   p r o c e s s ,   t h e   t e s t   o n l y   us e s   t he   f i r s t   10  b i t s   of   m e m o r y   da t a .   T h us ,   s a v i n t h e   f r a g m e nt s   o f   t h e   r u l e   ID   v e c t o r   c o n s um e s   13  M 10K .   W i t 1 f r a g m e nt s ,   f o r   di r e c t   s e a r c h i ng  i m pl e m e n t a t i o n,   13  M 10K   m e m o r i e s   a r e   us e t o   s t o r e   m a s v e c t o r s   of   r ul e s .   A l t h o ug h   t h e r e   a r e   o nl y   256  r u l e s ,   b ut   f o r   di r e c t   s e a r c h i n g ,   t o   s e a r c h   f o r   m a s v e c t o r s   i n   p a ra l l e l   w i t h   ID   v e c t o r ,   i t   i s   r e qui r e t o   b e   p e r f o r m   o n   13  p i e c e s   a t   t h e   s a m e   t i m e ,   e a c h   m e m o r y   c o n t a i n s   256  13 - b i t   of   m a s v e c t o r   da t a   o t h e   r u l e s .   T h e   r e s o ur c e s   fo r   s i m p l e   a n d i r e c t   c o n f i rm a t i o m e m o r y   a r e   13  2 56  x   125 - b i t   o f   m e m o r y .   E a c 125 - b i t   s t r i ngs   c o n s i s t s   o f   104  r ul e   da t a   b i t s ,   13  m a s b i t s   a n p r i o r i t y   b i t s .   I n   t hi s   s t e p,   52  M 10K   m e m o r y   un i t s   f o r   c o n f i r m a t i o n   a n p ri o r i t y   c o m pa ri s o n .   S i m ul a t i o n   a n s y n t h e s i s   r e s ul t s   o t h e   F P G A   ki t   s h o w e t ha t   t h e   a m o unt   o f   m e m o r y   r e s o ur c e s   c o n -   s um e i s   7 M 10K .   S i m u l a t e   t h e   r e s ul t   o t h e   t e s t b e n c h   s h o w s   a c c e pt a b l e   l a t e n c y .   T h e   de s i g w a s   r e l a t i v e l y   o pt i m i z e i n   t e rm s   o f   c l o c s pe e d,   r e s ul t i n i n   20 M H z   o t h e   F P G A   5CS X F C6D 6F 31C6  c h i p .   T h e   r e s ul t   c o n f i r m e t ha t   t h e   s t ruc t u r e   w o r ks   a s   i nt e n de i n   c o rr e s po nde n c e   w i t h   o u r   t h e o r y .   O v e r a l l   b l o c di a g r a m   o t h e   de s i g a s   s h o w n   i n   F i gu r e   9 .         Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   22 ,   N o .   1 A p r i l   20 21   :     89   -   96   94       F i gu r e   9 .   O v e r a l l   b l o c di a g ra m   o f   t h e   de s i g n       4.   R ES U LT  A N D   DISCUSSIO N   T h e   a l go ri t hm   i s   b ui l t   o n   t h e   pu r po s e   of   i m pr o v e m e n t   [17]  a n p r o v i de s   t h e   f ut ur e   de v e l o pm e n t   di -   r e c t i o n s   o f   t h e   a p pl i c a t i o n   c a p a b i l i t i e s   b a s e o n   t h e   n e e t o   i m pl e m e n t   da t a   a c c e s s   m e m o r y   t o   s uppo r t   c us t o m   v a l ue s   w i t h   a   l a r ge r   s c a l e .   B e c a us e   t h e   F P G A ’s   i nt e rna l   m e m o r y   i s   us e a n a c c e s s e m a n y   t i m e s   i n   t h e   pr o c e s s   of   s e a r c hi n g ,   t r a de - o ff  w i t h   l a t e n c y ,   t h e   pow e r   c o n s um pt i o n   o f   t h i s   a r c h i t e c t u r e   i s   l o w e r   t h a n   t ha t   of  t r a d i t i o n a l   T CA M   [17] .   I n   a dd i t i o n ,   t h e   e n t i r e   us e   of   s t a t i c   ra n do m - a c c e s s   m e m o r ( S R A M a l s gi v e s   t h e   m a x i m u m   c l o c s pe e of   t h e   s t r uc t u r e   hi g h e r   t h a t r a d i t i o na l   c o n t e n t   a dd r e s s a b l e   m e m o r y .   Co m pa r e t o   o t h e r   a l go r i t hm i c   T CA M   s t ruc t u r e s ,   o a   l a rge   s c a l e   a n o n   i ndus t r y - us e F P G A s ,   t h e   a l go ri t hm   a c hi e v e s   be t t e r   pe r f o r m a n c e   o pt i m i z a t i o n.   O n   hi gh - s pe e F P G A s   s uc h   a s   I n t e l   A rri a   a n S t ra t i s e r i e s ,   t h e   M 20K   m e m o r y   h a s   a   m i ni m u m   o f   9 - b i t   a dd r e s s   b i t   l e n gt h,   i n   [5]  ha s   d i f f i c ul t i e s   w i t h   l a r ge   i n t e rn a l   m e m o r y   c o n s um pt i o n   a n b e c a us e   i t   n e e ds   t o   a c c e s s   a   l o t   o f   m e m o r y   i n   p a r a l l e l ,   a nd  e v e r y   t i m e   a   n e w   r u l e   i s   w r i t t e i n,   a n o t h e 1 - b i t   c o l um i m e m o r y   i s   us e d.   I t   i s   d i f f i c ul t   t o   o pt i m i z e   m e m o r y   us a ge .   F o r   a   1024  104 - b i t   c o n t e n t   a dd r e s s a b l e   m e m o r y ,   b ui l di n g   o n   [5]  us e s   a n   a v e r a ge   of   302  M 20K .   T h e   p r o po s e s t r uc t u r e   do e s   n o t   c o n s um e   m o r e   M 20K   u n i t   t ha n   i n   t h e   e xa m p l e   (us i n o n l y   b i t s   of   b i t   a n d   us e   t h e   r e m a i ni n b i t   t o   w r i t e - c o p y ,   a l l o w i n t o   c h a n ge   t h e   e nt i r e   da t a b a s e   o m e m o r y   a c c e s s   w i t h o ut   a f fe c t i n t h e   r e t r i e v a l   p r o c e s s )   fo r   r ul e   ID   v e c t o r   s e a r c h .   T he   m e m o r y   s e c t i o n   c o n t a i n s   m a s v e c t o r s   a n t h e   r e c o n f i rm a t i o n   m e m o r y   c o n s um e s   t i m e s   m o r e   r e s o ur c e s ,   fo r   a   t o t a l   o f   273  M 20K   un i t s .   T h e   di f fe r e n c e   i n   r e s o ur c e   us a ge   w i l l   b e   gr e a t e r   w i t h   l o gi c a l   r u l e s   a rr a n ge m e nt ,   o pt i m i z i ng  t h e   a b i l i t y   t o   ov e r l a r u l e s   o n   s of t w a r e .   I n   a dd i t i o n,   m e m o r y   c o n t a i ni n t e rna r y   v e c t o r s   a nd  r e c e r t i f i e m e m o r y   c a n   b e   b ui l t   i n   o t h e r   w a y s   of   di r e c t   s e a r c h   a nd  w i l l   s a v e   m uc h   m o r e   r e s o ur c e s ,   w i t h   po pul a r   s e a r c h   m e t h o ds   i n s t e a o f   di r e c t   s e a r c h ,   s uc h   a s   ha s h   t a b l e s ,   b i na r y   t r e e s ,   a n b i t   v e c t o r s .   W i t h   us i ng  t h e   S R A M   T r ue   D u a l   P o r t   m o de ,   w e   h a v e   t w o   m e m o r y   a c c e s s   a s   r e a o w r i t e   pe r   c y c l e .   T h e   t hr o ug h p ut   i s   do ub l e   fo r   s e a r c hi n pu r po s e .   T h e   c o n s um e r e s o ur c e s   w o ul s t a y   t h e   s a m e   due   t da t a   w o r ds   w i dt h   i s   ha l v e c o m pa r e t o   S D P .   U pda t i n t h e   t a b l e   w o ul s l ow   t h e   t hr o ug h put   o f   t h e   a l go r i t hm i c   c o n t e n t   a dd r e s s a b l e   m e m o r y   dur i n w ri t i n c y c l e s   w h i c h   c o ul b e   f i w i t h   a n   upd a t e - c o p y   m e t h o b ut   i t   w o ul a l s o   r e qui r e   a dd i t i o na l   r e s o ur c e s .   F r a gm e n t s   b i t - l e ngt h   c o ul a l s o   b e   v a r y   b a s e o n   t h e   a p pl i c a t i o n s .   I n   r o ut e r s ,   p a r s i n g   IP   i n   t h e   r a nge   of   / 16  t o   / 24  s ub n e t   m a s w o ul m a ke   t h e   de f a ul t   8 - b i t   f ra gm e n t   b e c o m i n g   h e a vy   o n   t h e   e xpa n s i o a n d   r e s o ur c e s .   I n s t e a o f   o n e   f r a g m e nt   r e p r e s e n t s   f o r   t h e   8 - b i t   ra n ge   / 16  t o   / 24,   w e   c o ul s pl i t   i t   i nt o   t w 4 - b i t   f r a g m e nt s ,   s h o w n   i n   F i gu r e   10 .   M a n y   o t h e w a y s   o f   s e gm e n t i n t h e   b i t   s t r i de s   a ppl y   t o   di ff e r e n t   a pp l i c a t i o n s .   M a s ki n m e m o r y   s e a r c h i ng  s t e c o ul a l s o   b e   d e duc t e f r o m   t h e   s t r uc t u r e   by   i n c l ude   t h e   m a s ki n g   i n f o r m a t i o n   i n   t h e   r u l e   ID   v e c t o r   t a b l e .   E xa m p l e   i s   i l l us t ra t e i n   F i gu r e   11 .   F o r   t h e   c e l l   i n   c o l l i s i o n   o r   e m p t y   s t a t e ,   t h e r e   w o ul b e   b l a n k   m a s ki ng  i n f o r m a t i o n .   T h e   m a s k i n i n f o r m a t i o n   c o ul f ur t h e r   b e   e n c o de t o   r e duc e   m e m o r y   c o n s um pt i o n .   F o r   e xa m p l e ,   i IP v c a s e ,   t h e   r e a l - w o r l d   r ul e   s e t   c o ul b e   f o un i [25]   o n l y   h a v e   t h e   m a s ki ng   f r o m   m o s t l y   / 8.   W i t h   32 - b i t   da t a   ke y ,   4 - b i t   f r a g m e n t   n o rm a l l y   i t   w o ul r e qui r e   b i t s   t o   i n f o r m   t h e   m a s ks   (e a c b i t   f o r   e a c s e gm e n t ) .   B ut   t h e   c a s e   i s   t h a t   IP v w o ul o n l y   e i t h e r   b e   m a s i n   / 0,   / 4,   / 8,   / 12,   / 1 6,   / 20,   / 24,   / 28 ,   / 32 .   T h o s e   a r e   m a s k i n g   c a s e s ,   s o   w o ul r e qu i r e   a t   m o s t   4   b i t s   t o   r e p r e s e nt ,   w h i c h a s   h a l v e t h e   r e s o ur c e s   c o n s um pt i o n .   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A l gor i t hm i c   T CA M   on   F P G A   w i t da t c o l l i s i on   appr oa c h   ( Nguy e T r i nh )   95   T h e   s i t ua t i o n   w h e r e   ra n ge   m a t c h i n i s   n e e de c o ul b e   d o n e   w i t h   r e gi s t e r s   i n   c o m b i na t i o n   w i t h   t h e   a b ov e   s t r uc t u r e   o r   ra n ge   c o n v e r s i o n   i nt o   m a s ks   c o ul a l s o   b e   us e b ut   i t   w o ul c os t   a   huge   a m o u n t   o r e s o ur c e s .   T h e   p r o b l e m   t ha t   n e e t o   b e   c o n s i de r e w i t h   ra n ge   c o n v e r s i o n   i s   t ha t   t h e   s m a l l   ra n ge   w o ul d   c o l l i de   w i t t h e   l a rge   r a nge   d a t a ,   c a us i n g   m a n y   c o l l i s i o n   c e l l s   t o   a ppe a i n   t h e   r u l e   ID   t a b l e .   M a n y   h a s h - t a b l e   c h a i n i ng  a nd  b uc ke t   m e t h o ds   c o ul a l s o   be   i m pl e m e nt   i nt o   t h e   s t r uc t u r e   s uc h   a s   l i n e a r   c h a i n i ng  o r   b uc ke t   c e l l   r ul e   ID   t a b l e   a s   s h o w n   i n   F i gur e   12 .   O n e   i m po r t a n t   di r e c t i o n   o f   i m p r o v i n g   a l go ri t hm i c   T CA M   o n   F P G A   i s   t o   m a ke   i t   po s s i b l e   t o   be   i m -   pl e m e nt   o n   e xt e rna l   m e m o ri e s   w i t h   a n   i nt e r f a c e   t h a t   i s   f a s t   e n o ugh   t o   s uppo r t   i ndus t r y - l e v e l   r e qui r e m e nt .   T he   e xt e r na l   m e m o r y   c o ul be   D D R ,   H B M   o r   e ve n   e S RA M .             F i gu r e   10 .   S p l i t t i ng  t h e   o ri gi na l   8 - b i t   f ra g m e nt   i n t o   t w o   4 - b i t   f r a gm e n t s               F i gu r e   11 .   T h e   m a s k   v e c t o r   i n f o r m a t i o n   i s   i n c l ude w i t t h e   d a t a b a s e   t h a t   i s   us e d   t o   s e a r c m a t c v e c t o r     F i gu r e   12 .   M a n y   t e c hn i que s   t h a t   a r e   us e i n   ha s h - t a b l e   s e a r c hi n g   c o ul a l s o   b e   a ppl i e t o   t h e   p r o po s e s t ruc t u r e       5.   C O N C LU S I O N   T h e   pa pe r   p r e s e n t s   a   s t r uc t u r e   o R A M - b a s e d   T CA M   o n   F P G A .   It   ha s   a dv a n t a ge s   i n   s c a l a b i l t y   a n i n t e g r a t i o n   c o m pa r e   t o   t r a d i t i o na l   T CA M s .   I t s   f un c t i o n   ha s   b e e n   i m p r o v e a n r e s o ur c e   c o n s um pt i o n   i s   m o r e   o pt i m i z e c o m pa r e   t o   o t h e r   F P G A - b a s e T CA M   s t r uc t u r e .   W e   h o pe   t o   a c h i e v e   f ur t h e r   i m p r o v e m e n t s   of  FPGA - b a s e T CA M   de s i g n   a n d   e v e n   ge n e ra l   T CA M   i t h e   f ut u r e .         A C K N O WL ED G E M EN TS   T h i s   r e s e a r c h   i s   f un de by   H o   Ch i   M i nh  Ci t y   U n i v e r s i t y   of   T e c h n o l o g y - V N U - H CM   un de r   g ra n t   n u m b e r   T - ĐĐ T - 2020 - 4 4.   W e   g r a t e f ul l y   a c kn o w l e dg e   t h e i r   s uppo r t .       R EF ER EN C ES   [ 1]   T R W   C o m put e r   D i v i s i o A r c hi v e d   A ug us t   5 ,   2011 ,   a t   t he   W a y ba c k   M a c hi ne ,   p .   1 7,   19 63 .   [ 2]   H uc a b y ,   D a v i d ,   C C N P   B C M S N   e x a m   c e r t i f i c a t i o n   g ui de :   C C N P   s e l f - s t udy ,   C i s c o   P r e s s ,   200 4.     [ 3]   P a g i a m t z i s ,   K o s t a s ,   a nd  A l i   S he i kho l e s l a m i .   C o nt e n t - a dd r e s s a bl e   m e m o r y   ( C A M )   c i r c ui t s   a n a r c hi t e c t ur e s :   A   t ut o r i a l   a nd   s u r v e y .   I E E E   j our nal   o f   s o l i d - s t a t e   c i r c u i t s ,   v o l .   4 1,   no .   3 ,   pp .   712 - 72 7,   20 06.     [ 4]   D .   V .   G a r r o ,   C .   V .   C a l d e r o   ́n   a nd   C .   S .   Y e u ng ,   U s i ng   a   pr o g r a m m a bl e   ne t w o r s w i t c T C A M   t o   f i nd  t h e   b e s t   a l i g nm e nt   o f   t w o   D N A   s e que nc e s ,   201 I E E E   36 t C e nt r al   A m e r i c an  an P anam C onv e nt i on  ( C O N C A P A N   X X X V I ) ,   San   J os e ,   pp .   1 - 5,   201 6.     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   22 ,   N o .   1 A p r i l   20 21   :     89   -   96   96   [ 5]   Z .   U l l a h ,   M .   K .   J a i s w a l ,   Y .   C .   C ha a nd  R .   C .   C .   C he ung ,   F P G A   I m pl e m e nt a t i o o f   S R A M - ba s e d   T e r n a r y   C o nt e nt   A ddr e s s a b l e   M e m o r y ,   2012  I E E E   26t I nt e r na t i ona l   P ar al l e l   a nd  D i s t r i bu t e P r oc e s s i n Sy m pos i um   W or k s hops   &   P hD   F or um ,   Sha ngha i ,   p p.   38 3 - 389 ,   2 012 .     [ 6]   C hi o u,   D e r e k T he   m i c r o s o f t   c a t a pul t   p r o j e c t , ”  2 017  I E E E   I n t e r nat i o nal   Sy m p os i um   on  W or k l oad   C har a c t e r i z a t i on  ( I I SW C ) .   I E E E ,   20 17.     [ 7]   S o t i r i a d e s ,   E ur i pi de s ,   C hr i s t o s   K o z a ni t i s ,   a nd  A po s t o l o s   D o l l a s F P G A   ba s e a r c hi t e c t u r e   f o r   D N A   s e -   que nc e   c om pa r i s o a nd  da t a b a s e   s e a r c h, ”  P r oc e e di ng s   20 t I E E E   I n t e r nat i ona l   P ar a l l e l   &   D i s t r i bu t e P r oc e s s i ng   Sy m pos i um .   I E E E ,   200 6.     [ 8]   M .   I r f a n,   Z .   U l l a a nd  R .   C .   C .   C he ung ,   D - T C A M :   A   H i g h - P e r f o r m a nc e   D i s t r i b ut e R A M   B a s e T C A M   A r c hi t e c t ur e   o F P G A s ,   i n   I E E E   A c c e s s ,   v o l .   7 ,   pp .   9606 0 - 96069 ,   2019 .     [ 9]   U l l a h,   A ne e s ,   e t   a l . ,   B P R - T C A M - B l oc a nd  P a r t i a l   R e c o nf i g ur a t i o ba s e T C A M   o X i l i nx  F P G A s .   E l e c t r o ni c s   v o l .   9,   no .   2 ,   p .   353 ,   202 0.     [ 10]   R e v i r i e g o ,   P e d r o ,   A ne e s   U l l a h ,   a nd   S a l v a t o r e   P o nt a r e l l i ,   P R - T C A M :   E f f i c i e nt   T C A M   e m ul a t i o o X i l i nx  F P G A us i ng   pa r t i a l   r e c o nf i g ur a t i o n, ”  I E E E   T r a ns a c t i on s   on  V e r y   L ar ge   Sc al e   I n t e gr at i o ( V L SI )   S y s t e m s ,   v o l .   27,   no .   8 pp.   19 52 - 1956 ,   201 9.     [ 11]   P a ni g r a hy ,   R i na ,   a nd  S a m a r   S h a r m a .   R e duc i ng   T C A M   po w e r   c o ns um pt i o a n i nc r e a s i ng   t h r o ug hput .   P r oc e e di ngs   1 0t S y m po s i um   o H i gh   P e r f or m an c e   I n t e r c o nne c t s .   I E E E ,   2 002 .     [ 12]   N.   U.   R e hm a n ,   O.   M u j a h i d ,   M.   I r f a n,   A.   H a f e e z a ndZ .   U l l a h ,   L o w   P o w e r   P r e - c o m pa r i s o n   C o nf i g ur a t i o n   S t r a t e gy   f o r   a   L og i c - ba s e B i na r y   C A M   o F P G A ,   2019  Se c ond  I nt e r n at i ona l   C on f e r e nc e   on  L at e s t   t r e nds   i E l e c t r i c a l   E ngi ne e r i n and   C om pu t i ng   T e c hno l og i e s   ( I N T E L L E C T ) ,   K a r ac h i ,   P ak i s t an,   p p.   1 - 5,   2 019 .     [ 13]   Z .   Q i a n   a n M .   M a r g a l a ,   L o w   po w e r   R A M - ba s e d   h i e r a r c hi c a l   C A M   o F P G A ,   201 I nt e r n at i on al   C on f e r e nc e   on  R e C onF i gu r ab l e   C om pu t i ng   and   F P G A s   ( R e C onF i g14) ,   C a nc un ,   pp.   1 - 4 ,   2014 .     [ 14]   U l l a h,   I na y a t ,   Z a h i U l l a h ,   a nd  J e o ng - A .   L e e ,   E E - T C A M :   A E ne r gy - Ef f i c i e nt   S R A M - B a s e T C A M   o F P G A , ”  E l e c t r o n i c s ,   v o l .   7 ,   no .   9 p .   1 86 ,   2 018 .     [ 15]   U l l a h,   I na y a t ,   Z a h i d   U l l a a nd   J e o ng - A   L e e ,   E f f i c i e n t   T C A M   D e s i g B a s e o M u l t i pum p i ng - E na b l e d   M ul t i po r t e d   S R A M   o F P G A , ”  I E E E   A c c e s s ,   v o l .   6 ,   p p.   19 940 - 199 47,   20 18.     [ 16]   W .   J i a ng ,   S c a l a b l e   T e r na r y   C o nt e nt   A ddr e s s a b l e   M e m o r y   i m pl e m e n t a t i o us i ng   F P G A s ,   A r c h i t e c t ur e s   f o r   N e t w or k i ng   and   C om m u ni c at i o ns   Sy s t e m s ,   S an  J os e ,   C A ,   pp .   7 1 - 82,   201 3.     [ 17]   Y .   S a t o ,   K .   O t s u ka ,   K .   K o ba y a s hi ,   T .   K o uc hi ,   M .   U w a i   a nd  M .   N i s h i z a w a ,   N o v e l   a pp r o a c f o r   s e a r c e ng i n e ,   2016  11 t I nt e r na t i ona l   M i c r os y s t e m s ,   P ac k ag i ng ,   A s s e m bl y   an d   C i r c u i t s   T e c hno l og y   C onf e r -   e nc e   ( I M P A C T ) ,   T ai pe i ,   201 6,   p p.   6 9 - 7 2.   P r oc e e di ng s   20 t I E E E   I n t e r na t i o na l   P ar al l e l   &   D i s t r i b ut e P r oc e s s i ng  S y m pos i um ,   R hode s   I s l an d,   pp .   8,   2 006 .   [ 18]   L i ,   X i a nf e ng ,   Y ua nxi L i n,   a nd   W e nj un  L i .   G r e e nT C A M :   A   m e m o r y   a n e ne r gy   e f f i c i e nt   T C A M   ba s e p a c ke t   c l a s s i f i c a t i o n.   2 016  I nt e r n at i on al   C o nf e r e nc e   on  C om pu t i ng,   N e t w or k i n and  C om m uni c a t i o ns   ( I C N C ) .   I E E E 2016 .     [ 19]   W .   Y u,   S .   S i v a kum a r   a nd  D .   P a o ,   P s e u do - T C A M :   S R A M - B a s e d   A r c hi t e c t u r e   f o r   P a c ke t   C l a s s i f i c a -   t i o i O ne   Me m o r y   A c c e s s   i n   I E E E   N e t w or k i ng   L e t t e r s ,   v o l .   1,   no .   2,   p p.   89 - 92 20 19 .     [ 20]   S y e d,   F a r kha n da   U l l a h ,   D r .   Z a h i J a i s w a l ,   M a ni s h,   F a s t   C o nt e n t   U pda t i ng   A l go r i t hm   f o r   a S R A M   ba s e T C A M   o F P G A .   I E E E   E m be dde Sy s t e m s   L e t t e r s .   pp 1 - 1 20 17 .     [ 21]   R e v i r i e g o ,   P e dr o ,   M ul t i pl e   H a s M a t c hi ng   U ni t s   ( M H M U ) :   A A l go r i t hm i c   T e r na r y   C o nt e nt   A d -   dr e s s a b l e   M e m o r y   D e s i g f o r   F i e l P r o g r a m m a b l e   G a t e   A r r a y s , ”  2018  I E E E   19t I n t e r na t i ona l   C on f e r e nc e   on  H i gh   P e r f or m a nc e   Sw i t c hi ng   and   R o ut i ng   ( H P SR ) .   I E E E ,   201 8.     [ 22]   V .   S r i n i v a s a a nd  G .   V a r g he s e .   F a s t   a ddr e s s   l o o kups   us i ng   c o nt r o l l e p r e f i x   e x pa n s i o n,   A C M   T r a ns .   C om p ut .   Sy s t . ,   v o l .   17 ,   no .   1,   pp .   1 - 40 ,   1 999   [ 23]   E m be dde M e m o r y   ( R A M :   1 - P O R T ,   R A M :   2 - P O R T ,   R O M :   1 - P O R T ,   a nd  R O M :   2 - P O R T )   U s e r   G ui de   ht t ps : / / w w w . i n t e l . c o m / c o nt e nt / da m / w w w / p r o g r a m m a bl e / us / e n/ p df s / l i t e r a t u r e / ug / ug   r a m   r o m . pdf     [ 24]   N y g r e n,   A nde r s ,   O p e nf l o w   s w i t c h   s p e c i f i c a t i o n   v e r s i o 1 . 5 .   1.   O pe N e t w or k i n F ound at i on ,   T e c h.   R e p ,   20 15.     [ 25]   ht t p: / / bg p. po t a r o o . ne t / a s 2. 0/ bg p - a c t i v e . ht m l     Evaluation Warning : The document was created with Spire.PDF for Python.