Loading...
Please wait, while we are loading the content...
Similar Documents
Hyperplane Partitioning : An Approach To Global Data Partitioning For Distributed Memory Machines
| Content Provider | Indian Institute of Science (IISc) |
|---|---|
| Advisor | Srikant, Y. N. |
| Author | Prakash, S. R. |
| Abstract | Automatic Global Data Partitioning for Distributed Memory Machines (DMMs)is a difficult problem. Distributed memory machines are scalable,but since the memory is distributed across processors, the schemeof placement ofdata (arrays) onto local memories of different processors becomecrucial since any communication between processors for non-localdata access is an order of magnitude costlier than access to localmemory. Researchers have given varied solutionsto this problem, most of which work for uniform dependences in loopsand they suggest HPF-like distributions only. For non-uniformdependences the loop was made to run sequentially.In this work, we present a partitioning strategycalled Hyperplane Partitioning which works well withloops with non-uniform dependences also. In this method of partitioning,the iteration spaceis partitioned into as many number of partitions as there arenumber of logical processors, in such a way that the overallinter-processor communication will be minimum. The idea is tolocalize as many as dependences as possible so that overallcommunication both beacuse of non-local data as well asinter-processor synchronizations are reduced.These partitions arethen induced into data spaces of the arrays referenced in the loop.Each processor then runs its part of iteration space keeping the datapartition that it owns locally. Any non-local data access isimplemented by inter-processor communication at run-time.The Hyperplane Partitioning is also extended toa sequence of loops. This is done by first findingBest Local Distribution (BLD) for every loop first andthen finding the best way of grouping different adjacent loops(just for finding the data partition)which gives best global data partition. This sequence ofdistributions/redistributions is found by constructing adata structure called Data Distribution Tree (DDT) and findingthe least cost path from the source to any of the leaf nodesin the DDT. The costs for the edges come from the communicationcost incurred while running a loop with a particular distributionand redistribution to suit the requirement at the next loop.For this a communication cost estimator is developed whichworks well for fewer dimensions. To handle complete programswe use some heuristic to find the best global distributionfor the entire program.Some optimizations like message optimization to reduce the numberof messages sent across processors, time optimizationwhich is done by uniform scheduling across processors, andspace optimization to keep only the part of array spacethat any processor owns onto its local memory, are studied. Hyperplane Partitioning is also implemented using an algorithm forsynchronization to handle non-local memory access as wellas obeying data dependence constraints. The algorithm is alsoproved to be correct. The target machine is IBM-SP2 usingPVM for the message passing library. The performance of the toolon some standard benchmarks (ADI and RHS) and also on someprograms designed by us to show the specific merits of the tool.The results show that the loops which have non-uniform dependencesalso can be run on DMM with good speed-ups. |
| File Size | 937496 |
| File Format | |
| Language | English |
| Publisher | Indian Institute of Science |
| Access Restriction | Authorized |
| Subject Keyword | Computer and Information Science Parallellizing Compiler Automatic Data Partitioning Hyper-plane Partitioning Distributed Memory Machine Electronic Data Processing Multiprogramming Distributed Memory Multiprocessors Distributed Memory Multicomputers |
| Content Type | Text |
| Educational Degree | Doctor of Philosophy (Ph.D.) |
| Resource Type | Thesis |
