Accession Number:

ADA273402

Title:

A Resource Constrained Loop Pipelining Technique for Perfectly-Nested Loop Structures

Descriptive Note:

Master's thesis Jul 1991-Sep 1993

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-09-01

Pagination or Media Count:

180.0

Abstract:

This thesis presents a new technique for loop pipelining of perfectly-nested for-loop structures which is designed to optimize loop execution on VLIW machines. Previously implemented loop pipeline techniques provide limited performance benefit because they explicitly include the constraints imposed by a loops cyclic dependences i loop pipelining process. Some loop pipelining techniques have also ignored the realistic constraint of finite resource availability in the creation of final pipelined execution schedules. The new approach presented in this thesis eliminates the problem of cyclic dependences by first applying a linear transformation to the nested loop index space to ensure a cycle-free innermost loop, which is then pipelined using modulo scheduling for a known set of resources. The transformation guarantees that the target machines available resources are the only limit to the amount of exploitable fine-grained parallelism within the innermost loop. This results in pipelined execution schedules having near-optimal Inter-Iteration Initiation Intervals IIII with the achievable performance being scalable with the addition of resources. Consequently, our loop pipelining method utilizes more fine-grained parallelism than other loop pipelining techniques which directly incorporate a loops cyclic dependences in their pipelining process. We also explicitly provide a procedure for creating the resultant pipelined execution schedules.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE