Unstructured tree search on SIMD parallel computers

We present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on an SIMD machine consists of two major components: a triggering mechanism, which determines when the search space redistribution must occur to balance the search space over processors, and a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms and verify the results experimentally. The analysis and experiments show that our new load-balancing methods are highly scalable on SIMD architectures. Their scalability is shown to he no worse than that of the best load-balancing schemes on MIMD architectures. We verify our theoretical results by implementing the 15-puzzle problem on a CM-2 SIMD parallel computer     

Parallel architecture for fast transforms with trigonometric kernel

We present an unified parallel architecture for four of the most important fast orthogonal transforms with trigonometric kernel: Complex Valued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cosine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be transformed on a constant geometry flow using perfect unshuffle or shuffle permutations. The other three require some type of hardware modification to guarantee the constant geometry of the successive doubling method. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section permits the evaluation of the CFFT and FCT transforms in n data recirculations and the RFFT and FHT transforms in n-1 data recirculations, with n being the number of stages of a transform of length N=rⁿ. Also, the efficiency of the partitioned parallel architecture is optimum because there is no cycle loss in the systolic computation of all the butterflies for each of the four transforms     

The classification, fusion, and parallelization of array languageprimitives

We present a classification scheme for array language primitives that quantifies the variation in parallelism and data locality that results from the fusion of any two primitives. We also present an algorithm based on this scheme that efficiently determines when it is beneficial to fuse any two primitives. Experimental results show that five LINPACK routines report 50% performance improvement from the fusion of array operators     

Quantization effects in digitally behaving circuit implementationsof Kohonen networks

Implementing a neural network on a digital or mixed analog and digital chip yields the quantization of the synaptic weights dynamics. This paper addresses this topic in the case of Kohonen's self-organizing maps. We first study qualitatively how the quantization affects the convergence and the properties, and deduce from this analysis the way to choose the parameters of the network (adaptation gain and neighborhood). We show that a spatially decreasing neighborhood function is far more preferable than the usually rectangular neighborhood function, because of the weight quantization. Based on these results, an analog nonlinear network, integrated in a standard CMOS technology, and implementing this spatially decreasing neighborhood function is then presented. It can be used in a mixed analog and digital circuit implementation.     

A closer look at mutation in genetic algorithms

This paper examines the influence of mutation on the behavior of genetic algorithms through a series of examples and experiments. The results provide an existence proof that mutation is a far more profound operator than has ever been recognized. Implications are discussed which point to the importance of open questions concerning genetic algorithms. The paper also reviews the implementation of the infinite population model of Vose which forms the computational basis of this investigation.     

Bounded disorder file organization

The bounded disorder file organization proposed by W. Litwin and D.B. Lomet (1987) uses a combination of hashing and tree indexing. Lomet provided an approximate analysis with the mention of the difficulty involved in exact modeling of data nodes, which motivated this work. In an earlier paper (M.V. Ramakrishna and P. Mukhopadhyay, 1988) we provided an exact model and analysis of the data nodes, which is based on the solution of a classical sequential occupancy problem. After summarizing the analysis of data nodes, an alternate file growth method based on repeated trials using universal hashing is proposed and analyzed. We conclude that the alternate file growth method provides simplicity and significant improvement in storage utilization     

Machine independent AND and OR parallel execution of logicprograms. I. The binding environment

We describe a binding environment for the AND and OR parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by J. Conery. However, unlike Conery's scheme, it supports OR and independent AND parallelism on both types of machines. The term representation, the algorithms for unification and the join algorithms for parallel AND branches are presented in this paper. We also detail the differences between our scheme and Conery's scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel     

Structuring fault-tolerant object systems for modularity in adistributed environment

The object-oriented approach to system structuring has found widespread acceptance among designers and developers of robust computing systems. The authors propose a system structure for distributed programming systems that support persistent objects and describe how properties such as persistence and recoverability can be implemented. The proposed structure is modular, permitting easy exploitation of any distributed computing facilities provided by the underlying system. An existing system constructed according to the principles espoused here is examined to illustrate the practical utility of the proposed approach to system structuring     

E-kernel: an embedding kernel on the IBM victor V256 multiprocessorfor program mapping and network reconfiguration

We present the design of E-kernel, an embedding kernel on the Victor V256 message-passing partitionable multiprocessor, developed for the support of program mapping and network reconfiguration. E-kernel supports the embedding of a new network topology onto Victor's 2D mesh and also the embedding of a task graph onto the 2D mesh network or the reconfigured network. In the current implementation, the reconfigured network can be a line or an even-size ring, and the task graphs meshes or tori of a variety of dimensions and shapes or graphs with similar topologies. For application programs having these task graph topologies and that are designed according to the communication model of E-kernel, they can be run without any change on partitions connected by the 2D mesh, line, or ring. Further, E-kernel attempts the communication optimization of these programs on the different networks automatically, thus making both the network topology and the communication optimization attempt completely transparent to the application programs. Many of the embeddings used in E-kernel are optimal or asymptotically optimal (with respect to minimum dilation cost). The implementation of E-kernel translated some of the many theoretical results in graph embeddings into practical tools for program mapping and network reconfiguration in a parallel system. E-kernel is functional on Victor V256. Measurements of E-kernel's performance on V256 are also included     

Genetic evolution of the topology and weight distribution of neuralnetworks

This paper proposes a system based on a parallel genetic algorithm with enhanced encoding and operational abilities. The system, used to evolve feedforward artificial neural networks, has been applied to two widely different problem areas: Boolean function learning and robot control. It is shown that the good results obtained in both cases are due to two factors: first, the enhanced exploration abilities provided by the search-space reducing evolution of both coding granularity and network topology, and, second, the enhanced exploitational abilities due to a recently proposed cooperative local optimizing genetic operator.