Wire Length Distribution for Placements of Computer Logic

Abstract

It is shown from simple theoretical considerations that the distribution ƒ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</inf> of wire lengths for a good two-dimensional placement on a square Manhattan grid should be of the form ƒ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</inf> = g/k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">γ</sup> (1 ≤ k ≤ L) and ƒ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</inf> ≈ 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.