Tuning and hybrid parallelization of a genetic-based multi-point statistics simulation code

One of the main difficulties using multi-point statistical (MPS) simulation based on annealing techniques or genetic algorithms concerns the excessive amount of time and memory that must be spent in order to achieve convergence. In this work we propose code optimizations and parallelization schemes over a genetic-based MPS code with the aim of speeding up the execution time. The code optimizations involve the reduction of cache misses in the array accesses, avoid branching instructions and increase the locality of the accessed data. The hybrid parallelization scheme involves a fine-grain parallelization of loops using a shared-memory programming model (OpenMP) and a coarse-grain distribution of load among several computational nodes using a distributed-memory programming model (MPI). Convergence, execution time and speed-up results are presented using 2D training images of sizes 100 × 100 × 1 and 1000 × 1000 × 1 on a distributed-shared memory supercomputing facility.     

Parallel machine scheduling with flexible resources

Parallel machine flexible resource scheduling (PMFRS) problems consider an additional flexible resource (e.g. operators), which can be freely allocated to any jobs and/or any machines and may speed-up the process in proportion to its amount. If job–machine assignment is unspecified, the problem is referred to as unspecified PMFRS (UPMFRS). This paper reviews the mathematical models of both PMFRS and UPMFRS problems in the literature and not only gives some extensions to the model of dynamic PMFRS problem but also presents integer programming (IP) models for static and dynamic UPMFRS problems with the objective of minimizing makespan. To solve large-sized dynamic PMFRS and UPMFRS problems, a relaxed IP based constraint programming (CP) approach is also proposed. All IP models and the proposed IP/CP approach are tested with an extensive computational study. The results of the computational experiments are discussed with respect to the major parameters of the problem and conclusions are drawn.     

Optimal Read-Once Parallel Disk Scheduling

An optimal prefetching and I/O scheduling algorithm L-OPT, for parallel I/O systems, using a read-once model of block references is presented. The algorithm uses knowledge of the next $L$ references, $L$-block lookahead, to create a minimal-length I/O schedule. For a system with $D$ disks and a buffer of capacity $m$ blocks, we show that the competitive ratio of L-OPT is $\Theta(\sqrt{mD/L})$ when $L \geq m$, which matches the lower bound of any prefetching algorithm with $L$-block lookahead. Tight bounds for the remaining ranges of lookahead are also presented. In addition we show that L-OPT is the optimal offline algorithm: when the lookahead consists of the entire reference string, it performs the absolute minimum possible number of I/Os. Finally, we show that L-OPT is comparable with the best online algorithm with the same amount of lookahead; the ratio of the length of its schedule to the length of the optimal schedule is always within a constant factor.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

Frequency allocation problem in a SDMA satellite communication system

Spatial Division Multiple Access (SDMA) is a principle of radio resource sharing that relies on the division of the space dimension into separated communication channels. SDMA basically relies on adaptive and dynamic beam-forming associated to a clever algorithm in charge of resource allocation. As satellite communication systems move towards an increasing number of users and a larger throughput for each of them, SDMA is one of the most promising techniques that can reach these two goals. This paper studies static Frequency Assignment Problems (FAP) in a satellite communication system involving a gateway connected to a terrestrial network and some user terminals located in a service area. Two scenarios are considered: one based on SDMA and the other based on usual spot coverage. We propose original integer linear programming formulations and greedy allocation algorithms for the FAP which involves unusual cumulative interference constraints. By considering the link budget of each user, the objective is to maximize the number of users that the system can serve. We show through computational experiments on realistic data that the FAP associated with the SDMA system can be solved efficiently, yielding substantial improvement compared to the traditional system.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Scheduling algorithm based on evolutionary computing in identical parallel machine production line

Evolutionary programming is a kind of evolutionary computing method based on stochastic search suitable for solving system optimization. In this paper, evolutionary programming method is applied to the identical parallel machine production line scheduling problem of minimizing the number of tardy jobs, which is a very important optimization problem in the field of research on CIMS and industrial engineering, and researches on problem formulation, expression of feasible solution, methods for the generation of the initial population, the mutation and improvement on the local search ability of evolutionary programming. Computational results of different scales of problems show that the evolutionary programming algorithm proposed in this paper is efficient, and that it is fit for solving large-scale identical parallel machine production line scheduling problems, and that the quality of its solution has advantage over so far the best heuristic procedure.     

Improved parallel approximation of a class of integer programming problems

We present a method to derandomizeRNC algorithms, converting them toNC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems inNC, to within factors better than the current-bestNC algorithms (of Berger and Rompel and Motwaniet al.); in some cases, the approximation factors are as good as the best-known sequential algorithms, due to Raghavan. This class includes problems such as global wire-routing in VLSI gate arrays and a generalization of telephone network planning in SONET rings. Also for a subfamily of the “packing” integer programs, we provide the firstNC approximation algorithms; this includes problems such as maximum matchings in hypergraphs, and generalizations. The key to the utility of our method is that it involves sums ofsuperpolynomially many terms, which can however be computed inNC; this superpolynomiality is the bottleneck for some earlier approaches, due to Berger and Rompel and Motwaniet al. A preliminary version of this work appeared inProc. International Colloquim on Automata, Languages and Programming, 1996, pages 562–573. Work done in parts at DIMACS (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology), at the Institute for Advanced Study, Princeton (supported in part by Grant 93-6-6 of the Alfred P. Sloan Foundation), and at the National University of Singapore.     

A hybrid Branch-and-Bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems

Providing efficient workload management is an important issue for a large-scale heterogeneous distributed computing environment where a set of periodic applications is executed. The considered shipboard distributed system is expected to operate in an environment where the input workload is likely to change unpredictably, possibly invalidating a resource allocation that was based on the initial workload estimate. The tasks consist of multiple strings, each made up of an ordered sequence of applications. There is a quality of service (QoS) minimum throughput constraint that must be satisfied for each application in a string, and a maximum utilization constraint that must be satisfied on each of the hardware resources in the system. The challenge, therefore, is to efficiently and robustly manage both computation and communication resources in this unpredictable environment to achieve high performance while satisfying the imposed constraints. This work addresses the problem of finding a robust initial allocation of resources to strings of applications that is able to absorb some level of unknown input workload increase without rescheduling. The proposed hybrid two-stage method of finding a near-optimal allocation of resources incorporates two specially designed mapping techniques: (1) the Permutation Space Genitor-Based heuristic, and (2) the follow-up Branch-and-Bound heuristic based on an Integer Linear Programming (ILP) problem formulation. The performance of the proposed resource allocation method is evaluated under different simulation scenarios and compared to an iteratively computed upper bound.     

Optimal schemes for resubmitted lot acceptance using previous defect count data

Optimal defects-per-unit inspection schemes for screening batches of manufactured material are obtained by minimizing the expected sampling effort. Nonaccepted lots may be resubmitted for resampling inspection, whereas the Poisson model is used to describe the random behavior of the number of nonconformities per sampled unit. A coefficient is presented to assess the similarity degree between the available previous information and the current inspection, and truncated gamma distributions are adopted to quantify the natural prior uncertainty about the defect rate using past count data and expert opinions. A step-by-step computational procedure is proposed to solve the underlying integer nonlinear programming problem in order to find the best resubmitted lot sampling plan with controlled expected producer and consumer risks based on previous objective and subjective knowledge. In many practical cases, the inclusion of lot resubmissions and past information into the inspection process provides substantial savings in sample size, as well as more reliable evaluations of the existing producer and consumer risks. The proposed approach allows the practitioners to consider a restricted interval for the defect rate, which is reasonable in practice and unfeasible under the frequentist perspective. Moreover, a mechanism is suggested to update the prior distribution based on past performance of the inspection plan. For illustrative purposes, the methodology developed is applied to the manufacturing of glass.