Samenvatting
The design of functionally correct systems greatly bene¯ts from modularity. When ex
pressed in a formalism that possesses a compositional semantics, reasoning about the cor
rectness of these designs is considerably simpli¯ed. In this thesis we have extended such
an approach to include compositional performance analysis, enabling e±cient assessment
of the change in performance, when parts of a system are replaced by functional equivalent
ones.
We apply our approach to dataindependent stream processing systems, a class of elec
tronic systems of considerable interest, since it includes most digital signal processing
applications. For these systems we present a compositional approach to their design and
performance analysis, which is suitable for early design space exploration. Its key ingre
dients are: a design style in which systems are composed from a prede¯ned set of basic
components using a single universal composition operator, a CSPoriented hardware de
scription language to describe systems, two calculi to reason about the location of data
within streams, a schedule calculus in which schedules are syntactic objects, a performance
calculus based on truthful metrics, and a quantitative approach to elasticity, a novel per
formance metric that indicates how well a system can cope with small °uctuations in the
temporal behavior of its environment.
Truthful metrics are performance metrics that can be computed e±ciently and that
allow a reliable comparison of designs without accurate prediction of their performance.
This makes them eminently suitable for the determination of the Paretooptimal points of
a design space.
This thesis uses the concept of weight to capture causal dependencies between the inputs
and outputs of a system. Using weights, three classes of dataindependent systems are
de¯ned: dataconservative systems, blockconservative systems, and weightconservative
systems. An analytic design space exploration is performed for a representative application
from each class.
In terms of functionality, dataconservative systems perform the simplest computations.
A main result of this thesis is that dataconservative systems obey Little's law, which states
that the product of throughput and latency equals occupancy, no matter how the system's
events are scheduled. A speci¯c class of dataconservative systems is formed by bu®er
systems. This thesis de¯nes a taxonomy of bu®ers according to structural complexity. For
each class of the taxonomy, a design space exploration is performed that ¯nds optimally
elastic bu®ers.
Of the three classes, weightconservative systems are capable of the most complex com
putations. In particular, they can perform window computations, and many digital signal
processing applications are formulated as window computations. Performance metrics
and analysis techniques established for dataconservative systems are extended to weight
conservative systems. In particular, we have established a novel version of Little's law
involving weights. As a casestudy for this class of systems, we have explored a number of
¯nite impulse respons ¯lter designs.
Blockconservative systems are weightconservative systems that are special in the sense
that their performance analysis can be done as if they are dataconservative. As a case
study for this class of systems, we have analyzed the performance of various block sorters
known from the literature.
Our approach helps to alleviate a major problem in electronic system design, namely
that present design productivity does not increase fast enough to exploit the increase in
computational resources o®ered by the rapid advances in semiconductor technology.
Originele taal2  Engels 

Kwalificatie  Doctor in de Filosofie 
Toekennende instantie 

Begeleider(s)/adviseur 

Datum van toekenning  9 sep 2008 
Plaats van publicatie  Eindhoven 
Uitgever  
Gedrukte ISBN's  9789038613451 
DOI's  
Status  Gepubliceerd  2008 
Vingerafdruk Duik in de onderzoeksthema's van 'Design and performance analysis of dataindependent stream processing systems'. Samen vormen ze een unieke vingerafdruk.
Citeer dit
Mak, R. H. (2008). Design and performance analysis of dataindependent stream processing systems. Technische Universiteit Eindhoven. https://doi.org/10.6100/IR636537