An Experimental Study of Three Dataflow Paradigms in Multithreaded Database Transitive Closure Algorithms on Shared Memory Multiprocessors

This paper describes an experimental study of three dataflow paradigms, namely, no dataflow, pipelined dataflow, and network dataflow, in multithreaded database transitive closure algorithms on shared memory multiprocessors. This study shows that dataflow paradigm directly influences performance parameters such as the amount of interthread communication, how data are partitioned among the threads, whether access to each page of data is exclusive or shared, whether locks are needed for concurrency control, and how calculation termination is detected. The algorithm designed with no dataflow outperforms the algorithms with dataflow. Approximately linear speedup is achieved by the no dataflow algorithm with sufficient workload and primary memory. An exclusive access working set model and a shared access working set model describe the interactions between two or more threads′ working sets when access to each page of data is exclusive or shared among the threads, respectively. These models are experimentally verified.