Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques for improving the efficiency of k-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient k-Means variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

Parallel genetic algorithms for the tuning of a fuzzy AQM controller

This paper presents the results of the application of a parallel Genetic Algorithm (GA) in order to design a Fuzzy Proportional Integral (FPI) controller for active queue management on Internet routers. The Active Queue Management (AQM) policies are those policies of router queue management that allow the detection of network congestion, the notification of such occurrences to the hosts on the network borders, and the adoption of a suitable control policy. Two different parallel implementations of the genetic algorithm are adopted to determine an optimal configuration of the FPI controller parameters. Finally, the results of several experiments carried out on a forty nodes cluster of workstations are presented.

A parallel genetic algorithm for the Steiner Problem in Networks

This paper presents a parallel genetic algorithm to the Steiner Problem in Networks. Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the characteristics of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to build a comparison term for validating deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. On the other hand, the large dimensions of our sample networks require the adoption of a parallel implementation of the Steiner GA, which is able to deal with such large problem instances.

Parallel convolutional coder

A parallel convolutional coder (104) comprising: a plurality of serial convolutional coders (108) each having a register with a plurality of memory cells and a plurality of serial coder outputs,- input means (120) from which data can be transferred in parallel into the registers,- and a parallel coder output (124) comprising a plurality of output memory cells each of which is connected to one of the serial coder outputs so that data can be transferred in parallel from all of the serial coders to the parallel coder output.

Numerical simulation of the 12 May 1997 CME Event: The role of magnetic reconnection

We perform a numerical study of the evolution of a Coronal Mass Ejection (CME) and its interaction with the coronal magnetic field based on the 12 May 1997, CME event using a global MagnetoHydroDynamic (MHD) model for the solar corona. The ambient solar wind steady-state solution is driven by photospheric magnetic field data, while the solar eruption is obtained by superimposing an unstable flux rope onto the steady-state solution. During the initial stage of CME expansion, the core flux rope reconnects with the neighboring field, which facilitates lateral expansion of the CME footprint in the low corona. The flux rope field also reconnects with the oppositely orientated overlying magnetic field in the manner of the breakout model. During this stage of the eruption, the simulated CME rotates counter-clockwise to achieve an orientation that is in agreement with the interplanetary flux rope observed at 1 AU. A significant component of the CME that expands into interplanetary space comprises one of the side lobes created mainly as a result of reconnection with the overlying field. Within 3 hours, reconnection effectively modifies the CME connectivity from the initial condition where both footpoints are rooted in the active region to a situation where one footpoint is displaced into the quiet Sun, at a significant distance (≈1R ) from the original source region. The expansion and rotation due to interaction with the overlying magnetic field stops when the CME reaches the outer edge of the helmet streamer belt, where the field is organized on a global scale. The simulation thus offers a new view of the role reconnection plays in rotating a CME flux rope and transporting its footpoints while preserving its core structure.

Simulation of milk production by dairy cows fed sugarcane top-based diets with locally available supplements under Indian conditions

A model of sugarcane digestion was applied to indicate the suitability of various locally available supplements for enhancing milk production of Indian crossbred dairy cattle. Milk production was calculated according to simulated energy, lipogenic, glucogenic and aminogenic substrate availability. The model identified the most limiting substrate for milk production from different sugarcane-based diets. For sugarcane tops/urea fed alone, milk production was most limited by amino acid followed by long chain fatty acid availability. Among the protein-rich oil cake supplements at 100, 200 and 300 g supplement/kg total DM, cottonseed oil cake proved superior with a milk yield of 5.5, 7.3 and 8.3 kg/day, respectively. This was followed by mustard oil cake with 5.1, 6.5 and 7.6 kg/day, respectively. In the case of a protein-rich supplement (fish meal), milk yield was limited to 6.6 kg/day due to a shortage of long chain fatty acids. However, at 300 g of supplementation, energy became limiting, with a milk yield of 6.7 kg/day. Supplementation with rice bran and rice polishings at 100, 200 and 300 g restricted milk yield to 4.3, 4.9 and 5.5 and 4.5, 5.3 and 6.1 kg/day, respectively, and amino acids became the factor limiting milk production. The diet comprising basal sugarcane tops supplemented by leguminous fodder, dry fodder (e.g. rice or wheat straw) and concentrates at levels of 100, 200 and 300 g supplements/kg total diet DM proved to be the most balanced with a milk yield of 5.1, 6.7 and 9.0 kg/day, respectively.

