  Models of parallel processing systems typically assume that one has $l$
workers and jobs are split into an equal number of $k=l$ tasks. Splitting jobs
into $k > l$ smaller tasks, i.e. using ``tiny tasks'', can yield performance
and stability improvements because it reduces the variance in the amount of
work assigned to each worker, but as $k$ increases, the overhead involved in
scheduling and managing the tasks begins to overtake the performance benefit.
We perform extensive experiments on the effects of task granularity on an
Apache Spark cluster, and based on these, developed a four-parameter model for
task and job overhead that, in simulation, produces sojourn time distributions
that match those of the real system. We also present analytical results which
illustrate how using tiny tasks improves the stability region of split-merge
systems, and analytical bounds on the sojourn and waiting time distributions of
both split-merge and single-queue fork-join systems with tiny tasks. Finally we
combine the overhead model with the analytical models to produce an analytical
approximation to the sojourn and waiting time distributions of systems with
tiny tasks which include overhead. Though no longer strict analytical bounds,
these approximations matched the Spark experimental results very well in both
the split-merge and fork-join cases.
