Narrow Results

Today, high-performance computing is recognized as a necessity in various industries. The stable and secure connection between system components, such as CPUs and memories, requires efficient, reliable, and fault-tolerant networks. Multistage Interconnection Networks (MIN) are fundamental approaches to create such an interconnection facility among researchers and engineers. Meanwhile, the Gamma Interconnection Network (GIN) provides one of the highest levels of fault tolerance networks among MINs by establishing multiple paths. Considering the importance of disjoint paths, 4-Disjoint GIN (4DGIN) has been developed, which is an important type of GIN and provides four disjoint paths for all source–destination pairs. On the other hand, the replication approach improves network fault tolerance, which directly affects network reliability. In this paper, a replicated 4DGIN is proposed, enhancing the reliability and improving the fault-tolerance factor by creating disjoint and redundant paths. The reliability of the proposed network is evaluated using the Reliability Block Diagram (RBD) approach. The reliability evaluation results show that the proposed network outperforms several well-known MINs, such as different variations of SEN and Benes networks in terms of the terminal, broadcast, and network reliability factors. Moreover, it improves the cost per unit factor in comparison with the baselines.

The discretization of separable elliptic partial differential equations leads to linear systems with special block tridiagonal matrices. Several methods are known to solve these systems, the most general of which is the Block Cyclic Reduction (BCR) algorithm which handles equations with nonconstant coefficients. A method was recently proposed to parallelize and vectorize BCR. In this paper we discuss the mapping of BCR on distributed memory architectures and compare its complexity with that of other approaches including the Alternating-Direction method. We also describe a fast parallel solver, based on an explicit formula for the solution, which has parallel computational complexity lower than that of parallel BCR.

In this paper, we report the recent progress in parallel processing research in Japan.

The Fast Fourier Transform is a mainstay of certain numerical techniques for solving fluid dynamics problems. The Connection Machine CM-2 is the target for an investigation into the design of multidimensional SIMD parallel FFT algorithms for high performance. Critical algorithm design issues are discussed, necessary machine performance measurements are identified and made, and the performance of the developed FFT programs are measured. Our FFT programs are compared to the currently best Cray-2 FFT library program, CFFT2.

Two implementations of the molecular dynamics method on the Connection Machine are given demonstrating the advantage of using NEWS communication over the general router. Timing comparisons are also made with the Cray 2.

Circuit simulation is a highly compute-intensive task as it involves solving thousands of ordinary differential equations (ODEs) describing the VLSI circuit under consideration. This paper describes an effort towards speeding up this task using a hypercube-based architecture. The paper focusses on the design and development of HIRECS (Hypercube Implementation of RElaxation-Based Circuit Simulation). HIRECS is based on the relaxation approach of solving the ODEs describing the circuit. The natural decomposition of the problem makes the relaxation algorithms amenable to parallel implementation. HIRECS employs the Waveform Relaxation (WR) algorithm. The special feature of WR algorithm is that the latency of the circuit can be exploited better, effecting a saving in the total computation time. The concept of ’windowing’ has been incorporated in HIRECS to effect a saving in the memory requirement. Another important feature of HIRECS is a novel synchronization scheme called partial synchronization. HIRECS runs on a DEC-1090 system and is developed using SIMULA. Performance studies of HIRECS based on parameters such as speedup, efficiency, and utilization of processors have been carried out. The performance evaluation of HIRECS in the simulation of some bench mark circuits like inverter chains and multiplexers indicates that a significant speedup, almost linear, can be obtained using a hypercube. For circuits with large number of nodes, such an implementation can result in tremendous saving in the computation time.

The difficulties in conceptualizing the interactions among a large number of processors make it difficult both to identify the sources of inefficiencies and to determine how a parallel program could be made more efficient. This paper describes an instrumentation system that can trace the execution of distributed memory parallel programs by recording the occurrence of parallel program events. The resulting event traces can be used to compile summary statistics that provide a global view of program performance. In addition, visualization tools permit the graphic display of event traces. Visual presentation of performance data is particularly useful, indeed, necessary for large-scale parallel computers; the enormous volume of performance data mandates visual display.

The paper reviews existing methods for generating discrete random variables and their suitability for vector processing. A new method for generating discrete random variables for use in vectorized Monte Carlo simulations is presented. The method uses the concept of importance sampling and generates random variables by employing uniform distribution to speed up the computation. The sampled random variables are subsequently adjusted so that unbiased estimates are obtained. The method preserves both the mean and variance of the original distribution. It is demonstrated that the method requires simpler coding and shorter execution time for both scalar and vector processing, when compared with other existing methods. The vectorization speedup of the method is demonstrated on an IBM 3090–180 machine with a vector facility.

The importance of circuit simulation in the design of VLSI circuits has channelised research work in the direction of finding methods to speedup this highly compute-intensive problem. On one hand, attempts have been made to find better algorithms and use faster hardware; and on the other hand, to use parallel architectures for accelerating the circuit simulation task. In this paper, we examine the various issues involved in parallelizing two well-known circuit simulation approaches – direct methods and relaxation methods. A number of parallel computer architectures which have been used for this purpose are also surveyed.

In this paper we present a new parallel Iterative Deepening A* (IDA*) algorithm, the imprecise IDA* algorithm, for combinatorial optimization. This algorithm employs inadmissible heuristics. But approximate solutions which are arbitrarily close to the optimal ones can be obtained. In addition a linear speedup can be achieved by our algorithm. Experimental study has been carried out and the results are also reported here. Two computationally difficult problems, the quadratic assignment and the generalized assignment, are used in our experimental study. Our algorithm is effective for these problems of reasonable size.

