7218297
Improving effective bandwidth of networks on clusters using load balancing for communication-intensive applications
Clusters have emerged as a primary and cost-effective infrastructure for parallel applications, including communication-intensive applications that transfer a large amount of data among nodes of a cluster via interconnection networks. Conventional load balancers have been proven effective in increasing utilization of CPU, memory, and disk I/O resources in a cluster. However, most of the existing load-balancing schemes ignore network resources, leaving open an opportunity for improving effective bandwidth of networks on clusters running parallel applications. For this reason, we propose a communication-aware load balancing technique that is capable of improving performance of communication-intensive applications by increasing effective utilization of networks in cluster environments. Our load-balancing scheme can make use of an application model to quickly and accurately determine the load induced by a variety of parallel applications. Simulation results on executing a wide range of parallel applications on a cluster show that the proposed scheme can significantly improve the performance in slowdown and turn-around time over three existing schemes by up to 206% (with an average of 74%) and 235% (with an average of 82%), respectively.
26735928
I/O Response Time in a Fault-Tolerant Parallel Virtual File System
A fault tolerant parallel virtual file system is designed and implemented to provide high I/O performance and high reliability. A queuing model is used to analyze in detail the average response time when multiple clients access the system. The results show that I/O response time is with a function of several operational parameters. It decreases with the increase in I/O buffer hit rate for read requests, write buffer size for write requests and number of server nodes in the parallel file system, while higher I/O requests arrival rate increases I/O response time.
16880603
Adaptive Load Balancing for Long-Range MD Simulations in A Distributed Environment
Molecular dynamics, a computationally intensive application is used by researchers in various fields. The inherent parallelism (Plimpton and Hendrickson, 1994) in the computations involved with this application can be exploited in parallel and distributed environments. However, in distributed environments such as the grid (Foster et al., 2001), the available resources, namely the network and computational power, are continually changing with respect to every available node. To optimally utilize these dynamic resources, a scheduler should be able to continually adapt to the changes and suitably vary the load scheduled to every available node. We propose one such scheduling algorithm. The proposed scheduling algorithm builds and continually updates a model of the distributed system, which it then uses to make decisions about how to optimally redistribute the load in the system at every time step of the MD simulation. The scheduling algorithm can additionally handle dynamic changes in the number of nodes available for computation at runtime. We then demonstrate the efficiency of our scheduling algorithm when applied to MD simulations in a distributed environment
9864742
JOPI: a Java object-passing interface
Recently there has been an increasing interest in developing parallel programming capabilities in Java to harness the vast resources available in clusters, grids and heterogeneous networked systems. In this paper, we introduce a Java object-passing interface (JOPI) library. JOPI provides Java programmers with the necessary functionality to write object-passing parallel programs in distributed heterogeneous systems. JOPI provides an MPI-like interface that can be used to exchange objects among processes. In addition to the well-known benefits of the object-oriented development model, using objects to exchange information in JOPI is advantageous because it facilitates passing complex structures and enables the programmer to isolate the problem space from the parallelization problem. The run-time environment for JOPI is portable, efficient and provides the necessary functionality to deploy and execute parallel Java programs. Experiments were conducted on a cluster system and a collection of heterogeneous platforms to measure JOPI's performance and compare it with MPI. The results show good performance gains using JOPI.
1546029
Design and Analysis of Hierarchical Ring Networks for Shared-Memory Multiprocessors
ÐWe study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add ashortcuto edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRN's) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the acutwidtho of an express ring translating into the atree deptho of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-2dÿ 1 multiring. 3) Every depth-d multiring M can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of M resides at a corner of the mesh. 4) Every depth-d HRN H can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of H resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRNs that are asymptotically tight for large N and d. Index TermsÐRing networks, chordal rings, express rings, multirings, hierarchical ring networks, grid graphs, graph embedding, diameter trade-offs.
8918525
An efficient, low-cost inconsistency detection framework for data and service sharing in an Internet-scale system
In this paper, we argue that a broad range of Internet-scale distributed applications can benefit from an underlying low-cost consistency detection framework that is an alternative to inconsistency avoidance and can detect inconsistency among nodes sharing data or services in a timely manner. This paper first presents an overview of the inconsistency detection framework. Then, it discusses the detailed design of the two-layer inconsistency detection module, the core component of this framework, which can detect inconsistency among nodes in a timely manner. The proposed two-layer inconsistency detection module is evaluated both analytically and via simulations, which shows that this module can significantly reduce the time to detect inconsistency among nodes without adding much maintenance cost. Finally, this paper outlines the possible mechanisms to discern the application semantics and to resolve the detected inconsistencies
18051966
Design and analysis of adaptive strategies for locating internet-based servers in MANETs
A critical problem in providing Internet access to Mobile Ad Hoc Networks (MANETs) is how the mobile hosts can locate Internet-based servers efficiently in a dynamic, unstructured network. This paper studies adaptive strategies that combine both proactive advertising by the servers and on-demand discovery by the mobile hosts. The adaptive strategies determine the relative rate of proactive advertising and on-demand discovery according to system characteristics such as host mobility level and offered load. Our simulation study reveals that, compared to the previous proactive strategies and reactive strategies, the adaptive strategies reduce network traffic by several times when the network has a moderate offered load and a low or high level of host mobility.
22543009
Self-stabilizing Population Protocols
Self-stabilization in a model of anonymous, asynchronous interacting agents deployed in a network of unknown size is considered. Dijkstra-style round-robin token circulation can be done deterministically with constant space per node in this model. Constant-space protocols are given for leader election in rings, local-addressing in degree-bounded graphs, and establishing consistent global direction in an undirected ring. A protocol to construct a spanning tree in regular graphs using O(logD) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.
16906364
Scalable and Robust Aggregation Techniques for Extracting Statistical Information in Sensor Networks
Wireless sensor networks have stringent constraints on system resources and data aggregation techniques are critically important. However, accurate data aggregation is difficult due to the variation of sensor readings and due to the frequent communication failures. To address these difficulties, we propose a scalable and robust data aggregation algorithm. The novelty of our work includes two aspects. First, our algorithm exploits the mixture model and the Expectation Maximization (EM) algorithm for parameter estimation. Hence, it captures the effects of aggregation over different scales while keeping the communication cost low. Second, our algorithm exploits loss-tolerant multi-path routing schemes. Hence, it obtains accurate statistical information even in the presence of high link and node failure rates. We demonstrate that our techniques reduce communication cost while retaining the precious statistical information otherwise neglected by other aggregation techniques. Our evaluation shows the proposed techniques are robust against link and node failures, and perform consistently well.
19285635
Global Optimization of Lennard-Jones Clusters by a Parallel Fast Annealing Evolutionary Algorithm
A parallel fast annealing evolutionary algorithm (PFAEA) was presented and applied to optimize Lennard-Jones (LJ) clusters. All the lowest known minima up to LJ(116) with both icosahedral and nonicosahedral structure, including the truncated octahedron of LJ(38), central fcc tetrahedron of LJ(98), the Marks' decahedron of LJ(75)(-)(77), and LJ(102)(-)(104), were located successfully by the unbiased algorithm. PFAEA is a parallel version of fast annealing evolutionary algorithm (FAEA) that combines the aspect of population in genetic algorithm and annealing algorithm with a very fast annealing schedule. A master-slave paradigm is used to parallelize FAEA to improve the efficiency. The performance of PFAEA is studied, and the scaling of execution time with the cluster size is approximately cubic, which is important for larger scale energy minimization systems.
18487363
Confidence measures for speech recognition: A survey
Abstract In speech recognition, confidence measures (CM) are used to evaluate reliability of recognition results. A good confidence measure can largely benefit speech recognition systems in many practical applications. In this survey, I summarize most research works related to confidence measures which have been done during the past 10–12 years. I will present all these approaches as three major categories, namely CM as a combination of predictor features, CM as a posterior probability, and CM as utterance verification. Then, I also introduce some recent advances in the area. Moreover, I will discuss capabilities and limitations of the current CM techniques and generally comment on today’s CM approaches. Based on the discussion, I will conclude the paper with some clues for future works.