Inter-cluster communication in VLIW architectures

ABSTRACT

The traditional VLIW (very long instruction word) architecture with a single register file does not scale up well to address growing performance demands on embedded media processors. However, splitting a VLIW processor in smaller clusters, which are comprised of function units fully connected to local register files, can significantly improve VLSI implementation characteristics of the processor, such as speed, energy consumption, and area. In our paper we reveal that achieving the best characteristics of a clustered VLIW requires a thorough selection of an Inter-cluster Communication (ICC) model, which is the way clustering is exposed in the Instruction Set Architecture. For our study we, first, define a taxonomy of ICC models including copy operations, dedicated issue slots, extended operands, extended results, and multicast. Evaluation of the execution time of the models requires both the dynamic cycle count and clock period. We developed an advanced instruction scheduler for all the five ICC models in order to quantify the dynamic cycle counts of our multimedia C benchmarks. To assess the clock period of the ICC models we designed and laid out VLIW datapaths using the RTL hardware descriptions derived from a deeply pipelined commercial TriMedia processor. In contrast to prior art, our research shows that fully distributed register file architectures (with eight clusters in our study) often underperform compared to moderately clustered machines with two or four clusters because of explosion of the cycle count overhead in the former. Among the evaluated ICC models, performance of the copy operation model, popular both in academia and industry, is severely limited by the copy operations hampering scheduling of regular operations in high ILP (instruction-level parallelism) code. The dedicated issue slots model combats this limitation by dedicating extra VLIW issue slots purely for ICC, reaching the highest 1.74 execution time speedup relative to the unicluster. Furthermore, our VLSI experiments show that the lowest area and energy consumption of 42 and 57% relative to the unicluster, respectively, are achieved by the extended operands model, which, nevertheless, provides higher performance than the copy operation model.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: Alex Aletà , Josep M. Codina , F. Jesús Sánchez , Antonio González , David R. Kaeli, Exploiting Pseudo-Schedules to Guide Data Dependence Graph Partitioning, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.281-290, September 22-25, 2002
• 3: Alex Aletà , Josep M. Codina , Antonio González , David Kaeli, Instruction Replication for Clustered Microarchitectures, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.326, December 03-05, 2003
• 4: Bekooij, M. 2004. Constraint Driven Operation Assignment for Retargetable VLIW Compilers. PhD thesis, ISBN 90-74445-60-8, Technical University of Eindhoven, Eindhoven, The Netherlands.
• 5: Robert W. Brodersen, Energy Efficient Microprocessor Design, Kluwer Academic Publishers, Norwell, MA, 2001
• 6: Anantha P. Chandrakasan , Robert W. Brodersen, Low Power Digital CMOS Design, Kluwer Academic Publishers, Norwell, MA, 1995
• 7: Michael Chu , Kevin Fan , Scott Mahlke, Region-based hierarchical operation partitioning for multicluster processors, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 8: Josep M. Codina , Jesús Sánchez , Antonio González, A Unified Modulo Scheduling and Register Allocation Technique for Clustered Processors, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.175-184, September 08-12, 2001
• 9: Osvaldo Colavin , Davide Rizzo, A scalable wide-issue clustered VLIW with a reconfigurable interconnect, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951731]
• 10: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 11: 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
• 12: Fisher, J. A. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 478--490.
• 13: Fisher, J. A., Faraboschi, P., and Young, C. 2004. Embedded Computing: A VLIW Approach to Architecture, Compilers and Tools. Morgan Kaufmann. San Francisco, CA.
• 14: Gangwar, A., Balakrishnan, M., and Kumar, A. 2003. Impact of Inter-cluster Communication Mechanisms on ILP in Clustered VLIW Architectures, In Proceedings of the 2nd Workshop on Application Specific Processors, San Diego, CA.
• 15: Anup Gangwar , M. Balakrishnan , Preeti R. Panda , Anshul Kumar, Evaluation of Bus Based Interconnect Mechanisms in Clustered VLIW Architectures, Proceedings of the conference on Design, Automation and Test in Europe, p.730-735, March 07-11, 2005 [doi>10.1109/DATE.2005.141]
• 16: Enric Gibert , Jesús Sánchez , Antonio González, Effective instruction scheduling techniques for an interleaved cache clustered VLIW processor, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 17: Enric Gibert , Jesús Sánchez , Antonio González, Flexible Compiler-Managed L0 Buffers for Clustered VLIW Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.315, December 03-05, 2003
• 18: Enric Gibert , Jesus Sanchez , Antonio Gonzalez, Distributed Data Cache Designs for Clustered VLIW Processors, IEEE Transactions on Computers, v.54 n.10, p.1227-1241, October 2005 [doi>10.1109/TC.2005.163]
• 19: Halfhill, T. R. 2004. Best media processor: TriMedia TM5250. Microprocessor Report, 2/9/04, http://www.mpronline.com.
• 20: W. Havanki , S. Banerjia , T. Conte, Treegion Scheduling for Wide Issue Processors, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.266, January 31-February 04, 1998
• 21: G. D. La Hei, TriMedia CPU64 Design Space Exploration, Proceedings of the 1999 IEEE International Conference on Computer Design, p.599, October 10-13, 1999
• 22: Ho, R., Mai, K., and Horowitz, M. 2001. The future of wires. Proceedings of the IEEE, 89, 4, 490--504.
• 23: Hoogerbrugge, J. and Augusteijn, L. 1999. Instruction scheduling for TriMedia. The Journal of Instruction-Level Parallelism, 1, http://www.jilp.org/.
• 24: P. Y T Hsu , E. S. Davidson, Highly concurrent scalar processing, Proceedings of the 13th annual international symposium on Computer architecture, p.386-395, June 02-05, 1986, Tokyo, Japan
• 25: ITRS Technology Working Groups. 2005. International Technology Roadmap for Semiconductors (ITRS). The ITRS Technology Working Groups. http://www.itrs.net/.
• 26: Janssen, J. 2001. Compiler Strategies for Transport Triggered Architecture. PhD thesis, Technical University of Deflt, The Netherlands.
• 27: 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
• 28: Krishnan Kailas , Manoj Franklin , Kemal Ebcioglu, A Register File Architecture and Compilation Scheme for Clustered ILP Processors, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.500-511, August 27-30, 2002
• 29: The Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.282, September 16-18, 2002
• 30: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 31: Lapinskii, V. S., Jacome, M. F., and De Veciana, G. A. 2002. Application-specific clustered VLIW datapaths: Early exploration on a parameterized design space. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21, 8, 889--903.
• 32: Heng Liao , Andrew Wolfe, Available paralellism in video applications, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.321-329, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 33: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 34: Hsien-Hsin Lee , Youfeng Wu , G. Tyson, Quantifying instruction-level parallelism limits on an EPIC architecture, Proceedings of the 2000 IEEE International Symposium on Performance Analysis of Systems and Software, p.21-27, April 24-25, 2000
• 35: Levy, M. 2001. ManArray devours DSP code. Microprocessor report, 10/8/01-01, http://www.mpronline.com/.
• 36: 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
• 37: Rahul Nagpal , Y. N. Srikant, Integrated temporal and spatial scheduling for extended operand clustered VLIW processors, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977155]
• 38: 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
• 39: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 40: Joan-Manuel Parcerisa , Julio Sahuquillo , Antonio Gonzalez , Jose Duato, On-Chip Interconnects and Instruction Steering Schemes for Clustered Microarchitectures, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.130-144, February 2005 [doi>10.1109/TPDS.2005.23]
• 41: Rixner, S., Dally, W. J., Khailany, B., Mattson, P., Kapasi, U. J., Owens, J. D. 1999. Register organization for media processing. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture, Toulouse, France. IEEE Computer Society, Los Alamitos, CA. 375--386.
• 42: Roos, S., Corporaal, H., and Lamberts, R. 2002. Clustering on the Move. In Proceedings of the 4th International Conference on Massively Parallel Computing Systems, Ischia, Italy, IEEE Computer Society Press, Los Alamitos, CA.
• 43: Smith, J. E. 2006. Benchmarking: Science? Art? Neither? In 2006 SPEC Benchmark Workshop, Austin, Texas. http://www.spec.org/workshops/2006/.
• 44: Sudharsanan, S., Sriram, P., Frederickson, and H., Gulati, A. 2000. Image and video processing using Majc 5200. In Proceedings of the International Conference on Image Processing, Vancouver Canada, IEEE Computer Society Press, Los Alamitos, CA. 122--125.
• 45: Andrei Terechko , Erwan Le Thenaff , Manish Garg , Jos van Eijndhoven , Henk Corporaal, Inter-Cluster Communication Models for Clustered VLIW Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.354, February 08-12, 2003
• 46: Andrei Terechko , Erwan Le Thénaff , Henk Corporaal, Cluster assignment of global values for clustered VLIW processors, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951717]
• 47: Andrei Terechko , Manish Garg , Henk Corporaal, Evaluation of Speed and Area of Clustered VLIW Processors, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.557-563, January 03-07, 2005 [doi>10.1109/ICVD.2005.95]
• 48: J. T. J. Van Eijndhoven , E. J. D. Pol, TriMedia CPU64 Architecture, Proceedings of the 1999 IEEE International Conference on Computer Design, p.586, October 10-13, 1999
• 49: Jan-Willem van de Waerdt , Stamatis Vassiliadis , Sanjeev Das , Sebastian Mirolo , Chris Yen , Bill Zhong , Carlos Basto , Jean-Paul van Itegem , Dinesh Amirtharaj , Kulbhushan Kalra , Pedro Rodriguez , Hans van Antwerpen, The TM3270 Media-Processor, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.331-342, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.35]
• 50: Veredas, F. J., Scheppler, M., Moffat, W., and Mei, B. 2005. Custom implementation of the coarse-grained reconfigurable ADRES architecture for multimedia purposes. In Proceedings of the International Conference on Field Programmable Logic and Applications, Tampere, Finland. IEEE Computer Society Press, Los Alamitos, CA. 106--111.
• 51: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Hierarchical Clustered Register File Organization for VLIW Processors, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.77.1, April 22-26, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

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

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications

General Terms:
Design, Experimentation, Languages, Performance

Keywords:
Instruction-level parallelism, VLIW, clock frequency, cluster assignment, instruction scheduler, intercluster communication, optimizing compiler, pipelining, register allocation