Modeling parallel and distributed systems with finite workloads

In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling computer systems. However, the ability of Jackson networks to predict performance with system changes remains an open question, since they do not apply to systems where there are population size constraints. Also, the product-form solution of Jackson networks assumes steady-state and exponential service centers or certain specialized queueing discipline. In this paper, we present a transient model for Jackson networks that is applicable to any population size and any finite workload (no new arrivals). Using several non-exponential distributions we show to what extent the exponential distribution can be used to approximate other distributions and transient systems with finite workloads. When the number of tasks to be executed is large enough, the model approaches the product-form solution (steady-state solution). We also, study the case where the non-exponential servers have queueing (Jackson networks cannot be applied). Finally, we show how to use the model to analyze the performance of parallel and distributed systems.     

Computational algorithms for networks of queues with rejection blocking

Summary Open, closed and mixed queueing networks with reversible routing, multiple job classes and rejection blocking are investigated. In rejection blocking networks blocking event occurs when upon completion of its service of a particular station's server, a job attempts to proceed to its next station. If, at that moment, its destination station is full, the job is rejected. The job goes back to the server of the source station and immediately receives a new service. This is repeated until the next station releases a job and a place becomes available. In the model jobs may change their class membership and general service time distributions depending on the job class are allowed. Two station types are considered: Either the scheduling discipline is symmetric, in which case the service time distributions are allowed to be general and dependent on the job class or the service time distributions at a station are all identical exponential distributions, in which case more general scheduling disciplines are allowed. An exact product form solution for equilibrium state probabilities is presented. Using the exact product form solution of the equilibrium state distribution, algorithms for computation of performance measures, such as mean number of jobs and throughputs, are derived. The complexity of the algorithms is discussed.     

Higher-order distributional properties in closed queueing networks

In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form solution for queueing networks. Frequently, the coefficient of variation of the distributions encountered is well in excess of one, which would be its value for the exponential. For closed queueing networks with non-exponential servers there is no known general exact solution, and most, if not all, approximation methods attempt to account for the general service time distributions through their first two moments.We consider two simple closed queueing networks which we solve exactly using semi-numerical methods. These networks depart from the structure leading to a product-form solution only to the extent that the service time at a single node is non-exponential. We show that not only the coefficients of variation but also higher-order distributional properties can have an important effect on such customary steady-state performance measures as the mean number of customers at a resource or the resource utilization level in a closed network.Additionally, we examine the state that a request finds upon its arrival at a server, which is directly tied to the resulting quality of service. Although the well-known Arrival Theorem holds exactly only for product-form networks of queues, some approximation methods assume that it can be applied to a reasonable degree also in other closed queueing networks. We investigate the validity of this assumption in the two closed queueing models considered. Our results show that, even in the case when there is a single non-exponential server in the network, the state found upon arrival may be highly sensitive to higher-order properties of the service time distribution, beyond its mean and coefficient of variation.This dependence of mean numbers of customers at a server on higher-order distributional properties is in stark contrast with the situation in the familiar open M/G/1 queue. Thus, our results put into question virtually all traditional approximate solutions, which concentrate on the first two moments of service time distributions.     

Analysis of processor allocation in multiprogrammed,distributed-memory parallel processing systems

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy     

Computing performance bounds of fork-join parallel programs under amultiprocessing environment

We study a multiprocessing computer system which accepts parallel programs that have a fork-join computational paradigm. The multiprocessing computer system under study is modeled as K homogeneous servers, each with an infinite capacity queue. Parallel programs arrive at the multiprocessing system according to a series-parallel phase type interarrival process with mean arrival rate of h. Upon the program arrival, it forks into K-independent tasks and each task is assigned to an unique server. Each task's service time has a k-stage Erlang distribution with mean service time of λ. A parallel program is completed upon the completion of its last task. This kind of queuing model has no known closed form solution in the general (K⩾2) case. In this paper, we show that by carefully modifying the arrival and service distributions at some imbedded points in time, we can obtain tight performance bounds. We also provide a computational efficient algorithm for obtaining upper and lower bounds on the expected response time. The methodology is flexible and allows one to trade-off the tightness of the bounds and computational cost     

Performance analysis and scheduling of stochastic fork-join jobs ina multicomputer system

