Article

Free access

Improved force-directed scheduling

Authors:

W. F. J. Verhaegh,

E. H. L. Aarts,

J. H. M. Korst,

P. E. R. LippensAuthors Info & Claims

EURO-DAC '91: Proceedings of the conference on European design automation

Pages 430 - 435

Published: 25 February 1991 Publication History

PDF eReader

Abstract

We present a mathematical justification of the technique of force-directed scheduling and propose two modifications of the basis algorithm introduced by Paulin and Knight. The newly presented modifications improve the effectiveness of force-directed scheduling without affecting its time complexity. This is illustrated by an empirical performance analysis based on a number of problem instances.

References

[1]

G. Borriello, E. Detjens, High-Level Synthesis: Current Status and Future Directions, Proceedings of the 25th Design Automation Conference, Anaheim, CA, July 1988, pp. 477--482.

Digital Library

Google Scholar

[2]

R. J. Cloutier, D. E. Thomas, The Combination of Scheduling, Allocation, and Mapping in a Single Algorithm, Research Report No. CMUCAD-90--17, Carnegie Mellon University, Pittsburgh, PA, May 1990.

Google Scholar

[3]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., New York, NY 1979, page 239.

Digital Library

Google Scholar

[4]

S. Y. Kung, H. J. Whitehouse, T. Kailath, VLSI and Modern Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1985, pp. 258--264.

Digital Library

Google Scholar

[5]

P. E. R. Lippens et al., PHIDEO: A Silicon Compiler for High Speed Algorithms, to be published in Proceedings European Design Automation Conference, Amsterdam, The Netherlands, February 1991.

Digital Library

Google Scholar

[6]

M. C. McFarland, A. C. Parker, R. Camposano, Tutorial on High-Level Synthesis, Proceedings of the 25th Design Automation Conference, Anaheim, CA, July 1988, pp. 330--336.

Digital Library

Google Scholar

[7]

P. G. Paulin, J. P. Knight, Force-Directed Scheduling in Automatic Data Path Synthesis, Proceedings of the 24th Design Automation Conference, Miami Beach, FL, July 1987, pp. 195--202.

Digital Library

Google Scholar

[8]

P. G. Paulin, J. P. Knight, Force-Directed Scheduling for the Behavioural Synthesis of ASIC's IEEE Transactions on Computer Aided Design, vol. 8, no. 6, June 1989, pp. 661--679.

Crossref

Google Scholar

[9]

L. Stok, R. van den Born, EASY: Multiprocessor Architecture Optimization, Proceedings International Workshop Logic and Architecture Synthesis for Silicon Compilers, Grenoble, France, May 1988.

Google Scholar

[10]

W. E. J. Verhaegh, Scheduling Problems in Video Signal Processing, Philips Technical Note NL-TN089/90, April 1990, pp. 56--70.

Google Scholar

Cited By

View all

Verhaegh WLippens PAarts EKorst Jvan der Werf Avan Meerbergen JTrevillyan LLightner M(1992)Efficiency improvements for force-directed schedulingProceedings of the 1992 IEEE/ACM international conference on Computer-aided design10.5555/304032.304121(286-291)Online publication date: 8-Nov-1992
https://dl.acm.org/doi/10.5555/304032.304121
Lippens Pvan Meerbergen Jvan der Werf AVerhaegh WMcSweeney BHuisken JMcArdle OAmbler TJess JDe Man H(1991)PHIDEOProceedings of the conference on European design automation10.5555/951513.951608(436-441)Online publication date: 25-Feb-1991
https://dl.acm.org/doi/10.5555/951513.951608

Improved force-directed scheduling
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Improved Force-Directed Layouts
GD '98: Proceedings of the 6th International Symposium on Graph Drawing

Techniques for drawing graphs based on force-directed placement and virtual physical models have proven surprisingly successful in producing good layouts of undirected graphs. Aspects of symmetry, structure, clustering and reasonable vertex distribution ...
Improved force-directed scheduling in high-throughput digital signal processing

This paper discusses improved force-directed scheduling and its application in the design of high-throughput DSP systems, such as real-time video VLSL circuits. We present a mathematical justification of the technique of force-directed scheduling, ...
Integrating edge routing into force-directed layout
GD'06: Proceedings of the 14th international conference on Graph drawing

The typical use of force-directed layout is to create organic-looking, straight-edge drawings of large graphs while combinatorial techniques are generally preferred for high-quality layout of small to medium sized graphs. In this paper we integrate edge-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EURO-DAC '91: Proceedings of the conference on European design automation

February 1991

577 pages

ISBN:0818621303

Conference Chair:
Tony Ambler
Brunel University, Uxbridge, UK
,
General Chair:
Jochen Jess
TU Eindhoven, Eindhoven, The Netherlands
,
Program Chair:
Hugo De Man
KU Leuven/IMEC, Leuven, Belgium

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 25 February 1991

Check for updates

Qualifiers

Article

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
345
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)4

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Verhaegh WLippens PAarts EKorst Jvan der Werf Avan Meerbergen JTrevillyan LLightner M(1992)Efficiency improvements for force-directed schedulingProceedings of the 1992 IEEE/ACM international conference on Computer-aided design10.5555/304032.304121(286-291)Online publication date: 8-Nov-1992
https://dl.acm.org/doi/10.5555/304032.304121
Lippens Pvan Meerbergen Jvan der Werf AVerhaegh WMcSweeney BHuisken JMcArdle OAmbler TJess JDe Man H(1991)PHIDEOProceedings of the conference on European design automation10.5555/951513.951608(436-441)Online publication date: 25-Feb-1991
https://dl.acm.org/doi/10.5555/951513.951608

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Improved Force-Directed Layouts

Improved force-directed scheduling in high-throughput digital signal processing

Integrating edge routing into force-directed layout