Combining compile and run-time dependency resolution in Data-Driven Multithreading

Abstract

Threaded Data-Flow systems schedule threads based on data-availability i.e. a thread can be scheduled for execution only after all its inputs have been generated by its producer threads. This requires that all data dependencies are resolved. Two approaches are typically utilized for resolving the dependencies: •Compile-time: which is efficient but cannot handle programs with run-time determined dependencies • Run-time: which can handle run-time determined dependencies but incurs run-time overheads even when part of the dependencies can be determined at compile-time In this work, we combine the two approaches. The compiler (or the programmer) attempts to resolve all the dependencies and encodes them into the Data-Flow dependency graph. For any unresolved dependency, it generates a helper thread that resolves the dependency at run-time and updates the graph accordingly with the help of I-Structures. Thus, it gains the benefits of both compile-time and run-time dependency resolution. This can be also utilized to improve the programmability, in the case where the programmer has to manually resolve datadependencies, by deferring part of the dependency resolution to run-time. In this paper we describe our approach and present the implementation and evaluation on the Data-Driven Multithreading Virtual Machine (DDM-VM). The evaluation demonstrates that the overhead of the run-time dependency resolution can increase the execution time for small thread granularities, but it can be mostly eliminated when the thread granularity increases. © 2011 IEEE.