Pipelined functional tree accesses and updates: Scheduling, synchronization, caching and coherence

摘要

This paper is an exploration of the parallel graph reduction approach to parallel functional programming, illustrated by a particular example: pipelined, dynamically-scheduled imple- mentation of search, updates and read-modify-modify-write transactions on an in-store binary search tree. We use program transformation, execution-driven simulation and analytical modelling to expose the maximum potential parallelism, the minimum communication and synchronisa- tion overheads, and to control the overall space requirement.