Prediction of dynamical, nonlinear, and unstable process behavior

Springer Science and Business Media LLC - Tập 49 - Trang 22-41 - 2008
Rodrigo F. de Mello1, Laurence T. Yang2
1Institute of Mathematics and Computer Science, University of São Paulo, São Carlos, Brazil
2Department of Computer Science, St Francis Xavier University, Antigonish, Canada

Tóm tắt

Process scheduling techniques consider the current load situation to allocate computing resources. Those techniques make approximations such as the average of communication, processing, and memory access to improve the process scheduling, although processes may present different behaviors during their whole execution. They may start with high communication requirements and later just processing. By discovering how processes behave over time, we believe it is possible to improve the resource allocation. This has motivated this paper which adopts chaos theory concepts and nonlinear prediction techniques in order to model and predict process behavior. Results confirm the radial basis function technique which presents good predictions and also low processing demands show what is essential in a real distributed environment.

Tài liệu tham khảo

Abarbanel HDI, Brown R, Sidorowich JJ, Tsimring LS (1993) The analysis of observed chaotic data in physical systems. Rev Mod Phys 65:1331–1392 Amir Y (2000) An opportunity cost approach for job assignment in a scalable computing cluster. IEEE Trans Parallel Distrib Syst 11(7):760–768 Brecht T, Guha K (1996) Using parallel program characteristics in dynamic processor allocation policies. Perform Eval 27/28(4):519–539 Casdagli M (1989) Nonlinear prediction of chaotic time series. Physica D: Nonlinear Phenom 35:335–356. May de Mello RF, Senger LJ (2004) A new migration model based on the evaluation of processes load and lifetime on heterogeneous computing environments. In: International symposium on computer architecture and high performance computing—SBAC-PAD. IEEE Computer Society, pp 222–227 de Mello RF, Andrade Filho JA, Senger LJ, Yang LT (2007) Routega: a grid load balancing algorithm with genetic support. In: AINA, pp 885–892 Eckmann J-P, Ruelle D (1985) Ergodic theory of chaos and strange attractors. Rev Mod Phys 57:617–656 Edmonds AN (1996) Time series prediction using supervised learning and tools from chaos theory. PhD thesis, University of Luton, December 1996 Elert G (2005) The chaos hypertextbook—measuring chaos, August 2005 Elmer F-J (1998) The Lyapunov exponent, July 1998 Fraser AM, Swinney HL (1986) Independent coordinates for strange attractors from mutual information. Phys Rev A 33(2):1134–1140 Harchol-Balter M, Downey AB (1997) Exploiting process lifetimes distributions for dynamic load balancing. ACM Trans Comput Syst 15(3):253–285 Jackson EA (1989) Perspectives of nonlinear dynamics. Cambridge University Press, Cambridge Kaplan I (2003) Estimating the Hurst exponent. Available at http://www.bearcave.com/misl/misl_tech/wavelets/hurst/index.html, May 2003 Kennel M (2002) The multiple-dimensions mutual information program, March 2002 Kennel MB, Brown R, Abarbanel HDI (1992) Determining embedding dimension for phase-space reconstruction using a geometrical construction. Phys Rev A 45(6):3403–3411 Lorenz EN (1963) Deterministic nonperiodic flow. J Atmos Sci 20:130–141 Mané R (1980) On the dimension of the compact invariant sets of certain nonlinear maps. Springer, Berlin Medio A, Gallo G (1993) Chaotic dynamics: theory and applications to economics. Cambridge University Press, Cambridge Naik VK, Setia SK, Squillante MS (1997) Processor allocation in multiprogrammed distributed-memory parallel computer systems. J Parallel Distrib Comput 47(1):28–47 Mané R, Petascale data store institute, available at http://pdsi.nersc.gov/benchmarks.htm, December 2007 Rosenstein MT, Collins JJ, De Luca CJ (1993) A practical method for calculating largest Lyapunov exponents from small data sets. Physica D 65:117–134 Senger LJ, de Mello RF, Santana MJ, Santana RHC, Yang LT (2005) Improving scheduling decisions by using knowledge about parallel applications resource usage. In: HPCC, pp 487–498 Sevcik KC (1989) Characterizations of parallelism in applications and their use in scheduling. Perform Eval Rev 17(1):171–180 Shefler WC (1988) Statistics: concepts and applications. Benjamin/Cummings, Redwood City Shenshi G, Zhiqian W, Jitai C (1999) The fractal research and predicating on the times series of sunspot relative number. Appl Math Mech 20(1):84–89 Shivaratri NG, Krueger P, Singhal M (1992) Load distributing for locally distributed systems. IEEE Comput 25(12):33–44 Takens F (1980) Detecting strange attractors in turbulence. In: Dynamical systems and turbulence. Springer, Berlin, pp 366–381 Valle V Jr (2000) Chaos, complexity and deterrence. Technical report, National War College, April 2000 Zey C (2006) NIST/SEMATECH e-handbook of statistical methods. May 2006