Article

Free access

Trace selection for compiling large C application programs to microcode

Authors:

P. P. Chang,

W. W. HwuAuthors Info & Claims

MICRO 21: Proceedings of the 21st annual workshop on Microprogramming and microarchitecture

Pages 21 - 29

Published: 03 January 1988 Publication History

PDF eReader

Abstract

Microcode optimization techniques such as code scheduling and resource allocation can benefit significantly by reducing uncertainties in program control flow. A trace selection algorithm with profiling information reduces the uncertainties in program control flow by identifying sequences of frequently invoked basic blocks as traces. These traces are treated as sequential codes for optimization purposes. Optimization based on traces is especially useful when the code size is large and the control structure is complicated enough to defeat hand optimizations. However, most of the experimental results reported to date are based on small benchmarks with simple control structures.

For different trace selection algorithms, we report the distribution of control transfers categorized according to their potential impact on the microcode optimizations. The experimental results are based on ten C application programs which exhibit large code size and complicated control structure. The measured data for each program is accumulated across a large number of input files to ensure the reliability of the result. All experiments are performed automatically using our IMPACT C compiler which contains integrated profiling and analysis tools.

References

[1]

A.V. Aho, R. Sethi, and J.D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley Publishing Company, 1986.

Digital Library

Google Scholar

[2]

D.J. Kuck, R.H. Kuhn, D.A. Padu.a, B. Leasure and M. Wolfe, "Dependence Graphs and Compiler Optimizations," Proceedings of the 8th ACM Symposium on Principles of Programming Languages, Jan., 1981.

Digital Library

Google Scholar

[3]

Ron Cytron and Jeanne Ferrante, "The Value of Renaming for Parallelism Detection and Storage Allocation," Proceedings of the 1987 International Conference on Parallel Processing, Aug., 1987.

Google Scholar

[4]

Mario Tokoro, Eiji Tamura and Takashi Takizuka, "Optimization of Microprograms," IEEE Transactions on Computers, vol. c-30, no.7, July, 1981.

Google Scholar

[5]

Joseph A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, vol. c-30, no.7, July, 1981.

Google Scholar

[6]

John Hennessy and Thomas Gross, "Postpass Code Optimization of Pipeline Constraints," ACM Transactions on Programming Languages and Systems, vol. 5, no.3, July, 1983.

Digital Library

Google Scholar

[7]

B. Su, S. Ding, and J. Xia, "URPR - An Extension of URCR for Software Pipelining," Proceedings of the 19th Microprogramming Workshop, New York, NY, Dec., 1986.

Digital Library

Google Scholar

[8]

Wen-mei W. Hwu and Pohua P. Chang, "Exploiting Parallel Microprocessor Microarchitectures with a Compiler Code Generator," The 15th Annual International Symposium on Computer Architecture, Honolulu, Hawaii, May, 1988.

Digital Library

Google Scholar

[9]

J.L. Linn, "SRDAG Compaction: A Generalization of Trace Scheduling to Increase the Use of Global Context Information," Proceedings of the 16th Microprogramming Workshop, Downingtown, PA., Oct., 1983.

Google Scholar

[10]

B. Su, S. Ding, and L. Jin, "An Improvement of Trace Scheduling for Global Microcode Compaction," Proceedings of the 17th Microprogramming Workshop, New Orleans, LA., Nov., 1984.

Digital Library

Google Scholar

[11]

J.R. Ellis, Bulldog: A Compiler for VLIW Architectures. The MIT Press, 1985, PhD thesis, Yale, 1984.

Digital Library

Google Scholar

[12]

Michael A. Howland, Robert A. Mueller and Philip H. Sweany, "Trace Scheduling Optimization in a Retargetable Microcode Compiler," Proceedings of the 20th International Microprogramming Workshop, Colorado Springs, Dec., 1987.

Digital Library

Google Scholar

Cited By

View all

Lehmann DPradel MBahar IHerlihy MWitchel ELebeck A(2019)WasabiProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304068(1045-1058)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304068
Das ALu JChen HKim JYew PHsu WChen D(2005)Performance of Runtime Optimization on BLASTProceedings of the international symposium on Code generation and optimization10.1109/CGO.2005.25(86-96)Online publication date: 20-Mar-2005
https://dl.acm.org/doi/10.1109/CGO.2005.25
Ravindran RNagarkar PDasika GMarsman ESenger RMahlke SBrown R(2005)Compiler Managed Dynamic Instruction Placement in a Low-Power Code CacheProceedings of the international symposium on Code generation and optimization10.1109/CGO.2005.13(179-190)Online publication date: 20-Mar-2005
https://dl.acm.org/doi/10.1109/CGO.2005.13
Show More Cited By

