Article

Algorithmic transformation techniques for efficient exploration of alternative application instances

Authors:

Todor Stefanov,

Bart Kienhuis,

Ed DeprettereAuthors Info & Claims

CODES '02: Proceedings of the tenth international symposium on Hardware/software codesign

Pages 7 - 12

https://doi.org/10.1145/774789.774792

Published: 06 May 2002 Publication History

Get Access

Abstract

Following the Y-chart paradigm for designing a system, an application and an architecture are modeled separately and mapped onto each other in an explicit design step. Next, a performance analysis for alternative application instances, architecture instances and mappings has to be done, thereby exploring the design space of the target system. Deriving alternative application instances is not trivially done. Nevertheless, many instances of a single application exist that are worth to be derived for exploration. In this paper, we present algorithmic transformation techniques for systematic and fast generation of alternative application instances that express task-level concurrency hidden in an application in some degree of explicitness. These techniques help a system designer to speedup significantly the design space exploration process.

References

[1]

C. Ancourt and F. Irigoin. Scanning polyhedra with DO loops. In Proc. ACM SIGPLAN'91, pages 39--50, June 1991.

Digital Library

Google Scholar

[2]

P. Held. Functional Design of Data-Flow Networks, 1996. PhD thesis, Delft University of Technology, The Netherlands.

Google Scholar

[3]

G. Kahn. The semantics of a simple language for parallel programming. In Proc. of the IFIP Congress 74. North-Holland Publishing Co., 1974.

Google Scholar

[4]

B. Kienhuis. Design Space Exploration of Stream-based Dataflow Architectures: Methods and Tools, Jan. 1999, PhD thesis, Delft University of Technology, The Netherlands.

Google Scholar

[5]

B. Kienhuis. MatParser: An array dataflow analysis compiler. Technical report, University of California at Berkeley, 2000. UCB/ERL M00/9.

Google Scholar

[6]

