As seen in our empirical results, the stack-splitting scheme does not work on the larger systems because of its large communication-overhead. The total overhead of a parallel system is given by
It describes the amount of time the processors spend in addition to the
execution time of the sequential algorithm 
.
This overhead can be used in the speedup equation
and the efficiency equation
Kumar and Rao [7] define a measure for the scalability of
parallel systems.
The isoefficiency-function describes the required increase of the
work 
to achieve a constant efficiency 
with increasing system size
.
Because 
, we can derive the following general equation
for the growth rate of :
To compare the scalability of the two work-distribution schemes, we
must determine the overheads of both schemes.
In the stack-splitting scheme, the work must be splitted into 
sized work-packets to get an optimal distribution among
the processors.
When the stack is splitted, the work is divided into two parts,
the smallest of which is at least 
.
For a processor 
with distance 
from processor 
, which
initially holds all the work, the maximum work it can get - due to
the recursive splitting on the way from to - is
.
So must receive at least 
work packets.
This results in a total work transfer count greater than
with 
and 
as the diameter of the network.
With this, we get a lower bound for the overhead of the stack-splitting
scheme in our implementation on the ring:
Kumar and Rao [7] also describe another work-distribution
method for their stack-splitting scheme where the work can be received
from any processor throughout the system (not only neighboring processors).
They derive an upper bound for the isoefficiency function of
.
In our fixed-packet DFS, the communication overhead and the runtime spent in the initial work distribution phase grow only linear with the system size. This results in the following upper bound for the overhead of our fixed-packet DFS:
Figure 8: Isoefficiency functions for the ring
Figure 8 shows isoefficiency functions for the stack-splitting scheme (with both work distribution methods) and our fixed-packet scheme on the ring topology.