SPC: A Model of Parallel Computation

. A new model of parallel computation is presented that provides appropriate cost models for automatic systems parallelization. We demonstrate its utility in automatic optimization for vectorization and provide a reference to more elaborate examples. 1 Introduction In typical compile-time engines, optimization decisions, such as computation or communication pipelining and data distribution, are either hard-coded in terms of heuristic transformation schemes, or are simply left to programmer annotation. At a more generic level, a vast body of work exists on modeling parallel computations with the purpose of choosing between different algorithms or optimizations based on comparing the associated time costs. On the one hand, detailed cost prediction methods exist, ranging in flavor from performance simulation to static analysis [7]. Either the estimates are too unreliable or the computational complexity prohibits their use in automatic optimization. On the other hand, abstract models of p..