Article

Scalable custom instructions identification for instruction-set extensible processors

Authors:

Tulika MitraAuthors Info & Claims

CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems

Pages 69 - 78

https://doi.org/10.1145/1023833.1023844

Published: 22 September 2004 Publication History

Abstract

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. However, it is computationally expensive to automatically select the optimal set of custom instructions. Therefore, heuristic techniques are often employed to quickly search the design space. In this paper, we present an efficient algorithm for exact enumeration of all possible candidate instructions given the dataflow graph (DFG) corresponding to a code fragment. Even though this is similar to the "subgraph enumeration" problem (which is exponential), we find that most subgraphs are not feasible candidates for various reasons. In fact, the number of candidates is quite small compared to the size of the DFG. Compared to previous approaches, our technique achieves orders of magnitude speedup in enumerating these candidate custom instructions for very large DFGs.

References

[1]

A. Aho, J. Hopcroft, and J.D.Ullman. Data structures and Algorithms. Addison-Wesley, 1987.

Digital Library

[2]

Altera. Nios embedded processor system development. http://www.altera.com/products/ip/processors/nios/nio-index.html.

[3]

M. Arnold and H. Corporaal. Designing domain-specific processors. In CODES, 2001.

Digital Library

[4]

K. Atasu, L. Pozzi, and P. Ienne. Automatic application-specific instruction-set extensions under microarchitectural constraints. In DAC, 2003.

Digital Library

[5]

D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65, 1996.

Digital Library

[6]

M. Baleani et al. Hw/Sw partitioning and code generation of embedded control applications on a reconfigurable architecture platform. In CODES, May 2002.

Digital Library

[7]

P. Brisk, A. Kaplan, R. Kastner, and M. Sarrafzadeh. Instruction generation and regularity extraction for reconfigurable processors. In CASES, October 2002.

Digital Library

[8]

D. Burger, T. Austin, and S. Bennett. Evaluating Future Microprocessors: The SimpleScalar Toolset. Technical Report CS-TR96-1308, Univ. of Wisconsin - Madison, 1996. Available from http://www.simplescalar.com.

[9]

N. Clark, H. Zhong, and S. Mahlke. Processor acceleration through automated instruction set customization. In MICRO36, 2003.

Digital Library

[10]

J. Cong, Y. Fan, G. Han, and Z. Zhang. Application-specific instruction generation for configurable processor architectures. In FPGA, 2004.

Digital Library

[11]

P. Faraboschi et al. Lx: a technology platform for customizable VLIW embedded processing. In ISCA, 2000.

Digital Library

[12]

R. E. Gonzalez. Xtensa: A configurable and extensible processor. IEEE Micro, 20(2), 2000.

Digital Library

[13]

M. R. Guthausch et al. Mibench: A free, commercially representative embedded benchmark suite. In IEEE 4th Annual Workshop on Workload Characterization, 2001. Benchmark available from http://www.eecs.umich.edu/mibench/.

Digital Library

[14]

J. Lee, K. Choi, and N. Dutt. Efficient instruction encoding for automatic instruction set design of configurable ASIPs. In ICCAD, 2002.

Digital Library

[15]

S. Talla. Adaptive Explicitly Parallel Instruction Computing. PhD thesis, New York University, 2000.

Digital Library

[16]

L. Pozzi, M. Vuletic, and P. Ienne. Automatic topology-based identification of instruction-set extensions for embedded processor. Technical Report 01/377, NSwiss Federal Institute of Technology Lausanne (EPFL), 2001.

[17]

P. Yu and T. Mitra. Characterizing embedded applications for instruction-set extensible processors. In Proceedings of DAC, 2004.

Digital Library

[18]

Z. A. Ye. et al. Chimaera: A high-performance architecture with a tightly-coupled reconfigurable functional unit. In ISCA, 2000.

Digital Library

Cited By

