Iterational retiming with partitioning: Loop scheduling with complete memory latency hiding

Chun Jason Xue, Jingtong Hu, Zili Shao, Edwin Sha

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


The widening gap between processor and memory performance is the main bottleneck for modern computer systems to achieve high processor utilization. To hide memory latency, a variety of techniques have been proposedfrom intermediate fast memories (caches) to various prefetching and memory management techniques. In this article, we propose a new loop scheduling with memory management technique, Iterational Retiming with Partitioning (IRP), that can completely hide memory latencies for applications with multidimensional loops on architectures like CELL processor. In IRP, the iteration space is first partitioned carefully. Then a two-part schedule, consisting of processor and memory parts, is produced such that the execution time of the memory part never exceeds the execution time of the processor part. These two parts are executed simultaneously and complete memory latency hiding is reached. In this article, we prove that such optimal two-part schedule can always be achieved given the right partition size and shape. Experiments on DSP benchmarks show that IRP consistently produces optimal solutions as well as significant improvement over previous techniques.
Original languageEnglish
Article number22
JournalTransactions on Embedded Computing Systems
Issue number3
Publication statusPublished - 1 Feb 2010


  • Codesign
  • Hardware/software
  • Loop transformation
  • Memory latency hiding

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this