Cluster assignment of global values for clustered VLIW processors

ABSTRACT

In this paper high-level language (HLL) variables that are alive in a whole HLL function, across multiple scheduling units, are termed as global values. Due to their long live ranges and, hence, large impact on the schedule, the global values require different compiler optimizations than local values, which span across only one scheduling unit. The instruction scheduler for a clustered ILP processor, which is responsible for cluster assignment of operations and variables, faces a difficult problem of assigning global values to clusters. Our study shows that trivial assignments (e.g. mapping all global values into one cluster) may result in a severe cycle count overhead relative to the unicluster of up to 26.3% for a four cluster VLIW machine. This paper presents three advanced algorithms for assigning global values to clusters based on multi-pass scheduling and affinity of variables. Furthermore, we measure performance of these algorithms on optimized multimedia C applications and assess quality of our algorithms by comparing them to a practical higher performance bound derived from a vast random search. Our algorithms reduce the execution time overhead of the best simple algorithm round-robin from 10.5% to 5.9% for the two cluster VLIW machine and from 17.3% to 14.12% for the four cluster VLIW machine.

REFERENCES

• 1: S. Rixner, W.J. Dally, et al. "Register organization for media processing", In Proceedings of 26th International Symposium on High-Performance Computer Architecture, Orlando, January 1999.
• 2: R. Ho, K. Mai, and M. Horowitz, "The Future of Wires", In Proceedings of the IEEE, pp. 490--504, April 2001.
• 3: Texas Instrument TMS320C64xx DSP Generation. http://www.ti.com.
• 4: M. Levy, "ManArray devours DSP code", Microprocessor report, October 2001.
• 5: 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
• 6: P. Faraboschi, G. Desoli, J.A. Fisher, "Clustered instruction-level parallel processors", HPL-98-204, HP Laboratory, Cambridge, December 1998.
• 7: S. Sudharsanan, P. Sriram, et al., "Image And Video Processing Using MAJC 5200", In Proceedings of International Conference on Image Processing, Canada, September 2000.
• 8: Sun MAJC architecture tutorial, http://www.sun.com/.
• 9: S. Sudharsanan, "MAJC-5200: a high performance microprocessor for multimedia computing", White paper, http://www.sun.com.
• 10: Johan Janssen , Henk Corporaal, Partitioned register file for TTAs, Proceedings of the 28th annual international symposium on Microarchitecture, p.303-312, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 11: J. Janssen, "Compiler Strategies for Transport Triggered Architecture", PhD thesis, TU Deflt, The Netherlands, 2001.
• 12: S. Roos, H. Corporaal, et al., "Clustering on the Move", In Proceedings of 4th International Conference on Massively Parallel Computing Systems, Ischia Italy, April 2002.
• 13: J. Hoogerbrugge, L. Augusteijn, "Instruction scheduling for TriMedia", The Journal of Instruction-Level Parallelism, February 1999.
• 14: Selliah Rathnam , Gert Slavenburg, An Architectural Overview of the Programmable Multimedia Processor, TM-1, Proceedings of the 41st IEEE International Computer Conference, p.319, February 25-28, 1996
• 15: A. K. Riemens , G. D. La Hei, TriMedia CPU64 Application Domain and Benchmark Suite, Proceedings of the 1999 IEEE International Conference on Computer Design, p.580, October 10-13, 1999
• 16: 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
• 17: 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
• 18: Viktor S. Lapinskii , Margarida F. Jacome , Gustavo A. de Veciana, High-quality operation binding for clustered VLIW datapaths, Proceedings of the 38th conference on Design automation, p.702-707, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379051]
• 19: 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
• 20: 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
• 21: 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
• 22: J. H. Moreno , M. Moudgill , K. Ebcioğlu , E. Altman , C. B. Hall , R. Miranda , S.-K. Chen , A. Polyak, Simulation/evaluation environment for a VLIW processor architecture, IBM Journal of Research and Development, v.41 n.3, p.287-302, May 1997
• 23: M. Moudgill, "Implementing an Experimental VLIW compiler", IEEE Technical Committee on Computer Architecture Newsletter, pp. 39--40, June 1997.
• 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: 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
• 26: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 27: J.A. Fisher, "Trace Scheduling: a Technique for Global Microcode Compaction", IEEE Transactions on Computers, vol. C-30, pp. 478--490, July 1981.
• 28: Jason Hiser , Steve Carr , Philip Sweany, Global Register Partitioning, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.13, October 15-19, 2000
• 29: David J. Kolson , Alexandru Nicolau , Nikil D. Dutt , Ken Kennedy, A Method for Register Allocation to Loops in Multiple Register File Architectures, Proceedings of the 10th International Parallel Processing Symposium, p.28-33, April 15-19, 1996
• 30: 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
• 31: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Modulo scheduling with integrated register spilling for clustered VLIW architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 32: J. Sánchez, A. González, "Clustered Modulo Scheduling in a VLIW Architecture with Distributed Cache", Journal on Instruction Level Parallelism (JILP), Volume 3, October 2001.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
ILP, VLIW, cluster assignment, compiler, instruction scheduler, register allocation