Parallelization of Recursive Preorder Traversal Based on Building and Winding Call Stacks

This paper proposes a method to parallelize the recursive preorder traversal algorithm on an ordered general tree. The method is based on building and winding call stacks, which are achieved by statically prepared initializing and terminating functions. In the method, an ordered general tree is split in a manner in which the nodes of a consecutive preorder range are assigned to a worker thread. At that time, all worker threads are aligned in order of the worker IDs, and an earlier worker thread is assigned an earlier preorder range. Each node is processed exactly once by only one worker thread. This paper also provides a set of proofs to show that each worker thread can start/stop its recursive preorder traversal from/at an intended place in a tree. The method is sufficiently general to be applicable to existing applications that adopt the recursive preorder traversal such as Protocol Buffers, which is a type of serializer/deserializer tool. The evaluation results show that the serialization result writing time of the parallelized Protocol Buffers is 1.78 fold shorter than that for normal Protocol Buffers when serializing 40,320 double values using 5 worker threads.