HOME       UP       PREV       NEXT (Hazards From Array Memories)  

Smith-Waterman Genome Matcher

A well-known benchmark algorithm suitable for 2-D to 1-D parallel folding.

Use a 1-D grid of these elements:

public class SwElement
{ int width, unit;
  public int max;
  public int [] prev, here;
  public byte [,] slices;   // Local part of the PAM array
  public Kiwi.Channel < short > left_score, right_score;
  public Kiwi.Channel < byte > left_data, right_data;
  public Thread thread;
  short diag_left_left = 0;
  
  public SwElement(int u, int h)  // Constructor
   { width = h; unit = u;
     here = new int[width];
     prev = new int[width];
     slices = new byte[width, 20];
   }

  public short run()
  {
    max = 0;
    byte dbval = left_data.Read();
    short topScore = left_score.Read();
    right_data.Write(dbval);

    for (int qpos = 0; qpos < width; qpos++) prev[qpos] = here[qpos]; 

    for (int qpos = 0; qpos < width; qpos++)
    { 
      if ((qpos % unwind_factor)== 0) Kiwi.Pause();

      int above = prev[qpos];
      int left = qpos==0 ? topScore: here[qpos-1];
      int diag = (qpos == 0) ? diag_left_left:  prev[qpos - 1];
      int score = slices[qpos, dbval];
      int nv = Math.Max(0, Math.Max(left - 10, Math.Max(above - 10, diag + score)));
      if (nv > max) max = nv;
      here[qpos] = nv;
      if (qpos == width-1) right_score.Write((short)nv);
    }
    diag_left_left = topScore;
    return max;
  }

  // We need a way of exiting the elements when run as a KiwiS program.
  public void SWOperator()
  { 
    while(!elements_exit) run();
  }
}


22: (C) 2011, DJ Greaves, S Singh, University of Cambridge, Computer Laboratory.