Abstract :
We present techniques for compile time analysis of specifications in LACS (A Language for Affine Communication Structures), which has a unified method for specifying parallel assignment, communication and reduction operations. LACS uses convex polyhedra and affine transformations, and this allows tools from linear algebra to be used for the analysis. Given a LACS specification, we first show how the compiler can detect whether it is well formed - free of write conflicts, false broadcasts and reductions. Then we show how the analysis can be used to deduce the exact nature of the communication, such as detection of scatters, gathers, scans (parallel prefixes) and their generalization. The complexity of our analysis is polynomial in the number of dimensions of the arrays in the program, which is constant for practical purposes
Keywords :
computational complexity; linear algebra; parallel languages; polynomials; software tools; specification languages; system monitoring; LACS; affine communication specifications; affine transformations; compile time analysis; complexity; convex polyhedra; false broadcasts; gathers; linear algebra; parallel assignment; parallel prefixes; polynomial; reduction operations; scans; scatters; unified method; write conflicts; Broadcasting; Concurrent computing; Costs; Ear; Libraries; Los Angeles Council; Manufacturing; Parallel machines; Programming profession; Scattering;
