article

Wire length distribution for placements of computer logic

Author:

W. E. DonathAuthors Info & Claims

IBM Journal of Research and Development, Volume 25, Issue 2-3

Pages 152 - 155

https://doi.org/10.1147/rd.252.0152

Published: 01 March 1981 Publication History

Abstract

It is shown from simple theoretical considerations that the distribution f_k of wire lengths for a good two-dimensional placement on a square Manhattan grid should be of the form f_k = g/k^γ (1 ≤ k ≤ L) and f_k ≅ 0 (k > L), where γ is related to the Rent partitioning exponent p by the equation 2p + γ ≅ 3. Three placements were investigated and the distribution functions for wire length were found to follow the above relationships.

References

[1]

W. E. Donath, "Placement and Average Interconnection Lengths of Computer and Systems," IEEE Trans. Circuits and Systems CAS-26, 272-277 (1979).

Crossref

Google Scholar

[2]

W. R. Heller, W. E. Donath, and W. F. Mikhail, "Prediction of Wiring Space Requirements For LSI," Proceedings of the 14th Design Automation Conference, New Orleans, 1977, pp. 32-43.

Crossref

Google Scholar

[3]

B. S. Landman and R. L. Russo, "On a Pin or Block Relationship for Partitions of Logic Graphs," IEEE Trans. Computers C-20, 1469-1479 (1971).

Crossref

Google Scholar

[4]

W. E. Donath, "Equivalence of Memory to 'Random Logic,'" IBM J. Res. Develop. 18, 401-407 (1974).

Digital Library

Google Scholar

[5]

M. Feuer, "Connectivity of Random Logic," Proceedings of the Workshop on Large-Scale Networks and Systems, IEEE 1980 Symposium on Circuits and Systems, Houston, TX, pp. 7-11.

Google Scholar

[6]

B. Mandelbrot, "Self Similar Error Clusters and Communications Systems and the Concept of Conditional Stationarity," IEEE Trans. Commun. Syst. COM-13, 71-90 (1965).

Crossref

Google Scholar

[7]

P. Levy, Theorie de l'dddition des Variables Aleatoires, Gauthier-Villars, Paris, 1954.

Google Scholar

[8]

A. H. Dansky, "Bipolar Circuit Design for a 5000-Circuit VLSI Gate Array." IBM J. Res. Develop. 25, 116-125 (1981, this issue).

Digital Library

Google Scholar

[9]

W. E. Donath, IBM Tech. Disclosure Bull. 17, 3121-3125 (1975).

Google Scholar

Cited By

View all

Greene JIenne PZhang Z(2023)FPGA Mux Usage and Routability Estimates without Explicit RoutingProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573045(141-147)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573045
Vernizzi GLanzerotti MKujawski JWeatherwax A(2014)Topological constraints for E. F. Rent's work on microminiature packaging and circuitryIBM Journal of Research and Development10.1147/JRD.2014.230722558:2-3(13-13)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1147/JRD.2014.2307225
Rakai LFarshidi ABehjat LWestwick D(2012)A new length-based algebraic multigrid clustering algorithmVLSI Design10.1155/2012/3952602012(8-8)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1155/2012/395260
Show More Cited By

Recommendations

Semi-individual wire-length prediction with application to logic synthesis

A new concept for wire-length prediction, the semi-individual wire-length prediction, is introduced. Structural metrics, such as mutual contraction and net range, are used to predict which interconnects have a tendency to be long or short in the final ...
Wire length prediction in constraint driven placement
SLIP '03: Proceedings of the 2003 international workshop on System-level interconnect prediction

Experiments show that lengths of individual wires are different for different placement algorithms. To achieve accurate wire length prediction, some knowledge of a placer's details is necessary. We postulate that wire length prediction should be coupled ...
On legalization of row-based placements
GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI

Cell overlaps in the results of global placement are guaranteed to prevent successful routing. However, common techniques for fixing these problems may endanger routing in a different way --- through increased wirelength and congestion. We evaluate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IBM Journal of Research and Development

IBM Journal of Research and Development Volume 25, Issue 2-3

March 1981

96 pages

ISSN:0018-8646

Issue’s Table of Contents

Publisher

IBM Corp.

United States

Publication History

Published: 01 March 1981

Revised: 08 December 1980

Received: 14 October 1980

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Greene JIenne PZhang Z(2023)FPGA Mux Usage and Routability Estimates without Explicit RoutingProceedings of the 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays10.1145/3543622.3573045(141-147)Online publication date: 12-Feb-2023
https://dl.acm.org/doi/10.1145/3543622.3573045
Vernizzi GLanzerotti MKujawski JWeatherwax A(2014)Topological constraints for E. F. Rent's work on microminiature packaging and circuitryIBM Journal of Research and Development10.1147/JRD.2014.230722558:2-3(13-13)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1147/JRD.2014.2307225
Rakai LFarshidi ABehjat LWestwick D(2012)A new length-based algebraic multigrid clustering algorithmVLSI Design10.1155/2012/3952602012(8-8)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1155/2012/395260
Manevich RCidon IKolodny A(2012)Handling global traffic in future CMP NoCsProceedings of the International Workshop on System Level Interconnect Prediction10.1145/2347655.2347671(40-47)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2347655.2347671
York JChiou DGroeneveld PSciuto DHassoun S(2012)On the asymptotic costs of multiplexer-based reconfigurabilityProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228503(790-795)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228503
Strukov DMishchenko ADe Micheli GAl-Hashimi BMueller WMacii E(2010)Monolithically stackable hybrid FPGAProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871087(661-666)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871087
Fathi BBehjat LRakai LCheng CReda S(2009)A pre-placement net length estimation technique for mixed-size circuitsProceedings of the 11th international workshop on System level interconnect prediction10.1145/1572471.1572480(45-52)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1572471.1572480
Whitney MIsailovic NPatel YKubiatowicz J(2009)A fault tolerant, area efficient architecture for Shor's factoring algorithmACM SIGARCH Computer Architecture News10.1145/1555815.155580237:3(383-394)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1555815.1555802
Whitney MIsailovic NPatel YKubiatowicz JKeckler SBarroso L(2009)A fault tolerant, area efficient architecture for Shor's factoring algorithmProceedings of the 36th annual international symposium on Computer architecture10.1145/1555754.1555802(383-394)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1555754.1555802
Smith AWilton SDas JChow PCheung P(2009)Wirelength modeling for homogeneous and heterogeneous FPGA architectural developmentProceedings of the ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1508128.1508156(181-190)Online publication date: 24-Feb-2009
https://dl.acm.org/doi/10.1145/1508128.1508156
Show More Cited By

View Options

View options

Get Access

Login options

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

Abstract

References

Cited By

Recommendations

Semi-individual wire-length prediction with application to logic synthesis

Wire length prediction in constraint driven placement

On legalization of row-based placements

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations