Parallel Processing Letters

Earlier studies on Simultaneous Multithreaded (SMT) architectures showed that performance of a realistic SMT architecture saturates early. This paper addresses our contention that a fixed hardware thread scheduling strategy cannot provide optimal results for various thread combinations. We propose an approach that partially schedules threads in the form of a detector thread at a nominal hardware and software cost. It offers the capability to adaptively switch thread scheduling policies depending on various situations. This article shows that there is much room for performance improvement for our adaptive dynamic thread scheduling approach. The results we have obtained by simulating a realistic SMT architecture show that no single fetch policy may outperform the rest more than 50% of the total time. We show that 27% is approximately the upper-bound of the performance improvement for SMT with eight contexts. This demonstrates that our approach may significantly improve performance with good low-throughput detection and fetch policy selection heuristics.

In this paper, we introduce the Systolic Reconfigurable Mesh (SRM), which combines aspects of the reconfigurable mesh with that of systolic arrays. Every processor controls a local switch that can be reconfigured during every clock cycle in order to control the physical connections between its four bi-directional bus lines. Data is input on one side of the systolic reconfigurable mesh and output from another side, one row/column per unit time. Efficient algorithms are presented for intermediate-level vision tasks, including histograming, connectivity, convexity, and proximity.

We show nearly work-optimal parallel decoding algorithms which run on the PRAM EREW in O(log n) time with O(n/(log n)^1/2) processors for text compressed with LZ1 and LZ2 methods, where n is the length of the output string. We also present pseudo work-optimal PRAM EREW decoders for finite window compression and LZ2 compression requiring logarithmic time with O(dn) work, where d is the window size and the alphabet size respectively. Finally, we observe that PRAM EREW decoders requiring O(log n) time and O(n/log n) processors are possible with the non-conservative assumption that the computer word length is O(log² n) bits.

We prove that the cutwidth of the n-dimensional shuffle-exchange graph is at most ⌈2ⁿ⁺¹/n⌉, for n≥10. This essentially improves on the previous best constant factors. As a consequence we obtain an improved upper bound for the cutwidth of the de Bruijn graph.

We present an optimal embedding of a honeycomb network (honeycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of when n is a power of two. When n is not a power of two, the expansion is , which we conjecture to be near optimal. For a honeycomb mesh, the dilation of the embedding is 1. For a honeycomb torus, the dilation can be as large as 2⌈log n⌉+3, because of the extra links connecting symmetric opposite nodes of degree two. A honeycomb network, built recursively using hexagon tessellation, is a multiprocessor interconnection network, and also a Cayley graph, and it is better than the planar mesh with the same number of nodes in terms of degree, diameter, number of links, and bisection width.

In [10] the authors proved upper bounds for the arc-congestion and wave-length number of any permutation demand on a bidirected ring. In this note, we give generalizations of their results in two directions. The first one is that instead of considering only permutation demands we consider any balanced demand, and the second one is that instead of the ring network we consider any Hamilton decomposable network.

Thus, we obtain upper bounds (which are best possible in general) for the arc-congestion and wavelength number of any balanced demand on a Hamilton decomposable network. As a special case, we obtain upper bounds on arc- and edge-forwarding indices of Hamilton decomposable networks that are in many cases better than the known ones.

In the state-based self-stabilizing algorithmic paradigm for distributed computing, each node has only a local view of the system (seeing its neighbors' states), yet in a finite amount of time the system converges to a global state satisfying some desired property. In this paper we introduce a general mechanism that allows a node to act only on correct distance-two knowledge, provided there are IDs. We then apply the mechanism to graph problems in the areas of coloring and domination. For example, we obtain an algorithm for maximal 2-packing which is guaranteed to stabilize in polynomial moves under a central daemon.

Recently honeycomb meshes have been considered as alternative candidates for interconnection networks in parallel and distributed computer systems. This paper presents a solution to one of the open problems about honeycomb meshes—the so-called three disjoint path problem. The problem requires minimizing the length of the longest of any three disjoint paths between 3-degree nodes. This solution provides information on the re-routing of traffic along the network in the presence of faults.

In a previous paper we solved an open problem named as the three disjoint path problem on honeycomb meshes. In this paper we extend the technique used to solve the related problem on honeycomb tori. The result gives the minimum possible length of the longest of any three disjoint paths between two given nodes in a torus. The problem has practical benefits in the fault tolerant aspects of interconnection topologies.