Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems

Divisible load theory is a methodology involving the linear and continuous modeling of partitionable computation and communication loads for parallel processing. It adequately represents an important class of problems with applications in parallel and distributed system scheduling, various types of data processing, scientific and engineering computation, and sensor networks. Solutions are surprisingly tractable. Research in this area over the past decade is described.     

Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs

In this paper, we consider the problem of scheduling divisible loads on arbitrary graphs with the objective to minimize the total processing time of the entire load submitted for processing. We consider an arbitrary graph network comprising heterogeneous processors interconnected via heterogeneous links in an arbitrary fashion. The divisible load is assumed to originate at any processor in the network. We transform the problem into a multi-level unbalanced tree network and schedule the divisible load. We design systematic procedures to identify and eliminate any redundant processor–link pairs (those pairs whose consideration in scheduling will penalize the performance) and derive an optimal tree structure to obtain an optimal processing time, for a fixed sequence of load distribution. Since the algorithm thrives to determine an equivalent number of processors (resources) that can be used for processing the entire load, we refer to this approach as resource-aware optimal load distribution (RAOLD) algorithm. We extend our study by applying the optimal sequencing theorem proposed for single-level tree networks in the literature for multi-level tree for obtaining an optimal solution. We evaluate the performance for a wide range of arbitrary graphs with varying connectivity probabilities and processor densities. We also study the effect of network scalability and connectivity. We demonstrate the time performance when the point of load origination differs in the network and highlight certain key features that may be useful for algorithm and/or network system designers. We evaluate the time performance with rigorous simulation experiments under different system parameters for the ease of a complete understanding.     

A Novel Optimal Load Distribution Algorithm for Divisible Loads

A new model for divisible load problem is introduced. Its characteristics are analyzed. Optimal load distribution algorithms on the new model are presented for the tree-network and linear network. Applications that fit our model are briefly described. We show that our model outperforms the existing model such as Cheng–Robertazzi model. We show that the linear model is equivalent to a single-level tree network if the intermediate processors do not follow the store-and-forward communication model, but they follow the store-and-bypass model. This paper introduces the concept of store-and-bypass for divisible load theory.     

Divisible Load Scheduling in Systems with Limited Memory

In this work we consider scheduling divisible loads on a distributed computing system with limited available memory. The communication delays and heterogeneity of the system are taken into account. The problem studied consists in finding such a distribution of the load that the communication and computation time is the shortest possible. A new robust method is proposed to solve the problem of finding optimal distribution of computations on star network, and networks in which binomial trees can be embedded (meshes, hypercubes, multistage interconnections). We demonstrate that in many cases memory limitations do not restrict efficiency of parallel processing as much as computation and communication speeds.     

A \sqrt N Dynamic Load Distribution Algorithm Using Anti-Tasks and Load State Vectors

One of the fundamental issues to ensure maximal performance improvement in a cluster computing environment is load distribution, which is commonly achieved by using polling-based load distribution algorithms. Such algorithms suffer from two weaknesses: (1) Load information exchanged during a polling session is confined to the two negotiating nodes only. (2) Such algorithms are not scalable in that growth of the distributed system is accompanied with increasing amount of polling sessions.In this paper, we proposed a LD algorithm which is based on anti-tasks and load state vectors. Anti-tasks travel around the distributed system for pairing up task senders and receivers. As an anti-task travels, timed load information is collected and disseminated over the entire system via the load state vector bundled with the anti-task. Guided by load state vectors, anti-tasks are spontaneously directed towards processing nodes having high transient workload, thus allowing their surplus workload to be relocated soonest possible. No peer-to-peer negotiations between senders and receivers are needed.To reduce the network bandwidth consumption caused by the anti-task algorithm, the number of hosts that an anti-task needs to travel to must be carefully limited. The algorithm achieves this by employing the mathematical notion of Finite Projective Plane (FPP). By employing FPP, the number of nodes that each anti-task has to travel is at most , where N is the number of nodes in the system, without sacrifying the spread of load information.     

A Load Balancing Tool for Distributed Parallel Loops

