Studying overheads in massively parallel MIN/MAX-tree evaluation
Ranier Feldmann, Peter Mysliwiete, Burkhard Monien · 1994
In this paper we study the overheads arising in our algorithm for distributed evaluation of Min/Max trees.The overheads are classified into search overhead, performance loss, and decrease of work load.Several mechanisms are investigated to cope with these overheads in order to achieve a high performance.We study a combination of local, medium range, and global load distribution strategies that does not only show a good behavior in terms of work load, but also has a positive influence on the search overhead.The efficient use of a virtual shared memorv.that is distributed among the processors, shows also a big 'contribution to the overal~performance of the system.A carefully restricted application of parallelism using an improved version of the Young Brothers Wait Concept (YBWC) leads to a perfect behavior for minimal Min/Max trees and to a quite low search overhead, if well ordered trees are searched.Well ordered trees const itute the most important case in practice, since a couple of move ordering mechanisms are known that achieve a nearly optimal move ordering in many applications.The resulting combination of the methods shows an efficiency better than any previous approach.Experiments carried out using 256 DeBruijn-connected Transputers result in a speedup of 142 even applying restricted timing constraints.With a system consisting of 1024 grid connected Transputers we obtain a speedup of 344.Moreover the algorithm shows a very good scalability, especially using interconnection networks with logarithmic diameter.The experiments have been carried out using a Min/Max search program that incorporates all important state-of-theart search techniques ( ZUGZWANG, current vice world champion in computer chess) and therefore makes sure, that no artificial or simplifying assumptions on the structure of the problem are made.