Parallel Processing Letters

In optical networks the approach called wavelength division multiplexing allows multiple data streams to be transmitted concurrently along a single optical link, with different streams assigned separate wavelengths. In this paper we refer to all-optical networks, in which each connection is totally optical except at the terminal nodes. For these networks we determine the minimum possible number of links required to perform a fault tolerant broadcast from any node, in terms of the number of nodes, the number of link failures to tolerate and the number of wavelengths to use. We also give lower and upper bounds on the number of wavelengths required for any broadcast which tolerates a given number of link failures on networks with arbitrary topologies.

A product form solution for the optimal fractions of divisible load to distribute to processors in a multi-level tree network is described. Here optimality involves parallel processing the load in a minimal amount of time. This tractable solution is similar to the product form solution for equilibrium state probabilities arising in Markovian queueing networks. The existence of this product form solution answers a long standing open question for divisible load scheduling.

Recently, a secure two-factor user authentication scheme for wireless sensor networks (WSN) was proposed by Das. The proposed scheme can resist many logged in users with the same login identity, stolen-verifier, guessing, impersonation and replay threats. In this paper we study the two-factor user authentication scheme for WSN and find that the scheme is insecure against the masquerade attacks. With our masquerade attacks, an attacker can masquerade as any legal user to login the gateway node without knowing the user's password or can masquerade as a gateway node to communicate with the legal user at anytime.

The reconfigurable architecture is a parallel computation model that consists of many processor elements (PEs) and a reconfigurable bus system. There are many variant proposed reconfigurable architectures, for example, reconfigurable mesh (R-Mesh), directional reconfigurable mesh (DR-Mesh), processor arrays with reconfigurable bus systems (PARBS), complete directional processor arrays with reconfigurable bus systems (CD-PARBS), reconfigurable multiple bus machine (RMBM), directional reconfigurable multiple bus machine (directional RMBM), and etc. In this paper, a transitive closure (TC) algorithm of digraph is proposed on the models without the directional capability (non-directional). Some related digraph problems, such as strongly connected digraph, strongly connected component (SCC), cyclic checking, and tree construction, can also be resolved by modifying our transitive closure algorithm. All the proposed algorithms are designed on a three-dimensional (3-D) n×n×n non-directional reconfigurable mesh, n is the number of vertices in a digraph D, and can resolve the respective problems in O(log d(D)) time, d(D) is the diameter of the digraph D. The cyclic checking problem can be further reduced to O(log c(D)) time, c(D) is the minimum distance of cycles in the digraph D. There exist two different approaches: the matrix multiplication approach on the non-directional models for algebraic path problems (APP) and s-t connectivity approach on the directional models. In this paper, we will use the tree construction algorithm to prove those two approaches are insufficient to resolve all digraph problems and demonstrate why our approach is so important and innovative for digraph problems on the reconfigurable models.

Petascale parallel computers with more than a million processing cores are expected to be available in a couple of years. Although MPI is the dominant programming interface today for large-scale systems that at the highest end already have close to 300,000 processors, a challenging question to both researchers and users is whether MPI will scale to processor and core counts in the millions. In this paper, we examine the issue of scalability of MPI to very large systems. We first examine the MPI specification itself and discuss areas with scalability concerns and how they can be overcome. We then investigate issues that an MPI implementation must address in order to be scalable. To illustrate the issues, we ran a number of simple experiments to measure MPI memory consumption at scale up to 131,072 processes, or 80%, of the IBM Blue Gene/P system at Argonne National Laboratory. Based on the results, we identified nonscalable aspects of the MPI implementation and found ways to tune it to reduce its memory footprint. We also briefly discuss issues in application scalability to large process counts and features of MPI that enable the use of other techniques to alleviate scalability limitations in applications.

We present a surface area lemma to characterize the surface area of a product graph in terms of those of its factors via a generating function approach. We then apply this lemma to derive surface area related results for meshes and tori. Moreover, we also provide explicit formulas for the average distances of these networks.

In this article, we proposed a batch verification scheme for multiple proxy signatures to reduce the proxy signature verification time. The proposed scheme is not only efficient because it does not verify each individual proxy signature separately, but also secure because it can detect forged multiple proxy signatures without failure.

Several studies point out the benefits of a shared L2 cache, but some other properties of shared caches must be considered to lead to a thorough understanding of all chip multiprocessor (CMP) bottlenecks. Our paper evaluates and explains shared cache bottlenecks, which are very important considering the rise of many-core processors. The results of our simulations with 32 cores show low performance when L2 cache memory is shared between 2 or 4 cores. In these two cases, the increase of L2 cache latency and contention are the main causes responsible for the increase of execution time.