Parallel declines in pollinators and insect-pollinated plants in Britain and the Netherlands

Despite widespread concern about declines in pollination services, little is known about the patterns of change in most pollinator assemblages. By studying bee and hoverfly assemblages in Britain and the Netherlands, we found evidence of declines (pre- versus post-1980) in local bee diversity in both countries; however, divergent trends were observed in hoverflies. Depending on the assemblage and location, pollinator declines were most frequent in habitat and flower specialists, in univoltine species, and/or in nonmigrants. In conjunction with this evidence, outcrossing plant species that are reliant on the declining pollinators have themselves declined relative to other plant species. Taken together, these findings strongly suggest a causal connection between local extinctions of functionally linked plant and pollinator species.

Quantifying uncertainty in the simulation of crop-climate processes

The impacts of climate change on crop productivity are often assessed using simulations from a numerical climate model as an input to a crop simulation model. The precision of these predictions reflects the uncertainty in both models. We examined how uncertainty in a climate (HadAM3) and crop General Large-Area Model (GLAM) for annual crops model affects the mean and standard deviation of crop yield simulations in present and doubled carbon dioxide (CO2) climates by perturbation of parameters in each model. The climate sensitivity parameter (λ, the equilibrium response of global mean surface temperature to doubled CO2) was used to define the control climate. Observed 1966–1989 mean yields of groundnut (Arachis hypogaea L.) in India were simulated well by the crop model using the control climate and climates with values of λ near the control value. The simulations were used to measure the contribution to uncertainty of key crop and climate model parameters. The standard deviation of yield was more affected by perturbation of climate parameters than crop model parameters in both the present-day and doubled CO2 climates. Climate uncertainty was higher in the doubled CO2 climate than in the present-day climate. Crop transpiration efficiency was key to crop model uncertainty in both present-day and doubled CO2 climates. The response of crop development to mean temperature contributed little uncertainty in the present-day simulations but was among the largest contributors under doubled CO2. The ensemble methods used here to quantify physical and biological uncertainty offer a method to improve model estimates of the impacts of climate change.

Simulation of the impact of high temperature stress on annual crop yields

Brief periods of high temperature which occur near flowering can severely reduce the yield of annual crops such as wheat and groundnut. A parameterisation of this well-documented effect is presented for groundnut (i.e. peanut; Arachis hypogaeaL.). This parameterisation was combined with an existing crop model, allowing the impact of season-mean temperature, and of brief high-temperature episodes at various times near flowering, to be both independently and jointly examined. The extended crop model was tested with independent data from controlled environment experiments and field experiments. The impact of total crop duration was captured, with simulated duration being within 5% of observations for the range of season-mean temperatures used (20-28 degrees C). In simulations across nine differently timed high temperature events, eight of the absolute differences between observed and simulated yield were less than 10% of the control (no-stress) yield. The parameterisation of high temperature stress also allows the simulation of heat tolerance across different genotypes. Three parameter sets, representing tolerant, moderately sensitive and sensitive genotypes were developed and assessed. The new parameterisation can be used in climate change studies to estimate the impact of heat stress on yield. It can also be used to assess the potential for adaptation of cropping systems to increased temperature threshold exceedance via the choice of genotype characteristics. (c) 2005 Elsevier B.V. All rights reserved.

Simulation of crop yields using ERA-40: Limits to skill and nonstationarity in weather-yield relationships

