page 1  (12 pages)
2to next section

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.

[email protected]

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


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

? work funded by SERC Advanced Fellowship B/89/ITA/220