Conflict Resolution In Speculative Pipeline-parallel Model On CMP

With multi-core processors becoming more popular,how to extract parallelism from a legacy sequential program to improve performance on these architectures has become urgent.One promising automatic parallelization technique is rising by converting sequential programs into multi-threaded versions with use of speculative pipeline-parallel techniques within an automatic compiler.All of the related approaches always make an optimistic assumption that the speculatively-removed loop-carried dependences are either absent or rarely manifest themselves at runtime.Unfortunately,it is observed that in some applications in order to build one load balanced pipeline taking advantage of the above assumption removed some loop-carried dependences speculatively,but they manifested themselves frequently in the actual execution.In this case,this type of dependence(defined as “paradox” dependence)makes previous automatic parallelization techniques not able to speed up these sequential programs because data conflict caused by such dependences will cause high frequent recovery.To solve the existence problem of such “paradox” dependences in sequential programs,conflict resolution in speculative pipeline-parallel model on CMP is presented.This paper aims at making judicious use of the conflict resolution proposed to reduce high misspeculation rate caused by “paradox” dependences when using speculative pipeline-parallel techniques to speed up sequential programs on CMP.The significance of it lies in that it not only continues the advantage of speculative pipeline-parallel techniques for more thread-level parallelism from sequential progrmas but also expands the applicability of these techniques.The conflict resolution makes full use of the philosophy behind the speculative pipeline-parallel model to locate “paradox” dependences in programs by dynamic detection on the frequency of the conflict;calculate read and write access distance involved in such dependences dynamically by executing instrument code when one “paradox” dependence has been determinated;take corresponding code optimization strategy according to the ratio of read and write access distance as far as possible to meet the standard of safe access distance;and provides an efficient data forwarding mechanism to ensure the hazard data exposed to the subsequent readers in time between different cores.The experiment results show that the conflict resolution can reduce the misspeculation rate by around 20% on average across all used benchmarks.