Parallel Processing Letters

We show that the problem of finding the element with the highest frequency in a set, the mode of the set, is bounded by the problem of sorting multisets. As a consequence, we obtained an improvement of the upper bound for finding the mode. This result was obtained by presenting an algorithm that requires linear time when the set is initially sorted. The same algorithm was parallelized to produce the first optimal parallel algorithm for finding the mode.

A system of simultaneously triggered clocks is designed to be stabilizing: if the clock values ever differ, the system is guaranteed to converge to a state where all clock values are identical, and are subsequently maintained to be identical. For an N-clock system, the design uses N registers of 2logN bits each and guarantees convergence to identical values within N² "triggers".

In this paper, we derive array processors which are synthesized from uniform but non-local DAGs. We introduce limited broadcast facilities that can be adjusted to cope with current integration constraints. Our target problem is the Algebraic Path Problem, whose implementation on systolic architectures has been studied by numerous authors. We show how to compare, to classify and to improve several proposed architectures.

Quite recently it has been proved that a two-dimensional processor array with a reconfigurable bus system (PARBS, for short) is at least as powerful as the CRCW shared memory computer. In this note we argue that the well-known PARITY problem can be solved in O(1) time on a two-dimensional PARBS of (n+1)×n processors. Since it is known that PARITY cannot be solved in constant time on a CRCW even if a polynomial number of processors is available, our result shows that the two-dimensional PARBS is strictly more powerful than the CRCW.

A t-spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. This guarantees that if nodes u and v are at distance d(u,v) in the original network, they are at distance no more than t·d(u,v) in the t-spanner. We introduce a more general definition of spanners. A special case of this more general definition is the additive t-spanner: a subnetwork in which every two nodes u and v that were separated by distance d(u,v) in the original network are at distance no more than t+d(u,v) in the subnetwork. We construct low-degree additive t-spanners for hypercubes.

The Folded Hypercube (FHC) has been proven to be an attractive hypercube-based network. This paper closely compares the FHC to its standard hypercube counterpart from the subcube allocation viewpoint. It is shown that the FHC(n) outperforms the n-dimensional hypercube (n-cube for short) in offering subcubes of size k by a factor of . In an environment where subcubes of the original network must be allocated to incoming tasks, the FHC achieves an excellent processor utilization by assigning subcubes in an efficient and compact manner. Using the concept of virtual hypercubes, an efficient way is suggested to recognize the available subcubes in the FHC by adapting the already developed subcube recognition algorithms. An alternative approach to the subcube recognition problem is also given.

In this paper, we propose a parallel algorithm for the traffic control problem (an NP-complete problem) on crossbar switch networks. This problem is to find a set of conflict-free paths such that the maximum number of message packets can be transmitted over the network. The problem can be represented by an energy function. Then by applying our parallel algorithm, the state of the energy function is iteratively updated toward a stable state. When the energy function reaches a stable state, the state represents a solution of the problem. The empirical results show that the throughputs of the proposed algorithm are much better than the linear algorithm. We have shown that the time complexity of a parallel algorithm is O(n) by using n² processors. Furthermore, since the traffic control problem can be reduced to the traveling salesman problem, the proposed algorithm can be further applied to some other NP-complete problems.

This letter presents the modelling of a morphological thinning algorithm suggested by Jang and Chin [1] on the four models of shared memory SIMD computers. The time and cost complexity analyses for the models have been given. The performance of this algorithm on SIMD computers has been compared with the performance of a conventional thinning algorithm [2] proposed recently.

We show how to off-line route any permutation of an n×n mesh-connected processor array in 2.5n steps with at most two packets per processor per time step and in 2.25n+3 steps with at most four packets per processor per time step.