* The align() method is designed to be executed by a {@linkplain * edu.rit.pj.ParallelTeam} of threads. Thus, this class is suitable for use in * an SMP parallel program or a hybrid parallel program. *
* As an example of how the computation is performed in parallel while obeying * the sequential dependencies in the Smith-Waterman algorithm, suppose the * query sequence has 100 elements, the subject sequence has 500 elements, and * the parallel team has 4 threads. The 500 columns of the scoring matrix * S are partitioned equally among the threads: thread 0 gets columns * 1..125, thread 1 gets columns 126..250, thread 2 gets columns 251..375, * thread 3 gets columns 376..500. Then S is computed in parallel in a * series of rounds: *
*
| Round: | *Thread 0 computes: | *Thread 1 computes: | *Thread 2 computes: | *Thread 3 computes: | *
| 1 | *S[1][1..125] | *— | *— | *— | *
| 2 | *S[2][1..125] | *S[1][126..250] | *— | *— | *
| 3 | *S[3][1..125] | *S[2][126..250] | *S[1][251..375] | *— | *
| 4 | *S[4][1..125] | *S[3][126..250] | *S[2][251..375] | *S[1][376..500] | *
| 5 | *S[5][1..125] | *S[4][126..250] | *S[3][251..375] | *S[2][376..500] | *
| … | *… | *… | *… | *… | *
| 99 | *S[99][1..125] | *S[98][126..250] | *S[97][251..375] | *S[96][376..500] | *
| 100 | *S[100][1..125] | *S[99][126..250] | *S[98][251..375] | *S[97][376..500] | *
| 101 | *— | *S[100][126..250] | *S[99][251..375] | *S[98][376..500] | *
| 102 | *— | *— | *S[100][251..375] | *S[99][376..500] | *
| 103 | *— | *— | *— | *S[100][376..500] | *
* After a short startup period, all columns of S are being computed in * parallel, with different threads working on different rows so as to obey the * sequential dependencies. For example, S[4][126] is computed (by thread * 1 in round 5) after S[3][125] (by thread 0 in round 3), * S[3][126] (by thread 1 in round 4), and S[4][125] (by thread 0 * in round 4). * * @author Alan Kaminsky * @version 02-Jul-2008 */ public class ProteinLocalAlignmentSmp extends ProteinLocalAlignment { // Hidden data members. private ParallelTeam team; // Exported constructors. /** * Construct a new protein sequence local alignment object. * * @param team Parallel thread team that will compute the alignment. * * @exception NullPointerException * (unchecked exception) Thrown if team is null. */ public ProteinLocalAlignmentSmp (ParallelTeam team) { super(); if (team == null) { throw new NullPointerException ("ProteinLocalAlignmentSmp(): team is null"); } this.team = team; } // Exported operations. /** * Align the query sequence and the subject sequence. The parallel thread * team specified to the constructor computes the alignment in parallel. * * @return Alignment. * * @exception Exception * Thrown if an error occurred. */ public Alignment align() throws Exception { // Verify preconditions. if (A == null) { throw new IllegalStateException ("ProteinLocalAlignmentSmp.align(): Query sequence not set"); } if (B == null) { throw new IllegalStateException ("ProteinLocalAlignmentSmp.align(): Subject sequence not set"); } final int M = A.length - 1; final int N = B.length - 1; final int K = team.getThreadCount(); final int lastRound = M + K - 1; // Initialize global finish point reduction variable. final FinishPoint gblfp = new FinishPoint(); gblfp.maxScore = 0; gblfp.theQueryFinish = 0; gblfp.theSubjectFinish = 0; // Do the Smith-Waterman algorithm in the parallel thread team. team.execute (new ParallelRegion() { public void run() throws Exception { int threadIndex = getThreadIndex(); // Determine range of columns for this thread. Range range = new Range (1, N) .subrange (K, threadIndex); int jlb = range.lb(); int jub = range.ub(); // Initialize per-thread finish point. int maxScore = 0; int theQueryFinish = 0; int theSubjectFinish = 0; // Do all rounds. for (int round = 1; round <= lastRound; ++ round) { // Row for this thread in this round is round number offset // by thread index. If row is out of bounds, do nothing this // round. int i = round - threadIndex; if (1 <= i && i <= M) { int A_i = A[i]; int[] delta_A_i = delta[A_i]; int[] S_im1 = S[i-1]; int[] S_i = S[i]; int[] GA_im1 = GA[i-1]; int[] GA_i = GA[i]; int[] GB_i = GB[i]; int B_j, S_i_j, GA_i_j, GB_i_j; // Do only this thread's columns. for (int j = jlb; j <= jub; ++ j) { B_j = B[j]; GA_i_j = S_im1[j] + g; GA_i_j = Math.max (GA_i_j, GA_im1[j] + h); GB_i_j = S_i[j-1] + g; GB_i_j = Math.max (GB_i_j, GB_i[j-1] + h); S_i_j = S_im1[j-1] + delta_A_i[B_j]; S_i_j = Math.max (S_i_j, GA_i_j); S_i_j = Math.max (S_i_j, GB_i_j); S_i_j = Math.max (S_i_j, 0); if (S_i_j > maxScore) { maxScore = S_i_j; theQueryFinish = i; theSubjectFinish = j; } S_i[j] = S_i_j; GA_i[j] = GA_i_j; GB_i[j] = GB_i_j; } } // Wait for all threads to complete this round. barrier(); } // After all rounds, reduce per-thread finish point into global // finish point. gblfp.setToBest (maxScore, theQueryFinish, theSubjectFinish); } }); // Do the traceback in a single thread, starting from global finish // point. return computeTraceback (gblfp.maxScore, gblfp.theQueryFinish, gblfp.theSubjectFinish); } // Hidden helper classes. // A record of information about the local alignment finish point. private static class FinishPoint { // Alignment score. public int maxScore; // Query sequence index. public int theQueryFinish; // Subject sequence index. public int theSubjectFinish; // Set this finish point to the best of itself and the given finish // point. Multiple thread safe method. public synchronized void setToBest (int maxScore, int theQueryFinish, int theSubjectFinish) { if ((maxScore > this.maxScore) || (maxScore == this.maxScore && theQueryFinish < this.theQueryFinish) || (maxScore == this.maxScore && theQueryFinish == this.theQueryFinish && theSubjectFinish < this.theSubjectFinish)) { this.maxScore = maxScore; this.theQueryFinish = theQueryFinish; this.theSubjectFinish = theSubjectFinish; } } } }