Community detection is essential to various graph analysis applications. Infomap is a graph clustering algorithm capable of achieving high-quality communities. However, it remains a very challenging problem to effecti...
详细信息
ISBN:
(纸本)9781450365109
Community detection is essential to various graph analysis applications. Infomap is a graph clustering algorithm capable of achieving high-quality communities. However, it remains a very challenging problem to effectively apply Infomap on large graphs. By analyzing communication and workload patterns of Infomap and leveraging a distributed delegate partitioning and distribution method, we develop a new heuristic strategy to carefully coordinate the community constitution from the vertices of a graph in a distributed environment, and achieve the convergence of the distributed clustering algorithm. We have implemented our optimized algorithm using MPI (Message Passing Interface), which can be easily employed or extended to massively distributed computing systems. We analyze the correctness of our algorithm, and conduct an intensive experimental study to investigate the communication and computation cost of our distributed algorithm, which has not shown in previous work. The results demonstrate the scalability and the correctness of our distributed Infomap algorithm with large-scale real-world datasets.
The concept of Global virtual time (GVT) has become an essential element of optimistic time management algorithms (TMA) that provide synchronization in a parallel and distributed computing environment. The performance...
详细信息
ISBN:
(纸本)1601320841
The concept of Global virtual time (GVT) has become an essential element of optimistic time management algorithms (TMA) that provide synchronization in a parallel and distributed computing environment. The performance of this optimistic TMA is optimal since it gives accurate GVT approximation. However, this accurate GVT approximation comes at the expense of slower execution rate which results a high GVT latency. Since this resultant GVT latency is not only high but also widely varied, the multiple processors involve in communication remain idle during that period of time. This paper examines the potential use of tress and butterflies barriers with the Mattern's optimistic TMA [1] using a ring structure. Our Simulation and numerical results verify that the use of tree barriers with the Mattern's GVT structure can significantly improve the latency time and thus increase the overall throughput of the parallel and scalable distributed simulation systems.
In this paper, we present the clustering boundary cutting trie algorithm in order to solve the problem of huge time consumption in existing trie based algorithms. In the proposed solution, there are two stages. The fi...
详细信息
ISBN:
(纸本)9781538637906
In this paper, we present the clustering boundary cutting trie algorithm in order to solve the problem of huge time consumption in existing trie based algorithms. In the proposed solution, there are two stages. The first stage is the density-based rule clustering process. The rules are represented as a range between 0 and 1 according to the prefixes of the packet fields. When the number of the rules in a range reaches to a certain density, the corresponding rules are formed in a cluster. The second stage is the trie construction process based on these clusters. Compared with traditional packet classification algorithms, the searching time of our algorithm increases by 47.05% -73.76% and keep the high accuracy of 69.83%-93.17%. The experiment demonstrates that our algorithm can effectively keep high accuracy as well as keeping stable high-throughput, and it is suitable for actual deployment.
Porting to the cloud large scientific applications designed and optimized for a standard HPC facility does not always pay off, mainly because of the implied communication pattern. By profiling the applications, resear...
详细信息
ISBN:
(纸本)9781728116440
Porting to the cloud large scientific applications designed and optimized for a standard HPC facility does not always pay off, mainly because of the implied communication pattern. By profiling the applications, researchers can build a performance model, which is able to give insights about how the application will perform on the cloud. To validate this approach, we use a hemodynamic application that embeds both heavy computations and extensive communications with several collective operations to exchange data across all processes. We expect that this case instance is a model for other applications. Our approach is based on profiling and modeling, and builds an analytical model for the communication pattern of the chosen hemodynamic application. We collect data both on an on-premise HPC system and on the Google Cloud infrastructure, and assess the prediction based on the analytic model. The outcome suggests that the prediction consistently underestimates the actual execution time, but correctly guess the scalability, thus allowing to strike a good balance between performance and costs. Finally, we introduce a figure of merit to assess cost vs performance between cloud and on-premise implementation, and validate a first version of such a model.
The organizers of the 4th international Workshop on Autonomic Solutions for parallel and distributed Data Stream processing (Auto-DaSP 2021) are delighted to welcome you to the workshop proceedings as part of the ICPE...
详细信息
ISBN:
(纸本)9781450381949
The organizers of the 4th international Workshop on Autonomic Solutions for parallel and distributed Data Stream processing (Auto-DaSP 2021) are delighted to welcome you to the workshop proceedings as part of the ICPE 2021 conference companion.
The Travelling Salesman Problem (TSP) is one of the typical combinatorial optimization problems that is easy to describe but hard to solve. In this work, we present a novel solution that integrates a genetic algorithm...
详细信息
ISBN:
(纸本)9781538637906
The Travelling Salesman Problem (TSP) is one of the typical combinatorial optimization problems that is easy to describe but hard to solve. In this work, we present a novel solution that integrates a genetic algorithm, local-search heuristics, and a greedy algorithm. For the genetic algorithm we keep the evolutionary technique to generate children from parents, which uses operators like mutation, selection of the most fitted element, and crossover, but the latter is enhanced with a local-search heuristic. We also use the local search heuristic for its strong climbing ability, as well as to find local optima efficiently in the TSP space. The greedy algorithm is used to generate new greedy children from parents. The experimental evaluation shows that the optimization algorithm presented provides higher quality solutions for TSP with respect to previous genetic algorithms, within reasonable computational time.
Static routing, is an optimization problem, which can be solved when the network topology has been defined. Large scale networks, like Internet, have to face unpredictable behaviours: trafic conditions are constantly ...
详细信息
ISBN:
(纸本)1892512459
Static routing, is an optimization problem, which can be solved when the network topology has been defined. Large scale networks, like Internet, have to face unpredictable behaviours: trafic conditions are constantly changing, the structure of the network itself may fluctuate (switching stations or connections can fail),... In that context, dynamic routing systems seem to be a good approach. Some of them can be seen as quasistatic, others are highly dynamic, most of them are centralized, which increases the bandwidth according to information exchange for the network control, We propose a decentralized routing protocol with mobile reactive agents for network control, based on ant algorithms, where, at the beginning, clients and servers know neither the form of the network, nor the place of others agents on the network. We introduce a capacity model for information evaporation through the network, and a Time To Live (TTL) parameter which indicates how long a packet should be allowed to survive before it is discarded. We discuss the roles of those parameters in the self-organizing process, making the search of way on the network as best as possible (with regard to QoS) during time.
Massive remote sensing image fast processing is one of the important tasks for remote sensing image applications, it is not only data intensive but also computation intensive, which arises our interest in distributed ...
详细信息
ISBN:
(纸本)9780769529431
Massive remote sensing image fast processing is one of the important tasks for remote sensing image applications, it is not only data intensive but also computation intensive, which arises our interest in distributedparallelprocessing by grid computing., The novel grid computing technology seeks to aggregate computing resources which are geographically distributed or heterogeneous for computational intensive applications. In this paper, a grid-based image processing testbed is established for remote sensing image distributedprocessing, and middleware is developed, which was applied to remote sensing image distributed deblurring processing. Preliminary experimental results show the processing efficiency is greatly improved, which demonstrate the promising potential of grid computing technology on remote sensing image distributedprocessing.
Data parallel compilers have long aimed to equal the performance of carefully hand-optimized parallel codes. For tightly-coupled applications based on line sweeps, this goal has been particularly elusive. In the Rice ...
详细信息
ISBN:
(纸本)0769516203
Data parallel compilers have long aimed to equal the performance of carefully hand-optimized parallel codes. For tightly-coupled applications based on line sweeps, this goal has been particularly elusive. In the Rice dHPF compiler, we have developed a wide spectrum of optimizations that enable us to closely approach hand-coded performance for tightly-coupled line sweep applications including the NAS SP and BT benchmark codes. From lightly-modified copies of standard serial versions of these benchmarks, dHPF generates MPI-based parallel code that is within 4% of the performance of the hand-crafted MPI implementations of these codes for a 102(3) problem size (Class 13) on 64 processors. We describe and quantitatively evaluate the impact of partitioning, communication and memory hierarchy optimizations implemented by dHPF that enable us to approach hand-coded performance with compiler-generated parallel code.
A Leader is a Coordinator that supports a set of processes to cooperate a given task. This concept is used in several domains such as distributed systems, parallelism and cooperative support for cooperative work. In c...
详细信息
ISBN:
(纸本)1932415602
A Leader is a Coordinator that supports a set of processes to cooperate a given task. This concept is used in several domains such as distributed systems, parallelism and cooperative support for cooperative work. In completely asynchronous systems, there is no solution for the election problem satisfying both of safety and liveness properties in asynchronous distributed systems. Therefore, to solve the election problem in those systems, one property should be weaker than the other property. If an election algorithm strengthens the safety property in sacrifice of liveness property, it would never progress. But on the contrary, an election algorithm strengthening the liveness property in sacrifice of the safety property would have the high probability of violating the safety property. In this paper, we presents a safety strengthened Leader Election protocol with an unreliable failure detector and analyses it in terms of safety and liveness properties in asynchronous distributed systems.
暂无评论