I n t e r n a t i o n a l   J o u r n a l   o f   R e c o n f i g u r a b l e   a n d   E m b e d d e d   S y s t e m s   ( I J R E S )   V o l .   1 ,   N o .   1 ,   M a r c h   2 0 1 2 ,   p p .   1 9 ~ 2 4   I S S N :   2 0 8 9 - 4 8 6 4             1 9       J o u r n a l   h o m e p a g e :   h t t p : / / i a e s j o u r n a l . c o m / o n l i n e / i n d e x . p h p / I J R E S   A   N o v e l   F P G A   b a s e d   L e a d i n g   O n e   A n t i c i p a t i o n   A l g o r i t h m   f o r   F l o a t i n g   P o i n t   A r i t h m e t i c   U n i t s       A s h w i n i   S .   D e s h m u k h   D e p a r t m e n t   o f   E l e c t r o n i c s   a n d   T e l e c o m m u n i c a t i o n ,   Bh a g a w a t i   Ch a t u r v e d i   Co l l e g e   o f   E n g i n e e r i n g ,   N a g p u r       A r t i c l e   I n f o     A B S T R A C T   A r t i c l e   h i s t o r y :   R e c e i v e d   J a n   2 2 ,   2 0 1 2   R e v i s e d   M a r   1 8 ,   2 0 1 2   A c c e p t e d   M a r   2 3 ,   2 0 1 2       I n   m u l t i m e d i a   S y s t e m s - o n - Ch i p s ,   t h e   d e s i g n   o f   s p e c i a l i z e d   I E E E - 7 5 4 - c o m p l i a n t   f l o a t i n g   p o i n t   a r i t h m e t i c   u n i t s   ( F P U )   i s   c r i t i c a l   w i t h   r e s p e c t   t o   b o t h   o p e r a t i n g   s p e e d   a n d   s i l i c o n   a r e a   d e m a n d .   L e a d i n g   o n e   a n t i c i p a t i o n   i s   a   w e l l - k n o w n   i s s u e   i n   t h e   i m p l e m e n t a t i o n   o f   h i g h   s p e e d   F P U s .   W e   i n v e s t i g a t e d   a   n o v e l   l e a d i n g   o n e   a n t i c i p a t i o n   a l g o r i t h m   a l l o w i n g   u s   t o   s i g n i f i c a n t l y   r e d u c e   t h e   a n t i c i p a t i o n   f a i l u r e   r a t e   w i t h   r e s p e c t   t o   t h e   s t a t e - o f   t h e   a r t .   W e   e m b e d d e d   o u r   t e c h n i q u e   i n t o   a   c o m p l e t e   F P U   a n d   c o m p a r e d   i t s   p e r f o r m a n c e   a g a i n s t   e x i s t i n g   s o l u t i o n s ,   d e f i n i t e l y   s h o w i n g   b o t h   a r e a   s a v i n g s   a n d   t o t a l   l a t e n c y   r e d u c t i o n .   K e y w o r d :   f l o a t i n g   p o i n t   a r i t h m e t i c   u n i t s   I E E E - 7 5 4   l e a d i n g   o n e   a n t i c i p a t i o n   m u l t i m e d i a   s y s t e m s - o n - Ch i p s     Co p y r i g h t   ©   2 0 1 2   I n s t i t u t e   o f   A d v a n c e d   E n g i n e e r i n g   a n d   S c i e n c e .     A l l   r i g h t s   r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   M i s s .   A s h w i n i   S .   D e s h m u k h   D e p a r t m e n t   o f   E l e c t r o n i c s   a n d   T e l e c o m m u n i c a t i o n ,     B h a g a w a t i   C h a t u r v e d i   C o l l e g e   o f   E n g i n e e r i n g ,   N a g p u r   c / o   M r .   H i t e s h   M .   T u p k a r i ,   1 4 8   D a t t a t r a y a   N a g a r ,   N a g p u r -   2 4   P h o n e   N o :   8 7 9 3 6 6 2 1 3 5   E m a i l :   a s _ d e s h m u k h @ r e d i f f m a i l . c o m       1 .   I N T R O D U C T I O N   T h e   i n c r e a s e d   i n t e r e s t   i n   A S I C s   a n d   S o C s   f o r   m u l t i m e d i a   a p p l i c a t i o n s   j u s t i f i e s   t h e   e f f o r t   i n   t h e   d e s i g n   o f   h i g h - s p e e d   a r i t h m e t i c   u n i t s   w h e r e   e i t h e r   f i x e d   o r   f l o a t i n g - p o i n t   r e a l   n u m b e r   r e p r e s e n t a t i o n s   a r e   e x p l o i t e d   f o r   c a l c u l a t i o n s .   I n   p a r t i c u l a r ,   h i g h - t h r o u g h p u t   f l o a t i n g - p o i n t   s i g n e d   a d d e r s   ( F A D D )   l e n d   t h e m s e l v e s   t o   a   s o p h i s t i c a t e d   d e s i g n   a p p r o a c h   d u e   t o   b o t h   t h e   a m o u n t   a n d   c o m p l e x i t y   o f   t h e   r e q u i r e d   o p e r a t i o n s   ( o p e r a n d s   a l i g n m e n t ,   a d d i t i o n ,   r e n o r m a l i z a t i o n   a n d   r o u n d i n g ) .   I n   c a s e   o f   e f f e c t i v e   s u b t r a c t i o n   ( s u b t r a c t i o n   o f   o p e r a n d s   w e i t h   t h e   s a m e   s i g n   o r   a d d i t i o n   o f   o p e r a n d s   w i t h   d i f f e r e n t   s i g n s ) ,   t h e   n u m b e r   o f   l e a d i n g   d i g i t s   i n   t h e   o u t p u t   m u s t   b e   c a l c u l a t e d   t o   i n i t i a t e   t h e   r e n o r m a l i z a t i o n   p r o c e d u r e .   S i n c e   r e n o r m a l i z a t i o n   o c c u p i e s   t h e   d o m i n a n t   p o r t i o n   o f   a n   F P   a d d i t i o n ,   p e r f o r m i n g   t h e   l e a d i n g   d i g i t s   c a l c u l a t i o n   a f t e r   t h e   a d d i t i o n   i s   i n e f f e c t i v e   a n d   s o m e   r e l i a b l e   a n t i c i p a t i o n   l o g i c   m u s t   b e   d e v i s e d   f o r   p a r a l l e l   a n t i c i p a t i o n   o f   t h e   p o s i t i o n   o f   t h e   f i r s t   s i g n i f i c a n t   d i g i t .   F o r   p r a c t i c a l   i m p l e m e n t a t i o n s ,   w h e n   b o t h   l e a d i n g   z e r o e s   a n d   o n e s   m a y   o c c u r ,   e i t h e r   c a s e   c a n   b e   h a n d l e d   b y   a   s e p a r a t e   a n t i c i p a t o r   [ 2 ] [ 3 ] .     I n   m o d e r n   h a r d w a r e   a p p l i c a t i o n s ,   l a t e n c y   i s   t h e   m o s t   i m p o r t a n t   p a r a m e t e r   f o r   m o s t   o p e r a t i o n s .   W h i l e   d e s i g n i n g   f o r   F P G A   d e v i c e s   w i t h   m i l l i o n s   o f   r e c o n f i g u r a b l e   h a r d w a r e   g a t e s ,   a r e a   c a n   b e   g i v e n   u p   t o   g a i n   o v e r a l l   l a t e n c y .   P i p e l i n i n g   i s   a n o t h e r   t e c h n i q u e   u s e d   t o   i n c r e a s e   t h e   o v e r a l l   t h r o u g h p u t   o f   t h e   a d d e r   b u t   d o e s n t   d e c r e a s e   t h e   l a t e n c y .   I n   t h i s   c h a p t e r ,   p i p e l i n i n g   a n d   i t s   e f f e c t s   o n   f a r   a n d   c l o s e   d a t a - p a t h   a d d e r   i m p l e m e n t a t i o n   w i l l   a l s o   b e   d i s c u s s e d .       2 .   L E A D I N G   O N E   P R E D I C T O R   A L G O R I T H M   I n   t h i s   s e c t i o n ,   L O P   i m p l e m e n t a t i o n   a n d   i t s   u s e   i n   f l o a t i n g - p o i n t   a d d i t i o n   i s   d e s c r i b e d   i n   d e t a i l .   L O P   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 6 4   I J R E S     V o l .   1 ,   N o .   1 ,     M a r c h   2 0 1 2   :     1 9     2 4   2 0 m o d u l e   i s   a l s o   u s e d   i n   f a r   a n d   c l o s e   d a t a - p a t h   a l g o r i t h m   i m p l e m e n t a t i o n .   L O P   i s   u s e d   t o   p r e d i c t   t h e   l e a d i n g   o n e   i n   p a r a l l e l   w i t h   t h e   a d d e r   c o m p u t a t i o n .   T h i s   d e c r e a s e s   t h e   n u m b e r   o f   l o g i c   l e v e l s   i n   t h e   c r i t i c a l   p a t h   a n d   r e s u l t s   i n   a n   o v e r a l l   i m p r o v e m e n t   i n   t h e   l a t e n c y .     2 . 1 .   L e a d i n g   O n e   P r e d i c t o r   T h e   L O P   c o n s i s t s   o f   t w o   o p e r a t i o n s   [ 4 ,   5 ] :     P r e - e n c o d i n g   t h e   i n p u t s     L e a d i n g   o n e   d e t e c t i o n   P a r a l l e l ,   l e a d i n g   o n e   d e t e c t i o n   a n d   c o r r e c t i o n   a d d s   a r e a   t o   t h e   d e s i g n   b u t   d e c r e a s e s   t h e   o v e r a l l   l a t e n c y   o f   t h e   m o d u l e   b y   r e d u c i n g   l e v e l s   o f   l o g i c .   F o r   a   s i n g l e - p r e c i s i o n   f l o a t i n g - p o i n t   a d d i t i o n   o p e r a t i o n ,   a   2 4 - b i t   L O P   i s   n e e d e d .   A   a n d   B   a r e   t h e   t w o   i n p u t s ,   t h e   l e a d i n g   o n e   p r e d i c t o r   d e s i g n e d   i s   f o r   A   >   B   a n d / o r   A   <   B .   T h i s   i s   n e e d e d   b e c a u s e   e v e n   a f t e r   p r e - n o r m a l i z a t i o n ,   t h e   r e s u l t i n g   a d d i t i o n   c a n   b e   n e g a t i v e   a s   i n   c a s e   o f   A   <   B .   W h e n   t h e   e f f e c t i v e   o p e r a t i o n   i s   a d d i t i o n ,   t h e   L O P   r e s u l t   i s   n o t   u s e d   a n d   t h e   s h i f t   v a l u e   i s   a l w a y s   z e r o .   T h e   g e n e r a l   s t r u c t u r e   i s   s h o w n   i n   F i g u r e   1 .       F i g u r e   1 .   G e n e r a l   s t r u c t u r e   o f   L O P     2 . 2 .   P r e - E n c o d i n g   L o g i c   T h e   p r e - e n c o d i n g   m o d u l e   g i v e s   a   s t r i n g   o f   0 s   a n d   1 s   w i t h   t h e   l o c a t i o n   o f   t h e   f i r s t   o n e   b e i n g   t h e   l e a d i n g   o n e   p o s i t i o n .   A f t e r   t h i s ,   t h e   l e a d i n g   o n e   d e t e c t o r   a l r e a d y   d e s i g n e d   f o r   s t a n d a r d   a l g o r i t h m   i s   u s e d   t o   c o m p u t e   t h e   p o s i t i o n   o f   t h e   m o s t   s i g n i f i c a n t   b i t .   T h i s   i s   t h e   a m o u n t   w e   n e e d   t o   s h i f t   f o r   n o r m a l i z a t i o n ,   i n   c a s e   o f   n o   c o r r e c t i o n .   T h e   p r e - e n c o d i n g   m o d u l e   a l s o   g i v e s   s t r i n g s   o f   s y m b o l s ,   w h i c h   a r e   p a s s e d   t h r o u g h   t h e   b i n a r y   t r e e   t o   d e t e r m i n e   i f   c o r r e c t i o n   i s   n e e d e d .   A   o n e   i s   a d d e d   t o   t h e   l e a d i n g   o n e   p o s i t i o n   i f   a   c e r t a i n   s t r i n g   o f   s y m b o l s   i s   i d e n t i f i e d .   I n   o r d e r   t o   g e t   t h e   s t r i n g   o f   0 s   a n d   1 s ,   t o   p a s s   t h r o u g h   t h e   L O D .     2 . 3 .   L e a d i n g   O n e   D e t e c t o r   A f t e r   t h e   a d d i t i o n ,   t h e   n e x t   s t e p   i s   t o   n o r m a l i z e   t h e   r e s u l t .   T h e   f i r s t   s t e p   i s   t o   i d e n t i f y   t h e   l e a d i n g   o r   f i r s t   o n e   i n   t h e   r e s u l t .   T h i s   r e s u l t   i s   u s e d   t o   s h i f t   l e f t   t h e   a d d e r   r e s u l t   b y   t h e   n u m b e r   o f   z e r o s   i n   f r o n t   o f   t h e   l e a d i n g   o n e .   I n   o r d e r   t o   p e r f o r m   t h i s   o p e r a t i o n ,   s p e c i a l   h a r d w a r e ,   c a l l e d   L e a d i n g   O n e   D e t e c t o r   ( L O D )   o r   L e a d i n g   Z e r o   C o u n t e r   ( L Z C ) ,   h a s   t o   b e   i m p l e m e n t e d .   T h e r e   a r e   a   n u m b e r   o f   w a y s   o f   d e s i g n i n g   a   c o m p l e x   a n d   c o m p l i c a t e d   c i r c u i t   s u c h   a s   L O D .   A   c o m b i n a t i o n a l   a p p r o a c h   i s   a   c o m p l e x   p r o c e s s   b e c a u s e   e a c h   b i t   o f   t h e   r e s u l t   i s   d e p e n d a n t   o n   a l l   t h e   i n p u t s .   T h i s   a p p r o a c h   l e a d s   t o   l a r g e   f a n - i n   d e p e n d e n c i e s   a n d   t h e   r e s u l t i n g   d e s i g n   i s   s l o w   a n d   c o m p l i c a t e d .   A n o t h e r   a p p r o a c h   i s   u s i n g   B o o l e a n   m i n i m i z a t i o n   a n d   K a r n a u g h   m a p ,   b u t   t h e   d e s i g n   i s   a g a i n   c u m b e r s o m e   a n d   u n o r g a n i z e d .   T h e   c i r c u i t   c a n   a l s o   b e   e a s i l y   d e s c r i b e d   b e h a v i o r a l l y   u s i n g   V H D L   a n d   t h e   r e s t   c a n   b e   l e f t   t o   Q u a r t u s I I   o r   a n y   s y n t h e s i s   t o o l .   I n   o u r   f l o a t i n g - p o i n t   a d d e r   d e s i g n ,   w e   u s e d   t h e   L O D   d e s i g n   w h i c h   i d e n t i f i e s   c o m m o n   m o d u l e s   a n d   i m p o s e s   h i e r a r c h y   o n   t h e   d e s i g n .   A s   c o m p a r e d   t o   o t h e r   o p t i o n s ,   t h i s   d e s i g n   h a s   l o w   f a n - i n   a n d   f a n - o u t   w h i c h   l e a d s   t o   a r e a   a n d   d e l a y   e f f i c i e n t   d e s i g n   [ 6 ]   f i r s t   p r e s e n t e d   b y   O k l o b d z i j a   i n   1 9 9 4 .     2 . 3 . 1 .   O k l o b d z i j a s   L O D   T h e   f i r s t   s t e p   i n   t h e   d e s i g n   p r o c e s s   i s   t o   e x a m i n e   t w o   b i t s   c a s e   s h o w n   i n   T a b l e 1 . T h e   m o d u l e   i s   n a m e d   a s   L O D 2 .   T h e   p a t t e r n   s h o w s   t h e   p o s s i b l e   c o m b i n a t i o n s .   I f   t h e   l e f t   m o s t   b i t   i s   1 ,   t h e   p o s i t i o n   b i t   i s   a s s i g n e d   0   a n d   t h e   v a l i d   b i t   i s   a s s i g n e d   1 .   T h e   p o s i t i o n   b i t   i s   s e t   t o   1   i f   t h e   s e c o n d   b i t   i s   1   a n d   t h e   f i r s t   b i t   i s   0 .   T h e   v a l i d   b i t   i s   s e t   t o   0   i f   b o t h   t h e   b i t s   a r e   0 .   T h e   l o g i c   f o r   L O D 2   i s   s t r a i g h t f o r w a r d   a n d   s h o w n   i n   F i g u r e   2 .   T h e   s a m e   c o n c e p t   i s   u s e d   t o   i m p l e m e n t   L O D 8 ,   L O D 1 6 ,   a n d   L O D 3 2   m o d u l e s .   U s i n g   t h e   a b o v e   d e s i g n e d   m o d u l e s ,   t h e   l e a d i n g   o n e   d e t e c t o r   t a k e s   t h e   s h a p e   a s   s h o w n   i n   F i g u r e   3 .   T h e   i n p u t   t o   t h e   L O D   f o r   s i n g l e - p r e c i s i o n   f l o a t i n g   p o i n t   a d d e r   i s   t h e   f i r s t   2 4   b i t s   o f   t h e   r e s u l t   c o m i n g   o u t   o f   t h e   i n t e g e r   a d d e r .   T w e l v e   L O D 2 s ,   s i x   L O D 4 s ,   t h r e e   L O D 8 s ,   Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E S   I S S N :   2 0 8 9 - 4 8 6 4       A   N o v e l   F P G A   b a s e d   L e a d i n g   O n e   A n t i c i p a t i o n   A l g o r i t h m   f o r   F l o a t i n g   P o i n t   .   ( A s h w i n i   S .   D e s h m u k h )   2 1 t w o   L O D 1 6 s ,   a n d   o n e   L O D 3 2   a r e   i m p l e m e n t e d   i n   p a r a l l e l   t o   g e t   t h e   p o s i t i o n   o f   t h e   f i r s t   l e a d i n g   o n e   i n   t h e   a d d e r   r e s u l t .       T a b l e   1 .   T r u t h   t a b l e   f o r   L O D 2   P a t t e r n   P o s i t i o n   B i t   V a l i d   B i t   1 x   0   1   0 1   1   1   0 0   x   0         F i g u r e   2 :   H a r d w a r e   i m p l e m e n t a t i o n   f o r   L O D 2         F i g u r e   3 :   L O D   i m p l e m e n t a t i o n     T h e   b e h a v i o r a l   m o d e l   w a s   i m p l e m e n t e d   u s i n g   c a s e   s t a t e m e n t s   i n   V H D L   d e f i n i n g   e a c h   p o s s i b i l i t y   b e h a v i o r a l l y .       2 . 3 . 2 .   L e f t   S h i f t   B a r r e l   S h i f t e r   U s i n g   t h e   r e s u l t s   f r o m   t h e   L O D ,   t h e   r e s u l t   f r o m   t h e   a d d e r   i s   s h i f t e d   l e f t   t o   n o r m a l i z e   t h e   r e s u l t .   T h a t   m e a n s   n o w   t h e   f i r s t   b i t   i s   1 .   T h i s   s h i f t e r   c a n   b e   i m p l e m e n t e d   u s i n g   s h l   o p e r a t o r   i n   V H D L   o r   b y   d e s c r i b i n g   i t   b e h a v i o r a l l y   u s i n g   c a s e   s t a t e m e n t s .     T h e   b e h a v i o r a l   m o d e l   h a d   a   n e g l i g i b l y   s m a l l e r   c o m b i n a t i o n a l   d e l a y ,   a n d   s m a l l e r   a r e a ,   a n d   i s   t h e r e f o r e   u s e d   i n   o u r   i m p l e m e n t a t i o n .     F o r   a   s i n g l e   p r e c i s i o n   f l o a t i n g - p o i n t   a d d e r   t h e   m a x i m u m   a m o u n t   o f   l e f t   s h i f t   n e e d e d   i s   2 7 .   T h e   h a r d w a r e   f o r   t h e   b e h a v i o r a l   l e f t   s h i f t e r   i s   d e s i g n e d   t o   o n l y   a c c o m m o d a t e   t h e   m a x i m u m   s h i f t   a m o u n t .   A s   w e   h a v e   n o   c o n t r o l   o v e r   t h e   h a r d w a r e   i m p l e m e n t a t i o n   i n   V H D L   s h i f t e r ,   i t   i m p l e m e n t s   h a r d w a r e   f o r   s h i f t   a m o u n t s   g r e a t e r   t h a n   2 7 ,   t h u s   r e s u l t i n g   i n   b i g g e r   a r e a   a n d   d e l a y   c o m p a r e d   t o   b e h a v i o r a l   s h i f t e r .   I n   t h i s   c a s e   t h i s   o p e r a t i o n   i s   d o n e   i n   p a r a l l e l   t o   a d d i t i o n   a n d   t h u s   d e c r e a s e s   l e v e l s   o f   l o g i c   i n   t h e   c r i t i c a l   p a t h .     2 . 4 .   P o s t - n o r m a l i z a t i o n   I n   c a s e   o f   f a r   p a t h ,   o n l y   1   b i t   l e f t   o r   r i g h t   s h i f t   i s   n e e d e d .   1 - b i t   r i g h t   s h i f t   i s   d o n e   i f   t h e   r e s u l t   f r o m   t h e   a d d e r   i s   n o t   n o r m a l i z e d   a n d   t h e   e f f e c t i v e   o p e r a t i o n   i s   a d d i t i o n .   O n   t h e   o t h e r   h a n d ,   1   b i t   l e f t   s h i f t   i s   n e e d e d   i f   t h e   m o s t   s i g n i f i c a n t   b i t   o f   t h e   r e s u l t   i s   0   a n d   s u b t r a c t i o n   w a s   c a r r i e d   o u t .   T h i s   i s   a   b i g   r e d u c t i o n   i n   t h e   c r i t i c a l   p a t h   i n   t e r m s   o f   l a t e n c y   w h e n   c o m p a r e d   t o   s t a n d a r d   o r   L O P   a l g o r i t h m   i m p l e m e n t a t i o n s .   I n   c a s e   o f   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 6 4   I J R E S     V o l .   1 ,   N o .   1 ,     M a r c h   2 0 1 2   :     1 9     2 4   2 2 r i g h t   s h i f t ,   o n e   i s   a d d e d   t o   t h e   l a r g e r   e x p o n e n t   t o   o b t a i n   e x p o n e n t   o u t ,   o n   t h e   o t h e r   h a n d ,   o n e   i s   s u b t r a c t e d   f r o m   t h e   l a r g e r   e x p o n e n t   i n   c a s e   o f   l e f t   s h i f t .       3 .   R T L   V I E W :   T h e   R T L   V i e w   o f   t h e   L e a d i n g   O n e   P r e d i c t o r   a n d   P o s t n o r m a l i z a t i o n   b l o c k   i s   s h o w n   i n   F i g u r e   4 .   T h e   F l o a t i n g   P o i n t   A d d e r   i s   d e s i g n e d   a n d   i m p l e m e n t e d   u s i n g   Q u a r t u s I I   b y   D e v i c e :   C y c l o n e :   E P 1 C 4 F 4 0 0 C 8       F i g u r e   4 .   R T L   V i e w   o f   t h e   L e a d i n g   O n e   P r e d i c t o r   a n d   P o s t n o r m a l i z a t i o n   b l o c k       4 .   T I M I N G   A N D   A R E A   A N A L Y S I S   T h e   L O P   f l o a t i n g   p o i n t   a d d e r   i s   s y n t h e s i z e d ,   p l a c e d   a n d   r o u t e d   f o r   C y c l o n e :   E P 1 C 4 F 4 0 0 C 8   F P G A   d e v i c e   u s i n g   Q u a r t u s I I .   T h e   m i n i m u m   c l o c k   p e r i o d   r e p o r t e d   b y   t h e   s y n t h e s i s   t o o l   a f t e r   p l a c i n g   a n d   r o u t i n g   i s   3 . 6 3 6   n s .   T h e   l e v e l s   o f   l o g i c   c e l l s   r e p o r t e d   a r e   3 2 / 4 , 0 0 0   ( < 1 % ) .   T h a t   m e a n s   t h e   m a x i m u m   c l o c k   s p e e d   t h a t   c a n   b e   a c h i e v e d   f o r   t h i s   i m p l e m e n t a t i o n   i s   2 7 5 . 0 3   M H z .   A   T i m i n g   a n d   A r e a   A n a l y s i s   r e p o r t   f o r   L O P   a l g o r i t h m   i m p l e m e n t a t i o n   i s   s h o w n   i n   T a b l e   2   a n d   3 .       T a b l e   2 .   T i m i n g   A n a l y s i s   ( C y c l o n e :   E P 1 C 4 F 4 0 0 C 8 )   E n t i t y   C l o c k   P e r i o d   ( n s )   C l o c k   S p e e d ( M H z )   L O P   A l g o r i t h m   d e s i g n   3 . 6 3 6   n s   2 7 5 . 0 3   M H z       T a b l e   3 .   A r e a   A n a l y s i s   ( C y c l o n e :   E P 1 C 4 F 4 0 0 C 8 )   E n t i t y   L o g i c   Ce l l s   L Re g i s t e r s   P i n s   Re g i s t o r s - O n l y   L Cs   L U T / Re g i s t e r   L Cs   Ca r r y   Ch a i n   L Cs   L O P   A l g o r i t h m   d e s i g n   3 2 / 4 , 0 0 0   ( < 1 % )   3 2   5 6 / 3 0 1   ( 1 8 % )   2 2   1 0 ( 0 )   8   ( 0 )       5 .   I M P L E M E N T A T I O N   T h e   c o m p l e t e   c i r c u i t   o f   L O P   i s   d e s c r i b e d   i n   V H D L ,   a s   a   s t r u c t u r a l   c o m p o n e n t .   T h e n   h i e r a r c h i c a l   s t r u c t u r e   i s   c r e a t e d   a n d   t h e   c o m p l e t e   s i m u l a t i o n   c a n   b e   o b s e r v e d .   F i g u r e   5   s h o w s   t h e   w a v e f o r m   s i m u l a t i o n   r e s u l t   f o r   t h e   L O P   a l g o r i t h m .   W a v e   f o r m   s h o w s   t h e   l e a d i n g   o n e   d e t e c t i o n   a l o n g   w i t h   t h e   n o r m a l i z a t i o n   o f   t h e   n u m b e r .   A l s o   i t   g i v e s   c o u n t   v a l u e   o f   t h e   n u m b e r   o f   s h i f t   f o r   e x p o n e n t   t h a t   i s   t h e   r e s u l t   o f   p o s t   n o r m a l i z a t i o n .       6 .   F I V E   S T A G E   P I P E L I N E   L O P   F L O A T I N G   P O I N T   A D D E R   I M P L E M E N T A T I O N   T h e   l e a d i n g   o n e   p r e d i c t o r   a l g o r i t h m   i s   p i p e l i n e d   i n t o   f i v e   s t a g e s .   F i g u r e   6   s h o w s   t h e   m i c r o - a r c h i t e c t u r e   o f   t h e   f i v e   s t a g e   p i p e l i n e   i m p l e m e n t a t i o n   o f   L O P   f l o a t i n g - p o i n t   a d d e r   a l g o r i t h m .   T h e   d o t t e d   l i n e s   s h o w   t h e   r e g i s t e r s   u s e d   t o   i n d u c e   s t a g e s   b e t w e e n   l o g i c .   I n   t h e   f i r s t   s t a g e   o f   t h e   i m p l e m e n t a t i o n   t h e   t w o   o p e r a n d s   a r e   c o m p a r e d   t o   i d e n t i f y   d e n o r m a l i z a t i o n   a n d   i n f i n i t y .   T h e n   t h e   t w o   e x p o n e n t s   a r e   s u b t r a c t e d   t o   o b t a i n   t h e   e x p o n e n t   d i f f e r e n c e   a n d   i d e n t i f y   w h e t h e r   t h e   o p e r a n d s   n e e d   t o   b e   s w a p p e d   u s i n g   t h e   e x p o n e n t   d i f f e r e n c e   s i g n .   I n   t h e   s e c o n d   s t a g e   t h e   r i g h t   s i f t e r   i s   u s e d   t o   p r e   n o r m a l i z e   t h e   s m a l l e r   m a n t i s s a .   I n   t h e   t h i r d   s t a g e   t h e   a d d i t i o n   i s   d o n e   a l o n g   w i t h   l e a d i n g   o n e   p r e d i c t i o n .   I n   t h e   f o u r t h   s t a g e   l e f t   s h i f t e r   i s   u s e d   t o   p o s t   n o r m a l i z e   t h e   r e s u l t .   I n   t h e   l a s t   s t a g e   t h e   e x p o n e n t   o u t   i s   c a l c u l a t e d   a n d   r o u n d i n g   i s   d o n e .   T h e   r e s u l t s   a r e   t h e n   c o m p a r e d   t o   s e t   o v e r f l o w   o r   u n d e r f l o w   f l a g s .     Evaluation Warning : The document was created with Spire.PDF for Python.
I J R E S   I S S N :   2 0 8 9 - 4 8 6 4       A   N o v e l   F P G A   b a s e d   L e a d i n g   O n e   A n t i c i p a t i o n   A l g o r i t h m   f o r   F l o a t i n g   P o i n t   .   ( A s h w i n i   S .   D e s h m u k h )   2 3   F i g u r e   5 .   S i m u l a t i o n   W a v e f o r m   f o r   L O P         F i g u r e   6 .   M i c r o - a r c h i t e c t u r e   o f   5   s t a g e   p i p e l i n e   L O P   f l o a t i n g - p o i n t   a d d e r       7 .   C O N C L U S I O N   I n   t h i s   p a p e r ,   a   N o v e l   F P G A   b a s e d   L e a d i n g   O n e   A n t i c i p a t i o n   A l g o r i t h m   f o r   F l o a t i n g   P o i n t   A r i t h m e t i c   U n i t s   i s   d i s c u s s e d .   T h i s   a l g o r i t h m   g i v e s   d e s i g n e r   t h e   c h o i c e   t o   s e l e c t   a p p r o p r i a t e   i m p l e m e n t a t i o n   a c c o r d i n g   t o   t h e i r   d e s i g n   n e e d s .   S t a n d a r d   f l o a t i n g - p o i n t   a d d i t i o n   a l g o r i t h m   i s   m e a n t   f o r   a r e a   e f f i c i e n t   d e s i g n s   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 9 - 4 8 6 4   I J R E S     V o l .   1 ,   N o .   1 ,     M a r c h   2 0 1 2   :     1 9     2 4   2 4 w h e r e   d e s i g n e r s   a r e   w o r k i n g   w i t h   s m a l l   F P G A   d e v i c e s   w i t h   v e r y   f e w   e q u i v a l e n t   l o g i c   g a t e s   t o   f i t   i n   t h e i r   d e s i g n .   F o r   l a t e n c y   e f f i c i e n t   d e s i g n s   w h e r e   t h e   m a i n   a i m   i s   t o   h a v e   f a s t e r   e x e c u t i o n   u n i t s ,   L O P   a l g o r i t h m   i s   t h e   b e s t   o p t i o n .   L O P   i s   r u n n i n g   a t   a r o u n d   2 7 5   M H z   f o r   f i v e   p i p e l i n e   s t a g e s   i s   f a s t e r   a n d   b e t t e r   f o r     i m p l e m e n t a t i o n .   A   n o v e l   l e a d i n g   o n e   a n t i c i p a t i o n   a l g o r i t h m   a l l o w i n g   u s   t o   s i g n i f i c a n t l y   r e d u c e   t h e   a n t i c i p a t i o n   f a i l u r e   r a t e   w i t h   r e s p e c t   t o   t h e   s t a t e - o f   t h e   a r t .         R E F E R E N C E S   [ 1 ]     S t a n d a r d   f o r   b i n a r y   f l o a t i n g - p o i n t   a r i t h m e t i c ,   I E E E   S t a n d a r d   7 5 4 ,   1 9 8 5 .   [ 2 ]     S .   Br i t t o n ,   R.   A l l m o n ,   a n d   S .   S a m u d r a l a ,   L e a d i n g   o n e / z e r o   b i t   d e t e c t o r   f o r   f l o a t i n g - p o i n t   a d d i t i o n ,   U . S .   P a t e n t   5 3 1 7 5 2 7 ,   M a y   1 9 9 4 .   [ 3 ]     M . S .   S c h m o o k l e r ,   a n d   D .   M i k a n ,   T w o - s t a t e   l e a d i n g   z e r o / o n e   a n t i c i p a t o r   ( L Z A ) ,   U . S .   P a t e n t   5 4 9 3 5 2 0 ,   F e b r u a r y   1 9 9 6 .     [ 4 ]     J .   D .   Br u g u e r a   a n d   T .   L a n g ,   L e a d i n g - O n e   P r e d i c t i o n   w i t h   Co n c u r r e n t   P o s i t i o n   Co r r e c t i o n ,   I E E E   T r a n s a c t i o n s   o n   Co m p u t e r s ,   p p .   1 0 8 3 1 0 9 7 ,   1 9 9 9 ,   v o l .   4 8 ,   n o . 1 0 .     [ 5 ]     M .   J .   F l y n n ,   L e a d i n g   O n e   P r e d i c t i o n   - -   I m p l e m e n t a t i o n ,   g e n e r a l i z a t i o n ,   a n d   a p p l i c a t i o n ,   T e c h n i c a l   Re p o r t :   CS L - T R - 9 1 - 4 6 3 ,   M a r c h   1 9 9 1 .     [ 6 ]     V .   G .   O k l o b d z i j a ,   A n   A l g o r i t h m i c   a n d   N o v e l   D e s i g n   o f   a   L e a d i n g   Z e r o   D e t e c t o r   Ci r c u i t :   C o m p a r i s o n   w i t h   L o g i c   S y n t h e s i s .   I E E E   T r a n s a c t i o n s   o n   V e r y   L a r g e   S c a l e   I n t e g r a t i o n   ( V L S I )   S y s t e m s ,   p p .   1 2 4 - 1 2 8 ,   1 9 9 4 ,   V o l .   2 ,   N o .   1 .     [ 7 ]     T .   Ch a n g ,   J .   H u a n g ,   a n d   S .   Y a n g ,   L e a d i n g - z e r o   a n t i c i p a t o r y   l o g i c s   f o r   f a s t   f l o a t i n g   a d d i t i o n   w i t h   c a r r y   p r o p a g a t i o n   s i g n a l ,   P r o c .   4 0 t h   M i d we s t   S y m p o s i u m   o n   Ci r c u i t s   a n d   S y s t e m s ,   1 9 9 7 ,   v o l .   1 ,   p p .   3 8 5 - 3 8 8 .   [ 8 ]     H . P .   S i t ,   e t   a l . ,   P r e n o r m a l i z a t i o n   f o r   a   f l o a t i n g - p o i n t   a d d e r ,   U . S .   P a t e n t   5 0 1 0 5 0 8 ,   A p r i l   1 9 9 1     [ 9 ]     S .   O b e r m a n ,   a n d   M .   R o b e r t s ,   L e a d i n g   o n e   p r e d i c t i o n   u n i t   f o r   n o r m a l i z i n g   n e a r - p a t h   s u b t r a c t i o n   r e s u l t s   w i t h i n   a   f l o a t i n g   p o i n t   a r i t h m e t i c   u n i t ,   U . S .   P a t e n t   6 0 8 5 2 0 8 ,   J u l y   2 0 0 0 .   [ 1 0 ]     M . S .   S c h m o o k l e r ,   a n d   K . J .   N o w k a ,   L e a d i n g   z e r o   a n t i c i p a t i o n   a n d   d e t e c t i o n     a   c o m p a r i s o n   o f   m e t h o d s ,   P r o c .   1 5 t h   I E E E   S y m p o s i u m   o n   Co m p u t e r   A r i t h m e t i c ,   2 0 0 1 ,   p p .   7 - 1 2 .   [ 1 1 ]     H .   S u n ,   W .   H e ,   a n d   M .   G a o ,   D e s i g n i n g   l e a d i n g   z e r o s   a n t i c i p a t o r y   l o g i c   b a s e d   o n   p r o d u c t i o n   r u l e s ,   P r o c .   5 t h   I n t e r n a t i o n a l   Co n f e r e n c e   o n   A S I C ,   2 0 0 3 ,   v o l .   2 ,   p p .   1 2 6 0 - 1 2 6 4 .   H .   S u n ,   a n d   M .   G a o ,   U n i f i e d   b i t   p a t t e r n   f o r   l e a d i n g - z e r o   a n t i c i p a t o r y   l o g i c   f o r   h i g h - s p e e d   f l o a t i n g - p o i n t   a d d i t i o n ,   P r o c .   3 r d   I E E E   I n t e r n a t i o n a l   S y m p o s i u m   o n   S i g n a l   P r o c e s s i n g   a n d   I n f o r m a t i o n   T e c h n o l o g y ,   2 0 0 3 ,   p p .   7 8 6 - 7 8 9 .           Evaluation Warning : The document was created with Spire.PDF for Python.