Article

Free access

Realistic scheduling: compaction for pipelined architectures

Authors:

Alexandru Nicolau,

Roni PotasmanAuthors Info & Claims

MICRO 23: Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture

Pages 69 - 79

Published: 30 November 1990 Publication History

PDF eReader

Abstract

This paper presents an approach for the development of microcode for parallel and pipelined machines. The approach is geared towards mapping programs with real-time constraints and/or massive time requirements onto synchronous parallel computers (VLIW's, superscalars and microengines). In order to exploit the maximal parallelism from such machines, both spatial (multiple functional units) and temporal (pipelined) capabilities of the architecture need to be exploited. Until now, parallelizing compilers for parallel machines have not fully taken advantage of pipelining capabilities: they have either assumed that all operations take one cycle or have added pipelining as an after thought. These approaches restrict the speed-up. We built a system which is based on a set of low-level transformations called Pipelined Percolation Scheduling (PPS). The transformations integrate the exploitation of temporal and spatial parallelism. Although these low-level transformations are integrated into our system they are self-contained and may be used separately by applying 'higher level' transformations (on top of PPS) to optimize performance for a target architecture.

References

[1]

A. S. Aiken. Compaction-Based Parallelization. PhD thesis, Cornell University, August 1988.

Digital Library

Google Scholar

[2]

A. Aiken and A. Nicolau. A Development Environment for Horizontal Microcode. IEEE Transactions on Software Engineering, Vol. 14, No. 5, May 1988.

Digital Library

Google Scholar

[3]

A. Aiken and A. Nicolau. Perfect Pipelining: A new loop parallelization technique. In Proceedings of the 1988 European Symposium on Programming. Springer Verlag Lecture Notes in Computer Science no. 300, March 1988.

Digital Library

Google Scholar

[4]

R. P. Colwell, R. P. Nix, J. J.O'Donnell,D. B. Papworth,P. K. Rodman. A VLIW architecture for a Trace Scheduling Compiler. IEEE Transactions on Computers, Vol. 37, No. 8,1988.

Digital Library

Google Scholar

[5]

K.Ebcioglu. A Compilation Technique for Software Pipeliningof Loops with Conditional Jumps. Proceedings of the 20th Annual Workshop on Microprogramming, pp. 69-79, ACM Press, 1987.

Digital Library

Google Scholar

[6]

K.Ebcioglu. Some Design Ideas for a VLIW Architecture for Sequential-Natured Software. Proceedings IFIP, 1988.

Google Scholar

[7]

K.Ebcioglu, and T. Nakatani. A New Compilation Technique for Parallelizing Loops with Unpredictable Branches on a VLIW Architecture. Proceedings of the 2nd Workshop on Programming Languages and Compilers for Parallel Computing, 1989.

Digital Library

Google Scholar

[8]

K.Ebcioglu, and A.Nicolau. A global resource-constrained parallelization technique. Proc. ACM SIGARCH ICS-89: International Conference on Supercomputing, Crete, Greece June 2-9 1989.

Digital Library

Google Scholar

[9]

J. R. Ellis. Bulldog- A Compiler for VLIW Architectures. MIT Press, 1986.

Digital Library

Google Scholar

[10]

J. A. Fisher. Trace Scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, No. 7,pp. 478-490, 1981.

Google Scholar

[11]

T. Gross, M. S. Lam. Compilation for highperformance systolic array. Proceedings of the 1986 SIGPLAN Symposium on Compiler Construction, July 1986.

Digital Library

Google Scholar

[12]

A. Nicolau. Percolation Scheduling: A parallel compilation technique. Technical Report 85-678, Cornell University, 1984.

Digital Library

Google Scholar

[13]

B. R Rau, C. D. Glaeser. Efficient Code Generation for Horizontal Architectures: Compiler Techniques and Architectural Support. Proceedings of the 9th Symposium on Computer Architecture, April 1982.

Digital Library

Google Scholar

Cited By

View all

Conte TSathaye S(2000)Properties of Rescheduling Size Invariance for Dynamic Rescheduling-Based VLIW Cross-Generation CompatibilityIEEE Transactions on Computers10.1109/12.86802749:8(814-825)Online publication date: 1-Aug-2000
https://dl.acm.org/doi/10.1109/12.868027
Stotzer ELeiss E(1999)Modulo scheduling for the TMS320C6x VLIW DSP architectureACM SIGPLAN Notices10.1145/315253.31442734:7(28-34)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/315253.314427
Stotzer ELeiss ELiu YWilhelm R(1999)Modulo scheduling for the TMS320C6x VLIW DSP architectureProceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems10.1145/314403.314427(28-34)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/314403.314427
Show More Cited By

Realistic scheduling: compaction for pipelined architectures
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Dynamically Scheduling VLIW Instructions

Very long instruction word (VLIW) machines potentially provide the most direct way to exploit instruction-level parallelism; however, they cannot be used to emulate current general-purpose instruction set architectures. In addition, programs scheduled ...
Evaluation of scheduling techniques on a SPARC-based VLIW testbed
MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture

The performance of Very Long Instruction Word (VLIW) microprocessors depends on the close cooperation between the compiler and the architecture. This paper evaluates a set of important compilation techniques and related architectural features for VLIW ...
Lazy instruction scheduling: keeping performance, reducing power
ISLPED '08: Proceedings of the 2008 international symposium on Low Power Electronics & Design

An important approach to reduce power dissipation is reducing the number of instructions executed by the processor. To achieve this goal, this paper introduces a novel instruction scheduling algorithm that executes an instruction only when its result is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MICRO 23: Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture

November 1990

299 pages

ISBN:0897914139

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 30 November 1990

Check for updates

Qualifiers

Article

Conference

MICRO90

Sponsor:

SIGMICRO
IEEE-CS

MICRO90: 23nd Annual Workshop on Microprogramming and Microarchitecture

November 27 - 29, 1990

Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
211
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)9

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Conte TSathaye S(2000)Properties of Rescheduling Size Invariance for Dynamic Rescheduling-Based VLIW Cross-Generation CompatibilityIEEE Transactions on Computers10.1109/12.86802749:8(814-825)Online publication date: 1-Aug-2000
https://dl.acm.org/doi/10.1109/12.868027
Stotzer ELeiss E(1999)Modulo scheduling for the TMS320C6x VLIW DSP architectureACM SIGPLAN Notices10.1145/315253.31442734:7(28-34)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/315253.314427
Stotzer ELeiss ELiu YWilhelm R(1999)Modulo scheduling for the TMS320C6x VLIW DSP architectureProceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems10.1145/314403.314427(28-34)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/314403.314427
Allan VRajagopalan MLee R(1993)Software PipeliningProceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism10.5555/647025.714365(15-26)Online publication date: 20-Jan-1993
https://dl.acm.org/doi/10.5555/647025.714365
Rau BSchlansker MTirumalai PHwu W(1992)Code generation schema for modulo scheduled loopsProceedings of the 25th annual international symposium on Microarchitecture10.5555/144953.145795(158-169)Online publication date: 10-Dec-1992
https://dl.acm.org/doi/10.5555/144953.145795
Rau BSchlansker MTirumalai P(1992)Code generation schema for modulo scheduled loopsACM SIGMICRO Newsletter10.1145/144965.14579523:1-2(158-169)Online publication date: 10-Dec-1992
https://dl.acm.org/doi/10.1145/144965.145795
Rau BLee MTirumalai PSchlansker M(1992)Register allocation for software pipelined loopsACM SIGPLAN Notices10.1145/143103.14314127:7(283-299)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/143103.143141
Rau BLee MTirumalai PSchlansker MFeldman S(1992)Register allocation for software pipelined loopsProceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation10.1145/143095.143141(283-299)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/143095.143141
Jones RAllan VMalaiya Y(1991)Software pipeliningProceedings of the 24th annual international symposium on Microarchitecture10.1145/123465.123481(82-92)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1145/123465.123481

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Dynamically Scheduling VLIW Instructions

Evaluation of scheduling techniques on a SPARC-based VLIW testbed

Lazy instruction scheduling: keeping performance, reducing power