International Journal of High Speed Computing

We compare standard parallel algorithms for solving linear parabolic partial differential equations. The comparison is based on the combined effect of their numerical properties and their parallel performance. We discuss the classical explicit methods (forward Euler, Heun and DuFort-Frankel), the standard implicit methods (BDF₁, BDF₂ and Crank-Nicolson), the line Hopscotch technique and the ADI formula of McKee and Mitchell. Timing results obtained on a 16-processor Intel hypercube are given. It is shown that parallelism does not alter the ranking of the methods unless the number of grid points per processor is very small.

In this paper, we discuss the performance prediction of Fortran constructs commonly found in numerical scientific computing. Although the approach appears applicable to multi-processors in general, within the scope of the paper we will concentrate on the Alliant FX/8 multiprocessor. The techniques proposed involve a combination of empirical observations, architectural models and analytical techniques, and exploit earlier work on data locality analysis and empirical characterization of memory system behavior. The Lawrence Livermore Loops are used as a test-case to verify the approach. Our results indicate that a prediction approach developed for a target architecture following the strategy proposed can successfully predict the performance of numerical codes.

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.

Superscalar processors can execute multiple scalar instructions in parallel. Conventional statically scheduled superscalar processors have drawbacks when it comes to dynamic variations in instruction latency. In this paper a very simple synchronization method is described for a statically scheduled superscalar processor consisting of multiple functional units each processing its own instruction stream. This superscalar processor has not only a conventional program counter which is indispensable for the von Neumann execution model but also token counters which express the differences of instructions executed. The simulation results indicate that the superscalar processor with the proposed synchronization shows 33-42% speed up compared with a static VLIW processor and 4-13% speed up compared with a dynamic VLIW processor on the condition that there are dynamic variations in instruction latency.