Is there a fundamental set of rules by which we can design and analyze portable algorithms for locality and/or efficiency? This project continues work towards a model of parallel computation that captures locality for wide classes of parallel computers. Theoretical tools are developed that can be applied to gain a better understanding of the following: (1) Parallel Algorithms --- how to design and analyze architecture independent generic algorithms capable of exploiting abstract-locality for wide classes of parallel models; (2) Calculus of Architectures --- how to develop a calculus that, given such a generic algorithm, identifies necessary and/or sufficient characteristics of the parallel models for which the problem can be solved with prescribed levels of abstract-locality and/or efficiency; (3) Parallel-Performance Limitations --- how to discover those levels of abstract-locality, speedup, and efficiency which cannot be, or are highly unlikely to be, achieved by any such parallel algorithms for a given problem. These tools are tested by applying them to design and analyze portable algorithms, and to prove parallelism limitations, for fundamental combinatorial problems.
