Narrow Results

Generalized cubes are a subclass of hypercube-like networks that are employed by a number of parallel algorithms. Linear array is common topology of multicomputer system. So congestion is very useful to improve algorithm performance for implementing generalized cube communication pattern on linear array. This paper addresses the congestion of generalized cube communication patterns embedding into linear array topology. For this purpose, the maximum m-induced subgraph of generalized cube is determined firstly, which is very important for discussing the congestion. Then an embedding scheme is described, and the congestion is shown to attain the minimum, which guarantees the optimality of the proposed scheme.

The exchanged crossed cube, denoted by $ECQ(s,t)$, is a novel interconnection network with fewer edges and smaller diameter compared to other variations of the corresponding hypercube. The linear array, denoted by $L_n$, is one of the most popular topologies in optical networks. This paper addresses the routing and wavelength assignment for realizing $ECQ(s,t)$ communication pattern on wavelength division multiplexing (WDM) optical network $L_n$, where $n=s+t+1$. We prove that the congestion for $ECQ(s,t)$ on $L_n$ is equal to $2^{s+t-1}+\lfloor 2^t/3\rfloor$, which is the lower bound of the minimum number of required wavelengths. In addition, an embedding scheme and an optimal wavelength assignment algorithm that achieve this bound are also proposed.

A parenthesis string is a string of left and right parentheses. The string is well-formed when it consists of balanced pairs of left and right parentheses. This study presents a novel systolic algorithm for generating all the well-formed parenthesis strings in lexicographical order. The algorithm is cost-optimal and is run on a linear array of processors such that each well-formed parenthesis string can be generated in three time steps. The processor array is appropriate for VLSI implementation, since it has the features of modularity, regularity, and local connection.

In this paper, a joint direction of arrival (DOA) and frequency estimation algorithm of narrow-band signals is proposed via compressed sensing (CS) parallel factor (PARAFAC) framework. The proposed algorithm constructs the data model into a PARAFAC model, and compresses it to a smaller one. Then trilinear alternating least-squares (TALS) algorithm is exploited to estimate the compressed parameter matrices, and finally the joint DOA and frequency estimation is obtained via the spatial sparsity and the frequency sparsity. Due to compression, the proposed algorithm has lower computational complexity than the conventional PARAFAC algorithm, and saves more memory capacity for practical application. The DOA and frequency estimation performance of the proposed algorithm is very close to that of the conventional PARAFAC algorithm, and better than those of the estimation of signal parameters via rotational invariance techniques (ESPRIT) algorithm and the propagator method (PM). Furthermore, the proposed algorithm can achieve automatically paired DOA and frequency estimation. Besides, it is applicable for nonuniform linear arrays. Effectiveness of the proposed algorithm is assessed by simulations.