article

Free access

Precise instruction scheduling without a precise machine model

Author:

Henry G. BakerAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 19, Issue 6

Pages 4 - 8

https://doi.org/10.1145/152766.152767

Published: 01 December 1991 Publication History

Abstract

A simple technique is presented which allows an optimizing compiler to more precisely compare the performance of alternative instruction sequences on a complex RISC architecture so that the better sequence can be chosen. This technique may be faster than current techniques, and has the advantage that minor modifications to the hardware do not require any changes to the compiler (not even recompilation), and yet have an immediate effect on instruction scheduling decisions.

References

[1]

Appel, Andrew. Private communication, July, 1991.

[2]

ATT. WE® DSP32C Digital Signal Processor Advance Data Sheet. ATT Microelectronics, Allentown, PA, May 1988.

[3]

Baker, Henry, and Parker, Clinton. Micro SPL. Synapse Computer Services, Sept. 1979.

[4]

Baker, Henry, and Parker, Clinton. "High Level Language Programs Run Ten Times Faster in Microstore". Tech. Rept., Synapse Computer Services, 1980.

[5]

Bradlee, David G., et al. "The Marion System for Retargetable Instruction Scheduling". Proc. ACM PLDI'91, Sigplan Not. 26, 6 (June 1991), 229-240.

Digital Library

[6]

Chambers, C., and Ungar, D. "Customization: Optimizing Compiler Technology for SELF, A Dynamically-Typed Object-Oriented Programming Language". Proc. ACM PLDI'89, Sigplan Not. 24, 7 (July 1989), 146-160.

Digital Library

[7]

Chambers, C., Ungar, D., and Lee, E. "An Efficient Implementation of SELF, A Dynamically-Typed Object-Oriented Programming Language". Proc. OOPSLA'89, Sigplan Not. 24, 10 (Oct. 1989), 49-70.

Digital Library

[8]

Deutsch, L.P., and Schiffman, A.M. "Efficient Implementation of the Smalltalk-80 System". Proc. 11'th ACM POPL, Salt Lake City, UT, Jan. 1984, 297-302.

Digital Library

[9]

Ellis, John R. Bulldog: A Compiler for VLIW Architectures. MIT Press, Cambridge, MA, 1986.

Digital Library

[10]

Gibbons, P.B., and Muchnick, S.S. "Efficient instruction scheduling for a pipelined architecture". Proc. ACM Symp. on Compiler Constr., Sigplan Not. 21, 7 (July 1986), 11-16.

Digital Library

[11]

Hennessy, John, and Gross, Thomas. "Postpass Code Optimization of Pipeline Constraints". ACM TOPLAS 5, 3 (July 1983), 422-448.

Digital Library

[12]

Intel Corp. i860^TM [XR] 64-Bit Microprocessor Programmer's Reference Manual. #240329-002, 1989.

[13]

Intel Corp. i860^TMMicroprocessor Family Programmer's Reference Manual. #240875-001, 1991.

Digital Library

[14]

Intel Corp. i860^TM 64-bit Microprocessor Simulator and Debugger Reference Manual, Ver. 3. #240437-003, Jan. 1990.

[15]

Keppel, David. "A Portable Interface for On-The-Fly Instruction Space Modification". Proc. 4'th ACM ASPLOS, Sigplan Not. 26, 4 (April 1991), 86-95.

Digital Library

[16]

Knuth, Donald E. The Art of Computer Programming Vol. I: Fundamental Algorithms, 2nd Ed. Addison-Wesley, Reading, MA, 1973, 634 p.

Digital Library

[17]

Kogge, P.M. The Architecture of Pipelined Computers. McGraw-Hill, New York, 1981.

[18]

Massalin, Henry. "Superoptimizer--A Look at the Smallest Program". Proc. ACM ASPLOS'87, Sigplan Not. 22, 10 (Oct. 1987), 122-126.

Digital Library

[19]

