|  | |||||||||
Allocation of multiple processors
to lazy boolean function trees
? justification of the magic number 2/3
Alan Dix?
Computer Science Department
University of York, York, YO1 5DD, U.K.
First draft May 1991
Revised April 1992
In simulations of lazy evaluation of boolean formulae, Dunne, Gittings and Leng found that parallel
evaluation by two processors achieved a speed-up of 2/3 compared to single processor evaluation.
The reason that this factor was only 2/3 rather than a half was because the function nodes used for the
simulation were all `and' type functions, and hence sometimes the evaluation by the second processor
proved unnecessary. This paper is intended to provide a justification for this `magic number' of 2/3,
by proving that it is exactly the speed-up obtained for pure balanced trees. A similar speed-up figure
result is obtained for non-binary balanced trees and an equivalent speed-up figure for multiple
processors is also given. Unbalanced trees have worse behaviour and by way of example the speed-
up figure for an AVL tree is given (0.6952). Finally, numerical solutions are given for the case of
arbitrary random binary trees. Since this report was first written Dunne et al. have proved
analytically that the 2/3 figure does indeed hold for random trees generated by a reasonable
distribution.
1. Background
This report springs from work by Dunne, Gittings and Leng on the computer-aided design of VLSI logic
circuits.1, 2 They are in interested in efficient parallel evaluation strategies for simulation of Boolean
expression trees. Demand-driven lazy evaluation of such trees means that, for instance, at `and' nodes, if
the first evaluated sub-tree yields `false' the other need not be evaluated. In general, this will mean that
parallel evaluation will not achieve 100% process utilisation. At the Seventh British Colloquium on
Theoretical Computer Science in March 1991, Chris Gittings presented their simulation results which
suggested a speed-up figure of 2/3 for two processors on random trees with `and' type nodes.3
This magic number 2/3 arose out of empirical studies of randomly generated trees. Is this speed-up factor
for two processors exact? If so is it a feature of the particular random trees chosen, or is it more general?
Further, what is the generalisation to three or more processors? The following report is an attempt to
analytically justify the figure of 2/3 and partially generalise the result. I say `justify' as the report primarily
deals with deterministic rather than random trees. Since this report was originally written Dunne et al. have
produced a more complete analytic treatment of random trees both proving the speed-up of 2/3 can be
achieved, on average, for `and' type trees and giving similar figures for formula trees which also include
`xor' type nodes.4
hhhhhhhhhhhhhhhhhh
? work funded by SERC Advanced Fellowship B/89/ITA/220