Stream Processing Approach on the Fuce System for parallelizing Nested Loops with Data Dependency

摘要

It is widely known that nested loops with data dependency can be parallelized by transforming the original loops by techniques such as loop skewing, loop interchange (so called software pipelining and/or wavefront method). However, these loop transformation techniques need to solve the equation of simultaneous inequalities and modify loop index variables by "human". These procedures require complicated formalities to programmers. We have developed a much simpler method to parallelize nested loops with data dependency, which is an straightforward application of asynchronous handshaking stream programming on the continuation-based multithreading.In this paper, we discuss our new approach in detail and show the enough performance enhancements can be exploited by our approach by evaluating the parallelized version of nested loop programs, on the Fuce runtime system on a commodity machine.