Article

Free access

Module selection and data format conversion for cost-optimal DSP synthesis

Authors:

Keshab K. ParhiAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 322 - 329

Published: 06 November 1994 Publication History

Abstract

In high level synthesis each node of a synchronous dataflow graph (DFG) is scheduled to a specific time and allocated to a processor. In this paper we present new integer linear programming (ILP) models which generate a blocked schedule for a DFG with implicit retiming, pipelining, and unfolding while performing module selection and data format conversion. A blocked schedule is a schedule which overlaps multiple iterations of the DFG to guarantee a minimum number of processors. Component modules are selected from a library of processors to minimize cost. Furthermore, we include data format converters between processors of different data formats. In addition, we minimize the unfolding factor of the blocked schedule.

References

[1]

M. C. McFarland, A. C. Parker, and R. Camposano, "The High-Level Synthesis of Digital Systems," Proc. of the IEEE, vol. 78, pp. 301-318, Feb. 1990.

[2]

M. Renfors and Y. Neuvo, "The Maximum Sampling Rate of Digital Filters under Hardware Speed Constraints," IEEE Trans. Circuits Syst., vol. CAS-28, pp. 196-202, Mar. 1981.

[3]

K. K. Parhi and D. G. Messerschmitt, "Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding," IEEE Trans. Computers, vol. C-40, pp. 178- 195, Feb. 1991.

Digital Library

[4]

M.R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman, 1979.

Digital Library

[5]

P. G. Paulin and J. E Knight, "Force-Directed Scheduling for the Behavioral Synthesis of ASIC's," IEEE Trans. Computer-Aided Design, vol. CAD-8, pp. 661-679, June 1989.

[6]

N. Park and A. C. Parker, "Sehwa: A Software Package for Synthesis of Pipelines from Behavioral Specifications," IEEE Trans. Computer-Aided Design, vol. 7, Mar. 1988.

Digital Library

[7]

S.M. Heemstra de Groot, S. H. Gerez, and O. E. Herrmann, "Range-Chart-Guided Iterative Data-Flow Graph Scheduling," IEEE Trans. Circuits Syst.-I: Fund. Theory & Appl., vol. CAS-39, pp. 351-364, May 1992.

[8]

C.-Y. Wang and K. K. Parhi, "Resource Constrained Loop List Scheduler for DSP Algorithms," Journal of VLSI Signal Processing, Special issue of VLSI Design Methodologies for Digital Signal Processing Systems, to appear in 1994.

Digital Library

[9]

C.-T. Hwang, J.-H. Lee, and Y.-C. Hsu, "A Formal Approach to the Scheduling Problem in High Level Synthesis," IEEE Trans. Computer-Aided Design, vol. CAD-10, pp. 464-475, Apr. 1991.

[10]

C.H. Gebotys, "Synthesis of Throughput-Optimized Multichip Architectures," in Proc. IEEE Custom Integrated Circuits Conf., San Diego, pp. 5.2.1-5.2.4, May 1993.

[11]

C.H. Gebotys and R. J. Gebotys, "Optimal Mapping of DSP Applications to Architectures," in Proc. 26th Hawaii Int. Conf. System Sciences, pp. 116-123, 1993.

[12]

C.H. Gebotys and M. I. Elmasry, "Global Optimization Approach for Architecture Synthesis," IEEE Trans. Computer- Aided Design, vol. CAD-12, pp. 1266-1278, Sept. 1993.

[13]

C.-T. Hwang and Y.-C. Hsu, "Zone Scheduling," IEEE Trans. Computer-Aided Design, vol. CAD-12, pp. 926-934, July 1993.

[14]

A. Bachmann, M. Sch6binger, and L. Thiele, "Synthesis Methods for Domain Specific Multiprocessor Systems including Memory Design," in VLSI Signal Processing, VI, pp. 417-425, 1993.

[15]

L. E. Lucke and K. K. Parhi, "Generalized ILP Scheduling and Allocation for High-Level DSP Synthesis," in Proc. IEEE Custom Integrated Circuits Conf., San Diego, pp. 5.4.1-5.4.4, May 1993.

[16]

C. E. Leiserson et al., "Optimizing Synchronous Circuitry by Retiming," in 3rd Caltech Conf. on VLSI, Pasadena, CA, pp. 87-116, Mar. 1983.

[17]

