A parallel algorithm, called PARALLEX, which uses a conflict resolving method, has been developed for the switchbox routing problem in a parallel processing environment. PARALLEX can achieve a very high degree of parallelism by generating as many processes as nets. Each process is assigned to route a net, which bears the same identification number as the process. If conflicts are found for the current route of a net, then that process classifies the set(s) of conflict segments into groups that are identified by the various types of conflict(s) within each group. Each process with conflicts finds partial solutions by resolving every conflict of a group in the path-finding procedure and merges them with the solutions from other processes, which may or may not have conflicts, to make a conflict-free switchbox. The speed-up for 7and 19-net problems were 4.7 and 10, respectively.
展开▼
