<file_sep>package DataStructures;

import java.util.ArrayList;

import edu.princeton.cs.algs4.Digraph;

public class Controller {
	
	// The multithreaded computation
	protected MultithreadedComputation multithreadedComputation;
	
	// Work stealing controller
	protected ControllerStealing workStealingController;
	
	// Arraylist of processors
	ArrayList<Processor> processors;
	
	public Controller(Digraph pG, int numberOfProcessors) {
		this.multithreadedComputation = new MultithreadedComputation(pG,numberOfProcessors);
		this.setWorkStealingController(this.multithreadedComputation);
		processors = new ArrayList<Processor>();
	}
	
	// Beginning of the execution
	public void startExecution() {	
		// Starts each one of the processors
		for(int i=0; i<processors.size(); i++) {
			if(i == 0) {
				workStealingController.start();
				processors.get(i).start();
			}
			else {
				processors.get(i).start();
			}

		}
	}

	public ControllerStealing getWorkStealingController() {
		return workStealingController;
	}

	public void setWorkStealingController(MultithreadedComputation multithreadedComputation) {
		this.workStealingController = new ControllerStealing(multithreadedComputation);  
	}
	
	public void setProcessors(ArrayList<Processor> processors) {
		this.processors = processors;
	}
}
<file_sep># Evaluation of Work Stealing Algorithms

This repository contains a Benchmark for the evaluations of different work stealing algorithms.
Currently, the system can supports
  - FIFO
  - LIFO
  - Priorityes (developped for this work)

For each algorithm we execute 30 Iterations with a varying number of cores (1..96).
Our algorithm is tested on generated task DAGs of sizes 50..1600 with a varying density in the set {0.2, 0.5, 0.8} for each iteration and number of cores combination. The results of benchmarks are summarized at our [online webpage](https://flaglab.github.io/WorkStealingAlgorithms/)
<file_sep>package api;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;
import java.util.Hashtable;
import java.util.stream.IntStream;

public class ResultsParser {

	public static void main(String[] args) throws IOException {
		//LENGTH,num
		//VERTEX,num
		//algorithm,tasks,iteration,thread,tasks,time
		String baseDir = System.getProperty("user.dir");
		baseDir = baseDir.substring(0, baseDir.lastIndexOf("/"));
		int[] cores = {10, 16, 24, 48, 90};
		for(int i : cores) {
			BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(baseDir + "out_"+i+".csv"), StandardCharsets.UTF_8));
			//Iterations times
			PrintWriter prioritiesTimes = new PrintWriter(new FileWriter(baseDir + "/priorities_times.csv"));
			PrintWriter fifoTimes = new PrintWriter(new FileWriter(baseDir + "/fifo_times.csv"));
			PrintWriter lifoTimes = new PrintWriter(new FileWriter(baseDir + "/lifo_times.csv"));
			PrintWriter priorities;
			PrintWriter fifo;
			PrintWriter lifo;
			boolean length = false;

			String line = "";
			int size = 0;
			int iterationCount = 0;
			double priorityTime = 0.0;
			Hashtable<Integer, double[]> priorityData = new Hashtable<Integer, double[]>();
			while((line=br.readLine())!=null && line.length()!=0) {
				String[] parts = line.split(",");
				if(!length && parts[0].equals("LENGTH")) {
					size = Integer.parseInt(parts[1]);
					fifo = new PrintWriter(new FileWriter(baseDir + "fifo_" + size + ".csv"));
					lifo = new PrintWriter(new FileWriter(baseDir + "lifo_" + size + ".csv"));
					priorities = new PrintWriter(new FileWriter(baseDir + "priorities_" + size + ".csv"));
					//prioritiesTimes.println(size + "," + priorityTime / iterationCount);
					iterationCount = 0;
					size = 0;
					length = true;
				} else if(parts[0].equals("VERTEX")) {
					iterationCount += Double.parseDouble(parts[1]);
					iterationCount ++;
				} else {
					//parse per method - iteration - p.id and average
					if(parts[0].equals("PRIO")) {
						int tasks = Integer.parseInt(parts[1]);
						double[] values = priorityData.get(tasks);
						if(values == null) 
							priorityData.put(tasks, IntStream.rangeClosed(0,5).mapToDouble(it -> 0.0).toArray());
						else {
							values[Integer.parseInt(parts[3])] +=  Double.parseDouble(parts[5]);
							priorityData.replace(100, values);
						}
					} else if(parts[0].equals("FIFO")) {

					} else { //LIFO

					}
					iterationCount ++;
				}			
			}
		}
	}
}
<file_sep>package DataStructures.priorities;

import java.util.ArrayList;

import DataStructures.MultithreadedComputation;
import DataStructures.graph.LongestPathDAG;
import edu.princeton.cs.algs4.Digraph;

public class PriorityMultithreadedComputation extends MultithreadedComputation {
	
	// Object that will allow us to calculate the priority for each vertex in the computation
	private LongestPathDAG longestPath;
	
	// Array that stores the priority in the computation of each vertex;
	private ArrayList<Integer> priorityVertices;

	public PriorityMultithreadedComputation(Digraph pG, int pNumberOfProcessors) {
		super(pG, pNumberOfProcessors);
		longestPath = new LongestPathDAG(this.getG());
		priorityVertices = new ArrayList<Integer>();
		
		long startTime = System.currentTimeMillis();
		
		//Fill each priorityVertices array entry with its corresponding vertex priority
		longestPath.calculateLongestPathLengthFromVertex(0);
		priorityVertices = longestPath.getPriorityVerticesDAG();
		
		long executionTime = System.currentTimeMillis()-startTime;
		System.out.println("VERTEX," + executionTime);
	}
	
	public ArrayList<Integer> getPriorityVertices() {
		return this.priorityVertices;
	}
}
<file_sep>package DataStructures.priorities;

import DataStructures.Controller;
import edu.princeton.cs.algs4.Digraph;

public class PriorityController extends Controller {
	
	private  PriorityMultithreadedComputation multithreadedComputation;
	
	public PriorityController(Digraph graph, int numberOfProcessors, int totalTasks, int iteration) {
		super(graph, numberOfProcessors);
		//Create and store the processors
		this.multithreadedComputation = new PriorityMultithreadedComputation(graph,numberOfProcessors); 
		this.setWorkStealingController(this.multithreadedComputation);
		for (int i = 0 ; i < numberOfProcessors ; i++)
			this.workStealingController.addProcessor(new PriorityProcessor(this.multithreadedComputation,i,totalTasks,iteration));
		this.setProcessors(this.workStealingController.getProcessors());
	}
}
