process that crosses it. Here the expected points is defined as the closest point 
to target point T of all points on each line process. 

When all answers have arrived at the requesting line process, the line pro-
cess found to be closest to the target point is selected. Then, S and the 
intersection point of the two line processes are connected. 

Next, a request message (route message) for searching paths is thrown to 
the line process, which returned the closest point to the target point. Finally, 
the routing process is completed when the expected point is equal to the target 
point. 

PROCESS STRUCTURE FOR LARGE-SCALE DATA 

The designing of routing programs based on a concurrent objects model 
requires many communication paths between processors. So, a lot of memory 
is consumed in controlling them. To solve this problem, we assign a distrib-
utor process to each processor to reduce the number of communication paths 
between processors. 

PARALLEL SPEEDUP 




Speedup

92-fold speedup is attained using 256 processors. Also a good wiring rate of 
99% to 100% was attained in this case. 

OUTLINE OF DEMONSTRATION 

For small-scale data (262 × 106 grid and 136 nets) and large-scale data 
(1048 × 636 grid and 3264 nets), our routing Program executes a routing 
path on PIM/m with 256 processors. 


					- 50 -