I want to implement branch and bound algorithm in parallel, the
illustration is like this:
There are n processors, and a binary search tree. First, there is only one
node in tree, and it is processed by the first processor, and then if
branching, there will be two node in tree, the first one will proccessed by
the same processor and the second one will be sent to the one of available
processor, if there is no available processor then it will processed in the
same processor, and so on.
Also there are variable Z_optimal and Z_current, where Z_optimal is the
lower bound of best solution and Z_current is the value of the current
solution, and if one processor found new Z_Optimal, it should broadcast it
to all processors.
How can I check the status of all processor whether it's available or not
depending on the number of the tree nodes they currently have, if the
number of the node is 0 then it's available else it's not available. If the
processor is available then one of the processor that have more than 1 node
send 1 node to that processor. And the computation end if all processor are
available (there is no active node in tree).
What I think is: there is an array variable that keep the status of all
processor and if one processor change it's status locally then it's should
broadcast to all other processor.
The algorithm is like this:
Set proc_status[0]=1 and the other is set 0; // 0 = proc is available and 1
= proc is not available
while (not all proc available) {
if (numnode == 0) {
//Wait from other proc to send node;
if (receiving node) then set proc_status[my_rank]=1 and broadcast the
proc_status;
}
else {
if (numnode > 1 and there is proc available) then send 1 node to the
available proc;
doing computation;
if (Z_current >= Z_optimal) then prune the node;
else { // Z_current < Z_optimal
if (solution not integer) then branching;
else set Z_optimal=Z_current and broadcast Z_Optimal;
}
}
}
I have already try to use MPI_Bcast, it's not work because inside the loop,
other processor didn't access it
And also if I use the MPI_Send and MPI_Recv, but if there is no data send,
than MPI_Recv will always waiting, and I want my program continue to work
and not waiting if there is no updating data.
I also try the MPI_Irecv and MPI_Test but I still confused how they work
because when I use them sometime some processor receive it but more often
no processors receive the value that already send by one processor. How to
make sure that the data is received by processor and not lost ?
How to implement the correct and efficient brodcast of proc_status and the
Z_Optimal also the sending and receiving the node or is there better
solution to my program?
Thank you, and sorry if my English is bad and my question is too long.
|