Reanalysis data provide an excellent test bed for impacts prediction systems. because they represent an upper limit on the skill of climate models. Indian groundnut (Arachis hypogaea L.) yields have been simulated using the General Large-Area Model (GLAM) for annual crops and the European Centre for Medium-Range Weather Forecasts (ECMWF) 40-yr reanalysis (ERA-40). The ability of ERA-40 to represent the Indian summer monsoon has been examined. The ability of GLAM. when driven with daily ERA-40 data, to model both observed yields and observed relationships between subseasonal weather and yield has been assessed. Mean yields "were simulated well across much of India. Correlations between observed and modeled yields, where these are significant. are comparable to correlations between observed yields and ERA-40 rainfall. Uncertainties due to the input planting window, crop duration, and weather data have been examined. A reduction in the root-mean-square error of simulated yields was achieved by applying bias correction techniques to the precipitation. The stability of the relationship between weather and yield over time has been examined. Weather-yield correlations vary on decadal time scales. and this has direct implications for the accuracy of yield simulations. Analysis of the skewness of both detrended yields and precipitation suggest that nonclimatic factors are partly responsible for this nonstationarity. Evidence from other studies, including data on cereal and pulse yields, indicates that this result is not particular to groundnut yield. The detection and modeling of nonstationary weather-yield relationships emerges from this study as an important part of the process of understanding and predicting the impacts of climate variability and change on crop yields.

Quantification of physical and biological uncertainty in the simulation of the yield of a tropical crop using present-day and doubled CO2 climates

The impacts of climate change on crop productivity are often assessed using simulations from a numerical climate model as an input to a crop simulation model. The precision of these predictions reflects the uncertainty in both models. We examined how uncertainty in a climate (HadAM3) and crop General Large-Area Model (GLAM) for annual crops model affects the mean and standard deviation of crop yield simulations in present and doubled carbon dioxide (CO2) climates by perturbation of parameters in each model. The climate sensitivity parameter (lambda, the equilibrium response of global mean surface temperature to doubled CO2) was used to define the control climate. Observed 1966-1989 mean yields of groundnut (Arachis hypogaea L.) in India were simulated well by the crop model using the control climate and climates with values of lambda near the control value. The simulations were used to measure the contribution to uncertainty of key crop and climate model parameters. The standard deviation of yield was more affected by perturbation of climate parameters than crop model parameters in both the present-day and doubled CO2 climates. Climate uncertainty was higher in the doubled CO2 climate than in the present-day climate. Crop transpiration efficiency was key to crop model uncertainty in both present-day and doubled CO2 climates. The response of crop development to mean temperature contributed little uncertainty in the present-day simulations but was among the largest contributors under doubled CO2. The ensemble methods used here to quantify physical and biological uncertainty offer a method to improve model estimates of the impacts of climate change.

Amino acid pairing preferences in parallel beta-sheets in proteins

Statistical approaches have been applied to examine amino acid pairing preferences within parallel beta-sheets. The main chain hydrogen bonding pattern in parallel beta-sheets means that, for each residue pair, only one of the residues is involved in main chain hydrogen bonding with the strand containing the partner residue. We call this the hydrogen bonded (HB) residue and the partner residue the non-hydrogen bonded (nHB) residue, and differentiate between the favorability of a pair and that of its reverse pair, e.g. Asn(HB)-Thr(nHB)versus Thr(HB)-Asn(nHB). Significantly (p < or = 0.000001) favoured pairings were rationalised using stereochemical arguments. For instance, Asn(HB)-Thr(nHB) and Arg(HB)-Thr(nHB) were favoured pairs, where the residues adopted favoured chi1 rotamer positions that allowed side-chain interactions to occur. In contrast, Thr(HB)-Asn(nHB) and Thr(HB)-Arg(nHB) were not significantly favoured, and could only form side-chain interactions if the residues involved adopted less favourable chi1 conformations. The favourability of hydrophobic pairs e.g. Ile(HB)-Ile(nHB), Val(HB)-Val(nHB) and Leu(HB)-Ile(nHB) was explained by the residues adopting their most preferred chi1 and chi2 conformations, which enabled them to form nested arrangements. Cysteine-cysteine pairs are significantly favoured, although these do not form intrasheet disulphide bridges. Interactions between positively and negatively charged residues were asymmetrically preferred: those with the negatively charged residue at the HB position were more favoured. This trend was accounted for by the presence of general electrostatic interactions, which, based on analysis of distances between charged atoms, were likely to be stronger when the negatively charged residue is the HB partner. The Arg(HB)-Asp(nHB) interaction was an exception to this trend and its favorability was rationalised by the formation of specific side-chain interactions. This research provides rules that could be applied to protein structure prediction, comparative modelling and protein engineering and design. The methods used to analyse the pairing preferences are automated and detailed results are available (http://www.rubic.rdg.ac.uk/betapairprefsparallel/).

Amino acid pairing preferences in parallel beta-sheets in proteins

Statistical approaches have been applied to examine amino acid pairing preferences within parallel beta-sheets. The main chain hydrogen bonding pattern in parallel beta-sheets means that, for each residue pair, only one of the residues is involved in main chain hydrogen bonding with the strand containing the partner residue. We call this the hydrogen bonded (HB) residue and the partner residue the non-hydrogen bonded (nHB) residue, and differentiate between the favourability of a pair and that of its reverse pair, e.g. Asn(HB)-Thr(nHB) versus Thr(HB)-Asn(nHB). Significantly (p <= 0.000001) favoured pairings were rationalised using stereochemical arguments. For instance, Asn(HB)-Thr(nHB) and Arg(HB)-Thr(nHB) were favoured pairs, where the residues adopted favoured chi(1) rotamer positions that allowed side-chain interactions to occur. In contrast, Thr(HB)-Asn(nHB) and Thr(HB)-Arg(nHB) were not significantly favoured, and could only form side-chain interactions if the residues involved adopted less favourable chi(1) conformations. The favourability of hydrophobic pairs e.g. Ile(HB)-Ile(nHB), Val(HB)-Val(nHB) and Leu(HB)-Ile(nHB) was explained by the residues adopting their most preferred chi(1) and chi(2) conformations, which enabled them to form nested arrangements. Cysteine-cysteine pairs are significantly favoured, although these do not form intrasheet disulphide bridges. Interactions between positively and negatively charged residues were asymmetrically preferred: those with the negatively charged residue at the HB position were more favoured. This trend was accounted for by the presence of general electrostatic interactions, which, based on analysis of distances between charged atoms, were likely to be stronger when the negatively charged residue is the HB partner. The Arg(HB)-Asp(nHB) interaction was an exception to this trend and its favourability was rationalised by the formation of specific side-chain interactions. This research provides rules that could be applied to protein structure prediction, comparative modelling and protein engineering and design. The methods used to analyse the pairing preferences are automated and detailed results are available (http:// www.rubic.rdg.ac.uk/betapairprefsparallel/). (c) 2005 Elsevier Ltd. All rights reserved.

A suite of parallel vectors for baculovirus expression

The expression of proteins using recombinant baculoviruses is a mature and widely used technology. However, some aspects of the technology continue to detract from high throughput use and the basis of the final observed expression level is poorly understood. Here, we describe the design and use of a set of vectors developed around a unified cloning strategy that allow parallel expression of target proteins in the baculovirus system as N-terminal or C-terminal fusions. Using several protein kinases as tests we found that amino-terminal fusion to maltose binding protein rescued expression of the poorly expressed human kinase Cot but had only a marginal effect on expression of a well-expressed kinase IKK-2. In addition, MBP fusion proteins were found to be secreted from the expressing cell. Use of a carboxyl-terminal GFP tagging vector showed that fluorescence measurement paralleled expression level and was a convenient readout in the context of insect cell expression, an observation that was further supported with additional non-kinase targets. The expression of the target proteins using the same vectors in vitro showed that differences in expression level were wholly dependent on the environment of the expressing cell and an investigation of the time course of expression showed it could affect substantially the observed expression level for poorly but not well-expressed proteins. Our vector suite approach shows that rapid expression survey can be achieved within the baculovirus system and in addition, goes some way to identifying the underlying basis of the expression level obtained. (c) 2006 Elsevier Inc. All rights reserved.