More Web Proxy on the site http://driver.im/

article

Synthesis of application-specific multiprocessor systems including memory components

Authors:

Alice C. ParkerAuthors Info & Claims

Journal of VLSI Signal Processing Systems, Volume 8, Issue 2

Pages 97 - 116

Published: 01 October 1994 Publication History

Abstract

Heterogeneous systems have the potential to achieve enhanced performance as well as cost-effectiveness over homogeneous systems when the application domain is known since they can match the problem structure more closely. A formal design method, SOS, has been developed which can be used to synthesize optimal heterogeneous systems for given applications. The method involves creation of a Mixed Integer-Linear Programming (MILP) model and solution of the model. In this paper, first we show how to apply the method to application-specific systems with bus-style interconnection between the processors. We further demonstrate how to extend the method to deal with memory costs explicitly. Several experiments were performed with the original as well as the extended MILP models. These results indicate that it is important to include memory costs explicitly at design time.

References

[1]

"CAD for system design: Is it practical?"SIGDA Newsletter, vol. 19, pp. 40---49, September 1989.

Digital Library

[2]

E.A. Lee and J.C. Bier, "Architectures for Statically Scheduled Dataflow,"Journal of Parallel and Distributed Computing, vol. 10 pp. 333---348, 1990.

Digital Library

[3]

H.J. Siegel, T. Schwederski, J.T. Kuehn, and N.J. Davis, IV, "An overview of the PASM parallel processing system," D.D. Gajski, V.M. Milutinovic, H.J. Siegel and B.P. Furht, editors,Computer Architecture, pp. 387---407. IEEE Computer Society Press, Washington, D.C., 1987.

[4]

R. Freund and D. Conwell, "Superconcurrency: A Form of Distributed Heterogeneous Supercomputing,"Supercomputing Review, October 1990.

[5]

G. Amdahl, "The Validity of the Single-Processor Approach to Achieving Large-Scale Computing Capabilities,"AFIPS Conference Proceedings, pp. 483---485, 1967.

[6]

S. Prakash and A.C. Parker, "Synthesis of Application-Specific Multiprocessor Architectures,"Proceedings 28th Design Automation Conference, pp. 8---13. ACM/IEEE, June 1991.

[7]

S. Prakash and A.C. Parker, "A Design Method for Optimal Synthesis of Application-Specific Heterogeneous Multiprocessor Systems,"Proceedings IPPS '92--Workshop on Heterogeneous Processing. ACM/IEEE, March 1992.

[8]

S. Prakash and A.C. Parker, "SOS: Synthesis of Application-Specific Heterogeneous Multiprocessor Systems,"Journal of Parallel and Distributed Computing, vol. 16, pp. 338---351, 1992.

[9]

S. Prakash,Synthesis of Application-Specific Multiprocessor Systems, Ph.D. Thesis, Dept. of Electrical Engineering, University of Southern California, Los Angeles, CA, January 1993.

[10]

E.B. Fernandez and B. Bussell, "Bounds on the number of processors and time for multiprocessor optimal schedules,"IEEE Transactions on Computers, vol. C-22, pp. 745---751, 1973.

[11]

T.L. Adam, K.M. Chandy, and J.R. Dickson, "A comparison of list schedules for parallel processing systems,"Communications of the ACM, vol. 17, pp. 685---690, 1974.

Digital Library

[12]

H. Kasahara and S. Narita, "Practical multiprocessor scheduling algorithms for efficient parallel processing,"IEEE Transactions on Computers, vol. C-33, pp. 1023---1029, 1984.

[13]

Jing-Jang Hwang, Yuan-Chieh Chow, Frank D. Anger, and Chung-Yee Lee, "Scheduling precedence graphs in systems with interprocessor communication times,"SIAM J. Comput., vol. 18, pp. 244---257, 1989.

Digital Library

[14]

H. El-Rewini and T.G. Lewis, "Scheduling parallel program tasks onto arbitrary target machines,"Journal of Parallel and Distributed Computing, vol. 9 pp. 138---153, 1990.

