International Journal of High Speed Computing

Through simulation, we studied the performance of three adaptive “wormhole” routing strategies, and compared them with static routing. Since adaptive routing is susceptible to deadlock, an abort-and-retry strategy was used to prevent it from arising. The impact of packetization of long messages and buffering at message destinations were also studied. Results are presented and analyzed for a variety of hardware configurations and traffic conditions. The combination of adaptive routing, abort-and-retry, and buffering at the destination is shown to achieve excellent performance for modest cost.

In recent years, multiprocessor systems have been developed to exploit parallelism within individual programs. However, a multiprocessor system may be used more efficiently if its processors are partitioned among independent parallel programs. The partitioning of a multiprocessor system is addressed in this paper.

A simple yet powerful model is proposed for the analysis of various partitioning schemes. The model parameterizes both a multiprocessor system and its parallel workload. Attention is restricted to a multiprocessor system partitioned between two parallel programs. The model is studied to determine (1) when partitioning is worthwhile, (2) the extent of performance improvement under optimal partitioning, and (3) which of three partition scheduling schemes is best.

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.

In parallel computing systems, a crucial factor that can limit parallelism is the distribution of operands, which usually are vectors, matrices or higher dimensional arrays, among parallel memory modules. In this paper, we introduce a method of assignment of high dimensional arrays, which include vectors and matrices as special cases, to parallel memory modules of parallel computing systems. Our analysis shows that the method achieves maximum parallelism for a very high percentage of array operations. We have derived the exact conditions under which optimality is achieved. Also provided are the worst and average case bounds on array operation performance.

The routing problem of VLSI layout design is very compute intensive. Consequently, the routing task often turns out to be a bottleneck in the layout design of large circuits. Parallel processing of the routing problem holds promise for mitigating this situation. In this context, we present a parallel channel routing algorithm that is targetted to run on loosely coupled computers like hypercubes. The proposed parallel algorithm employs the simulated annealing technique for obtaining near- optimum solutions. Initially, the number of tracks in the channel is made equal to the number of nets, and partitions of the channel are appropriately assigned to the nodes of the hypercube. Each node carries out concurrent perturbations to obtain new channel states that satisfy the constraints for a given net list. The algorithm minimizes the number of tracks iteratively by using the simulated annealing technique. For efficient execution, we attempt to reduce the communication overheads by restricting the broadcast updates to cases of interprocessor net transfers only. Performance evaluation studies of the algorithm show promising results.

It has been already demonstrated that cost-effective multiprocessor designs may be obtained by combining in the same architecture processors of different speeds (heterogeneous architecture) so that the serial and critical portions of the application may benefit from a fast single processor. In such an environment, the problem of assigning tasks to processors becomes a very important one. This papers presents a systematic way to build static heuristic scheduling algorithms. Using this strategy, several algorithms are proposed and their performance are compared through simulation. One of the proposed algorithms is shown to achieve substantial performance gains as the degree of heterogeneity of the architecture increases.

The primary goal of processor scheduling is to assign tasks in a parallel program to processors, so as to minimize the execution time. Most existing approaches to processor scheduling for multiprocessors assume that the execution time of each task is fixed and is independent of processor scheduling. In this paper, we argue that the execution time of a given task is not fixed but is critically dependent on the performance of the caches, which have become an essential component of shared-memory multiprocessors and propose a scheduling algorithm, called data distribution constrained scheduling algorithm. The proposed scheduling algorithm tries to maximize the number of cache hits by scheduling the processors so that the task that brings a memory block into the cache and the tasks that subsequently access the same memory block are executed on the same processor.

In this paper, we describe a way of obtaining a domain decomposition method for efficiently solving the linear system which arises from the discretization of symmetric elliptic problems using the finite difference approximation. The resulting linear system is solved iteratively by using the conjugate gradient method together with the capacitance matrix method. The algorithm is designed to be implemented on a parallel computer and to reach high parallelization rates together with nearly optimal speed-ups, i.e., close to the number of processors.