Parallel CRC generation

Theoretical aspects of encoding cyclic redundant codes (CRCs) are reviewed. A method of designing hardware parallel encoders for CRCs that is based on digital system theory and z-transforms is presented. It allows designers to derive the logic equations of the parallel encoder circuit for any generator polynomial. A few interesting application areas for hardware parallel encoders are pointed out     

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.     

Constructive methods for scheduling uniform loop nests

This paper surveys scheduling techniques for loop nests with uniform dependences. First, we introduce the hyperplane method and related variants. Then we extend it by using a different affine scheduling for each statement within the nest. In both cases, we present a new, constructive, and efficient method to determine optimal solutions, i.e., schedules whose total execution time is minimum     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

Parallel machine scheduling with multiple unloading servers

We study a parallel machine scheduling problem with multiple unloading servers. After a machine completes processing one job, an unloading server is needed to remove the job from the machine. Only after unloading, the machine is available for processing the next job. The model is motivated by the milk run operations of a logistics company that faces limited unloading docks at the warehouse. Our interest is to minimize the total completion time of the jobs. We show that the shortest-processing-time-first (SPT) algorithm has a worst-case bound of 2. We also develop other improved heuristic algorithms as well as a branch-and-bound algorithm to solve the problem. Computational experiments show that our algorithms are efficient and effective.     

Parallel algorithms for line generation

A new, parallel approach for generating Bresenham-type lines is developed. Coordinate pairs which approximate straight lines on a square grid are derived from line equations. These pairs serve as a basis for the development of four new parallel algorithms. One of the algorithms uses the fact that straight time generation is equivalent to a vector prefix sums calculation. The algorithms execute on a binary tree of processors. Each node in the tree performs a simple calculation that involves only additions and shifts. All four algorithms have time complexityO(log₂ n) wheren in the form 2 ^m denotes the number of points generated andn-1 is the number of processors in the tree. This compares toO(n) for Bresenham's algorithm executed on a sequential processor. Pipelining can be used to achieve a constant time per line generation as long as line length is less thann.     

Parallel generation of infinite images

We introduce a syntactic model for generating sets of finite and infinite images where a finite image can be viewed as an array over finite alphabet and an infinite image is an array with finite number of columns and infinite number of rows. This model, called image grammar, can be considered as a generalization of classical Chromsky grammar.

We study various types of infinite image grammars using Nivat's derivation which is an infinite unrestrictive derivation, Bvichi's (respectively Muller's) which is defined as infinite derivations selected by some repetitive set (respectively sets of rewriting rules). Then we study the combinatorial and language theoretical properties such as complexity measure, closure properties and decidability results. In terms of complexity measure we give a strict infinite hierarchy. We have extended Nivat's and Eilenberg's theorems to infinite images. Unfortunately we prove that Biichi's and McNaughton's theorems cannot be extended to infinite images. We also characterize these families in terms of deterministic image co-substitution and ω-languages     

Power generation scheduling by neural network

A new method for solving a power generation scheduling problem in an electric power system is presented. The objective is to determine the hourly start-up/ shut-down schedules of all generators so that forecasted hourly power demands per day may be met and total operating costs, the sum of setup and fuel costs for a given day, may be minimized. The problem may be formulated as a large-scale combinatorial optimization problem which includes 0-1 variables representing the start-up/shut-down of generators and continuous variables representing the power outputs. Determination of an optimalsolution within practical time limits is consequently difficult. Until now, the lagrangian relaxation method has been studied as it appeared to be the most practical method for obtaining an approximate solution to the problem. The efficiency of this method, however, depends on how the Lagrange multipliers are determined. Here, it is proposed that the Lagrange multipliers be estimated by utilizing the neural network and results determined from examination of the possibility of applying the backpropagation algorithm to pattern recognitions which presume the relationship between power demand pattern and Lagrange multipliers are reported. Through numerical experiments, it was established that the Lagrange multipliers, estimated by the neural network, are applicable to the problem.     

Using processor affinity in loop scheduling on shared-memorymultiprocessors

Loops are the single largest source of parallelism in many applications. One way to exploit this parallelism is to execute loop iterations in parallel on different processors. Previous approaches to loop scheduling attempted to achieve the minimum completion time by distributing the workload as evenly as possible while minimizing the number of synchronization operations required. The authors consider a third dimension to the problem of loop scheduling on shared-memory multiprocessors: communication overhead caused by accesses to nonlocal data. They show that traditional algorithms for loop scheduling, which ignore the location of data when assigning iterations to processors, incur a significant performance penalty on modern shared-memory multiprocessors. They propose a new loop scheduling algorithm that attempts to simultaneously balance the workload, minimize synchronization, and co-locate loop iterations with the necessary data. They compare the performance of this new algorithm to other known algorithms by using five representative kernel programs on a Silicon Graphics multiprocessor workstation, a BBN Butterfly, a Sequent Symmetry, and a KSR-1, and show that the new algorithm offers substantial performance improvements, up to a factor of 4 in some cases. The authors conclude that loop scheduling algorithms for shared-memory multiprocessors cannot afford to ignore the location of data, particularly in light of the increasing disparity between processor and memory speeds     

A performance-based parallel loop scheduling on grid environments

The effectiveness of loop self-scheduling schemes has been shown on traditional multiprocessors in the past and computing clusters in the recent years. However, parallel loop scheduling has not been widely applied to computing grids, which are characterized by heterogeneous resources and dynamic environments. In this paper, a performance-based approach, taking the two characteristics above into consideration, is proposed to schedule parallel loop iterations on grid environments. Furthermore, we use a parameter, SWR, to estimate the proportion of the workload which can be scheduled statically, thus alleviating the effect of irregular workloads. Experimental results on a grid testbed show that the proposed approach can reduce the completion time for applications with regular or irregular workloads. Consequently, we claim that parallel loop scheduling can benefit applications on grid environments.     

Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

Compiler-assisted leakage-aware loop scheduling for embedded VLIW DSP processors

As feature size shrinks, leakage energy consumption has become an important concern. In this paper, we develop a compiler-assisted instruction-level scheduling technique to reduce leakage energy consumption for applications with loops on VLIW architecture. In the proposed technique, we obtain the schedule with minimum leakage energy from the ones that are generated by repeatedly regrouping a loop based on rotation scheduling and bipartite-matching. We conduct experiments on a set of benchmarks from DSPstone, Mediabench, Netbench, and MiBench based on the power model of the VLIW processors. The results show that our algorithm can achieve significant leakage energy saving compared with the previous work.     

Parallel generation of unstructured surface grids

In this paper, a new grid generation system is presented for the parallel generation of unstructured triangular surface grids. The object-oriented design and implementation of the system, the internal components and the parallel meshing process itself are described. Initially in a rasterisation stage, the geometry to be meshed is analysed and a smooth distribution of local element sizes in 3-D space is set up automatically and stored in a Cartesian mesh. This background mesh is used by the advancing front surface mesher as spacing definition for the triangle generation. Both the rasterisation and the meshing are MPI-parallelised. The underlying principles and strategies will be outlined together with the advantages and limitations of the approach. The paper will be concluded with examples demonstrating the capabilities of the presented approach.

Parallel permutation generation on linear array

Given n items, a parallel algorithm for generating all the n! permutations is presented. The computational model used is a linear array which consists of n identical processing elements with a simple structure. One permutation is produced at each other time step. The elapsed time to produce a permutation is independent of the integer n. The basic idea used is the iterative method and the exchange of two consecutive components in an existing permutation. The design procedures of this algorithm are considered in detail. The ranking and unranking functions of the required permutations are also discussed.     

Energy minimization with loop fusion and multi-functional-unit scheduling for multidimensional DSP

Energy saving is becoming one of the major design issues in processor architectures with multiple functional units (FUs). Nested loops are usually the most critical part in multimedia and high-performance DSP systems. There is a tradeoff between power saving and performance, such as timing constraint and code size requirement, of nested loops. This paper studies how to minimize the total energy while satisfying performance requirement for applications with multidimensional nested loops. An algorithm, energy minimization with loop fusion and FU schedule (EMLFS), is proposed. We first use retiming and partition to fuse nested loops. Then we use novel FU scheduling algorithms to maximize energy saving without sacrificing performance. The experimental results show that the average improvement on energy saving is significant by using our EMLFS algorithm.     

Lagrangian relaxation and constraint generation for allocation and advanced scheduling

Diverse applications in manufacturing, logistics, health care, telecommunications, and computing require that renewable resources be dynamically scheduled to handle distinct classes of job service requests arriving randomly over slotted time. These dynamic stochastic resource scheduling problems are analytically and computationally intractable even when the number of job classes is relatively small. In this paper, we formally introduce two types of problems called allocation and advanced scheduling, and formulate their Markov decision process (MDP) models. We establish that these MDPs are “weakly coupled” and exploit this structural property to develop an approximate dynamic programming method that uses Lagrangian relaxation and constraint generation to efficiently make good scheduling decisions. In fact, our method is presented for a general class of large-scale weakly coupled MDPs that we precisely define. Extensive computational experiments on hundreds of randomly generated test problems reveal that Lagrangian decisions outperform myopic decisions with a statistically significant margin. The relative benefit of Lagrangian decisions is much higher for advanced scheduling than for allocation scheduling.     

Parallel generation of architecture on the GPU

In this paper, we present a novel approach for the parallel evaluation of procedural shape grammars on the graphics processing unit (GPU). Unlike previous approaches that are either limited in the kind of shapes they allow, the amount of parallelism they can take advantage of, or both, our method supports state of the art procedural modeling including stochasticity and context‐sensitivity. To increase parallelism, we explicitly express independence in the grammar, reduce inter‐rule dependencies required for context‐sensitive evaluation, and introduce intra‐rule parallelism. Our rule scheduling scheme avoids unnecessary back and forth between CPU and GPU and reduces round trips to slow global memory by dynamically grouping rules in on‐chip shared memory. Our GPU shape grammar implementation is multiple orders of magnitude faster than the standard in CPU‐based rule evaluation, while offering equal expressive power. In comparison to the state of the art in GPU shape grammar derivation, our approach is nearly 50 times faster, while adding support for geometric context‐sensitivity.     

Parallel generation of permutations on systolic arrays

We present a systolic algorithm to generate all the n! permutations of n given items. The computational model used is a linear systolic array consisting of n identical PEs. This algorithm requires n! time steps to solve this problem. Since any PE is identical and executes the same program, it is suitable for VLSI implementation. The correctness of the algorithm is proved. We also consider the ranking and unranking functions of permutations in this parallel algorithm