In this paper, we present and analyze a distributed hash table-based supervised peer-to-peer system that allows an even distribution of and efficient lookup for objects (e.g. data or tasks) stored in the system. A sup...
详细信息
ISBN:
(纸本)0769521320
In this paper, we present and analyze a distributed hash table-based supervised peer-to-peer system that allows an even distribution of and efficient lookup for objects (e.g. data or tasks) stored in the system. A supervised peer-to-peer system is a system that is formed by a supervisor but in which all other activities can be performed on a peer-to-peer basis without involving the supervisor. Our system has average constant degree and can distribute objects evenly among the peers up to a constant factor in expectation. The supervised peer-to-peer approach makes the system particularly useful for computational grids. As an example, we discuss the use of our structure for recursively defined algorithms such as dynamic programming and distributed tree searches, and practical problems such as web crawling;our structure distributes tasks randomly and prevents repeated computations to optimize parallel efficiency.
QR methods for solving Toeplitz tridiagonal systems are well developed with applications in numerous interdisciplinary fields. There is a strong motivation to develop faster, more efficient and, more importantly, scal...
详细信息
ISBN:
(纸本)0769521320
QR methods for solving Toeplitz tridiagonal systems are well developed with applications in numerous interdisciplinary fields. There is a strong motivation to develop faster, more efficient and, more importantly, scalable algorithms to factor such systems due to their significance in many scientific applications. In this paper, we present two parallel QR factorization algorithms used to solve Toeplitz tridiagonal systems. QR factorization is accomplished using Householder reflections and Givens rotations. These parallel algorithms exhibit high scalability and near linear to superlinear speedup on large system sizes when implemented on a distributed system.
distributed systems verification is one of the main issues in software engineering. It is considered as the major field of the formal specification techniques. However, many difficulties remain. In fact, the principal...
详细信息
ISBN:
(纸本)0769521320
distributed systems verification is one of the main issues in software engineering. It is considered as the major field of the formal specification techniques. However, many difficulties remain. In fact, the principal problem is in producing a coherent specification and providing a fully integrated semantics. Since formal methods are mathematical description models that try to give a response concerning the reliability of a system. It remains a hard way for the designers. Thus, we present, in this paper, an open environment for the integration of formal methods in the description and verification of distributed and concurrent systems. The system currently uses UML notation and provides rewriting logic, model checking, theorem proving, and simulation techniques.
As clusters of workstations become increasingly popular the need for component frameworks that facilitate the high level modeling and rapid prototyping of parallel and distributed applications on such systems is becom...
详细信息
ISBN:
(纸本)0769521320
As clusters of workstations become increasingly popular the need for component frameworks that facilitate the high level modeling and rapid prototyping of parallel and distributed applications on such systems is becoming pressing. Many scientists and engineers have image and signal processing applications that could benefit from cluster computing. However, these applications often exist as legacy code, such as serial Matlab functions, which are not easily parallelizable. The goal of the JavaPorts project is to provide a framework and a set of tools that make it easy to develop component-based parallel and distributed applications for networks of heterogeneous computing nodes. The latest version of the package supports the integration of Java and Matlab components into the same application and provides a mechanism for incorporating legacy Matlab functions into parallelprocessing applications. The design and salient features of the framework and associated tools are discussed here, and application examples are presented which highlight how JavaPorts can be used to model, develop, launch and restructure applications with any number of interacting Java and Matlab components.
This paper studies a communication model that aims at extending the scope of computational grids by allowing the execution of parallel and/or distributed applications without imposing any programming constraints or th...
详细信息
ISBN:
(纸本)0769521320
This paper studies a communication model that aims at extending the scope of computational grids by allowing the execution of parallel and/or distributed applications without imposing any programming constraints or the use of a particular communication layer. Such model leads to the design of a communication framework for grids which allows the use of the appropriate middleware for the application rather than the one dictated by the available resources. Such a framework is able to handle any communication middleware - even several at the same time - on any kind of networking technologies. Our proposed dual-abstraction (parallel and distributed) model is organized into three layers: arbitration, abstraction and personalities which are highlighted in the paper. The performance obtained with PadicoTM, our available open source implementation of the proposed framework, show that such functionality can be obtained with still providing very high performance.
The paper concerns task graph scheduling in parallel programs for a parallel architecture based on dynamic SMP processor clusters with data transmissions on the fly. The assumed executive computer architecture consist...
详细信息
ISBN:
(纸本)0769522106
The paper concerns task graph scheduling in parallel programs for a parallel architecture based on dynamic SMP processor clusters with data transmissions on the fly. The assumed executive computer architecture consists of a set of NoC modules, each containing a set of processors and memory blocks connected via a local interconnection network. NoC modules are connected via a global interconnection network. An algorithm for scheduling parallel program graphs is presented, which decomposes an initial program graph into sub-graphs, which are then mapped to NoC modules, reducing global communication between modules. Then these subgraphs are structured inside the modules to include reads on the fly and processor switching. Reads on the fly reduce execution time of the program by elimination of read operations in linear program execution time.
In this paper we present a coarse-grained parallel multilevel algorithm for the k-way hypergraph partitioning problem. The algorithm significantly improves on our previous work in terms of run time and scalability beh...
详细信息
This paper applies nature inspired concepts and techniques from computer science, i.e. evolutionary computing, to gain a better understanding of the evolutionary history of birdsong. Notes are created and evolved acco...
详细信息
ISBN:
(纸本)0769521320
This paper applies nature inspired concepts and techniques from computer science, i.e. evolutionary computing, to gain a better understanding of the evolutionary history of birdsong. Notes are created and evolved according to fitness criteria to produce accurate and recognizable birdsong notes. The successful parallel simulation that was produced for this study can provide an excellent framework for future experimentation to determine how and why birdsongs evolved. This work is supported by NSF grant 0321218.
We present a parallel simulator - BigSim - for predicting performance of machines with a very large number of processors. The simulator provides the ability to make performance predictions for machines such as Blue-Ge...
详细信息
ISBN:
(纸本)0769521320
We present a parallel simulator - BigSim - for predicting performance of machines with a very large number of processors. The simulator provides the ability to make performance predictions for machines such as Blue-Gene/L, based on actual execution of real applications. We present this capability using case-studies of some application benchmarks. Such a simulator is useful to evaluate the performance of specific applications on such machines even before they are built. A sequential simulator may be too slow or infeasible. However, a parallel simulator faces problems of causality violations. We describe our scheme based on ideas from parallel discrete event simulation and utilize inherent determinacy of many parallel applications. We also explore techniques for optimizing such parallel simulations of machines with large number of processors on existing machines with fewer number of processors.
In this paper we present a disk-based parallel formulation of the multilevel k-way hypergraph partitioning algorithm. This algorithm provides the capability to partition very large hypergraphs that hitherto could not ...
详细信息
ISBN:
(纸本)0769521320
In this paper we present a disk-based parallel formulation of the multilevel k-way hypergraph partitioning algorithm. This algorithm provides the capability to partition very large hypergraphs that hitherto could not be partitioned since the memory required exceeds that available on a single workstation. The algorithm has three main phases: parallel coarsening, sequential partitioning of the coarsest hypergraph and parallel refinement. At each parallel coarsening and refinement step disk is used to minimise memory usage. We apply the algorithm to very large hypergraphs with (10 7) vertices from the domain of performance modelling and show that the partitioning quality is approximately 20% better in terms of the (k - 1) metric than approximate partitionings produced by a state-of-the-art parallel graph partitioning tool.
暂无评论