Direction-constrained layer assignment for rectangle escape routing

摘要

Given a set of n buses with their possible escape directions to the available boundaries in a pin array, firstly, the layer assignment of the given buses with the same escape direction in rectangle escape routing can be transformed into an interval packing problem. Based on the optimality of a left-edge algorithm for interval packing, the layer assignment of the given buses can be obtained by using the concept of the density-reduction-oriented assignment. Based on the density-reduction-oriented layer assignment on an available boundary, an iterative assignment approach can be proposed for direction-constrained layer assignment in rectangle escape routing. Compared with a direction-constrained algorithm modified from Ma's approximation algorithm[10], the experimental results show that our proposed iterative assignment algorithm obtains the same optimal result but reduces 90.3% of CPU time for eight tested examples on the average.