International Journal of High Speed Computing

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.

The i860™ is a high performance microprocessor used in the Intel Touchstone project. This paper proposes a paradigm for programming the i860™ that is modelled on the vector instructions of the Cray computers. A collection of Fortran callable assembler subroutines (Naspack routines) were written that mimic the concurrent vector instructions of the Cray with cache taking the place of vector registers. Using the Naspack subroutines on an adisolve, we obtained a speedup of 3.9 for a 128 by 128 system over compiled code.

The combinatorial optimization problem of assigning parallel tasks onto a multiprocessor so as to minimize the execution time is termed as the mapping problem. This problem even in its simplest form is known to be NP-hard. Several heuristic solutions that have been proposed seek to obtain a 'good' sub-optimal mapping in a reasonable time. In this paper we present two randomized heuristics for the mapping problem one of which is based on Plaisted's randomized graph separator heuristic while the other is based on the principles of genetic algorithms. We empirically compare the performance of our algorithms with two other such existing randomized mapping algorithms. One of them is the recursive min-cut partitioning heuristic due to Sadayappan et al., while the other is a simple genetic algorithm for mapping of our earlier work.

This comparison of relative performance of the four randomized algorithms indicates that the genetic class of algorithms always produces better mappings than algorithms of the clustering class. In addition it is found that the recursive separator mapping algorithm performs as good as the recursive clustering algorithm while our new variant of genetic algorithm performs no better than our simple genetic algorithm.

In this paper we study the problem of schedule upper bound of a set of different types and partially ordered instructions with a maximal pipeline delay of z cycles, where z is an arbitrary integer, on k types of pipelined processors (or functional units). The goal of this scheduling is to minimize execution time for these instructions. This problem is NP-hard, so we analyze the worst case of any greedy schedule, since the optimal schedule of this problem can always be transformed into a greedy form. Let w_g and w₀ be the completion times of an arbitrary greedy schedule and the optimal schedule, respectively. With each type containing m_i processors, for 1 ≤ i ≤ k, we establish a bound that w_g/w₀ ≤ (k + 1 − 1/(z + 1)* max{m_i}) and show also that this bound is best possible.

In this paper, we propose a parallel computational model, called (Parallel Resolution and Reduction with RAP), and its abstract machine for a functional logic language whose main execution is based on both of the resolution and lazy reduction. Since the parallel reductions of the function arguments can be regarded as a parallel evaluation of independent subgoals, only Independent-And Parallelism is exploited in in order to simplify the execution control of Lazy Aflog program. is an extension of DeGroot's RAP model [5] equipped with the mechanisms to support parallel function reductions.

A parallel abstract machine for based on the RAP-WAM [6] is also developed, which is an extension of sequential abstract machine FWAM-II equipped with the run-time structures and the primitive instructions to spawn the parallel tasks and gather the results. Simulation results show that both of the parallel resolution and parallel lazy reduction can be efficiently supported in the and its abstract machine simultaneously.

Since the general problem of optimal multiprocessor scheduling is NP-Hard, a lot of research effort has focused on developing heuristic methods. Simple and low cost heuristic algorithms that produce fairly good schedules are of interest for practical reasons. In this work, we give an extensive analysis of the existing Heavy Node First(HNF) algorithm, and propose an improved version called Multi-level Heavy Node First (MHNF) algorithm. We also initiate a new approach in worst case evaluation of various heuristics, with which we compare HNF with MHNF. We find that the improved MHNF enjoys the low cost of HNF but better quality of average case scheduling.