The authors model a parallel processing system comprising several homogeneous computers interconnected by a communication network. Jobs arriving to this system have a linear fork-join structure. Each fork of the job gives rise to a random number of tasks that can be processed independently on any of the computers. Since exact analysis of fork-join models is known to be intractable, the authors resort to obtaining analytical bounds to the mean job response time of the fork-join job. For jobs with a single fork-join and, probabilistic allocation of tasks of the job to the N processors, they obtain upper and lower bounds to the mean job response time. Upper bounds are obtained using the concept of associated random variables and are found to be a good approximation to the mean job response time. A simple lower bound is obtained by neglecting queueing delays. They also find two lower bounds that include queueing delays. For multiple fork-join jobs, they study an approximation based on associated random variables. Finally, two versions of the join-the-shortest-queue (JSQ) allocation policy (i.e., JSQ by batch and JSQ by task) are studied and compared, via simulations and diffusion limits     

On the convergence of the holistic analysis for EDF distributed systems

Dynamic scheduling techniques, and EDF (Earliest Deadline First) in particular, have demonstrated their ability to increase the schedulability of real time systems compared to fixed-priority scheduling. In distributed systems, the scheduling policies of the processing nodes tend to be the same as in stand-alone systems and, although few EDF networks exist, it is foreseen that dynamic scheduling will gradually develop into real-time networks. There are some response time analysis techniques for EDF scheduled distributed systems, mostly derived from the holistic analysis developed by Spuri. A major factor influencing the response time is the release jitter of each task, which is the maximum variation suffered by the release time of the task jobs. The convergence of the holistic analysis in the context of EDF distributed systems with shared resources had not been studied until now. There is a circular dependency between the task release jitter values, response times and the preemption level ceilings of shared resources. In this paper we present an extension of Spuri’s algorithm and we demonstrate that its iterative formulas are non-decreasing, even in the presence of shared resources. This result enables us to assert that the new algorithm converges towards a solution for the response times of the tasks and messages in a distributed system.¹     

The impact of task service time variability on gang scheduling performance in a two-cluster system

Gang scheduling is a common task scheduling policy for parallel and distributed systems which combines elements of space-sharing and time-sharing. In this paper we present a migration strategy which reduces the fragmentation in the schedule caused by gang scheduled jobs. We consider the existence of high priority jobs in the workload. These jobs need to be started immediately and they may interrupt a parallel job’s execution. A distributed system consisting of two homogeneous clusters is simulated to evaluate the performance for various workloads. We study the impact on performance of the variability in service time of the parallel tasks. Our simulation results indicate that the proposed strategy can result in a significant performance gain and that the performance improvement depends on the variability of gang tasks’ service time.     

A hybrid solution of fork/join synchronization in parallel queues

A new analysis technique, dynamic-bubblesort analysis, is introduced for general K-queue first-in-first-out HFJ (homogenous fork/join queuing) systems of K⩾2 . The dynamic-bubblesort model dynamically sorts the branches of the queues based on the number of the tasks waiting for synchronization in each branch. Jobs arrive with mean rate λ and a general arrival distribution. Upon arrival, a job forks into K tasks. Task k, k=1, 2, ..., K, is assigned to the kth queuing system, which is a first-in-first-out server with a general service distribution and an infinite capacity queue. A job leaves the HFJ system as soon as all its tasks complete their service. In other words, tasks corresponding to the same job are joined before departing the HFJ system. We obtain a general and simple hybrid solution which combines analysis and simulation for the mean response time that we denote by T_K. We obtain a very simple (as a function of T₁ and T₂ only) and general upper bound expression for T_K and we get an exact relationship between the cases for K=2 and 3. We evaluate our results by simulating 2, 3, ..., 99, and 100 queues for p=0.1, 0.2, ....0.8, and 0.9, each for four different HFJ cases, where ρ=λ/μ and μ is the average task service rate for a server. The maximum absolute offset for our hybrid solutions from all the simulations is less than 0.33 percent (1/300), which is a reasonable error ratio for simulation. The maximum offset for our upper bounds over all the simulations is 21 percent     

Performance analysis of parallel processing systems

A bulk arrival M/sup x//M/c queuing system is used to model a centralized parallel processing system with job splitting. In such a system, jobs wait in a central queue, which is accessible by all the processors, and are split into independent tasks that can be executed on separate processors. The job response-time consists of three components: queuing delay, service time, and synchronization delay. An expression for the mean job response-time is obtained for this centralized parallel-processing system. Centralized and distributed parallel-processing systems (with and without job-splitting) are considered and their performances compared. Furthermore, the effects of parallelism and overheads due to job-splitting are investigated.<>     

Analysis of a shared-memory multiprocessor via a novel queuing model

