Home » forums » LtU Forum

assistance with some data flow terms

I'm working out some rules for a data flow network and certain conditions apply in certain situations, but I am not sure what the accepted terminology is for these. So, if you will, what are the names for these:

numOut == numIn
A node (in a data flow graph) always provides exactly one output token for one input token. I've been calling this "systolic", but "systolic" really means "clocked" which this isn't necessarily.

numOut != numIn
A node may provide more or less than one output for one input. I've been calling this "asystolic", but that is even worse since I can't find much use of that term in the literature and in medicine it means "absence or cessation of heartbeat" or "any deviation from a healthy or normal condition" neither of which are desirable descriptions of the situation.

numOut <= numIn
A node provides an equal or fewer number of output tokens as input tokens, e.g. the "filter" operation from FP.

numOut >= numIn
A node provides at least as many output tokens as input tokens, possibly more.

Thank you!

By James McCartney at 2006-06-08 00:39 | LtU Forum | previous forum topic | next forum topic | other blogs | 6549 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

How often do we know in advance?

At my day job, they're doing a chip with a largely dataflow architecture. After talking with the applications guys, my
take on your questions is that for most algorthims, those categories are largely data-dependent. So, here are my names for them:

numOut == numIn ... wishful thinking
numOut != numIn ... reality, usually
numOut <= numIn ... comme ci
numOut >= numIn ... comme ça

By Doug Landauer at Thu, 2006-06-08 15:45 | login or register to post comments

In my case you always know.

In my case you always know.
+ - * / and most signal processing elements .. always one in one out.
sample rate converter .. numOut != numIn
predicate based sieves .. numOut <= numIn
sequence generators .. numOut >= numIn

By James McCartney at Thu, 2006-06-08 15:59 | login or register to post comments

Linear, affine, relevant?

You could borrow from the substructural types terminology. From ATAPL, chapter 1:

  • A linear type system ensures that every variable is used exactly once.
  • An affine type system ensures that every variable is used at most once.
  • A relevant type system ensures that every variable is used at least once.

One problem I see is that "linear", when applied to functions, usually means "differening by a constant factor", informally speaking, not "exactly the same" number of items as here. If you take the function terminology, you could use the "bijective"/"injective"/"surjective" terminology instead.

By Mario B. at Thu, 2006-06-08 17:11 | login or register to post comments

Occam syntax?

These sound like familiar distinctions from process languages. For the last two terms I'm fairly sure these are referred to as mux's and demux's, which are fairly close to the underlying hardware. They're abbreviations for multiplexer (something that places multiple inputs into a single output) and a demultiplexer, which does the reverse. The terminology is common in networks and telecomms.

The first two sound like a synchronous / asychronous division but you're not really talking about timing as such. In pure functional terms the outNum lessThan inNum in would describe a compression function, so perhaps there is some related terminology in dataflow?

Sorry these aren't exactly what you asked for, but hopefully they are helpful.

By Andrew Moss at Mon, 2006-06-12 11:00 | login or register to post comments

tokens not ports

I think you misunderstood me. I am not referring to the numbers of input and output ports. I am referring to numbers of tokens consumed by an operation at a node. For example, the addition operator has two input ports and one output port, but it always produces one output token for one input token at each port. Operators like Haskell's filter, take, drop, always output fewer tokens than input.

By James McCartney at Tue, 2006-06-13 04:08 | login or register to post comments

found the answer: on-line, off-line

OK I have found the answer in the documentation of the Lisp Series macro package.

"A series input port or series output port of a series function is on-line if and only if it is processed in lockstep with all the other on-line ports as follows: the initial element of each on-line input is read, then the initial element of each on-line output is written, then the second element of each on-line input is read, then the second element of each on-line output is written, and so on. Ports that are not on-line are off-line. If all of the series ports of a function are on-line, the function is said to be on-line; otherwise, it is off-line. (The above extends the standard definition of the term on-line so that it applies to individual ports as well as whole functions.)"

So, numOut == numIn is "on-line" and numOut != numIn is "off-line".

Interestingly, in the meantime I've rediscovered the wheel by working out on my own the optimization conditions and constraints he describes above and in this paper: Automatic Transformation of Series Expressions into Loops.

By James McCartney at Thu, 2006-08-10 21:35 | login or register to post comments