Article

Free access

RTGEN: An Algorithm for Automatic Generation of Reservation Tables from Architectural Descriptions

Authors:

Alex NicolauAuthors Info & Claims

ISSS '99: Proceedings of the 12th international symposium on System synthesis

Page 44

Published: 01 November 1999 Publication History

PDF eReader Publisher Site

Abstract

Reservation Tables (RTs) have long been used to detect conflicts between operations that simultaneously access the same architectural resource. Traditionally, these RTs have been specified explicitly by the designer. However, the increasing complexity of modern processors makes the manual specification of RTs cumbersome and error-prone. Furthermore, manual specification of such conflict information is infeasible for supporting rapid architectural exploration. In this paper we present an algorithm to automatically generate RTs from a high-level processor description, with the goal of avoiding manual specification of RTs, resulting in more concise architectural specifications and also supporting faster turn-around time in Design Space Exploration. We demonstrate the utility of our approach on a set of experiments using the TI C6201 VLIW DSP and DLX processor architectures, and a suite of multimedia and scientific applications.

References

[1]

{1} V. Bala and N. Rubin. Efficient instruction scheduling using finite state automata. IJPP, 25(2):53-82, 1997.

Digital Library

[2]

{2} E. S. Davidson. The design and control of pipelined function generators. In IEEE Conf. SNC, pages 19-21, Mexico, 1971.

[3]

{3} A. E. Eichenberger and E. S. Davidson. A reduced multipipeline description that preserves scheduling constraints. In PLDI, pages 12-20, May 1996.

Digital Library

[4]

{4} E. S. Davidson et al. Effective control for pipelined processors. In IEEE COMPCON, pages 181-184, San Fransisco, 1975.

[5]

{5} G. Hadjiyiannis et al. ISDL: An instruction set description language for retargetability. In Proc. DAC, 1997.

Digital Library

[6]

{6} J. C. Gyllenhaal et al. Optimization of machine descriptions for efficient use. IJPP, 26(4):417-447, 1998.

Digital Library

[7]

{7} P. G. Lowney et al. The multiflow trace scheduling compiler. J. Supercomputing , 7:51-142, 1993.

Digital Library

[8]

{8} V. Zivojnovic et al. LISA - machine description language and generic machine model for HW/SW co-design. In IEEE Workshop on VLSI Signal Processing, 1996.

[9]

{9} M. Freericks. The nML machine description formalism. Technical Report TR SM-IMP/DIST/08, TU Berlin CS Dept., 1993.

[10]

{10} P. Grun, A. Halambi, N. Dutt, and A. Nicolau. Automatic generation of reservation tables from an architecture description. Technical report, University of California, Irvine, 1999.

[11]

{11} A. Halambi, P. Grun, V. Ganesh, A. Khare, N. Dutt, and A. Nicolau. EXPRESSION: A language for architecture exploration through compiler/simulator retargetability. In Proc. DATE, March 1999.

Digital Library

[12]

{12} J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, 1996.

Digital Library

[13]

{13} A. Khare, N. Savoiu, A. Halambi, P. Grun, N. Dutt, and A. Nicolau. V-SAT: A visual specification and analysis tool for system-on-chip exploration. In Proc. EUROMICRO, October 1999.

[14]

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

[15]

{15} R. Leupers and P. Marwedel. Retargetable code generation based on structural processor descriptions. Design Automation for Embedded Systems , 3(1), 1998.

[16]

{16} S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, 1997.

Digital Library

[17]

{17} S. Novack, A. Nicolau, and N. Dutt. A unified code generation approach using mutation scheduling. In Code Gen. for Embedded Processors. Kluwer, 1995.

[18]

{18} T. A. Proebsting and C. W. Fraser. Detecting pipeline hazards quickly. In PPL, January 1994.

Digital Library

[19]

{19} B. R. Rau. Iterative modulo scheduling: An algorithm for software pipelining loops. In Proc. 27th Microarchit., November 1994.

Digital Library

[20]

{20} C. Siska. A processor description language supporting retargetable multi-pipeline dsp program development tools. In Proc. ISSS, December 1998.

Digital Library

[21]

{21} TEXAS INSTRUMENTS. TMS320C62x/C67xCPU and Instruction Set Reference Guide, 1998.