The study on the delay effects caused by memory interference in a parallel processing system with shared memory was implemented using a Machine Repair queuing Model (MRM). In our model the Repair Server has a constant service time and the parallel operating Job Servers have negative exponential service time distributions. Mean Value Analysis (MVA) was used to solve this particular MRM. However, to apply MVA successfully in this model with heterogeneous servers, the response time equation of the Repair Server has been modified. This modified equation was derived by combining mathematics and heuristics. To check this novel method on its accuracy, comparisons were made with as many as 1200 simulations, having a wide spread of model parameters. The results are extremely good, differences between the analytical results and the simulations are always smaller than 2%.     

Piecewise-linear networks with multimode service strategies

Consideration is given to open and closed queueing networks with Markov routing and symmetric service procedures. Single-line nodes can operate in several modes; the switching time from one mode to another is of exponential distribution. The switching occurs only to nearby modes. The quantity of work on service of the arriving customer is a random quantity with an arbitrary distribution function. For open networks, the input flow is the simplest. The invariancy of the stationary distribution of network states with respect to the functional form of distributions of quantities of works at fixed first moments is established.     

网络安全；无线传感器网络；入侵检测；代理；智能优化 ；粒子群优化

文章提出了一种专门针对无线传感器网络的轻量级本地入侵检测系统(单机IDS)的设计方案.采用监视、检测、响应和控制4个代理模块,1个数据库连接接口和1个响应接口实现这一系统;每个代理模块独立运行,各自执行系统分配的任务.在检测代理模块实现中,文章提出采用一种基于GM(1,1)的智能优化预测算法作为检测技术,经实验分析该算法在建模数据较少的情况下仍具有较高的准确性.     

Sliding mode control for two-time scale systems: stability issues

The paper presents some results on global exponential stability of linear time invariant systems with different time scales. The full system is decomposed in two reduced ones by means of singular perturbations and a smooth approximation of a Variable Structure Control is synthesized for each of them using Reaching Law approach. The global closed loop stability is then proved for the whole system using Lyapunov methods and a particular state space decomposition. Moreover a literal form for ε∗ (a parameter which measures the minimum separation between time scales) is derived.     

Performance of gang scheduling strategies in a parallel system

In this paper we study job scheduling performance in a partitionable parallel system. Jobs consist of parallel tasks scheduled to execute concurrently on processor partitions, where each task starts at the same time and computes at the same pace. The performance of different scheduling schemes is compared over various workloads. The impact of the variability of tasks service time is also studied. Various performance metrics are examined. The objective is to achieve good overall performance and also small scheduling overhead. Simulated results reveal that periodic job scheduling and also scheduling which depends on the number of job insertions in the queue can succeed these goals.     

Dynamic control of service rates in queuing networks

A method for dynamic control of service rates in closed exponential queuing networks is proposed. The performance of queuing networks with the service-rate control is analyzed, and the main steady-state network characteristics are computed using an analytic approximation. A simple example of a queuing network with controlled service rates is considered as an illustration. The efficiency of the service-rate control is confirmed by Monte Carlo simulations, which, as a by-product, also show acceptable accuracy of our analytical approximations.     

Perturbation analysis of closed queueing networks with generalservice time distributions

Perturbation analysis of closed queuing networks with nonexponential service time distributions is studied. Perturbation analysis formulas using realization probabilities are extended to these networks. A perturbation generation function, which generalizes the perturbation generation rule, is defined. equations for realization probability and formulas for sensitivity of the system throughput with respect to service time distribution parameters are presented. The formulas provide an analytical method of calculating throughput sensitivity and an explanation of the application of perturbation analysis algorithms for networks with general service time distributions. The author focuses on the extension of concepts and intuitive explanations of the formulas rather than on mathematical derivations     

基于干扰观测器的一类不确定非线性系统自适应二阶动态terminal滑模控制

针对一类不确定非线性系统的跟踪控制问题,在考虑建模误差、参数不确定和外部干扰情况下,以其拥有良好的跟踪性能以及强鲁棒性为目标,提出基于回归扰动模糊神经网络干扰观测器(recurrent perturbation fuzzy neural networks disturbance observer,RPFNNDO)的鲁棒自适应二阶动态terminal滑模控制策略.将回归网络、模糊神经网络和sine-cosine扰动函数各自优势相结合,给出一种回归扰动模糊神经网络结构,提出RPFNNDO设计方法,保证干扰估计准确性;构造基于带有指数函数滑模面的二阶快速terminal滑模面,给出其控制器设计过程,避免了滑模到达阶段、传统滑模的抖振问题,采用具有指数收敛的鲁棒项抑制干扰估计误差对系统跟踪性能的影响,利用Lyapunov理论证明闭环系统的稳定性;将该方法应用于混沌陀螺系统同步控制仿真实验,结果表明所提方法的有效性.     

计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.     

A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier’s total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier’s total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.