Parallel Processing Letters

Dimension-adaptive sparse grid interpolation is a powerful tool to obtain surrogate functions of smooth, medium to high-dimensional objective models. In case of expensive models, the efficiency of the sparse grid algorithm is governed by the time required for the function evaluations. In this paper, we first briefly analyze the inherent parallelism of the standard dimension-adaptive algorithm. Then, we present an enhanced version of the standard algorithm that permits, in each step of the algorithm, a specified number (equal to the number of desired processes) of function evaluations to be executed in parallel, thereby increasing the parallel efficiency.

This paper presents fault-tolerant simulations of a single-writer multi-reader regular register in storage systems. One simulation tolerates fail-stop failures of storage servers and requires a majority of nonfaulty servers, while the other simulation tolerates Byzantine failures and assumes that two-thirds of the servers are nonfaulty. A construction of Afek et al. [3] is used to mask semi-Byzantine failures of clients that result in erroneous write operations. The simulations are used to derive Paxos algorithms that tolerate semi-Byzantine failures of clients as well as fail-stop or Byzantine failures of storage servers.

Wang and Sahni [4] reported two parallel algorithms for N-point prefix computation on an N-processor OTIS-Mesh optoelectronic computer. The overall time complexity for both SIMS and MIMD models of their first algorithm was shown to be (8 N^1/4 - 1) electronic moves and 2 OTIS moves. This was further reduced to (7 N^1/4 - 1) electronic moves and 2 OTIS moves in their second algorithm. We present here an improved parallel algorithm for N-point prefix computation on an N-processor OTIS-Mesh, which needs (5.5 N^1/4 + 3) electronic moves and 2 OTIS moves. Our algorithm is based on the general theme of parallel prefix algorithm proposed in [4] but following the data distribution and local prefix computation similar to that of [1].

This paper proposes waiting ratio as a basis in evaluating various scheduling methods for dynamic workloads consisting of multi-processor jobs on parallel computers. We evaluate commonly used methods as well as several methods proposed in this paper by simulation studies. The results indicate that some commonly used methods do not improve the waiting ratios as expected by intuition, while some methods proposed in this paper do greatly improve waiting ratios more than 10 times for some workload data, promising in leading to more reasonable waiting time and better user's satisfaction.

This paper presents our experience in parallelizing a Monte Carlo/fluid hybrid simulation of radio frequency glow discharge in plasma physics. The application is a dynamic loosely-synchronous system with time-increasing workload. We adopt adaptive processor allocation to effectively parallelize the time-increasing workload. The results show that adaptive processor allocation has potential to improve performance of parallel applications with time-varying workloads. The methods proposed in this paper can be applied to other dynamic loosely-synchronous applications as well.

The asynchronous group mutual exclusion (GME) problem [5] is a generalization of the (ordinary) mutual exclusion problem. Each process requests a forum. When a process is in the critical section (CS), we say its forum is held. The GME problem (i) allows at most one forum to be held at any time and, (ii) when a forum is held, encourages any number of processes requesting that forum to participate in that forum, that is, to be in the CS simultaneously. An extension of this problem, called the group mutual l-exclusion with multiple forum requests (GMLE-M) problem [8], allows each process to request multiple forums and up to l forums to be held simultaneously. In this paper, we give a simple GMLE-M algorithm that facilitates a highly concurrent participation of processes in forums. The algorithm uses a new technique, called automatic joining, that enables processes to enter the CS directly when their forums are being held. This technique can be used in other extensions of the GME problem also, to increase concurrency.

Grid computing integrates heterogeneous, geographically distributed, Internet-ready resources that are administered under multiple domains. A key challenge in grid computing is to provide a high quality of service to users in a transparent fashion, hiding issues that include ownership, administration, and geographic location of a wide variety of resources that provide compute cycles, data storage, rendering cycles, imaging devices, and sensors, to name a few. Ensuring the functionality of a wide variety of resources under multiple administrative policies requires tools for discovering, repairing, and publishing information on the services offered by individual sites within a given grid. In this paper, we present the ACDC Operations Dashboard, an interactive, collaborative environment for collecting, addressing, and publishing operational service information for resources across a computational grid.

Email and short message service are pervasive on the Internet now and continue to grow rapidly, which propels the research on small file access in storage systems. The Clustering technology places logical data blocks of multiple small files on physically contiguous disk blocks and accesses them as a single unit, which is normally adopted to improve small file access performance. This paper constructs a mathematical analysis model to discover the optimal clustering size of small file access in Network Attached Storage (NAS). The analysis results indicate that the optimal clustering size for small file access is the product of one cylinder size and disk number in NAS. Experimental results give a useful validation of our analysis. The analysis results can be applied to optimize the NAS oriented system software and the corresponding application software design.