Large scale applications typically contain parallel loops with many iterates. The iterates of a parallel loop may have variable execution times which translate into performance degradation of an application due to load imbalance. This paper describes a tool for load balancing parallel loops on distributed-memory systems. The tool assumes that the data for a parallel loop to be executed is already partitioned among the participating processors. The tool utilizes the MPI library for interprocessor coordination, and determines processor workloads by loop scheduling techniques. The tool was designed independent of any application; hence, it must be supplied with a routine that encapsulates the computations for a chunk of loop iterates, as well as the routines to transfer data and results between processors. Performance evaluation on a Linux cluster indicates that the tool reduces the cost of executing a simulated irregular loop without load balancing by up to 81%. The tool is useful for parallelizing sequential applications with parallel loops, or as an alternate load balancing routine for existing parallel applications.     

遗传负荷理论的一种普适框架

遗传负荷表示种群由于遗传变异能力的存在而在平均适宜度上的损失,定量讨论各种遗传负荷,对研究现实发生水平上的物种进化具有重要意义,以往的遗传负荷理论从种群平衡出发,探讨现实发生水平上的物种进化,可是,进化是种群平衡的位移;这便构成了理论与现实之间的矛盾,为拓展以往的遗传负荷理论,给出了一个描述各种遗传负荷的普适理论框架,利用这个理论框架既能探讨平衡种群的遗传负荷,又能模写非平衡种群的遗传负荷及其变化,从而克服了以往的遗传负荷理论不能描述非平衡种群和不时与生物进化现实相悖的不足之处,为研究物种的进化提供了一种可靠的模拟方法。     

A Multistage Procedure for Analyzing Unreplicated Factorial Experiments

A multistage procedure, which is based on the likelihood principle, is proposed to identify active effects in unreplicated factorial designs and their fractions. The proposed procedure controls the experimental error rate (EER) at any prespecified level in industrial and biomedical experiments. Extensive comparison with Lenth 's (1989) test is discussed.     

A critical assessment of standard processing methods for the preparation of palynological samples

Standard processing techniques for the isolation of organic walled dinoflagellate cysts from geological samples are examined, with particular attention to the size and type of sieve mesh used. Variations within the ‘standard’ processing techniques used by different laboratories are identified, and an assessment of the retention capacities of meshes of different sizes and different materials is carried out. Some dinoflagellate cysts and large numbers of Lycopodium spores, used for the calculations of absolute abundance data, were found to pass through 20 μm meshes. This is due to a combination of factors including: the diagonal aperture diameter of a 20 μm mesh measuring over 28 μm; the three-dimensional properties of different mesh weaves (nylon and polyester); and the non-spherical shape of the particles. Experiments demonstrate that the maximum mesh size that should be used in palynological processing is 15 μm. Nylon mesh is more practical to use than polyester as processing time is reduced, but nylon is degraded by contact with acid solutions. Meshes with apertures < 15 μm may be used, though this may be impractical for large samples containing significant quantities of fine siliciclastic or organic material.     

Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness

While the MPP is still the most common architecture in supercomputer centers today, a simpler and cheaper machine configuration is appearing at many supercomputing sites. This alternative setup may be described simply as a collection of multiprocessors or a distributed server system. This collection of multiprocessors is fed by a single common stream of jobs, where each job is dispatched to exactly one of the multiprocessor machines for processing.The biggest question which arises in such distributed server systems is what is a good rule for assigning jobs to host machines: i.e. what is a good task assignment policy. Many task assignment policies have been proposed, but not systematically evaluated under supercomputing workloads.In this paper we start by comparing existing task assignment policies using a trace-driven simulation under supercomputing workloads. We validate our experiments by providing analytical proofs of the performance of each of these policies. These proofs also help provide much intuition. We find that while the performance of supercomputing servers varies widely with the task assignment policy, none of the above task assignment policies perform as well as we would like.We observe that all policies proposed thus far aim to balance load among the hosts. We propose a policy which purposely unbalances load among the hosts, yet, counter-to-intuition, is also fair in that it achieves the same expected slowdown for all jobs – thus no jobs are biased against. We evaluate this policy again using both trace-driven simulation and analysis. We find that the performance of the load unbalancing policy is significantly better than the best of those policies which balance load.     

