A novel approach for distributed application scheduling based on prediction of communication events

The evolution of commodity computing lead to the possibility of efficient usage of interconnected machines to solve computationally-intensive tasks, which were previously solvable only by using expensive supercomputers. This, however, required new methods for process scheduling and distribution, considering the network latency, communication cost, heterogeneous environments and distributed computing constraints. An efficient distribution of processes over such environments requires an adequate scheduling strategy, as the cost of inefficient process allocation is unacceptably high. Therefore, a knowledge and prediction of application behavior is essential to perform effective scheduling. In this paper, we overview the evolution of scheduling approaches, focusing on distributed environments. We also evaluate the current approaches for process behavior extraction and prediction, aiming at selecting an adequate technique for online prediction of application execution. Based on this evaluation, we propose a novel model for application behavior prediction, considering chaotic properties of such behavior and the automatic detection of critical execution points. The proposed model is applied and evaluated for process scheduling in cluster and grid computing environments. The obtained results demonstrate that prediction of the process behavior is essential for efficient scheduling in large-scale and heterogeneous distributed environments, outperforming conventional scheduling policies by a factor of 10, and even more in some cases. Furthermore, the proposed approach proves to be efficient for online predictions due to its low computational cost and good precision. (C) 2009 Elsevier B.V. All rights reserved.

Prediction of dynamical, nonlinear, and unstable process behavior

Process scheduling techniques consider the current load situation to allocate computing resources. Those techniques make approximations such as the average of communication, processing, and memory access to improve the process scheduling, although processes may present different behaviors during their whole execution. They may start with high communication requirements and later just processing. By discovering how processes behave over time, we believe it is possible to improve the resource allocation. This has motivated this paper which adopts chaos theory concepts and nonlinear prediction techniques in order to model and predict process behavior. Results confirm the radial basis function technique which presents good predictions and also low processing demands show what is essential in a real distributed environment.

Crop rotation scheduling with adjacency constraints

In this article we propose a 0-1 optimization model to determine a crop rotation schedule for each plot in a cropping area. The rotations have the same duration in all the plots and the crops are selected to maximize plot occupation. The crops may have different production times and planting dates. The problem includes planting constraints for adjacent plots and also for sequences of crops in the rotations. Moreover, cultivating crops for green manuring and fallow periods are scheduled into each plot. As the model has, in general, a great number of constraints and variables, we propose a heuristics based on column generation. To evaluate the performance of the model and the method, computational experiments using real-world data were performed. The solutions obtained indicate that the method generates good results.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (I the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry`s own practice. (c) 2006 Elsevier Ltd. All rights reserved.

Scheduling Grid Applications with Software Requirements

The aim of task scheduling is to minimize the makespan of applications, exploiting the best possible way to use shared resources. Applications have requirements which call for customized environments for their execution. One way to provide such environments is to use virtualization on demand. This paper presents two schedulers based on integer linear programming which schedule virtual machines (VMs) in grid resources and tasks on these VMs. The schedulers differ from previous work by the joint scheduling of tasks and VMs and by considering the impact of the available bandwidth on the quality of the schedule. Experiments show the efficacy of the schedulers in scenarios with different network configurations.

Tempol ameliorates murine viral encephalomyelitis by preserving the blood-brain barrier, reducing viral load, and lessening inflammation

Multiple sclerosis (MS) is a progressive inflammatory and/or demyelinating disease of the human central nervous system (CNS). Most of the knowledge about the pathogenesis of MS has been derived from murine models, such as experimental autoimmune encephalomyelitis and vital encephalomyelitis. Here, we infected female C57BL/6 mice with a neurotropic strain of the mouse hepatitis virus (MHV-59A) to evaluate whether treatment with the multifunctional antioxidant tempol (4-hydroxy-2,2,6,6-tetramethyl-1-piperidinyloxy) affects the ensuing encephalomyelitis. In untreated animals, neurological symptoms developed quickly: 90% of infected mice died 10 days after virus inoculation and the few survivors presented neurological deficits. Treatment with tempol (24 mg/kg, ip, two doses on the first day and daily doses for 7 days plus 2 mM tempol in the drinking water ad libitum) profoundly altered the disease outcome: neurological symptoms were attenuated, mouse survival increased up to 70%, and half of the survivors behaved as normal mice. Not Surprisingly, tempol substantially preserved the integrity of the CNS, including the blood-brain barrier. Furthermore, treatment with tempol decreased CNS vital titers, macrophage and T lymphocyte infiltration, and levels of markers of inflammation, such as expression of inducible nitric oxide synthase, transcription of tumor necrosis factor-alpha and interferon-gamma, and protein nitration. The results indicate that tempol ameliorates murine viral encephalomyelitis by altering the redox status of the infectious environment that contributes to an attenuated CNS inflammatory response. overall, our study supports the development of therapeutic strategies based on nitroxides to manage neuroinflammatory diseases, including MS. (C) 2009 Elsevier Inc. All rights reserved.

Nickel catalysts supported on ZrO2, Y2O3-stabilized ZrO2 and CaO-stabilized ZrO2 for the steam reforming of ethanol: Effect of the support and nickel load

Catalysts with various nickel loads were prepared on supports of ZrO2, ZrO2-Y2O3 and ZrO2-CaO, characterized by XRD and TPR and tested for activity in ethanol steam reforming. XRD of the supports identified the monoclinic crystalline phase in the ZrO2 and cubic phases in the ZrO2-Y2O3 and ZrO2-CaO supports. In the catalysts, the nickel impregnated on the supports was identified as the NiO phase. In the TPR analysis, peaks were observed showing the NiO phase having different interactions with the supports. In the catalytic tests, practically all the catalysts achieved 100% ethanol conversion, H-2 yield was near 70% and the gaseous concentrations of the other co-products varied in accordance with the equilibrium among them, affected principally by the supports. It was observed that when the ZrO2 was modified with Y2O3 and CaO, there were big changes in the CO and CO2 concentrations, which were attributed to the rise in the number of oxygen vacancies, permitting high-oxygen mobility and affecting the gaseous equilibrium. The liquid products analysis showed a low selectivity to liquid co-products during the reforming reactions. (c) 2007 Published by Elsevier B.V.

A Unified Load Generator for Geographically Distributed Generation ofNetwork Traffic

During the last decade, the Internet usage has been growing at an enormous rate which has beenaccompanied by the developments of network applications (e.g., video conference, audio/videostreaming, E-learning, E-Commerce and real-time applications) and allows several types ofinformation including data, voice, picture and media streaming. While end-users are demandingvery high quality of service (QoS) from their service providers, network undergoes a complex trafficwhich leads the transmission bottlenecks. Considerable effort has been made to study thecharacteristics and the behavior of the Internet. Simulation modeling of computer networkcongestion is a profitable and effective technique which fulfills the requirements to evaluate theperformance and QoS of networks. To simulate a single congested link, simulation is run with asingle load generator while for a larger simulation with complex traffic, where the nodes are spreadacross different geographical locations generating distributed artificial loads is indispensable. Onesolution is to elaborate a load generation system based on master/slave architecture.

Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

Rate Scheduling for HSDPA in UMTS

The introduction of a new technology High Speed Downlink Packet Access (HSDPA) in the Release 5 of the 3GPP specifications raises the question about its performance capabilities. HSDPA is a promising technology which gives theoretical rates up to 14.4 Mbits. The main objective of this thesis is to discuss the system level performance of HSDPAMainly the thesis exploration focuses on the Packet Scheduler because it is the central entity of the HSDPA design. Due to its function, the Packet Scheduler has a direct impact on the HSDPA system performance. Similarly, it also determines the end user performance, and more specifically the relative performance between the users in the cell.The thesis analyzes several Packet Scheduling algorithms that can optimize the trade-off between system capacity and end user performance for the traffic classes targeted in this thesis.The performance evaluation of the algorithms in the HSDPA system are carried out under computer aided simulations that are assessed under realistic conditions to predict the results as precise on the algorithms efficiency. The simulation of the HSDPA system and the algorithms are coded in C/C++ language

Branch and Bound Algorithm for Multiprocessor Scheduling

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

University Scheduling using Genetic Algorithm

The automated timetabling and scheduling is one of the hardest problem areas. This isbecause of constraints and satisfying those constraints to get the feasible and optimizedschedule, and it is already proved as an NP Complete (1) [1]. The basic idea behind this studyis to investigate the performance of Genetic Algorithm on general scheduling problem underpredefined constraints and check the validity of results, and then having comparative analysiswith other available approaches like Tabu search, simulated annealing, direct and indirectheuristics [2] and expert system. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems and later analysis will prove this argument. The programis written in C++ and analysis is done by using variation in various parameters.

BEE COLONIES APPLIED TO MULTIPROCESSOR SCHEDULING

In order to achieve the high performance, we need to have an efficient scheduling of a parallelprogram onto the processors in multiprocessor systems that minimizes the entire executiontime. This problem of multiprocessor scheduling can be stated as finding a schedule for ageneral task graph to be executed on a multiprocessor system so that the schedule length can be minimize [10]. This scheduling problem is known to be NP- Hard.In multi processor task scheduling, we have a number of CPU’s on which a number of tasksare to be scheduled that the program’s execution time is minimized. According to [10], thetasks scheduling problem is a key factor for a parallel multiprocessor system to gain betterperformance. A task can be partitioned into a group of subtasks and represented as a DAG(Directed Acyclic Graph), so the problem can be stated as finding a schedule for a DAG to beexecuted in a parallel multiprocessor system so that the schedule can be minimized. Thishelps to reduce processing time and increase processor utilization. The aim of this thesis workis to check and compare the results obtained by Bee Colony algorithm with already generatedbest known results in multi processor task scheduling domain.

Load and Season Adapted Solar Collectors

In Sweden solar irradiation and space heating loads are unevenly distributed over the year. Domestic hot water loads may be nearly constant. Test results on solar collector performance are often reported as yearly output of a certain collector at fixed temperatures, e g 25, 50 and 75 C. These data are not suitable for dimensioning of solar systems, because the actual performance of the collector depends heavily on solar fraction and load distribution over the year.At higher latitudes it is difficult to attain high solar fractions for buildings, due to overheating in summer and small marginal output for added collector area. Solar collectors with internal reflectors offer possibilities to evade overheating problems and deliver more energy at seasons when the load is higher. There are methods for estimating the yearly angular irradiation distribution, but there is a lack of methods for describing the load and the storage in such a way as to enable optical design of season and load adapted collectors.This report describes two methods for estimation of solar system performance with relevance for season and load adaption. Results regarding attainable solar fractions as a function of collector features, load profiles, load levels and storage characteristics are reported. The first method uses monthly collector output data at fixed temperatures from the simulation program MINSUN for estimating solar fractions for different load profiles and load levels. The load level is defined as estimated yearly collector output at constant collector temperature divided be yearly load. This table may examplify the results:CollectorLoadLoadSolar Improvementtypeprofile levelfractionover flat plateFlat plateDHW 75 %59 %Load adaptedDHW 75 %66 %12 %Flat plateSpace heating 50 %22 %Load adaptedSpace heating 50 %28 %29 %The second method utilises simulations with one-hour timesteps for collectors connected to a simplified storage and a variable load. Collector output, optical and thermal losses, heat overproduction, load level and storage temperature are presented as functions of solar incidence angles. These data are suitable for optical design of load adapted solar collectors. Results for a Stockholm location indicate that a solar combisystem with a solar fraction around 30 % should have collectors that reduce heat production at solar heights above 30 degrees and have optimum efficiency for solar heights between 8 and 30 degrees.

Load Adapted Solar Thermal Combisystems - Optical Analysis and Systems Optimization

In a northern European climate a typical solar combisystem for a single family house normally saves between 10 and 30 % of the auxiliary energy needed for space heating and domestic water heating. It is considered uneconomical to dimension systems for higher energy savings. Overheating problems may also occur. One way of avoiding these problems is to use a collector that is designed so that it has a low optical efficiency in summer, when the solar elevation is high and the load is small, and a high optical efficiency in early spring and late fall when the solar elevation is low and the load is large.The study investigates the possibilities to design the system and, in particular, the collector optics, in order to match the system performance with the yearly variations of the heating load and the solar irradiation. It seems possible to design practically viable load adapted collectors, and to use them for whole roofs ( 40 m2) without causing more overheating stress on the system than with a standard 10 m2 system. The load adapted collectors collect roughly as much energy per unit area as flat plate collectors, but they may be produced at a lower cost due to lower material costs. There is an additional potential for a cost reduction since it is possible to design the load adapted collector for low stagnation temperatures making it possible to use less expensive materials. One and the same collector design is suitable for a wide range of system sizes and roof inclinations. The report contains descriptions of optimized collector designs, properties of realistic collectors, and results of calculations of system output, stagnation performance and cost performance. Appropriate computer tools for optical analysis, optimization of collectors in systems and a very fast simulation model have been developed.