PERFORMANCE ESTIMATION AND SCHEDULING FOR PARALLEL PROGRAMS WITH CRITICAL SECTIONS

A fundamental problem in multithreaded parallel programs is the partial serialization that is imposed due to the presence of mutual exclusion variables or critical sections. In this work we investigate a model that considers the threads consisting of an equal number L of functional blocks, where each functional block has the same duration and either accesses a critical section or executes non-critical code. We derived formulas to estimate the average time spent in a critical section in presence of synchronization barrier and in absence of it. We also develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of threads and for any number of critical sections for the case of L = 2. For the general case L > 2, which is NP-complete, we present a competitive heuristic and provide experimental comparisons with the ideal integer linear programming (ILP) formulation.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Campus Only Dissertation

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Year dc:date.available

2017

Author dc:creator

• Dutta, Sourav

Contributors dc:contributor

• Kagaris, Dimitri

• Distributed computing
• Parallel computing
• Scheduling

Repository record dc:identifier

https://opensiuc.lib.siu.edu/dissertations/1353

OAI identifier oai:identifier

oai:opensiuc.lib.siu.edu:dissertations-2357