Data parallelism with hierarchically tiled objects

parallelism;parallel programming;data parallelism;tiling

Brodman, James C.

关键词: parallelism;    parallel programming;    data parallelism;    tiling;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/24316/Brodman_James.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Exploiting parallelism in modern machines increases the di culty of developing applications.Thus, new abstractions are needed that facilitate parallel programming and at the sametime allow the programmer to control performance. Tiling is a very important primitivefor controlling both parallelism and locality, but many traditional approaches to tiling areonly applicable to computations on dense arrays. This thesis makes several contributions,all in the general area of data parallel operators for the programming of multiprocessorsand their current most popular incarnation, multicores. It accomplishes this through thedevelopment 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 HierarchicallyTiled Array, or HTA.Ravenna supports arbitrary data types, enabling programmers to write data parallel computationsbased on other data types such as sets or graphs. Ravenna provides programmerswith several mechanisms for tiling data types. In particular for data structures other thandense arrays, it provides a generalized approach called functional tiling. Functional tilingprovides programmers with a separation of concerns between implementing a computationand how to tile it. Functional tiling in this way also acts as a tuning mechanism that allowsprogrammers 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 ofhigher level data parallel operators through examining several applications from di erentdomains written in Ravenna. These applications include simple microbenchmarks used to compare against another shared-memory programming library, a solver for banded linearsystems called SPIKE, n-body simulation, clustering, and discrete optimization. The evaluationshows that these programs can be elegantly expressed by the programming model, andthat 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 allowprogrammers to tune in order to obtain good parallel performance.