Article

Free access

A Specification Invariant Technique for Regularity Improvement between Flow-Graph Clusters

Authors:

Martin Janssen,

Francky Catthoor,

Hugo de ManAuthors Info & Claims

EDTC '96: Proceedings of the 1996 European conference on Design and Test

Page 138

Published: 11 March 1996 Publication History

Abstract

In system-level synthesis for DSP applications, algorithmic transformations on the initially specified flow-graph are crucial to arrive at a good specification as input for either high-level hardware synthesis, or for code generation. For both target styles, sharing of clusters (partitions) of the flow-graph on the same resource is essential to optimize within the combined search space of area, time, and power. To decrease sharing overhead, it is important for clusters that share the same resource to match each other as good as possible, which is the aim of regularity improvement. In this paper, we present a new technique that improves the regularity between two or more flow-graph clusters by means of algebraic transformations, operating at the word-level. The technique consists of a steepest descent optimization step, preceded by a normalization step. Both steps use optimizing algebraic transformations that feature a limited look-ahead. Regularity improvement is modeled as an area minimization problem. The technique is invariant to structural changes in the specification of the clusters, as long as their functionality is not affected. Our main target domain consists of lowly-multiplexed realizations of real-time DSP applications. The power of our approach is substantiated on several real-life applications from the video and image processing domain. The regularity improvement technique is able to generate optimal (or close to optimal) results, independent of cluster duplications or (behavior-preserving) cluster structure modifications, with only a few composite transformations. Large savings are possible compared to non optimized flow-graph clusters with an acceptable but relatively large run time complexity.

References

[1]

[1] N. Ahmed, et al., "Discrete cosine transform," IEEE Transactions on Computers, pp. 90-93, 1974.

Digital Library

[2]

[2] A. V. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986.

Digital Library

[3]

[3] R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang, "MIS: A Multiple-Level Logic Optimization System," IEEE Transactions on Computer-Aided Design, Vol. 6, No. 6, pp. 1062-1081. 1987.

Digital Library

[4]

[4] A. Chandrakasan, M. Potkonjak, J. Rabaey, and R. Brodersen, "An Approach For Power Minimization Using Transformations," Proceedings IEEE VLSI Signal Processing Workshop, pp. 41-50, 1992.

[5]

[5] G. P. Fettweis and L. Thiele, "Algebraic Recurrence Transformations for Massive Parallelism," Proceedings IEEE VLSI Signal Processing Workshop, pp. 332-341, 1992.

[6]

[6] W. Geurts, F. Catthoor, H. De Man, "Time constrained allocation and assignment techniques for high throughput signal processing," Proc. 29th IEEE Design Automation Conference, pp. 124-127, June 1992.

Digital Library

[7]

[7] W. Geurts, F. Franssen, M. van Swaaij, F. Catthoor, H. De Man, and M. Moonen, "Memory and data-path mapping for image and video applications," Application-driven architecture synthesis, F. Catthoor, L. Svensson (eds.), Kluwer, pp. 143-166, 1993.

[8]

[8] R. I. Hartley and A. Casavant, "Optimizing pipelined networks of associative and commutative operators," IEEE Transactions on Computer-Aided Design, Vol. 13, No. 11, pp. 1418-1425, Nov. 1994.

Digital Library

[9]

[9] S-H. Huang and J. Rabaey, "Maximizing the throughput of high-performance DSP applications using behavioral transformations," Proc. 5th European Design and Test Conf., pp. 25-30, Feb. 1994.

[10]

[10] J. M. J. Janssen, F. Catthoor, H. De Man, "A Specification Invariant Technique for Operation Cost Minimisation in Flow-graphs," Proc. 7th IEEE Int. Symp. on High-Level Synthesis, pp. 146-151, 1994.

Digital Library

[11]

[11] E. Katsadas, Z. Sahraoui, M. Wouters, V. Derudder, L. Bolsens, P. Six, and H. De Man, "Regular Module Generation or Standard Cells: Two Alternative Implementations for a Library of Functional Building Blocks," Selection of papers IFIP WG10.2/WG10.5 Workshop , Apr. and Sep. 1992.

Digital Library

[12]

[12] C. Liem, T. May, and P. Paulin, "Instruction-set matchine and selection for DSP and ASIP code generation," Proceedings 5th European Design and Test Conference, pp. 31-37, Feb. 1994.

[13]

[13] D. B. Loveman, "Program Improvement by Source-to-Source Transformation," J. of the ACM, Vol. 24, No. 1, pp. 121-145, Jan. 1977.

Digital Library

[14]

[14] P. Marwedel, "A new synthesis algorithm for the MIMOLA software system," Proceedings 23rd IEEE Design Automation Conference, pp. 271-277, June 1986.

Digital Library

[15]

[15] M. C. McFarland, A. C. Parker, and R. Camposano, "The high-level synthesis of digital systems," Proceedings of the IEEE, Vol. 78, No. 2, pp. 301-318, Feb. 1990.

[16]

[16] A. Nicolau and R. Potasman, "Incremental Tree Height Reduction For High Level Synthesis," Proceedings 28th IEEE Design Automation Conference, pp. 770-774, 1991.

Digital Library

[17]

[17] D. A. Padua and M. J. Wolfe, "Advanced Compiler Optimizations for Supercomputers," Communications of the ACM, Vol. 29, No. 12, pp. 1184-1201, Dec. 1986.

Digital Library

[18]

[18] C. Polychronopoulos, "Compiler optimizations for enhancing parallelism and their impact on the architecture design," IEEE Transactions on Computers, Vol. 37, No. 8, pp. 991-1004, Aug. 1988.

Digital Library

[19]

