CRbS:A Code Reordering Based Speeding-up Method of Irregular Loops on CMP

CMP (chip multiprocessor) used to improve throughput and speed up multithreaded applications is becoming more and more commonplace. However, it is difficult for compilers to automatically parallelize irregular single-threaded applications which have complex data dependence caused by non-linear subscripts, pointers, or function calls within code sections. Loops iterations can be easily split into threads and they account for a large fraction of the program execution time for many classes of applications while there are so many data dependences between iterations for a loop. Fortunately, for some loops the inter-thread signaling needed for synchronization can be minimized both by code optimization. In order to reduce the communication cost between the iterations, this paper proposes a code reordering method to speeding up the irregular loops. In this method, we adopt code reordering to cutting down the data-dependence by reordering the key codes that may cause data-dependence. The experimental results shows that, compared to the P-Slice method, we can achieve a little better performance only based on the code reordering method and significant performance improvement about 10.6% when combine the two methods.