  We study the problem of scheduling an arbitrary computational DAG on a fixed
number of processors while minimizing the makespan. While previous works have
mostly studied this problem in fairly restricted models, we define and analyze
DAG scheduling in the Bulk Synchronous Parallel (BSP) model, which is a
well-established parallel computing model that captures the communication cost
between processors much more accurately. We provide a taxonomy of simpler
scheduling models that can be understood as variants or special cases of BSP,
and discuss how the properties and optimum cost of these models relate to BSP.
This essentially allows us to dissect the different building blocks of the BSP
model, and gain insight into how these influence the scheduling problem.
  We then analyze the hardness of DAG scheduling in BSP in detail. We show that
the problem is solvable in polynomial time for some very simple classes of
DAGs, but it is already NP-hard for in-trees or DAGs of height 2. We also prove
that in general DAGs, the problem is APX-hard: it cannot be approximated to a
$(1+\epsilon)$-factor in polynomial time for some specific $\epsilon>0$. We
then separately study the subproblem of scheduling communication steps, and we
show that the NP-hardness of this problem depends on the problem parameters and
the communication rules within the BSP model. Finally, we present and analyze a
natural formulation of our scheduling task as an Integer Linear Program.