The i860™ microprocessor is a powerful pipelined processor that is being used in the Touchstone project to develop a teraflop computer by the year 2000. It was expected that memory bandwidth would limit performance on certain kernels used with sparse matrices. Measured performances of three kernels were less than what memory bandwidth limitations would predict. This paper develops a model that explains the discrepancy in terms of memory latencies.

Operational numerical weather prediction requires that all available main-frame computing power be harnessed to the one task, in order to maintain operational schedules. ECMWF therefore became involved in parallel processing as soon as it became available on supercomputers. The main operational programs were restructured to use multitasking on a limited number of processors, currently 8.

The availability of supercomputers with massively parallel architecture which is expected in the near future raises quite a number of major problems. These areas have been discussed in the biennial workshops held at ECMWF since 1984. Besides the user environment, the inter-dependency of hardware architecture and algorithms needs most attention. To study these questions, ECMWF became involved in the GENESIS project sponsored by the European Community. Initial results of this co-operation in the form of benchmark results will be presented.

The challenges posed by new developments in weather prediction strategies will be highlighted and an assessment of the impact parallel computing will have on their being met will be made.

In this paper, a heuristic mapping approach which maps parallel programs, described by precedence graphs, to MIMD architectures, described by system graphs, is presented. The complete execution time of a parallel program is used as a measure, and the concept of critical edges is utilized as the heuristic to guide the search for a better initial assignment and subsequent refinement. An important feature is the use of a termination condition of the refinement process. This is based on deriving a lower bound on the total execution time of the mapped program. When this has been reached, no further refinement steps are necessary. The algorithms have been implemented and applied to the mapping of random problem graphs to various system topologies, including hypercubes, meshes, and random graphs. The results show reductions in execution times of the mapped programs of up to 77 percent over random mapping.

LINDA is a system for programming parallel computers. Although it was originally designed for shared memory machines, versions for distributed memory systems and machines connected over a network are also available. LINDA programs that run well over the network will run well without change on a shared memory system.

This report discusses some features of LINDA as implemented for networked IBM RS/6000s. Measurements of network performance running across both Ethernet and the Serial Link Adapter fiber optic channel are presented. A parallelization of the Linpack 100 algorithm applied to a problem of order 1000 is described. Some details of how we have configured our system at the Palo Alto Scientific Center that others might find useful are also included.

This paper proposes a simple and efficient parallelizing scheme of the genetic algorithm on distributed-memory multiprocessor that maintains the execution behaviours of sequential genetic algorithm. In this parallelizing scheme, the global population is evenly partitioned into several subpopulations, each of which is assigned to the processor to be evolved in parallel. An interprocessor communication pattern, called AAB (All-To-All Broadcasting), is used at each generation in order to exchange the informations on all individuals evolved in all other processors. It allows the processor to reproduce the individuals in a global sense, in other words, the sequential execution behaviours can be maintained in the parallelized genetic algorithm. This paper shows that the genetic algorithms employing widely used selection schemes such as proportionate selection, ranking selection and tournament selection can be efficiently parallelized on distributed-memory multiprocessor using the proposed parallelizing scheme. Some experimental speedups on AP1000 are also presented to show the usefulness of the proposed parallelizing scheme.

Parallel programs may be represented as a set of interrelated sequential tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an appropriate allocation of processors to the tasks of the application. Given a parallel application defined by a task precedence graph, the goal of task scheduling (or processor assignment) is thus the minimization of the makespan of the application. In a heterogeneous multiprocessor system, task scheduling consists of determining which tasks will be assigned to each processor, as well as the execution order of the tasks assigned to each processor. In this work, we apply the tabu search metaheuristic to the solution of the task scheduling problem on a heterogeneous multiprocessor environment under precedence constraints. The topology of the Mean Value Analysis solution package for product form queueing networks is used as the framework for performance evaluation. We show that tabu search obtains much better results, i.e., shorter completion times, improving from 20 to 30% the makespan obtained by the most appropriate algorithm previously published in the literature.

Analysis of skewed memory schemes for parallel implementation of Kohonen’s topological feature maps are presented in this paper. It is found that linear skewing is more general and more effective for this problem as compared with other memory skewing schemes. Implementations on parallel machines and performance results will also be presented.

Informatics and Scientific Computing approach parallel processing in a different way. We briefly describe the different points of view of both camps. Next we concentrate on a case study in the area of scientific computing. The problem chosen is from Physical Chemistry (self-consistent field computation). We describe the problem, the sequential solution, the parallelization strategy and present the performance values we have achieved. Our implementation is based on a 60-node transputer system, available at the Parallel Processing Laboratory in Basel.

In numerical computations, the method of divided differences is a very important technique for polynomial approximations. Consider a pipelined divided–difference computation for approximating an nth degree polynomial. This paper first presents a method to transform the computational structure of divided differences into the pyramid tree with nodes. Based on graph embedding technique, without any extra communication delay, the pipelined divided–difference computation can be performed in a (2k + 1)-dimensional fault–free hypercube for n + 1 = 2^k + t, k > 0, and 0 < t < 2^k; the pipelined divided-difference computation can be further performed in a (2k + 2)-dimensional faulty hypercube to tolerate arbitrary (k - 1) faulty nodes/links. To the best of our knowledge, this is the first time such mapping methods are being proposed in the literature.

This paper discusses the parallel implementation of the solution of a set of linear equations using the Alternative Quadrant Interlocking Factorisation Methods (AQIF), on a star topology. Both the AQIF and LU decomposition methods are mapped onto star topology on an IBM SP2 system, with MPI as the internode communicator. Performance parameters such as speedup, efficiency have been obtained through experimental and theoretical means. The studies demonstrate (i) a mismatch of 15% between the theoretical and experimental results, (ii) scalability of the AQIF algorithm, and (iii) faster executing AQIF algorithm.