Search

Algebraic Reconstruction Technique (ART) is an age-old method used for solving the problem of three-dimensional (3-D) reconstruction from projections in electron microscopy and radiology. In medical applications, direct 3-D reconstruction is at the forefront of investigation. The simultaneous iterative reconstruction technique (SIRT) is an ART-type algorithm with the potential of generating in a few iterations tomographic images of a quality comparable to that of convolution-backprojection (CBP) methods. Pixel-based reconstruction (PBR) [10] is similar to SIRT reconstruction, and it has been shown that PBR algorithms give better quality pictures compared to those produced by SIRT algorithms. In this work, we propose a few modifications to the PBR algorithms. The modified algorithms are shown to give better quality pictures compared to PBR algorithms. The PBR algorithm and the modified PBR algorithms are highly compute intensive. Not many attempts have been made to reconstruct objects in the true 3-D sense because of the high computational overhead. In this study, we have developed parallel two-dimensional (2-D) and 3-D reconstruction algorithms based on modified PBR. We attempt to solve the two problems encountered by the PBR and modified PBR algorithms, i.e., the long computational time and the large memory requirements, by parallelizing the algorithm on a multiprocessor system. We investigate the possible task and data partitioning schemes by exploiting the potential parallelism in the PBR algorithm subject to minimizing the memory requirement. We have implemented an extended hypercube (EH) architecture for the high-speed execution of the 3-D reconstruction algorithm using the commercially available fast floating point digital signal processor (DSP) chips as the processing elements (PE's) and dual-port random access memories (DPR) as channels between the PE's. We discuss and compare the performances of the PBR algorithm on an IBM 6000 RISC workstation, on a Silicon Graphics Indigo 2 workstation, and on an EH system. The results show that an EH(3,1) using DSP chips as PE's executes the modified PBR algorithm about 100 times faster than an IBM 6000 RISC workstation. We have executed the algorithms on a 4-node IBM SP2 parallel computer. The results show that execution time of the algorithm on an EH(3,1) is better than that of a 4-node IBM SP2 system. The speed-up of an EH(3,1) system with eight PE's and one network controller (NC) is approximately 7.85.

We present through the use of Petri Nets, modeling techniques for digital systems realizable using FPGAs. These Petri Net models are used for logic validation at the logic design phase. The technique is illustrated by modeling practical circuits. Further, the utility of the technique with respect to timing analysis of the modeled digital systems is considered. Key words: Petri Nets, Field Programmable Gate Arrays, Computer-Aided Design, VLSI design, digital system design.

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions. This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption. Index Terms - Search methods, genetic algorithms, fitness moments, adaptive variation of parameters, controlled disruption.

The PET image reconstruction based on the EM algorithm has several attractive advantages over the conventional convolution backprojection algorithms. However, the PET image reconstruction based on the EM algorithm is computationally burdensome for today's single processor systems. In addition, a large memory is required for the storage of the image, projection data, and the probability matrix. Since the computations are easily divided into tasks executable in parallel, multiprocessor configurations are the ideal choice for fast execution of the EM algorithms. In this study, we attempt to overcome these two problems by parallelizing the EM algorithm on a multiprocessor system. The parallel EM algorithm on a linear array topology using the commercially available fast floating point digital signal processor (DSP) chips as the processing elements (PE's) has been implemented. The performance of the EM algorithm on a 386/387 machine, IBM 6000 RISC workstation, and on the linear array system is discussed and compared. The results show that the computational speed performance of a linear array using 8 DSP chips as PE's executing the EM image reconstruction algorithm is about 15.5 times better than that of the IBM 6000 RISC workstation. The novelty of the scheme is its simplicity. The linear array topology is expandable with a larger number of PE's. The architecture is not dependent on the DSP chip chosen, and the substitution of the latest DSP chip is straightforward and could yield better speed performance.

In this paper a pipelined ring algorithm is presented for efficient computation of one and two dimensional Fast Fourier Transform (FFT) on a message passing multiprocessor. The algorithm has been implemented on a transputer based system and experiments reveal that the algorithm is very efficient. A model for analysing the performance of the algorithm is developed from its computation-communication characteristics. Expressions for execution time, speedup and efficiency are obtained and these expressions are validated with experimental results obtained on a four transputer system. The analytical model is then used to estimate the performance of the algorithm for different number of processors, and for different sizes of the input data.

In this paper we describe an efficient approach for multimodal function optimization using Genetic Algorithms (GAs). We recommend the use of adaptive probabilities of crossover and mutation to realize the twin goals of maintaining diversity in the population and sustaining the convergence capacity of the GA. In the Adaptive Genetic Algorithm (AGA), the probabilities of crossover and mutation, p(sub c) and p(sub m), are varied depending on the fitness values of the solutions. High-fitness solutions are 'protected', while solutions with subaverage fitnesses are totally disrupted. By using adaptively varying p(sub c) and p(sub m), we also provide a solution to the problem of deciding the optimal values of p(sub c) and p(sub m), i.e., p(sub c) and p(sub m) need not be specified at all. The AGA is compared with previous approaches for adapting operator probabilities in genetic algorithms. The sShema theorem is derived for the AGA, and the working of the AGA is analyzed. We compare the performance of the AGA with that of the Standard GA (SGA) in optimizing several nontrivial multimodal functions with varying degrees of complexity. For most functions, the AGA converges to the global optimum in far fewer generations than the SGA, and it gets stuck at a local optimum fewer times. Our experiments demonstrate that the relative performance of the AGA as compared to that of the SGA improves as the epistacity and the multimodal nature of the objective function increase. We believe that the AGA is the first step in realizing a class of self organizing GAs capable of adapting themselves in locating the global optimum in a multimodal landscape.

In executing tasks involving intelligent information processing, the human brain performs better than the digital computer. The human brain derives its power from a large number (O(10 to the eleventh power)) of neurons which are interconnected by a dense interconnection network (O(10 to the fifth power)) connections per neuron). Artificial neural network (ANN) paradigms adopt the structure of the brain to try to emulate the intelligent information processing methods of the brain. ANN techniques are being employed to solve problems in areas such as pattern recognition, and robotic processing. Simulation of ANNs involves implementation of large number of neurons and a massive interconnection network. In this paper, we discuss various simulation models of ANNs and their implementation on distributed memory systems. Our investigations reveal that communication-efficient networks of distributed memory systems perform better than other topologies in implementing ANNs.

The Extended Hypercube (EH) is an interconnection network with recursive, hierarchical features that uses a prespecified building block. It contains k-cubes of processor elements with a corresponding network controller per k-cube. It has a lower value for the product (diameter * degree of a node), a cost and performance measure, over the hypercube, hypernet and the pyramid. The ASCEND/DESCEND types of parallel algorithms are found to be easily implementable on the EH.