Performance bounds on multiprocessor scheduling strategies for statically allocated programs

In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is an NP-hard problem to find an optimal schedule, and very little is known of how close the heuristic solutions get.The major result here is a theorem stating that if certain program parameters, which can be obtained from an execution of the program on a single-processor, are known, the execution time of the optimal schedule can be calculated within a factor equal to the largest number of border processes on one processor. Border processes are processes which communicate with other processors. The program parameters are obtained using a previously developed tool.Due to the generality of this theorem, the proof is rather complex because it has to cover a large range of situations. The theorem itself, however, is easy to apply, making it possible to compare the performance of different scheduling strategies with the optimal case. The proof also gives important hints on how to design efficient scheduling algorithms for statically allocated programs.     

A Genetic/Tabu Thresholding Hybrid Algorithm for the Process Allocation Problem

In this paper we describe an hybrid heuristic approach, which combines Genetic Algorithms and Tabu Thresholding, for the static allocation of interacting processes onto a parallel target system, where the number of processes is greater than the number of available processors. This problem is known to be NP-hard and finds many practical applications, given the increasing diffusion of distributed and parallel computing systems.The algorithm faces infeasibilities due to processors overload by incorporating them into the objective function and by adapting the mutation operator. Global search is performed on the set of local optima obtained by a repair search operator based on a Tabu Thresholding procedure.Extensive computational testing on randomly generated instances with up to 100 processes characterized by different target network topologies with 4 to 25 processors, shows that the algorithm favorably compares with other approaches from the literature.The proposed approach has also been extended to the allocation of parallel objects and classes, where an additional co-residence constraint between each parallel object and the associated class arises.     

Pipeline implementation of cellular automata for structural design on message-passing multiprocessors

The inherent structure of cellular automata is trivially parallelizable and can directly benefit from massively parallel machines in computationally intensive problems. This paper presents both block synchronous and block pipeline (with asynchronous message passing) parallel implementations of cellular automata on distributed memory (message-passing) architectures. A structural design problem is considered to study the performance of the various cellular automata implementations. The synchronous parallel implementation is a mixture of Jacobi and Gauss–Seidel style iteration, where it becomes more Jacobi like as the number of processors increases. Therefore, it exhibits divergence because of the mathematical characteristics of Jacobi iteration matrix for the structural problem as the number of processors increases. The proposed pipeline implementation preserves convergence by simulating a pure Gauss–Seidel style row-wise iteration. Numerical results for analysis and design of a cantilever plate made of composite material show that the pipeline update scheme is convergent and successfully generates optimal designs.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

A variable neighbourhood search algorithm for the constrained task allocation problem

A variable neighbourhood search algorithm that employs new neighbourhoods is proposed for solving a task allocation problem whose main characteristics are: (i) each task requires a certain amount of resources and each processor has a capacity constraint which limits the total resource of the tasks that are assigned to it; (ii) the cost of solution includes fixed costs when using processors, task assignment costs, and communication costs between tasks assigned to different processors. A computational study shows that the algorithm performs well in terms of time and solution quality relative to other local search procedures that have been proposed.     

A parallel implementation of the restarted GMRES iterative algorithm for nonsymmetric systems of linear equations

We describe the parallelisation of the GMRES(c) algorithm and its implementation on distributed-memory architectures, using both networks of transputers and networks of workstations under the PVM message-passing system. The test systems of linear equations considered are those derived from five-point finite-difference discretisations of partial differential equations. A theoretical model of the computation and communication phases is presented which allows us to decide for which values of the parameterc our implementation executes efficiently. The results show that for reasonably large discretisation grids the implementations are effective on a large number of processors.     

The Process Allocation Problem: a Survey of the Application of Graph-Theoretic and Integer Programming Approaches

The Process Allocation Problem, which consists of allocating a number of processes to a network of processors with the objective of minimizing the sum of communication (between processes residing on different processors) and execution costs, is presented and the relevant literature reviewed. Solution procedures employing graph-theoretic and mathematical programming methods are critically examined. Some heuristic algorithms are also presented.     

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.     

Resource level minimization in the discrete–continuous scheduling

A discrete–continuous problem of non-preemptive task scheduling on identical parallel processors is considered. Tasks are described by means of a dynamic model, in which the speed of the task performance depends on the amount of a single continuously divisible renewable resource allotted to this task over time. An upper bound on the completion time of all the tasks is given. The criterion is to minimize the maximum resource consumption at each time instant, i.e., the resource level. This problem has been observed in many industrial applications, where a continuously divisible resource such as gas, fuel, electric, hydraulic or pneumatic power, etc., has to be distributed among the processing units over time, and it affects their productivity. The problem consists of two interrelated subproblems: task sequencing on processors (discrete subproblem) and resource allocation among the tasks (continuous subproblem). An optimal resource allocation algorithm for a given sequence of tasks is presented and computationally tested. Furthermore, approximation algorithms are proposed, and their theoretical and experimental worst-case performances are analyzed. Computer experiments confirmed the efficiency of all the algorithms.     

