International Journal of High Speed Computing

Given the coordinates of N points in D dimensions, the Barnes-Hut tree algorithm produces an ordered list so that successive pairs in the sequence are nearest neighbors, sets of four form a cluster, sets of eight form a bigger cluster, and so on. We describe a parallel implementation of this algorithm on the IBM SP2 using Fortran 77 and MPI message-passing calls, and study its performance.

In this paper, we present the design and implementation of a source-to-source High Performance Fortran assistant Tool (HPFT) in DEC 3000 workstations. For a given sequential program written in Fortran 77, the HPFT generates a vectorized, reuse-exploited and/or parallelized version for vector computers. Several new compilation schemes in vectorization, reuse exploitation and multithreading are designed in the HPFT. A performance evaluator is developed for measuring the system performance. The user interface is also designed for the programmer to capture the information related to the compilation and execution of the program. Experimental results based on the Convex C3840 vector computer show that the developed HPFT enhances the system performance and usually reduces the program execution time.

A distributed computing system (DCS) provides a platform for concurrent execution of tasks consisting of various modules. The problem of task allocation becomes quite difficult to solve when the precedence constraint is considered along with other constraints such as memory, network topology, etc. Various solutions have been proposed, considering one or the other constraint, in the literature. The present work discusses a comprehensive task allocation policy that can promise to provide an optimal solution to the problem. An algorithm, considering the precedence relation among the modules of a task, is proposed for allocation. The algorithm is used to show the allocation for some interconnection topologies and task graphs.

Reciprocal and reciprocal square root operations are partially supported by the i860 floating point unit, whereas square roots are not. We point out the reasons for this, and its consequences for the optimization of code involving many reciprocal square roots, such as many-body simulations involving Coulomb-like potentials. We conclude that code which can be optimized to explicitly combine reciprocals and square roots in the form of reciprocal square roots can attain significantly higher performance, and that assembly language coding of such operations can make the greatest use of the hardware by calculating only to the accuracy required, which may be less than single precision.

The linear quadtree is a useful data structure for representing an image for the sake of the storage saving and further image manipulations. In this paper we propose a linear quadtree coding scheme and implement this algorithm on the parallel virtual machine (PVM). Our goal is to demonstrate the applicability of using the PVM in combining the computing power of computers in a network to solve this kind of image processing problems. The processors in the PVM are organized as a master-slave paradigm and various numbers of processors are applied for different PVM’s to compare their performances. Experimental results show that the speedup of solving this image encoding problem in parallel is quite satisfactory. With such a PVM environment which is easily accessible in the public domain, high performance computing is truly possible without additional hardware cost.

This paper proposes a novel routing algorithm, called the direction-first e-cube, for routing on k-ary n-cube interconnection networks. It is an adaptive, partially minimal algorithm based on the wormhole-routing strategy and effectively extends the basic e-cube technique. It has been proved by a set of theorems that the proposed algorithm is deadlock-, livelock- and starvation-free. In the absence of faults, the algorithm is fully minimal. Even in the presence of faults and network congestion, the number of extra hops required to route a message is minimal. The algorithm is also simple to implement, since it utilizes a small header node of 2 log₂ n+n log₂k+1 bits. Simulation results are given to validate the proposed algorithm.

We formulate a microscopic model of the stock market and study the resulting macroscopic phenomena via simulation. In a market of homogeneous investors periodic booms and crashes in stock price are obtained, When there are two types of investors in the market, differing only in their memory spans, we observe sharp irregular transitions between eras where one population dominates the market and eras where the other population dominates. When the number of investor subgroups is three the market undergoes a dramatic qualitative change — it becomes complex. We show that complexity is an intrinsic property of the stock market. This suggests an alternative to the widely accepted but empirically questionable random walk hypothesis.