Parallelisation

Parallelisation

Implementation

• Used newWorkStealingPool(<no. of cores>) to set ExecutorService in PartialSchedule class.
  • This means threads can 'steal' work from other threads.
    • e.g. If a thread spawns new subtasks, it can't do all at once, so the free thread steals some, decreasing overall computation time.
• Number of cores passed as input to aStarAlgorithm() function.
• This calls chooseExpansionAlgorithm() function, which carries out node expansion.
  • If there's more than one core:
    • An ArrayList containing Callable HashSets of PartialSchedules is used to indicate the function calls to be done on the new threads.
    • Every node's expansion using the expandNewStatesParallel() method is added to the list of tasks.
    • the invokeAll(<tasks>) method is called on the ExecutorService, with starts/executes the tasks on threads from the thread pool.
      • This calls expandNewStatesParallel() on a new task.
    • The result of computation of expansion on each node from each of the threads is stored in a List of Future Hashsets of PartialSchedules.
      • A Future object represents the result of asynchronous computation (i.e. on different threads at different, indeterminate times).
    • A for loop then retrieves the result of asynchronous computation using the get() method, which blocks if no result is available yet.
• Finally shutdown ExecutorService with shutdown().

Implications

• Increased time taken to compute a schedule for smaller graphs, but sped up for large graphs.
  • There is an overhead associated with creating all the threads and maintaining them in the thread pool.
  • Also the get() method to retrieve the result stored in a Future object is blocking if the Future object has not yet been computed.
    • This can increase the total time taken by preventing/delaying the reading of Future objects that are checked after the current one.

Hindsight

• Shouldn't have called newWorkStealingPool() if number of cores was one, as it comes with an overhead.
  • This method will create a thread pool with a single thread, which is unnecessary, considering the calling thread would be the only one used.