Exploiting Locality with Qthreads for Portable Parallel Performance

Doctoral Dissertation


Large scale hardware-supported multithreading, an attractive means of increasing computational power, benefits significantly from low per-thread costs. Hardware support for lightweight threads and synchronization is a developing area of research. Shared memory parallel systems are flourishing, but with a wide variety of architectures, synchronization mechanisms, and topologies. Portable abstractions are needed that provide basic lightweight thread control, synchronization primitives, and topology information to enable scalable application development on the full range of shared memory parallel system designs. Additionally, programmers need to be able to understand, analyze, tune, and troubleshoot the resulting large scale multithreaded programs. This thesis discusses the implementation of scalable software for massively parallel computers based on locality-aware lightweight threads and lightweight synchronization. First, this thesis presents an example lightweight threading API, the qthread library, that supports the necessary features in a portable manner. This exposes the need for a structural understanding of parallel applications. ThreadScope, a tool and visual language for structural analysis of multithreaded parallel programs is presented to address this need. A strong understanding of algorithm structure combined with a locality-aware portable threading library leads to the development of three distributed data structures Ì¢âÂ' a memory pool, an array, and a queue Ì¢âÂ' that adapt to system topology at runtime. Such adaptive data structures enable the development of three example adaptive computational templates Ì¢âÂ' sorting, all-pairs, and wavefront Ì¢âÂ' that hide the parallelism details without sacrificing scalable performance.


Attribute NameValues
  • etd-11062009-151325

Author Kyle Bruce Wheeler
Advisor Dr. Peter Bauer
Contributor Dr. Doug Thain, Committee Member
Contributor Dr. Peter Kogge, Committee Member
Contributor Dr. Christian Poellabauer, Committee Member
Contributor Dr. Peter Bauer, Committee Member
Contributor Dr. Gregory Madey, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Computer Science and Engineering
Degree Name Doctor of Philosophy
Defense Date
  • 2009-09-28

Submission Date 2009-11-06
  • United States of America

  • state

  • lightweight

  • data structures

  • adaptive

  • memory

  • topology

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units

Digital Object Identifier


This DOI is the best way to cite this doctoral dissertation.


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.