K-d Tree based Gridless Maze Routing on Message Passing Multiprocessor Systems

Abstract

The routing of nets or a set of interconnection points is a compute intensive application encountered in CAD for VLSI design. In this paper, we propose a gridless algorithm for area routing based on the Hightower's Maze routing algorithm for message passing multiprocessor systems. The suitability of k-d trees as a data structuring technique for gridless maze routing is established. Since segments of routes are stored as rectangular objects in the k-d tree, the algorithm facilitates routing with variable width conductor paths. Results obtained both through simulation techniques and those obtained on an actual multiprocessor system based on message passing exhibit speedup proportional to the number of processors in the multiprocessor system.

Indexing terms:

• Gridless maze routing
• MMS architecture