A Code Mapping Scheme for Dataflow Software Pipelining

1. Front Matter

   Pages i-xxi

   PDF

2. Introduction

   • Guang R. Gao

   Pages 1-16

3. The Static Data Flow Model

   • Guang R. Gao

   Pages 17-39

4. Algorithmic Aspects of Pipeline Balancing

   • Guang R. Gao

   Pages 41-59

5. Source Program Structure and Notation

   • Guang R. Gao

   Pages 61-75

6. Basic Pipelined Code Mapping Schemes

   • Guang R. Gao

   Pages 77-87

7. Mapping Rules for Expressions without Array Creation Constructs

   • Guang R. Gao

   Pages 89-107

8. Mapping Scheme for One-Level FORALL Expressions

   • Guang R. Gao

   Pages 109-132

9. Mapping Scheme for Multi-Level FORALL Expressions

   • Guang R. Gao

   Pages 133-154

10. Mapping Scheme for FOR-CONSTRUCT Expressions

    • Guang R. Gao

    Pages 155-169

11. Related Optimization Techniques

    • Guang R. Gao

    Pages 171-191

12. Program Structure, Compilation, and Machine Design

    • Guang R. Gao

    Pages 193-209

13. Efficient Dataflow Software Pipelining

    • Guang R. Gao

    Pages 211-229

14. Conclusions

    • Guang R. Gao

    Pages 231-234

15. Back Matter

    Pages 235-249

    PDF

This monograph evolved from my Ph. D dissertation completed at the Laboratory of Computer Science, MIT, during the Summer of 1986. In my dissertation I proposed a pipelined code mapping scheme for array operations on static dataflow architectures. The main addition to this work is found in Chapter 12, reflecting new research results developed during the last three years since I joined McGill University-results based upon the principles in my dissertation. The terminology dataflow soft­ ware pipelining has been consistently used since publication of our 1988 paper on the argument-fetching dataflow architecture model at McGill University [43]. In the first part of this book we describe the static data flow graph model as an operational model for concurrent computation. We look at timing considerations for program graph execution on an ideal static dataflow computer, examine the notion of pipe lining, and characterize its performance. We discuss balancing techniques used to transform certain graphs into fully pipelined data flow graphs. In particular, we show how optimal balancing of an acyclic data flow graph can be formulated as a linear programming problem for which an optimal solution exists. As a major result, we show the optimal balancing problem of acyclic data flow graphs is reduceable to a class of linear programming problem, the net­ work flow problem, for which well-known efficient algorithms exist. This result disproves the conjecture that such problems are computationally hard.

• Scheme
• addition
• algorithms
• character
• code
• computer
• data flow
• design
• form
• graph
• mathematical programming
• optimization
• pipelining
• programming
• software

• School of Computer Science, McGill University, USA

  Guang R. Gao

Policies and ethics