  We present a new parallel model of computation suitable for spatial
architectures, for which the energy used for communication heavily depends on
the distance of the communicating processors. In our model, processors have
locations on a conceptual two-dimensional grid, and their distance therein
determines their communication cost. In particular, we introduce the energy
cost of a spatial computation, which measures the total distance traveled by
all messages, and study the depth of communication, which measures the largest
number of hops of a chain of messages. We show matching energy lower- and upper
bounds for many foundational problems, including sorting, median selection, and
matrix multiplication. Our model does not depend on any parameters other than
the input shape and size, simplifying algorithm analysis. We also show how to
simulate PRAM algorithms in our model and how to obtain results for a more
complex model that introduces the size of the local memories of the processors
as a parameter.
