The authors present a new parallel global routing algorithm for sea-of-gates arrays and its parallel implementation. In the proposed method, making use of the fact that the number of widely distributed nets is comparatively small. The widely distributed nets are processed on one processor and the local nets are processed based on the RSM (region shifting method) in parallel. The algorithm has been implemented on a distributed environment using many engineering workstations. The experimental results have shown that the proposed method achieved good speedups of up to seven using eight processors. The routing quality is the same as the quality obtained by the sequential global routing method.
展开▼