作者：
Derbel, B.Mosbah, M.LaBRI
Université Bordeaux I ENSEIRB 351 Cours de la libration 33405 Talence France
We present a linear time distributed algorithm for decomposing a graph into a disjoint set of clusters. This algorithm is truly parallel since many clusters can be constructed in parallel, which gives an answer to a q...
详细信息
We present a linear time distributed algorithm for decomposing a graph into a disjoint set of clusters. This algorithm is truly parallel since many clusters can be constructed in parallel, which gives an answer to a question asked by S. Moran and S. Snir in [1]. Moreover, no precomputed spanning tree is required for the computation of clusters. We apply the designed algorithm to construct covers for synchronizers γ1 and γ2.
In this paper parallel approach to the algorithm of discrete exact state estimation is presented. The novel idea of double-layer parallel decomposition of such computational algorithm is explained and results of its f...
详细信息
ISBN:
(纸本)9780889867048
In this paper parallel approach to the algorithm of discrete exact state estimation is presented. The novel idea of double-layer parallel decomposition of such computational algorithm is explained and results of its full implementation are showed. Numerical tests of the computational algorithm with discrete exact state estimator in the context of its scalability are included. All of presented results were obtained by the use of MPI library in the Linux cluster.
As grids typically consist of heterogeneously managed subsystems with strongly varying resources, resource availability should be taken into account in the job scheduling process. This paper introduces several dynamic...
详细信息
ISBN:
(纸本)9780889866386
As grids typically consist of heterogeneously managed subsystems with strongly varying resources, resource availability should be taken into account in the job scheduling process. This paper introduces several dynamic online scheduling heuristics that reduce task loss and execution delay resulting from resource failures. ne heuristics are based upon task replication and rescheduling of failed tasks. Characteristic to the proposed methods is the relative simplicity and the efficiency with which they are dealing with dynamic grid environments. For tuning and evaluation of the algorithms, a discrete-event simulation framework was used. Grid systems with high and low system load. as well as varying failure patterns were investigated. The experiments have shown that the proposed failure detection based heuristics provide for almost lossless task execution but can decrease system performance. while replication-based algorithms generally result in good throughput on unreliable non-excessively loaded grids, however without giving a guarantee on the number of jobs lost.
This paper develops a parallelcomputing system based on open standards, such as Extensible Markup Language (XML), Simple Object Access Protocol (SOAP)1 and Common Language Runtime (CLR) 2. To date parallelsystems ba...
详细信息
This paper develops a parallelcomputing system based on open standards, such as Extensible Markup Language (XML), Simple Object Access Protocol (SOAP)1 and Common Language Runtime (CLR) 2. To date parallelsystems based on clustered computers have been primarily restricted to the Unix and Linux family of operating systems. However, the popularity of the Microsoft Windows platform and the richness of reusable modules provided by the *** Framework makes it an attractive platform. Motivated by this, a new parallelcomputing System based *** (***) is described. *** provides higher level abstractions for message passing than the widely used Message Passing Interface (MPI).
The use of divisible load scheduling theory to model and design grid systems such as those arising in large physics experiments is discussed. Current divisible load theory is summarized. A typical application, the STA...
详细信息
ISBN:
(纸本)088986392X
The use of divisible load scheduling theory to model and design grid systems such as those arising in large physics experiments is discussed. Current divisible load theory is summarized. A typical application, the STAR experiment at the Relativistic Heavy Ion Collider (RHIC) is discussed. This includes a sample calculation based on existing infrastructure numbers.
OpenMP is a popular programming environment for high-level shared-memory parallel processing in C, C++ and Fortran on multiple platforms. Using OpenMP, application developers can focus on the code they want to paralle...
详细信息
ISBN:
(纸本)9780889867048
OpenMP is a popular programming environment for high-level shared-memory parallel processing in C, C++ and Fortran on multiple platforms. Using OpenMP, application developers can focus on the code they want to parallelize for better performance without having to do all the work in code parallelization. While hiding much of the complexity in parallel processing, it imposes a great challenge for the developers to make sure the run-time behavior of the code is as expected. In this paper, we explore potential risks with using OpenMP through reduction, a frequently performed operation in parallel processing.
Mutual exclusion is a fundamental problem in distributed processing systems. A generalization of mutual exclusion called k-exclusion for shared memory systems was introduced by Fischer et al. in [8] and subsequently s...
详细信息
Mutual exclusion is a fundamental problem in distributed processing systems. A generalization of mutual exclusion called k-exclusion for shared memory systems was introduced by Fischer et al. in [8] and subsequently studied in [1, 2, 3, 5]. In this paper, we present a simple solution to this problem and prove its correctness. Our solution is efficient both in time and space.
The purpose of this case study is to develop a performance model for an enterprise grid for performance management grid capacity planning(1). The target environment includes,grid applications such as health-care arid ...
详细信息
ISBN:
(纸本)9780889866386
The purpose of this case study is to develop a performance model for an enterprise grid for performance management grid capacity planning(1). The target environment includes,grid applications such as health-care arid financial services where the data is located primarily within the resources of a worldwide corporation. The approach is to build a discrete event simulation model for a representative work-flow grid. Five work-flow classes, found using a customized k-means clustering algorithm characterize the workload of the grid. Analyzing the gap between the simulation arid measurement data validates the model. The case study demonstrates that the simulation model can be used to predict the V a given a workload forecast. The,rid system performance model is also used to evaluate alternative scheduling strategies. The simulation model is flexible arid easily incorporates several system details.
This paper addresses the workflow rescheduling problem in the Grid where resource performance is fluctuating and hard to predict. Unlike existing rescheduling approaches targeting the same problem, the proposed a mobi...
详细信息
ISBN:
(纸本)9780889867048
This paper addresses the workflow rescheduling problem in the Grid where resource performance is fluctuating and hard to predict. Unlike existing rescheduling approaches targeting the same problem, the proposed a mobile agent based distributed approach. Once a workflow is submitted to a central workflow scheduler, an initial schedule for tasks in that workflow will be created first. Then, at the workflow run-time, mobile agents which carry those tasks will reschedule themselves by a rescheduling algorithm when resource performance changes.
In this paper, we present a new auction algorithm for the linear assignment problem, based on a new technique, called look-back bidding. The main idea is to keep local working sets of objects. It leads to significant ...
详细信息
ISBN:
(纸本)088986392X
In this paper, we present a new auction algorithm for the linear assignment problem, based on a new technique, called look-back bidding. The main idea is to keep local working sets of objects. It leads to significant performance gains both in sequential and distributed memory parallel versions. We give performance results of the new algorithm, called look-back auction algorithm, and compare its complexity with standard auction algorithms. In the parallel version, our new algorithm eliminates a substantial amount of interprocessor communication.
暂无评论