Abstract
Applications that process continuous streams of data, e.g., sensor signals, video images, network packets, etc. are well-suited for pipelined execution on multicore processors. In many cases, however, the applications are subject to real-time constraints, especially in embedded systems. Besides maximizing the throughput, it is therefore important to minimize deviations in the timing. To solve this problem, we propose a method for self-timed scheduling and parallel execution of stream-based applications in soft real-time environments. Our experimental results show significantly lower latencies compared to state-of-the-art approaches, while achieving high throughput.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Sriram, S., Bhattacharyya, S.: Embedded Multiprocessors: Scheduling and Synchronization, 2nd edn. CRC Press (2009)
Lee, E., Ha, S.: Scheduling strategies for multiprocessor DSP. In: Global Telecommunications Conference, Dallas, TX, USA. IEEE (1989)
Davis, R., Burns, A.: A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems. Technical Report YCS-2009-443, University of York, Department of Computer Science (2009)
Sinnen, O.: Task Scheduling for Parallel Systems. Wiley (2007)
Kwok, Y.K., Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys 31, 406–471 (1999)
Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. In: Annual Symposium on Foundations of Computer Science (FOCS), Santa Fe, NM, USA, pp. 356–368. IEEE (1994)
Mattson, T., Sanders, B., Massingill, B.: Patterns for Parallel Programming. Addison Wesley (2005)
Ortega-Arjona, J.: Patterns for Parallel Software Design. Wiley (2010)
Stephens, R.: A survey of stream processing. Acta Informatica 34(7), 491–541 (1997)
Aldinucci, M., Torquati, M., Meneghin, M.: FastFlow: Efficient parallel streaming applications on multi-core. Technical Report TR-09-12, Università di Pisa, Dipartimento di Informatica, Italy (September 2009)
Otto, F., Pankratius, V., Tichy, W.F.: XJava: Exploiting parallelism with object-oriented stream programming. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 875–886. Springer, Heidelberg (2009)
Thies, W., Karczmarek, M., Amarasinghe, S.: StreamIt: A language for streaming applications. In: Nigel Horspool, R. (ed.) CC 2002. LNCS, vol. 2304, pp. 179–196. Springer, Heidelberg (2002)
MacDonald, S., Szafron, D., Schaeffer, J.: Rethinking the pipeline as object-oriented states with transformations. In: High-Level Parallel Programming Models and Supportive Environments (HIPS), Santa Fe, NM, USA, pp. 12–21. IEEE Computer Society (2004)
Bokhari, S.: Partitioning problems in parallel, pipelined, and distributed computing. IEEE Transactions on Computers 37(1), 48–57 (1988)
Hoang, P., Rabaey, J.: Scheduling of DSP programs onto multiprocessors for maximum throughput. IEEE Transactions on Signal Processing 31(6), 2225–2235 (1993)
Banerjee, S., Hamada, T., Chau, P., Fellman, R.: Macro pipelining based scheduling on high performance heterogeneous multiprocessor systems. IEEE Transactions on Signal Processing 43(6), 1468–1484 (1995)
Wu, M.Y., Gajski, D.: Hypertool: A programming aid for message-passing systems. IEEE Transactions on Parallel and Distributed Systems 1, 330–343 (1990)
Kwok, Y.K., Ahmad, I.: Benchmarking and comparison of the task graph scheduling algorithms. Journal of Parallel and Distributed Computing 59(3), 381–422 (1999)
Schuele, T.: A coordination language for programming embedded multi-core systems. In: International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Hiroshima, Japan. IEEE (2009)
Schuele, T.: Efficient parallel execution of streaming applications on multi-core processors. In: International Conference on Parallel, Distributed and Network-Based Processing (PDP), Ayia Napa, Cyprus. IEEE (2011)
Lee, E., Parks, T.: Dataflow process networks. Proceedings of the IEEE 83(5), 773–801 (1995)
Ungerer, T., Cazorla, F., Sainrat, P., Bernat, G., Petrov, Z., Cassé, H., Rochange, C., Quinones, E., Uhrig, S., Gerdes, M., Guliashvili, I., Houston, M., Kluge, F., Metzlaff, S., Mische, J., Paolieri, M., Wolf, J.: MERASA: Multi-core execution of hard real-time applications supporting analysability. IEEE Micro 30(5), 66–75 (2010)
Karcher, T., Schaefer, C., Pankratius, V.: Auto-tuning support for manycore applications: perspectives for operating systems and compilers. ACM SIGOPS Operating Systems Review Archive 43(2), 96–97 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lucas, L., Schuele, T., Schwitzer, W. (2013). Self-timed Scheduling and Execution of Nonlinear Pipelines with Parallel Stages. In: Lourenço, J.M., Farchi, E. (eds) Multicore Software Engineering, Performance, and Tools. MUSEPAT 2013. Lecture Notes in Computer Science, vol 8063. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39955-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-39955-8_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39954-1
Online ISBN: 978-3-642-39955-8
eBook Packages: Computer ScienceComputer Science (R0)