CFGReader

Prefix sum

    A. First Edition

    This is programming assignment of comp346.

    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.

    And please see the following which is the PA1 model which only requires THREE sum operations. I agree that in multi-
    processor-situation PA2 has some advantages such that each thread don't have to wait each other at each LEVEL. But the
    total number of sum operation is also a factor when considering the efficiency of algorithms.

              col0       col1                 col2                    col3
    level 0     a0         a1                  a2                       a3
    level 1     a0       a01=a0+a1             a2                       a3
    level 2     a0       a01               a012=a01+a2                  a3
    level 3     a0       a01                 a012                      a0123=a012+a3

    D.The major functions

    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[P];
      static int    a[][]   = new int[2][P];
    //  static int    a[logP]   = new int[P];
    //  static ...
    //  static ...

      public static void main (String[] args) {
        int col;
        Worker w[] = new Worker[P];

        for( int j=0; j<P; j++ )
        {
    	int temp=0;
    	if (j==0)
    	{
    		temp=1;
    	}
    	future[j]  = new Semaphore(temp);
       }
        for( int j=0; j<P; j++ ) {
          col = daemon.column (j);
          w[col] = new Worker (col);
          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=0; j<P; j++ )
       {
           System.out.println ("Sum " + (j+1)+ " = "+a[1][j]);
        }
        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, 4, 4, 4, 4, 4, 4, 4, 4};

      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) {
        j   = col;
        sum = j+1;
      }

      public void run () {
        System.out.println ("Worker " + (j+1) + " begins execution.");
        yield ();

        for (int level=0; level<2; level++)
        {
    	if (level==0)
    	{
          		System.out.println ("Worker " + (j+1) + " defines a[" + level + "," + j +"].");
    		Cyclic.a[level][j] = sum;
    		System.out.println("a["+level+"]["+j+"]="+Cyclic.a[level][j]);
    	}
    	else
    	{
    		if (j>0)
    		{
    			Cyclic.future[j].Wait();
    	        	System.out.println ("Worker " + (j+1) + " uses    a[" + level + ","
                               + j +"].");
    	        	sum += Cyclic.a[level][j-1];
    			//System.out.println("Worker " +(j+1)+ " has sum of " + sum);
    		}

    		Cyclic.a[level][j]=sum;
    		if (j<(Cyclic.P-1))
    		{
    			Cyclic.future[j+1].Signal();
    		}
          	};
    	Cyclic.daemon.interrupt(j);

        };

        System.out.println ("Worker " + (j+1) + " terminates.");
      }
    }

    The running result is something like following:

[qingz_hu@alpha A2] % java Cyclic
Worker 4 begins execution.
Worker 7 begins execution.
Worker 6 begins execution.
Worker 8 begins execution.
Worker 5 begins execution.
Worker 3 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.
Worker 4 defines a[0,3].
a[0][3]=4
Worker 7 defines a[0,6].
a[0][6]=7
Worker 6 defines a[0,5].
a[0][5]=6
Worker 8 defines a[0,7].
a[0][7]=8
Worker 5 defines a[0,4].
a[0][4]=5
Worker 3 defines a[0,2].
a[0][2]=3
Worker 2 defines a[0,1].
a[0][1]=2
Worker 1 defines a[0,0].
a[0][0]=1
Worker 1 terminates.
Worker 2 uses a[1,1].
Worker 2 terminates.
Worker 3 uses a[1,2].
Worker 3 terminates.
Worker 4 uses a[1,3].
Worker 4 terminates.
Worker 5 uses a[1,4].
Worker 5 terminates.
Worker 6 uses a[1,5].
Worker 6 terminates.
Worker 7 uses a[1,6].
Worker 7 terminates.
Worker 8 uses a[1,7].
Worker 8 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.
[qingz_hu@alpha A2] %
กก