A comparative study of shared memory parallelism on regular and irregular data structures using OpenMP and Galois

Task and/or data parallelism can be exploited in most applications on today's multi-core processors. However, inefficient data organization, data dependencies, and hardware constraints limit scalable parallelization of these applications. In this thesis, performance and the impact of some optimizations is compared and evaluated for simple tasks using two parallel frameworks, OpenMP and Galois. Additionally, their performance on three real life applications, High Accuracy Relativistic Magnetohydrodynamics (HARM) which operates on a grid data structure; Delaunay Triangulation, which refines a triangulated mesh; and Dynamic Fracture Propagation, which operates on a triangulated mesh with adaptive refinement; is evaluated. It is found that OpenMP is a simple yet powerful tool for parallelization of most regular applications and workloads. Galois, which is specially designed for irregular data patterns, performs well for graph like structures. However, neither of them are well suited for all tasks and other frameworks must be explored to find one that is simple to use and yet powerful for all possible applications.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2016

Author dc:creator

• Pothukuchi, Sweta Yamini

Contributors dc:contributor

• Padua, David

• parallel
• OpenMP
• Galois

Statement dc:rights

• Copyright 2015 Sweta Yamini Pothukuchi

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/88935

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/88935