Fast shared-memory streaming multilevel graph partitioning Jafari, Nazanin; Selvitopi, Oguz; Aykanat, Cevdet
Journal of parallel and distributed computing,
January 2021, 2021-01-00, 2021-01-01, Letnik:
147, Številka:
C
Journal Article
Recenzirano
Odprti dostop
A fast parallel graph partitioner can benefit many applications by reducing data transfers. The online methods for partitioning graphs have to be fast and they often rely on simple one-pass streaming ...algorithms, while the offline methods for partitioning graphs contain more involved algorithms and the most successful methods in this category belong to the multilevel approaches. In this work, we assess the feasibility of using streaming graph partitioning algorithms within the multilevel framework. Our end goal is to come up with a fast parallel offline multilevel partitioner that can produce competitive cutsize quality. We rely on a simple but fast and flexible streaming algorithm throughout the entire multilevel framework. This streaming algorithm serves multiple purposes in the partitioning process: a clustering algorithm in the coarsening, an effective algorithm for the initial partitioning, and a fast refinement algorithm in the uncoarsening. Its simple nature also lends itself easily for parallelization. The experiments on various graphs show that our approach is on the average up to 5.1x faster than the multi-threaded MeTiS, which comes at the expense of only 2x worse cutsize.
•We propose a parallel multilevel graph partitioner based on a flexible streaming algorithm.•The same streaming algorithm is utilized within each of the three stages of the multilevel partitioning process.•By adopting a streaming-based approach for partitioning, we offer a tradeoff between speed and quality.•Our approach is five times faster than a very common offline partitioner while it degrades the quality only by a factor of two.
In this report we show that a fast parallel graph partitioner can benefit many applications by reducing data transfers. The online methods for partitioning graphs have to be fast and they often rely ...on simple one-pass streaming algorithms, while the offline methods for partitioning graphs contain more involved algorithms and the most successful methods in this category belong to the multilevel approaches. In this work, we assess the feasibility of using streaming graph partitioning algorithms within the multilevel framework. Our end goal is to come up with a fast parallel offline multilevel partitioner that can produce competitive cutsize quality. We rely on a simple but fast and flexible streaming algorithm throughout the entire multilevel framework. This streaming algorithm serves multiple purposes in the partitioning process: a clustering algorithm in the coarsening, an effective algorithm for the initial partitioning, and a fast refinement algorithm in the uncoarsening. Its simple nature also lends itself easily for parallelization. The experiments on various graphs show that our approach is on the average up to 5.1x faster than the multi-threaded MeTiS, which comes at the expense of only 2x worse cutsize.
In this paper, a multiscale convolutional network (MSCN) and graph-partitioning-based method is proposed for accurate segmentation of cervical cytoplasm and nuclei. Specifically, deep learning via ...the MSCN is explored to extract scale invariant features, and then, segment regions centered at each pixel. The coarse segmentation is refined by an automated graph partitioning method based on the pretrained feature. The texture, shape, and contextual information of the target objects are learned to localize the appearance of distinctive boundary, which is also explored to generate markers to split the touching nuclei. For further refinement of the segmentation, a coarse-to-fine nucleus segmentation framework is developed. The computational complexity of the segmentation is reduced by using superpixel instead of raw pixels. Extensive experimental results demonstrate that the proposed cervical nucleus cell segmentation delivers promising results and outperforms existing methods.
For an integer k≥2, a k-community structure in an undirected graph is a partition of its vertex set into k sets called communities, each of size at least two, such that every vertex of the graph has ...proportionally at least as many neighbours in its own community as in any other community. In this paper, we give a necessary and sufficient condition for a forest on n vertices to admit a k-community structure. Furthermore, we provide an O(k2⋅n2)-time algorithm that computes such a k-community structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n≥k≥2 vertices admits a k-community structure that can be found in time O(k2⋅n2). We then consider threshold graphs and show that every connected threshold graph admits a 2-community structure if and only if it is not isomorphic to a star; also if such a 2-community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2-community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2-community structures, even if communities are allowed to have size one.
Sharding is an important technology that utilizes group parallelism to enhance the scalability and performance of blockchain. However, the existing solutions use a historical transaction-based ...approach to reallocate shards, which cannot handle temporary overload and incurs additional overhead during the reallocation process. To this end, this paper proposes LMChain, an efficient load-migratable beacon-based sharding blockchain system. The primary goal of LMChain is to eliminate reliance on historical transactions and achieve the high performance. Specifically, we redesign the state maintenance data structure in Beacon Shard to effectively manage all account states at the shard level. Then, we innovatively propose a load-migratable transaction processing protocol built upon the new data structure. To mitigate read-write conflicts during the selection of migration transactions, we adopt a novel graph partitioning scheme. We also adopt a relay-based method to handle cross-shard transactions and resolve inter-shard state read-write conflicts. We implement the LMChain prototype and conduct experiments in a real network environment comprising 17 cloud servers. Experimental results show that, compared with state-of-the-art solutions, LMChain effectively reduces the average transaction waiting latency of overloaded transactions by 30% to 48% in different cases within 16 transaction shards, while improving throughput by 3% to 10%.
In a discrete balanced graph partitioning problem (DBGPP), a simple undirected weighted graph in that both vertices and edges are weighted is given. The task is dividing vertices into two disjoint ...subsets such that the sum of the weights of cut edges is minimized and the sum of the weights of vertices in each subset must equal or be as close as possible to each other. Here in order to solve the DBGPP, we first transform the problem into continuous quadratic programming and then show that the new problem has a binary solution, which is the optimal solution for the DBGPP. We also give necessary and sufficient conditions of continuous quadratic programming to identify stationary and local optimal solutions. In addition, we propose a local search to find a binary solution of the continuous quadratic programming. An approximated solution of the DBGPP is obtained using a hybrid simulated annealing algorithm. In our proposed algorithm, the structure of the objective function in a continues problem is considered as the evaluator function. Due to the Dolan–Moré performance profiles and the non-parametric statistical one-sided Wilcoxon signed rank test, we demonstrate the efficiency of our proposed approach in comparison with other available methods.
•Transforming the DBGPP into continuous quadratic programming.•Continuous quadratic programming has a binary solution.•Proving necessary and sufficient conditions.•Proposing a local search to find a binary solution.•Finding an approximated solution of the DBGPP
•A new methodology to partition the bipartite graph in the ride-matching problem.•The partitioning forms sub-problems that are uniform within tolerance in size.•An entire trip is considered to be the ...object in partitioning.•The iterative solution algorithm terminates in a finite number of steps.•The iterative solution algorithm obtains strictly superior partitions with iterations.
A dynamic ridesharing system is a platform that connects drivers who use their personal vehicles to travel with riders who are in need of transportation, on a short notice. Since each driver/rider may have several potential matches, to achieve a high performance level, the ridesharing operator needs to make the matching decisions based on a global view of the system that includes all active riders and drivers. Consequently, the ride-matching problem that needs to be solved can become computationally expensive, especially when the system is operating over a large region, or when it faces high demand levels during certain hours of the day. This paper develops a graph partitioning methodology based on the bipartite graph that arises in the one-to-one ride-matching problem. The proposed method decomposes the original graph into multiple sub-graphs with the goal of reducing the overall computational complexity of the problem as well as providing high quality solutions. We further show that this methodology can be extended to more complex ride-matching problems in a dynamic ride-sharing system. Using numerical experiments, we showcase the advantages of the new partitioning method for different forms of ride-matching problems. Moreover, a sensitivity analysis is conducted to show the impact of different parameters on the quality of our solution.
Microgrids are known as clusters of distributed energy resources serving a group of distributed loads in grid-connected and isolated grid modes. Nowadays, the concept of microgrids has become a key ...subject in the smart grid area, demanding a systematic procedure for their optimal construction. According to the IEEE Std 1547.4, large distribution systems can be clustered into a number of microgrids to facilitate powerful control and operation infrastructure in future distribution systems. However, clustering large systems into a set of microgrids with high reliability and security is not reported in current literature. To fill-out this gap, this paper presents a systematic and optimized approach for designing microgrids taking into account system reliability- and supply-security-related aspects. The optimum design considers sustained and temporary faults, for system reliability via a combined probabilistic reliability index, and real and reactive power balance, for supply security. The loads are assumed to be variable and different distributed generation (DG) technologies are considered. Conceptual design, problem formulation and solution algorithms are presented in this paper. The well-known PG&E 69-bus distribution system is selected as the test system. The effect of optimization coefficients on the design and the robustness of the algorithm are investigated using sensitivity studies.
PDF
