9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # The CBP Parameter — a Useful Annotation to Aid SDF Compilers 1

The CBP Parameter — a Useful Annotation to Aid SDF Compilers1

Shuvra S. Bhattacharyya Department of Electrical and Computer Engineering, and Institute for Advanced Computer Studies University of Maryland, College Park ssb@eng.umd.edu Praveen K. Murthy Angeles Design Systems San Jose, California pmurthy@angeles.com

Abstract

Memory consumption is an important metric for DSP software implementation [11]. In this paper, we develop a module characterization technique that promotes more economical use of memory resources at the system level. Our work is in the context of software synthesis from signal/video/ image processing applications expressed as synchronous dataflow (SDF) graphs. SDF is a restricted form of dataflow where each computational module (actor) consumes and produces a fixed number of data values (tokens) on each firing. Usually, no assumption is made about when during the execution of an actor, the tokens are actually consumed and produced; the firing of an actor is treated as an atomic event for most purposes. However, we show in this report that it is possible to concisely and precisely capture key properties pertaining to the relative times at which tokens are produced and consumed by an actor. We show this by introducing the consumedbefore-produced (CBP) parameter, which provides a general method for characterizing the token transfer of an SDF actor. Good bounds on the CBP parameter can aid an SDF compiler in performing more aggressive optimizations for reducing buffer sizes on the edges between actors. We formally define the CBP parameter; derive some useful properties of this parameter; illustrate how the value of the parameter is derived by examining in detail the multirate FIR filter, which is a fundamental actor in multirate signal processing applications; and examine CBP parameterizations for several other practical SDF actors.

1. Technical report UMIACS-TR-99-56, Institute for Advanced Computer Studies, University of Maryland, College Park, 20742, September, 1999. S. S. Bhattacharyya was supported in this work by the US National Science Foundation (CAREER, MIP9734275) and Northrop Grumman Corp. The CBP Parameter — a Useful Annotation to Aid SDF Compilers

1 of 20

1

Introduction

Dataflow is a natural model of computation to use as the underlying model for a block-

diagram language for designing digital signal processing (DSP) systems. Functional blocks in dataflow-based, block-diagram languages correspond to vertices (actors) in a dataflow graph, and the connections correspond to directed edges between the actors. These edges not only represent communication channels, conceptually implemented as FIFO queues, but also establish precedence constraints. An actor fires in a dataflow graph by removing tokens from its input edges and producing tokens on its output edges. The stream of tokens produced this way corresponds naturally to a discrete time signal in a DSP system. In this paper, we consider a restricted form of dataflow called synchronous dataflow (SDF) [8]. In SDF, each actor produces and consumes fixed numbers of tokens, and these numbers are known at compile time. In addition, each edge has a fixed number of initial tokens, called delays. SDF is used in numerous commercial and researchoriented design tools for DSP, such as COSSAP [12] from the Aachen University of Technology (now from Synopsys), GRAPE [7] from K. U. Leuven, Ptolemy [5] from U. C. Berkeley, DSP Canvas from Angeles Design Systems, SPW from Cadence, and ADS from Hewlett Packard.

2

Notation and background

Fig. 1(a) shows a simple SDF graph. Each edge is annotated with the number of tokens

produced (consumed) by its source (sink) actor. Given an SDF edge e , we denote the source actor, sink actor, and delay of e by src ( e ) , snk ( e ) , and del ( e ) . Also, prod ( e ) and cons ( e ) denote the number of tokens produced onto e by src ( e ) and consumed from e by snk ( e ) . A schedule is a sequence of actor firings. We compile an SDF graph by first constructing a valid schedule — a finite schedule that fires each actor at least once, does not deadlock, and produces no net change in the number of tokens queued on each edge. Corresponding to each actor in the schedule, we instantiate a code block that is obtained from a library of predefined actors. The resulting sequence of code blocks is encapsulated within an infinite loop to generate a software implementation of the SDF graph. SDF graphs for which valid schedules exist are called consistent SDF graphs. In [8], efficient algorithms are presented to determine whether or not a given SDF graph is consistent, and to determine the minimum number of times that each actor must be fired in a valid schedule. We rep2 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

resent these minimum numbers of firings by a vector q G , indexed by the actors in G (we often suppress the subscript if G is understood). These minimum numbers of firings can be derived by finding the minimum positive integer solution to the balance equations for G , which specify that q must satisfy prod ( e ) q ( src ( e ) ) = cons ( e ) q ( snk ( e ) ) , for every edge e in G . The vector q , when it exists, is called the repetitions vector of G .

(EQ 1)

3

Constructing memory-efficient loop structures

In [1, 2], the concept and motivation behind single appearance schedules (SAS) has been

defined and shown to yield an optimally compact inline implementation of an SDF graph with regard to code size (neglecting the code size overhead associated with the loop control). An SAS is a looped schedule in which each actor appears only once. A looped schedule is a schedule that employs a parenthesized schedule loop notation to organize repetitive execution sequences into looping constructs. Figure 1 shows an SDF graph, and valid looped schedules for it. Here, the schedule loop ( 2 B ) represents the firing sequence BB . Similarly, ( 2 B ( 2 C ) ) is a schedule loop with the firing sequence BCCBCC . Schedules 2 and 3 in figure 1 are single appearance schedules since actors A, B, C appear only once. An SAS like the third one in Figure 1(b) is called flat since it does not have any nested loops. In general, there can be exponentially many ways of nesting loops in a flat SAS [2]. Scheduling can also have a significant impact on the amount of memory required to implement the buffers on the edges in an SDF graph. For example, in Figure 1(b), the buffering requirements for the four schedules, assuming that one separate buffer is implemented for each edge, are 50, 40, 60, and 50 respectively.

(a)

A

20

10

B

20

10

C

Valid Schedules (b ) (1): ABCBCCC (3): A(2 B)(4 C) (2): A(2 B(2 C))) (4): A(2 BC)(2 C)

Fig 1. An example used to illustrate the interaction between scheduling SDF graphs and the memory requirements of the generated code.

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

3 of 20

To guide scheduling decisions, it is useful to have an accurate characterization of the interface (data production/consumption) behavior of each actor. The quantities prod ( e ) and cons ( e ) are examples of useful forms of interface characterization. In this paper, we develop an additional form of interface characterization, which we call the consumed-before-produced (CBP) parameter.

4

The CBP parameter

We say that a token is consumed from a memory buffer when the last access to it from the

buffer is completed. Also, for a given invocation I of an SDF actor, a given input edge α i of the actor, and a given output edge α o , we represent the number of tokens produced (onto αo ) and consumed (from α i ) during the time interval [ 0, t ] by p I ( t ) and c I ( t ) , respectively (time 0 corresponds to the starting time of the actor invocation, and t must be less than or equal to the completion time). If I is understood from context, we may drop the subscript I , and simply write p ( t ) and c ( t ) . Definition 1: Suppose that A is an actor in an SDF graph, αi is an input edge of A , and α o is an output edge of A . The CBP parameter of the pair ( α i, αo ) for the given implementation of A , denoted CBP A ( α i, αo ) , is intended to specify the best (largest) known lower bound on cI ( t ) – pI ( t ) . Thus if a CBP parameter has been specified by the actor programmer for ( α i, α o ) , then an SDF compiler can assume that ( c I ( t ) – p I ( t ) ) ≥ CBP A ( α i, α o ) for any invocation I , and for all valid t . If no CBP parameter has been specified, a worst-case CBP parameter CBP A ( α i, α o ) = – prod ( αo ) must be assumed, or the actor source code must be analyzed to try to determine a tighter bound. Such source code analysis is beyond the scope of this paper, and we simply assume the worst case bound CBP A ( α i, α o ) = – prod ( αo ) when the actor programmer has not specified a CBP value. Note that we always have CBP A ( α i, α o ) ≤ 0 since c I ( 0 ) = p I ( 0 ) = 0 . Thus, we have the following fact. Fact 1: If A is an actor with input edge α i and output edge α o , then the value of the associated CBP parameter must satisfy ( – prod ( α o ) ) ≤ CBP A ( α i, α o ) ≤ 0 .

4 of 20

(EQ 2)

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

Higher CBP values give more flexibility in buffer sharing, as will be demonstrated below, and thus, it is advantageous to specify a tight lower bound as the CBP. Due to the regularity of many DSP computations, the computation of tight CBP bounds is often straightforward. As a simple example of a tight CBP bound, consider the “block addition” actor illustrated in Figure 2(a), which inputs a block of N tokens from each input, and outputs a block of N tokens such that each i th value in the output block is the sum of the i th values in the input blocks. If the Motorola DSP56000 code outlined in Figure 2(b) is used to implement this actor, then it is apparent that the i th token read from each input edge is always consumed before the i th output is computed. As a result, the total number of tokens produced p ( t ) at any given time (during the execution of a particular invocation of the actor) can never be greater than the number of tokens c ( t ) consumed until that time from any single input edge. Thus, we are guaranteed that c I ( t ) – p I ( t ) ≥ 0 and CBP A ( α i, α o ) = 0 is a valid choice. This knowledge that c I ( t ) – p I ( t ) ≥ 0 allows us to fully overlay the output buffering for the code segment shown in Figure 2(a) with either of the two input buffers. For example, if we initialize the output write pointer to the beginning of the input buffer that starts at address inbuf1, we are guaranteed by the relation CBP A ( α i, αo ) = 0 that the output write pointer will never “overtake” the input read pointer associated with the inbuf1 buffer. Code for the block addition actor that incorporates this input/output overlaying is shown in Figure 2(c). We refer to this form

N + N N

(a) (c) move #inbuf1, r0 move #inbuf2, r5 move r5, r4 move x:(r0)+, x0 move y:(r5)+, a do #N, LOOPEND add x0, a move x:(r0)+, x0 move y:(r5)+, a move a, y:(r4)+ LOOPEND:

(b) move #inbuf1, r0 move #inbuf2, r5 move #outbuf, r4 move x:(r0)+, x0 move y:(r5)+, a do #N, LOOPEND add x0, a move x:(r0)+, x0 move y:(r5)+, a move a, y:(r4)+ LOOPEND:

Fig 2. A block addition actor that illustrates the derivation and exploitation of a tight CBP bound.

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

5 of 20

of buffer sharing — in which an input channel and output channel of the same actor share the same physical buffer — as buffer merging. Definition 2: Since CBP A ( α i, α o ) always lies in the range { – prod ( α o ), – prod ( α o ) + 1, – prod ( α o ) + 2, …, 0 } , the ratio of the absolute value of the CBP parameter to prod ( α 0 ) is a useful gauge of the degree to which a given actor implementation facilitates the consolidation of an input/output buffer pair. Thus, we define the CBP efficiency of an actor implementation A with respect to the ordered pair ( αi, α o ) as the sum CBP A ( α i, α o ) 1 + ---------------------------------, prod ( α o ) which is always equal to CBPA ( α i, α o ) 1 – -----------------------------------prod ( αo ) since from Fact 1, the value of the CBP parameter is always non-positive. Thus, the CBP efficiency is always a non-negative rational number that lies in the closed interval [ 0, 1 ] . For the example of Figure 2, we have a CBP efficiency of unity, or 100%, since CBP A ( α i, α o ) = 0 . In Section 5, we will see an example of an actor that can have an infinite range of different CBP efficiencies depending on its functional parameters. CBP parameters can also be exploited significantly in multirate FIR filters, which are common building blocks in multirate DSP applications. As we show in the following section, a a - (in reduced-fraction form) multirate FIR filter that performs a sample rate conversion of factor -b can be implemented with an efficient polyphase realization [2, 3] for which the CBP parameter can be set to ? 0 if ( a < b ) CBP ( α i, α o ) = ? . ( b – a ) if ( a > b ) ?

(EQ 4) (EQ 3)

(EQ 5)

6 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

We conclude this section with a simple fact concerning CBP parameters that is useful in deriving CBP parameters for specific actor implementations. Fact 2: Suppose that A , α i , and α o are as in Definition 1. Given an invocation A I of A , let t i denote the time (relative to the beginning of A I ) at which the i th output token of A I is produced, for i = { 1, 2, …, prod ( α 0 ) } . Also, define t 0 ≡ 0 , let T I denote the duration of A I , and let x be a non-positive integer. Then, if c I ( t i ) – p I ( t i ) ≥ x for all i ∈ { 0, 1, 2, …, prod ( α 0 ) } , we are guaranteed that c I ( t ) – pI ( t ) ≥ x for all t ∈ [ 0, T I ] . The most important implication of Fact 2 is that to determine a lower bound on c I ( t ) – p I ( t ) it suffices to examine the values of c I ( t ) and p I ( t ) only at the time instants at which output tokens are generated. In particular, we need not explicitly consider the time instants associated with consumption activity. We will exploit this simplification in Section 5. Proof of Fact 2: Since no production activity occurs between successive t i s, we have that t i < t < t i + 1 ? c I ( t ) – p I ( t ) ≥ c I ( t i ) – p I ( t i ) for 0 ≤ i < prod ( α0 ) . Similarly, t prod ( α ) < t ≤ T I ? c I ( t ) – p I ( t ) ≥ c I ( t prod ( α ) ) – p I ( t prod ( α ) ) .

0 0 0

(EQ 6)

(EQ 7)

From (6) and (7), we can conclude that ?t? ∈ [ 0, T I ] , ?i? ∈ { 0, 1, 2, …, prod ( α 0 ) } such that c I ( t? ) – p I ( t? ) ≥ c I ( t i? ) – p I ( t i? ) . (EQ 8) The desired result follows immediately from (8). QED.

5

Multirate FIR filters

A multirate FIR filter actor, shown in Figure 3(a), performs a sample rate conversion of an u - along with an FIR (“finite impulse response”) filtering operation. Funcarbitrary rational factor -d tionally, it is equivalent to the structure shown in Figure 3(b), which contains a conventional upsampler, downsampler, and an appropriately designed single-rate FIR filter. Details on the applications and signal processing aspects of multirate FIR filters are given in [6].

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

7 of 20

The computational “core” of Figure 3(b) is the FIR actor, which effectively forms an inner product of a vector of adjacent data samples with a vector of constant coefficients. In this discussion, we consider the class of multirate FIR filter implementations in which the vector of “past” (previously consumed) data samples involved in the FIR inner product is maintained in a separate memory buffer that is internal to the multirate FIR actor. This is a natural approach to implementing filtering operations, and it is compatible with the concept of polyphase filter implementations in which storage and operations associated with zero-valued samples are avoided [6][4]. In other words, we do not consider “in-place” computation of the FIR operation, where the inner product operates directly on the buffer associated with the input edge to the multirate FIR actor. This assumption is consistent with our primary objective of memory minimization since performing in-place buffering generally increases the lifetimes of the buffers on the associated edges, and thus reduces opportunities for buffer sharing [10]. The benefit of in-place buffering is that it saves the execution-time cost of having to move each data sample from the input edge buffer to the corresponding internal buffer. The problem of systematically balancing the execution-time benefits of in-place buffering for SDF graphs with the construction of compact looped schedules and buffer sharing is a useful topic for future study.

(a)

d

M FIR

u

(b)

1

↑u

u

1

FIR

1

d

↓d

1

0 0

x2

0 0

x1

0

0

x0

0 0

x-1

0 0

x-2

(c) y2 y1 y0

Fig 3. An example of a multirate FIR filter actor that we use to illustrate the derivation of CBP parameters.

8 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

Figure 3(c) illustrates the production and consumption activity that occurs in a multirate FIR filter. In this illustration u and d are taken to be 3 and 2 , respectively, and the order of the filter is taken to be 4 . The order O M of the filter is the number of adjacent samples from the input of the FIR block of Figure 3(b) that are involved in the computation of each output sample. Since u = 3 and d = 2 in the illustration of Figure 3(c), the multirate FIR filter actor consumes 2 tokens and produces 3 tokens per invocations here. The first row of symbols (zeros and x i s) shown in Figure 3(c) represents a stream of data samples processed in a given invocation M I of the multirate FIR filter M . The zeros shown in the stream are inserted by the logical upsampler block (labeled “↑u”) in Figure 3(b). The upsampler effectively interleaves u – 1 zeros between each pair of input tokens. Each x i represents the input token value at offset i relative to the beginning of M I . Thus, x 0 and x 1 are, respectively, the first and second token values consumed by M I ; x 2 is the first token value consumed by M I + 1 , the next invocation of M ; and x – 1 is last token value consumed by M I – 1 (if M I is the first invocation of M — that is, I = 1 — then x – 1 is part of the initial state of M ). Similarly, y 0, y 1, y 2 represent the first, second and third token values produced by MI . The three overlapping ovals in Figure 3(c) group sets (“windows”) of O M = 4 adjacent token values in the upsampled stream with the actor output tokens that are derived from them. Successive windows (windows associated with successive actor invocations) are offset by two sample positions due to the downsampler of Figure 3(b), which has downsampling factor d = 2 in this example. Assuming that the output tokens y 0, y 1, y 2 are produced according to their logical ordering (as they usually are) — that is, as long as ( i < j ) ? ( y i is produced before y j ) — we have the following observations from Figure 3(c): c ( t 0 ) ≥ 1 , c ( t 1 ) ≥ 1 , and c ( t 2 ) ≥ 2 , where t 0, t 1, t 2 respectively denote the times at which y 0, y 1, y 2 are produced.

(EQ 10) (EQ 9)

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

9 of 20

It follows that for the multirate FIR filter illustrated in Figure 3(c) ( u = 3 , d = 2 ), we have that c ( t ) – p ( t ) ≥ max ( { ( 1 – 1 ), ( 1 – 2 ), ( 2 – 3 ) } ) = 0 . Thus, for this example, a CBP parameter of 0 is feasible for any implementation. To generalize this analysis, we observe that for arbitrary u , d and O M , the grouping of values in the upsampled stream with corresponding output tokens has the following characteristics: each pair of adjacent input tokens x i and x i + 1 is separated by exactly ( u – 1 ) zero-valued samples; each output token is derived from a “window” of O M adjacent values in the upsampled stream; each successive “window” of O M samples is shifted d units (token positions) to the left (towards increasing time) with respect to the previous window; and the first window — the window associated with output y 0 — has x 0 as its left-most sample1. Now let c ( t ) and p ( t ) denote the total number of tokens consumed and produced, respectively, during the first t time units (during the interval [ 0, t ] ) in the execution of a given invocation M? of a multirate FIR filter actor. Recall that each output token is derived from a window of O M successive samples from the upsampled data stream illustrated in Figure 3(b), and let L k denote the offset, relative to x 0 , of the window that corresponds to the k th output token. Thus, L 1 = 0 , L 2 = d , L 3 = 2 d , and so on. In other words, L k = ( k – 1 ) d for k = 1, 2, …, u . Furthermore, observe that for p ( t ) ≥ 1 , we must have Lp ( t ) ≤ ( c ( t ) – 1 ) u + ( u – 1 ) ;

