CONCURRENT ROUTlNG ALGORITHM 

In our program, each line segment corresponds to a process. So, we used the 
lookahead line search method as a basic algorithm. This algorithm guarantees 
connection between a start point and a target point when paths exist between 
them.

Two types of parallelism are embedded. One is in the lookahead operation, 
and the other is concurrent routing of different nets. 




Parallel execution of expected points 

Parallel execution of lookahead operation for one net is as follows. A start 
point S and a target point T are given. When the operation starts search-
ing virtically from S, request messages (estimate messages) for calculation of 
expected points are distributed from the line process including S to the line 


					- 49 -