Digital Library

[15]

M.A. Al-Mouhamed, "Lower bound on the number of processors and time for scheduling precedence graphs with communication costs,"IEEE Transactions on Software Engineering, vol. 16, pp. 1390---1401, 1990.

Digital Library

[16]

H.S. Stone, "Multiprocessor scheduling with the aid of network flow algorithms,"IEEE Transactions on Software Engineering, vol. SE-3, pp. 85---93, 1977.

Digital Library

[17]

S.H. Bokhari, "A shortest tree algorithm for optimal assignments across space and time in a distributed processor system,"IEEE Transactions on Software Engineering, vol. SE-7, pp. 583---589, 1981.

Digital Library

[18]

S.H. Bokhari, "Partitioning problems in parallel, pipe-lined, and distributed computing,"IEEE Transactions on Computers, vol. 37, pp. 48---57, 1988.

Digital Library

[19]

Chien-Chung Shen and Wen-Hsiang Tsai, "A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion,"IEEE Transactions on Computers, vol. C-34, pp. 197---203, 1985.

[20]

B. Indurkhya, H. S. Stone and L. Xi-Cheng, "Optimal partitioning of randomly generated distributed programs,"IEEE Transactions on Software Engineering, vol. SE-12, pp. 483---495, 1986.

Digital Library

[21]

W.W. Chu and L.M.-T. Lan, "Task allocation and precedence relations for distributed real-time systems,"IEEE Transactions on Computers, vol. C-36, pp. 667---679, 1987.

[22]

C.E. Houstis, "Module allocation of real-time applications to distributed systems,"IEEE Transactions on Software Engineering, vol. 16, pp. 699---709, 1990.

Digital Library

[23]

W.W. Chu, L.J. Hollaway, M.-T. Lan, and K. Efe, "Task allocation in distributed data processing,"Computer, vol. 13, pp. 57---69, Nov. 1980.

Digital Library

[24]

E.K. Haddad, "Partitioned load allocation for minimum parallel processing time,"Proceedings 1989 International Conference on Parallel Processing. IEEE Computer Society, Aug. 1989.

[25]

R. Mehrotra and S.N. Talukdar, "Task scheduling on multiprocessors," Tech. Rep. DRC-18-55-82, Department of Electrical Engineering, Carnegie-Mellon University, Pittsburgh, PA, Dec. 1982.

[26]

L.J. Hafer and A.C. Parker, "A formal method for the specification, analysis, and design of register-transfer level digital logic,"IEEE Transactions on Computer-Aided Design, vol. CAD-2, pp. 4---17, 1983.

[27]

J.A.B. Fortes and D.I. Moldovan, "Parallelism detection and transformation techniques useful for VLSI algorithms,"Journal of Parallel and Distributed Computing, vol. 2, pp. 277---301, 1985.

[28]

L.J. Hafer and E. Hutchings, "Bringing up Bozo," Tech. Rep. CMPT TR 90-2, School of Computing Science, Simon Fraser University, Burnaby, B.C., V5A 1S6, Mar. 1990.

[29]

R. Jain, K. Kuçükçakar, M. Mlinar, and A. Parker, "Experience with the ADAM Synthesis System,"Proceedings 26th Design Automation Conference, pp. 56---61. ACM/IEEE, June 1989.

Cited By

Baruah SFisher N(2005)Code-Size Minimization in Multiprocessor Real-Time SystemsProceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 2 - Volume 0310.1109/IPDPS.2005.139Online publication date: 4-Apr-2005
https://dl.acm.org/doi/10.1109/IPDPS.2005.139
Grünewald MNiemann JPorrmann MRückert U(2004)A Mapping Strategy for Resource-Efficient Network Processing on Multiprocessor SoCsProceedings of the conference on Design, automation and test in Europe - Volume 210.5555/968879.969125Online publication date: 16-Feb-2004
https://dl.acm.org/doi/10.5555/968879.969125
Cai LYu HGajski DImai M(2004)A novel memory size model for variable-mapping in system level designProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015308(812-817)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015308
Show More Cited By