Liyanage KGamaarachchi HSaadat HLi TSamarakoon HParameswaran S(2024)Accelerating Chaining in Genomic Analysis Using RISC- V Custom Instructions2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546650(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546650
Hussein EWaschneck BMayr C(2024)Automating application-driven customization of ASIPs: A surveyJournal of Systems Architecture10.1016/j.sysarc.2024.103080148(103080)Online publication date: Mar-2024
https://doi.org/10.1016/j.sysarc.2024.103080
Todman TLuk W(2022)Custom Instructions for Networked Processor TemplatesIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2022.317838969:7(3096-3100)Online publication date: Jul-2022
https://doi.org/10.1109/TCSII.2022.3178389
Show More Cited By

Index Terms

Scalable custom instructions identification for instruction-set extensible processors
1. Computer systems organization
  1. Architectures
    1. Other architectures

Recommendations

Automatic custom instruction identification for application-specific instruction set processors

The application-specific instruction set processors (ASIPs) have received more and more attention in recent years. ASIPs make trade-offs between flexibility and performance by extending the base instruction set of a general-purpose processor with custom ...
Code transformation strategies for extensible embedded processors
CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

Embedded application requirements, including high performance, low power consumption and fast time to market, are uncommon in the broader domain of general purpose applications. In order to satisfy these demands, chip manufacturers often provide ...
Exploring custom instruction synthesis for application-specific instruction set processors with multiple design objectives
ISLPED '10: Proceedings of the 16th ACM/IEEE international symposium on Low power electronics and design

Application-specific instruction set processor (ASIP) has become a promising platform for embedded system design in the past decade. Traditional custom instruction synthesis flows for ASIPs mainly target performance improvement. Other design metrics are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems

September 2004

324 pages

ISBN:1581138903

DOI:10.1145/1023833

General Chairs:
Mary Jane Irwin
Pennsylvania State University
,
Wei Zhao
Texas Instruments
,
Program Chairs:
Luciano Lavagno
Politecnico di Torino/Cadence Labs
,
Scott Mahlke
University of Michigan, Ann Arbor, MI

Copyright © 2004 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CASES04

Sponsor:

CASES04: 2004 International Conference on Compilers, Architectures and Synthesis for Embedded Systems

September 22 - 25, 2004

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

145
Total Citations
View Citations
917
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liyanage KGamaarachchi HSaadat HLi TSamarakoon HParameswaran S(2024)Accelerating Chaining in Genomic Analysis Using RISC- V Custom Instructions2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546650(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546650
Hussein EWaschneck BMayr C(2024)Automating application-driven customization of ASIPs: A surveyJournal of Systems Architecture10.1016/j.sysarc.2024.103080148(103080)Online publication date: Mar-2024
https://doi.org/10.1016/j.sysarc.2024.103080
Todman TLuk W(2022)Custom Instructions for Networked Processor TemplatesIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2022.317838969:7(3096-3100)Online publication date: Jul-2022
https://doi.org/10.1109/TCSII.2022.3178389
Singh SSarangi S(2021)ISAMod: A Tool for Designing ASIPs by Comparing Different ISAs2021 34th International Conference on VLSI Design and 2021 20th International Conference on Embedded Systems (VLSID)10.1109/VLSID51830.2021.00005(1-6)Online publication date: Feb-2021
https://doi.org/10.1109/VLSID51830.2021.00005
Xiao CWang SLiu WWang XCasseau E(2021)An Optimal Algorithm for Enumerating Connected Convex Subgraphs in Acyclic DigraphsIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2020.300029768:1(261-265)Online publication date: Jan-2021
https://doi.org/10.1109/TCSII.2020.3000297
Todman TLuk W(2021)Custom enhancements to networked processor templates2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI51109.2021.00049(224-229)Online publication date: Jul-2021
https://doi.org/10.1109/ISVLSI51109.2021.00049
Gnanasambandapillai VPeddersen JRagel RParameswaran S(2020)FINDER: Find Efficient Parallel Instructions for ASIPs to Improve Performance of Large ApplicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.3012211(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.3012211
Venkataramani VBodin BKulkarni AMitra TPeh L(2020)Time-Predictable Software-Defined Architecture with Sdf-Based Compiler Flow for 5g Baseband ProcessingICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP40776.2020.9054285(1553-1557)Online publication date: May-2020
https://doi.org/10.1109/ICASSP40776.2020.9054285
Zacharopoulos GFerretti LGiaquinta EAnsaloni GPozzi L(2019)RegionSeeker: Automatically Identifying and Selecting Accelerators From Application Source CodeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.281868938:4(741-754)Online publication date: Apr-2019
https://doi.org/10.1109/TCAD.2018.2818689
Venkanna MRao R(2018)Static Worst-Case Execution Time Optimization using DPSO for ASIP ArchitectureIngeniería Solidaria10.16925/.v14i0.223014:25(1-11)Online publication date: 1-May-2018
https://doi.org/10.16925/.v14i0.2230
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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents