Efficient Index Set Generation for Compiling HPF Array Statements on Distributed-Memory Machines
✍ Scribed by S.D. Kaushik; C.-H. Huang; P. Sadayappan
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 316 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
programming environment which allows annotation of single address space programs with distribution directives specifying the mapping of arrays to processors of a distributed-memory machine. The compiler is responsible for partitioning the arrays and generating SPMD messagepassing node code for the annotated program. Array statements are used to express data parallelism in these languages. Consider the array statement B(l 2 : u 2 : s 2 ) ϭ F (A(l 1 : u 1 : s 1 )).
(1)
The array section A(l 1 :
Under the owner-computes rule, the processor on which B(l 2 ϩ i ء s 2 ) is located performs the computation and the assignment B(l 2 ϩ i ء s 2 ) ϭ F (A(l 1 ϩ i ء s 1 )). Since the computation performed on a processor may involve array elements resident on other processors, all nonlocal data is fetched into temporary arrays in a processor's local memory using interprocessor communication. Thus a processor must determine which elements of B(l 2 : u s : s 2 ) are allocated to it, the order in which these elements are located in its local memory, the processors from which it must receive nonlocal data, and the location of the nonlocal data in its local memory. Efficient methods for enumerating the following index sets for a processor p reduces the indexing overhead for executing array statements on a distributed-memory machine.
• Local index set of p (LIndex(p)): set of local indices on p of the array elements of B whose values will be evaluated by the array statement.
• Send data index set of p to processor q (DSend(p,q)):
set of local indices of the array elements of array A, resident on p but needed by processor q.
• Receive data index set of p from processor q(DRecv(p,q)): set of local indices of the array elements of array A needed by p but resident on q.
• Send processor set of p (PSend(p)): set of processors to which p has to send data.
• Receive processor set of p (PRecv(p)): set of processors from which p has to receive data.