Morris, W.G. "CCG: A Prototype Coagulating Code Generator". Proc. ACM PLDI'91, Sigplan Not. 26, 6 (June 1991), 45-58.

Digital Library

[20]

Moyer, Steven A. "Performance of the iPSC/860 Node Architecture". IPC-TR-91-007, Inst. for Parallel Comp., Eng. & Applied Sci., U. of Va., May 1991.

Digital Library

[21]

Scott, D.S., and Withers, G.R. "Performance and Assembly Language Programming of the iPSC/860 System". Tech. Report, Intel Supercomputer Systems Div., Beaverton, OR, 1990.

[22]

Texas Inst. TMS320C30: The Third Generation of the TMS320 Family of Digital Signal Processors. Texas Instruments, Feb. 1988.

[23]

Wirth, Niklaus. "From Programming Language Design to Computer Construction". CACM 28, 2 (Feb. 1985), 160-164.

Digital Library

[24]

Xerox Corp. ALTO: A Personal Computer System Hardware Manual. Xerox PARC, Palo Alto, CA, Jan. 1977.

Cited By

Bergstra JMiddelburg C(2012)On the Behaviours Produced by Instruction Sequences under ExecutionFundamenta Informaticae10.5555/2594813.2594814120:2(111-144)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2594813.2594814
Bergstra JMiddelburg C(2012)Instruction sequence processing operatorsActa Informatica10.1007/s00236-012-0154-249:3(139-172)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s00236-012-0154-2
Bergstra JMiddelburg C(2012)On the Expressiveness of Single-Pass Instruction SequencesTheory of Computing Systems10.1007/s00224-010-9301-850:2(313-328)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00224-010-9301-8
Show More Cited By

Recommendations

Precise Runahead Execution
Runahead execution improves processor performance by accurately prefetching long-latency memory accesses. When a long-latency load causes the instruction window to fill up and halt the pipeline, the processor enters runahead mode and keeps speculatively ...
Effective instruction scheduling with limited registers
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

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 19, Issue 6

Dec. 1991

20 pages

ISSN:0163-5964

DOI:10.1145/152766

Editor:
Doug DeGroot
Texas Instruments Inc., Dallas, TX

Issue’s Table of Contents

Copyright © 1991 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1991

Published in SIGARCH Volume 19, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)10

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bergstra JMiddelburg C(2012)On the Behaviours Produced by Instruction Sequences under ExecutionFundamenta Informaticae10.5555/2594813.2594814120:2(111-144)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2594813.2594814
Bergstra JMiddelburg C(2012)Instruction sequence processing operatorsActa Informatica10.1007/s00236-012-0154-249:3(139-172)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s00236-012-0154-2
Bergstra JMiddelburg C(2012)On the Expressiveness of Single-Pass Instruction SequencesTheory of Computing Systems10.1007/s00224-010-9301-850:2(313-328)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00224-010-9301-8
Bridges MVachharajani NOttoni GAugust DSchwartzbach MBall T(2006)Automatic instruction scheduler retargeting by reverse-engineeringProceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1133981.1134008(228-238)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133981.1134008
Bridges MVachharajani NOttoni GAugust D(2006)Automatic instruction scheduler retargeting by reverse-engineeringACM SIGPLAN Notices10.1145/1133255.113400841:6(228-238)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133255.1134008
Collberg C(2002)Automatic derivation of compiler machine descriptionsACM Transactions on Programming Languages and Systems10.1145/567097.56710024:4(369-408)Online publication date: 1-Jul-2002
https://dl.acm.org/doi/10.1145/567097.567100
Collberg C(1997)Reverse interpretation + mutation analysis = automatic retargetingACM SIGPLAN Notices10.1145/258916.25892232:5(57-70)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/258916.258922
Collberg CChen MCytron R(1997)Reverse interpretation + mutation analysis = automatic retargetingProceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation10.1145/258915.258922(57-70)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.1145/258915.258922

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents