Article

Operation tables for scheduling in the presence of incomplete bypassing

Authors:

Aviral Shrivastava,

Eugene Earlie,

Nikil Dutt,

Alex NicolauAuthors Info & Claims

CODES+ISSS '04: Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

Pages 194 - 199

https://doi.org/10.1145/1016720.1016768

Published: 08 September 2004 Publication History

Get Access

Abstract

Register bypassing is a powerful and widely used feature in modern processors to eliminate certain data hazards. Although complete bypassing is ideal for performance, bypassing has significant impact on cycle time, area, and power consumption of the processor. Due to the strict constraints on performance, cost and power consumption in embedded processors, architects need to evaluate and implement incomplete register bypassing mechanisms. However traditional data hazard detection and/or avoidance techniques used in retargetable schedulers break down in the presence of incomplete bypassing. In this paper, we present the concept of Operation Tables, which can be used to detect data hazards, even in the presence of incomplete bypassing. Furthermore our technique integrates the detection of both data, as well as resource hazards, and can be easily employed in a compiler to generate better schedules. Our experimental results on the popular Intel XScale embedded processor platform show that even with a simple intra-basic block scheduling technique, we achieve upto 20% performance improvement over fully optimized GCC generated code on embedded applications from the MiBench suite.

References

[1]

Intel xscale microarchitecture programmers reference manual.

Google Scholar

[2]

A. Abnous and N. Bagerzadeh. Pipelining and bypassing in a vliw processor. In IEEE trans. on Parallel and Distributed Systems, 1995.

Digital Library

Google Scholar

[3]

P. Ahuja, D. W. Clark, and A. Rogers. The performance impact of incomplete bypassing in processor pipelines. In Proc. of Symposium on Microarchitecture MICRO-28, 1995.

Digital Library

Google Scholar

[4]

E. Bloch. The engineering design of the stretch computer. In Proc. of Eastern Joint Computer Conference, pages 48--59, 1959.

Digital Library

Google Scholar

[5]

M. Buss, R. Azavedo, P. Centoducatte, and G. Araujo. Tailoring pipeline bypassing and functional unit mapping for application in clustered vliw architectures. In Proc. of CASES, 2001.

Digital Library

Google Scholar

[6]

E. S. Davidson. The design and control of pipelined function generators. Int. IEEE Conf. on Systems Networks and Computers, pages 19--21, 1971.

Google Scholar

[7]

K. Fan, N. Clark, M. Chu, K. V. Manjunath, R. Ravindran, M. Smelyanskiy, and S. Mahlke. Systematic register bypass customization for application-specific processors. In Proc. of IEEE Intl. Conf. on ASSAP, 2003.

Crossref

Google Scholar

[8]

M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. Mibench: A free, commercially representative embedded benchmark suite. In IEEE Workshop in workload characterization, 2001.

Digital Library

Google Scholar

[9]

A. Halambi, P. Grun, V. Ganesh, A. Khare, N. Dutt, and A. Nicolau. EXPRESSION: A language for architecture exploration through compiler/simulator retargetability. In Proceedings of Design Automation and Test in Europe, 1999.

Digital Library

Google Scholar

[10]

A. Halambi, A. Shrivastava, N. Dutt, and A. Nicolau. A customizable compiler framework for embedded systems. In SCOPES, 2001.

Google Scholar

[11]

P. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. 1990.

Digital Library

Google Scholar

[12]

P. G. Lowney, S. M. Freudenberger, T. J. Karzes, W. D. Lichtenstein, R. P. Nix, J. S. O'Donnell, and J. C. Ruttenberg. The Multiflow Trace Scheduling compiler. The Journal of Supercomputing", 7(1-2):51--142, 1993.

Digital Library

Google Scholar

[13]

S. Muchnick. Advanced Compiler Design and Implementation. 1998.

Digital Library

Google Scholar

[14]

The Trimaran Consortium. The Trimaran Compiler Infrastructure for Instruction Level Parallelism.

Google Scholar

Cited By

View all