Index Terms

Synthesis of application-specific multiprocessor systems including memory components

Recommendations

Synthesis of application-specific memory structures
High-level synthesis of memory-intensive application-specific systems
Synthesis of application-specific heterogeneous multiprocessor systems (abstract)
Special Issue: Proceedings of the 19th annual international symposium on Computer architecture (ISCA '92)

Heterogeneous systems can achieve enhanced performance and/or cost-effectiveness over homogeneous systems. SOS, a formal method to synthesize optimal heterogeneous systems for given applications, involves creation and solution of a mixed integer-linear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of VLSI Signal Processing Systems

Journal of VLSI Signal Processing Systems Volume 8, Issue 2

Special issue on application specific array processors (ASAP-92)

Oct. 1994

103 pages

ISSN:0922-5773

Editors:
Lothar Thiele
Univ. des Saarlandes, Saarbru¨cken, Germany
,
Edward Chow
California Institute of Technology, Pasadena
,
Earl E. Swartzlander
Univ. of Texas at Austin, Austin
,
S. Y. Kung
Princeton Univ., Princeton, NJ

Issue’s Table of Contents

Copyright © Copyright © 1994 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Baruah SFisher N(2005)Code-Size Minimization in Multiprocessor Real-Time SystemsProceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 2 - Volume 0310.1109/IPDPS.2005.139Online publication date: 4-Apr-2005
https://dl.acm.org/doi/10.1109/IPDPS.2005.139
Grünewald MNiemann JPorrmann MRückert U(2004)A Mapping Strategy for Resource-Efficient Network Processing on Multiprocessor SoCsProceedings of the conference on Design, automation and test in Europe - Volume 210.5555/968879.969125Online publication date: 16-Feb-2004
https://dl.acm.org/doi/10.5555/968879.969125
Cai LYu HGajski DImai M(2004)A novel memory size model for variable-mapping in system level designProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015308(812-817)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015308
Parameswaran S(2001)Code placement in hardware/software co-synthesis to improve performance and reduce costProceedings of the conference on Design, automation and test in Europe10.5555/367072.367836(626-632)Online publication date: 13-Mar-2001
https://dl.acm.org/doi/10.5555/367072.367836
Szymanek RKuchcinski KMadsen JHenkel JHu X(2001)A constructive algorithm for memory-aware task assignment and schedulingProceedings of the ninth international symposium on Hardware/software codesign10.1145/371636.371706(147-152)Online publication date: 25-Apr-2001
https://dl.acm.org/doi/10.1145/371636.371706
Madsen JBjørn-Jørgensen PJerraya ALavagno LVahid F(1999)Embedded system synthesis under memory constraintsProceedings of the seventh international workshop on Hardware/software codesign10.1145/301177.301526(188-192)Online publication date: 1-Mar-1999
https://dl.acm.org/doi/10.1145/301177.301526
Lee CPotkonjak MWolf W(1999)Synthesis of Hard Real-Time Application Specific SystemsDesign Automation for Embedded Systems10.1023/A:10089653045674:4(215-242)Online publication date: 1-Oct-1999
https://dl.acm.org/doi/10.1023/A%3A1008965304567
Heo DParker ARavikumar C(1997)Rapid Synthesis of Multi-Chip SystemsProceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications10.5555/523974.834851Online publication date: 4-Jan-1997
https://dl.acm.org/doi/10.5555/523974.834851
Kuchcinski KVahid FCatthoor F(1997)Embedded system synthesis by timing constraints solvingProceedings of the 10th international symposium on System synthesis10.5555/261693.261709(50-57)Online publication date: 17-Sep-1997
https://dl.acm.org/doi/10.5555/261693.261709
Lee CPotkonjak MWolf W(1996)System-Level Synthesis of Application Specific Systems using A* Search and Generalized Force-Directed HeuristicsProceedings of the 9th international symposium on System synthesis10.5555/524431.857932Online publication date: 6-Nov-1996
https://dl.acm.org/doi/10.5555/524431.857932

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents