BACKGROUND 

LSI routing is used to determine the connections between circuit terminals 
on LSI chips, after the placement of terminals is given. As the degree of LSI 
is large, routing design takes much time to develop. Thus, a fast and flexible 
router to deal with a routing constraints is desired. 

A new routing program based on a concurrent objects model has been de-
veloped, and has been evaluated from the viewpoint that the parallel inference 
machine PIM is a high performance MIMD machine with distributed memory. 

ROUTER SPECIFICATION 

The program is applicable for two layer routing. That is, using two layers, 
one for vertical and one for horizontal paths, each connection is routed on a 
virtual grid on the chip surface. 

The block and through hole inhibition conditions are also dealt with. 




An example of two layer routing 

PROGRAMMING BASED ON CONCURRENT OBJECTS MODEL 

Formalizing a problem based on the concurrent objects model is one of 
the most promissing ways of embedding parallelism in a given problem. In 
our routing program, each line segment on a routing grid line corresponds 
to a process (line process). Line processes determine their routing path in 
communication with other line processes. 

Then, the processes, which exchange messages frequently, are grouped. The 
groups are assigned to processors and are executed in parall by the various 
processors. 


					- 48 -