(21) A Parallel Multilayer-Channel Router in CMGTP

[Software Features]

This package contains three programs for solving multilayer channel 
routing problems written in CLP(FD), KLIC, and CMGTP, respectively.
These programs can be used for two different purposes: First, they 
can be used to evaluate (constraint) logic and parallel logic 
programming languages and systems. A channel routing problem is a 
real-world problem in VLSI design that has been studied extensively 
before. The CLP(FD)  program has not only successfully solved all 
problems instances derived from the well-known Deutsch's Difficult 
Problem which have been solved before, but has also solved a problem 
instance which has never been solved before. The KLIC program has 
successfully solved many problem instances derived from the 
Deutsch's Difficult Problem although the intrinsic parallel processing 
ability in KLIC has not been fully exploited. Second, the other purpose 
is to improve these programs for solving many other types of channel 
routing problems and put them into practical use.
 

[Required Environment]

The CLP(FD) program runs on B-Prolog 
(http://www.cad.mse.kyutech.ac.jp/people/zhou/bprolog.html), which 
runs on most UNIX workstations and MS-Windows machines. To run the 
KLIC program, the KLIC system (http://www.icot.or.jp) needs be 
installed. The CMGTP program, which only solves a small example 
problem, was tested on the Prolog version of MGTP and should have no 
problem running on the KLIC version.

[File Configuration]

clpfd  - directory containing the CLP(FD) program
   route.pl         -- program
   deutsch72.pl  -- nets in Deutsch's Problem for dogleg-free routing
   deutsch218.pl -- nets in Deutsch's Problem for dogleg routing

klic -- directory containing the KLIC program
   route.kl1        -- program
   deutsch72.kl1  -- data1
   deutsch218.kl1 -- data2

cmgtp -- directory containing the MGTP program
   route.mg  -- program

[Others]

To run the CLP(FD) and KLIC programs for solving other problems, 
one needs to supplement the programs with another file that stores 
the nets (connecting requirements) and information about 
the channel. It is easy to prepare such a file. For an example, 
see deutsch72.pl.

[FTP]

• README
• Program and Documents in Japanese 21[K]