24528410
Improving the performance of communication-intensive parallel applications executing on clusters
Summary form only given. 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 the interconnection network. Conventional load balancers have been proven effective in increasing the 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 the opportunity for significant performance bottleneck to form for communication-intensive parallel applications due to unevenly distributed communication load. To remedy this problem, we propose a communication-aware load balancing technique that is capable of improving the performance of communication-intensive applications by increasing the effective utilization of network resources in clusters. To facilitate the proposed load-balancing scheme, we introduce a behavior model for parallel applications with large requirements of CPU, memory, network, and disk 170 resources. The proposed load-balancing scheme can make full use of this model to quickly and accurately determine the load induced by a variety of parallel applications. Simulation results on executing a diverse set of both synthetic bulk synchronous and real parallel applications on a cluster show that the proposed scheme can significantly improve the performance both 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.
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
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.
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.
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
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.
9730668
Broadening the Semantic Coverage of Agent Communicative Acts
Communicative acts-based ACLs specify domain-independent information about communication and relegate domain-dependent information to an unspecified content language. This is reasonable, but the ACLs cover only a small fraction of the domain-independent information possible. As a key element of modern ACLs, the set of communicative acts needs to be as complete as possible to allow agents to communicate the widest range of information with agreed-upon semantics. This paper describes a new approach to broaden the semantic coverage of agent communicative acts. It provides agents with the ability to express more of the semantics of human languages and yields a more powerful ACL. We first describe the main meaning categories and semantics for an ACL, which we derive from prior work on speech-act classifications. Next, we prove the resultant semantic coverage. Finally, we present some example applications, which demonstrate that the approach can combine the benefits of the FIPA ACL with Ballmer and Brennenstuhl’s speech act classification, resulting in a more expressive and efficient ACL.
20921565
Dynamical Process of Excitation Fusion in Polymers
Due to the confinement effect in the nondegenerate polymers and the electron-lattice interaction, the electron-hole pair forms a self-trapped single excitation. It is shown that two single excitations in one chain can fuse into one double excitation, and the relaxation time of the fusion process is about 160 fs.
22852167
Parallel Random Tunneling Algorithm for Structural Optimization of Lennard-Jones Clusters up to N = 330
A random tunneling algorithm (RTA) is derived from the terminal repeller unconstrained subenergy tunneling (TRUST) algorithm, and the parallelization of the RTA is implemented with an island parallel paradigm. Combined with the techniques of angular moving, the parallel random tunneling algorithm (PRTA) is applied to the optimization of Lennard-Jones (LJ) atomic clusters, and all the global minima of LJ clusters with size up to 200 are successfully located. For the optimization of larger cluster, a PRTA with an improved seeding technique is developed and successfully applied to the optimization of LJ151-LJ309. Furthermore, the optimized structures of LJ309-330 with the PRTA, which have not been studied before, are also provided.
14525964
Adaptive strategies for efficiently locating internet-based servers in MANETs
Providing Internet access to Mobile Ad hoc Networks (MANETs) can greatly extend their applications, increase their scalability, and improve the quality of service. However, a critical problem is how the mobile hosts can locate Internet-based servers efficiently in a dynamic, unstructured network. Neither reactive strategies, where the hosts initiate on-demand server discovery, nor proactive strategies, where the servers periodically advertise their availability information, are optimal. To that end, this paper studies adaptive strategies that (1) combine both proactive advertising by the servers and on-demand discovery by the mobile hosts, and (2) determine the relative rate of proactive advertising and on-demand discovery adaptively according to the network characteristics including the host mobility level and the offered load. We propose and evaluate two novel, integrated algorithms. First, to determine the rate of proactive advertising, we propose an exponential backoff algorithm to probe the optimal operating point. Second, to reduce the network traffic due to reactive (on-demand) discovery, we propose a novel controlled flooding algorithm. Our simulation study reveals that, compared to the previous proactive strategies and reactive strategies, our adaptive strategies reduce network traffic for locating the servers by several times when the network has a moderate offered load and a low or high level of host mobility.