Matching and searching analysis for parallel hardware implementation on FPGAs

ABSTRACT

Matching and searching computations play an important role in the indexing of data. These computations are typically encoded in very tight loops with a single index variable and a simple search/ matching predicate. Their inherent sequential nature, either because of data dependences but more often because of very strong control dependences, makes it impossible to apply existing data dependence and parallelization analysis to exploit significant levels parallelism on traditional architectures. This paper describes a class of searching and matching computations and describes a mapping strategy to map these computations to hardware. We have developed a compiler analysis in SUIF using array data dependence analysis and implicit loop unrolling analysis to expose more parallelism for the parallel evaluation of these computations. Our compiler generates parallel hardware specifications in VHDL. The resulting parallel hardware yields significant performance improvements when these kernel operators are repeated over shifted portions of the input data on FPGA-based computing architectures.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: P. Banerjee , N. Shenoy , A. Choudhary , S. Hauck , C. Bachmann , M. Haldar , P. Joisha , A. Jones , A. Kanhare , A. Nayak , S. Periyacheri , M. Walkden , D. Zaretsky, A MATLAB Compiler for Distributed, Heterogeneous, Reconfigurable Computing Systems, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.39, April 17-19, 2000
• 3: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 4: D. C. Cronquist , P. Franklin , S. G. Berg , C. Ebeling, Specifying and Compiling Applications for RaPiD, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.116, April 15-17, 1998
• 5: Pedro Diniz , Joonseok Park, Automatic Synthesis of Data Storage and Control Structures for FPGA-Based Computing Engines, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.91, April 17-19, 2000
• 6: Maya B. Gokhale , Janice M. Stone, NAPA C: Compiling for a Hybrid RISC/FPGA Architecture, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.126, April 15-17, 1998
• 7: Maya Gokhale , Brian Schott, Data-parallel C on a reconfigurable logic array, The Journal of Supercomputing, v.9 n.3, p.291-313, 1995 [doi>10.1007/BF01212873]
• 8: The Stanford SUIF Compilation System". Public Domain Software and Documentation available at http:// suif.stanford.edu.
• 9: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 10: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 11: Markus Weinhardt , Wayne Luk, Pipeline Vectorization for Reconfigurable Systems, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.52, April 21-23, 1999
• 12: Markus Weinhardt , Wayne Luk, Memory Access Optimization and RAM Inference for Pipeline Vectorization, Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications, p.61-70, August 30-September 01, 1999
• 13: Allan L. Fisher , Anwar M. Ghuloum, Parallelizing complex scans and reductions, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.135-146, June 20-24, 1994, Orlando, Florida, United States
• 14: Martin C. Rinard , Pedro C. Diniz, Commutativity analysis: a new analysis framework for parallelizing compilers, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.54-67, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 15: Seth Copen Goldstein , Herman Schmit , Matthew Moe , Mihai Budiu , Srihari Cadambi , R. Reed Taylor , Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia, United States
• 16: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 17: S. Hauck , T. W. Fry , M. M. Hosler , J. P. Kao, The Chimaera reconfigurable functional unit, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.87, April 16-18, 1997

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Design, Experimentation, Performance