In circuit-switched routing, the path between a source and its destination is established by incrementally reserving all required links before the data transmission can begin. If the routing algorithm is not carefully designed, deadlocks can occur in reserving these links. Deadlock-free algorithms based on dimension-ordered routing, such as the E-cube , exist. However, E-cube does not provide any flexibility in choosing a path from a source to its destination and can thus result in long latencies under heavy or uneven traffic. Adaptive, minimum-distance routing algorithms, such as the Turn Model and the UP Preference algorithms, have previously been reported. In this article, we present a new class of adaptive, provably deadlock-free, minimum-distance routing algorithms. We prove that the algorithms developed here are optimally adaptive in the sense that any further flexibility in communication will result in deadlock. We show that the Turn Model is actually a member of our new class of algorithms that does not perform as well as other algorithms within the new class. It creates artificial hotspots in routing the traffic and allows fewer total paths. We present an analytical comparison of the flexibility and balance in routing provided by various algorithms and a comparison based on uniform and nonuniform traffic simulations. The Extended UP Preference algorithm developed in this article is shown to have improved performance with respect to existing algorithms. The methodology and the algorithms developed here can be used to develop routing for other schemes such as wormhole routing, and for other recursively defined networks such as k -ary n -cubes.

Sparse matrix solution (SOLVE) is a dominant part of the total execution time in a circuit simulation program such as SPICE. For simulation of modern VLSI circuit designs, it is important that this time be reduced. This paper presents a block partitionable sparse matrix solution algorithm in which a matrix is divided into equal size blocks, and blocks are assigned to different processors for parallel execution. The algorithm developed in this work exploits sparsity at the block level as well as within a non-zero block. An efficient mapping scheme to assign matrix blocks to processors is developed which maximizes concurrency and minimizes communication between processors. Associated reordering and efficient sparse storage schemes are also developed. An implementation of this parallel algorithm is carried out on a Transputer processor array which plugs into a PC bus. The sparse matrix solver is tested on matrices generated from a transistor-level expansion of ISCAS-85 benchmark logic circuits. Good speedup is obtained for all benchmark matrices up to the number of Transputers available.