article · 2014

Optimization of Nest-Loop Software Pipelining

Qingfeng Zhuge, Zili Shao, Edwin H. -m. Sha

Cited by 0Abstract and details only

Abstract

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, little research has been done for the software pipelining problem on nested loops. The existing software pipelining techniques for single loops can only explore the innermost loop parallelism of a nested loop, so the final timing performance is inferior. While multi-dimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to transformation. In this paper, we propose theory and algorithms of software pipelining for nested loops with minimal overheads based on the fundamental understanding of the properties of software pipelining for nested loops. We show the relationship among execution sequence, execution time of loop body, and software pipelining degree of a nested loop using retiming concepts. Two algorithms of Software PIpelining for NEsted loops (SPINE) are proposed: The SPINE-FULL algorithm generates fully parallelized loops with computation and code size overheads as small as possible. The SPINE-ROW-WISE algorithm generates the best possible parallelized loops with the minimal overheads. Our technique can be directly applied to imperfect nested loops. The experimental results show that the average improvement on the execution time of the pipelined loop generated by SPINE is 71.7 % compared with that generated by the standard software pipelining approach. The average code size is reduced by 69.5 % compared with that generated by MD retiming.

Cite this paper

APA 7

Zhuge, Q., Shao, Z., & Sha, E. H. M. (2014). Optimization of Nest-Loop Software Pipelining.

MLA 9

Zhuge, Qingfeng, et al. “Optimization of Nest-Loop Software Pipelining.” 2014.

Chicago

Zhuge, Qingfeng, Zili Shao, and Edwin H. -m. Sha. 2014. “Optimization of Nest-Loop Software Pipelining.”

Harvard

Zhuge, Q., Shao, Z. and Sha, E.H.M. (2014) ‘Optimization of Nest-Loop Software Pipelining’.

BibTeX

@article{zhuge2014optimization,
  title = {{Optimization of Nest-Loop Software Pipelining}},
  author = {Zhuge, Qingfeng and Shao, Zili and Sha, Edwin H. -m.},
  year = {2014}
}

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