A systolic array for a 2D-FIR filter for image processingOutlineWhy Systolic Arrays? (1)Why Systolic Arrays? (2)Design IssuesApproach (1)Approach (2)SolutionResultA systolic array for a 2D-FIR filter for image processingSebastian SiegelECE 734H2Outline•Why Systolic Arrays (SA)?•Design Issues•Approach•Solution•Result3Why Systolic Arrays? (1) 4-level nested do-loop: VVvUUuvuhvjuipjif ),(),(),(v,u,j,ivuhvjuipjifjifVVvUUujifVJVjUIUi enddo),(),(),(),( to do to do 0),( 1 to do 1 to do4Why Systolic Arrays? (2)•Sequential execution on one MAC requires too much timeExample: image: 512x512, filter: 3x3 2.3 Million operations @ 10 Mhz = 0.23 s•Algorithm in nested do-loop structure Single Assignment Format possible Parallel execution possible•Systematic approach vs. “rocket science”5Design Issues•Recall:•Avoid multiple access to the same databy pipelining it•Minimize execution time and registers•Maximize Usage of Processing Elements (PEs)),(),(),( vuhvjuipjif 6Approach (1)Steps:•Rewrite Algorithm in Single Assignment Format (SAF)•Draw and examine Dep. Graph (DG)•Map DG to SA by generating suitable solutions and chose an optimal oneProblem: SA too big partitioning data reaccessed or cache needed7Approach (2)Partitioning of the DG generates even more (and better) solutions:8Solution9Result•Fully pipelined SA•100% PE utilization•SA can be partitioned with relatively small cache and 100% data reuse or without cache and high data reuse•PEs and their interconnections (# of registers per pipeline) independent of filter size•Low latency for the results•Constant I/O rate•Fast MATLAB®
View Full Document