J. Jump and S. Ahuja, "Effective Pipelining of Digital Systems," IEEE Trans. Computers, vol. C-27, pp. 855-865, Sept. 1978.

[18]

J. M. Rabaey, C. Chu, E Hoang, and M. Potkonjak, "Fast Prototyping of Datapath-Intensive Architectures," IEEE Design & Test of Computers, vol. 8, pp. 40-51, June 1991.

Digital Library

[19]

M. Ishikawa and G. D. Micheli, "A module Selection Algorithm for High-Level Synthesis," in Proc. of the IEEE Int. Symp. Circuits and Systems, Singapore, pp. 1777-1780, June 1991.

[20]

A.H. Timmer and J. A. G. Jess, "Execution Interval Analysis under Resource Constraints," in Proc. of the IEEE Int. Conf. on Computer Aided Design, pp. 454-459, 1993.

Digital Library

[21]

K. K. Parhi, "A Systematic Approach for Design of Digit- Serial Processing Architectures," IEEE Trans. Circuits Syst., vol. 38, pp. 358-375, Apr. 1991.

[22]

L. E. Lucke and K. K. Parhi, "Data-Flow Transformations for Critical Path Reduction in High-Level DSP Synthesis," IEEE Trans. Computer-Aided Design, vol. CAD-12, pp. 1063-1068, July 1993.

[23]

E. E Girczyz, "Loop Winding--A Data Flow Approach to Functional Pipelining," in Proc. of the IEEE Int. Symp. Circuits and Systems, Philadelphia, pp. 382-385, May 1987.

[24]

D. A. Schwartz and T. E Barnwell, III, "Cyclo-static solutions: Optimal multiprocessor realizations of Recursive Algorithms," VLSI Signal Processing H, 1986.

[25]

A. Brooke, D. Kendrick, and A. Meeraus, GAMS: A User's Guide, Release 2.25. South San Francisco, CA: The Scientific Press, 1992.

Cited By

O'Neil TSha EGhose KMadden PDe VKogge P(2002)Minimizing resources in a repeating schedule for a split-node data-flow graphProceedings of the 12th ACM Great Lakes symposium on VLSI10.1145/505306.505336(136-141)Online publication date: 18-Apr-2002
https://dl.acm.org/doi/10.1145/505306.505336
Ito KParhi K(1997)A Generalized Technique for Register Counting and its Application to Cost-Optimal DSP Architecture SynthesisJournal of VLSI Signal Processing Systems10.5555/255436.281294416:1(57-72)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.5555/255436.2812944

Index Terms

Module selection and data format conversion for cost-optimal DSP synthesis
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Signal processing systems
  2. Electronic design automation
    1. High-level and register-transfer level synthesis

Recommendations

ILP-based cost-optimal DSP synthesis with module selection and data format conversion

In high-level synthesis, a data flow graph (DFG) description of an algorithm is mapped onto a register transfer level description of an architecture. Each node of the DFG is scheduled to a specific time and allocated to a processor. In this paper, we ...
A Generalized Technique for Register Counting and its Application to Cost-Optimal DSP Architecture Synthesis
Special issue on the 1995 VLSI signal processing workshop

In this paper we propose a generalized technique to count the required number of registers in a schedule which supports overlapped scheduling and can be applied to the case where a general digit-serial data format is used. This technique is integrated ...
Code Synthesis for Sparse Tensor Format Conversion and Optimization
CGO '23: Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization

Many scientific applications compute using sparse data and store that data in a variety of sparse formats because each format has unique space and performance benefits. Optimizing applications that use sparse data involves translating the sparse data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Upcoming Conference

ICCAD '24

Sponsor:
sigda

IEEE/ACM International Conference on Computer-Aided Design

October 27 - 31, 2024

New York , NY , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
181
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)14

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

O'Neil TSha EGhose KMadden PDe VKogge P(2002)Minimizing resources in a repeating schedule for a split-node data-flow graphProceedings of the 12th ACM Great Lakes symposium on VLSI10.1145/505306.505336(136-141)Online publication date: 18-Apr-2002
https://dl.acm.org/doi/10.1145/505306.505336
Ito KParhi K(1997)A Generalized Technique for Register Counting and its Application to Cost-Optimal DSP Architecture SynthesisJournal of VLSI Signal Processing Systems10.5555/255436.281294416:1(57-72)Online publication date: 1-May-1997
https://dl.acm.org/doi/10.5555/255436.2812944

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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