Khavari Tavana MAhmadian Khameneh SGoudarzi M(2015)Dynamically adaptive register file architecture for energy reduction in embedded processorsMicroprocessors & Microsystems10.1016/j.micpro.2015.01.00539:2(49-63)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.01.005
Lara JGuerra ECuadrado J(2014)When and How to Use Multilevel ModellingACM Transactions on Software Engineering and Methodology10.1145/268561524:2(1-46)Online publication date: 23-Dec-2014
https://dl.acm.org/doi/10.1145/2685615
Hao DZhang LZhang LRothermel GMei H(2014)A Unified Test Case Prioritization ApproachACM Transactions on Software Engineering and Methodology10.1145/268561424:2(1-31)Online publication date: 23-Dec-2014
https://dl.acm.org/doi/10.1145/2685614
Show More Cited By

Index Terms

Operation tables for scheduling in the presence of incomplete bypassing
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers
      2. Source code generation

Recommendations

Operation Tables for Scheduling in the Presence of Incomplete Bypassing
CODES+ISSS '04: Proceedings of the international conference on Hardware/Software Codesign and System Synthesis: 2004

Register bypassing is a powerful and widely used feature in modern processors to eliminate certain data hazards. Although complete bypassing is ideal for performance, bypassing has significant impact on cycle time, area, and power consumption of the ...
Bypass aware instruction scheduling for register file power reduction
Proceedings of the 2006 LCTES Conference

Since register files suffer from some of the highest power densities within processors, designers have investigated several architectural strategies for register file power reduction, including "On Demand RF Read" where the register file is read only if ...
Machine-Description Driven Compilers for EPIC and VLIW Processors

In the past, due to the restricted gate count available on an inexpensive chip, embedded DSPs have had limited parallelism, few registers and irregular, incomplete interconnectivity. More recently, with increasing levels of integration, embedded VLIW ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CODES+ISSS '04: Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

September 2004

266 pages

ISBN:158113 9373

DOI:10.1145/1016720

General Chairs:
Alex Orailoglu
University of California, San Diego, CA
,
Pai H. Chou
University of California, Irvine, CA
,
Program Chairs:
Petru Eles
Linköping University, Sweden
,
Axel Jantsch
Royal Institute of Technology, Sweden

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CODES/ISSS04

Sponsor:

CODES/ISSS04: Second IEEE/ACM/IFIP International CODES/ ISSS 2004 Merged Conference

September 8 - 10, 2004

Stockholm, Sweden

Acceptance Rates

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
278
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Khavari Tavana MAhmadian Khameneh SGoudarzi M(2015)Dynamically adaptive register file architecture for energy reduction in embedded processorsMicroprocessors & Microsystems10.1016/j.micpro.2015.01.00539:2(49-63)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.01.005
Lara JGuerra ECuadrado J(2014)When and How to Use Multilevel ModellingACM Transactions on Software Engineering and Methodology10.1145/268561524:2(1-46)Online publication date: 23-Dec-2014
https://dl.acm.org/doi/10.1145/2685615
Hao DZhang LZhang LRothermel GMei H(2014)A Unified Test Case Prioritization ApproachACM Transactions on Software Engineering and Methodology10.1145/268561424:2(1-31)Online publication date: 23-Dec-2014
https://dl.acm.org/doi/10.1145/2685614
Xu PTirthapura S(2014)Optimality of Clustering Properties of Space-Filling CurvesACM Transactions on Database Systems10.1145/255668639:2(1-27)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1145/2556686
Thomson ADiamond TWeng SRen KShao PAbadi D(2014)Fast Distributed Transactions and Strongly Consistent Replication for OLTP Database SystemsACM Transactions on Database Systems10.1145/255668539:2(1-39)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1145/2556685
Lee JShrivastava A(2011)Static Analysis of Register File VulnerabilityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.209563030:4(607-616)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TCAD.2010.2095630
Guan XFei Y(2010)Register file partitioning and recompilation for register file power reductionACM Transactions on Design Automation of Electronic Systems10.1145/1754405.175440915:3(1-30)Online publication date: 10-Jun-2010
https://dl.acm.org/doi/10.1145/1754405.1754409
Jeyapaul RShrivastava A(2010)Code Transformations for TLB Power ReductionInternational Journal of Parallel Programming10.1007/s10766-009-0123-838:3-4(254-276)Online publication date: 21-Jan-2010
https://doi.org/10.1007/s10766-009-0123-8
Lee JShrivastava ABenini LDe Micheli GAl-Hashimi BMueller W(2009)Static analysis to mitigate soft errors in register filesProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874949(1367-1372)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874949
Gracioli GFischmeister S(2009)Tracing interrupts in embedded softwareACM SIGPLAN Notices10.1145/1543136.154247144:7(137-146)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1543136.1542471
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations