Graph models for scheduling systems with machine saturation property

Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs     

Scheduling with uncertainties on new computing platforms

New distributed computing platforms (grids) are based on interconnections of a large number of processing elements. A most important issue for their effective utilization is the optimal use of resources through proper task scheduling. It consists of allocating the tasks of a parallel program to processors on the platform and to determine at what time the tasks will start their execution. As data may be subject to uncertainties or disturbances, it is practically impossible to precisely predict the input parameters of the task scheduling problem.     

Idle regulation in non-clairvoyant scheduling of parallel jobs

The optimization of parallel applications is difficult to achieve by classical optimization techniques because of their diversity and the variety of actual parallel and distributed platforms and/or environments. Adaptive algorithmic schemes, capable of dynamically changing the allocation of jobs during the execution to optimize global system behavior, are the best alternatives for solving this problem. In this paper, we focus on non-clairvoyant scheduling of parallel jobs with known resource requirements but unknown running times, with emphasis on the regulation of idle periods in the context of general list policies. We consider a new family of scheduling strategies based on two phases which successively combine sequential and parallel execution of jobs. We generalize known worst-case performance bounds by considering two extra parameters, in addition to the number of processors and maximum processor requirements considered in the literature, namely, job parallelization penalty and idle regulation factor. Furthermore, we prove that under certain conditions of idle regulation, the performance guarantee of parallel job scheduling in space-sharing mode can be improved.     

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.     

The efficiency of application of dual-processor computers for the analysis of the three-dimensional second harmonic generation problem

The efficiency of application of dual-processor computers, various operating systems, and library functions adapted to the used processors for increasing the execution speed of a computer program used for solving a system of two 3D nonlinear Schrödinger equations is analyzed. The computation speeds obtained on computers with 32-bit and 64-bit processors are compared. It is shown that the use of all mentioned possibilities and the Intel Itanium 2 processor provides from to threefold to tenfold total saving of time, depending on the operating system and the computer type. Parallelization of the algorithm for different operating systems in combination with the use of a library adapted to the processor can increase the program’s execution speed by a factor of 1.5–3.     

A multiple-tree search procedure for the resource-constrained project scheduling problem

For over three decades, researchers have sought effective solution procedures for PERT/CPM types of scheduling problems under conditions of limited resource availability. This paper presents a procedure for this problem which takes advantage of the emerging technology provided by multiple parallel processors to find and verify an optimal schedule for a project under conditions of multiple resource constraints. In our approach, multiple solutions trees are searched simultaneously in the quest for a minimum duration schedule. Global upper and lower bound information in common memory is shared among processors, enabling one or several processors to prune potentially significant portions of its search tree based upon bounds discovered by a processor using a different search tree. Computational experience is reported both for problems in which resources are available in constant amounts per period, as well as the much more difficult problem in which the resources available are allowed to vary over the schedule horizon (e.g., travel, sick leave, assignment to other tasks or projects, and so forth). The modular multiple-tree search procedure described in this paper is quite general, permitting most types of existing serial search strategies to be adapted to this approach where multiple processors are available.     

Modeling of superscalar instruction scheduling and analysis of a heuristic scheduling algorithm

The problem of superscalar instruction scheduling is studied and an analysis of a heuristic scheduling algorithm is presented. First, a superscalar architecture is characterized byk, the number of types of functional units employed,m _i , the number of typei functional units,P _ij , thejth functional unit of typei, andz, the maximal number of delay cycles incurred by the execution of instructions. A program trace to be scheduled is modeled by a directed acyclic graph with delay on precedence relations. These two models reflect most of the flavor of the superscalar instruction scheduling problem. A heuristic scheduling algorithm called the ECG-algorithm is designed by compiling two scheduling guidelines. The performance of the ECG-algorithm is evaluated through worst-case analysis. Lettingw _ECG denote the length of an ECG-schedule andw _opt the length of an optimal schedule, we established the boundwv _ECG /w _opt k+1–2/[max{m _i }(z+1)], which is smaller than other known bounds.     

Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

Decentralized list scheduling

Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor only has a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load imbalance between the local lists. We obtain an equation giving the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precedence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log₂ W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. (Theory Comput. Syst. 34(2):115–144, 2001). We end with some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. Moreover, the simulations give a better insight into the additive term whose value is shown to be around 3log₂ W confirming the precision of our analysis.     

An elementary proof of the duality theorem of linear programming

A constructive and elementary proof of the duality theorem of linear programming is presented. The proof utilizes the new concept of an embedded core program, which is a program generated from a linear program with finite optimum by successively removing constraints until no remaining constraints can be deleted without changing the optimal solution.     

Schedule execution for two-machine flow-shop with interval processing times

This paper addresses the issue of how to best execute the schedule in a two-phase scheduling decision framework by considering a two-machine flow-shop scheduling problem in which each uncertain processing time of a job on a machine may take any value between a lower and upper bound. The scheduling objective is to minimize the makespan. There are two phases in the scheduling process: the off-line phase (the schedule planning phase) and the on-line phase (the schedule execution phase). The information of the lower and upper bound for each uncertain processing time is available at the beginning of the off-line phase while the local information on the realization (the actual value) of each uncertain processing time is available once the corresponding operation (of a job on a machine) is completed. In the off-line phase, a scheduler prepares a minimal set of dominant schedules, which is derived based on a set of sufficient conditions for schedule domination that we develop in this paper. This set of dominant schedules enables a scheduler to quickly make an on-line scheduling decision whenever additional local information on realization of an uncertain processing time is available. This set of dominant schedules can also optimally cover all feasible realizations of the uncertain processing times in the sense that for any feasible realizations of the uncertain processing times there exists at least one schedule in this dominant set which is optimal. Our approach enables a scheduler to best execute a schedule and may end up with executing the schedule optimally in many instances according to our extensive computational experiments which are based on randomly generated data up to 1000 jobs. The algorithm for testing the set of sufficient conditions of schedule domination is not only theoretically appealing (i.e., polynomial in the number of jobs) but also empirically fast, as our extensive computational experiments indicate.     

一种改进的多模式项目反应性调度问题

既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。     

An algebraic certificate for Budan’s theorem

The existing algorithms to construct the real closure of an ordered field involve very high complexities. These algorithms are based on Sturm’s theorem which we suspect to be one reason for the complexities since all known proofs of Sturm’s theorem use Rolle’s theorem which is problematic in a constructive context.Therefore we propose to replace the use of Sturm’s theorem by Budan’s theorem. In this paper we present as a first step in this direction an algebraic certificate for Budan’s theorem. An algebraic certificate is a certain kind of proof of a statement. In particular, it is an algorithm which produces, from an arbitrary data in the premise of the statement, explicit (in)equalities which express the conclusion.     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

Real time task scheduling allowing fuzzy due dates

The paper deals with periodical task scheduling. The tasks are described by fuzzy due dates and fuzzy execution times. The goal of scheduling is to find an optimal assignment of priorities such that the satisfaction associated with due dates and execution times be minimized. The paper shows how the rules associated with task priorities improve the optimal assignment search.     

Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search

A graph matching approach to optimal assignment of task modules with varying lengths and precedence relationship in a distributed computing system is proposed. Inclusion of module precedence into the optimal solution is made possible by the use of topological module orderings. Two graphs are defined to represent the processor structure and the module precedence relationship, respectively. Assignment of the task modules to the system processors is transformed into a type of graph matching. The search of optimal graph matching corresponding to optimal task assignment is formulated as a state-space search problem which is then solved by theA* algorithm in artificial intelligence. Illustrative examples and experimental results are included to show the effectiveness of the proposed approach.     

A cyclic scheduling problem with an undetermined number of parallel identical processors

This paper presents two integer linear programming (ILP) models for cyclic scheduling of tasks with unit/general processing time. Our work is motivated by digital signal processing (DSP) applications on FPGAs (Field-Programmable Gate Arrays)—hardware architectures hosting several sets of identical arithmetic units. These hardware units can be formalized as dedicated sets of parallel identical processors. We propose a method to find an optimal periodic schedule of DSP algorithms on such architectures where the number of available arithmetic units must be determined by the scheduling algorithm with respect to the capacity of the FPGA circuit. The emphasis is put on the efficiency of the ILP models. We show the advantages of our models in comparison with common ILP models on benchmarks and randomly generated instances.     

Task scheduling with and without communication delays: A unified approach

The problem of scheduling directed acyclic task graphs on an unbounded number of processors is considered. We present a single algorithm which is applicable to several special cases, thus effecting a unified approach to task scheduling independent of the task graph. We start by considering multi-stage dags and present an algorithm that computes a schedule in O(Nq log q) time, where N is the number of stages, and q is the maximum number of edges between any two stages of the graph. We show that the schedule produced by the algorithm is optimal when: (i) all communication delays are zero or, (ii) the precedence graph is an in-tree or an out-tree and communication times are small or, (iii) the task graph is densely connected and communication costs and processing costs are unity. For multi-stage dags with small communication times we show that the makespan of the schedule generated by our algorithm is less than twice that of the optimal. We also bound the makespan for the case when communication times are arbitrary. We then show how the algorithm may be applied to schedule arbitrary dags and derive the performance bounds for this case. Finally, we present the results of tests we carried out with randomly generated task graphs. These seem to indicate that, on the average, the algorithm performs substantially better than theoretical worst case predictions.     

Optimal resource allocation and scheduling for?the?CELL BE platform

Resource allocation and scheduling for multicore platforms is one of the most critical challenges in today??s embedded computing. In this paper we focus on a well-known multicore platform, namely the Cell BE processor, and we address the problem of allocating and scheduling its processors, communication channels and memories, with the goal of minimizing execution time for complex data streaming applications. We propose three complete approaches that optimally solve the problem and prove optimality. The first is based on the recursive application of the Logic Based Benders decomposition, resulting in a three stage algorithm. The second is a pure CP approach while the third is a hybrid approach integrating the first two. Extensive experimental evaluation shows the features of each approach and its effectiveness on a specific instance structure.