RTS: A system to simulate the real time cost behaviour of parallel computations

In this paper, we present a software tool, RTS (real time simulator), that analyses the time cost behaviour of parallel computations through simulation. It is assumed in RTS that the computer system which supports the executions of parallel computations has a limited number of processors all processors have the same speed and they communicate with each other through a shared memory. In RTS, the time cost of a parallel computation is defined as a function of the input, the algorithm, the data structure, the processor speed, the number of processors, the processor power allocation, the communication and the execution environment. How RTS models the time cost is first discussed in the paper. In the model, a locking technique is used to manipulate the access to the shared memory, processing power is equally allocated among all the operations that are currently being performed in parallel in the computer system, and the number of operations in the execution environment of a parallel computation changes from time to time. How RTS works and how the simulation is used to do time cost analysis are also discussed.     

Performance of parallel computations with dynamic processor allocation

In parallel adaptive mesh refinement (AMR) computations the problem size can vary significantly during a simulation. The goal here is to explore the performance implications of dynamically varying the number of processors proportional to the problem size during simulation. An emulator has been developed to assess the effects of this approach on parallel communication, parallel runtime and resource consumption. The computation and communication models used in the emulator are described in detail. Results using the emulator with different AMR strategies are described for a test case. Results show for the test case, varying the number of processors, on average, reduces the total parallel communications overhead from 16 to 19% and improves parallel runtime time from 4 to 8%. These results also show that on average resource utilization improves more than 37%.     

Efficient parallel processing of range queries through replicated declustering

A common technique used to minimize I/O in data intensive applications is data declustering over parallel servers. This technique involves distributing data among several disks so as to parallelize query retrieval and thus, improve performance. We focus on optimizing access to large spatial data, and the most common type of queries on such data, i.e., range queries. An optimal declustering scheme is one in which the processing for all range queries is balanced uniformly among the available disks. It has been shown that single copy based declustering schemes are non-optimal for range queries. In this paper, we integrate replication in conjunction with parallel disk declustering for efficient processing of range queries. We note that replication is largely used in database applications for several purposes like load balancing, fault tolerance and availability of data. We propose theoretical foundations for replicated declustering and propose a class of replicated declustering schemes, periodic allocations, which are shown to be strictly optimal for a number of disks. We propose a framework for replicated declustering, using a limited amount of replication and provide extensions to apply it on real data, which include arbitrary grids and a large number of disks. Our framework also provides an effective indexing scheme that enables fast identification of data of interest in parallel servers. In addition to optimal processing of single queries, we show that this framework is effective for parallel processing of multiple queries. We present experimental results comparing the proposed replication scheme to other techniques for both single queries and multiple queries, on synthetic and real data sets. Recommended by: Ahmed Elmagarmid Supported by U.S. Department of Energy (DOE) Award No. DE-FG02-03ER25573, and National Science Foundation (NSF) grant CNS-0403342.     

Stochastic scheduling on parallel machines to minimize discounted holding costs

We study stochastic scheduling on m parallel identical machines with random processing times. The cost involved in the problem is discounted to the present value and the objective is to minimize the expected discounted holding cost, which covers in a unified framework many performance measures discussed in the literature as special cases, including discounted rewards, flowtime, and makespan. We prove that the SEPT rule is optimal, on a fairly general ground, in the class of preemptive dynamic policies, the class of nonpreemptive dynamic policies, and the class of nonpreemptive static list policies. The LEPT rule, on the other hand, is optimal to minimize the expected discounted makespan only under certain restrictive conditions. Without such conditions, the LEPT rule is found no longer optimal for discounted makespan by a counterexample, in contrast to the case without discounting. This research was partially supported by the National Natural Science Foundation of China under Grant No. 70671043, Research Grants Council of Hong Kong Under Project No. 410208, NSFC/RGC Joint Research Grant No. N-CUHK442/05 (NSFC Ref: 70518002), and Macquarie University Research Development Grant.     

A system organization for parallel image processing

One of the problems in the development of multiprocessor systems for image analysis is the selection and efficient utilization of an interconnection network between the multiple processing units. This paper proposes a system organization centered around a class of interconnection networks and a global bus. Control schemes are developed for realizing the intertask communication requirements typically encountered in the parallel formulation of problems for image analysis. These schemes are simple, distributed and efficient. The utility of this organization is demonstrated by evaluating the performance of two applications.     

An optimal stopping time problem with time average cost in a bounded interval

An optimal stopping time problem for a diffusion process stopped at the boundary of a bounded interval is studied. Our cost functional is of time average type which is different from standard long term average cost functional but can be considered as a version of the Gittins index. Both characterization of the, value function and construction of optimal stopping policy will be presented.     

Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints

This paper considers a deterministic scheduling problem where multiple jobs with s-precedence relations are processed on multiple identical parallel machines. The objective is to minimize the total completion time. The s-precedence relation between two jobs i and j represents the situation where job j is constrained from processing until job i starts processing, which is different from the standard definition of a precedence relation where j cannot start until i completes. The s-precedence relation has wide applicability in the real world such as first-come-first-served processing systems.     

System reliability maximization for a computer network by finding the optimal two-class allocation subject to budget

In the real world, a computer/communication system is usually modeled as a capacitated-flow network since each transmission line (resp. facility) denoted by an edge (resp. node) has multiple capacities. System reliability is thus defined to be a probability that d units of data are transmitted successfully from a source node to a sink node. From the perspective of quality management, system reliability is a critical performance indicator of the computer network. This paper focuses on maximizing system reliability for the computer network by finding the optimal two-class allocation subject to a budget, in which the two-class allocation is to allocate exactly one transmission line (resp. facility) to each edge (resp. node). In addition, allocating transmission lines and facilities to the computer network involves an allocation cost where the cost for allocating a transmission line depends on its length. For solving the addressed problem, a genetic algorithm based method is proposed, in which system reliability is evaluated in terms of minimal paths and state-space decomposition. Several experimental results demonstrate that the proposed algorithm can be executed in a reasonable time and has better computational efficiency than several popular soft computing algorithms.     

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.     

Scheduling with flexible resources in parallel workcenters to minimize maximum completion time

In this paper we consider the parallel machine scheduling problem with dual resource constraints with the objective of minimizing the maximum completion time. We develop heuristics that combine list-scheduling and bin-packing approaches with rules to iteratively modify the flexible resource allocation. A lower bound is presented and the previous and proposed solution approaches to the problem are analyzed under a variety of experimental conditions, demonstrating that there are advantages to the proposed heuristics.     

A novel approach to resource scheduling for parallel query processing on computational grids

Advances in network technologies and the emergence of Grid computing have both increased the need and provided the infrastructure for computation and data intensive applications to run over collections of heterogeneous and autonomous nodes. In the context of database query processing, existing parallelisation techniques cannot operate well in Grid environments because the way they select machines and allocate tasks compromises partitioned parallelism. The main contribution of this paper is the proposal of a low-complexity, practical resource selection and scheduling algorithm that enables queries to employ partitioned parallelism, in order to achieve better performance in a Grid setting. The evaluation results show that the scheduler proposed outperforms current techniques without sacrificing the efficiency of resource utilisation. Recommended by: Ioannis Vlahavas     

Single machine batch scheduling to minimize total completion time and resource consumption costs

In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).     

Research on the Optimal Parallel Algorithms of Broadcast-Class Problems

Speedup is considered as the criterion of determining whether a parallel algorithm is optimal.But broadcast-class problems,existing only on parallel computer system,have no sequential algorithms at all.Speedup standard becomes invalid here.Through this research on broadcast algorithms under several typical prallel computation models,a model-independent evaluation standard min C^2 is developed,which can be not only used to determine an optimal broadcasting algorithm,but also normalized to apply to any parallel algorithm.As a new idea,min C^2 will lead to a new way in this field.     

Production and allocation policies in a two-class inventory system with time and quantity dependent waiting costs

This paper presents an integrated production and inventory allocation model in a two-echelon supply chain system. The higher echelon is a manufacturer, who produces a single commodity. The lower echelon consists of two types of major commodity distributors who might face stochastic or deterministic demands from multiple retailers. Our analytical model provides optimal decision policies that minimize total production and customer waiting costs from the manufacturer's perspective when there are time and quantity dependent customer waiting costs. We identify the value of the integrated policy and compare it with typical approximations such as aggregating the multiple demands or applying the single demand multiple times.     

An application of parallel virtual machine framework to film production problem

Along with the rapid progress in computer technologies, both the theoretical foundations and practical applications of operations research are becoming more and more profound. In the literature, many techniques have been thus proposed to deal with real-world problems. However, the problems often exhibit complicated structures, and it is difficult to derive exact solutions in a reasonable time. PVM (Parallel Virtual Machine), the platform of our study, is a widely used environment in the world of parallel computing. It can be used to integrate existing department facilities without incurring additional hardware costs. Furthermore, the ease in programming also facilitates a wide adoption of PVM. In our study, we incorporate the concepts of the branch-and-bound method, multiprocess programming, and shared memory to design a parallel branch-and-bound algorithm to cope with the problem of minimizing talent hold cost in film production. We conduct a series of computational experiments to measure the effectiveness of our paralleization scheme. The results reveal that the speedup based upon our parallel algorithm is significant. This research provides a convincing demonstration in achieving effective parallelization with low costs.     

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used; thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented.     

Analysis of a model for parallel image processing

An increasing awareness of the need for high speed parallel processing systems for image analysis has stimulated a great deal of interest in the design and development of such systems. Efficient processing schemes for several specific problems have been developed providing some insight into the general problems encountered in designing efficient image processing algorithms for parallel architectures. However it is still not clear what architecture or architectures are best suited for image processing in general, or how one may go about determining those which are. An approach that would allow application requirements to specify architectural features would be useful in this context. Working towards this goal, general principles are outlined for formulating parallel image processing tasks by exploiting parallelism in the algorithms and data structures employed. A synchronous parallel processing model is proposed which governs the communication and interaction between these tasks. This model presents a uniform framework for comparing and contrasting different formulation strategies. In addition, techniques are developed for analyzing instances of this model to determine a high level specification of a parallel architecture that best ‘matches’ the requirements of the corresponding application. It is also possible to derive initial estimates of the component capabilities that are required to achieve predefined performance levels. Such analysis tools are useful both in the design stage, in the selection of a specific parallel architecture, or in efficiently utilizing an existing one. In addition, the architecture independent specification of application requirements makes it a useful tool for benchmarking applications.     

Video streaming over the internet with optimal bandwidth resource allocation

In this paper, an adaptive framework for video streaming over the Internet is presented. The framework is a joint design of packet scheduling and rate control with optimal bandwidth resource allocation. The transmission rate is dynamically adjusted to obtain maximal utilization of the client buffer and minimal allocation of the bandwidth. Under the constraint of the transmission rate, a prioritized packet scheduling is designed to provide a better visual quality of video frames. The packet scheduling is a refined bandwidth allocation which takes into account of varying importance of the different packets in a compressed video stream. Moreover, the proposed approach is scalable with increasing multimedia flows in the distributed Internet environment. Comparisons are made with the most current streaming approaches to evaluate the performance of the framework using the H.264 video codec. The extensive simulation results show that the average Peak Signal to Noise Ratio (PSNR) increases in our proposed approach. It provides a better quality of the decoded frames, and the quality of the decoded frames changes more smoothly. The achieved video quality among different users also has a lower fluctuation, which indicates a fair sharing of network resources.

Multiagent based differential evolution approach to optimal power flow

This paper proposes a new differential evolution approach named as multiagent based differential evolution (MADE) based on multiagent systems, for solving optimal power flow problem with non-smooth and non-convex generator fuel cost curves. This method integrates multiagent systems (MAS) and differential evolution (DE) algorithm. An agent in MADE represents an individual to DE and a candidate solution to the optimization problem. All agents live in a lattice like environment, with each agent fixed on a lattice point. In order to obtain optimal solution quickly, each agent competes and cooperates with its neighbors and it can also use knowledge. Making use of these agent-agent interaction and DE mechanism, MADE realizes the purpose of minimizing the value of objective function. MADE applied to optimal power flow is evaluated on 6 bus system and IEEE 30 bus system with different generator characteristics. Simulation results show that the proposed method converges to better solutions much faster than earlier reported approaches.