International Journal of High Speed Computing

For real-time communication, we must be able to guarantee timely delivery of messages. In a previous paper, Kim et al. presented a real-time communication method for networks which uses a deterministic wormhole routing algorithm. It would be more desirable to be able to use an adaptive wormhole routing algorithm. However, the use of an adaptive algorithm results in highly unpredictable communication delays because the path used by each message cannot be known in advance. Thus, an alternative is to use a flexible wormhole routing algorithm, in which one of a set of predefined paths is chosen (in advance) for each pair of communicating nodes. With flexible routing, real-time communication guarantees are again possible while making more effective use of the available network resources than deterministic routing. This paper examines the problem of selecting a set of paths to maximize the probability of meeting real-time communication guarantees for a set of communicating nodes. Since this problem is NP-hard, a heuristic solution is proposed and compared with previous path selection algorithms. Simulation results are used to show that the proposed path selection algorithm outperforms all previous algorithms.

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.

The BGHC is a generalized hypercube that has exactly w nodes along each of the d dimensions for a total of w^d nodes. A BGHC is said to be maximal if the w nodes along each dimension form a complete directed graph. A BGHC is said to be minimal if the w nodes along each dimension form a unidirectional ring. Lower bound complexities are derived for three intensive communication patterns assuming the balanced generalized hypercube (BGHC) topology. A maximal N node BGHC with a node degree equal to αlog₂N, where α≥2, can process certain intensive communication patterns α(α-1) times faster than an N node binary hypercube (which has a node degree equal to log₂N). On the other hand, a minimal N node BGHC with a node degree equal to , where β≥2, is 2^β times slower at processing certain intensive communication patterns than an N node binary hypercube. For certain communication patterns, increasing one unit cost gains a normalized speedup to the binary hypercube by wlog₂w times for the maximal BGHC. For the minimal BGHC, reducing one unit cost gains times speedup normalized to the binary hypercube.

In this paper three communication algorithms are proposed for two types of generalized hypercube multiprocessor. The algorithms are intended to solve three intensive communication problems: complete broadcast, single-node scatter and total exchange. The algorithms achieve both the time and transmission complexity bounds for the three problems on the balanced generalized hypercube (BGHC). The BGHC is a w^d-node network with w nodes along each of the d dimensions. These communication algorithms are performed based on a balanced spanning tree, called a compatible tree, which can be used to solve any of the tree problems. Several theoretical results related to the compatible tree and then the sufficient and necessary condition for concurrent transmissions are presented. The concurrent condition ensures the maximum use of network bandwidth so that the optimal bounds are achieved. It is shown that the proposed scheduling algorithms achieve the optimal bounds for any w and d.

Functional-level simulators have become an indispensable tool in designing today's processors. They help to exploit the design space and evaluate various design options so as to derive a suitable processor microarchitecture. Although Intel's x86 series processors are the most popular CPU in the computers, there are only a few simulation tools available for studying these processors. This paper introduces such a simulation tool. Internally it simulates a decoupled decode/encode architecture and has a RISC core. It is trace-driven and thus has a tracing system, a trace sampling system, and a processor simulator. We will describe the internal workings of the simulation tool and demonstrate how it can be used in evaluating a specific x86-compatible processor.