A key problem in parallel programming is how data is {\em partitioned}:
divided into subsets that can be operated on in parallel and, in
distributed memory machines, spread across multiple address spaces.

We present a {\em dependent partitioning} framework that allows an
application to concisely describe relationships between partitions.
Applications first establish {\em independent partitions}, which may contain
arbitrary subsets of application data, permitting the expression of
arbitrary application-specific data distributions.
{\em Dependent partitions} are then derived from these using the
{\em dependent partitioning operations} provided by the framework.
By directly capturing inter-partition relationships, our framework
can soundly and precisely reason about programs to perform important
program analyses crucial to ensuring correctness
and achieving good performance.
As an example of the reasoning made possible,
we present a static analysis that
discharges most consistency checks on partitioned data during compilation.

We describe an implementation of our framework within Regent, a language
designed for the Legion programming model. The use of dependent partitioning
constructs results in a 86-96% decrease in the lines of code required to describe
the partitioning,
eliminates many of the expensive dynamic checks required for soundness
by the current Regent partitioning implementation, and speeds up the
computation of partitions by 2.6-12.7X even on a single thread.
Additionally, we show that a distributed implementation incorporated into the the
Legion runtime system allows partitioning of data sets that are too large to
fit on a single node and yields a further 29X speedup of partitioning
operations on 64 nodes.