Interconnection networks often constrain the performance of multi-cores chips or parallel computers. Cube Connected Cycles (CCC) is an attractive interconnection network because of its symmetry, small constant node degree and a small diameter. This paper develops an algebraic model for the CCC using the direct product of a cyclic group and a finite field. This model allows the use of powerful algebraic techniques to study the structural properties of the network. This paper exploits these techniques to find optimal paths in the CCC and to explore the relationships between the Cube Connected Cycles, the Shuffle Exchange and the deBruijn networks.

This paper obtains all the automorphisms of a wrapped Butterfly network of degree n using an algebraic model. It also investigates the translation of butterfly edges by automorphisms. It proposes a new strategy for algorithm mappings on an architecture with faulty edges. This strategy essentially consists of finding an automorphism that would map the faulty edges to the free edges in the graph. Having a set of n2n+1well defined simple automorphisms which translate graph edges deterministically, makes this a very powerful technique for dealing with edge faults. We illustrate the technique by mapping Hamilton cycle on the butterfly under various edge fault scenarios.

A new algorithm for the modulated complex lapped transform (MCLT) with a sine windowing function is presented. It is shown that by merging the windowing operation with the main computation, both the real and the imaginary parts of the MCLT with 2Ninputs can be obtained from twoN-point discrete cosine transforms of type II (DCTs-II) of appropriate inputs. The resulting algorithm is computationally very efficient. In general, the value ofNis an even number. WhenNis a power of 2, the proposed algorithm uses onlyNlogN+ 2 real multiplications (including the scaling factors in the DCT computation), with none of those being outside the DCT blocks.

We give a new algebraic representation for the wrap-around butterfly interconnection network. This new representation is based on the direct product of groups and finite fields and allows an algebraic expression of the network connectivity. The abstract algebraic tools may then be employed to explore the structural properties of the butterfly. In this paper we exploit this model to map guest graphs on the butterfly. In particular, we provide designs of unit dilation mappings of all possible length cycles on butterflies. We also map the largest possible binary trees on butterfly networks with a dilation 2 if the network degree is less than 16, 3 if it is less than 32, and 4 if it is less than 64. This is a great improvement over previous results.

Parallel recursive computations incorporating the unavoidable and significant parallel computing overheads, encompassing a wide variety of applications, can be modeled as T(n) = left{ {mathop {min }limits_{0 le r le n}^{t_{(),} } } right.left{ {max left{ {T(n - r),T(r) + k(r)} right} + mathop {mathop {lambda (n,r)}limits_{otherwise} }limits^{forn le n_{(),} } } right} where k(r) and X(n,r) represent the partition and recombination overheads respectively. The optimal partition size (solution to r of the above minmax recurrence relation) is nontrivial and is very different from the n/2 value conventionally used. Using the optimal partitions at every stage of the recursion enhances the performance greatly. In this paper we solve a challenging case of our parallel recursive model where the overhead functions are problem-dependent.

There are many parallel signal processing algorithms that are I/O bound. For such algorithms, fast data and program diStribution is very important. In this paper we study a new strategy for data: distribuUonfiom host to MIMD hypercube nodes. This strategy, based on scatteeng on hypercubes of decremental dimensions, perform much better than other strategies known today. It optimizes both the host and node utilization and also exploits the possible overlap in data sent i o different nodes.

An analysis and a simulation of a type of multistage interconnection network, a banyan network based on buffers of various sizes connected at the input link of each node are described. A generalized model for estimating performance indices is developed. It is demonstrated that while buffering produces a considerable improvement in performance, optimum buffer size depends on the average input load. Analytic estimates are substantiated by simulation results.>

An automated path planning algorithm for a mobile robot in a structured environment is presented. An algorithm based on the Quine-McCluskey method of finding prime implicants in a logical expression is used to isolate all the largest rectangular free convex areas in a specified environment. The free convex areas are represented as nodes in a graph, and a graph traversal strategy that dynamically allocates costs to graph paths is used. Complexity of the algorithm and a strategy to trade optimality for smaller computation time are discussed.

This paper deals with an automated path planning algorithm for a mobile robot in a structured enviornment. The algorithm is based upon finding all the largest (prime) free convex areas in the environment and representing this information in the form of a graph. A graph traversal algorithm which exploits back-tracking as well as dynamic cost allocation to graph arcs is presented and simulated. A strategy to trade of the optimality of the results for a smaller computation time is described.

The structure of bilinear cyclic convolution algorithms is explored over finite fields. The algorithms derived are valid for any length not divisible by the field characteristic and are based upon the small length polynomial multiplication algorithms. The multiplicative complexity of these algorithms is small and depends on the field of constants. The linear transformation matricesA, B(premultiplication), andC(postmultiplication) defining the algorithm have block structures which are related to one another. The rows ofAandBand the columns ofCare maximal length recurrent sequences. Because of the highly regular structure ofA, B, andC, the algorithms can be very easily designed even for large lengths. The application of these algorithms to the decoding of Reed-Solomon codes is also examined.

By making an example of the earlier proposed cyclic convolution algorithms, the computational efficiency of the multidimensional techniques over finite fields is investigated. It is shown that the multidimensional techniques are inferior to the directly designed algorithms for all lengths except when applied to lengths whose exponents are relatively prime. Relations between the complexities of the directly designed algorithms and those derived through the multidimensional techniques are also established in various cases.

An alternate algorithm to compute the discrete cosine transform (DCT) of sequences of arbitrary number of points is proposed. The algorithm consists of partitioning the DCT kernel into submatrices which by proper row and column shuffling and negations can be made equivalent to the group tables (or parts of them) of appropriate Abelian groups. The computations pertaining to the submatrices can be carried out using multidimensional cyclic convolutions. Algorithms are also developed to perform the computations associated with the submatrices that are parts of larger group tables. The new algorithms are more versatile and generally better in terms of the computational complexity in comparison with the existing algorithms.

lt is shown that if the Fourier transform over an Abelian groupGof a sequence is zero except over a set of ceset representatives of a subgroupH'\subset G, then the sequence can be easily reconstructed from its values over a subgroupH \subset Grelated toH'.