A Three-Dimensional Kinematics Analysis of a Koi Carp Pectoral Fin by Digital Image Processing

Pectoral fins fascinate researchers for their important role in fish maneuvers. By possessing a complicated flexible structure with several fin rays made by a thin film, the fin exhibits a three-dimensional (3D) motion. The complex 3D fin kinematics makes it challenging to study the performance of pectoral fin. Nevertheless, a detailed study on the 3D motion pattern of pectoral fins is necessary to the design and control of a bio-inspired fin rays. Therefore, a highspeed photography system is introduced in this paper to study the 3D motion of a Koi Carp by analyzing the two views of its pectoral fin simultaneously. The key motions of the pectoral fins are first captured in both hovering and retreating. Next, the 3D configuration of the pectoral fins is reconstructed by digital image processing, in which the movement of fin rays during fish retreating and hovering is obtained. Furthermore, the method of Singular Value Decomposition (SVD) is adopted to extract the basic motion patterns of pectoral fins from extensive image sequences, i.e. expansion, bending, cupping, and undulation. It is believed that the movement of the fin rays and the basic patterns of the pectoral fins obtained in the present work can provide a good foundation for the development and control of bionic flexible pectoral fins for underwater propeller.     

DyRAM: An Active Reliable Multicast Framework for Data Distribution

Group communications (multicast) are foreseen to be one of the most critical yet challenging technologies to meet the exponentially growing demands for data distribution in a large variety of applications of the Internet (such as grid computing, web applications and distributed simulations). When reliability is required, there is no straightforward solutions and meeting the objectives of reliable multicast is not an easy task. Active networks open a new perspective in providing more efficient solutions for the problem of reliability. In this context, routers are able to perform customized computations on the packets flowing through them. In this paper, we propose a receiver-based (replier) local recovery multicast protocol with dynamic repliers elected on a per-packet basis. Designed to provide an efficient reliable multicast service without any cache facilities inside the network, our approach, uses low-overhead active services in routers. The current paper addresses the design, evaluation and the implementation of an efficient and scalable reliable multicast protocol noted DyRAM standing for Dynamic Replier Active reliable multicast.     

A direct estimate of gillnet selectivity for brown trout

Five hundred pre-measured brown trout (Salmo trutta), 20 of each cm-class from 5 to 29 inclusive, were released. They were recaptured with gillnets of mesh size 8.0, 10.5, 16.0, 19.5 and 24.0 mm, measured between adjacent knots. The nets were made of clear, nylon monofilament. The modal lengths and the general shape of the selectivity curves were in agreement with earlier findings. The height of the selectivity curve (S) increased exponentially with mesh size in mm (M): S= 0.047e^0.075M.     

A System for Distributed Storage and Analysis of Genome Information

A distributed computing system is developed to search and analyze genetic databases using parallel computing technologies. Queries are processed by a local network PC cluster. A universal task and data exchange format is developed for effective query processing. A multilevel hierarchic task batching procedure is elaborated to generate multiple subtasks and distribute them over cluster units under dynamic priority levels and with dynamic distribution of replicated source data subbases. Primary source data preparation and generation of annotation word indices are used to significantly reduce query processing time.     

Performance Evaluation of the Deadline Credit Scheduling Algorithm for Soft-Real-Time Applications in Distributed Video-on-Demand Systems

Video-on-Demand (VoD) systems are expected to support a variety of multimedia services to the users, such as tele-education, teleconference, remote working, videotelephony, high-definition TV, etc. These applications necessitate abundant bandwidth and buffer space as well as appropriate software and hardware for the efficient manipulation of the networks resources. In this work we investigate a promising scheduling algorithm referred to as the Deadline Credit (DC) algorithm, which exploits the available bandwidth and buffer space to serve a diverse class of prerecorded video applications. We provide simulation results when the DC algorithm is applied to a hierarchical architecture distributed VoD network, which fits the existing tree topology used in todays cable TV systems. The issues investigated via the simulations are: the system utilization, the influence of the buffer space on the delivered Quality of Service, and the fairness of the scheduling mechanism. We examine cases with homogenous as well as diverse video streams, and extend our system to support interactive VCR-like functions. We also contribute a modification to the DC algorithm so that in cases when the video applications have different displaying periods, the video streams obtain a fair share of the networks resources. Finally, we validate our results by simulating actual videos encoded in MPEG-4 and H.263 formats.     

