Modulo scheduling with integrated register spilling for clustered VLIW architectures

ABSTRACT

Clustering is a technique to decentralize the design of future wide issue VLIW cores and enable them to meet the technology constraints in terms of cycle time, area and power dissipation. In a clustered design, registers and functional units are grouped in clusters so that new instructions are needed to move data between them. New aggressive instruction scheduling techniques are required to minimize the negative effect of resource clustering and delays in moving data around.In this paper we present a novel software pipelining technique that performs instruction scheduling with reduced register requirements, register allocation, register spilling and inter-cluster communication in a single step. The algorithm uses limited backtracking to reconsider previously taken decisions. This backtracking provides the algorithm with additional possibilities for obtaining high throughput schedules with low spill code requirements for clustered architectures. We show that the proposed approach outperforms previously proposed techniques and that it is very scalable independently of the number of clusters, the number of communication buses and communication latency. The paper also includes an exploration of some parameters in the design of future clustered VLIW cores.

REFERENCES

• 1: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 2: M. Berry, D. Chen, P. Koss, and D. Kuck. The Perfect Club benchmarks: Effective performance evaluation of supercomputers. Technical Report 827, Center for Supercomputing Research and Development, November 1988.
• 3: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
• 4: 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
• 5: A. Charlesworth. An approach to scientific array processing: The architectural design of the AP120B/FPS-164 family. Computer, 14(9):18-27, 1981.
• 6: A. Dani, Register-Sensitive Software Pipelining, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.194, March 30-April 03, 1998
• 7: James C. Dehnert , Ross A. Towle, Compiling for the Cydra 5, The Journal of Supercomputing, v.7 n.1-2, p.181-227, May 1993 [doi>10.1007/BF01205184]
• 8: G. Desoli. Instruction assignment for clustered VLIW DSP compilers: A new approach. Technical Report HPL-98-13, HP Laboratories, January 1998.
• 9: Alexandre E. Eichenberger , Edward S. Davidson, Stage scheduling: a technique to reduce the register requirements of a modulo schedule, Proceedings of the 28th annual international symposium on Microarchitecture, p.338-349, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 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: Partitioned Schedules for Clustered VLIW Architectures, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.386, March 30-April 03, 1998
• 13: Joseph A. Fisher, Very Long Instruction Word architectures and the ELI-512, Proceedings of the 10th annual international symposium on Computer architecture, p.140-150, June 13-17, 1983, Stockholm, Sweden
• 14: Jose Fridman , Zvi Greenfield, The TigerSHARC DSP Architecture, IEEE Micro, v.20 n.1, p.66-76, January 2000 [doi>10.1109/40.820055]
• 15: P. N. Glaskowsky. MAP1000 unfolds at Equator. Microporcessor Report., 12(16), December 1998.
• 16: Richard A. Huff, Lifetime-sensitive modulo scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.258-267, June 21-25, 1993, Albuquerque, New Mexico, United States
• 17: T. I. Inc. TMS320C62x/67x CPU and Instruction Set Reference Guide. 1998.
• 18: S. Jang, S. Carr, P. Sweany, and D. Kuras. A code geration framework for VLIW architectures with partitioned register banks. In Procs. of 3rd. Int. Conf. on Massively Parallel Computing Systems, April 1998.
• 19: 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
• 20: Josep Llosa , Eduard Ayguadé , Antonio Gonzalez , Mateo Valero , Jason Eckhardt, Lifetime-Sensitive Modulo Scheduling in a Production Environment, IEEE Transactions on Computers, v.50 n.3, p.234-249, March 2001 [doi>10.1109/12.910814]
• 21: Josep Llosa , Mateo Valero , Eduard Ayguadé, Heuristics for register-constrained software pipelining, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.250-261, December 02-04, 1996, Paris, France
• 22: Josep Llosa , Mateo Valero , Eduard Ayguadé , Antonio González, Hypernode reduction modulo scheduling, Proceedings of the 28th annual international symposium on Microarchitecture, p.350-360, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 23: 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
• 24: 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
• 25: S. Ramakrishnan. Software pipelining in PA-RISC compilers. Hewlett-Packard Journal, pages 39-45, July 1992.
• 26: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 27: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 28: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 29: S. Rixner, W. Dally, B. Khailany, P. Mattson, U. Kapasi, and J. Owens. Register organization for media processing. In Proc., 6th High-Performance Computer Architecture (HPCA-6), pages 375-386, January 2000.
• 30: F. Jesús Sánchez , Antonio González, Cache sensitive modulo scheduling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.338-348, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 31: Jesús Sánchez , Antonio González, The Effectiveness of Loop Unrolling for Modulo Scheduling in Clustered VLIW Architectures, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.555, August 21-24, 2000
• 32: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Improved spill code generation for software pipelined loops, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.134-144, June 18-21, 2000, Vancouver, British Columbia, Canada
• 33: J. Zalamea, J. Llosa, E. Ayguadé, and M. Valero. MIRS: Modulo scheduling with integrated register spilling. In Proc. of 14th Annual Workshop on Languages and Compilers for Parallel Computing (LCPC2001), August 2001.