Comparing Performance and Workload Balance of Paralleling Models

Parallel Programming Models

OpenMP

• Historically used for loop-level and regular parallelism through its compiler directives
• From OpenMP 3.0, supports task parallelism

CILK Plus

• Provides language contrasts for both task and data parallelism
• Simple and High level of abstraction
• Scheduling policy provides load balance close to the optimal
• Deprecated in 2018

Thread Building Blocks (TBB)

• Object C++ runtime library
• Contains data structures and algorithms used in parallel programs
• Abstracts the low-level thread interface

Problem Description

BFS (Breadth First Search)

Problem Size Setup : increased number of vertices and set the number of edges as a factor of 12 of the number of vertices.
(reference : Hong, Sungpack & Kim, Sang Kyun & Oguntebi, Tayo & Olukotun, Kunle. (2011). Accelerating CUDA graph algorithms at maximum warp)

Results

Comparing the performance with the increase of number of threads (1 to 8) with OpenMP

--> The increase in the number of threads used leads to better performamce in terms of the total computation time.

Comparing the performance overhead with different scheduling methods (Static, Dynamic, Guided) with OpenMP

--> Dynamic Scheduling had the highest overhead followed by Guided and Static. The overhead in Dynamic Scheduling occures because it checks for remaining tasks after ever iteration. Guided Scheduling also has a overhead because it is a type of Dynamic Scheduling, but it starts with large chunks of task which leads to less number of total chunks than Guided Scheduling.

Comparing the workload balance with different scheduling methods (Static, Dynamic, Guided) with OpenMP

Static

Dynamic

Guided

--> Dynamic Scheduling had the best workload balance followed by Guided Scheduling and then Static Scheduling.

Comparing the performance of baseline module, OpenMP, TBB

(From here, used a different computer enviorment due to small issues on the TBB setup which could have caused some problems)

Evaluation of the workload balance between threads using TBB