Resource-Aware Distributed Scheduling Strategies for Large-Scale Computational Cluster/Grid Systems

In this paper, we propose distributed algorithms referred to as resource-aware dynamic incremental scheduling (RADIS) strategies. Our strategies are specifically designed to handle large volumes of computationally intensive arbitrarily divisible loads submitted for processing at cluster/grid systems involving multiple sources and sinks (processing nodes). We consider a real-life scenario, wherein the buffer space (memory) available at the sinks (required for holding and processing the loads) varies over time, and the loads have deadlines and propose efficient "pull-based" scheduling strategies with an admission control policy that ensures that the admitted loads are processed, satisfying their deadline requirements. The design of our proposed strategies adopts the divisible load paradigm, referred to as the divisible load theory (DLT), which is shown to be efficient in handling large volume loads. We demonstrate detailed workings of the proposed algorithms via a simulation study by using real-life parameters obtained from a major physics experiment.     

Handling large-size discrete wavelet transform on network-based computing systems — parallelization via divisible load paradigm

The discrete wavelet transform (DWT) is a powerful signal processing tool, but comes with a considerable computation cost. In this paper, we consider the problem of parallelizing the DWT computation on loosely-coupled networked systems. We first systematically analyze the data dependencies among DWT computations, identify the partitionable portions and then by applying the divisible load theory (DLT), we derive a novel scheduling strategy to schedule DWT computation onto bus networks. Our study is first of its kind in the DLT literature to demonstrate handling a highly coupled recursive computational nature of this problem towards gaining a significant speed-up.     

Handling biological sequence alignments on networked computing systems: A divide-and-conquer approach

