Prefix sum (multi-processor-final)

A. Third Edition
This is programming assignment of comp346. And in this edition I changed the implementation to follow professor's
idea. But does the second algorithm have a better efficiency than the first one?
B.The problem

What is "prefix sum"? Try to imagine that we have n numbers and I want to know the sum of first 1,

the sum of first 2, the sum of first 3... the sum of first n. How to calculate?

กก

C.The idea of program
A kind of repetition  of previous assignment. Basically you need only calculate the sum AFTER your previous 
neighbor finishes it. So, you simply declare n threads and each them just sum up its own value with its previous
neighbor's value. 
Maybe I am still not quite clear about the algorithms of programming assignment2 because I am still not sure about if
the way PA2 is better than what we did in PA1. See below, is it correct about PA2? That is each column will calculate
its "sum" with "previous-hop-column"  (sum+=a[level][j-hop]). You can see the total sum operation is FIVE.
 

           col0       col1              col2                     col3
level 0     a0         a1                  a2                      a3
level 1     a0       a01=a0+a1           a12=a1+a2            a23=a2+a3  
level 2     a0       a01                a012=a0+a12           a0123=a01+a23
 
D.The major functions
Actually I didn't do lot in this edition except that I add the first condition in function "run" so that we 
don't need to initialize each entry every time. And the initialization of double-dimension array is amended
because I don't know the syntax of Java and don't bother to check it!
E.Further improvement
F.File listing
1. Cyclic.java
file name: Cyclic.java
public class Cyclic {
  static int P         = 8;                         // number of workers
  static int logP      = 3;
  static int Pplus1    = 9;                         // 0-indexed array
  static int logPplus1 = 4;                         // lengths

  static Daemon        daemon = new Daemon ();
  static Semaphore[][]  future = new Semaphore[logP][P];
  static int[][]        a      = new int[logP][P];
  static int col;
  static int row;                  // A meaningless variable

  public static void main (String[] args) {

    Worker w[] = new Worker[P];

    for (int j=0; j<future.length; j++)           //I changed it back here
    {
	//future[k]=new Semaphore[P];

	for( int k=0; k<future[j].length; k++ )  //I changed here
	//for( int k=0; k<P; k++ )

	//for (int j=0; j<P; j++)
      	{
	    future[j][k]  = new Semaphore(0);
       	}
    }

    for( int j=0; j<P; j++ ) {
      //test
	//System.out.println("test signal here");
	future[0][3].Signal();
	
	col = daemon.column (j);
      w[col] = new Worker (col+1);
      w[col].start ();
    }

    for( int j=0; j<P; j++ ) {                      // wait for workers
      try { w[j].join (); }                         // to terminate
      catch (InterruptedException exc) { };
    }
    for( int j=1; j<Pplus1; j++ )
      System.out.println ("Sum " + j + " = "+ a[logP-1][j-1]);
    System.out.println ("System terminates normally.");
  }
}

class Daemon {
  private static int[] w = new int[] {3, 6, 5, 7, 4, 2, 1, 0};
  private static int[] d = new int[] {0, 7, 4, 5, 4, 4, 9, 4, 1};

  public int column (int j) {
    return w[j];
  }

  public void interrupt (int j) {
    if ( d[j] > 4 )
      Thread.yield ();
  }
}

class Semaphore {
  private int value;
  Semaphore (int value1) {
    value = value1;
  }

  public synchronized void Wait () {
    while( value <= 0 ) {
      try { wait (); }
      catch (InterruptedException e) { };
    }
    value--;
  }

  public synchronized void Signal () {
    ++value;
    notify ();
  }
}

class Worker extends Thread {
  private int j;
  private int sum;
  private int hop = 1;
  Worker (int col) {
    sum = col;
    j  = col-1;
  }