(EQ 13) (EQ 12) (EQ 11)

otherwise ( c ( t ) + 1 ) tokens will have been consumed throughout the time interval [ 0, t ] . This is because each pair of successive x i s is separated by exactly ( u – 1 ) zero-valued samples in the “internal” upsampled data stream, and we are assuming that input tokens to the multirate FIR filter are transferred to an internal buffer as soon as they are encountered (no in-place computation). From (12) and (13), it follows immediately that

1. This last characteristic depends on the phase setting of the multirate filter. Our analysis in this section can easily be extended to handle arbitrary, less conventional phase settings to derive CBP parameters for such cases. We omit the details in this paper.

10 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

( p( t) – 1 )d ≤ ( c ( t ) – 1 )u + u – 1 ,

(EQ 14)

and although we have derived (14) under the assumption that p ( t ) ≥ 1 , the inequality is easily seen to hold for p ( t ) = 0 as well. This is because by definition, we have that d ≥ 1 , and c ( t ) ≥ 0 , and thus, (c( t) – 1)u + u – 1 ≥ (( c( t) – 1)u + u – 1) We conclude that (14) holds for all t . With some rearrangement of terms, (14) can be seen to be equivalent to (t )u p(t) < 1 + c -----------. d

(EQ 16)

c(t) = 0

= –1 ≥ –d = ( ( p ( t ) – 1 ) d )

p(t) = 0

. (EQ 15)

Now suppose, as above, that t 0, t 1, …, t u – 1 denote the times at which outputs y 0, y 1, …, y u – 1 , respectively, are produced. Then, clearly for all i , p ( ti ) = ( i + 1 ) , and combining this with (16) yields c ( ti ) -u , i + 1 < 1 + ---------d which is equivalent to di -. c ( t i ) > ---u Thus, combining (19) and (17), we have c ( t i ) – p ( t i ) > di ---- – (i + 1) . u From (20) and the restriction that i ∈ { 0, 1, …, ( u – 1 ) }

(EQ 21) (EQ 20) (EQ 19) (EQ 18) (EQ 17)

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

11 of 20

(since M? produces u output tokens), it follows that c ( t i ) – p ( t i ) ≥ 0 whenever d ≥ u .

(EQ 22)

On the other hand, if u > d , then the LHS of (19) attains its minimum value over the range (21) when i = ( u – 1 ) . Thus, for u > d , we have (u – 1) c ( ti ) – p ( ti ) > d -------------------–u , u which is equivalent to c ( ti ) – p ( ti ) > ( d – u ) – d --. u Since u > d , and both c ( t i ) and p ( t i ) must be integers, it follows that c ( t i ) – p ( ti ) ≥ ( d – u ) whenever u > d .

(EQ 25) (EQ 24) (EQ 23)

From Fact 2, we can extend the conclusions of (22) and (25) to arbitrary values of t . That is, throughout any invocation of M? , we have that ( d ≥ u ) ? ( c ( t ) – p ( t ) ≥ 0 ) and ( u > d ) ? ( c ( t ) – p ( t ) ≥ ( d – u ) ) . In summary, we have established the following result.

Theorem 1: If in-place buffering is not used and output tokens are produced according to their log(EQ 26)

ical ordering, then a rational, multirate FIR filter can be derived from the following relations: ? 0 if ( u ≤ d ) CBP = ? , ? ( d – u ) if ( u > d ) u - is the reduced form of the output-to-input sample-rate conversion ratio. where -d From Theorem 1, we see that the CBP efficiency of a multirate FIR filter is unity (100%) if u ≤ d ; otherwise, for u > d , the CBP efficiency is given by d –u u+d–u -----------? 1+? - = d --. ? u ? = -------------------u u

12 of 20

(EQ 27)

(EQ 28)

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

Thus, when a multirate FIR filter has an output-to-input sample-rate conversion ratio that exceeds unity, the CBP efficiency decreases monotonically with the magnitude of the conversion ratio.

6

Chop

The chop actor is another example of a practical actor for which CBP parameterization is

useful. In this section, we consider the chop actor that is available in the Ptolemy design environment [5]. On each invocation, the chop actor reads a block of data from its input channel, and in general, produces on its output a “window” of contiguous samples from the input channel. Three parameters — the integer offset ? , the boolean-valued past-inputs parameter, and the production parameter N w — determine the size and relative position of the output window that is produced. The size of each input block is determined by the consumption parameter N R . These parameters must satisfy Nw + ? ≤ NR ,

(EQ 29)