A dynamometer for evaluation of dynamic muscle work

The validation of a new dynamometer for evaluation of dynamic muscle work is presented. The device was based on a precise measurement of load displacements of any machine using gravitational loads as external resistance. It allowed, through a sensor consisting of an infrared photo interrupter, the calculation of velocity, force and power during concentric, eccentric and stretch-shortening cycle activity. To validate the dynamometer 33 male and female track and field athletes (12 throwers and 21 jumpers) participated in the study. The throwers (4 women and 8 men) were asked to perform half-squat exercises on a slide machine with a load of 100% of the subject's body mass. The day-to-day reproducibility of half-squat exercises gave a correlation coefficient ofr = 0.88, 0.97 and 0.95 for average push-off force (AF), average push-off velocity (AV), and average push-off power (AP) respectively. Comparison of half-squat measurements was performed against jumping and running test evaluation by the jumpers (7 women and 14 men). The interrelationships among the different variables studied demonstrated a strong correlation between AF, AV and AP and sprinting and jumping parameters (r = 0.53–0.97;P < 0.05–0.001). Using values of AF, AV and AP developed in half-squat exercises executed with different loads, ranging from 35% to 210% of the subject's body mass, it was also possible to establish the force-velocity and power-velocity relationships for both male and female jumpers. In any individual case, the maximal error due to the measurement system was calculated to be less than 0.3%, 0.9% and 1.2% for AF, AV, and AP respectively. Given the accuracy of the ergometer, the high reliability found between 2 days of measurements, and the specificity of the results it is suggested that the dynamic dynamometer would be suitable for evaluation of athletes performing specific skills. In addition, because single and multiple joint movements involving appropriate muscle groups can be easily performed, physiological characteristics could be evaluated for both athletic and rehabilitation purposes. Therefore, because of its simplicity of use and application, and its low cost the dynamometer would be suitable for both laboratory and field conditions.     

A Note on a Continuity Correction for Testing in Three-Dimensional Configural Frequency Analysis

A continuity correction is proposed for the test statistics of HABERMAN (1978) and LEHMACHER (1981) for identifying overfrequented (or underfrequented) cells in the three-dimensional Configural Frequency Analysis (CFA). Its quality is shown by comparison with the test based on the exact distribution of the cell frequencies.     

Condor-G: A Computation Management Agent for Multi-Institutional Grids

In recent years, there has been a dramatic increase in the number of available computing and storage resources. Yet few tools exist that allow these resources to be exploited effectively in an aggregated form. We present the Condor-G system, which leverages software from Globus and Condor to enable users to harness multi-domain resources as if they all belong to one personal domain. We describe the structure of Condor-G and how it handles job management, resource selection, security, and fault tolerance. We also present results from application experiments with the Condor-G system. We assert that Condor-G can serve as a general-purpose interface to Grid resources, for use by both end users and higher-level program development tools.     

A Parallel Algorithm for Nonequilibrium Molecular Dynamics Simulation of Shear Flow on Distributed Memory Machines

Abstract

An algorithm is described which allows Nonequilibrium Molecular Dynamics (NEMD) simulations of a fluid undergoing planar Couette flow (shear flow) to be carried out on a distributed memory parallel processor using a (spatial) domain decomposition technique. Unlike previous algorithms, this algorithm uses a co-moving, or Lagrangian, simulation box. Also, the shape of the simulation box changes throughout the course of the simulation. The algorithm, which can be used for two or three dimensional systems, has been tested on a Fujitsu AP1000 Parallel computer with 128 processors.