SEARCH · PubMed Health

Results for “Parallel Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8Linked to original sources

PubMed2005

Parallel statistical image reconstruction for cone-beam x-ray CT on a shared memory computation platform.

Statistical reconstruction methods offer possibilities of improving image quality as compared to analytical methods, but current reconstruction times prohibit routine clinical applications. To reduce reconstruction times we have parallelized a statistical reconstruction algorithm for cone-beam x-ray CT, the ordered subset convex algorithm (OSC), and evaluated it on a shared memory computer. Two different parallelization strategies were developed: one that employs parallelism by computing the work for all projections within a subset in parallel, and one that divides the total volume into parts and processes the work for each sub-volume in parallel. Both methods are used to reconstruct a three-dimensional mathematical phantom on two different grid densities. The reconstructed images are binary identical to the result of the serial (non-parallelized) algorithm. The speed-up factor equals approximately 30 when using 32 to 40 processors, and scales almost linearly with the number of cpus for both methods. The huge reduction in computation time allows us to apply statistical reconstruction to clinically relevant studies for the first time.

Algorithms↗

PubMed2006

Simulated annealing in ocular adaptive optics.

We present what is to our knowledge a first hardware realization of a simulated annealing algorithm in an adaptive optics system designed to image the retina of the human eye. The algorithm is applied to the retinal image itself without the need for wavefront sensors in the system. We find that this optimization algorithm can be an alternative to the traditional Hartmann-Shack sensing. We also compare the simulated annealing algorithm to the stochastic parallel gradient descent algorithm.

Algorithms↗

PubMed2002

Optimization of polytomies: state set and parallel operations.

New algorithms for calculating the most parsimonious state sets for polytomies under Fitch parsimony are described. Because they are based on state set operations, these algorithms can be extended for optimization of several characters in parallel, thus increasing speed by a significant factor. This speed increase may facilitate analysis of molecular data sets, many of which contain hundreds of taxa, thousands of multistate nonadditive characters, and numerous polytomies.

Algorithms↗

PubMed2006

Striped Smith-Waterman speeds database searches six times over other SIMD implementations.

MOTIVATION: The only algorithm guaranteed to find the optimal local alignment is the Smith-Waterman. It is also one of the slowest due to the number of computations required for the search. To speed up the algorithm, Single-Instruction Multiple-Data (SIMD) instructions have been used to parallelize the algorithm at the instruction level. RESULTS: A faster implementation of the Smith-Waterman algorithm is presented. This algorithm achieved 2-8 times performance improvement over other SIMD based Smith-Waterman implementations. On a 2.0 GHz Xeon Core 2 Duo processor, speeds of >3.0 billion cell updates/s were achieved. AVAILABILITY: http://farrar.michael.googlepages.com/Smith-waterman

Algorithms↗

PubMed2006

Tilted cone-beam reconstruction with row-wise fan-to-parallel rebinning.

Reconstruction algorithms for cone-beam CT have been the focus of many studies. Several exact and approximate reconstruction algorithms were proposed for step-and-shoot and helical scanning trajectories to combat cone-beam related artefacts. In this paper, we present a new closed-form cone-beam reconstruction formula for tilted gantry data acquisition. Although several algorithms were proposed in the past to combat errors induced by the gantry tilt, none of the algorithms addresses the scenario in which the cone-beam geometry is first rebinned to a set of parallel beams prior to the filtered backprojection. We show that the image quality advantages of the rebinned parallel-beam reconstruction are significant, which makes the development of such an algorithm necessary. Because of the rebinning process, the reconstruction algorithm becomes more complex and the amount of iso-centre adjustment depends not only on the projection and tilt angles, but also on the reconstructed pixel location. In this paper, we first demonstrate the advantages of the row-wise fan-to-parallel rebinning and derive a closed-form solution for the reconstruction algorithm for the step-and-shoot and constant-pitch helical scans. The proposed algorithm requires the 'warping' of the reconstruction matrix on a view-by-view basis prior to the backprojection step. We further extend the algorithm to the variable-pitch helical scans in which the patient table travels at non-constant speeds. The algorithm was tested extensively on both the 16- and 64-slice CT scanners. The efficacy of the algorithm is clearly demonstrated by multiple experiments.

Algorithms↗

PubMed2004

Roughening of the interfaces in (1+1) -dimensional two-component surface growth with an admixture of random deposition.

We simulate competitive two-component growth on a one-dimensional substrate of L sites. One component is a Poisson-type deposition that generates Kardar-Parisi-Zhang (KPZ) correlations. The other is random deposition (RD). We derive the universal scaling function of the interface width for this model and show that the RD admixture acts as a dilatation mechanism to the fundamental time and height scales, but leaves the KPZ correlations intact. This observation is generalized to other growth models. It is shown that the flat-substrate initial condition is responsible for the existence of an early nonscaling phase in the interface evolution. The length of this initial phase is a nonuniversal parameter, but its presence is universal. We introduce a method to measure the length of this initial nonscaling phase. In application to parallel and distributed computations, the important consequence of the derived scaling is the existence of the upper bound for the desynchronization in a conservative update algorithm for parallel discrete-event simulations. It is shown that such algorithms are generally scalable in a ring communication topology.

Journal Article↗

PubMedDate not supplied

A low-cost system for digital image processing of moving images in real time: application to X-ray fluoroscopy.

A low-cost image processing system and two real-time digital image processing algorithms using parallel processing have been developed to provide automatic equalization of moving images at video frequencies. The algorithms differ in the processing time required and the characteristics of the final image. The system takes an entire image from the video sequence, digitizes it, automatically calculates its histogram and the lowest and highest useful grey levels, equalizes the histogram, and finally converts it to the analogue image. Methods were applied to X-ray fluoroscopy (angiography) images, which are usually saturated or of uniform intensity (low contrast), leading to information loss. An application of these methods is in interventional radiography, which requires images in real time.

Algorithms↗

PubMed2004

Exploring the protein folding free energy landscape: coupling replica exchange method with P3ME/RESPA algorithm.

A highly parallel replica exchange method (REM) that couples with a newly developed molecular dynamics algorithm particle-particle particle-mesh Ewald (P3ME)/RESPA has been proposed for efficient sampling of protein folding free energy landscape. The algorithm is then applied to two separate protein systems, beta-hairpin and a designed protein Trp-cage. The all-atom OPLSAA force field with an explicit solvent model is used for both protein folding simulations. Up to 64 replicas of solvated protein systems are simulated in parallel over a wide range of temperatures. The combined trajectories in temperature and configurational space allow a replica to overcome free energy barriers present at low temperatures. These large scale simulations reveal detailed results on folding mechanisms, intermediate state structures, thermodynamic properties and the temperature dependences for both protein systems.

Algorithms↗

PubMed2006

Seizure detection algorithm for neonates based on wave-sequence analysis.

OBJECTIVE: The description and evaluation of the performance of a new real-time seizure detection algorithm in the newborn infant. METHODS: The algorithm includes parallel fragmentation of EEG signal into waves; wave-feature extraction and averaging; elementary, preliminary and final detection. The algorithm detects EEG waves with heightened regularity, using wave intervals, amplitudes and shapes. The performance of the algorithm was assessed with the use of event-based and liberal and conservative time-based approaches and compared with the performance of Gotman's and Liu's algorithms. RESULTS: The algorithm was assessed on multi-channel EEG records of 55 neonates including 17 with seizures. The algorithm showed sensitivities ranging 83-95% with positive predictive values (PPV) 48-77%. There were 2.0 false positive detections per hour. In comparison, Gotman's algorithm (with 30s gap-closing procedure) displayed sensitivities of 45-88% and PPV 29-56%; with 7.4 false positives per hour and Liu's algorithm displayed sensitivities of 96-99%, and PPV 10-25%; with 15.7 false positives per hour. CONCLUSIONS: The wave-sequence analysis based algorithm displayed higher sensitivity, higher PPV and a substantially lower level of false positives than two previously published algorithms. SIGNIFICANCE: The proposed algorithm provides a basis for major improvements in neonatal seizure detection and monitoring.

Algorithms↗

PubMed2003

Peptide folding simulations.

Developments in the design of small peptides that mimic proteins in complexity, recent advances in nanosecond time-resolved spectroscopy methods to study peptides and the development of modern, highly parallel simulation algorithms have come together to give us a detailed picture of peptide folding dynamics. Two newly implemented simulation techniques, parallel replica dynamics and replica exchange molecular dynamics, can now describe directly from simulations the kinetics and thermodynamics of peptide formation, respectively. Given these developments, the simulation community now has the tools to verify and validate simulation protocols and models (forcefields).

Computer Simulation↗

PubMedDate not supplied

Medical volume visualization on general-purpose parallel architectures.

Parallel volume visualization is of interest to a variety of application areas since current single-processor systems fall short in interactively rendering complex, large-sized datasets. This article presents a survey of volume-visualization methods on general-purpose parallel architectures, with special attention being paid to medical imaging applications. First, the various approaches to volume visualization are briefly discussed, followed by a description of relevant aspects of parallel architectures. Next, the implications of the various architectures are illustrated on the basis of a number of existing implementations of visualization algorithms on parallel architectures and their results. For parallel volume visualization, multiple instruction, multiple data (MIMD) architectures are found to be superior to single instruction, multiple data (SIMD) architectures. The latter type suffers from a lack of performance as well as flexibility. For most applications of interactive volume visualization, including the important area of medical imaging, shared memory MIMD architectures are preferred over distributed memory MIMD architectures. The ease of programming of shared memory architectures allows existing algorithms to be readily implemented without loss of performance or flexibility.

Algorithms↗

PubMed2001

Extended state-space Monte Carlo methods.

In this paper various extensions of the parallel-tempering algorithm are developed and their properties are analyzed. The algorithms are designed to alleviate quasiergodic sampling in systems which have rough energy landscapes by coupling individual Monte Carlo chains to form a composite chain. As with parallel tempering, the procedures are based upon extending the state space to include parameters to encourage sampling mobility. One of the drawbacks of the parallel-tempering method is the stochastic nature of the Monte Carlo dynamics in the auxiliary variables which extend the state space. In this work, the possibility of improving the sampling rate by designing deterministic methods of moving through the parameter space is investigated. The methods developed in this article, which are based upon a statistical quenching and heating procedure similar in spirit to simulated annealing, are tested on a simple two-dimensional spin system (xy model) and on a model in vacuo polypeptide system. In the coupled Monte Carlo chain algorithms, we find that the net mobility of the composite chain is determined by the competition between the characteristic time of coupling between adjacent chains and the degree of overlap of their distributions. Extensive studies of all methods are carried out to obtain optimal sampling conditions. In particular, the most efficient parallel-tempering procedure is to attempt to swap configurations after very few Monte Carlo updates of the composite chains. Furthermore, it is demonstrated that, contrary to expectations, the deterministic procedure does not improve the sampling rate over that of parallel tempering.

Journal Article↗

PubMed2006

Comparison of P-RnaPredict and mfold--algorithms for RNA secondary structure prediction.

MOTIVATION: Ribonucleic acid is vital in numerous stages of protein synthesis; it also possesses important functional and structural roles within the cell. The function of an RNA molecule within a particular organic system is principally determined by its structure. The current physical methods available for structure determination are time-consuming and expensive. Hence, computational methods for structure prediction are sought after. The energies involved by the formation of secondary structure elements are significantly greater than those of tertiary elements. Therefore, RNA structure prediction focuses on secondary structure. RESULTS: We present P-RnaPredict, a parallel evolutionary algorithm for RNA secondary structure prediction. The speedup provided by parallelization is investigated with five sequences, and a dramatic improvement in speedup is demonstrated, especially with longer sequences. An evaluation of the performance of P-RnaPredict in terms of prediction accuracy is made through comparison with 10 individual known structures from 3 RNA classes (5S rRNA, Group I intron 16S rRNA and 16S rRNA) and the mfold dynamic programming algorithm. P-RnaPredict is able to predict structures with higher true positive base pair counts and lower false positives than mfold on certain sequences. AVAILABILITY: P-RnaPredict is available for non-commercial usage. Interested parties should contact Kay C. Wiese (wiese@cs.sfu.ca).

Algorithms↗

PubMed2004

[Determining global heart function with real time TrueFISP in one respiratory cycle].

Real-time multislice cine techniques lead to inaccurate results in ventricular volumes based on limited temporal resolution. The purpose of the study is to evaluate a real-time cine technique with parallel imaging algorithms in comparison to standard segmented techniques. Twelve patients underwent cardiac cine MRI using real-time multislice cine trueFISP. Temporal resolution was improved using parallel acquisition techniques (iPAT) and data acquisition was performed in a single breath-hold along the patients' short axis. Evaluation of EDV, ESV, EF and myocardial mass was performed and results compared to a standard segmented single-slice cine trueFISP. Combination of real-time cine trueFISP and iPAT provided a temporal resolution of 48 ms. Results of the multislice approach showed an excellent correlation to standard single-slice trueFISP for EDV (0.94, p <0.001), ESV (0.97, p <0.001) EF (0.99, p <0.001) and myocardial mass (0.93, p <0.001). No significant differences could be found. The use of parallel acquisition techniques (PAT) allow for a substantial improvement of temporal resolution in real-time cine MRI (<50 ms). Therefore these techniques enable an accurate and exact quantification of global ventricular function.

Algorithms↗

PubMed1979

An iterative algorithm for the separation of action potential sequences.

Various iterative algorithms for separation of superimposed event sequences were designed, and their efficiency examined through simulation studies. It has been found that a double parallel-serial algorithm improved markedly the efficiency of the filtration process. For the same probability of detection of the event series to be extracted, the probability of 'impurity' events dropped by roughly 0.10, as compared to the non-iterative fixed window width algorithm. Conclusions are drawn regarding separation of motor unit action potential sequences from the total electromyogram.

Action Potentials↗

PubMed2004

Run-length chain coding and scalable computation of a shape's moments using reconfigurable optical buses.

The main contribution of this paper is the design of several efficient algorithms for modified run-length chain coding and for computing a shape's moments on arrays with reconfigurable optical buses. The proposed algorithms are based on the boundary representation of an object. Instead of using chain code, the boundary can be represented by a modified run-length chain code, where each entity represents a line segment (two adjacent corner pixels). The sequential nature of the chain code makes it difficult to be parallelized. We first propose two constant time algorithms for boundary extraction and run-length chain coding. To the authors' knowledge, these are the most time efficient algorithms yet published. Based on the modified run-length chain coding, and the advantages of both optical transmission and electronic computation, a constant time parallel algorithm for computing a shape's moments using N x N processors is proposed. Additionally, instead of using N x N processors, a scalable moment algorithm using r x r processors is also derived, where r < N. Based on the product of time and the number of processors used, both proposed parallel algorithms are time and cost optimal.

Algorithms↗

PubMed2003

Use of sequential structure in simulation from high-dimensional systems.

Sampling from high-dimensional systems often suffers from the curse of dimensionality. In this paper, we explored the use of sequential structures in sampling from high-dimensional systems with an aim at eliminating the curse of dimensionality, and proposed an algorithm, so-called sequential parallel tempering as an extension of parallel tempering. The algorithm was tested with the witch's hat distribution and Ising model. Numerical results suggest that it is a promising tool for sampling from high-dimensional systems. The efficiency of the algorithm was argued theoretically based on the Rao-Blackwellization theorem.

Journal Article↗

PubMed2001

Improved compensation of turbulence-induced amplitude and phase distortions by means of multiple near-field phase adjustments.

An approach for compensation of turbulence-induced amplitude and phase distortions is described. Two deformable mirrors are placed optically conjugate to the collecting aperture and to a finite range from this aperture. Two control algorithms are presented. The first is a sequential generalized projection algorithm (SGPA) that is similar to the Gerchberg-Saxton phase retrieval algorithm. The second is a parallel generalized projection algorithm (PGPA) that introduces constraints that minimize the number of branch points in the control commands for the deformable mirrors. These approaches are compared with the approach of placing the second deformable mirror conjugate to the far field of the collecting aperture and using the Gerchberg-Saxton algorithm to determine the optimal mirror commands. Simulation results show that placing the second deformable mirror at a finite range can achieve near-unity Strehl ratio regardless of the strength of the scintillation induced by propagation through extended paths, while the maximum Strehl ratio of the far-field approach drops off with increasing scintillation. The feasibility of the solutions is evaluated by counting the branch points contained in the deformable mirror commands. There are large numbers of branch points contained in the control commands that are generated by the Gerchberg-Saxton SGPA-based algorithms, irrespective of where the second deformable mirror is located. However, the control commands generated by the PGPA with branch point constraints achieves excellent Strehl ratio and minimizes the number of branch points.

Journal Article↗