TY - JOUR T1 - An integrated runtime and compile-time approach for parallelizing structured and block structured applications JF - IEEE Transactions on Parallel and Distributed Systems Y1 - 1995 A1 - Agrawal,G. A1 - Sussman, Alan A1 - Saltz, J. KW - Bandwidth KW - block structured applications KW - block structured codes KW - compile-time approach KW - compiling applications KW - data access patterns KW - Data analysis KW - Delay KW - distributed memory machines KW - distributed memory systems KW - FORTRAN KW - Fortran 90D/HPF compiler KW - High performance computing KW - HPF-like parallel programming languages KW - integrated runtime approach KW - irregularly coupled regular mesh problems KW - multigrid code KW - Navier-Stokes solver template KW - Parallel machines KW - parallel programming KW - Pattern analysis KW - performance evaluation KW - program compilers KW - Program processors KW - Runtime library KW - Uninterruptible power systems AB - In compiling applications for distributed memory machines, runtime analysis is required when data to be communicated cannot be determined at compile-time. One such class of applications requiring runtime analysis is block structured codes. These codes employ multiple structured meshes, which may be nested (for multigrid codes) and/or irregularly coupled (called multiblock or irregularly coupled regular mesh problems). In this paper, we present runtime and compile-time analysis for compiling such applications on distributed memory parallel machines in an efficient and machine-independent fashion. We have designed and implemented a runtime library which supports the runtime analysis required. The library is currently implemented on several different systems. We have also developed compiler analysis for determining data access patterns at compile time and inserting calls to the appropriate runtime routines. Our methods can be used by compilers for HPF-like parallel programming languages in compiling codes in which data distribution, loop bounds and/or strides are unknown at compile-time. To demonstrate the efficacy of our approach, we have implemented our compiler analysis in the Fortran 90D/HPF compiler developed at Syracuse University. We have experimented with a multi-bloc Navier-Stokes solver template and a multigrid code. Our experimental results show that our primitives have low runtime communication overheads and the compiler parallelized codes perform within 20% of the codes parallelized by manually inserting calls to the runtime library VL - 6 SN - 1045-9219 CP - 7 M3 - 10.1109/71.395403 ER -