Figure 2: Process model on PVM
Figure 2: Process model on PVM
For the implementation on PVM, the AIDA* process model had to be changed. Our transputer executes only one task per processor, so that tree search and load-balancing must be done in one single task. Following Rao and Kumar [2], we interrupt the node expansion process at certain time intervals to allow processing of incoming messages. The frequency of the subroutine calls for this communication management depends on the system size. Communication service interrupts occur every 100 to 1000 node expansions. With an average working rate of 35000 nodes per second one processor can manage 40 to 300 messages in one second (64 and 512 tasks resp.). As shown in Figure 2, the implementation also makes use of a ring topology (like the Parix version), but work packets are returned directly to the requester.