Stability Analysis Of Delay Dynamic Load Balancing System In Distributed Memory Architecture

Load balancing is a key issue in parallel computing area. The imbalance of load among computing nodes can intensely influence the performance of parallel computing. Classified by the immediacy of available resource information and task running state while scheduling, there are static and dynamic load balancing methods, in which, the dynamic method gradually becomes the hot researching area due to its flexibility and advantages in solving irregular problems.Time delay phenomenon commonly exists in parallel environment, specially, in distributed memory architecture, when executing load balancing algorithm, the parallel system will do large amounts of communications and transmissions for keeping the accuracy of information and migrating excess load. In these procedures, time delay will be brought in different extent without exception. Time delay can not only bring difficulties to collect and manage load information accurately but also causes some unstable oscillatory actions to the dynamic load balancing method, thus intensely affect the performance of parallel computing. So, how to analyze and reduce the effect of time delay becomes one of significant problem in dynamic load balancing area. In this case, this paper uses the linear time-delay system theory in control area to model and analyze DDLB system in distributed memory architecture, and decreases the effect of delay by using proper feedback control gain.First of all, aiming at the DDLB system in parallel environment, this paper proposes a frequency-domain model which is closer to the reality based on the original models. According to this model, a heterogeneous time-domain model which is equivalent is presented later. The two kinds of models consider the some actual factors (including the load can not be divided infinitely and the CPU queue length should be non-negative) in parallel environment fully, and describe the external disturbance which can influence the stability of DDLB system intensely. Meanwhile, the introduction of load balancing domain lets the model more flexible, and makes it can hold a compromise between the balancing speed and balancing quality. At last, according to the stability theory, some reasonable assumptions and definitions are proposed, and based on these, this paper transforms the time-domain model into the normal formula which is easy to analyze, thus, lays a foundation for the forthcoming analyzing work.Secondly, aiming at the proposed DDLB model, this paper presents a necessary and sufficient condition of DDLB system’s stability. The frequency domain analytical method is used to analyze the stability of homogeneous delay dynamic load balancing model. Laplace and some matrix transforms are used to deduce the transfer function matrix of system, and according to Routh-Hurwitz criterion, the asymptotic stable necessary and sufficient condition is obtained by analyzing the system closed-loop poles. Thus, this paper finds an approximate relation among load balancing gain, time delay and system scale. Meanwhile, according to the proposed stability condition, this paper presents an adaptive control method in the local optimization approach. Compared with original local optimization method, the proposed adaptive control method not only adjusts the load balancing gain real-timely and optimally, but also guarantees the stability of DDLB system, thus, makes the proposed method closer to the actual application.Thirdly, for describing the effect brought by different kinds of time delay on stability of dynamic load balancing system more clearly, this paper presents a sufficient condition of DDLB system’s stability in the constant time delay case. The time domain analytical method is used to analyze the stability of hetero-geneous delay dynamic load balancing model in constant time delay. By choosing proper Lyapunov-Krasovskii functionals and using Newton-Leibniz formula, Moon inequality and Schur complement property of the matrix, this paper obtains the asymptotic stable sufficient condition and enhances the convergence speed of system by introducing exponential stability. The obtained theoretical results are fit for the dynamic load balancing system whose change rate of time delay is smaller.Fourthly, aiming at the dynamic load balancing system which holds a bigger change rate of time delay, t this paper presents a sufficient condition of DDLB system’s stability in the varying time delay case. An exponential stable sufficient condition is obtained by choosing proper Lyapunov-Krasovskii functionals and using the basic property of integral equality, Jessen inequality and Schur complement property of the matrix. This condition is suitable for system whose time delay is changing in a certain interval and its change rate is bounded. Moreover, based on above-mentioned analyzing work, this paper transforms the obtained stable conditions into a normal LMI optimization problem and uses LMI tool box in Matlab to solve the theoretical load balancing gainLast but not least, aiming at the actual DDLB system, this paper gives a discrete-event simulation method based on multi-threads, and simulates different kinds of case according to theoretical analysis by this method. The experiments indicate that the optimal load balancing gain is in inverse proportion to communication/transmission delay and in direct proportional to system scale. Communication/transmission delay, system scale and DDI(Deterministic Degree of Information) have larger effects on stability of system and this kind of effects can be reduced by choosing proper load balancing gain. The theory introduced in this paper holds guiding effects on finding the optimal control law of DDLB and designing more practical dynamic load balancing algorithm in the delay surrounding.