* Class MaximumParsimonyBnbHyb is designed to be used in a hybrid parallel * program that runs on multiple nodes with one process per node and multiple * threads per process. Each thread has its own MaximumParsimonyBnbHyb instance. * Each thread uses its own MaximumParsimonyBnbHyb instance to search different * sections of the search graph concurrently. *
* Each process has a shared, replicated variable, bound, that holds the * best parsimony score found so far (i.e., the bound for branch-and-bound * search). The bound variable is an instance of class {@linkplain * edu.rit.pj.replica.ReplicatedInteger}. All the MaximumParsimonyBnbHyb * instances within the process share the same bound variable. Whenever * one thread finds a phylogenetic tree with a better parsimony score, it * notifies all the threads and processes by updating the bound variable. *
* To perform a search, each process must: *
* Note: Class MaximumParsimonyBnbHyb is not multiple thread safe; it is * intended to be used as a per-thread variable. * * @author Alan Kaminsky * @version 21-Nov-2008 */ public class MaximumParsimonyBnbHyb { // Exported static operations. /** * Create a new shared, replicated bound variable. The bound * variable will use the world communicator and a message tag of * Integer.MAX_VALUE. This message tag must not be used in any * other messages in the program. * * @param initialBound Initial bound for branch-and-bound search. */ public static ReplicatedInteger createBoundVariable (int initialBound) { return createBoundVariable (initialBound, Comm.world(), Integer.MAX_VALUE); } /** * Create a new shared, replicated bound variable. * * @param initialBound Initial bound for branch-and-bound search. * @param comm Communicator used by the bound variable. * @param tag Message tag used by the bound variable. * This message tag must not be used in any other * messages in the program. */ public static ReplicatedInteger createBoundVariable (int initialBound, Comm comm, int tag) { return new ReplicatedInteger (IntegerOp.MINIMUM, initialBound, tag, comm); } // Hidden data members. // List of DNA sequences with which to construct trees. private DnaSequenceList seqList; // Shared, replicated bound variable. private ReplicatedInteger bound; // For holding search results. private MaximumParsimonyResults results; // Length of each DNA sequence. private int L; // Number of DNA sequences. private int N; // Tree capacity. private int C; // Number of absent states as each DNA sequence is added. private int[] absentStates; // Stack of DNA sequence trees. private DnaSequenceTree[] treeStack; // Stack of auxiliary DNA sequence arrays. DnaSequence[][] seqArrayStack; // Tree signature currently being searched. private int[] signature; // Extra padding to avert cache interference. private long p0, p1, p2, p3, p4, p5, p6, p7; private long p8, p9, pa, pb, pc, pd, pe, pf; // Exported constructors. /** * Construct a new maximum parsimony phylogenetic tree construction * algorithm object. * * @param seqList DNA sequence list. * @param bound Shared, replicated bound variable. * @param results Object in which to store the results. */ public MaximumParsimonyBnbHyb (DnaSequenceList seqList, ReplicatedInteger bound, MaximumParsimonyResults results) { // Record parameters. this.seqList = seqList; this.bound = bound; this.results = results; // Initialize. L = seqList.seq(0).length(); N = seqList.length(); C = 2*N - 1; // Compute number of absent states as each DNA sequence is added. absentStates = seqList.countAbsentStates(); // Set up stack of DNA sequence trees. treeStack = new DnaSequenceTree [N]; for (int i = 0; i < N; ++ i) { treeStack[i] = new DnaSequenceTree (C); } // Initialize DNA sequence tree at first level of the search graph. treeStack[0].add (0, seqList.seq(0)); // Set up stack of auxiliary DNA sequence arrays. seqArrayStack = new DnaSequence [N] []; for (int i = 0; i < N; ++ i) { DnaSequence[] seqArray = new DnaSequence [i]; seqArrayStack[i] = seqArray; for (int j = 0; j < i; ++ j) { seqArray[j] = new DnaSequence (L); } } // Set up tree signature. signature = new int [N+32]; // Extra padding } // Exported operations. /** * Find the maximum parsimony phylogenetic tree(s) in the given section of * the search graph. The DNA sequence list was specified to the constructor. *
* The search will commence at level L of the search graph, 0 ≤ * L ≤ N−1, where N is the number of sequences * in the DNA sequence list. Of the (2L−1)!! vertices at level * L, the search will start at the V1-th such * vertex and end at the V2-th such vertex, 0 ≤ * V1 ≤ V2 ≤ * (2L−1)!! − 1. All search graph vertices at * and below vertices V1 through V2 * inclusive will be searched. *
* The results are stored in the {@linkplain MaximumParsimonyResults} object
* specified to the constructor. The findTrees() method will only
* find trees whose parsimony scores are less than or equal to the value of
* the bound variable specified to the constructor or the best
* bound found thereafter, whichever is smaller.
*
* @param startLevel
* L, the level of the search graph at which to commence the
* search.
* @param vertex1
* V1, the search graph vertex at level L at
* which to start the search.
* @param vertex2
* V2, the search graph vertex at level L at
* which to end the search.
*
* @exception IOException
* Thrown if an I/O error occurred.
*/
public void findTrees
(int startLevel,
int vertex1,
int vertex2)
throws IOException
{
// Initialize tree signature as specified by