Prediction of dynamical, nonlinear, and unstable process behavior
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