A Class of Array Architectures for Hardware Grid Routers

Special-purpose hardware architectures have been recently proposed for solving a number of increasingly complex design automation problems. This paper proposes a class of two-dimensional SIMD array processors--the IAP architectures for implementation of grid routing algorithms. The major advantages of the IAP machines are, completely modular designs which are not pin-limited regardless of array size, and the ability to find the lowest cost route for a net, in time which is a linear function of the length of that route. A number of new procedures for parallel routing (simultaneous routing of k nets) are introduced, which take advantage of the linear time complexity of the IAP architectures. An analysis is presented of the time complexities of these procedures and examples are presented to exhibit their applicability.