Skip to main content
SpringerLink
Log in

A Code Mapping Scheme for Dataflow Software Pipelining

  • Book
  • © 1991

Overview

Authors:
  1. Guang R. Gao

    1. School of Computer Science, McGill University, USA

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: The Springer International Series in Engineering and Computer Science (SECS, volume 125)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (13 chapters)

  1. Front Matter

    Pages i-xxi
    Download chapter 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
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • School of Computer Science, McGill University, USA

    Guang R. Gao

Bibliographic Information

  • Book Title: A Code Mapping Scheme for Dataflow Software Pipelining

  • Authors: Guang R. Gao

  • Series Title: The Springer International Series in Engineering and Computer Science

  • DOI: https://doi.org/10.1007/978-1-4615-3988-9

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer Science+Business Media New York 1991

  • Hardcover ISBN: 978-0-7923-9130-2Published: 31 December 1990

  • Softcover ISBN: 978-1-4613-6782-6Published: 21 November 2012

  • eBook ISBN: 978-1-4615-3988-9Published: 06 December 2012

  • Series ISSN: 0893-3405

  • Edition Number: 1

  • Number of Pages: XXI, 249

  • Topics: Processor Architectures

Publish with us

Policies and ethics

Back to top

Search

Navigation