Code Monkey home page Code Monkey logo

paralleling-model-performance-workloadbalance's Introduction

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

image

--> 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

image

image

--> 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

image

Dynamic

image

Guided

image

--> 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) image

Evaluation of the workload balance between threads using TBB

image

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.