Article

Data-flow transformations using Taylor expansion diagrams

Authors:

D. Gomez-Prado,

E. BoutillonAuthors Info & Claims

DATE '07: Proceedings of the conference on Design, automation and test in Europe

Pages 455 - 460

Published: 16 April 2007 Publication History

Abstract

An original technique to transform functional representation of the design into a structural representation in form of a data flow graph (DFG) is described. A canonical, word-level data structure, Taylor Expansion Diagram (TED), is used as a vehicle to effect this transformation. The problem is formulated as that of applying a sequence of decomposition cuts to a TED that transforms it into a DFG optimized for a particular objective. A systematic approach to arrive at such a decomposition is described. Experimental results show that such constructed DFG provides a better starting point for architectural synthesis than those extracted directly from HDL specifications.

References

[1]

G. DeMicheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.

Digital Library

[2]

L. Guerra, M. Potkonjak, and J. Rabaey, "High level Synthesis for Reconfigurable Datapath Structures," Proc. Intl. Conf. on Computer-Aided Design, 1993.

Digital Library

[3]

V. Chaiyakul, D. Gajski, and R. Ramachandran, "High-level transformations for minimizing syntactic variances," Design Automation Conf., pp. 413--418, 1993.

Digital Library

[4]

A. Chandrakasan, M. Potkonjak, R. Mehra, Rabaey J., and Brodersen R., "Optimizing Power Using Transformations," IEEE Transactions on Computer Aided Design, pp. 12--31, 1995.

Digital Library

[5]

M. Potkonjak, S. Dey, and R. Roy, "Synthesis for testability using transformations," ASP-DAC'95, pp. 485--490, 1995.

Digital Library

[6]

M. Srivastava and M. Potkonjak, "Optimum and heuristic transformation techniques for simultaneous optimization of latency and throughtput," IEEE Transactions on VLSI Systems, 1995.

Digital Library

[7]

M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo, "SPIRAL: Code Generation for DSP Transforms," Proceedings of the IEEE, vol. 93, no. 2, 2005.

[8]

S. Gupta, N. Savoiu, N. D. Dutt, R. K. Gupta, and A. Nicolau, "Using Global Code Motion to Improve the Quality of Results in High Level Synthesis," IEEE Trans. on CAD, pp. 302--311, 2004.

Digital Library

[9]

J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, Maryland, 1983.

Digital Library

[10]

K. Wakabayashi, Cyber: High Level Synthesis System from Software into ASIC, pp. 127--151, Kluwer Academic Publishers, 1991.

[11]

S. Gupta, R. K. Gupta, N. D. Dutt, and A. Nicolau, SPARK: A Parallelizing Approach to the High-Level Synthesis of Digital Circuits, Kluwer Academic Publishers, 2004.

[12]

M. Ciesielski, P. Kalla, and S. Askar, "Taylor Expansion Diagrams: A Canonical Representation for Verification of Data Flow Designs," IEEE Trans. on Computers, vol. 55, no. 9, pp. 1188--1201, Sept. 2006.

Digital Library

[13]

J. Guillot, E. Boutillon, D. Gomez-Prado, S. Askar, Q. Ren, and M. Ciesielski, "Efficient Factorization of DSP Transforms using Taylor Expansion Diagrams," Design Automation and Test in Europe, DATE-06, 2006.

Digital Library

[14]

Université de Bretagne Sud LESTER, "GAUT, Architectural Synthesis Tool," http://lester.univ-ubs.fr:8080, 2004.

[15]

D. Gomez-Prado, Q. Ren, S. Askar, M. Ciesielski, and E. Boutillon, "Variable Ordering for Taylor Expansion Diagrams," IEEE Intl. High Level Design Validation and Test Workshop, HLDVT-04, 2004, pp. 55--59.

Digital Library

[16]

http://tango.ecs.umass.edu/TED/Doc/html

Cited By

Pérez JSánchez PFernández VDe Micheli GAl-Hashimi BMueller WMacii E(2010)Optimizing data-flow graphs with min/max, adding and relational operationsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871253(1361-1364)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871253
Yang ZMa GZhang S(2010)Formal verification of high-level data-flow synthesis designs using relational modeling and symbolic computationIntegration, the VLSI Journal10.1016/j.vlsi.2009.06.00343:1(101-112)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.vlsi.2009.06.003
Gomez-Prado DRen QCiesielski MGuillot JBoutillon EBenini LDe Micheli GAl-Hashimi BMueller W(2009)Optimizing data flow graphs to minimize hardware implementationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874649(117-122)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874649
Show More Cited By

Recommendations

High-Level Dataflow Transformations Using Taylor Expansion Diagrams

Editor's note:This article provides an overview of a canonical representation for arithmetic expressions and how it can be used to obtain various factorizations of such expressions to optimize them. The applicability of the approach is demonstrated in a ...
Taylor Expansion Diagrams: A Compact, Canonical Representation with Applications to Symbolic Verification
DATE '02: Proceedings of the conference on Design, automation and test in Europe

This paper presents a new, compact, canonicalgraph-based representation, called Taylor Expansion Diagrams(TEDs). It is based on a general non-binary decompositionprinciple using Taylor series expansion. It can be exploitedto facilitate the verification ...
High-level design verification using Taylor Expansion Diagrams: first results
HLDVT '02: Proceedings of the Seventh IEEE International High-Level Design Validation and Test Workshop

Recently a theory of a compact, canonical representation for arithmetic expressions, called Taylor Expansion Diagram (TED) has been proposed. This representation, based on a novel, non-binary decomposition principle, raises a level of design abstraction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '07: Proceedings of the conference on Design, automation and test in Europe

April 2007

1741 pages

ISBN:9783981080124

General Chair:
Rudy Lauwereins
IMEC and KULeuven, Belgium
,
Program Chair:
Jan Madsen
DTU, Denmark

Sponsors

The EDA Consortium
EDAA: European Design Automation Association
ECSI
SIGDA: ACM Special Interest Group on Design Automation
The IEEE Computer Society TTTC
IEEE Council on Electronic Design Automation (CEDA)
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

EDA Consortium

San Jose, CA, United States

Publication History

Published: 16 April 2007

Check for updates

Qualifiers

Article

Conference

DATE07

Sponsor:

EDAA
SIGDA
The Russian Academy of Sciences

DATE07: Design, Automation and Test in Europe

April 16 - 20, 2007

Nice, France

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
134
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pérez JSánchez PFernández VDe Micheli GAl-Hashimi BMueller WMacii E(2010)Optimizing data-flow graphs with min/max, adding and relational operationsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871253(1361-1364)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871253
Yang ZMa GZhang S(2010)Formal verification of high-level data-flow synthesis designs using relational modeling and symbolic computationIntegration, the VLSI Journal10.1016/j.vlsi.2009.06.00343:1(101-112)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.vlsi.2009.06.003
Gomez-Prado DRen QCiesielski MGuillot JBoutillon EBenini LDe Micheli GAl-Hashimi BMueller W(2009)Optimizing data flow graphs to minimize hardware implementationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874649(117-122)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874649
Ciesielski MGomez-Prado DRen QGuillot JBoutillon E(2009)Optimization of data-flow computations using canonical TED representationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.202470828:9(1321-1333)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2024708

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