Parallel Exploration of an Unknown Random Forest

Conference: ARCS Workshop 2018 - 31th International Conference on Architecture of Computing Systems
04/09/2018 - 04/12/2018 at Braunschweig, Germany

Proceedings: ARCS 2018

Pages: 4Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Authors:
Keller, Joerg; Eitschberger, Patrick (Faculty of Mathematics and Computer Science, FernUniversität in Hagen, 58084 Hagen, Germany)

Abstract:
We investigate how to explore with a parallel machine a random and unknown forest, of which we only know an upper bound on the total size, some leaves to start from, and the roots. The size of the forest is too large to represent it explicitly in the machine’s main memory. Instead for each node, its parent node is given by an oracle, i.e. a piece of code of which no particulars may be known. We present a parallel algorithm, and use experiments to find parameter settings that influence the runtime favorably