面向分布式图计算的平衡图划分算法

关注分布式图计算和迭代计算处理方法选择,对计算机技术应用和改善计算机性能等方面具有现实意义。传统算法计算分布式图时,切割率最小化与负载均衡性方面无法实现协调控制,且极易出现NP组合优化等系列问题。因此,以平衡图划分算法为手段,解决分布式图计算问题,重点研究平衡系数、切割边规模。扰动次数一定的条件下,引入Metis,结合平衡图划分算法,进行试验对比分析。通过对比可以发现,该算法下的分布式图割边率计算准确性高于Metis,可以满足分布式图的实际计算需求,这说明平衡图划分算法具有实践应用价值。     

利用子空间划分的局部离群数据挖掘算法

目前大多数局部离群数据挖掘算法需人为事先设置参数或阈值,且难以应用到高维数据集.给出一种新的局部离群数据挖掘算法PSO-SPLOF,该算法首先将数据集划分为互不相交的子空间,利用偏斜度判断子空间划分的优劣,并采用微粒群算法搜索最优划分子空间集;其次针对每个最优划分子空间,计算其数据对象的局部离群因子SPLOF值,并用SPLOF值来度量数据对象的局部偏离程度.最后采用离散化的天体光谱数据作为数据集,实验验证了PSO-SPLOF算法具有受人为因素影响小、伸缩性强和运算效率高等优点.     

GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.     

Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning

In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic Bubble-FOS/C, a key component of a practical successful graph partitioner?(Meyerhenke et al. in J. Parallel Distrib. Comput. 69(9):750?C761, 2009). We begin by studying the disturbed diffusion scheme FOS/C, which computes the similarity measure used in Bubble-FOS/C and is therefore the most crucial component. By relating FOS/C to random walks, we obtain precise characterizations of the behavior of FOS/C on tori and hypercubes. Besides leading to new knowledge on FOS/C (and therefore also on Bubble-FOS/C), these characterizations have been recently used for the analysis of load balancing algorithms?(Berenbrink et al. in Proceedings of the 22nd Annual Symposium on Discrete Algorithms, pp. 429?C439, 2011). We then regard Bubble-FOS/C, which has been shown in previous experiments to produce solutions with good partition shapes and other favorable properties. In this paper we prove that it computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). This result provides the first substantial theoretical insight why Bubble-FOS/C yields good experimental results in terms of graph partitioning metrics. Moreover, we show that in bisections computed by Bubble-FOS/C, at least one of the two parts is connected. Using the aforementioned relation between FOS/C and random walks, we prove that in vertex-transitive graphs both parts must be connected components.     

Bipartite-Oriented Distributed Graph Partitioning for Big Learning

Many machine learning and data mining (MLDM) problems like recommendation, topic modeling, and medical diagnosis can be modeled as computing on bipartite graphs. However, most distributed graph-paralle...     

一种改进的并行计算图划分模型

图划分成功地应用在许多领域,但应用于并行计算时,使用边割度量通信量,其主要缺点是不能准确代表通信量,而且图划分模型没有考虑通信延迟和通信额外开销的分布对并行性能的影响.提出了改进的图划分模型,该模型将影响并行性能的多个要素(通信延迟、最大的局部通信额外开销和整体通信额外开销)整合到一个统一的代价函数,不仅克服了图划分模型中边割度量的一些缺点,而且可以通过调整加权参数,处理不同的优化目标和强调不同因素对并行性能的影响.     

用神经网络求解划分问题

划分问题是一类常见的ＮＰ完备的优化问题,本文利用推广的Ｈｏｐｆｉｅｌｄ神经网络模型解决了划分问题,并取得了较好的效果,为这个总理２的解决提供了一条新的途径。同时也为解决其它优化总理２提供了有益的启示。     

Parallel Dynamic Graph Partitioning for Adaptive Unstructured Meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimization technique known as relative gain optimization which both balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.     

Using Differential Evolution for a Subclass of Graph Theory Problems

Conventional differential evolution algorithms explore continuous spaces. In contrast, NP-complete graph problems are combinatorial and thus have discrete solution spaces, many with solutions encoded as binary strings. This letter describes a simple method showing how a conventional differential evolution algorithm can be used to solve these types of graph theory problems. The method is deterministic and can handle graphs of arbitrary size.     

Global Minimization for Continuous Multiphase Partitioning Problems Using a Dual Approach

This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding duality-based approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality.     

Achieving Optimal Inter-Node Communication in Graph Partitioning Using Random Selection and Breadth-First Search

Processing large graph datasets represents an increasingly important area in computing research and applications. The size of many graph datasets has increased well beyond the processing capacity of a single computing node, thereby necessitating distributed approaches. As these datasets are processed over a distributed system of nodes, this leads to an inter-node communication cost problem that negatively affects system performance. Previously proposed algorithms implemented breadth-first search (BFS) for graph searching and focused on the execution, parallel performance and not the communication. In this paper a new methodology is proposed that combines BFS with random selection in order to partition large graph datasets and effectively minimize inter-node communication. The new method is discussed and applied to the single-source shortest path and PageRank algorithms using three graphs that are representative of real-world scenarios. Experimental results show that graph inter-node communication for canonical graphs representative of real-world data is improved up to 42 % in case of Powerlaw graph, up to 27 % in case of Random near K-regular graph (with low degree), and up to 7 % in case of Random near K-regular graph (with high degree).     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