A Method of Dealing with Certain Non-Linear Allocation Problems Using the Transportation Technique

An investigation was carried out to establish a method of determining the allocation between certain factories of a known production requirement so as to minimize the total expense of production. Each factory was made up of a number of departments or services whose total expense varied non-linearly with production level.The method was to divide the production range of each department in each factory into regions of approximate linear expense, and consider the associated total company expense connected with the optimum allocation for each possible group of regions (one region in each department). In theory the simplex technique could be applied to each group to find its optimum allocation, but as the number of groups is prodigious for quite simple problems this is not practicable. (In the actual problem for which the method was produced there was of the order of 100,000 groups.)A procedure was devised using the transportation technique together with various lemmas proved in the text and feasibility considerations, by which it was possible to reduce rapidly the number of groups needed to be considered in detail to just a few.Other problems should be amenable to this method provided they are similar to the one above in two respects.(1) The departmental variation of expense with production from one region to the next is in general continuous with decreasing rate of change of expense, i.e. the variation is concave.(2) It should be possible to put the requirements into one of the units of capacity usage in which there are important physical or maximum capacity restrictions.In addition, the method is particularly suitable when the number of factories is not large.As the method required repeated applications of the transportation model, a technique was devised for obtaining an optimum solution to this model more quickly than by the usual techniques. This technique will be described in another paper.An example of a whole problem is given after the Appendix. A full solution of this problem is shown in which occur most of the points dealt with in the text.The problem for which the method was devised, was one of minimizing the total expense of production of twenty common products between three factories. Each factory had seven departments or services, in most of which two regions were required to describe satisfactorily a department's variation of expense with production, in linear terms. A complete solution was obtained in a few days using the method described without recourse to an electronic computer (not counting the initial computations of costs, etc. required).     

Cooperative computing with fragmentable and mergeable groups

This work considers the problem of performing a set of N tasks on a set of P cooperating message-passing processors (PN). The processors use a group communication service (GCS) to coordinate their activity in the setting where dynamic changes in the underlying network topology cause the processor groups to change over time. GCSs have been recognized as effective building blocks for fault-tolerant applications in such settings. Our results explore the efficiency of fault-tolerant cooperative computation using GCSs. The original investigation of this area by (Dolev et al., Dynamic load balancing with group communication, in: Proc. of the 6th International Colloquium on Structural Information and Communication Complexity, 1999) focused on competitive lower bounds, non-redundant task allocation schemes and work-efficient algorithms in the presence of fragmentation regroupings. In this work we investigate work-efficient and message-efficient algorithms for fragmentation and merge regroupings. We present an algorithm that uses GCSs and implements a coordinator-based strategy. For the analysis of our algorithm we introduce the notion of view-graphs that represent the partially-ordered view evolution history witnessed by the processors. For fragmentations and merges, the work of the algorithm (defined as the worst case total number of task executions counting multiplicities) is not more than min{N·f+N,N·P}, and the message complexity is no worse than 4(N·f+N+P·m), where f and m denote the number of new groups created by fragmentations and merges, respectively. Note that the constants are very small and that, interestingly, while the work efficiency depends on the number of groups f created as the result of fragmentations, work does not depend on the number of groups m created as the result of merges.     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

Material allocation in MRP with tardiness penalties

In this paper, we address some flaws in the material allocation function of Materials Requirements Planning (MRP). The problem formulation differs from standard MRP logic in certain important ways: start and finish times for orders are forced to be realistic and material allocations are made to minimize the total tardiness penalty associated with late completion. We show that the resulting MRP material allocation problem is NP-hard in the strong sense. A lower bound and a heuristic are developed from a mixed integer linear formulation and its Lagrangean relaxation. The lower bound and the heuristics are closer to the optimum in cases where there is either abundant material or considerable competition for material; in intermediate cases, small perturbations in material allocation can have a significant effect. A group of heuristics based on the MRP approach and its modifications is examined; they are optimal under certain conditions. An improvement method that preserves priorities inherent in any given starting solution is also presented. The Lagrangean heuristic performs better than the MRP based heuristics for a set of 3900 small problems, yielding solutions that are about 5% to 10% over the optimal. The best MRP based heuristic does about as well as the Lagrangean heuristic on a set of 120 larger problems, and is 25% to 40% better than the standard MRP approach, on the data sets tested.     

