Article

Area-efficient instruction set synthesis for reconfigurable system-on-chip designs

Authors:

Majid SarrafzadehAuthors Info & Claims

DAC '04: Proceedings of the 41st annual Design Automation Conference

Pages 395 - 400

https://doi.org/10.1145/996566.996679

Published: 07 June 2004 Publication History

Abstract

Silicon compilers are often used in conjunction with Field Programmable Gate Arrays (FPGAs) to deliver flexibility, fast prototyping, and accelerated time-to-market. Many of these compilers produce hardware that is larger than necessary, as they do not allow instructions to share hardware resources. This study presents an efficient heuristic which transforms a set of custom instructions into a single hardware datapath on which they can execute. Our approach is based on the classic problems of finding the longest common subsequence and substring of two (or more) sequences. This heuristic produces circuits which are as much as 85.33% smaller than those synthesized by integer linear programming (ILP) approaches which do not explore resource sharing. On average, we obtained 55.41% area reduction for pipelined datapaths, and 66.92% area reduction for VLIW datapaths. Our solution is simple and effective, and can easily be integrated into an existing silicon compiler.

References

[1]

Atasu, K., Pozzi, L., and Ienne, P. Automatic Application-Specific Instruction Set Extensions under Microarchitectural Constraints. Design Automation Conf. (DAC), 2003.

Digital Library

[2]

Brisk, P., Kaplan A., and Sarrafzadeh, M. Instruction Generation and Regularity Extraction for Reconfigurable Processors. Conf. Compilers, Architectures, and Synthesis for Embedded Systems (CASES), 2002.

Digital Library

[3]

Bunke, H., Guidobaldi, C., and Vento, M. Weighted Minimum Common Supergraph for Cluster Representation. In IEEE Int. Conf. Image Processing (ICIP), 2003.

Digital Library

[4]

Cadambi, S., and Goldstein, S. C. CPR: A Configuration Profiling Tool. Symp. Field-Programmable Custom Computing Machines (FCCM). 1999.

Digital Library

[5]

Cheung, N., Parameswaran, S., and Henkel, J. INSIDE: Instruction Selection/Identification & Design Exploration for Extensible Processors. Int. Conf. Computer-Aided Design (ICCAD), 2002.

Digital Library

[6]

Clark, N. Zhong, H. and Mahlke, S. Processor Acceleration Through Automated Instruction Set Customization. Int. Symp. Microarchitecture (MICRO), 2003.

Digital Library

[7]

Garey, M. R., and Johnson., D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company, 1979.

Digital Library

[8]

Goodwin, D., and Petkov, D. Automatic Generation of Application Specific Processors. Conf. Compilers, Architectures, and Synthesis for Embedded Systems (CASES), 2003.

Digital Library

[9]

Huang, Z., and Malik, S. Managing Dynamic Reconfiguration Overhead in Systems-on-a-Chip Design Using Reconfigurable Datapaths and Optimized Interconnection Networks. Conf. Design Automation and Test in Europe (DATE), 2001.

Digital Library

[10]

Janssen, M., Catthoor, F., and De Man, H. A Specification Invariant Technique for Regularity Improvement between Flow Graph Clusters. Euro. Design Automation & Test Conf. (ED&TC), 1996.

Digital Library

[11]

Kastner R., Kaplan, A., Memik, S., and Bozorgzadeh, E. Instruction Generation for Hybrid-Reconfigurable Systems. ACM Trans. Design Automation of Embedded Systems, 7, 4 (Oct. 2002). 605--627.

Digital Library

[12]

Lee, C., Potkonjak, M., Mangione-Smith, W. H. MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems. Int. Symp. Microarchitecture (MICRO), 1997.

Digital Library

[13]

Masek, W. J., and Paterson, M. S. A faster algorithm for computing string edit distances. Journal of Computer and System Sciences, 20, 1, (1980). 18--31.

[14]

Moreano, N., Arujo, G., Haung, Z., and Malik, S. Datapath Merging and Interconnection Sharing for Reconfigurable Architectures. In Int. Symp. System Synthesis (ISSS), 2002.

Digital Library

[15]

Pearson, D., and Vazirani, V. Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets. Journal of Algorithms, 14, 2 (Mar. 1993), 171--179.

Digital Library

[16]

Sun, F., Ravi, S., Raghunathan, A., and Jha, N. K. Synthesis of Custom Processors based on Extensible Platforms. Int. Conf. Computer-Aided Design (ICCAD), 2002.

Digital Library

[17]

Sun, F. Ravi, S. Raghunathan, A., and Jha, N. K. A Scalable Application-Specific Processor Synthesis Methodology. Int. Conf. Computer-Aided Design (ICCAD), 2003.

Digital Library

[18]

Ukkonen, E. Online Construction of Suffix Trees. Algorithmica 14, 3, (Sep. 1995). 249--260.

Digital Library

[19]

http://www.xilinx.com

[20]

http://www.synplicity.com

[21]

http://www.eecs.harvard.edu/hube/research/machsuif

