Computation Offloading for Frame-Based Real-Time Tasks under Given Server Response Time Guarantees

Anas S. M. Toma, Jian-Jia Chen

Abstract


Computation offloading has been adopted to improve the performance of embedded systems by offloading the computation of some tasks, especially computation-intensive tasks, to servers or clouds. This paper explores computation offloading for real-time tasks in embedded systems, provided given response time guarantees from the servers, to decide which tasks should be offloaded to get the results in time. We consider frame-based real-time tasks with the same period and relative deadline. When the execution order of the tasks is given, the problem can be solved in linear time. However, when the execution order is not specified, we prove that the problem is NP-complete. We develop a pseudo-polynomial-time algorithm for deriving feasible schedules, if they exist.  An approximation scheme is also developed to trade the error made from the algorithm and the complexity. Our algorithms are extended to minimize the period/relative deadline of the tasks for performance maximization. The algorithms are evaluated with a case study for a surveillance system and synthesized benchmarks.

Keywords


Computation offloading; Task scheduling; Real-time systems

Full Text:

PDF

References


Gary R. Bradski and Adrian Kaehler. Learning OpenCV – computer vision with the OpenCV library: software that sees. O’Reilly, 2008. URL: http://www.oreilly.de/catalog/9780596516130/index.html.

Giorgio C. Buttazzo. Hard Real-time Computing Systems. Springer US, 2011. URL: http://www.springer.com/978-1-4614-0675-4.

Luis Lino Ferreira, Guilherme D. Silva, and Luís Miguel Pinho. Service offloading in adaptive real-time systems. In Zoubir Mammeri, editor, IEEE 16th Conf. on Emerging Technologies & Factory Automation (ETFA’11), Toulouse, France, September 5–9, 2011, pages 1–6. IEEE, 2011. doi:10.1109/ETFA.2011.6059236.

M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

Rafael C. Gonzalez and Richard E. Woods. Digital Image Processing (3rd Edition). Prentice-Hall, Inc., NJ, USA, 2008. URL: http://www.

imageprocessingplace.com/.

Yu-Ju Hong, Karthik Kumar, and Yung-Hsiang Lu. Energy efficient content-based image retrieval for mobile systems. In Int’l Symp. on Circuits and Systems (ISCAS’09), 24–17 May 2009, Taipei, Taiwan, pages 1673–1676. IEEE, 2009. doi:10.1109/ISCAS.2009.5118095.

IFR International Federation of Robotics. Service Robot Statistics, September 2011. URL: http://www.ifr.org/service-robots/statistics/.

Dejan Kovachev, Tian Yu, and Ralf Klamma. Adaptive computation offloading from mobile devices into the cloud. In 10th IEEE Int’l Symp. on Parallel and Distributed Processing with Applications (ISPA’12), Leganes, Madrid, Spain, July 10–13, 2012, pages 784–791. IEEE, 2012. doi:10.1109/ISPA.2012.115.

Zhiyuan Li, Cheng Wang, and Rong Xu. Computation offloading to save energy on handheld devices: a partition scheme. In 2001 Int’l Conf. on Compilers, Architecture, and Synthesis for Embedded Systems (CASES’01), pages 238–246, 2001. URL: http://portal.acm.org/citation.cfm?id=502217.502257.

Zhiyuan Li, Cheng Wang, and Rong Xu. Task allocation for distributed multimedia processing on wirelessly networked handheld devices. In 16th Int’l Parallel and Distributed Processing Symp. (IPDPS’02), 15–19 April 2002, Fort Lauderdale, FL, USA, CD-ROM/Abstracts Proceedings. IEEE Computer Society, 2002. doi:10.1109/IPDPS.2002.1015589.

David G. Lowe. Object recognition from local scale-invariant features. In Int’l Conf. on Computer Vision (ICCV’99), Vol. 2, pages 1150–1157, 1999. URL: http://dl.acm.org/citation.cfm?id=850924.851523.

Yamini Nimmagadda, Karthik Kumar, Yung-Hsiang Lu, and C. S. George Lee. Real-time moving object recognition and tracking using computation offloading. In 2010 IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS’10), October 18–22, 2010, Taipei, Taiwan, pages 2449–2455. IEEE, 2010. doi:10.1109/IROS.2010.5650303.

Massimo Piccardi. Background subtraction techniques: a review. In 2004 IEEE Int’l Conf. on Systems, Man & Cybernetics (ICSMC’04), The Hague, Netherlands, 10–13 October 2004, pages 3099–3104. IEEE, 2004. doi:10.1109/ICSMC.2004.1400815.

Marco Spuri and Giorgio C. Buttazzo. Efficient aperiodic service under earliest deadline scheduling. In 15th IEEE Real-Time Systems Symp. (RTSS’94), San Juan, Puerto Rico, December 7–9, 1994, pages 2–11. IEEE Computer Society, 1994. doi:10.1109/REAL.1994.342735.

Marco Spuri and Giorgio C. Buttazzo. Scheduling aperiodic tasks in dynamic priority systems. Real-Time Systems, 10(2):179–210, 1996. doi:10.1007/BF00360340.

Richard Wolski, Selim Gurun, Chandra Krintz, and Daniel Nurmi. Using bandwidth data to make computation offloading decisions. In 22nd IEEE Int’l Symp. on Parallel and Distributed Processing (IPDPS’08), Miami, Florida USA, April 14–18, 2008, pages 1–8. IEEE, 2008. doi:10.1109/IPDPS.2008.4536215.

Changjiu Xian, Yung-Hsiang Lu, and Zhiyuan Li. Adaptive computation offloading for energy conservation on battery-powered systems. In 13th Int’l Conf. on Parallel and Distributed Systems (ICPADS’07), December 5–7, 2007, Hsinchu, Taiwan, pages 1–8. IEEE Computer Society, 2007. doi:10.1109/ICPADS.2007.4447724.




DOI: https://doi.org/10.4230/LITES-v001-i002-a002

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v001-i002-a002-pdf7

Copyright (c) 2014 Anas S. M. Toma, Jian-Jia Chen

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy