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 91 records · Page 5Linked to original sources

PubMed2000

A decentralized multichannel length transformation algorithm and its parallel implementation for real-time ECG monitoring.

Multichannel algorithms have been developed for more accurate analysis of electrocardiograms (ECGs). Their benefit is the ability to use the information contained in all simultaneously acquired channels. In this paper we present a multichannel version of a nonsyntactic algorithm, based on length transformation. The proposed algorithm uses a decentralized schema for combining the results derived from each individual lead, instead of a global/centralized one (a spatial vector approach). Its performance was evaluated using the CSE database and real ECGs acquired by a 12-lead cardiograph. The results are also compared with previous-single-channel and multichannel-versions of the algorithm, showing a better performance. Since a multichannel algorithm is always a time-consuming task, it is rarely used in real-time monitoring systems. Motivated by this observation, we designed a parallel implementation of the proposed algorithm and tested its ability to be used in such systems.

Algorithms↗

PubMed1999

Micro flow bio-molecular computation.

In this paper we provide a model for micro-flow based bio-molecular computation (MF-BMC). It provides an abstraction for the design of algorithms which account for the constraints of the model. Our MF-BMC model uses abstractions of both the recombinant DNA (RDNA) technology as well as of the micro-flow technology and takes into account both of their limitations. For example, when considering the efficiency of the recombinant DNA operation of annealing, we take into account the limitation imposed by the concentration of the reactants. The fabrication technology used to construct MEMS is limited to constructing relatively thin 3D structures. We abstract this by limiting the model to a small constant number of layers (as is done with VLSI models). Besides our contribution of the MF-BMC model, the paper contains two other classes of results. The main result is the volume and time efficient algorithm for message routing in the MF-BMC model, specifically useful for PA-Match. We will show that routing of strands between chambers will occur in time O(N x D/ m x n), where N is the number of strands in the MF-BMC, n is the number of chambers where RDNA operations are occurring, D is the diameter of the topology of the layout of the chambers, and m is proportional to the channel width. Operations that need annealing, such as PA-Match, are shown feasible in O(N2logN/n/n) volume instead of the previous use of omega(N2) volume, with reasonable time constraints. Applications of the volume efficient algorithm include the use of the Join operation for databases, logarithmic depth solutions to SAT (Boolean formula satisfiability) problems and parallel algorithms that execute on a PRAM. Existent algorithms can be mapped to ones that work efficiently in the MF-BMC model, whereas previous methods for applications such as PRAM simulation in BMC were not both time and volume efficient. Our other class of results are theoretical lower bounds on the quantities of DNA and the time needed to solve a problem in the MF-BMC model, analogous to lower bounds in VLSI. We bound the product BT from below, and further show that BT2 has a stronger lower bound of I2. Here B is the maximum amount of information encoded in the MF-BMC system at a time. T is the time for an algorithm to complete, and I is the information content of a problem.

Animals↗

PubMed2005

Fast parallel molecular solutions for DNA-based supercomputing: the subset-product problem.

In this paper our main purpose is to give molecular solutions for the subset-product problem. In order to achieve this, we propose three DNA-based algorithms--parallel adder, parallel multiplier and parallel comparator--that formally verify our designed molecular solutions for the subset-product problem. We also show that Boolean circuits are not needed to perform mathematical operations on a molecular computer. Furthermore, this work indicates that the subset-product problem is solved and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.

Algorithms↗

PubMed1990

Parallel computation of multiple biological sequence comparisons.

A parallel implementation of an efficient method for comparison of multiple DNA sequences is presented. The method is described in terms of a conceptual tree data structure for the sequences to be compared. The parallel algorithm shows efficient utilization of processors on an Encore Multimax computer in a sample comparison of 11 sequences totaling over 4000 bases. Timing data show the strong influence of computer system details on this parallel program. Also presented is a graphics program for displaying multiple sequence comparison output data. The display is capable of representing large volumes of multiple sequence comparison data in a single plot. The program has several additional features that allow closer examination of subsets of sequences. A display of matches from the sample comparison reflects the known structure of these sequences.

Algorithms↗

PubMed1999

A parallel noise-robust algorithm to recover depth information from radial flow fields.

A parallel algorithm operating on the units ('neurons') of an artificial retina is proposed to recover depth information in a visual scene from radial flow fields induced by ego motion along a given axis. The system consists of up to 600 radii with fewer than 65 radially arranged neurons on each radius. Neurons are connected only to their nearest neighbors, and they are excited as soon as a sufficiently strong gray-level change occurs. The time difference of two subsequently activated neurons is then used by the last-excited neuron to compute the depth information. All algorithmic calculations remain strictly local, and information is exchanged only between adjacent active neurons (except for the final read-out). This, in principle, permits parallel implementation. Furthermore, it is demonstrated that the calculation of the object coordinates requires only a single multiplication with a constant, which is dependent on only the retinal position of the active neuron. The initial restriction to local operations makes the algorithm very noise sensitive. In order to solve this problem, a predication mechanism is introduced. After an object coordinate has been determined, the active neuron computes the time when the next neuronal excitation should take place. This estimated time is transferred to the respective next neuron, which will wait for this excitation only within a certain time window. If the excitation fails to arrive within this window, the previously computed object coordinate is regarded as noisy and discarded. We will show that this predictive mechanism relies also on only a (second) single multiplication with another neuron-dependent constant. Thus, computational complexity remains low, and noisy depth coordinates are efficiently eliminated. Thus, the algorithm is very fast and operates in real time on 128 x 128 images even in a serial implementation on a relatively slow computer. The algorithm is tested on scenes of growing complexity, and a detailed error analysis is provided showing that the depth error remains very low in most cases. A comparison to standard flow-field analysis shows that our algorithm outperforms the older method by far. The analysis of the algorithm also shows that it is generally applicable despite its restrictions, because it is fast and accurate enough such that a complete depth percept can be composed from radial flow field segments. Finally, we suggest how to generalize the algorithm, waiving the restriction of radial flow.

Algorithms↗

PubMed2004

A hierarchical clustering algorithm for MIMD architecture.

Hierarchical clustering is the most often used method for grouping similar patterns of gene expression data. A fundamental problem with existing implementations of this clustering method is the inability to handle large data sets within a reasonable time and memory resources. We propose a parallelized algorithm of hierarchical clustering to solve this problem. Our implementation on a multiple instruction multiple data (MIMD) architecture shows considerable reduction in computational time and inter-node communication overhead, especially for large data sets. We use the standard message passing library, message passing interface (MPI) for any MIMD systems.

Algorithms↗

PubMed1994

Parallel computing in biomedical research.

Scalable parallel computer architectures provide the computational performance needed for advanced biomedical computing problems. The National Institutes of Health have developed a number of parallel algorithms and techniques useful in determining biological structure and function. These applications include processing electron micrographs to determine the three-dimensional structure of viruses, calculating the solvent-accessible surface area of proteins to help predict the three-dimensional conformation of these molecules from their primary structures, and searching for homologous DNA or amino acid sequences in large biological databases. Timing results demonstrate substantial performance improvements with parallel implementations compared with conventional sequential systems.

Algorithms↗

PubMedDate not supplied

Parallel computing in interval mapping of quantitative trait loci.

Linear regression analysis is considered the least computationally demanding method for mapping quantitative trait loci (QTL). However, simultaneous search for multiple QTL, the use of permutations to obtain empirical significance thresholds, and larger experimental studies significantly increase the computational demand. This report describes an easily implemented parallel algorithm, which significantly reduces the computing time in both QTL mapping and permutation testing. In the example provided, the analysis time was decreased to less than 15% of a single processor system by the use of 18 processors. We indicate how the efficiency of the analysis could be improved by distributing the computations more evenly to the processors and how other ways of distributing the data facilitate the use of more processors. The use of parallel computing in QTL mapping makes it possible to routinely use permutations to obtain empirical significance thresholds for multiple traits and multiple QTL models. It could also be of use to improve the computational efficiency of the more computationally demanding QTL analysis methods.

Algorithms↗

PubMed2004

Efficient generation of discontinuity-preserving adaptive triangulations from range images.

This paper presents an efficient technique for generating adaptive triangular meshes from range images. The algorithm consists of two stages. First, a user-defined number of points is adaptively sampled from the given range image. Those points are chosen by taking into account the surface shapes represented in the range image in such a way that points tend to group in areas of high curvature and to disperse in low-variation regions. This selection process is done through a noniterative, inherently parallel algorithm in order to gain efficiency. Once the image has been subsampled, the second stage applies a two and one half-dimensional Delaunay triangulation to obtain an initial triangular mesh. To favor the preservation of surface and orientation discontinuities (jump and crease edges) present in the original range image, the aforementioned triangular mesh is iteratively modified by applying an efficient edge flipping technique. Results with real range images show accurate triangular approximations of the given range images with low processing times.

Algorithms↗

PubMed2007

Parallel computing of a digital hologram and particle searching for microdigital-holographic particle-tracking velocimetry.

We have developed a parallel algorithm for microdigital-holographic particle-tracking velocimetry. The algorithm is used in (1) numerical reconstruction of a particle image computer using a digital hologram, and (2) searching for particles. The numerical reconstruction from the digital hologram makes use of the Fresnel diffraction equation and the FFT (fast Fourier transform), whereas the particle search algorithm looks for local maximum graduation in a reconstruction field represented by a 3D matrix. To achieve high performance computing for both calculations (reconstruction and particle search), two memory partitions are allocated to the 3D matrix. In this matrix, the reconstruction part consists of horizontally placed 2D memory partitions on the x-y plane for the FFT, whereas, the particle search part consists of vertically placed 2D memory partitions set along the z axes. Consequently, the scalability can be obtained for the proportion of processor elements, where the benchmarks are carried out for parallel computation by a SGI Altix machine.

Journal Article↗

PubMed2003

Mode switching failure during atrial flutter: the '2:1 lock-in' phenomenon.

AIMS: To evaluate incidence and mechanism of a special form of automatic mode switching (MS) failure in patients with atrial flutter. METHODS AND RESULTS: Retrospectively the charts of 134 patients implanted with dual chamber pacemakers with MS algorithms were reviewed. Seven patients (5.2%) were identified that presented with sustained rapid ventricular pacing resulting from atrial flutter with failure of automatic MS. Since this form of MS failure implies 2:1 tracking of atrial flutter, it was coined '2:1 lock-in'. A theoretical timing model was developed to clarify the mechanism of this special form of MS failure. Prerequisites for the '2:1 lock-in' phenomenon are: (1). the sum of the AV delay and the post ventricular blanking (PVAB) must be longer than the cycle length of the atrial flutter, (2). the tachycardia detection rate must be higher than half the atrial flutter rate and (3). the maximum tracking rate (MTR) must be higher than half the atrial flutter rate. Recommendations for programming in order to avoid this specific form of MS failure are made accordingly and parallel algorithms for flutter detection are discussed. CONCLUSION: '2:1 lock-in' is a typical form of MS failure in patients with atrial flutter and the mechanism is closely linked to the typical atrial sensing windows.

Algorithms↗

PubMed2004

Emergence of orientation-selective inhibition in the primary visual cortex: a Bayes-Markov computational model.

The recent consensus is that virtually all aspects of response selectivity exhibited by the primary visual cortex are either created or sharpened by cortical inhibitory interneurons. Experimental studies have shown that there are cortical inhibitory cells that are driven by geniculate cells and that, like their cortical excitatory counterparts, are orientation selective, though less sharply tuned. The main goal of this article is to demonstrate how orientation-selective inhibition might be created by the circuitry of the primary visual cortex (striate cortex, V1) from its nonoriented geniculate inputs. To fulfill this goal, first, a Bayes-Markov computational model is developed for the V1 area dedicated to foveal vision. The developed model consists of three parts: (i) a two-layered hierarchical Markov random field that is assumed to generate the activity patterns of the geniculate and cortical inhibitory cells, (ii) a Bayesian computational goal that is formulated based on the maximum a posteriori (MAP) estimation principle, and (iii) an iterative, deterministic, parallel algorithm that leads the cortical circuitry to achieve its assigned computational goal. The developed model is not fully LGN driven and it is not implementable by the neural machinery of V1. The model, then, is transformed into a fully LGN-driven and physiologically plausible form. Computer simulation is used to demonstrate the performance of the developed models.

Action Potentials↗

PubMed1999

Neuromolecular computing: a new approach to human brain evolution.

Evolutionary approaches in human cognitive neurobiology traditionally emphasize macroscopic structures. It may soon be possible to supplement these studies with models of human information-processing of the molecular level. Thin-film, simulation, fluorescence microscopy, and high-resolution X-ray crystallographic studies provide evidence for transiently organized neural membrane molecular systems with possible computational properties. This review article examines evidence for hydrophobic-mismatch molecular interactions within phospholipid microdomains of a neural membrane bilayer. It is proposed that these interactions are a massively parallel algorithm which can rapidly compute near-optimal solutions to complex cognitive and physiological problems. Coupling of microdomain activity to permenant ion movements at ligand-gated and voltage-gated channels permits the conversion of molecular computations into neuron frequency codes. Evidence for microdomain transport of proteins to specific locations within the bilayer suggests that neuromolecular computation may be under some genetic control and thus modifiable by natural selection. A possible experimental approach for examining evolutionary changes in neuromolecular computation is briefly discussed.

Brain Chemistry↗

PubMed2004

Parallel programming of gradient-based iterative image reconstruction schemes for optical tomography.

Optical tomography (OT) is a fast developing novel imaging modality that uses near-infrared (NIR) light to obtain cross-sectional views of optical properties inside the human body. A major challenge remains the time-consuming, computational-intensive image reconstruction problem that converts NIR transmission measurements into cross-sectional images. To increase the speed of iterative image reconstruction schemes that are commonly applied for OT, we have developed and implemented several parallel algorithms on a cluster of workstations. Static process distribution as well as dynamic load balancing schemes suitable for heterogeneous clusters and varying machine performances are introduced and tested. The resulting algorithms are shown to accelerate the reconstruction process to various degrees, substantially reducing the computation times for clinically relevant problems.

Algorithms↗

PubMed2005

Ab initio integrated multi-center molecular orbitals method for large cluster systems: total energy and normal vibration.

A new computational scheme integrating multi-center ab initio molecular orbitals for determining total energy and normal vibration of large cluster systems is presented. This method can be used to treat large cluster systems such as solvents by quantum mechanics. The geometry parameters, the total energies, the relative energies, and the normal vibrations for four models of water cluster, the hydrated hydronium ion complex, and the transition state of proton transfer are calculated by the present method and are compared with those obtained by the full ab initio MO method. The results agree very well. The scheme proposed in this article is also intended to be used in modeling computer cluster systems using parallel algorithms.

Journal Article↗

PubMed2003

Programmable computing with a single magnetoresistive element.

The development of transistor-based integrated circuits for modern computing is a story of great success. However, the proved concept for enhancing computational power by continuous miniaturization is approaching its fundamental limits. Alternative approaches consider logic elements that are reconfigurable at run-time to overcome the rigid architecture of the present hardware systems. Implementation of parallel algorithms on such 'chameleon' processors has the potential to yield a dramatic increase of computational speed, competitive with that of supercomputers. Owing to their functional flexibility, 'chameleon' processors can be readily optimized with respect to any computer application. In conventional microprocessors, information must be transferred to a memory to prevent it from getting lost, because electrically processed information is volatile. Therefore the computational performance can be improved if the logic gate is additionally capable of storing the output. Here we describe a simple hardware concept for a programmable logic element that is based on a single magnetic random access memory (MRAM) cell. It combines the inherent advantage of a non-volatile output with flexible functionality which can be selected at run-time to operate as an AND, OR, NAND or NOR gate.

Journal Article↗

PubMed2004

Artificial neural networks and image interpretation: a ghost in the machine.

The artificial neural network (ANN) is a non-algorithmic parallel processing device modeled after human cerebral architecture. ANNs can be readily simulated on a digital computer and have the potential for significant diagnostic application in both image- and non-imagebased medical diagnosis. This paper briefly discusses the operation of ANNs, differences between these and more traditional problem solving methods, and some diagnostic imaging problems amenable to their application.

Humans↗

PubMed2006

Higher-order equation-of-motion coupled-cluster methods for ionization processes.

Compact algebraic equations defining the equation-of-motion coupled-cluster (EOM-CC) methods for ionization potentials (IP-EOM-CC) have been derived and computer implemented by virtue of a symbolic algebra system largely automating these processes. Models with connected cluster excitation operators truncated after double, triple, or quadruple level and with linear ionization operators truncated after two-hole-one-particle (2h1p), three-hole-two-particle (3h2p), or four-hole-three-particle (4h3p) level (abbreviated as IP-EOM-CCSD, CCSDT, and CCSDTQ, respectively) have been realized into parallel algorithms taking advantage of spin, spatial, and permutation symmetries with optimal size dependence of the computational costs. They are based on spin-orbital formalisms and can describe both alpha and beta ionizations from open-shell (doublet, triplet, etc.) reference states into ionized states with various spin magnetic quantum numbers. The application of these methods to Koopmans and satellite ionizations of N2 and CO (with the ambiguity due to finite basis sets eliminated by extrapolation) has shown that IP-EOM-CCSD frequently accounts for orbital relaxation inadequately and displays errors exceeding a couple of eV. However, these errors can be systematically reduced to tenths or even hundredths of an eV by IP-EOM-CCSDT or CCSDTQ. Comparison of spectroscopic parameters of the FH+ and NH+ radicals between IP-EOM-CC and experiments has also underscored the importance of higher-order IP-EOM-CC treatments. For instance, the harmonic frequencies of the A 2Sigma- state of NH+ are predicted to be 1285, 1723, and 1705 cm(-1) by IP-EOM-CCSD, CCSDT, and CCSDTQ, respectively, as compared to the observed value of 1707 cm(-1). The small adiabatic energy separation (observed 0.04 eV) between the X 2Pi and a 4Sigma- states of NH+ also requires IP-EOM-CCSDTQ for a quantitative prediction (0.06 eV) when the a 4Sigma- state has the low-spin magnetic quantum number (s(z) = 1/2). When the state with s(z) = 3/2 is sought, the energy separations converge much more rapidly with the IP-EOM-CCSD value (0.03 eV) already being close to the observed (0.04 eV).

Journal Article↗