Throughput-Constrained Buffer Capacity Computation for Run-Time Scheduled Modal Task Graphs


Dr. Maarten Wiggers (University of Twente + UC Berkeley),Dr. Marco Bekooij (NXP Semiconductors, Eindhoven)


Increasingly, stream processing applications include complex control structures to better adapt to changing conditions in their environment. This adaptivity often results in task execution rates that are dependent on the processed stream. Current approaches to compute buffer capacities that are sufficient to satisfy a throughput constraint have limited applicability in case of data-dependent task execution rates. This talk presents a dataflow model that allows tasks to have loops with an unbounded number of iterations. For instances of this dataflow model, we present efficient checks on their validity. Furthermore, we present an efficient algorithm to compute buffer capacities that are sufficient to satisfy a throughput constraint. This allows to guarantee satisfaction of a throughput constraint over different modes of a stream processing application, such as the synchronizing and synchronized modes of a digital radio receiver.


Maarten Wiggers has M.S. ('04) and Ph.D. ('09) degrees in computer science from the University of Twente in The Netherlands. He is currently a postdoctoral researcher at the University of Twente in collaboration with and located at the University of California at Berkeley. His interests are in models and the corresponding analysis techniques to derive the temporal behavior of applications on predictable multi-processor systems.

Marco Bekooij obtained his Ph.D. degree from the Eindhoven University of Technology in 2004. He is currently a principal researcher at NXP Semiconductors and part-time full professor at the University of Twente. He is currently involved in the design of channel decoders for car radio and wireless LAN receivers. His current research interests include the design and analysis of predictable and composable embedded multiprocessor systems for stream processing applications and the development of multiprocessor compilers for real-time systems.


(remove if unused)