• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Euro-Par Parallel Processing Conference; 20050830-0902; Lisbon(PT) >Fast Convex Closure for Efficient Predicate Detection
【24h】

Fast Convex Closure for Efficient Predicate Detection

机译：快速凸封闭，可高效地进行谓词检测

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

摘要

The behaviour of parallel and distributed programs can be modeled as the occurrence of events and their interrelationship. Event data collected according to the event model is stored within a partial-order data structure, where it can be reasoned about, enabling debugging, program steering, and autonomic feedback control of the application. Reasoning over event data, a critical requirement for autonomic computing, is typically in the form of predicate detection, a search mechanism able to detect and locate arbitrary predicates within the event data. To enable hierarchical predicate detection, compound events are formed by computing the convex closure of the matching primitive events. In particular, the Xie and Taylor convex-closure algorithm forms the basis for such an approach to predicate detection. Unfortunately, their algorithm can be quite slow, especially for hierarchical compound events. In this paper, we study the cause of the problems in the Xie and Taylor algorithm. We then develop an efficient extension to their algorithm, based on a simple caching scheme. We prove our algorithm correct. We also provide experimental results that demonstrate that our approach reduces the execution time of the Xie and Taylor algorithm by up to 98 percent.
机译：可以将并行程序和分布式程序的行为建模为事件的发生及其相互关系。根据事件模型收集的事件数据存储在偏序数据结构中，可以在其中进行推理，从而启用应用程序的调试，程序控制和自主反馈控制。对事件数据进行推理（对自主计算的一项关键要求）通常采用谓词检测的形式，谓词检测是一种能够检测和定位事件数据中任意谓词的搜索机制。为了实现层次谓词检测，通过计算匹配原始事件的凸闭包来形成复合事件。特别地，Xie和Taylor凸封闭算法构成了这种谓词检测方法的基础。不幸的是，他们的算法可能非常慢，尤其是对于分层复合事件。在本文中，我们研究了Xie和Taylor算法中出现问题的原因。然后，我们基于简单的缓存方案，对其算法进行了有效扩展。我们证明我们的算法是正确的。我们还提供了实验结果，表明我们的方法将Xie和Taylor算法的执行时间减少了多达98％。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号