Fork Join

These are simple programs that might help one understand how to use java.util.concurrent.RecursiveAction which uses the ForkJoin framework. I am trying to analyze how this framework employs the work stealing algorithm so that the programs use multiple cores more efficiently.

The innards of this algorithm and its variataions do not seem to be so simple and I did not find any cheap tools that will help me understand how the cores are more efficiently used. I am looking for a way to visualize this algorithm in a simpler way. JavaFX looks appealing but the problem is that the actual algorithm should drive the UI instead of a visually appealing show that does not reveal the way the code behaves in a certain multi-core environment. So I am trying to manipulate the UI exactly when a task is stolen but how this type of code interacts with the framework is not known at this time.

MergeSort

 

public class SortTask {
	
    long[] aux = new long[ 40 ];

    static long[] list = new long[ 40 ];

    private void mergeSort( int lo, int hi){
 
    	if( lo < hi ){
    		
        	int mid = ( lo + hi )/ 2;
        	
        	mergeSort( lo, mid );
        	
        	mergeSort( mid + 1, hi );
        	
        	merge( lo, mid, hi );
    	}
    	
    }
    
	private void merge( int lo,
    		            int mid,
    		            int hi ){
    	 int i = lo, j = mid + 1;
    	 
    	 int k = lo;
    	 
    	 for( ; k <= hi ; k ++ ){
    		aux[ k ] = list[ k ];
    	 }
    	 k = lo;
    	 while( i <= mid && j <= hi){
    		 if( aux[i] < aux[j]){
    			 list[k++] = aux[i++];
    		 }else{
    			 list[k++] = aux[j++];
    		 }
    	 }
    	 while( i <= mid ){
			 list[k++] = aux[i++];
    	 }
     }
     
     private static long[] getArray(){
   	 
    	 Random random = new Random();
    	 
    	 for( int i = 0 ; i < list.length ; i ++ ){
    		 list[ i ] = random.nextInt(1000);
    	 }
    	 
    	 return list;
    	 
     }
     
     private void printArray(){
    	 for( int i = 0 ; i < list.length ; i ++ ){
    		 System.out.printf( "%2s ", list[ i ]);
    	 }
   		 System.out.printf( "%n");
     }
     
     public  static void main( String... argv ){
    	 list = SortTask.getArray();
    	 SortTask st = new SortTask();
    	 st.printArray();
    	 st.mergeSort( 0, list.length - 1 );
    	 st.printArray();
     }
     
}

MergeSort using ForkJoin

 

 
public class ForkJoinSortTask extends RecursiveAction{
	
	private static final long serialVersionUID = 1070860898589424509L;

	long[] aux = new long[ 40 ];

	private int lo;

	private int hi;

    long[] list = new long[ 40 ];

    public ForkJoinSortTask( long[] list, int lo, int hi ){
    	this.list = list;
    	this.lo = lo;
    	this.hi = hi;
    }
    
	public ForkJoinSortTask() {
   	    this.list = getArray();
    	this.lo = 0;
    	this.hi = list.length - 1;
	}

  
	private void merge( int lo,
    		            int mid,
    		            int hi ){
    	 int i = lo, j = mid + 1;
    	 
    	 int k = lo;
    	 
    	 for( ; k <= hi ; k ++ ){
    		aux[ k ] = list[ k ];
    	 }
    	 k = lo;
    	 while( i <= mid && j <= hi){
    		 if( aux[i] < aux[j]){
    			 list[k++] = aux[i++];
    		 }else{
    			 list[k++] = aux[j++];
    		 }
    	 }
    	 while( i <= mid ){
			 list[k++] = aux[i++];
    	 }
     }
     
     private long[] getArray(){
   	 
    	 Random random = new Random();
    	 
    	 for( int i = 0 ; i < list.length ; i ++ ){
    		 list[ i ] = random.nextInt(1000);
    	 }
    	 
    	 return list;
    	 
     }
     
     private void printArray(){
    	 for( int i = 0 ; i < list.length ; i ++ ){
    		 System.out.printf( "%2s ", list[ i ]);
    	 }
   		 System.out.printf( "%n");
     }
     
     public  static void main( String... argv ){
    	 ForkJoinSortTask st = new ForkJoinSortTask();
    	 st.printArray();
    	 ForkJoinPool fjp = new ForkJoinPool();
    	 fjp.invoke( st );
    	 st.printArray();
     }

	@Override
	protected void compute() {

    	if( lo < hi ){
    		
        	int mid = ( lo + hi )/ 2;
        	
            invokeAll( new ForkJoinSortTask(list, lo, mid),
                       new ForkJoinSortTask(list, mid + 1, hi));
        	
        	merge( lo, mid, hi );
    	}

	}
     
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: