Performance Analysis of Reversible Fast Decimal Adders

This paper presents a performance analysis of reversible, fault tolerant VLSI implementations of carry select and hybrid decimal adders suitable for multi-digit BCD addition. The designs enable partial parallel processing of all digits that perform high-speed addition in decimal domain. When the number of digits is more than 25 the hybrid decimal adder can operate 5 times faster than conventional decimal adder using classical logic gates. The speed up factor of hybrid adder increases above 10 when the number of decimal digits is more than 25 for reversible logic implementation. Such highspeed decimal adders find applications in real time processors and internet-based applications. The implementations use only reversible conservative Fredkin gates, which make it suitable for VLSI circuits.

A Novel Fast Hybrid Cryptographic System: MARS4

A novel and fast technique for cryptographic applications is designed and developed using the symmetric key algorithm “MAJE4” and the popular asymmetric key algorithm “RSA”. The MAJE4 algorithm is used for encryption / decryption of files since it is much faster and occupies less memory than RSA. The RSA algorithm is used to solve the problem of key exchange as well as to accomplish scalability and message authentication. The focus is to develop a new hybrid system called MARS4 by combining the two cryptographic methods with an aim to get the advantages of both. The performance evaluation of MARS4 is done in comparison with MAJE4 and RSA.

Fast Fractal Coding Method for the Detection of Microcalcification in Mammograms

The presence of microcalcifications in mammograms can be considered as an early indication of breast cancer. A fastfractal block coding method to model the mammograms fordetecting the presence of microcalcifications is presented in this paper. The conventional fractal image coding method takes enormous amount of time during the fractal block encoding.procedure. In the proposed method, the image is divided intoshade and non shade blocks based on the dynamic range, andonly non shade blocks are encoded using the fractal encodingtechnique. Since the number of image blocks is considerablyreduced in the matching domain search pool, a saving of97.996% of the encoding time is obtained as compared to theconventional fractal coding method, for modeling mammograms.The above developed mammograms are used for detectingmicrocalcifications and a diagnostic efficiency of 85.7% isobtained for the 28 mammograms used.

A New Fast Fractal Modeling Approach for the Detection of Microcalcifications in Mammograms

In this paper, a novel fast method for modeling mammograms by deterministic fractal coding approach to detect the presence of microcalcifications, which are early signs of breast cancer, is presented. The modeled mammogram obtained using fractal encoding method is visually similar to the original image containing microcalcifications, and therefore, when it is taken out from the original mammogram, the presence of microcalcifications can be enhanced. The limitation of fractal image modeling is the tremendous time required for encoding. In the present work, instead of searching for a matching domain in the entire domain pool of the image, three methods based on mean and variance, dynamic range of the image blocks, and mass center features are used. This reduced the encoding time by a factor of 3, 89, and 13, respectively, in the three methods with respect to the conventional fractal image coding method with quad tree partitioning. The mammograms obtained from The Mammographic Image Analysis Society database (ground truth available) gave a total detection score of 87.6%, 87.6%, 90.5%, and 87.6%, for the conventional and the proposed three methods, respectively.

On the localization of electrons and holes in Hg_n and rare-gas clusters

We have used a microscopic theory to study the size dependence of the degree of localization of the valence electrons and holes in neutral an ionized rare-gas and Hg_n clusters. We discuss under which circumstances localization of the electrons and holes is favoured. We have calculated the ionization potential of Xe_n, Kr_n and small Hg_n clusters. Good agreement with experiments is obtained. We have also determined the dependence of the ionization potential on cluster structure.

Estimation of the ground state correlation energy for isoelectronic series of 2 to 20 electrons

Correlation energies for all isoelectronic sequences of 2 to 20 electrons and Z = 2 to 25 are obtained by taking differences between theoretical total energies of Dirac-Fock calculations and experimental total energies. These are pure relativistic correlation energies because relativistic and QED effects are already taken care of. The theoretical as well as the experimental values are analysed critically in order to get values as accurate as possible. The correlation energies obtained show an essentially consistent behaviour from Z = 2 to 17. For Z > 17 inconsistencies occur indicating errors in the experimental values which become very large for Z > 25.

Fast computation of concept lattices using data mining techniques

We present a new algorithm called TITANIC for computing concept lattices. It is based on data mining techniques for computing frequent itemsets. The algorithm is experimentally evaluated and compared with B. Ganter's Next-Closure algorithm.

Analyse selbsterregter Strömungsfelder im Verdichter-Leitrad durch Kopplung von Particle Image Velocimetry und Hitzdrahtanemometrie mittels Fast Fourier Transformation

Der Einsatz der Particle Image Velocimetry (PIV) zur Analyse selbsterregter Strömungsphänomene und das dafür notwendige Auswerteverfahren werden in dieser Arbeit beschrieben. Zur Untersuchung von solchen Mechanismen, die in Turbo-Verdichtern als Rotierende Instabilitäten in Erscheinung treten, wird auf Datensätze zurückgegriffen, die anhand experimenteller Untersuchungen an einem ringförmigen Verdichter-Leitrad gewonnen wurden. Die Rotierenden Instabilitäten sind zeitabhängige Strömungsphänomene, die bei hohen aerodynamischen Belastungen in Verdichtergittern auftreten können. Aufgrund der fehlenden Phaseninformation kann diese instationäre Strömung mit konventionellen PIV-Systemen nicht erfasst werden. Die Kármánsche Wirbelstraße und Rotierende Instabilitäten stellen beide selbsterregte Strömungsvorgänge dar. Die Ähnlichkeit wird genutzt um die Funktionalität des Verfahrens anhand der Kármánschen Wirbelstraße nachzuweisen. Der mittels PIV zu visualisierende Wirbeltransport erfordert ein besonderes Verfahren, da ein externes Signal zur Festlegung des Phasenwinkels dieser selbsterregten Strömung nicht zur Verfügung steht. Die Methodik basiert auf der Kopplung der PIV-Technik mit der Hitzdrahtanemometrie. Die gleichzeitige Messung mittels einer zeitlich hochaufgelösten Hitzdraht-Messung ermöglicht den Zeitpunkten der PIV-Bilder einen Phasenwinkel zuzuordnen. Hierzu wird das Hitzdrahtsignal mit einem FFT-Verfahren analysiert, um die PIV-Bilder entsprechend ihrer Phasenwinkel zu gruppieren. Dafür werden die aufgenommenen Bilder auf der Zeitachse der Hitzdrahtmessungen markiert. Eine systematische Analyse des Hitzdrahtsignals in der Umgebung der PIV-Messung liefert Daten zur Festlegung der Grundfrequenz und erlaubt es, der markierten PIV-Position einen Phasenwinkel zuzuordnen. Die sich aus den PIV-Bildern einer Klasse ergebenden Geschwindigkeitskomponenten werden anschließend gemittelt. Aus den resultierenden Bildern jeder Klasse ergibt sich das zweidimensionale zeitabhängige Geschwindigkeitsfeld, in dem die Wirbelwanderung der Kármánschen Wirbelstraße ersichtlich wird. In hierauf aufbauenden Untersuchungen werden Zeitsignale aus Messungen in einem Verdichterringgitter analysiert. Dabei zeigt sich, dass zusätzlich Filterfunktionen erforderlich sind. Im Ergebnis wird schließlich deutlich, dass die Übertragung der anhand der Kármánschen Wirbelstraße entwickelten Methode nur teilweise gelingt und weitere Forschungsarbeiten erforderlich sind.

ADAM: A Decentralized Parallel Computer Architecture Featuring Fast Thread and Data Migration and a Uniform Hardware Abstraction

The furious pace of Moore's Law is driving computer architecture into a realm where the the speed of light is the dominant factor in system latencies. The number of clock cycles to span a chip are increasing, while the number of bits that can be accessed within a clock cycle is decreasing. Hence, it is becoming more difficult to hide latency. One alternative solution is to reduce latency by migrating threads and data, but the overhead of existing implementations has previously made migration an unserviceable solution so far. I present an architecture, implementation, and mechanisms that reduces the overhead of migration to the point where migration is a viable supplement to other latency hiding mechanisms, such as multithreading. The architecture is abstract, and presents programmers with a simple, uniform fine-grained multithreaded parallel programming model with implicit memory management. In other words, the spatial nature and implementation details (such as the number of processors) of a parallel machine are entirely hidden from the programmer. Compiler writers are encouraged to devise programming languages for the machine that guide a programmer to express their ideas in terms of objects, since objects exhibit an inherent physical locality of data and code. The machine implementation can then leverage this locality to automatically distribute data and threads across the physical machine by using a set of high performance migration mechanisms. An implementation of this architecture could migrate a null thread in 66 cycles -- over a factor of 1000 improvement over previous work. Performance also scales well; the time required to move a typical thread is only 4 to 5 times that of a null thread. Data migration performance is similar, and scales linearly with data block size. Since the performance of the migration mechanism is on par with that of an L2 cache, the implementation simulated in my work has no data caches and relies instead on multithreading and the migration mechanism to hide and reduce access latencies.

Compact Representations for Fast Nonrigid Registration of Medical Images

We develop efficient techniques for the non-rigid registration of medical images by using representations that adapt to the anatomy found in such images. Images of anatomical structures typically have uniform intensity interiors and smooth boundaries. We create methods to represent such regions compactly using tetrahedra. Unlike voxel-based representations, tetrahedra can accurately describe the expected smooth surfaces of medical objects. Furthermore, the interior of such objects can be represented using a small number of tetrahedra. Rather than describing a medical object using tens of thousands of voxels, our representations generally contain only a few thousand elements. Tetrahedra facilitate the creation of efficient non-rigid registration algorithms based on finite element methods (FEM). We create a fast, FEM-based method to non-rigidly register segmented anatomical structures from two subjects. Using our compact tetrahedral representations, this method generally requires less than one minute of processing time on a desktop PC. We also create a novel method for the non-rigid registration of gray scale images. To facilitate a fast method, we create a tetrahedral representation of a displacement field that automatically adapts to both the anatomy in an image and to the displacement field. The resulting algorithm has a computational cost that is dominated by the number of nodes in the mesh (about 10,000), rather than the number of voxels in an image (nearly 10,000,000). For many non-rigid registration problems, we can find a transformation from one image to another in five minutes. This speed is important as it allows use of the algorithm during surgery. We apply our algorithms to find correlations between the shape of anatomical structures and the presence of schizophrenia. We show that a study based on our representations outperforms studies based on other representations. We also use the results of our non-rigid registration algorithm as the basis of a segmentation algorithm. That algorithm also outperforms other methods in our tests, producing smoother segmentations and more accurately reproducing manual segmentations.

Fast Learning by Bounding Likelihoods in Sigmoid Type Belief Networks

Sigmoid type belief networks, a class of probabilistic neural networks, provide a natural framework for compactly representing probabilistic information in a variety of unsupervised and supervised learning problems. Often the parameters used in these networks need to be learned from examples. Unfortunately, estimating the parameters via exact probabilistic calculations (i.e, the EM-algorithm) is intractable even for networks with fairly small numbers of hidden units. We propose to avoid the infeasibility of the E step by bounding likelihoods instead of computing them exactly. We introduce extended and complementary representations for these networks and show that the estimation of the network parameters can be made fast (reduced to quadratic optimization) by performing the estimation in either of the alternative domains. The complementary networks can be used for continuous density estimation as well.

Fast Object Recognition in Noisy Images Using Simulated Annealing

A fast simulated annealing algorithm is developed for automatic object recognition. The normalized correlation coefficient is used as a measure of the match between a hypothesized object and an image. Templates are generated on-line during the search by transforming model images. Simulated annealing reduces the search time by orders of magnitude with respect to an exhaustive search. The algorithm is applied to the problem of how landmarks, for example, traffic signs, can be recognized by an autonomous vehicle or a navigating robot. The algorithm works well in noisy, real-world images of complicated scenes for model images with high information content.

Fast Sorting on a Distributed-Memory Architecture

We consider the often-studied problem of sorting, for a parallel computer. Given an input array distributed evenly over p processors, the task is to compute the sorted output array, also distributed over the p processors. Many existing algorithms take the approach of approximately load-balancing the output, leaving each processor with Θ(n/p) elements. However, in many cases, approximate load-balancing leads to inefficiencies in both the sorting itself and in further uses of the data after sorting. We provide a deterministic parallel sorting algorithm that uses parallel selection to produce any output distribution exactly, particularly one that is perfectly load-balanced. Furthermore, when using a comparison sort, this algorithm is 1-optimal in both computation and communication. We provide an empirical study that illustrates the efficiency of exact data splitting, and shows an improvement over two sample sort algorithms.

FastAero – A Precorrected FFT – Fast Multipole Tree Steady and Unsteady Potential Flow Solver

In this paper a precorrected FFT-Fast Multipole Tree (pFFT-FMT) method for solving the potential flow around arbitrary three dimensional bodies is presented. The method takes advantage of the efficiency of the pFFT and FMT algorithms to facilitate more demanding computations such as automatic wake generation and hands-off steady and unsteady aerodynamic simulations. The velocity potential on the body surfaces and in the domain is determined using a pFFT Boundary Element Method (BEM) approach based on the Green’s Theorem Boundary Integral Equation. The vorticity trailing all lifting surfaces in the domain is represented using a Fast Multipole Tree, time advected, vortex participle method. Some simple steady state flow solutions are performed to demonstrate the basic capabilities of the solver. Although this paper focuses primarily on steady state solutions, it should be noted that this approach is designed to be a robust and efficient unsteady potential flow simulation tool, useful for rapid computational prototyping.