This paper introduces a new network topology, called Multi-Mesh (MM), which uses multiple meshes as the basic building blocks interconnected in a suitable manner. The proposed network consists of n/sup 4/ processors and is 4-regular with a diameter of 2n. The network also contains a Hamiltonian cycle. Simple routing algorithms for point-to-point communication, one-to-all broadcast, and multicast have been described for this network. It is shown that a simple n/sup 2//spl times/n/sup 2/ mesh can also be emulated on this network in O(1) time. Several application examples have been discussed for which this network is found to be more efficient with regard to computational time than the corresponding mesh with the same number of processors. As examples, O(n) time algorithms for finding the sum, average, minimum, and maximum of n/sup 4/ data values, located at n/sup 4/ different processors have been discussed. Time-efficient implementations of algorithms for solving nontrivial problems, e.g., Lagrange's interpolation, matrix transposition, matrix multiplication, and Discrete Fourier Transform (DFT) computation have also been discussed. The time complexity of Lagrange's interpolation on this network is O(n) for n/sup 2/ data points compared to O(n/sup 2/) time on mesh of the same size. Matrix transpose requires O(n/sup 0.5/) time for an n/spl times/n. matrix. The time for multiplying two n/spl times/n matrices is O(n/sup 0.6/) with an AT-cost of O(n/sup 3/). DFT of n sample points can be computed in O(n/sup 0.6/) time on this network. The previous papers show that n/sup 4/ data elements can be sorted on this network in O(n) time.

An efficient complete exchange algorithm is presented for a multi mesh network having N (=n/sup 4/) processors (n=2/sup k/), with wormhole routing as the method of message passing between two communicating processors. The proposed algorithm effectively uses the cycles of length n and 2n respectively, present in the multi mesh topology. The total time required for complete exchange is O(mN/sup 5/4/logN), where m is the message length (assumed to be the same for all the messages).

The shear-sort algorithm on an SIMD mesh model requires 4/spl radic/N+o(/spl radic/N) time for sorting N elements arranged on a /spl radic/N/spl times//spl radic/N mesh. In this paper, we present an algorithm for sorting N elements in time O(N/sup 1/4/) on an SIMD multi-mesh architecture, thereby significantly improving the order of the time complexity. The multi-mesh architecture is built around n/sup 2/ blocks, where each block is an n/spl times/n mesh with n=N/sup 1/4/, so that each processor will uniformly have four neighbors in the final topology.

A generalized model for faults in multivalued I/sup 2/L circuits has been proposed. Using this model, the test sets have been generated for testing the basic modules of a parallel multiplier using multivalued I/sup 2/L technology. These basic modules include four input balanced ternary full adder and a precarry generator, each of which has multivalued current inputs and outputs. The generated test sets can detect single faults (either 'stuck-at' or 'skew' type) in these circuits.

Presents an algorithm for parallel multiplication of two n-bit ternary numbers. This algorithm uses the technique of column compression and computes the product in (2 upper bound /spl lsqb/log/sub 2/n/spl rsqb/+2) units of addition time of a single-bit ternary full adder. This algorithm requires regular interconnection between any two types of cells and hence is very suitable for VLSI implementation. The same algorithm is also applicable to the multiplication of negative numbers.>