In this paper, we address the biological sequence alignment problem, which is one of the most commonly used steps in several bioinformatics applications. We employ the Divisible Load Theory (DLT) paradigm that is suitable for handling large-scale processing on network-based systems to achieve a high degree of parallelism. Using the DLT paradigm, we propose a strategy in which we carefully partition the computation work load among the processors in the system so as to minimize the overall computation time of determining the maximum similarity between the DNA/protein sequences. We consider handling such a computational problem on networked computing platforms connected as a linear daisy chain. We derive the individual load quantum to be assigned to the processors according to computation and communication link speeds along the chain. We consider two cases of sequence alignment where post-processes, i.e., trace-back processes that are required to determine an optimal alignment, may or may not be done at individual processors in the system. We derive some critical conditions to determine if our strategies are able to yield an optimal processing time. We apply three different heuristic strategies proposed in the literature to generate sub-optimal solutions for processing time when the above conditions cannot be satisfied. To testify the proposed schemes, we use real-life DNA samples of house mouse mitochondrion and the DNA of human mitochondrion obtained from the public database GenBank [GenBank, http://www.ncbi.nlm.nih.gov] in our simulation experiments. By this study, we conclusively demonstrate the applicability and potential of the DLT paradigm to such biological sequence related computational problems.     

Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing

In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191–207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted.     

Requirement-aware strategies for scheduling real-time divisible loads on clusters

This paper investigates the real-time scheduling problem for handling heterogeneous divisible loads on cluster systems. Divisible load applications occur in many fields of science and engineering. Such applications can be easily parallelized in a master–worker fashion, but pose several scheduling challenges. We consider divisible loads associated with deadlines to enhance quality-of-service (QoS) and provide performance guarantees in distributed computing environments. In addition, since the divisible loads to be performed may widely vary in terms of their required hardware and software, we capture the loads’ various processing requirements in our load distribution strategies, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus in our problem formulation each load can only be processed by certain processors as both the loads and processors are heterogeneous. We propose scheduling algorithms referred to as Requirements-Aware Real-Time Scheduling (RARTS) algorithms, which consist of a novel scheduling policy, referred to as Minimum Slack Capacity First (MSCF), and two multi-round load distribution strategies, referred to as All Eligible Processors (AEP) and Least Capability First (LCF). We perform rigorous performance evaluation studies to quantify the performance of our strategies on a variety of scenarios.     

Minimizing the stretch when scheduling flows of divisible requests

In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed for this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive single processor case, and we show how to extend algorithms that have been proposed in the literature for the single processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any online algorithm, we present new competitiveness results for existing algorithms, and we develop several new online heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics under realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the single processor model are inefficient in practice. In contrast, we show that our online algorithms based on linear programming are in practice near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case.     

生物多序列比对的并行算法

多序列比对是生物信息学中的基本问题。由于生物序列数据库的快速增长,即使优秀的串行算法已不能满足实际的需要。研究了Gusfield提出的星型比对模型的串行算法,进行了空间和时间上的改进,基于cluster结构的菜并行机提出了一种并行算法,并对大量基因数据进行了测试,结果表明对于大规模的多序列比对,算法能达到较高的加速比。     

Scheduling divisible MapReduce computations

In this paper we analyze MapReduce distributed computations as a divisible load scheduling problem. The two operations of mapping and reducing can be understood as two divisible applications with precedence constraints. A divisible load model of the computation, and two load partitioning algorithms are proposed. Performance limits of MapReduce computations are investigated. To our best knowledge this is the first time that processing applications with precedence constraints have been considered on the grounds of divisible load theory.     

Load Management in Loosely Coupled Multiprocessor Systems

Scheduling is a typical technique used to distribute the load in multiprocessor systems. Usually, the manager(dispatcher or operating system)schedule the tasks so that the average finish time is minimized. Constraints related to the characteristics of the load such as precedence relation, deadline time, etc. must be taken into consideration. With ever increasing applications of a new paradigm of divisible tasks in image processing and parallel processing, one must concentrate on the characteristics of the system such as processor speed, link speed, and processor interconnection topology when distributing the load. By exploiting queuing theory, we managed to find different bounds on the arrival rate(load) as a function of link speed, processor speed and the size of tasks. A flow control mechanism for different multiprocessor systems with different topologies is embedded in our analysis. Moreover, our model indicates to the design engineers, depending on the traffic intensity, which element(s)of a parallel system has to be upgraded or replaced to meet the new load. This, of course, has to be justified by cost consideration.     

Strategyproof Mechanisms for Scheduling Divisible Loads in Bus-Networked Distributed Systems

The scheduling of arbitrarily divisible loads on a distributed system is studied by Divisible Load Theory (DLT). DLT has the underlying assumption that the processors will not cheat. In the real world, this assumption is unrealistic as the processors are owned and operated by autonomous rational organizations that have no a priori motivation for cooperation. Consequently, they will manipulate the algorithms if it benefits them to do so. In this work, we propose strategyproof mechanisms for scheduling divisible loads on three types of bus-connected distributed systems. These mechanisms provide incentives to the processors to obey the prescribed algorithms and to truthfully report their parameters, leading to an efficient load allocation and execution.     

Task migration in three-dimensional meshes

As a result of the emerging use of mesh-based multicomputers (and recently mesh-based multiprocessor systems-on-chip), issues related to processor management have attracted much attention. In a mesh-based multiprocessor, after repeated submesh allocations and de-allocations, the system network may be fragmented, i.e. there might be unallocated nodes in the network. As a result, in a system with contiguous processor allocation, no new tasks can start running due to the lack of enough free adjacent processors to form a suitable submesh. Although there might be enough free processors available, they remain idle until the allocator can find a set of adjacent free nodes forming a submesh to be used for the new task. This can lead to low system performance. Task migration was introduced as a solution to this problem through migration of tasks running on some submeshes to other free areas in order to reduce fragmentation by chaining the newly freed areas and disengaging nodes to form larger submeshes. In this paper, we propose a novel structured and formulated way to code task migration, which is helpful for congestion detection in different steps of task migration algorithms. Moreover, considering the fact that the 3D mesh-based multicomputers are now very popular, a new task migration algorithm in 3D meshes is proposed. We also address the special case of the 2D migration in a 3D mesh multicomputer.     

Multiple Sequence Alignment with Evolutionary Computation

In this paper we provide a brief review of current work in the area of multiple sequence alignment (MSA) for DNA and protein sequences using evolutionary computation (EC). We detail the strengths and weaknesses of EC techniques for MSA. In addition, we present two novel approaches for inferring MSA using genetic algorithms. Our first novel approach utilizes a GA to evolve an optimal guide tree in a progressive alignment algorithm and serves as an alternative to the more traditional heuristic techniques such as neighbor-joining. The second novel approach facilitates the optimization of a consensus sequence with a GA using a vertically scalable encoding scheme in which the number of iterations needed to find the optimal solution is approximately the same regardless the number of sequences being aligned. We compare both of our novel approaches to the popular progressive alignment program Clustal W. Experiments have confirmed that EC constitutes an attractive and promising alternative to traditional heuristic algorithms for MSA.     

Scheduling divisible loads with time and cost constraints

In distributed computing, divisible load theory provides an important system model for allocation of data-intensive computations to processing units working in parallel. The main task is to define how a computation job should be split into parts, to which processors those parts should be allocated and in which sequence. The model is characterized by multiple parameters describing processor availability in time, transfer times of job parts to processors, their computation times and processor usage costs. The main criteria are usually the schedule length and cost minimization. In this paper, we provide the generalized formulation of the problem, combining key features of divisible load models studied in the literature, and prove its NP-hardness even for unrestricted processor availability windows. We formulate a linear program for the version of the problem with a fixed number of processors. For the case with an arbitrary number of processors, we close the gaps in the study of special cases, developing efficient algorithms for single criterion and bicriteria versions of the problem, when transfer times are negligible.

     

Hybrid multiobjective artificial bee colony for multiple sequence alignment

In the bioinformatics community, it is really important to find an accurate and simultaneous alignment among diverse biological sequences which are assumed to have an evolutionary relationship. From the alignment, the sequences homology is inferred and the shared evolutionary origins among the sequences are extracted by using phylogenetic analysis. This problem is known as the multiple sequence alignment (MSA) problem. In the literature, several approaches have been proposed to solve the MSA problem, such as progressive alignments methods, consistency-based algorithms, or genetic algorithms (GAs). In this work, we propose a Hybrid Multiobjective Evolutionary Algorithm based on the behaviour of honey bees for solving the MSA problem, the hybrid multiobjective artificial bee colony (HMOABC) algorithm. HMOABC considers two objective functions with the aim of preserving the quality and consistency of the alignment: the weighted sum-of-pairs function with affine gap penalties (WSP) and the number of totally conserved (TC) columns score. In order to assess the accuracy of HMOABC, we have used the BAliBASE benchmark (version 3.0), which according to the developers presents more challenging test cases representing the real problems encountered when aligning large sets of complex sequences. Our multiobjective approach has been compared with 13 well-known methods in bioinformatics field and with other 6 evolutionary algorithms published in the literature.     

Slabpose Columnsort: A New Oblivious Algorithm for Out-of-Core Sorting on Distributed-Memory Clusters

Our goal is to develop a robust out-of-core sorting program for a distributed-memory cluster. The literature contains two dominant paradigms for out-of-core sorting algorithms: merging-based and partitioning-based. We explore a third paradigm, that of oblivious algorithms. Unlike the two dominant paradigms, oblivious algorithms do not depend on the input keys and therefore lead to predetermined I/O and communication patterns in an out-of-core setting. Predetermined I/O and communication patterns facilitate overlapping I/O, communication, and computation for efficient implementation. We have developed several out-of-core sorting programs using the paradigm of oblivious algorithms. Our baseline implementation, 3-pass columnsort, was based on Leighton's columnsort algorithm. Though efficient in terms of I/O and communication, 3-pass columnsort has a restriction on the maximum problem size. As our first effort toward relaxing this restriction, we developed two implementations: subblock columnsort and M-columnsort. Both of these implementations incur substantial performance costs: subblock columnsort performs additional disk I/O, and M-columnsort needs substantial amounts of extra communication and computation. In this paper we present slabpose columnsort, a new oblivious algorithm that we have designed explicitly for the out-of-core setting. Slabpose columnsort relaxes the problem-size restriction at no extra I/O or communication cost. Experimental evidence on a Beowulf cluster shows that unlike subblock columnsort and M-columnsort, slabpose columnsort runs almost as fast as 3-pass columnsort. To the best of our knowledge, our implementations are the first out-of-core multiprocessor sorting algorithms that make no assumptions about the keys and produce output that is perfectly load balanced and in the striped order assumed by the Parallel Disk Model.     

Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach

Optimal multiprocessor real-time schedulers incur significant overhead for preemptions and migrations. We present RUN, an efficient scheduler that reduces the multiprocessor problem to a series of uniprocessor problems. RUN significantly outperforms existing optimal algorithms with an upper bound of O(logm) average preemptions per job on m processors (fewer than 3 per job in all of our simulated task sets) and reduces to Partitioned EDF whenever a proper partitioning is found.     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

Pipeline optimizations of the prime factor algorithm

The prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm used when the sequence length can be decomposed into mutually prime factors. Following our previous results on PFA decomposition carried out at Caltech on hypercube machines, we present in the paper a pipeline PFA implementation suitable for multiprocessor systems with distributed memory. This implementation achieves high values of efficiency and speed-up when processing multiple sequences of data. The paper shows how an optimized structure can be obtained when the concurrency among computation and communications is exploited at each node of the pipe. Experimental results obtained on transputer-based structures and on the Intel Touchstone Delta system are also reported.     

Real-time scheduling of divisible loads in cluster computing environments

Cluster computing has become an important paradigm for solving large-scale problems. To enhance the quality of service (QoS) and provide performance guarantees in a cluster computing environment, various real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent tasks represent many real-world applications. However, the problem of providing performance guarantees to divisible load applications has only recently been studied systematically. In this work, three important and necessary design decisions, (1) workload partitioning, (2) node assignment, and (3) task execution order, are identified for real-time divisible load scheduling. A scheduling framework that can configure different policies for each of the three design decisions is proposed and used to generate various algorithms. This paper systematically studies these algorithms and identifies scenarios where the choices of design parameters have significant effects.     

Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks

This paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics.