article · 1993

Software Pipelining for Nested Loops

Guang R. Gao, Qi Ning, Vincent Van Dongen

Cited by 0Abstract and details only

Abstract

In this paper, we present a novel framework of software pipelining for nested loops. Under this framework, a periodic scheduling function, called r-periodic schedule, is associated with each operation of the loop body in the entire iteration space. We present a simple problem formulation as well as efficient solutions which gives provable asymptotically time-optimal schedule for nested loops under our program model. It also provides some useful insights on the interplay between unimodular loop transformation and fine-grain scheduling under a unified framework. The main results are: ffl We show that, for nested loops under our program model, software pipelining problem can be formulated into a very simple linear programming problem based on r-periodic schedules. ffl We prove that the r-periodic scheduling is asymptotically time-optimal, that is, it is asymptotically as good as the best schedule --- the free schedule where statements can be freely scheduled as early as possible subjec...

Cite this paper

APA 7

Gao, G. R., Ning, Q., & Van Dongen, V. (1993). Software Pipelining for Nested Loops.

MLA 9

Gao, Guang R., et al. “Software Pipelining for Nested Loops.” 1993.

Chicago

Gao, Guang R., Qi Ning, and Vincent Van Dongen. 1993. “Software Pipelining for Nested Loops.”

Harvard

Gao, G.R., Ning, Q. and Van Dongen, V. (1993) ‘Software Pipelining for Nested Loops’.

BibTeX

@article{gao1993software,
  title = {{Software Pipelining for Nested Loops}},
  author = {Gao, Guang R. and Ning, Qi and Van Dongen, Vincent},
  year = {1993}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.