B. Kienhuis, E. Deprettere, K. Vissers, and P. van der Wol. The Construction of a Retargetable Simulator for an Architecture Template. In Proc. 6-th Int. Workshop on Hardware/Software Codesign (CODES'98), Seattle, Washington, Mar. 15--18 I998.

Digital Library

Google Scholar

[7]

B. Kienhuis, E. Rijpkema, and E. F. Deprettere. Compaan: Deriving Process Networks from Matlab for Embedded Signal Processing Architectures. In Proc. 8th International Workshop on Hardware/Software Codesign (CODES'2000). San Diego, CA, USA, May 3--5 2000.

Digital Library

Google Scholar

[8]

P. Lieverse, T. Stefanov. P. van der Wolf, and E. Deprettere. System Level Design with SPADE: an M-JPEG Case Study. In Proc. Int. Conference on Computer Aided Design (ICCAD'01), pages 31--38, San Jose CA, USA, Nov. 4--8 2001.

Digital Library

Google Scholar

[9]

P. Lieverse. P. van der Wolf, K. Vissers, and E. Deprettere. A Methodology for Architecture Exploration of Heterogeneous Signal Processing Systems. Int. Journal of VLSI Signal Processing for Signal, Image and Video Technology, 29(3): 197--207, 2001.

Digital Library

Google Scholar

[10]

S. Muchnick. Advanced Compiler Design and lmplementation. Morgan Kaufmann Publishers. Inc., 1997.

Digital Library

Google Scholar

[11]

K. Parhi. VLSI Digital Signal Processing Systems: Design and Implementation. John Wiley & Sons. Inc., 1999.

Google Scholar

[12]

J. Proakis, C. Rader, F. Ling, C. Nikias, M. Moonen, and I. Proudler. Algorithms for Statistical Signal Processing, Prentice Hall, Inc., 2002.

Digital Library

Google Scholar

[13]

J. Teich and L. Thiele. Exact Partitioning of Affine Dependence Algorithms. Lecture Notes in Computer Science (LNCS), Springer, 2268:133--151, 2002.

Digital Library

Google Scholar

Cited By

View all

Theelen BDeprettere EBhattacharyya S(2018)Dynamic Dataflow GraphsHandbook of Signal Processing Systems10.1007/978-3-319-91734-4_32(1173-1210)Online publication date: 14-Oct-2018
https://doi.org/10.1007/978-3-319-91734-4_32
van Teijlingen Wvan Leuken RGaluzzi CKienhuis B(2016)Determining Performance Boundaries on High-Level System SpecificationsProceedings of the 19th International Workshop on Software and Compilers for Embedded Systems10.1145/2906363.2906386(90-97)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2906363.2906386
Meloni PTuveri GRaffo LLoi IConti FDaneshtalab MPalesi MAngiolini FPlosila JEbrahimi M(2014)A Stream Buffer Mechanism for Pervasive Splitting Transformations on Polyhedral Process NetworksProceedings of International Workshop on Manycore Embedded Systems10.1145/2613908.2613913(25-32)Online publication date: 15-Jun-2014
https://dl.acm.org/doi/10.1145/2613908.2613913
Show More Cited By

Index Terms

Algorithmic transformation techniques for efficient exploration of alternative application instances
1. Hardware
  1. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors
2. Mathematics of computing
  1. Mathematical software

Recommendations

A constructive approach for design space exploration
EICS '13: Proceedings of the 5th ACM SIGCHI symposium on Engineering interactive computing systems

The co-evolution of different kinds of external representations is essential in Human-Centered Design. It helps design teams to interleave different design activities and to view a design problem from different perspectives. The paper investigates a ...
Divergent exploration in design with a dynamic multiobjective optimization formulation

Formulation space exploration is a new strategy for multiobjective optimization that facilitates both divergent exploration and convergent optimization during the early stages of design. The formulation space is the union of all variable and design ...
Exploiting the model-driven engineering approach to improve design space exploration of embedded systems
SBCCI '09: Proceedings of the 22nd Annual Symposium on Integrated Circuits and System Design: Chip on the Dunes

This paper proposes a design space abstraction, in order to decouple the exploration algorithm from the design space, which allows the application of the design space exploration (DSE) tool in different design scenarios and is appropriate for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CODES '02: Proceedings of the tenth international symposium on Hardware/software codesign

May 2002

232 pages

ISBN:1581135424

DOI:10.1145/774789

General Chairs:
Joerg Henkel
C & C Research Labs, NEC
,
Xiaobo Sharon Hu
University of Notre Dame
,
Program Chairs:
Rajesh Gupta
University of California, Irvine
,
Sri Parameswaran
University of New South Wales, Australia

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: 06 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CODES02

Sponsor:

IFIP WG 10.5
SIGDA
SIGSOFT
IEEE-CS\DATC

CODES02: 10th International Symposium on Hardware/Software Codesign

May 6 - 8, 2002

Colorado, Estes Park

Acceptance Rates

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
328
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Theelen BDeprettere EBhattacharyya S(2018)Dynamic Dataflow GraphsHandbook of Signal Processing Systems10.1007/978-3-319-91734-4_32(1173-1210)Online publication date: 14-Oct-2018
https://doi.org/10.1007/978-3-319-91734-4_32
van Teijlingen Wvan Leuken RGaluzzi CKienhuis B(2016)Determining Performance Boundaries on High-Level System SpecificationsProceedings of the 19th International Workshop on Software and Compilers for Embedded Systems10.1145/2906363.2906386(90-97)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2906363.2906386
Meloni PTuveri GRaffo LLoi IConti FDaneshtalab MPalesi MAngiolini FPlosila JEbrahimi M(2014)A Stream Buffer Mechanism for Pervasive Splitting Transformations on Polyhedral Process NetworksProceedings of International Workshop on Manycore Embedded Systems10.1145/2613908.2613913(25-32)Online publication date: 15-Jun-2014
https://dl.acm.org/doi/10.1145/2613908.2613913
(2014)Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizingProceedings of the Twelfth ACM/IEEE Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2014.6961839(12-21)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1109/MEMCOD.2014.6961839
Du JWang YZhuge QHu JSha E(2013)Efficient Loop Scheduling for Chip Multiprocessors with Non-Volatile Main MemoryJournal of Signal Processing Systems10.1007/s11265-012-0703-571:3(261-273)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s11265-012-0703-5
McAllister J(2013)FPGA-Based DSPHandbook of Signal Processing Systems10.1007/978-1-4614-6859-2_22(707-739)Online publication date: 10-May-2013
https://doi.org/10.1007/978-1-4614-6859-2_22
Keinert JTeich JKeinert JTeich J(2011)Fundamentals and Related WorkDesign of Image Processing Embedded Systems Using Multidimensional Data Flow10.1007/978-1-4419-7182-1_3(23-80)Online publication date: 2011
https://doi.org/10.1007/978-1-4419-7182-1_3
Meijer SNikolov HStefanov TDe Micheli GAl-Hashimi BMueller WMacii E(2010)Throughput modeling to evaluate process merging transformations in polyhedral process networksProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871106(747-752)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871106
Banerjee SBozorgzadeh ENoguera JDutt N(2010)Bandwidth Management in Application Mapping for Dynamically Reconfigurable ArchitecturesACM Transactions on Reconfigurable Technology and Systems10.1145/1839480.18394883:3(1-30)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1839480.1839488
McAllister J(2010)FPGA-based DSPHandbook of Signal Processing Systems10.1007/978-1-4419-6345-1_14(363-392)Online publication date: 16-Jul-2010
https://doi.org/10.1007/978-1-4419-6345-1_14
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.

Cited By

Index Terms

Recommendations

A constructive approach for design space exploration

Divergent exploration in design with a dynamic multiobjective optimization formulation

Exploiting the model-driven engineering approach to improve design space exploration of embedded systems