|dc.description.abstract||This paper presents a design synthesis method for distributed embedded
systems. In such systems, computations can flow through long pipelines
of interacting software components, hosted on a variety of resources,
each of which is managed by a local scheduler. Our method
automatically calibrates the local resource schedulers to achieve the
system's global end-to-end performance requirements.
A system is modeled as a set of distributed task chains (or
pipelines), where each task represents an activity requiring nonzero
load from some CPU or network resource. Task load
requirements can vary stochastically, due to second-order effects
like cache memory behavior, DMA interference, pipeline stalls,
bus arbitration delays, transient head-of-line blocking, etc.
We aggregate these effects -- along with a
task's per-service load demand -- and model them via
a single random variable,
ranging over an arbitrary discrete probability distribution.
Load models can be obtained via
profiling tasks in isolation,
or simply by using an engineer's hypothesis about the system's
The end-to-end performance requirements are posited in terms of
throughput and delay constraints. Specifically, a pipeline's delay
constraint is an upper bound on the total latency a computatation can
accumulate, from input to output. The corresponding
throughput constraint mandates the pipeline's minimum acceptable output
rate -- counting only outputs which meet their delay constraints.
Since per-component loads can be generally distributed, and since
resources host stages from multiple pipelines, meeting all of the
system's end-to-end constraints is a nontrivial problem.
Our approach involves solving two sub-problems in tandem: (A)~finding
an optimal proportion of load to allocate each task and channel; and
(B)~deriving the best combination of service intervals over which all
load proportions can be guaranteed. The design algorithms use
analytic approximations to quickly estimate output rates and
propagation delays for candidate solutions.
When all parameters are synthesized, the estimated end-to-end
performance metrics are re-checked by simulation. The per-component
load reservations can then be increased, with the synthesis algorithms
re-run to improve performance. At that point the system can be
configured according to the synthesized scheduling parameters -- and
then re-validated via on-line profiling.
In this paper we demonstrate our technique on an example system, and
compare the estimated performance to its simulated on-line behavior.
(Also cross-referenced as UMIACS-TR-98-18)||en_US
|dc.relation.ispartofseries||UM Computer Science Department; CS-TR-3885||en_US
|dc.title||Parametric Design Synthesis of Distributed Embedded Systems||en_US
|dc.relation.isAvailableAt||Digital Repository at the University of Maryland||en_US
|dc.relation.isAvailableAt||University of Maryland (College Park, Md.)||en_US
|dc.relation.isAvailableAt||Tech Reports in Computer Science and Engineering||en_US
|dc.relation.isAvailableAt||UMIACS Technical Reports||en_US