| At time of publication: | University of York, UK. |
| Contact | alan@hcibook.com |
Download full paper - compressed postscript (40K) or Adobe PDF (65K).
Full reference:
A. J. Dix (1992).
Allocation of Multiple Processors to Lazy Boolean Function Trees - Justification of the Magic Number 2/3.
YCS 174, Department of Computer Science, University of York.
http://www.hcibook.com/alan/papers/two-thirds-92/
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.
Keywords: parallel evaluation, VLSI simulation, VLSI design.