机器可选制造单元设计的半边图划分模型

机器可选制造单元设计问题是一类含有多种局部约束的复杂组合优化问题,用图划分算法解决此类问题将会面临指数级个图的划分。论文提出半边图理论,半边附属于顶点,一对半边可结合为边。用半边及其结合性表示各种局部约束,将机器可选制造单元设计问题转化为基于半边图的组合优化问题,即计划路径可选的半边图划分问题。     

A Dynamic Diffusion Optimization Method for Irregular Finite Element Graph Partitioning

To efficiently execute a finite element application program on a distributed memory multicomputer, we need to distribute nodes of a finite element graph to processors of a distributed memory multicomputer as evenly as possible and minimize the communication cost of processors. This partitioning problem is known to be NP-complete. Therefore, many heuristics have been proposed to find satisfactory sub-optimal solutions. Based on these heuristics, many graph partitioners have been developed. Among them, Jostle, Metis, and Party are considered as the best graph partitioners available up-to-date. For these three graph partitioners, in order to minimize the total cut-edges, in general, they allow 3% to 5% load imbalance among processors. This is a tradeoff between the communication cost and the computation cost of the partitioning problem. In this paper, we propose an optimization method, the dynamic diffusion method (DDM), to balance the 3% to 5% load imbalance allowed by these three graph partitioners while minimizing the total cut-edges among partitioned modules. To evaluate the proposed method, we compare the performance of the dynamic diffusion method with the directed diffusion method and the multilevel diffusion method on an IBM SP2 parallel machine. Three 2D and two 3D irregular finite element graphs are used as test samples. For each test sample, 3% and 5% load imbalance situations are tested. From the experimental results, we have the following conclusions. (1) The dynamic diffusion method can improve the partition results of these three partitioners in terms of the total cut-edges and the execution time of a Laplace solver in most test cases while the directed diffusion method and the multilevel diffusion method may fail in many cases. (2) The optimization results of the dynamic diffusion method are better than those of the directed diffusion method and the multilevel diffusion method in terms of the total cut-edges and the execution time of a Laplace solver for most test cases. (3) The dynamic diffusion method can balance the load of processors for all test cases.     

Discrete and Continuous Models for Partitioning Problems

Recently, variational relaxation techniques for approximating solutions of partitioning problems on continuous image domains have received considerable attention, since they introduce significantly less artifacts than established graph cut-based techniques. This work is concerned with the sources of such artifacts. We discuss the importance of differentiating between artifacts caused by discretization and those caused by relaxation and provide supporting numerical examples. Moreover, we consider in depth the consequences of a recent theoretical result concerning the optimality of solutions obtained using a particular relaxation method. Since the employed regularizer is quite tight, the considered relaxation generally involves a large computational cost. We propose a method to significantly reduce these costs in a fully automatic way for a large class of metrics including tree metrics, thus generalizing a method recently proposed by Strekalovskiy and Cremers (IEEE conference on computer vision and pattern recognition, pp. 1905–1911, 2011).     

基于0-1规划的并行计算图划分模型

图划分广泛地应用在许多科学与工程领域,但它应用于并行计算任务分配时,使用无向图表示数据依赖关系,这限制了它的应用(例如,无向图不能表示矩形和非对称依赖关系的应用).为了克服图划分的这个缺点,我们对数据间的依赖关系进行区分(即同一条边区分通信的发送方与接收方),然后基于0-1规划模型化这个问题,并通过互联网上求解优化问题常用的NEOS服务器进行求解,在一些数据集上的实验表明,0-1规划方法优于求解图划分流行的多层划分方法.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Parallel Algorithms for Partitioning Sorted Sets and Related Problems

We consider the following partition problem: Given a set S of n elements that is organized as k sorted subsets of size n/k each and given a parameter h with 1/k ≤ h ≤ n/k , partition S into g = O(n/(hk)) subsets D ₁ , D ₂ , . . . , D _g of size Θ(hk) each, such that, for any two indices i and j with 1 ≤ i < j ≤ g , no element in D _i is bigger than any element in D _j . Note that with various combinations of the values of parameters h and k , several fundamental problems, such as merging, sorting, and finding an approximate median, can be formulated as or be reduced to this partition problem. The partition problem also finds many applications in solving problems of parallel computing and computational geometry. In this paper we present efficient parallel algorithms for solving the partition problem and a number of its applications. Our parallel partition algorithm runs in O( log n) time using processors in the EREW PRAM model. The complexity bounds of our parallel partition algorithm on the respective special cases match those of the optimal EREW PRAM algorithms for merging, sorting, and finding an approximate median. Using our parallel partition algorithm, we are also able to obtain better complexity bounds (even possibly on a weaker parallel model) than the previously best known parallel algorithms for several important problems, including parallel multiselection, parallel multiranking, and parallel sorting of k sorted subsets. Received May 5, 1996; revised July 30, 1998.