Data parallelism with hierarchically tiled objects

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Brodman, James C.

Contributors dc:contributor

• Padua, David A.
• Garzaran, Maria J.
• Cytron, Ron
• Gropp, William D.
• Heath, Michael T.

• parallelism
• parallel programming
• data parallelism
• tiling

Statement dc:rights

• Copyright 2011 James C Brodman

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24316