PARALLEL FORMULATION OF RA 

Parallel RA can update schedule tables more times than SA at medium 
and low temperatures. 

A host PE controls all clusters, and each cluster consists of one master 
PE and several slave PEs. 


  In each cluster, a master PE updates its own schedule table by using 
     the rearrangement procedures which slave PEs find in parallel. 

  A host PE increases the number of slave PEs by merging two clusters 
     gradually to avoid decreases in the acceptance ratio (update ratio). 

OUTLINE OF DEMONSTRATION (2) 

(1) Changes of cluster 
    First, all PEs except the host PE perform annealing processes as the 
    master PE. Then, some of the master PEs become slave PEs. 

(2) Changes in acceptance ratio 
    The black line shows parallel RA and the purple line shows serial SA. 

(3) Changes in cost 
    The black line shows parallel RA and the purple line shows serial SA. 





Demonstration (2) 


					- 42 -