Estimation of more than one parameters in stratified sampling with fixed budget

In a multivariate stratified sampling more than one characteristic are defined on every unit of the population. An optimum allocation which is optimum for one characteristic will generally be far from optimum for others. A compromise criterion is needed to work out a usable allocation which is optimum, in some sense, for all the characteristics. When auxiliary information is also available the precision of the estimates of the parameters can be increased by using it. Furthermore, if the travel cost within the strata to approach the units selected in the sample is significant the cost function remains no more linear. In this paper an attempt has been made to obtain a compromise allocation based on minimization of individual coefficients of variation of the estimates of various characteristics, using auxiliary information and a nonlinear cost function with fixed budget. A new compromise criterion is suggested. The problem is formulated as a multiobjective all integer nonlinear programming problem. A solution procedure is also developed using goal programming technique.     

Allocation of Doctors to Health Centres in Haryana State of India — A Case Study

Medical Administrators are usually confronted with the problem of determining the number of doctors to be posted at different health centres within their jurisdiction. In India the number of doctors allocated to a health centre is normally decided without any proper study of the health needs of the area served by the centre. In certain areas the number of doctors posted is considerably different from the requirement of the area. Also, in certain health centres situated in villages lacking in modern amenities, absenteeism among doctors poses a very serious problem in day to day running of the health centres. The problem of allocation is formulated and a heuristic method is suggested for determining the optimum number of doctors to be posted at each health centre in order to maximise the number of patients seen by the doctor per day. The heuristic method is applied to nine health centres of Haryana state of India in order to demonstrate the potential benefits.     

An Optimal Chance Constraint Multivariate Stratified Sampling Design Using Auxiliary Information

When we are dealing with multivariate problem then we need an allocation which is optimal for all the characteristics in some sense because the individual optimum allocations usually differ widely unless the characteristics are highly correlated. So an allocation called “Compromise allocation” is to be worked out suggested by Cochran. When auxiliary information is also available, it is customary to use it to increase the precision of the estimates. Moreover, for practical implementation of an allocation, we need integer values of the sample sizes. In the present paper the problem is to determine the integer optimum compromise allocation when the population means of various characteristics are of interest and auxiliary information is available for the separate and combined ratio and regression estimates. This paper considers the optimum compromise allocation in multivariate stratified sampling with non-linear objective function and probabilistic non-linear cost constraint. The probabilistic non-linear cost constraint is converted into equivalent deterministic one by using Chance Constrained programming. The formulated multi-objective nonlinear programming problem is solved by Fuzzy Goal programming approach and Chebyshev approximation. Numerical illustration is also given to show the practical utility of the approaches.     

An Optimum Multivariate Stratified Sampling Design with Nonresponse: A Lexicographic Goal Programming Approach

In a multivariate stratified sample survey with L strata and p > 1 characteristics, defined on each unit of the population, let the estimation of all the p-population means be of interest. As discussed by Cochran (1977), since the optimum allocation for one characteristic will not in general be optimum for other characteristics some compromise must be reached in a multiple characteristics stratified surveys. Various authors worked out allocations that are based on a compromise criterion. The resulting allocations are optimal for all characteristics in some sense, for example an allocation that minimizes the trace of the variance-covariance matrix of the estimators of the population means or an allocation that minimizes the weighted average of the variances or an allocation that maximizes the total relative efficiency of the estimators as compared to the corresponding individual optimum allocations. In the present paper the problem of optimum allocation in multivariate stratified random sampling in the presence of nonresponse has been formulated as a multiobjective integer nonlinear programming problem and a solution procedure is developed using goal programming technique. Three numerical examples are worked out to illustrate the computational details. A comparison of the proposed method with some well known methods is also carried out to show the practical utility of the proposed method.     

Managing variances in manufacturing system design

The goal of this paper is to investigate how uncertainties in demand and production should be incorporated into manufacturing system design problems. We examine two problems in manufacturing system design: the resource allocation problem and the product grouping problem. In the resource allocation problem, we consider the issue of how to cope with uncertainties when we utilize two types of resources: actual processing capacity and stored capacity (inventory). A closed form solution of the optimal allocation scheme for each type of capacity is developed, and its performance is compared to that of the conventional scheme where capacity allocation and inventory control decisions are made sequentially. In the product grouping problem, we consider the issue of how we design production lines when each line is dedicated to a certain set of products. We formulate a mathematical program in which we simultaneously determine the number of production lines and the composition of each line. Two heuristics are developed for the problem.     

Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. We provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(log n) using O(n/log n) processors on an . We also prove that the algorithm is the fastest possible independently of the number of processors available.