Placement and average interconnection lengths of computer logic

Abstract

The length of the interconnections for a placement of logic gates is an important variable in the estimation of wiring space requirements, delay values, and power dissipation. A formula for an upper bound on expected average interconnection length, based on partitioning results, is given for linear and square arrays of gates. This upper bound gives significantly lower interconnection length than the bound based upon random placement. Actual placements give average interconnection lengths of about half the upper bound given by theory.