University of Illinois Urbana-Champaign

Data parallelism with hierarchically tiled objects

Brodman, James C.

Content Files
Brodman_James.pdf

Permalink

https://hdl.handle.net/2142/24316

Description

Title
Data parallelism with hierarchically tiled objects
Author(s)
Brodman, James C.
Issue Date
2011-05-25T14:53:56Z
Director of Research (if dissertation) or Advisor (if thesis)
  • Padua, David A.
  • Garzaran, Maria J.
Doctoral Committee Chair(s)
Padua, David A.
Committee Member(s)
  • Garzaran, Maria J.
  • Cytron, Ron
  • Gropp, William D.
  • Heath, Michael T.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2011-05-25T14:53:56Z
Keyword(s)
  • parallelism
  • parallel programming
  • data parallelism
  • tiling
Abstract
Exploiting parallelism in modern machines increases the di culty of developing applications. Thus, new abstractions are needed that facilitate parallel programming and at the same time allow the programmer to control performance. Tiling is a very important primitive for controlling both parallelism and locality, but many traditional approaches to tiling are only applicable to computations on dense arrays. This thesis makes several contributions, all in the general area of data parallel operators for the programming of multiprocessors and their current most popular incarnation, multicores. It accomplishes this through the development of Ravenna, a library of data parallel operators for shared-memory systems. Ravenna extends previous work on a data type for dense arrays called the Hierarchically Tiled Array, or HTA. Ravenna supports arbitrary data types, enabling programmers to write data parallel computations based on other data types such as sets or graphs. Ravenna provides programmers with several mechanisms for tiling data types. In particular for data structures other than dense arrays, it provides a generalized approach called functional tiling. Functional tiling provides programmers with a separation of concerns between implementing a computation and how to tile it. Functional tiling in this way also acts as a tuning mechanism that allows programmers to tune the performance of their codes by plugging in di erent tiling strategies. This thesis evaluates the programming model of expressing programs as a sequence of higher level data parallel operators through examining several applications from di erent domains written in Ravenna. These applications include simple microbenchmarks used to compare against another shared-memory programming library, a solver for banded linear systems called SPIKE, n-body simulation, clustering, and discrete optimization. The evaluation shows that these programs can be elegantly expressed by the programming model, and that the model's applicability is not limited to computations based on dense arrays. Particularly, it shows that the resulting programs resemble conventional, sequential programs, simplifying programmer e ort and that the available abstractions provided by Ravenna allow programmers to tune in order to obtain good parallel performance.
Graduation Semester
2011-05
Permalink
http://hdl.handle.net/2142/24316
Copyright and License Information
Copyright 2011 James C Brodman

Owning Collections

Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois