A parallel formulation for the simulation of a generic branch predictor

A parallel formulation for the simulation of a branch prediction algorithm is presented. This parallel formulation identifies independent tasks in the algorithm which can be executed concurrently. The parallel implementation is based on the multithreading model and two parallel programming platforms: pthreads and Cilk++. Improvement in execution performance by up to 7 times is observed for a generic 2-bit predictor in a 12-core multiprocessor system.

Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred as Bit-index sort, which is a non-comparison sorting algorithm for partial per-mutations, with linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers supported by machine hardware to retrieve the ordered output sequence. Results show that Bit-index sort outperforms in execution time to quicksort and counting sort algorithms. A parallel approach for Bit-index sort using two simultaneous threads is included, which obtains speedups up to 1.6.

Genetic dissection of vitamin E biosynthesis in tomato

Vegetables are critical for human health as they are a source of multiple vitamins including vitamin E (VTE). In plants, the synthesis of VTE compounds, tocopherol and tocotrienol, derives from precursors of the shikimate and methylerythritol phosphate pathways. Quantitative trait loci (QTL) for alpha-tocopherol content in ripe fruit have previously been determined in an Solanum pennellii tomato introgression line population. In this work, variations of tocopherol isoforms (alpha, beta, gamma, and delta) in ripe fruits of these lines were studied. In parallel all tomato genes structurally associated with VTE biosynthesis were identified and mapped. Previously identified VTE QTL on chromosomes 6 and 9 were confirmed whilst novel ones were identified on chromosomes 7 and 8. Integrated analysis at the metabolic, genetic and genomic levels allowed us to propose 16 candidate loci putatively affecting tocopherol content in tomato. A comparative analysis revealed polymorphisms at nucleotide and amino acid levels between Solanum lycopersicum and S. pennellii candidate alleles. Moreover, evolutionary analyses showed the presence of codons evolving under both neutral and positive selection, which may explain the phenotypic differences between species. These data represent an important step in understanding the genetic determinants of VTE natural variation in tomato fruit and as such in the ability to improve the content of this important nutriceutical.

A Parallel Hardware Architecture for Scale and Rotation Invariant Feature Detection

This paper proposes a parallel hardware architecture for image feature detection based on the Scale Invariant Feature Transform algorithm and applied to the Simultaneous Localization And Mapping problem. The work also proposes specific hardware optimizations considered fundamental to embed such a robotic control system on-a-chip. The proposed architecture is completely stand-alone; it reads the input data directly from a CMOS image sensor and provides the results via a field-programmable gate array coupled to an embedded processor. The results may either be used directly in an on-chip application or accessed through an Ethernet connection. The system is able to detect features up to 30 frames per second (320 x 240 pixels) and has accuracy similar to a PC-based implementation. The achieved system performance is at least one order of magnitude better than a PC-based solution, a result achieved by investigating the impact of several hardware-orientated optimizations oil performance, area and accuracy.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Pharmacogenetics of Warfarin: Development of a Dosing Algorithm for Brazilian Patients

A dosing algorithm including genetic (VKORC1 and CYP2C9 genotypes) and nongenetic factors (age, weight, therapeutic indication, and cotreatment with amiodarone or simvastatin) explained 51% of the variance in stable weekly warfarin doses in 390 patients attending an anticoagulant clinic in a Brazilian public hospital. The VKORC1 3673G>A genotype was the most important predictor of warfarin dose, with a partial R(2) value of 23.9%. Replacing the VKORC1 3673G>A genotype with VKORC1 diplotype did not increase the algorithm`s predictive power. We suggest that three other single-nucleotide polymorphisms (SNPs) (5808T>G, 6853G>C, and 9041G>A) that are in strong linkage disequilibrium (LD) with 3673G>A would be equally good predictors of the warfarin dose requirement. The algorithm`s predictive power was similar across the self-identified ""race/color"" subsets. ""Race/color"" was not associated with stable warfarin dose in the multiple regression model, although the required warfarin dose was significantly lower (P = 0.006) in white (29 +/- 13 mg/week, n = 196) than in black patients (35 +/- 15 mg/week, n = 76).

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.

Estimation of genetic variance for macro- and micro-environmental sensitivity using double hierarchical generalized linear models

Background: Genetic variation for environmental sensitivity indicates that animals are genetically different in their response to environmental factors. Environmental factors are either identifiable (e.g. temperature) and called macro-environmental or unknown and called micro-environmental. The objectives of this study were to develop a statistical method to estimate genetic parameters for macro- and micro-environmental sensitivities simultaneously, to investigate bias and precision of resulting estimates of genetic parameters and to develop and evaluate use of Akaike’s information criterion using h-likelihood to select the best fitting model. Methods: We assumed that genetic variation in macro- and micro-environmental sensitivities is expressed as genetic variance in the slope of a linear reaction norm and environmental variance, respectively. A reaction norm model to estimate genetic variance for macro-environmental sensitivity was combined with a structural model for residual variance to estimate genetic variance for micro-environmental sensitivity using a double hierarchical generalized linear model in ASReml. Akaike’s information criterion was constructed as model selection criterion using approximated h-likelihood. Populations of sires with large half-sib offspring groups were simulated to investigate bias and precision of estimated genetic parameters. Results: Designs with 100 sires, each with at least 100 offspring, are required to have standard deviations of estimated variances lower than 50% of the true value. When the number of offspring increased, standard deviations of estimates across replicates decreased substantially, especially for genetic variances of macro- and micro-environmental sensitivities. Standard deviations of estimated genetic correlations across replicates were quite large (between 0.1 and 0.4), especially when sires had few offspring. Practically, no bias was observed for estimates of any of the parameters. Using Akaike’s information criterion the true genetic model was selected as the best statistical model in at least 90% of 100 replicates when the number of offspring per sire was 100. Application of the model to lactation milk yield in dairy cattle showed that genetic variance for micro- and macro-environmental sensitivities existed. Conclusion: The algorithm and model selection criterion presented here can contribute to better understand genetic control of macro- and micro-environmental sensitivities. Designs or datasets should have at least 100 sires each with 100 offspring.

Genetic heterogeneity of residual variance : estimation of variance components using double hierarchical generalized linear models

Background: The sensitivity to microenvironmental changes varies among animals and may be under genetic control. It is essential to take this element into account when aiming at breeding robust farm animals. Here, linear mixed models with genetic effects in the residual variance part of the model can be used. Such models have previously been fitted using EM and MCMC algorithms. Results: We propose the use of double hierarchical generalized linear models (DHGLM), where the squared residuals are assumed to be gamma distributed and the residual variance is fitted using a generalized linear model. The algorithm iterates between two sets of mixed model equations, one on the level of observations and one on the level of variances. The method was validated using simulations and also by re-analyzing a data set on pig litter size that was previously analyzed using a Bayesian approach. The pig litter size data contained 10,060 records from 4,149 sows. The DHGLM was implemented using the ASReml software and the algorithm converged within three minutes on a Linux server. The estimates were similar to those previously obtained using Bayesian methodology, especially the variance components in the residual variance part of the model. Conclusions: We have shown that variance components in the residual variance part of a linear mixed model can be estimated using a DHGLM approach. The method enables analyses of animal models with large numbers of observations. An important future development of the DHGLM methodology is to include the genetic correlation between the random effects in the mean and residual variance parts of the model as a parameter of the DHGLM.

Use of genetic algorithms and solvation potential to study peptides structure

In this work, genetic algorithms concepts along with a rotamer library for proteins side chains and implicit solvation potential are used to optimize the tertiary structure of peptides. We starting from the known PDB structure of its backbone which is kept fixed while the side chains allowed adopting the conformations present in the rotamer library. It was used rotamer library independent of backbone and a implicit solvation potential. The structure of Mastoporan-X was predicted using several force fields with a growing complexity; we started it with a field where the only present interaction was Lennard-Jones. We added the Coulombian term and we considered the solvation effects through a term proportional to the solvent accessible area. This paper present good and interesting results obtained using the potential with solvation term and rotamer library. Hence, the algorithm (called YODA) presented here can be a good tool to the prediction problem. (c) 2007 Elsevier B.V. All rights reserved.

Genetic parameters of milk, fat, and protein yields in the first three lactations, using an animal model and restricted maximum likelihood

Milk, fat, and protein yields of Holstein cows from the States of New York and California in the United States were used to estimate (co)variances among yields in the first three lactations, using an animal model and a derivative-free restricted maximum likelihood (REML) algorithm, and to verify if yields in different lactations are the same trait. The data were split in 20 samples, 10 from each state, with means of 5463 and 5543 cows per sample from California and New York. Mean heritability estimates for milk, fat, and protein yields for California data were, respectively, 0.34, 0.35, and 0.40 for first; 0.31, 0.33, and 0.39 for second; and 0.28, 0.31, and 0.37 for third lactations. For New York data, estimates were 0.35, 0.40, and 0.34 for first; 0.34, 0.44, and 0.38 for second; and 0.32, 0.43, and 0.38 for third lactations. Means of estimates of genetic correlations between first and second, first and third, and second and third lactations for California data were 0.86, 0.77, and 0.96 for milk; 0.89, 0.84, and 0.97 for fat; and 0.90, 0.84, and 0.97 for protein yields. Mean estimates for New York data were 0.87, 0.81, and 0.97 for milk; 0.91, 0.86, and 0.98 for fat; and 0.88, 0.82, and 0.98 for protein yields. Environmental correlations varied from 0.30 to 0.50 and were larger between second and third lactations. Phenotypic correlations were similar for both states and varied from 0.52 to 0.66 for milk, fat and protein yields. These estimates are consistent with previous estimates obtained with animal models. Yields in different lactations are not statistically the same trait but for selection programs such yields can be modelled as the same trait because of the high genetic correlations.

Parallel simulated annealing applied to long term transmission network expansion planning

The simulated annealing optimization technique has been successfully applied to a number of electrical engineering problems, including transmission system expansion planning. The method is general in the sense that it does not assume any particular property of the problem being solved, such as linearity or convexity. Moreover, it has the ability to provide solutions arbitrarily close to an optimum (i.e. it is asymptotically convergent) as the cooling process slows down. The drawback of the approach is the computational burden: finding optimal solutions may be extremely expensive in some cases. This paper presents a Parallel Simulated Annealing, PSA, algorithm for solving the long term transmission network expansion planning problem. A strategy that does not affect the basic convergence properties of the Sequential Simulated Annealing algorithm have been implementeded and tested. The paper investigates the conditions under which the parallel algorithm is most efficient. The parallel implementations have been tested on three example networks: a small 6-bus network, and two complex real-life networks. Excellent results are reported in the test section of the paper: in addition to reductions in computing times, the Parallel Simulated Annealing algorithm proposed in the paper has shown significant improvements in solution quality for the largest of the test networks.

Genetic variation along time in a brazilian population of Aedes aegypti (Diptera : Culicidae), detected by changes in the esterase patterns

Aedes aegypti from the Brazilian cities of Sao Jose do Rio Preto (SJ) and Goiania (GO) were analyzed as to their esterase patterns and the results were compared with data obtained about 5 years before for SJ population. Esterase bands not detected in the previous study were now observed in mosquitoes from both SJ and GO populations, being the last considered a population resistant to insecticides. Other similarities between SJ and GO populations in this study, and some differences in comparison with the previous data on SJ were observed, involving, in addition to changes in band type, changes in frequency of mosquitoes expressing them and differential gene activation during development. As it is generally true for genetic features, changes in the esterase patterns are expected to be the result of factors such as selection by environmental conditions and genetic drift. In the present case, continuous use of insecticides aiming mosquito population size control in SJ by sanitary authorities could be involved in the observed changes. Changed esterases were classified as carboxylesterases and cholinesterases, which are enzymes already shown to take part in the development of resistance in several organisms. In addition, data obtained in the elapsed time by authorities responsible for the mosquito control has shown increasing insecticide resistance of SJ population mosquitoes parallel to increase in the total amount of esterases, reinforcing the mentioned possibility.

Genetic divergence in Eucalyptus spp. clones by molecular RAPD markers

The genetic divergence in 20 Eucalyptus spp. clones was evaluated by multivariate techniques based on 167 RAPD markers, of which 155 were polymorphic and 12 monomorphic. The measures of genetic distances were obtained by the arithmetic complement of the coefficients of Jaccard and of Sorenso-Nei and Li and evaluated by the hierarchical methods of Single Linkage clustering and Unweighted Pair Group Method with Arithmetic Mean (UPGMA). Independent of the dissimilarity coefficient, the greatest divergence was found between clones 7 and 17 and the smallest between the clones 11 and 14. Clone clustering was little influenced by the applied procedure so that, adopting the same percentage of divergence, the UPGMA identified two groups less for the coefficient of Sorenso-Nei and Li. The clones evidenced considerable genetic divergence, which is partly associated to the origin of the study material. The clusters formed by the UPGMA clustering algorithm associated to the arithmetic complement of Jaccard were most consistent.

Distribution network reconfiguration using an efficient evolutionary algorithm

Network reconfiguration is an important tool to optimize the operating conditions of a distribution system. This is accomplished modifying the network structure of distribution feeders by changing the open/close status of sectionalizing switches. This not only reduces the power losses, but also relieves the overloading of the network components. Network reconfiguration belongs to a complex family of problems because of their combinatorial nature and multiple constraints. This paper proposes a solution to this problem, using a specialized evolutionary algorithm, with a novel codification, and a brand new way of implement the genetic operators considering the problem characteristics. The algorithm is presented and tested in a real distribution system, showing excellent results and computational efficiency. © 2007 IEEE.