Parallel Operators
Principal Investigators: David Padua, María Garzarán
A particularly useful form of disciplined control is provided by data parallel operators: in data-based parallelism, tasks perform the same operation on different components of a pre-existing data ensemble or a simple iteration domain. In the simple case, such as a vector sum, the operations on distinct elements are independent and perform the same amount of work. In more complex cases, the operations may take different amounts of time and may not be all independent: one needs to find and repeatedly schedule an independent subset of operations.
Data parallelism can be encapsulated inside operands defined on aggregates, such as arrays or sets and, hence, can be incorporated into traditional languages in a transparent manner. Second, because parallelism is encapsulated in the data parallel operators, it is possible to modify the implementation of these operators. Portability is achieved by providing optimized versions of the data parallel operators for different platforms including shared and distributed memory multiprocessors, SIMD processors, and combinations of these. The result is that the same code can be executed on different platforms with minimal loss of performance. Finally, data parallel operators are an effective mechanism to encapsulate non-determinism. The possible results of these non-deterministic operations could be identical or just be guaranteed to satisfy some property while differing in significant ways as discussed above. We have extended the traditional array operators of array languages such as APL, Fortran 90, or Matlab by adding tile abstraction and well-defined parallel semantics. We thus obtained a new data type that we call Hierarchically Tiled Arrays (HTAs) which enables the direct manipulation of tiles sequentially or in parallel. This extension facilitates the development of array-based parallel codes that have a high degree of locality and gives programmers the ability to directly control data layout, scheduling strategy, affinity, data distribution, and communication. We are currently developing abstractions that extend data parallel operations to other classes of aggregates such as sets, graphs, or trees to enable the development of highly readable parallel non-numeric programs.
