Journal of Information Organization


Vol No. 14 ,Issue No. 1 2024

Computational Offloading for Real-Time Tasks in Embedded Systems
Anas Toma and Jian-Jia Chen
Department of Informatics, Karlsruhe Institute of Technology Germany., Department of Informatics, TU Dortmund University Germany
Abstract: Computation Offloading has been developed to enhance the performance of Embedded Systems by transferring the execution of specific tasks, especially computationally intensive tasks, to Servers or clouds. This paper explores computational offloading for real-time tasks in embedded systems, provided the servers guarantee response time. To decide which tasks to offload to get results in real-time, we consider frame-based real-time tasks with equivalent periods and relative deadlines. When an execution order is provided for the tasks, the problems can be solved in linear time; however, when no execution order is provided, we prove the problems to be NP-completable. To derive feasible schedules if they exist, we develop a pseudo-projective-time algorithm. We also develop an approximation scheme to trade off the algorithm’s error and complexity. We extend our algorithms to minimize the periods/ relative deadlines of the tasks for maximum performance. The algorithms are tested using a case study for a surveillance system and synthesised benchmarks.
Keywords: Embedded Systems, NP-Complete, Real-Time Systems, Time Alg Computational Offloading for Real-Time Tasks in Embedded Systems
DOI:https://doi.org/10.6025/jio/2024/14/1/34-55
Full_Text   PDF 3.74 MB   Download:   10  times
References:

[1] Bradski, Gary R., 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.
[2] Buttazzo, Giorgio C. “Hard Real-time Computing Systems.” Springer US, 2011. URL: http:// www.springer.com/978-1-4614-0675-4.
[3] Ferreira, Luis Lino, Guilherme D. Silva, and Luís Miguel Pinho. “Service offloading in adaptive real-time systems.” In Zoubir Mammeri (Ed.), IEEE 16th Conference on Emerging Technologies & Factory Automation (ETFA’11), Toulouse, France, September 5–9, 2011, pp. 1–6. IEEE, 2011. doi:10.1109/ETFA.2011.6059236.
[4] Garey, M. R., and David S. Johnson. “Computers and Intractability: A Guide to the Theory of NP-Completeness.” W. H. Freeman, 1979.
[5] Gonzalez, Rafael C., and Richard E. Woods. “Digital Image Processing (3rd Edition).” PrenticeHall, Inc., NJ, USA, 2008. URL: http://www.imageprocessingplace.com/.
[6] Hong, Yu-Ju, Karthik Kumar, and Yung-Hsiang Lu. “Energy efficient content-based image retrieval for mobile systems.” In International Symposium on Circuits and Systems (ISCAS’09), Taipei, Taiwan, May 24–17, 2009, pp. 1673–1676. IEEE, 2009. doi:10.1109/ISCAS.2009.5118095.
[7] IFR International Federation of Robotics. “Service Robot Statistics, September 2011.” URL: http://www.ifr.org/service-robots/statistics/.
[8] Kovachev, Dejan, Tian Yu, and Ralf Klamma. “Adaptive computation offloading from mobile devices into the cloud.” In 10th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA’12), Leganes, Madrid, Spain, July 10–13, 2012, pp. 784–791. IEEE, 2012. doi:10.1109/ISPA.2012.115.
[9] Li, Zhiyuan, Cheng Wang, and Rong Xu. “Computation offloading to save energy on handheld devices: a partition scheme.” In 2001 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES’01), 2001, pp. 238–246. URL: http://portal.acm.org/ citation.cfm?id=502217.502257.
[10] Li, Zhiyuan, Cheng Wang, and Rong Xu. “Task allocation for distributed multimedia processing on wirelessly networked handheld devices.” In 16th International Parallel and Distributed Processing Symposium (IPDPS’02), Fort Lauderdale, FL, USA, April 15–19, 2002, CD-ROM/Abstracts Proceedings. IEEE Computer Society, 2002. doi:10.1109/IPDPS.2002.1015589.
[11] Lowe, David G. “Object recognition from local scale-invariant features.” In International Conference on Computer Vision (ICCV’99), Vol. 2, 1999, pp. 1150–1157. URL: http://dl.acm.org/ citation.cfm?id=850924.851523.
[12] Nimmagadda, Yamini, Karthik Kumar, Yung-Hsiang Lu, and C. S. George Lee. “Real-time moving object recognition and tracking using computation offloading.” In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’10), Taipei, Taiwan, October 18–22, 2010, pp. 2449–2455. IEEE, 2010. doi:10.1109/IROS.2010.5650303.
[13] Piccardi, Massimo. “Background subtraction techniques: a review.” In 2004 IEEE International Conference on Systems, Man & Cybernetics (ICSMC’04), The Hague, Netherlands, October 10– 13, 2004, pp. 3099–3104. IEEE, 2004. doi:10.1109/ICSMC.2004.1400815.
[14] Spuri, Marco, and Giorgio C. Buttazzo. “Efficient aperiodic service under earliest deadline scheduling.” In 15th IEEE Real-Time Systems Symposium (RTSS’94), San Juan, Puerto Rico, December 7–9, 1994, pp. 2–11. IEEE Computer Society, 1994. doi:10.1109/REAL.1994.342735.
[15] Spuri, Marco, and Giorgio C. Buttazzo. “Scheduling aperiodic tasks in dynamic priority systems.” Real-Time Systems, 10(2):179–210, 1996. doi:10.1007/BF00360340.
[16] Wolski, Richard, Selim Gurun, Chandra Krintz, and Daniel Nurmi. “Using bandwidth data to make computation offloading decisions.” In 22nd IEEE International Symposium on Parallel and Distributed Processing (IPDPS’08), Miami, Florida USA, April 14–18, 2008, pp. 1–8. IEEE, 2008. doi:10.1109/IPDPS.2008.4536215.
[17] Xian, Changjiu, Yung-Hsiang Lu, and Zhiyuan Li. “Adaptive computation offloading for energy conservation on battery-powered systems.” In 13th International Conference on Parallel and Distributed Systems (ICPADS’07), Hsinchu, Taiwan, December 5–7, 2007, pp. 1–8. IEEE Computer Society, 2007. doi:10.1109/ICPADS.2007.4447724.