Instruction generation for hybrid reconfigurable systems

ABSTRACT

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.

REFERENCES

• 1: Peter M. Athanas , A. Lynn Abbott, Real-Time Image Processing on a Custom Computing Platform, Computer, v.28 n.2, p.16-24, February 1995 [doi>10.1109/2.347995]
• 2: Bozorgzadeh, E., Ogrenci Memik, S., Kastner, R., and Sarrafzadeh, M. 2002a. Pattern selection: Customized block allocation for domain-specific programmable systems. In Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms.
• 3: Bozorgzadeh, E., Ogrenci Memik, S., Kastner, R., and Sarrafzadeh, M. 2002b. SPS: Strategically programmable system---fully automated architecture generation and application compilation. Tech. Rep. UCLA.
• 4: Srihari Cadambi , Seth Copen Goldstein, CPR: A Configuration Profiling Tool, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.104, April 21-23, 1999
• 5: Timothy J. Callahan , Philip Chong , André DeHon , John Wawrzynek, Fast module mapping and placement for datapaths in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.123-132, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275132]
• 6: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 7: Amit Chowdhary , Sudhakar Kale , Phani Saripella , Naresh Sehgal , Rajesh Gupta, A general approach for regularity extraction in datapath circuits, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.332-339, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289050]
• 8: Katherine Compton , Scott Hauck, Totem: Custom Reconfigurable Array Generation, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111-119, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.47]
• 9: Katherine Compton , Akshay Sharma , Shawn Phillips , Scott Hauck, Flexible Routing Architecture Generation for Domain-Specific Reconfigurable Subsystems, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.59-68, September 02-04, 2002
• 10: Corazao, M. R., Khalaf, M. A., Guerra, L. M., Potkonjak, M., and Rabaey, J. M. 1996. Performance optimization using template mapping for datapath-intensive high-level synthesis. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 15, 8, 877--888.
• 11: André DeHon, DPGA utilization and application, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.115-121, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228387]
• 12: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 13: Ebeling, C. and Zajicek, O. 1983. Validating VLSI circuit layout by wirelist comparison. In Proceedings of the International Conference on Computer-Aided Design.
• 14: Edwards, S. A. 2002. An Esterel compiler for large control-dominated systems. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 21, 2, 169--183.
• 15: Gajski, D. D., Zhu, J., Dömer, R., Gerstlauser, A., and Zhoa, S. 2000. SpecC: Specification Language and Methodology. Kluwer Academic, Boston.
• 16: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: Girault, A., Bilung, L., and Lee, E. A. 1999. Hierarchical finite state machines with multiple concurrency models. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 18, 6, 742--760.
• 18: Maya Gokhale , William Holmes , Andrew Kopser , Sara Lucas , Ronald Minnich , Douglas Sweely , Daniel Lopresti, Building and Using a Highly Parallel Programmable Logic Array, Computer, v.24 n.1, p.81-89, January 1991 [doi>10.1109/2.67197]
• 19: Seth Copen Goldstein , Herman Schmit , Mihai Budiu , Srihari Cadambi , Matt Moe , R. Reed Taylor, PipeRench: A Reconfigurable Architecture and Compiler, Computer, v.33 n.4, p.70-77, April 2000 [doi>10.1109/2.839324]
• 20: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 21: Thorsten Grotker, System Design with SystemC, Kluwer Academic Publishers, Norwell, MA, 2002
• 22: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 23: 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
• 24: Kahrs, M. 1986. Matching a parts library in a silicon compiler. In Proceedings of the International Conference on Computer-Aided Design.
• 25: Kastner, R., Bozorgzadeh, E., Ogrenci Memik, S., and Sarrafzadeh, M. 2002. Compiler techniques for system synthesis optimization, Tech. Rep. UCLA.
• 26: Ryan Kastner , Seda Ogrenci-Memik , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Instruction generation for hybrid reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 27: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 28: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 29: Scott A. Mahlke , Richard E. Hank , James E. McCormick , David I. August , Wen-Mei W. Hwu, A comparison of full and partial predicated execution support for ILP processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.138-150, June 22-24, 1995, S. Margherita Ligure, Italy
• 30: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 31: Renu Mehra , Jan Rabaey, Exploiting regularity for low-power design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.166-172, November 10-14, 1996, San Jose, California, United States
• 32: Micali, S. and Vazirani, V. V. 1980. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the Symposium on Foundations of Computer Science.
• 33: Stefaan Note , Werner Geurts , Francky Catthoor , Hugo De Man, Cathedral-III: Architecture-driven high-level synthesis for high throughput DSP applications, Proceedings of the 28th conference on ACM/IEEE design automation, p.597-602, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127739]
• 34: Ogrenci Memik, S., Bozorgzadeh, E., Kastner, R., and Sarrafzadeh, M. 2001a. Strategically programmable systems. In Proceedings of the Reconfigurable Architecture Workshop.
• 35: S. Ogrenci Memik , E. Bozorgzadeh , R. Kastner , M. Sarrafzadeh, A super-scheduler for embedded reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 36: Peixin, Z., Martonosi, M., Ashar, P., and Malik, S. 1999. Using configurable computing to accelerate Boolean satisfiability. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 18, 6, 861--868.
• 37: Rao, D. S. and Kurdahi, F. J. 1993. On clustering for maximal regularity extraction. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 12, 8, 1198--1208.
• 38: Robert Schreiber , Shail Aditya , B. Ramakrishna Rau , Vinod Kathail , Scott Mahlke , Santosh Abraham , Greg Snider, High-Level Synthesis of Nonprogrammable Hardware Accelerators, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.113, July 10-12, 2000
• 39: Reetinder P. S. Sidhu , Alessandro Mei , Viktor K. Prasanna, String matching on multicontext FPGAs using self-reconfiguration, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.217-226, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296463]
• 40: Smith, M. D. and Holloway, G. An introduction to machine SUIF and its portable libraries for analysis and optimization. Tech. Rep., Division of Engineering and Applied Sciences, Harvard University.
• 41: Tai Ly , David Knapp , Ron Miller , Don MacMillen, Scheduling using behavioral templates, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.101-106, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217514]
• 42: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware; Gate arrays

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design

Keywords:
FPGA, high-level synthesis, reconfigurable computing