Prediction of Queue Waiting Times for Metascheduling on Parallel Batch Systems

Prediction of queue waiting times of jobs submitted to production parallel batch systems is important to provide overall estimates to users and can also help meta-schedulers make scheduling decisions. In this work, we have developed a framework for predicting ranges of queue waiting times for jobs by employing multi-class classification of similar jobs in history. Our hierarchical prediction strategy first predicts the point wait time of a job using dynamic k-Nearest Neighbor (kNN) method. It then performs a multi-class classification using Support Vector Machines (SVMs) among all the classes of the jobs. The probabilities given by the SVM for the class predicted using k-NN and its neighboring classes are used to provide a set of ranges of predicted wait times with probabilities. We have used these predictions and probabilities in a meta-scheduling strategy that distributes jobs to different queues/sites in a multi-queue/grid environment for minimizing wait times of the jobs. Experiments with different production supercomputer job traces show that our prediction strategies can give correct predictions for about 77-87% of the jobs, and also result in about 12% improved accuracy when compared to the next best existing method. Experiments with our meta-scheduling strategy using different production and synthetic job traces for various system sizes, partitioning schemes and different workloads, show that the meta-scheduling strategy gives much improved performance when compared to existing scheduling policies by reducing the overall average queue waiting times of the jobs by about 47%.

ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing Systems

In this paper, we present a decentralized dynamic load scheduling/balancing algorithm called ELISA (Estimated Load Information Scheduling Algorithm) for general purpose distributed computing systems. ELISA uses estimated state information based upon periodic exchange of exact state information between neighbouring nodes to perform load scheduling. The primary objective of the algorithm is to cut down on the communication and load transfer overheads by minimizing the frequency of status exchange and by restricting the load transfer and status exchange within the buddy set of a processor. It is shown that the resulting algorithm performs almost as well as a perfect information algorithm and is superior to other load balancing schemes based on the random sharing and Ni-Hwang algorithms. A sensitivity analysis to study the effect of various design parameters on the effectiveness of load balancing is also carried out. Finally, the algorithm's performance is tested on large dimensional hypercubes in the presence of time-varying load arrival process and is shown to perform well in comparison to other algorithms. This makes ELISA a viable and implementable load balancing algorithm for use in general purpose distributed computing systems.

Real-World Extensions To Scheduling Algorithms Based On Lagrangian Relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs, The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework, In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling.

Optimal scheduling of hydro-thermal power systems under shortage

The problem of optimal scheduling of the generation of a hydro-thermal power system that is faced with a shortage of energy is studied. The deterministic version of the problem is first analyzed, and the results are then extended to cases where the loads and the hydro inflows are random variables.

Bi-criteria single machine scheduling problem with a learning effect: Aneja-Nair method to obtain the set of optimal sequences

In this paper, we consider the bi-criteria single machine scheduling problem of n jobs with a learning effect. The two objectives considered are the total completion time (TC) and total absolute differences in completion times (TADC). The objective is to find a sequence that performs well with respect to both the objectives: the total completion time and the total absolute differences in completion times. In an earlier study, a method of solving bi-criteria transportation problem is presented. In this paper, we use the methodology of solvin bi-criteria transportation problem, to our bi-criteria single machine scheduling problem with a learning effect, and obtain the set of optimal sequences,. Numerical examples are presented for illustrating the applicability and ease of understanding.

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.

1- and 2-Chloromorphine. Halogenation of Morphine meta to the Free Phenolic Hydroxyl Group

Treatment of morphine in aqueous HCl at 70° with KIO3 yields a monochloromorphine, identified as 1-chloromorphine by spectroscopic means and by the fact that it, and its methyl ether 1-chlorocodeine, are different from 2-chloromorphine and 2-chlorocodeine prepared from 2-aminomorphine of unequivocally established structure. Formation of 1-chloromorphine and the previously known 1-bromomorphine involves entry of the halogen into the position meta to the free phenolic hydroxyl. Possible mechanistic interpretations of this unusual orientation are discussed.

Distributed Scheduling for Multi-Hop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. We suggest how the greedy heuristic can be implemented in a distributed manner. We evaluate an analytical bound in detail, for the special case of a line graph and also provide a loose bound on the greedy heuristic for the case of an arbitrary graph.

Experiences With WM: A Centralised Scheduling Approach for Performance Management of IEEE 802.11 Wireless LANs

In our earlier work ([1]) we proposed WLAN Manager (or WM) a centralised controller for QoS management of infrastructure WLANs based on the IEEE 802.11 DCF standards. The WM approach is based on queueing and scheduling packets in a device that sits between all traffic flowing between the APs and the wireline LAN, requires no changes to the AP or the STAs, and can be viewed as implementing a "Split-MAC" architecture. The objectives of WM were to manage various TCP performance related issues (such as the throughput "anomaly" when STAs associate with an AP with mixed PHY rates, and upload-download unfairness induced by finite AP buffers), and also to serve as the controller for VoIP admission control and handovers, and for other QoS management measures. In this paper we report our experiences in implementing the proposals in [1]: the insights gained, new control techniques developed, and the effectiveness of the WM approach in managing TCP performance in an infrastructure WLAN. We report results from a hybrid experiment where a physical WM manages actual TCP controlled packet flows between a server and clients, with the WLAN being simulated, and also from a small physical testbed with an actual AP.

Geochemistry of meta-anorthosites from Holénarasipur, Karnataka, South India

Geochemical and Rb---Sr isotope studies indicate that the meta-anorthosites of Holénarasipur, occurring as minor differentiates in ultramafic-mafic complex are igneous intrusives with cumulus character, emplaced around 3095 m.y. ago. The fine-grained nature is secondary; relict cumulus features are preserved in less deformed bodies. In major element chemistry, they compare well with other Archean anorthosites. Abundance levels of Ti, Zr, Y and P indicate the evolution through crystal fractionation of a parental magma; cumulus olivine and pyroxenes dominated chemistry for ultramafites, cumulus plagioclase and possibly clinopyroxene controlled chemistry for anorthosite-gabbros and cumulus magnetite in magnetite-gabbros. Magnetite is not an early cumulate. REE geochemistry is dominated by plagioclase with low abundance levels, slightly LREE enriched and variable positive Eu anomaly. Sr and Image values vary with An content in plagioclase. Isotopic studies show low initial Image (=0.7016) indicating that Rb---Sr isochron age represents the time of intrusion rather than the time of metamorphism.

Crystal structure of ferroelectric sodium meta vanadate, NaVO3

The crystal structure of ferroelectric sodium meta vanadate, NaVO3 has been solved using three dimensional X-ray data and refined to an R-value of 0.077 for 375 observed reflections. The crystal belongs to the monoclinic system with space group Cc and with unit cell dimensions a = 10.494 (9) Aring, b = 9.434 (7) Aring, c = 5.863 (6) Aring and β = 108° 48' in the room temperature ferroelectric phase. The unit cell dimensions in the high temperature paraelectric phase (above 380°C) are a = 10.595 (15) Aring, b = 9.671 (10) Aring, c = 5.926 (8) Aring and β = 108° 45' with space group C2/c. The crystal structure may be viewed as consisting of alternate channels of sodium polyhedra and VO4 tetrahedra.

Polyvanadate-stimulated NADH oxidation by plasma membranes-The need for a mixture of deca and meta forms of vanadate

Polyvanadate solutions obtained by extracting vanadium pentoxide with dilute alkali over a period of several hours contained increasing amounts of decavanadate as characterized by NMR and ir spectra. Those solutions having a metavanadate:decavanadate ratio in the range of 1-5 showed maximum stimulation of NADH oxidation by rat liver plasma membranes. Reduction of decavanadate, but not metavanadate, was obtained only in the presence of the plasma membrane enzyme system. High simulation of activity of NADH oxidation was obtained with a mixture of the two forms of vanadate and this further increased on lowering the pH. Addition of increasing concentrations of decavanadate to metavanadate and vice versa increased the stimulatory activity, reaching a maximum when the metavanadate:decavanadate ratio was in the range of 1-5. Increased stimulatory activity can also be obtained by reaching these ratios by conversion of decavanadate to metavanadate by alkaline phosphate degradation, and of metavanadate to decavanadate by acidification. These studies show for the first time that both deca and meta forms of vanadate present in polyvanadate solutions are needed for maximum activity of NADH oxidation.

Greedy Scheduling in Multihop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice.

A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi-cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedule than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors.

Cross-Layer Scheduling with Infrequent Channel and Queue Measurements

The downlink scheduling problem in multi-queue multi-server systems under channel uncertainty is considered. Two policies that make allocations based on predicted channel states are proposed. The first is an extension of the well-known dynamic backpressure policy to the uncertain channel case. The second is a variant that improves delay performance under light loads. The stability region of the system is characterised and the first policy is argued to be throughput optimal. A recently proposed policy of Kar et al [1] has lesser complexity, but is shown to be throughput suboptimal. Further, simulations demonstrate better delay and backlog properties for both our policies at light loads.