Implementing global address space in distributed local memories

To parallelise Do-across loop nests on distributed-memory multicomputers, parallelising compilers need to convert the global data arrays in the original sequential programs into local data arrays in local memories of parallel processors. The address translation scheme from the global data array to the local memory should be such that the demand for local memory should be kept as low as possible so the the problem size of the program can scale up with the number of processors. This paper introduces the techniques to achieve that goal, namely: (1) address compression, (2) address folding and (3) memory recycling. Using these techniques in our experiment of Do-across loops on Fujitsu AP1000, we are able to run very large Do-across loop nests with relatively small size local memories of the AP1000 processors