Monotonicity and run-time scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Monotonicity and run-time scheduling

Full text

Pdf (375 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the seventh ACM international conference on Embedded software table of contents

Grenoble, France

SESSION: Scheduling table of contents

Pages 177-186

Year of Publication: 2009

ISBN:978-1-60558-627-4

Authors

Maarten H. Wiggers	Technical University of Eindhoven, Eindhoven, Netherlands
Marco J.G. Bekooij	NXP Semiconductors, Eindhoven, Netherlands
Gerard J.M. Smit	University of Twente, Enschede, Netherlands

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629335.1629359 What is a DOI?

ABSTRACT

Modern embedded multi-processors can execute several stream-processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	SoftWare ARM. www.cl.cam.ac.uk/ mwd24/phd/swarm.html.
	2	L. Abeni and G. Butazzo. Resource Reservation in Dynamic Real-Time Systems. Real-Time Systems, (27):123--167, 2004.
	3	M. J. G. Bekooij, S. Parmar, and J. van Meerbergen. Performance Guarantees by Simulation of Process Networks. In Proc. Int'l Workshop on Software and Compilers for Embedded Systems (SCOPES), September 2005.
	4	G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. Cyclo-Static Dataflow. IEEE Transactions on Signal Processing, 44(2):397--408, 1996.
	5	G. C. Butazzo. Hard Real-Time Computing Systems. Kluwer, 1997.
	6	R. L. Cruz. A Calculus for Network Delay, Part II: Network Analysis. IEEE Transactions on Information Theory, 37(1):132--141, January 1991.
	7	E. A. de Kock, W. Smits, P. van der Wolf, J. Y. Brunel, W. M. Kruijtzer, P. Lieverse, K. Vissers, and G. Essink. YAPI: Application Modeling for Signal Processing Systems. In Proc. DAC, 2000.
	8	A. Donlin. Transaction level modeling: Flows and use models. In Proc. ACM/IEEE Int'l Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2004.
	9	A. Gerstlauer, H. Yu, and D. D. Gajski. RTOS Modeling for System Level Design. In Proc. Design, Automation and Test in Europe (DATE), 2003.
	10	R. L. Graham. Computer and Job Scheduling Theory, chapter Bounds on the Performance of Scheduling Alogrithms. John Wiley & Sons, 1976.
	11	W. Haid and L. Thiele. Complex Task Activation Schemes in System Level Performance Analysis. In Proc. ACM/IEEE Int'l Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2007.
	12	A. Hamann, M. Jersak, K. Richter, and R. Ernst. Design Space Exploration and System Optimization with SymTA/S - Symbolic Timing Analysis for Systems. In Proc. IEEE Real-Time Systems Symposium (RTSS), 2004.
	13	A. Hansson, M. H. Wiggers, A. J. M. Moonen, K. G. W. Goossens, and M. J. G. Bekooij. Enabling Application-Level Performance Guarantees in Network-Based Systems on Chip by Applying Dataflow Analysis. IET Computers & Digital Techniques, 2009. to appear.
	14	M. Jersak, K. Richter, and R. Ernst. Performance Analysis of Complex Embedded Systems. Int'l Journal of Embedded Systems, 1(1-2):33--49, 2005.
	15	E. A. Lee and T. M. Parks. Dataflow Process Networks. Proceedings of the IEEE, 83(5):773--801, 1995.
	16	Y.-T. Li and S. Malik. Performance analysis of real-time embedded software. Kluwer academic publishers, 1999.
	17	Z. Lu, M. Millberg, A. Jantsch, A. Bruce, P. van der Wolf, and T. Henriksson. Flow Regulation for On-Chip Communication. In Proc. Design, Automation and Test in Europe (DATE), 2009.
	18	A. K. Mok and D. Chen. A Multiframe Model for Real-Time Tasks. IEEE Transactions on Software Engineering, 23(10):635--645, October 1997.
	19	A. Nieuwland, J. Kang, O. P. Gangwal, R. Sethuraman, N. Busa, K. Goossens, and R. Peset Llopis. C-HEAP: A Heterogeneous Multi-Processor Architecture Template and Scalable and Flexible Protocol for the Design of Embedded Signal Processing Systems. Design Automation for Embedded Systems, 7(3):233--270, 2002.
	20	S. Park, W. Olds, K. G. Shin, and S. Wang. Integrating Virtual Execution Platform for Accurate Analysis in Distributed Real-Time Control System Development. In Proc. IEEE Real-Time Systems Symposium (RTSS), 2007.
	21	S. Sriram and S.S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker Inc., 2000.
	22	B. Sprunt, L. Sha, and J. P. Lehoczky. Aperiodic Task Scheduling for Hard Real-Time Systems. Real-Time Systems, 1(1):27--60, 1989.
	23	M. Spuri and G. C. Buttazzo. Scheduling aperiodic tasks in dynamic priority systems. Journal of Real-Time Systems, 10(2), 1996.
	24	M. Steine, M. J. G. Bekooij, and M. H. Wiggers. A Priority-Based Budget Scheduler with Conservative Dataflow Model. In Proc. Euromicro Conference on Digital System Design (DSD), 2009.
	25	D. Stiliadis and A. Varma. Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms. IEEE/ACM Transactions on Networking, 6(5):611--624, October 1998.
	26	S. Stuijk, M. Geilen, and T. Basten. Multiprocessor Resource Allocation for Throughput-Constrained Synchronous Dataflow Graphs. In Proc. Design Automation Conference (DAC), 2007.
	27	S. Tripakis, C. Pinello, A. Benveniste, A. Sangiovanni-Vincentelli, P. Caspi, and M. Di Natale. Implementing Synchronous Models on Loosely Time Triggered Architectures. IEEE Transactions on Computers, 2008.
	28	Underbit Technologies. Mad: Mpeg Audio Decoder. http://www.underbit.com/products/mad/, 2009.
	29	M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit. Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. In Proc. Design Automation Conference (DAC), June 2007.
	30	M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit. Modelling Run-Time Arbitration by Latency-Rate Servers in Dataflow Graphs. In Proc. Int'l Workshop on Software and Compilers for Embedded Systems (SCOPES), 2007.
	31	M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit. Buffer Capacity Computation for Throughput Constrained Streaming Applications with Data-Dependent Inter-Task Communication. In Proc. IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2008.