which ensures that the actor will not attempt to read samples that have not yet been produced. If ? > 0 , then the output window starts at an offset of ? from the beginning of the input window and extends for N w samples. The past-inputs parameter is not relevant in this case. If ? < 0 , and past-inputs is false, then the first ( – ? ) tokens that are produced are all zero-valued tokens, and the remaining output tokens are copies of the first ( N w + ? ) tokens in the input block. Finally, if ? < 0 and past-inputs is true, then the first ( – ? ) tokens produced are copies of the last ( –? ) tokens from the previous input block. Again, the remaining output tokens are copies of the first ( N w + ? ) tokens in the input block. Using techniques similar to those illustrated in Section 5, the implementation of the chop actor in Ptolemy can be shown to satisfy the following tight CBP parameterization: 0 if ( ? ≥ 0 ) ? ? ? if ( ( ? < 0 ) and ( past-inputs = false ) ) CBP = ? . ? ? ( min ( { N r – N w, 0 } ) ) if ( ( ? < 0 ) and ( past-inputs = true ) )

(EQ 30)

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

13 of 20

7

Autocorrelation

The autocor actor in the Ptolemy SDF DSP library “estimates a certain number of samples

of the autocorrelation of the input by averaging a certain number of input samples.” Like the multirate FIR and chop actors, autocor has one input port (edge) and one output port. Two parameters control the token transfer of this actor. The first parameter N avg specifies the number of input samples that are averaged, and the second parameter N lag specifies the number of lags that are estimated. It is required that the value of the N avg parameter be strictly greater than the value of N lag . The number tokens consumed from the input edge e i , and the number tokens produced on the output edge e o on each invocation are given by cons ( e i ) = N avg , and prod ( e o ) = 2 N lag .

(EQ 31)

By analyzing the definition of the Ptolemy autocor actor, the following tight CBP specification can be derived: CBP = 1 – N lag . The associated CBP efficiency is thus given by 1 + N lag ------------------. 2 N lag

(EQ 33) (EQ 32)

As N lag increases from its minimum possible value of 1 , the CBP efficiency decreases monotonically from 100%, and asymptotically approaches 50% as N lag → + ∞ . To get a sense of a “typical value” of CBP efficiency for this actor, observe that the default value of N lag in Ptolemy is 64. From (33), this yields a CBP efficiency of 50.8%. Indeed, since usually N lag ? 1 , the CBP efficiency of autocor is usually very close to 50%.

8

CBP tables

For actors that have multiple input ports or multiple output ports, the full specification of

CBP parameters takes the form of a matrix or table. Each entry of the matrix corresponds to the CBP parameter associated with the merging of a specific input port with a specific output port.

14 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

8.1

Block lattice As a simple example, consider the block lattice actor in Ptolemy, which has two input

ports — the “coefficient input” and the “signal input” port — and two parameters, the block size N B and the filter order N o . On each invocation, N o new filter tap values are read from the coefficient input port, a block of N B samples is consumed on the signal input port, and a block of N B samples is output on the output port. Tight CBP parameters for the Ptolemy implementation of block lattice can be specified by the following table:

Table 1.

Input port coefficient input signal input

The CBP table for the block lattice actor.

CBP w.r.t. output port

0 –1

The associated CBP efficiencies can be specified in a similar manner:

Table 2.

Input port coefficient input signal input

The table of CBP efficiencies for the block lattice actor.

CBP efficiency 1.0

( NB – 1 ) ? NB

8.2

Commutator Another example of an actor with multiple input ports is the commutator actor, which

interleaves blocks of samples from multiple input streams onto a single output stream. This actor has three parameters — the number of input ports k , the block size N B , and an ordering ( i 1, i 2, …, i k ) of the input ports. On each invocation, N B samples are consumed from each input port, and ( k × N B ) samples are produced on the output port. The first N B output samples are derived by copying N B samples from the first input port i 1 ; the next block of N B output samples is derived by copying N B samples from the input port i 2 ; and so on. Since the number of samples produced on the output is significantly larger than the number consumed from any given input,

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

15 of 20

the CBP efficiencies associated with this actor are relatively low. For any input port, the CBP with respect to the output port is given by CBP = ( 1 – k ) N B , and the CBP efficiency is given by ( 1 – k ) NB = 1 --. 1 + ----------------------k kN B 8.3 Distributor The distributor actor is the dual of the commutator. Like the commutator, the distributor has three parameters. These parameters specify the number of output ports ( k ), the block size ( N B ) , and an ordering ( o1, o 2, …, o k ) of the output ports. On a given invocation, the first (least recent) N B samples from the input channel are copied to the first output port o 1 ; the next N B input samples are copied to output port o 2 ; and so on. Given i ∈ { 1, 2, …, k } and j ∈ { 1, 2, …, N B } , the number of tokens c ( i, j ) consumed just prior to producing the j th output sample on the i th output port is given by c ( i, j ) = ( i – 1 ) N B + j .

(EQ 36) (EQ 35) (EQ 34)

