Mapping a single assignment programming language to reconfigurable systems

The Journal of Supercomputing, Volume 21, pages 117-130, 2002.





 
 

  
  




  
  
  
   
  



   
     
 
    

   


  
   
                                           
     ! !"  #  
        
                 
      
  
                      
    

 $"    %       $      !"   

#
     &   


  

             !   "    "          #       $%&'
$%&'   !   "  #    (  %  )**+,    ( -

 
. )**/, #!   (.   !  )***,     (    
 )**0,    #  (1     )**2,
3 !   !           " -  !       Æ "      
$%&'                   4 5 (% )**6,
'                           "              7   
3   % (   
 )***,     #

        8'# (    )***, " 7#


 '(     $  )  ! $
    !**+,-./,*,. Ý 
0   £

­ 122,     

      


   

 





9


  DFG Simulator

SA-C

SA-C Compiler

DDCF

SA-C Codegen

DFG

AHA Simulator

DFG to AHA

AHA

VHDL Macro Library

AHA to VHDL VHDL

host C-code

Synplify EDF

gcc

Xilinx M1 X86 Run-Time Library

Host

RCS

executable

      

            $%&'
3 8'#   #       7 !

 $%&' -  
'"         8'#              

  : (

$,     


$         .        -  8'#       "
'" .        

!  "   :   ( $& ,    
$&     4 5   '!     ' (' ',  
3 4 5    .   # #  $%&' !   "  
$  )   #  "   
3          !        "
$   !    8'#      ! 7    
'     "   !   $&  ' '     !  
3 8'# #    Ì Å  #   !     !      ; (;      )**2,    "   
3   "      . "
'  "  8'#          9
 .           6
3       :      4 5  ' '       2
'    "         0
"           .    "   "    
=  7  !    .     .
3  "  = E &1   676           $E'55 
3   E3                  "    "    
1  1 F1 8F     "   

   
$   E83F3 ''G    ! "        "    !     
  =%    -7 .  "      
'
     "  !   


   

 





        -1 -1 -1 0 0 0 1 1 1

0

-1 0 1 -1 0 1 -1 0 1

Image CREATE_ARRAY

CREATE_ARRAY

’H’

’V’ 3 1

3 1

FORALL

WINDOW_GEN

’W’ FORALL DOT ELEMENT_GEN

ELEMENT_GEN

ELEMENT_GEN

*

*

REDUCE_SUM

REDUCE_SUM

’dfdy’

’dfdx’

*

* + SQRT

’magnitude’ CONSTRUCT_ARRAY

’M’

 

! 
 '  

.          
'  . "#       "             
=  . "  "      !    " . "   
1H . "   .    $ 5 F  '  1      
  
  

       ! # ! "     !       " $%&'  !                  
8    ">    =%   " 7     -7 .  
    
   "   "  #         "     "    
            ! #    
=  % 7   .       


 
  


 3   Æ   #  "     !             
3        "             !  .     
3   -7 ! "   #  "      >   ! 
), 3    ! !  "  . "          




   

 





<
  
9, &  .     ! !  "    7          "   .


 


 7  ( " )**         

 " #    " "       Æ          
=         #   #!#     " 
  #  !  "   =%       
   "   @ 


 
 

(  
 )) (  
 ))


   
 


(  
 





="  7     (  ),7(  ),     ! (  9,7(  9,           ! "  
     !  "      ! 7     
E  "  

979 !#   "    "      !#       676 !#   "
=   !                676     !      " "   "
 8!7  1  (81,    #  .        !  "   !7        
3  !   C  #   81D    "  !7   ! " 
3 8'#  "      81 ! 

  "      "                   
=            !   !                !      ! 
















   

 





/ 
   7       !7 @

       

 
 )
*

 $   $ 
 $   $    
  $'$

3       "   "    "      
   "  -    "                  -     !        7  
             "             > "   !
'  "  "   3  81@       "   "    "     !      
 !
      $%&'   >    A  
=      "   H "   . 

  ! ?      !    
3 8'#     "  .   !  !

     
3      7  H         #  H









   

'   :   ( $&,  #     #     
$&   !  !                   
           
$&      
3 8'#            

$&
3      -    !     "             ! "   
=           !     

$&
3         >    . " A    !    
=  %       

$      # "   $&   $  2
3 8F    ! #     "      "  
3         "    !      " "   
3 E83F3 ''G           



   

 





+


  Image 3 1

FORALL

3 1

WINDOW_GEN

neg

neg

neg

neg

neg

SUM

SUM

*

* + SQRT

CONSTRUCT_ARRAY

 ! !"  '     

$&         "   '!   #   ' (' ',
3      " !       -#     $&       !       4 5 
' '     

 
3   #    #     !            .      
8       !     
' ' '     . > "     

 ! ! 
'  !     "          #  #
=  ' '   -        !              ! !        
3    $&            -
3 ' '   "  %        7         ()0 " 90  .  )+B  .
=     %= !       66  .
=     !      9       6    7   8    " 99     %
0
6
=  0
)      %  
'   #               "  
3 "   ),     9,       ( .,    6, # 7  #         2,     !   

   
$     7   "       !   (3  4 )**+,  #  2
3 -    "      8'#     -  !   
'      !   8'#      !   $%&'
3"          ! "    
3  "   "       . 
8'# 7    8   <  
   "   %   
'   "            =A =%5   !
3       +0B     %
 =A E4 !    #. !#   "       " (  , 
          !   (         ,  E4    )60  # 






   

 





)9
  
8 8'#  99  "    !   )2B  "      =%5  
0
2


     " #        #   "    
  -  " !  " -  !       # !        (;  9BBB,
3         " >  .     "    #  "    
3 8'#    9   7    $%&'    %      /0  
8'#  6/  " 
    "         8'#   8     47 9BBB1   ! 9B  /0  "     "         +BB  . % ===


!
" #

   "      -  !   

  
   "       L       H## "  (

$%&' ,          
3 8 #9 (  
 )**   
   % ===KI   !        8'#    

 '  8  !    47 9BBB $%&'    "        =%5     !     /0      7    %        1 >
%"     "  8'#      ! 
' "    !       !    !      #            " 

       H !   "      !
  4 5   "  ' '        "    !   ' '  
   !       "   %    (%,      "    "  7     
%     "    "                     
'        !    8'#              !    $%&'
3  7  "          "      
"' 

 '   
 $ 5 6 !( 7  8 (  6 (
  9 ,..: ;
 $7   ;    $         = 9 $ 7 #    6 ?   @A9 '
 (
  )    )   $$


   8

5  ,-+B,+: 5*B1-1 E 9 1222 ; 5
(    3             $4   ! '  = 9 0777 , #  
 $

0  ! ,2,1 6    G  
 3  $ # ) E(  D  ('9 ,... ;#' '     3 $  
  = 9 
 8 9  


   " # 
6  C 5

 ! E
9 ,... ;
 6
  $   = 9 

 ,
 33


   

 



 

)<


 

C