A Code Mapping Scheme for Dataflow Software Pipelining by Guang R. Gao

By Guang R. Gao

This monograph advanced from my Ph. D dissertation accomplished on the Laboratory of laptop technology, MIT, throughout the summer time of 1986. In my dissertation I proposed a pipelined code mapping scheme for array operations on static dataflow architectures. the most addition to this paintings is located in bankruptcy 12, reflecting new examine effects built over the last 3 years when you consider that I joined McGill University-results established upon the foundations in my dissertation. The terminology dataflow smooth­ ware pipelining has been continually used due to the fact that ebook of our 1988 paper at the argument-fetching dataflow structure version at McGill college [43]. within the first a part of this ebook we describe the static info circulation graph version as an operational version for concurrent computation. we glance at timing issues for software graph execution on an awesome static dataflow laptop, research the idea of pipe lining, and symbolize its functionality. We speak about balancing suggestions used to remodel yes graphs into totally pipelined info circulation graphs. specifically, we exhibit how optimum balancing of an acyclic info movement graph may be formulated as a linear programming challenge for which an optimum resolution exists. As a big outcome, we convey the optimum balancing challenge of acyclic facts stream graphs is reduceable to a category of linear programming challenge, the web­ paintings circulation challenge, for which recognized effective algorithms exist. This end result disproves the conjecture that such difficulties are computationally hard.

Show description

Read Online or Download A Code Mapping Scheme for Dataflow Software Pipelining PDF

Best software books

Fundamental Approaches to Software Engineering: 12th International Conference, FASE 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings

This publication constitutes the refereed complaints of the twelfth foreign convention on primary ways to software program Engineering, FASE 2009, held in York, united kingdom, in March 2009, as a part of ETAPS 2009, the eu Joint meetings on concept and perform of software program. The 30 revised complete papers provided including 2 software demonstrations have been conscientiously reviewed and chosen from 123 regluar and nine device paper submissions.

Software Business: 6th International Conference, ICSOB 2015, Braga, Portugal, June 10-12, 2015, Proceedings

This e-book includes the refereed lawsuits of the sixth foreign convention on software program company, ICSOB 2015, held in Braga, Portugal, in June 2015. The topic of the development was once "Enterprising towns" concentrating on a visible spillover of software program inside of different industries permitting new company versions: businesses package deal their actual items and software program providers into options and begin to promote self reliant software program items as well as actual items.

Software Architecture: 10th European Conference, ECSA 2016, Copenhagen, Denmark, November 28 -- December 2, 2016, Proceedings

This booklet constitutes the complaints of the tenth ecu convention on software program structure, ECSA 2016, held in Copenhagen, Denmark, in November/December 2016. The thirteen complete papers awarded including 12 brief papers have been rigorously reviewed and chosen from eighty four submissions. they're prepared in topical sections on complete learn and adventure papers, brief papers for addressing rising study, and schooling and coaching papers.

Additional info for A Code Mapping Scheme for Dataflow Software Pipelining

Example text

Chapters 4 through 9 are devoted to the development of our pipelined code mapping scheme. Chapter 4 specifies the representation of the source language. In particular, it introduces PIP VAL-a subset of Val used as the source language for the application programs that are to be mapped. Chapter 4 also introduces the major code blocks: array creation expressions built using the foraH and for-construct language constructs. Lastly, the mapping of array operations organized in these code blocks are also the focus of this chapter.

Chapter 2 The Static Data Flow Model In this chapter we describe the static data flow graph model as an operational model for concurrent computation. This model has evolved from a number of graph operational models for studying concurrent computation. Earlier models concentrated more on basic theoretical aspects, such as decidability properties of concurrent computations: deadlock, non determinacy, equivalence of program graphs, and expressive power for parallelism [7,76,109]. Later works were oriented toward operational models of practical programming languages designed for dataflow computers [14,29,42,38,123].

12 A Code Mapping Scheme for Dataflow Software Pipelining Since we are concerned with how to utilize the regularity of array operations, we concentrate on two particular array creation constructsforall and for-construct. The forall construct allows a programmer to specify the construction of an array where similar independent computations are performed to determine each element. The following expression defines a onedimensional array X from an input array A: X := array[real] := forall i in [0, m+1] % range spec construct if i = 0 then A[i] elseifi = m+1 then A[i] else (A[i-1]+A[i]+A[i+1])/3 endif endall The for-construct expression, proposed as a special case of Val's for-iter, is used to specify construction of an array where certain forms of data dependencies exist between elements.

Download PDF sample

Rated 4.91 of 5 – based on 38 votes

Related posts