package edu.rice.hj.example.comp322.assignments.hw1;
import edu.rice.hj.api.HjMetrics;
import edu.rice.hj.api.HjProcedure;
import edu.rice.hj.runtime.config.HjSystemProperty;
import edu.rice.hj.runtime.metrics.AbstractMetricsManager;
import java.util.Random;
import static edu.rice.hj.Module1.*;
/**
*
QuicksortUtil class.
*
* @author Vivek Sarkar (vsarkar@rice.edu)
*/
public class QuicksortUtil {
/**
* Main function, runs the program
*
* @param args - command line arguments to the application
*/
public static void main(final String args[]) {
final int size;
if (args.length > 0) {
size = Integer.parseInt(args[0]);
} else {
size = 1_000;
}
System.out.println("Input Length = " + size);
System.out.println("--------------------\n");
System.out.println("Running SEQUENTIAL: ");
System.out.println("--------------------");
final HjMetrics seqMetrics = kernel(size, (A) -> QuicksortSeq.quicksort(A, 0, size - 1));
System.out.println("Running PARALLEL: ");
System.out.println("--------------------");
final HjMetrics parMetrics = kernel(size, (A) -> QuicksortPar.quicksort(A, 0, size - 1));
final long seqWork = seqMetrics.totalWork();
final long parCpl = parMetrics.criticalPathLength();
final double actualParallelism = (1.0 * seqWork) / parCpl;
System.out.println("====================");
System.out.printf("IDEAL SPEED-UP = %.4f \n", actualParallelism);
}
/**
* Function that runs an instance of quicksort. Can check the program with Various metrics
*
* @param size - how loarge to make the array
* @param sortFunctionCall - class that contains the functions to quicksort the array, in this case either the
* sequential or parallel version
* @return The performance metrics of the run
*/
public static HjMetrics kernel(final int size, final HjProcedure sortFunctionCall) {
final Comparable[] A = QuicksortUtil.generateInput(size);
final HjMetrics[] actualMetrics = {null};
HjSystemProperty.abstractMetrics.set(true);
launchHabaneroApp(() -> {
finish(() -> {
sortFunctionCall.apply(A);
});
actualMetrics[0] = abstractMetrics();
AbstractMetricsManager.dumpStatistics(actualMetrics[0]);
finish(() -> {
if (QuicksortUtil.valid(A)) {
System.out.println("Sorting succeeded\n");
} else {
System.err.println("Sorting FAILED\n");
}
});
});
return actualMetrics[0];
}
/**
* Exchanges two array elements in an array
*
* @param A an array of comparable objects
* @param x the index of an item to be exchanged
* @param y the index of the other item to be exchanged
*/
public static void exchange(final Comparable[] A, final int x, final int y) {
doWork(1);
final Comparable temp = A[x];
A[x] = A[y];
A[y] = temp;
}
/**
* Checks that the array is sorted
*
* @param A The array to check
* @return whether the array is sorted
*/
@SuppressWarnings("unchecked")
public static boolean valid(final Comparable[] A) {
for (int i = 1; i < A.length; i++) {
if (A[i].compareTo(A[i - 1]) < 0) {
return false;
}
}
return true;
}
/**
* Generates a random array of comparable objects
*
* @param size - the size of the array
* @return An array of comparable objects in arbitrary order
*/
protected static Comparable[] generateInput(final int size) {
final Random rand = new Random(size);
final Comparable[] A = new Comparable[size];
for (int i = 0; i < size; i++) {
A[i] = new DataItem(rand.nextInt(10 * size));
}
return A;
}
/**
* A comparable object
*/
public static class DataItem implements Comparable {
private final int data;
/**
* Constructor for a dataItem
*
* @param data - an integer
*/
private DataItem(final int data) {
this.data = data;
}
@Override
public int compareTo(final DataItem other) {
// Every comparison is a unit of work
doWork(1);
return this.data - other.data;
}
}
}