SHF: Medium:Performance Analysis and Optimization for Logic Rule Engines

规则系统越来越多地应用于程序分析、语义网、安全框架、传感器网络、认知无线电和容忍中断网络等领域，每个领域都有自己对效率和可扩展性的需求。这些领域的进步将导致新一代崩溃和安全的应用程序，这些应用程序控制人类安全甚至生命所依赖的设备，提供关键信息，并通过汇集分散的以Web为中心的资源、分析它们并自动执行复杂的信息绑定任务来帮助人们做出明智的决策。然而，规则系统的现有实现不具有足够的可扩展性，并且已被证明在性能上存在很大差异。要使下一代健壮应用的上述愿景成为现实，必须了解规则系统的性能特征以及针对它们的可开发的可扩展优化和分析技术。虽然在改进规则系统的性能方面取得了进展，但这一问题仍然极具挑战性，在理论和实施方面都缺乏了解。该项目将为严格理解和优化规则系统制定一个全面的框架。该方法基于精确的代价计算和全局程序转换，结合和扩展了数据库查询优化、编译器优化和递归查询处理等技术。它包括：(1)生成逻辑等价但更有效的程序的技术；(2)为规则程序的运行时间和空间使用生成参数化代价公式的成本模型和分析；(3)预测代价公式参数的技术；(4)在逻辑等价的规则程序的指数级大空间中搜索启发式以找到具有最佳预测时间、空间和折衷的程序的启发式方法；以及(5)将该策略作为广泛使用的开源XSB Logic编程系统的优化器来实现。该方法和实现将使用程序分析和语义网中的应用程序进行评估。

Rule systems are increasingly used in areas ranging from Program Analysis,Semantic Web, Security Frameworks, Sensor Networks, Cognitive Radio, andDisruption-tolerant Networking, each with its own demands for efficiencyand scalability. Advances in these areas will lead to a new generation ofrobust and secure applications that control devices on which human safetyand even lives depend, supply with critical information, and help peoplemake informed decisions by pulling together distributed Web-centricresources, analyzing them, and automating complex information-bound tasks.However, existing implementations of rule systems are not sufficientlyscalable and have been shown to vary widely in performance. To make theabove vision of next generation robust applications a reality, one mustunderstand the performance characteristics of rule systems and developscalable optimization and analysis techniques for them. Although advanceshave been made in improving performance of rule systems, the problemremained extremely challenging and poorly understood both theoretically andimplementation-wise.This project will develop a comprehensive framework for rigorousunderstanding and optimization of rule systems. The approach is based onprecise cost calculations and global program transformations, and itcombines and extends techniques from database query optimization, compileroptimization, and recursive query processing. It includes: (1) techniquesfor generating logically equivalent but more efficient programs; (2) costmodels and analysis for generating parameterized cost formulas for therunning time and space usage of rule programs; (3) techniques forestimating parameters of the cost formulas; (4) heuristics for searchingthe exponentially large space of logically equivalent rule programs to findthe ones with the best predicted time, space, and tradeoffs; and (5)implementation of the strategy as an optimizer for the widely used,open-source XSB Logic Programming System. The method and implementationwill be evaluated using applications in Program Analysis and Semantic Web.