Parallelization Approach - Ormulsoft/Task-Scheduler GitHub Wiki

A* Parallelization

The A* algorithm was parallelized using basic Java threads. The number of threads created is based on the CLI number of cores input. These A* threads concurrently access the same data structures containing the current state space and closed states, and effectively speed up the algorithm.


The AStarParallel class is a parent that invokes the AStarThread computation methods. Hosts the shared state space data structures (open / closed sets).


The AStarThread runs the A* algorithm accessing the shared open / closed sets.

Branch and Bound Parallelization

The Branch and Bound A* algorithm (named DFS in the code) has a parallel implementation using the Fork-Join framework provided by the Java API. The number of cores specified in the CLI is inputted into the thread pool constructor, which invokes an initial DFSTask. Every algorithm recursion generates as a new DFSTask object which and fired on an individual fork thread.


The parent parallelized DFS class initializes the state space and invokes the Fork-Join thread pool on the recursive DFSTasks.


The DFS task is a Fork-Join recursive action, and provides the main algorithm body. It makes recursive calls to itself by instantiating new DFSTasks and invoking them.