NWSLite: A general-purpose, nonparametric prediction utility for embedded systems

ABSTRACT

Time series-based prediction methods have a wide range of uses in embedded systems. Many OS algorithms and applications require accurate prediction of demand and supply of resources. However, configuring prediction algorithms is not easy, since the dynamics of the underlying data requires continuous observation of the prediction error and dynamic adaptation of the parameters to achieve high accuracy. Current prediction methods are either too costly to implement on resource-constrained devices or their parameterization is static, making them inappropriate and inaccurate for a wide range of datasets. This paper presents NWSLite, a prediction utility that addresses these shortcomings on resource-restricted platforms.

REFERENCES

• 1: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl , P. Venkat Rangan, Characterizing user behavior and network performance in a public wireless LAN, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 2: Rajesh Krishna Balan , Mahadev Satyanarayanan , So Young Park , Tadashi Okoshi, Tactics-based remote execution for mobile computing, Proceedings of the 1st international conference on Mobile systems, applications and services, p.273-286, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066125]
• 3: Francine D. Berman , Rich Wolski , Silvia Figueira , Jennifer Schopf , Gary Shao, Application-level scheduling on distributed heterogeneous networks, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369109]
• 4: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 5: Bottomley, G. and Alexander, S. 1991. A novel approach for stabilizing recursive least squares filters. IEEE Trans. Signal Processing 39, 1770--1779.
• 6: Burger, D. and Austin, T. 1997. The simplescalar tool set, version 2.0. Tech. Rept. 1342, UW Madison Computer Sciences. June.
• 7: Stuart K. Card , Allen Newell , Thomas P. Moran, The Psychology of Human-Computer Interaction, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1983
• 8: Compaq Computer Corporation. iPAQ Pocket PC. Compaq Computer Corporation. http://www.compaq.com/products/handhelds/pocketpc/.
• 9: Jason Nelson Flinn , Mahadev Satyanarayanan, Extending mobile computer battery life through energy-aware adaptation, Carnegie Mellon University, Pittsburgh, PA, 2001
• 10: Jason Flinn , M. Satyanarayanan, Energy-aware adaptation for mobile applications, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.48-63, December 12-15, 1999, Charleston, South Carolina, United States
• 11: Jason Flinn , Dushyanth Narayanan , M. Satyanarayanan, Self-Tuned Remote Execution for Pervasive Computing, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.61, May 20-22, 2001
• 12: Jason Flinn , SoYoung Park , M. Satyanarayanan, Balancing Performance, Energy, and Quality in Pervasive Computing, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.217, July 02-05, 2002
• 13: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 14: GLVU 2002. GLVU source code and documentation. http://www.cs.unc.edu/~walk/software/glvu/.
• 15: Kinshuk Govil , Edwin Chan , Hal Wasserman, Comparing algorithm for dynamic speed-setting of a low-power CPU, Proceedings of the 1st annual international conference on Mobile computing and networking, p.13-25, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215546]
• 16: GrADS. The grid application development software project (GrADS). http://hipersoft.cs.rice.edu/grads/.
• 17: Dirk Grunwald , Charles B. Morrey, III , Philip Levis , Michael Neufeld , Keith I. Farkas, Policies for dynamic clock scheduling, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.6-6, October 22-25, 2000, San Diego, California
• 18: Gurun, S., Krintz, C., and Wolski, R. 2003. Efficient Prediction. Tech. Rept., 2003-34, University of California, Santa Barbara.
• 19: Selim Gurun , Chandra Krintz , Rich Wolski, NWSLite: a light-weight prediction utility for mobile devices, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990068]
• 20: Minkyong Kim , Brian Noble, Mobile network estimation, Proceedings of the 7th annual international conference on Mobile computing and networking, p.298-309, July 2001, Rome, Italy [doi>10.1145/381677.381705]
• 21: Kremer, U., Hicks, J., and Rehg, J. M. 2001. A compilation framework for power and energy management on mobile computers. In International Workshop on Languages and Compilers for Parallel Computing (LCPC'01).
• 22: Chandra Krintz , Ye Wen , Rich Wolski, Application-level prediction of battery dissipation, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013292]
• 23: Zhiyuan Li , Cheng Wang , Rong Xu, Computation offloading to save energy on handheld devices: a partition scheme, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502257]
• 24: Dushyanth Narayanan , M. Satyanarayanan, Operating system support for mobile interactive applications, Carnegie Mellon University, Pittsburgh, PA, 2002
• 25: Dushyanth Narayanan , M. Satyanarayanan, Predictive Resource Management for Wearable Computing, Proceedings of the 1st international conference on Mobile systems, applications and services, p.113-128, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1189041]
• 26: Brian D. Noble , M. Satyanarayanan , Dushyanth Narayanan , James Eric Tilton , Jason Flinn , Kevin R. Walker, Agile application-aware adaptation for mobility, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.276-287, October 05-08, 1997, Saint Malo, France
• 27: NWS. The Network Weather Service Home page -- http://nws.cs.ucsb.edu.
• 28: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 29: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, Saving portable computer battery power through remote process execution, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.1, p.19-26, January 1998 [doi>10.1145/584007.584008]
• 30: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, The remote processing framework for portable computer power saving, Proceedings of the 1999 ACM symposium on Applied computing, p.365-372, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298385]
• 31: Sigcomm01traces. Wireless LAN Traces from ACM SIGCOMM'01. http://ramp.ucsd.edu/pawn/sigcomm-trace/.
• 32: Amit Sinha , Anantha Chandrakasan, Energy efficient operating systems and software, Massachusetts Institute of Technology, 2001
• 33: Amit Sinha , Anantha P. Chandrakasan, Dynamic Voltage Scheduling Using Adaptive Filtering of Workload Traces, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.221, January 03-07, 2001
• 34: Neil Spring , Rich Wolski, Application level scheduling of gene sequence comparison on metacomputers, Proceedings of the 12th international conference on Supercomputing, p.141-148, July 1998, Melbourne, Australia [doi>10.1145/277830.277860]
• 35: Sezgin Sucu , Chandra Krintz, ACE: A Resource-Aware Adaptive Compression Environment, Proceedings of the International Conference on Information Technology: Computers and Communications, p.183, April 28-30, 2003
• 36: Martin Swany , Rich Wolski, Representing Dynamic Performance Information in Grid Environments with the Network Weather Service, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.48, May 21-24, 2002
• 37: Mark Weiser , Brent Welch , Alan Demers , Scott Shenker, Scheduling for reduced CPU energy, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.2-es, November 14-17, 1994, Monterey, California
• 38: Willmott, A. J. 1999. Radiator source code and online documentation. http://www.cs.cmu.edu/~ajw/software/.
• 39: Rich Wolski, Dynamically forecasting network performance using the Network Weather Service, Cluster Computing, v.1 n.1, p.119-132, 1998 [doi>10.1023/A:1019025230054]
• 40: Wolski, R. 1999. Predicting CPU availability on the computational grid using the network weather service. J. Parallel Processing Lett. 9, 4, 227--241.
• 41: Rich Wolski, Experiences with predicting resource performance on-line in computational grid settings, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773064]
• 42: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
• 43: Peter Young, Recursive estimation and time-series analysis: an introduction, Springer-Verlag New York, Inc., New York, NY, 1984

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

General Terms:
Measurement, Performance

Keywords:
CPU availability estimation, Computation offloading, embedded systems, network performance estimation, prediction algorithms