DOcyclical: A Latency-Resistant Cyclic Multi-Threading Approach for Automatic Program Parallelization

Hairong Yu, Guohui Li, Jianjun Li, Lihchyun Shu

Research output: Contribution to journalArticlepeer-review


Chip multiprocessors have been proposed for many years and have become the prevalent architecture for high-performance general-purpose processors. Currently, the search for automatic parallelization techniques that can take full advantage of processor resources is still an active research area. The cyclic multi-threading (CMT) approach, a popular parallelization paradigm, is widely applicable to many applications and delivers good performance scalability. Despite so, its performance could be quite sensitive to fluctuations in communication latencies without substantive operations that prefetch synchronization signals. To address this problem, we propose a novel CMT technique called ${rm DO}- rm cyclical}}$ that employs a priority-based scheme to reduce greatly the frequency of cross-core loop-carried dependences, hence removes considerable amount of communication latency from critical paths of loop executions. Further, it is the priority-based scheme that keeps all processors busy most of time while maintaining processor load balanced. To demonstrate the capacities of $rm DO rm cyclical}}$, we have evaluated it by using the SPEC CPU2006 and StreamIt benchmarks on three real platforms. Experimental results show that our method is much less sensitive to fluctuations in communication latencies, compared with traditional cyclical multi-threading techniques. Besides, $rm DO rm cyclical}}$ outperforms other well-known parallelization methods, including decoupled software pipelines (DSWP), PS-DSWP and HELIX, in terms of speedup by 21-50, 16-27 and 15-25%, respectively, on the three platforms.

Original languageEnglish
Pages (from-to)1155-1173
Number of pages19
JournalComputer Journal
Issue number8
Publication statusPublished - 2016 Aug 1

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


Dive into the research topics of 'DOcyclical: A Latency-Resistant Cyclic Multi-Threading Approach for Automatic Program Parallelization'. Together they form a unique fingerprint.

Cite this