• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Throughput-Driven Partitioning of Stream Programs on Heterogeneous Distributed Systems
【24h】

Throughput-Driven Partitioning of Stream Programs on Heterogeneous Distributed Systems

机译：异构分布式系统上流程序的吞吐量驱动分区

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

摘要

Graph partitioning is an important problem in computer science and is of NP-hard complexity. In practice it is usually solved using heuristics. In this article we introduce the use of graph partitioning to partition the workload of stream programs to optimise the throughput on heterogeneous distributed platforms. Existing graph partitioning heuristics are not adequate for this problem domain. In this article we present two new heuristics to capture the problem space of graph partitioning for stream programs to optimise throughput. The first algorithm is an adaptation of the well-known Kernighan-Lin algorithm, called (KLA), which is relatively slow. As a second algorithm we have developed the (CA) partitioning algorithm, which performs reconfiguration moves optimised to our problem type. We compare both KLA and CA with the generic meta-heuristic (SA). All three methods achieve similar throughput results for most cases, but with significant differences in calculation time. For small graphs KLA is faster than SA, but KLA is slower for larger graphs. CA on the other hand is always orders of magnitudes faster than both KLA and SA, even for large graphs. This makes CA potentially useful for re-partitioning of systems during runtime.
机译：图分区是计算机科学中的一个重要问题，具有NP困难的复杂性。在实践中，通常使用启发式方法解决。在本文中，我们介绍了使用图分区来划分流程序的工作量，以优化异构分布式平台上的吞吐量。现有的图分区试探法不适用于此问题域。在本文中，我们提出了两种新的启发式方法来捕获流程序的图分区问题空间，以优化吞吐量。第一种算法是相对较慢的著名的Kernighan-Lin算法（KLA）的改编。作为第二种算法，我们开发了（CA）分区算法，该算法执行针对我们的问题类型优化的重新配置动作。我们将KLA和CA与通用元启发式（SA）进行了比较。在大多数情况下，这三种方法均能获得相似的吞吐量结果，但计算时间却存在显着差异。对于小图，KLA比SA快，但是对于大图，KLA较慢。另一方面，即使对于大型图形，CA总是比KLA和SA快几个数量级。这使得CA可能在运行时对系统进行重新分区很有用。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号