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 );
    	}

	}
     
}