[22]

{22} Trimaran Release: http://www.trimaran.org. The MDES User Manual, 1997.

Cited By

Najaf-Abadi HImai M(2004)A procedure for obtaining a behavioral description for the control logic of a non-linear pipelineProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015112(86-91)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015112
Mishra PMamidipaka MDutt N(2004)Processor-memory coexploration using an architecture description languageACM Transactions on Embedded Computing Systems10.1145/972627.9726343:1(140-162)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1145/972627.972634
Wahlen OHohenauer MLeupers RMeyr H(2003)Instruction Scheduler Generation for Retargetable CompilationIEEE Design & Test10.1109/MDT.2003.117305120:1(34-41)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/MDT.2003.1173051
Show More Cited By

Recommendations

RTGEN: an algorithm for automatic generation of reservation tables from architectural descriptions

Reservation Tables (RTs) have long been used to detect conflicts between operations that simultaneously access the same architectural resource. Traditionally, these RTs have been specified explicitly by the designer. However, the increasing complexity ...
An evaluation of speculative instruction execution on simultaneous multithreaded processors

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...
Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading

To achieve high performance, contemporary computer systems rely on two forms of parallelism: instruction-level parallelism (ILP) and thread-level parallelism (TLP). Wide-issue super-scalar processors exploit ILP by executing multiple instructions from a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSS '99: Proceedings of the 12th international symposium on System synthesis

November 1999

133 pages

ISBN:076950356X

Copyright © Copyright (c) 1998 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 1999

Check for updates

Qualifiers

Article

Conference

ISSS99

Sponsor:

SIGDA

ISSS99: 12th International Symposium on System Synthesis

November 1 - 4, 1999

Acceptance Rates

Overall Acceptance Rate 38 of 71 submissions, 54%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
183
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)5

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Najaf-Abadi HImai M(2004)A procedure for obtaining a behavioral description for the control logic of a non-linear pipelineProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015112(86-91)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015112
Mishra PMamidipaka MDutt N(2004)Processor-memory coexploration using an architecture description languageACM Transactions on Embedded Computing Systems10.1145/972627.9726343:1(140-162)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1145/972627.972634
Wahlen OHohenauer MLeupers RMeyr H(2003)Instruction Scheduler Generation for Retargetable CompilationIEEE Design & Test10.1109/MDT.2003.117305120:1(34-41)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/MDT.2003.1173051
Grun PDutt NNicolau A(2002)Memory System Connectivity ExplorationProceedings of the conference on Design, automation and test in Europe10.5555/882452.874550Online publication date: 4-Mar-2002
https://dl.acm.org/doi/10.5555/882452.874550
Milner CDavidson J(2002)Quick pipingACM SIGPLAN Notices10.1145/566225.51385937:7(175-184)Online publication date: 19-Jun-2002
https://dl.acm.org/doi/10.1145/566225.513859
Milner CDavidson JMarwedel PDevadas S(2002)Quick pipingProceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems10.1145/513829.513859(175-184)Online publication date: 19-Jun-2002
https://dl.acm.org/doi/10.1145/513829.513859
Grun PDutt NNicolau A(2001)Access pattern based local memory customization for low power embedded systemsProceedings of the conference on Design, automation and test in Europe10.5555/367072.367973(778-784)Online publication date: 13-Mar-2001
https://dl.acm.org/doi/10.5555/367072.367973
Grun PDutt NNicolau ASentovich E(2000)MISTProceedings of the 2000 IEEE/ACM international conference on Computer-aided design10.5555/602902.602999(431-438)Online publication date: 5-Nov-2000
https://dl.acm.org/doi/10.5555/602902.602999
Halambi ACornea RGrun PDutt NNicolau ABolsens I(2000)Architecture exploration of parameterizable EPIC SOS architectures (poster paper)Proceedings of the conference on Design, automation and test in Europe10.1145/343647.344138Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1145/343647.344138
Catthoor FDutt NKozyrakis CBolsens I(2000)How to solve the current memory access and data transfer bottlenecksProceedings of the conference on Design, automation and test in Europe10.1145/343647.343813(426-435)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1145/343647.343813
Show More Cited By

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

Figures

Tables

Media

View Table of Conten