Parametric Design Synthesis of Distributed Embedded Systems

dc.contributor.authorKang, Dong-Inen_US
dc.contributor.authorGerber, Richarden_US
dc.contributor.authorSaksena, Manasen_US
dc.date.accessioned2004-05-31T22:50:39Z
dc.date.available2004-05-31T22:50:39Z
dc.date.created1998-03-12en_US
dc.date.issued1998-10-15en_US
dc.description.abstractThis 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 projected behavior. 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.format.extent389221 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/945
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3885en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-98-18en_US
dc.titleParametric Design Synthesis of Distributed Embedded Systemsen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3885.ps
Size:
380.1 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3885.pdf
Size:
333.38 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3885.ps