Data parallelism with hierarchically tiled objects

Brodman, James C.

Permalink

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

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

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