[19] M. Potkonjak and J. Rabaey, "Optimizing Resource Utilization using Transformations," Proceedings IEEE International Conference on Computer-Aided Design, pp. 88-91, Nov. 1991.

[20]

[20] M. Potkonjak, M. Srivastava, and J. Rabaey, "Efficient substitution of multiple constant multiplications by shifts and additions using iterative pairwise matching," Proceedings 31st IEEE Design Automation Conference, pp. 189-194, June 1994.

Digital Library

[21]

[21] D. S. Rao and F. Kurdahi, "Hierarchical design space exploration for a class of digital systems," IEEE Transactions on VLSI Systems, Vol. 1, No. 3, pp. 282-295, Sep. 1993.

Digital Library

[22]

[22] E. Rundensteiner, D. Gajski, and L. Bit, "Component synthesis from functional descriptions," IEEE Transactions on Computer-Aided Design , Vol. 12, No. 9, pp. 1287-1298, Sep. 1993.

Digital Library

[23]

[23] H. Samsom, L. Claesen, and H. De Man, "Syn Guide: An environment for doing interactive Correctness Preserving Transformations," Proc. IEEE VLSI Signal Processing Workshop, pp. 269-277, 1993.

[24]

[24] L. Stok, "False loops through resource sharing," Proc. IEEE Intn'l Conference on Computer-Aided Design, pp. 345-348, Nov. 1992.

Digital Library

[25]

[25] H. Trickey, "Flamel: A high-Level Hardware Compiler," IEEE Trans. on Computer-Aided Design, Vol. 6, No. 2, pp. 259-269, 1987.

Digital Library

[26]

[26] J. Van Praet, G. Goossens, D. Lanneer, and H. De Man, "Instruction set definition and instruction selection for ASIPs," Proceedings 7th IEEE International Symposium on High-Level Synthesis, May 1994.

Digital Library

[27]

[27] R. A. Walker and D. E. Thomas, "Behavioral Transformations for Algorithmic Level IC Design," IEEE Transactions on Computer-Aided Design, Vol. 8, No. 10, pp. 1115-1127, 1989.

[28]

[28] A. van der Werf, E. Aerts, M. Peek, J. van Meerbergen, P. Lippens, and W. Verhaeph, "Area Optimization of Multi-function Processing Units," Proceedings IEEE International Conference on Computer-Aided Design, pp. 292-299, Nov. 1992.

Digital Library

[29]

[29] D. Whitfield and M. L. Soffa, "An Approach to Ordering Optimizing Transformations," 2nd ACM Symposium on Principles and Practice of Parallel Programming, pp. 137-147, March 1990.

Digital Library

[30]

[30] M. Wolfe, "The tiny loop restructuring research tool," Proc. International Conference on Parallel Processing, pp. II-46-II-53, 1991.

Cited By

Galuzzi CBertels K(2011)The Instruction-Set Extension ProblemACM Transactions on Reconfigurable Technology and Systems10.1145/1968502.19685094:2(1-28)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1145/1968502.1968509
Brisk PKaplan ASarrafzadeh MMalik SFix LKahng A(2004)Area-efficient instruction set synthesis for reconfigurable system-on-chip designsProceedings of the 41st annual Design Automation Conference10.1145/996566.996679(395-400)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996679
Um JKim TAckland B(2002)Layout-aware synthesis of arithmetic circuitsProceedings of the 39th annual Design Automation Conference10.1145/513918.513971(207-212)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.1145/513918.513971
Show More Cited By

Recommendations

Regularity driven logic synthesis
ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design

We present a new and innovative logic synthesis approach using regularity information of a design to selectively apply transformations and globally guide the synthesis process.Since traditional logic synthesis applies transformations without ...
Extraction of functional regularity in datapath circuits

Datapath circuits exhibit a very high degree of regularity, which is exploited by designers to generate layouts with a high density and performance as well as to reduce the overall design effort. Regularity in a datapath circuit manifests itself at ...
On clustering for maximal regularity extraction

The authors point out that proper usage of regularity in digital systems leads to efficient as well as economical designs. This important question of regularity extraction is examined, and a general and efficient methodology for component clustering ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EDTC '96: Proceedings of the 1996 European conference on Design and Test

March 1996

585 pages

ISBN:0818674237

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 March 1996

Check for updates

Qualifiers

Article

Conference

EDTC96

Sponsor:

SIGDA

EDTC96: European Design and Test Conference

March 11 - 14, 1996

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
102
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Galuzzi CBertels K(2011)The Instruction-Set Extension ProblemACM Transactions on Reconfigurable Technology and Systems10.1145/1968502.19685094:2(1-28)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1145/1968502.1968509
Brisk PKaplan ASarrafzadeh MMalik SFix LKahng A(2004)Area-efficient instruction set synthesis for reconfigurable system-on-chip designsProceedings of the 41st annual Design Automation Conference10.1145/996566.996679(395-400)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996679
Um JKim TAckland B(2002)Layout-aware synthesis of arithmetic circuitsProceedings of the 39th annual Design Automation Conference10.1145/513918.513971(207-212)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.1145/513918.513971
Kim YKim TGoto S(2001)Accurate exploration of timing and area trade-offs in arithmetic optimization using carry-save-addersProceedings of the 2001 Asia and South Pacific Design Automation Conference10.1145/370155.370565(622-628)Online publication date: 30-Jan-2001
https://dl.acm.org/doi/10.1145/370155.370565
Um JKim T(2001)An Optimal Allocation of Carry-Save-Adders in Arithmetic CircuitsIEEE Transactions on Computers10.1109/12.91081350:3(215-233)Online publication date: 1-Mar-2001
https://dl.acm.org/doi/10.1109/12.910813

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents