• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Algorithms for Balanced Graph Colorings with Applications in Parallel Computing
【24h】

Algorithms for Balanced Graph Colorings with Applications in Parallel Computing

机译：平衡图着色的算法及其在并行计算中的应用

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graph coloring—in a generic sense—is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.
机译：从一般意义上讲，图形着色用于识别并行科学计算应用程序中独立任务的子集。传统的颜色启发法旨在减少使用的颜色数量，因为该数量也对应于应用程序中并行步骤的数量。但是，如果生成的颜色类别在尺寸上存在偏差，则硬件资源的利用效率就会降低，尤其是对于较小的颜色类别而言。合理的着色是一种色彩的理论表述，可以保证颜色类别之间的完美平衡，在这里将其实际松弛称为平衡着色。在本文中，我们考虑了并行计算环境中的平衡着色模型。目的是实现输入图的平衡着色，而又不增加平衡不考虑的算法本来可以使用的颜色数量。我们提出并研究了多种启发式方法，旨在为着色问题的两个变体（距离1着色（标准着色问题）和部分距离2着色（在二分图上定义））实现这种平衡的着色。我们介绍了多核和多核架构的并行化方法，并就实现的平衡质量和性能对它们的有效性进行了交叉评估。此外，我们研究了提出的平衡着色启发法对具体应用的影响，即。并行社区检测，这是不规则应用程序的一个示例。此外，我们对基本的平衡方案提出了一些扩展，并评估了它们的平衡功效和性能特征。从算法到应用程序，本文中提出的对平衡着色的彻底处理有望为寻求使用着色改进其应用程序并行性能的并行应用程序开发人员提供宝贵的资源。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号