Thus, if c ( t ) denotes the number of tokens consumed from the input port up to time t , and p i ( t ) denotes the number of tokens produced on output port i up to time t , we have that c ( t ) – pi ( t ) ≥ ( i – 1 ) NB . From the definition of CBP, it follows that for any output port o i , CBP = 0 is a valid CBP parameter setting for any output port with respect to the input port.

(EQ 38) (EQ 37)

16 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

9

Summary of derivations

To emphasize that CBP parameters may vary widely depending on the particular actor

Table 3.

Actor

A summary of the CBP parameterizations derived in this paper.

Relevant parameters Block size N . Rate conversion ratio a ? b (in reduced form). 1 (100%) 1 if a < b ; b ? a if a > b . 1 if ? ≥ 0 ; 1 + ? ? N w if ( ( ? < 0 ) and ( past-inputs = false ) ) ; (Max.) CBP efficiency

Block addition Multirate FIR filter

Chop

Production param. N w ; consumption param. N r ; offset ? ; past-inputs (boolean).

min ( { N r – N w, 0 } ) 1 + ---------------------------------------------Nw

if ( ( ? < 0 ) and ( past-inputs = true ) ) . 1 + N lag ------------------2 N lag 1 1 -k 1

Autocorrelation Block lattice Commutator Distributor

Inputs to average N avg ; lags to estimate N lag . Block size N B ; filter order N o . Number of input ports k ; block size N B . Number of output ports k ; block size N B .

under consideration, and to juxtapose the practical examples examined in this paper, Table 3 summarizes the CBP efficiencies that we have derived. For actors that have multiple inputs or multiple outputs, we have listed the maximum CBP efficiency over all input/output combinations. We observe that a significant proportion of the actors examined in Table 3 admit a CBP efficiency of 100%, while the CBP efficiencies of other actors can be significantly lower and heavily parameter-dependent.

10

Related Work

The CBP parameter plays a role that is somewhat similar to the array index distances

derived in the in-place memory management strategies of Cathedral [16], which apply to nested loop constructs in Silage. The CBP-based buffer merging approach presented in this paper is difThe CBP Parameter — a Useful Annotation to Aid SDF Compilers

17 of 20

ferent from the approach of [16] in that it is specifically targeted to the high regularity and modularity present in SDF graph implementations (at the expense of decreased generality). In particular, the overlapping of SDF input/output buffers by systematically applying CBP analysis does not emerge in any straightforward way from the more general techniques developed in [16]. Our form of buffer merging is especially well-suited for incorporation with the SDF vectorization techniques (for minimizing context-switch overhead) developed at the Aachen University of Technology [13] since the absence of nested loops in the vectorized schedules allows for more flexible merging of input/output buffers. Buffer merging is also compatible with buffer access enhancements such as polyphase filter implementation [4, 6], and cyclo-static dataflow specification [3]. Vanhoof, Bolsens and H. De Man have observed that in general, the full address space of an array does not always contain live data [15]. Thus, they define an “address reference window” as the maximum distance between any two live data elements throughout the lifetime of an array, and fold multiple array elements into a single window element using a modulo operation in the address calculation. The concept of the address reference window is similar to our use of the maximum number of live tokens as the size of each individual SDF buffer. The number of logically distinct memory elements (the full address space) in a buffer for an edge e is equal to q ( snk ( e ) ) cons ( e ) , which can be much larger than the maximum number of live tokens that reside on e simultaneously [2].

11

Conclusions

The CBP parameter provides a concise and precise method for encapsulating a library

developer’s knowledge of DSP software functionality in a manner that is valuable for synthesis tools. Our previous work has demonstrated the ability to systematically exploit pre-specified CBP parameters to significantly reduce memory requirements in software implementations [9]. In this paper we have discussed the derivation of CBP parameters for individual DSP functions. By focusing on the multirate FIR filter, we have demonstrated analysis techniques that can be used to derive tight CBP parameters from an understanding of the library function or analysis of code that implements the function. We have also given general, tight expressions for the CBP parameters for a number of additional practical DSP building blocks, which were obtained by analyzing implementations in the DSP libraries provided within the Ptolemy design environment [5]. A use18 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

ful direction for further study is the investigation of tools to help automate the derivation of tight CBP parameters.

12

References