Cited By

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
Brumar IZacharopoulos GYao YRama SBrooks DWei G(2023)Early DSE and Automatic Generation of Coarse-grained Merged AcceleratorsACM Transactions on Embedded Computing Systems10.1145/354607022:2(1-29)Online publication date: 24-Jan-2023
https://dl.acm.org/doi/10.1145/3546070
Pilato CSoldavini S(2022)Accelerator Design with High-Level SynthesisHandbook of Computer Architecture10.1007/978-981-15-6401-7_19-1(1-33)Online publication date: 27-Jan-2022
https://doi.org/10.1007/978-981-15-6401-7_19-1
Show More Cited By

Index Terms

Area-efficient instruction set synthesis for reconfigurable system-on-chip designs
1. Computer systems organization
  1. Architectures
    1. Other architectures

Recommendations

Resource Sharing of Pipelined Custom Hardware Extension for Energy-Efficient Application-Specific Instruction Set Processor Design

Application-Specific Instruction set Processor (ASIP) has become an increasingly popular platform for embedded systems because of its high performance, flexibility, and short turn-around time. The hardware extension in ASIPs can speed-up program ...
Reconfigurable Instruction Set Processors: A Survey
RSP '00: Proceedings of the 11th IEEE International Workshop on Rapid System Prototyping (RSP 2000)

Reconfigurable instruction set processors have the capability to adapt their instruction sets to the application being executed through a reconfiguration in their hardware. Through this adaptation, they are expected to achieve a great improvement in ...
Outer loop pipelining for application specific datapaths in FPGAs

Most hardware compilers apply loop pipelining to increase the parallelism achieved, but pipelining is restricted to the only innermost level in a nested loop. In this work we extend and adapt an existing outer loop pipelining approach known as single ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '04: Proceedings of the 41st annual Design Automation Conference

June 2004

1002 pages

ISBN:1581138288

DOI:10.1145/996566

General Chair:
Sharad Malik
Princeton University, Princeton, NJ
,
Program Chairs:
Limor Fix
Intel Semiconductors Ltd., Haifa, Israel
,
Andrew B. Kahng
University of California at San Diego, La Jolla, CA

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: 07 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC04

Sponsor:

DAC04: The 41st Annual Design Automation Conference 2004

June 7 - 11, 2004

CA, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
579
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Brumar IZacharopoulos GYao YRama SBrooks DWei G(2023)Early DSE and Automatic Generation of Coarse-grained Merged AcceleratorsACM Transactions on Embedded Computing Systems10.1145/354607022:2(1-29)Online publication date: 24-Jan-2023
https://dl.acm.org/doi/10.1145/3546070
Pilato CSoldavini S(2022)Accelerator Design with High-Level SynthesisHandbook of Computer Architecture10.1007/978-981-15-6401-7_19-1(1-33)Online publication date: 27-Jan-2022
https://doi.org/10.1007/978-981-15-6401-7_19-1
Wongjak A(2021)Text Compare and Grouping Program using Dynamic Programming Algorithm2021 Research, Invention, and Innovation Congress: Innovation Electricals and Electronics (RI2C)10.1109/RI2C51727.2021.9559779(303-306)Online publication date: 1-Sep-2021
https://doi.org/10.1109/RI2C51727.2021.9559779
Horn MRaidl G(2021)A$$^*$$-Based Compilation of Relaxed Decision Diagrams for the Longest Common Subsequence ProblemIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-030-78230-6_5(72-88)Online publication date: 17-Jun-2021
https://doi.org/10.1007/978-3-030-78230-6_5
Blum CDjukanovic MSantini AJiang HLi CManyà FRaidl G(2020)Solving Longest Common Subsequence Problems via a Transformation to the Maximum Clique ProblemComputers & Operations Research10.1016/j.cor.2020.105089(105089)Online publication date: Sep-2020
https://doi.org/10.1016/j.cor.2020.105089
Horn MDjukanovic MBlum CRaidl G(2020)On the Use of Decision Diagrams for Finding Repetition-Free Longest Common SubsequencesOptimization and Applications10.1007/978-3-030-62867-3_11(134-149)Online publication date: 4-Nov-2020
https://doi.org/10.1007/978-3-030-62867-3_11
Djukanovic MRaidl GBlum C(2020)A Beam Search for the Longest Common Subsequence Problem Guided by a Novel Approximate Expected Length CalculationMachine Learning, Optimization, and Data Science10.1007/978-3-030-37599-7_14(154-167)Online publication date: 3-Jan-2020
https://doi.org/10.1007/978-3-030-37599-7_14
Islam MSaifullah CAsha ZAhamed R(2019)Chemical reaction optimization for solving longest common subsequence problem for multiple stringSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3200-323:14(5485-5509)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00500-018-3200-3
Ng HLiu SLuk WAnderson JBazargan K(2018)ADAMProceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3174243.3174247(189-198)Online publication date: 15-Feb-2018
https://dl.acm.org/doi/10.1145/3174243.3174247
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