Index Terms

Trace selection for compiling large C application programs to microcode
1. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

A trace simplification technique for effective debugging of concurrent programs
FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering

Concurrent programs are notoriously difficult to debug. We see two main reasons for this: 1) concurrency bugs are often difficult to reproduce, 2) traces of buggy concurrent executions can be complicated by fine-grained thread interleavings. Recently, a ...
Trace Size vs. Parallelism in Trace-and-Replay Debugging of Shared-Memory Programs
Reducing trace selection footprint for large-scale Java applications without performance loss
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

When optimizing large-scale applications, striking the balance between steady-state performance, start-up time, and code size has always been a grand challenge. While recent advances in trace compilation have significantly improved the steady-state ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MICRO 21: Proceedings of the 21st annual workshop on Microprogramming and microarchitecture

January 1988

139 pages

ISBN:0818619198

Chairman:
Yale N. Patt

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 03 January 1988

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
682
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)12

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lehmann DPradel MBahar IHerlihy MWitchel ELebeck A(2019)WasabiProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304068(1045-1058)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304068
Das ALu JChen HKim JYew PHsu WChen D(2005)Performance of Runtime Optimization on BLASTProceedings of the international symposium on Code generation and optimization10.1109/CGO.2005.25(86-96)Online publication date: 20-Mar-2005
https://dl.acm.org/doi/10.1109/CGO.2005.25
Ravindran RNagarkar PDasika GMarsman ESenger RMahlke SBrown R(2005)Compiler Managed Dynamic Instruction Placement in a Low-Power Code CacheProceedings of the international symposium on Code generation and optimization10.1109/CGO.2005.13(179-190)Online publication date: 20-Mar-2005
https://dl.acm.org/doi/10.1109/CGO.2005.13
Bradel BAbdelrahman T(2004)The use of traces for inlining in java programsProceedings of the 17th international conference on Languages and Compilers for High Performance Computing10.1007/11532378_14(179-193)Online publication date: 22-Sep-2004
https://dl.acm.org/doi/10.1007/11532378_14
Magklis GScott MSemeraro GAlbonesi DDropsho S(2003)Profile-based dynamic voltage and frequency scaling for a multiple clock domain microprocessorACM SIGARCH Computer Architecture News10.1145/871656.85962131:2(14-27)Online publication date: 1-May-2003
https://dl.acm.org/doi/10.1145/871656.859621
Magklis GScott MSemeraro GAlbonesi DDropsho SGottlieb ALi K(2003)Profile-based dynamic voltage and frequency scaling for a multiple clock domain microprocessorProceedings of the 30th annual international symposium on Computer architecture10.1145/859618.859621(14-27)Online publication date: 9-Jun-2003
https://dl.acm.org/doi/10.1145/859618.859621
Rosner RMoffie MSazeides YRonen RBanerjee UGallivan KGonzalez A(2003)Selecting long atomic traces for high coverageProceedings of the 17th annual international conference on Supercomputing10.1145/782814.782818(2-11)Online publication date: 23-Jun-2003
https://dl.acm.org/doi/10.1145/782814.782818
Jacome Mde Veciana GPillai SRabaey J(2001)Clustered VLIW architecture with predicated switchingProceedings of the 38th annual Design Automation Conference10.1145/378239.379050(696-701)Online publication date: 22-Jun-2001
https://dl.acm.org/doi/10.1145/378239.379050
Rotenberg ESmith JRonen RFarrens MSpillinger I(1999)Control independence in trace processorsProceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture10.5555/320080.320084(4-15)Online publication date: 16-Nov-1999
https://dl.acm.org/doi/10.5555/320080.320084
Rotenberg EBennett SSmith J(1999)A Trace Cache Microarchitecture and EvaluationIEEE Transactions on Computers10.1109/12.75265248:2(111-120)Online publication date: 1-Feb-1999
https://dl.acm.org/doi/10.1109/12.752652
Show More Cited By

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

Index Terms

Recommendations

A trace simplification technique for effective debugging of concurrent programs

Trace Size vs. Parallelism in Trace-and-Replay Debugging of Shared-Memory Programs

Reducing trace selection footprint for large-scale Java applications without performance loss