[1] S. S. Bhattacharyya, J. T. Buck, S. Ha, and E. A. Lee, “Generating Compact Code from Dataflow Specifications of Multirate Signal Processing Algorithms,” IEEE Transactions on Circuits and Systems — I: Fundamental Theory and Applications, vol. 42, pp. 138–150, 1995. [2] S. S. Bhattacharyya, P. K. Murthy, E. A. Lee, Software synthesis from dataflow graphs, Kluwer academic publishers, 1996. [3] G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete, “Cyclo-Static Dataflow,” IEEE Transactions on Signal Processing, vol. 44, pp. 397-408, 1996. [4] J. T. Buck, S. Ha, D. G. Messerschmitt, and E. A. Lee, “Multirate signal processing in Ptolemy.” In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, April 1991, pp. 1245–1248. [5] J. Buck, S. Ha, E. A. Lee, D. G. Messerschmitt, “Ptolemy: a Framework for Simulating and Prototyping Heterogeneous Systems”, International Journal of Computer Simulation, Jan. 1995. [6] F. J. Harris. “Multirate FIR filters for interpolating and desampling.” In Handbook of Digital Signal Processing. Academic Press, 1987. [7] R. Lauwereins, M. Engels, J. A. Peperstraete, E. Steegmans, and J. V. Ginderdeuren, “GRAPE: A CASE Tool for Digital Signal Parallel Processing,” IEEE ASSP Magazine, vol. 7, 1990. [8] E. A. Lee, D. G. Messerschmitt, “Static Scheduling of Synchronous Dataflow Programs for Digital Signal Processing,” IEEE Trans. on Computers, Feb., 1987. [9] P. K. Murthy, S. S. Bhattacharyya, “A Buffer Merging Technique for Reducing Memory Requirements of Synchronous Dataflow Specifications,” in Proceedings of the International Symposium on System Synthesis, November, 1999, to appear. [10] P. K. Murthy, S. S. Bhattacharyya, Shared Memory Implementations of Synchronous Dataflow Specifications using Lifetime Analysis Techniques, Technical Report UMIACS-TR-9932, University of Maryland at College Park, June 1999. [11] P. Marwedel, G. Goossens, Code Generation for embedded processors, Kluwer Academic Publishers, 1995. [12] S. Ritz, M. Pankert, and H. Meyr, “High Level Software Synthesis for Signal Processing Systems,” in Proceedings of the International Conference on Application Specific Array Processors, 1992. [13] S. Ritz, M. Pankert, and H. Meyr. “Optimum vectorization of scalable synchronous dataflow graphs.” In Proceedings of the International Conference on Application Specific Array Processors, October 1993.

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

19 of 20

[14] P. P. Vaidyanathan. Multirate Systems and Filter Banks. Prentice Hall, 1993. [15] J. Vanhoof, I. Bolsens, H. De Man, “Compiling Multi-dimensional Data Streams into Distributed DSP ASIC Memory,” Proceedings of the International Conference on Computer-Aided Design, 1991. [16] I. Verbauwhede, F. Catthoor, J. Vandewalle, and H. De Man. “In-place memory management of algebraic algorithms on application specific ICs.” Journal of VLSI Signal Processing, pp. 193–200, 1991.

20 of 20

The CBP Parameter — a Useful Annotation to Aid SDF Compilers

- The Gene Ontology Annotation (GOA) Database--an integrated resource of GO annotations to the UniProt
- The subsystems approach to genome annotation and its use in the project to annotate 1000 ge
- The_DAWGPAWS_pipeline_for_the_annotation_of_genes_and_transposable_elements_in_plant_genomes
- The CKIP Chinese Treebank Guidelines for Annotation
- Compiling language definitions The ASF+SDF compiler
- Bridging the gap between social tagging and semantic annotation E.D. the Entity Describer
- The ELAN environment a rewriting logic environment based on ASF+SDF technology
- Tools to aid the selection of ideal attribute parameter values
- The annotation process in the Turkish treebank
- Semantic Annotation and Intelligent Content Proceedings of the Workshop Supported by SIGLEX

更多相关文章：
**
***The* Sparse Cyclic Distribution against its Dense Co....pdf

*compilers* were born *to* *aid* their programming tasks...Since *the* sparse matrix plays *a* primary role, ...PROCESSORS Q(0:P1 -*1*,0:P2 -*1*) *PARAMETER* (N...**
***The* Read-Write-ReSet (RWS) Model of Provenance Conc....pdf

Intl. Provenance and*Annotation* Workshop (IPAW'06...(re-)attach prior data products *to* *a* new ...*SDF* (token rate is *1*-in, *1*-out) each ...**
***The* Sparse Cyclic Distribution against its Dense Co....pdf

*compilers* were born *to* *aid* their programming tasks...Since *the* sparse matrix plays *a* primary role, ...PROCESSORS Q(0:P1 -*1*,0:P2 -*1*) *PARAMETER* (N...**
***1* Introduction Type-Based Race Detection for Java (....pdf

*1*); } } } *The* guarded by *annotation* on *the* ...*compilers*, *the* additional type information used in...that it is *a* *useful* tool for detecting races. ...**
Productions of ***a* Calculator.pdf

*compilers* Syntax usually defined using context-free...*Annotation*/decoration of parse tree Some classes ...j ? n on *the* rhs of *A* depends only on *1*.... 更多相关标签：

Intl. Provenance and