Study the impact of using Lock-free buffer to communicate the DOACROSS loop iterations

Abstract EN

Communication dependency overhead becomes the biggest obstacle that facing the parallelizing loops containing loop-carried dependencies such us DOACROSS loop.

Although of a substantial researches had been devoted to this field, the problem still far from solved.

This work introduces a FastForward circular lock-free queue algorithm to communicate the dependency between DOACROSS loop iterations.

Instead of giving each iteration of DOACROSS loop to thread as in the original methods, group of iterations will be given to each thread.

So to ensure correct results, the dependence between threads must be respected and for parallelism to be effective, the overhead on core-to-core communication must be as low as possible.

Experimental results are implemented on Intel Core i7 processor that has 4GB RAM running SUSE operating system show performance improvements of the proposed DOACROSS approach.

An evaluation of this technique on four programs with a range of dependence patterns lead to ≈ 0.9 speed-