  public void run () {
    
    //int level;
    System.out.println ("Worker " + (j) + " begins execution.");
    yield ();
    //for (level=0; level<Cyclic.logP; level++) {
    for (int level=0; level<Cyclic.logP; level++) {


      //if ((j <= (Cyclic.P-hop))&&(level<Cyclic.logP-1))
      if (j < (Cyclic.P-hop))//&&(level<Cyclic.logP-1)) //So, we don't need to initialize every entry

      {
        System.out.println ("Worker " + j + " defines a[" + (level) + ","
                           + j +"].");
        Cyclic.a[level][j] = sum;
	//System.out.println("a["+level+"]["+j+"]="+Cyclic.a[level][j]);
	//System.out.println("exactly here before signal "+j);
	Cyclic.future[level][j].Signal();
	//System.out.println("exactly after signal of "+j);

	// ...
      }
      if (j >= hop)
	{
	     //   ...
	//test
	//System.out.println("before wait of "+j);

	Cyclic.future[level][j-hop].Wait();
	    	
        System.out.println ("Worker " + j + " uses    a[" + (level) + ","
                           + (j-hop) +"].");
        sum += Cyclic.a[level][j-hop];
	System.out.println("worker "+(j)+" has sum of "+ sum);
      }
	//test	
	//System.out.println("before interrupt");

      Cyclic.daemon.interrupt (j);
	//test
	//System.out.println("after interrupt");
	
      hop = 2*hop;
    }
   
/*
    if (level==Cyclic.logP -1)
	{
		Cyclic.a[level][j]=sum;
	}
*/
    Cyclic.a[Cyclic.logP-1][j]=sum;  //do I change here?
    System.out.println("Worker " + j + " terminates.");
  }
}
กก


The running result is something like following:

[qingz_hu@alpha PA2] % java Cyclic
Worker 3 begins execution.
Worker 6 begins execution.
Worker 5 begins execution.
Worker 7 begins execution.
Worker 4 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 0 begins execution.
Worker 3 defines a[0,3].
Worker 6 defines a[0,6].
Worker 5 defines a[0,5].
Worker 7 defines a[0,7].
Worker 7 uses a[0,6].
worker 7 has sum of 15
Worker 7 defines a[1,7].
Worker 4 defines a[0,4].
Worker 4 uses a[0,3].
worker 4 has sum of 9
Worker 4 defines a[1,4].
Worker 2 defines a[0,2].
Worker 1 defines a[0,1].
Worker 0 defines a[0,0].
Worker 0 defines a[1,0].
Worker 0 defines a[2,0].
Worker 0 terminates.
Worker 6 uses a[0,5].
worker 6 has sum of 13
Worker 5 uses a[0,4].
worker 5 has sum of 11
Worker 5 defines a[1,5].
Worker 3 uses a[0,2].
worker 3 has sum of 7
Worker 2 uses a[0,1].
worker 2 has sum of 5
Worker 2 defines a[1,2].
Worker 2 uses a[1,0].
worker 2 has sum of 6
Worker 2 defines a[2,2].
Worker 2 terminates.
Worker 1 uses a[0,0].
worker 1 has sum of 3
Worker 6 defines a[1,6].
Worker 6 uses a[1,4].
worker 6 has sum of 22
Worker 7 uses a[1,5].
worker 7 has sum of 26
Worker 7 defines a[2,7].
Worker 3 defines a[1,3].
Worker 4 uses a[1,2].
worker 4 has sum of 14
Worker 4 defines a[2,4].
Worker 4 uses a[2,0].
worker 4 has sum of 15
Worker 4 terminates.
Worker 1 defines a[1,1].
Worker 6 defines a[2,6].
Worker 6 uses a[2,2].
worker 6 has sum of 28
Worker 5 uses a[1,3].
worker 5 has sum of 18
Worker 5 defines a[2,5].
Worker 3 uses a[1,1].
worker 3 has sum of 10
Worker 1 defines a[2,1].
Worker 6 terminates.
Worker 3 defines a[2,3].
Worker 5 uses a[2,1].
worker 5 has sum of 21
Worker 5 terminates.
Worker 1 terminates.
Worker 7 uses a[2,3].
worker 7 has sum of 36
Worker 7 terminates.
Worker 3 terminates.
Sum 1 = 1
Sum 2 = 3
Sum 3 = 6
Sum 4 = 10
Sum 5 = 15
Sum 6 = 21
Sum 7 = 28
Sum 8 = 36
System terminates normally.





                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)