Reducing synchronization in distributed parallel programs

Miller, Philip B

Permalink

https://hdl.handle.net/2142/95305 Copy

Description

Title

Reducing synchronization in distributed parallel programs

Author(s)

Miller, Philip B

Issue Date

2016-11-04

Director of Research (if dissertation) or Advisor (if thesis)

Kalé, Laxmikant V

Doctoral Committee Chair(s)

Kalé, Laxmikant V

Committee Member(s)

• Gropp, William
• Olson, Luke
• Dubey, Anshu

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• parallel programming
• computational science

Abstract

Developers of scalable libraries and applications for distributed-memory parallel systems face many challenges to attaining high performance. These challenges include communication latency, critical path delay, suboptimal scheduling, load imbalance, and system noise. These challenges are often defined and measured relative to points of broad synchronization in the program’s execution. Given the way in which many algorithms are defined and systems are implemented, gauging the above challenges at synchronization points is not unreasonable. In this thesis, I attempt to demonstrate that in many cases, those synchronization points are themselves the core issue behind these challenges. In some cases, the synchronizing operations cause a program to incur the costs from these challenges. In other cases, the presence of synchronization potentially exacerbates these problems. Through a simple performance model, I demonstrate that making synchronization less frequent can greatly mitigate performance issues. My work and several results in the literature show that many motifs and whole applications can be successfully redesigned to operate with asymptotically less synchronization than their naïve starting points. In exploring these issues, I have identified recurrent patterns across many applications and multiple environments that can guide future efforts more directly toward synchronization-avoiding designs. Thus, I attempt to offer developers the beginnings of a high-level play-book to follow rather than having to rediscover application-specific instances of the patterns.

Graduation Semester

2016-12

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2016 Philip Miller

Owning Collections