Analysis of affine communication specifications

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