Cluster assignment for high-performance embedded VLIW processors

ABSTRACT

Clustering is an effective method to increase the available parallelism in VLIW datapaths without incurring severe penalties associated with a large number of register file ports. Efficient utilization of a clustered datapath requires careful binding/assignment of operations to clusters. The article proposes a binding algorithm that effectively explores trade-offs between in-cluster operation serialization and delays associated with data transfers between clusters. Extensive experimental evidence is provided showing that the algorithm generates high quality solutions for representative kernels, with up to 33% improvement over a state-of-the-art binding algorithm.

REFERENCES

• 1: Cagdas Akturan , Margarida F. Jacome, CALiBeR: a software pipelining algorithm for clustered embedded VLIW processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 2: Akturan, C. and Jacome, M. F. 2002. An effective software pipelining algorithm for clustered embedded VLIW processors. J. Des. Autom. Embed. Sys., Special Issue on Design Methodologies and Tools for Real-Time Embedded Systems (to appear).
• 3: Analog Devices. 2001. ADSP-TS001M TigerSHARC DSP product description. Available online at http://www.analog.com/products/descriptions/ADSP-TS001.html.
• 4: Basoglu, C., Zhao, K., Kojima, K., and Kawaguchi, A. 2000. The MAP-CA VLIW-based media processor. Equator Technologies Inc. and Hitachi Ltd. Available online at http://equator.com.
• 5: Andrea Capitanio , Nikil Dutt , Alexandru Nicolau, Partitioned register files for VLIWs: a preliminary analysis of tradeoffs, Proceedings of the 25th annual international symposium on Microarchitecture, p.292-300, December 01-04, 1992, Portland, Oregon, United States
• 6: Robert P. Colwell , W. Eric Hall , Chandra S. Joshi , David B. Papworth , Paul K. Rodman , James E. Tornes, Architecture and implementation of a VLIW supercomputer, Proceedings of the 1990 conference on Supercomputing, p.910-919, October 1990, New York, New York, United States
• 7: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 8: Desoli, G. 1998. Instruction assignment for clustered VLIW DSP compilers: A new approach. Tech. Rep. HPL-98-13, Hewlett-Packard Co., February.
• 9: Dixit, K. 2001. Performance SPECulations---Benchmarks, friend or foe. In Procedings of the Seventh International Symposium on High Performance Computer Architecture (Monterrey, Mexico).
• 10: An Eight Issue Tree-VLIW Processor for Dynamic Binary Translation, Proceedings of the International Conference on Computer Design, p.488, October 05-05, 1998
• 11: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 12: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 13: Faraboschi, P., Desoli, G., and Fisher, J. A. 1998. Clustered instruction-level parallel processors. Tech. Rep. HPL-98-204, Hewlett-Packard Co., December.
• 14: Marcio Merino Fernandes , Josep Llosa , Nigel Topham, Distributed Modulo Scheduling, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.130, January 09-12, 1999
• 15: Jason Fritts , Zhao Wu , Wayne Wolf, Parallel Media Processors for the Billion-Transistor Era, Proceedings of the 1999 International Conference on Parallel Processing, p.354, September 21-24, 1999
• 16: Werner Geurts, Accelerator Data-Path Synthesis for High-Throughput Signal Processing Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 17: Silvina Hanono , Srinivas Devadas, Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator, Proceedings of the 35th annual conference on Design automation, p.510-515, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277184]
• 18: Emmanuel C. Ifeachor , Barrie W. Jervis, Digital Signal Processing: A Practical Approach, Pearson Education, 2002
• 19: Margarida F. Jacome , Gustavo de Veciana, Design Challenges for New Application-Specific Processors, IEEE Design & Test, v.17 n.2, p.40-50, April 2000 [doi>10.1109/54.844333]
• 20: Krishnan Kailas , Ashok Agrawala , Kemal Ebcioglu, CARS: A New Code Generation Framework for Clustered ILP Processors, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.133, January 20-24, 2001
• 21: Lapinskii, V., Jacome, M. F., and de Veciana, G. 2002. Application-specific clustered VLIW datapaths: Early exploration on a parameterized design space. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. (accepted for publication).
• 22: 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
• 23: Rainer Leupers, Instruction Scheduling for Clustered VLIW DSPs, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.291, October 15-19, 2000
• 24: Peter Mattson , William J. Dally , Scott Rixner , Ujval J. Kapasi , John D. Owens, Communication scheduling, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.82-92, November 2000, Cambridge, Massachusetts, United States
• 25: Erik Nystrom , Alexandre E. Eichenberger, Effective cluster assignment for modulo scheduling, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.103-114, November 1998, Dallas, Texas, United States
• 26: Emre Özer , Sanjeev Banerjia , Thomas M. Conte, Unified assign and schedule: a new approach to scheduling for clustered register file microarchitectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.308-315, November 1998, Dallas, Texas, United States
• 27: P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
• 28: Helvio Pereira Peixoto , Margarida F. Jacome, Reuse and estimation techniques for embedded systems-on-a-chip, 1999
• 29: Rau, B. R., Kathail, V., and Aditya, S. 1998. Machine-description driven compilers for EPIC processors. Tech. Rep. HPL-98-40, Hewlett-Packard Co., September.
• 30: Rixner, S., Dally, W. J., Khailany, B., Mattson, P., Kapasi, U. J., and Owens, J. D. 1999. Register organization for media processing. In Proceedings of the 26th International Symposium on High-Performance Computer Architecture.
• 31: Jesús Sánchez , Antonio González, Instruction scheduling for clustered VLIW architectures, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain [doi>10.1145/501790.501801]
• 32: Texas Instruments. 2000. TMS320C6000 CPU and instruction set reference guide. Literature Number: SPRU226.
• 33: S. W. White , S. Dhawan, POWER2: next generation of the RISC System/6000 family, IBM Journal of Research and Development, v.38 n.5, p.493-502, Sept. 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Operation binding, clustered VLIW datapaths, embedded processors, embedded systems, partitioning