Evaluating Ordering Heuristics for Dynamic Partial-Order Reduction Techniques
Evaluating Ordering Heuristics for Dynamic Partial-Order Reduction Techniques
复制标题
评估动态偏序约简技术的排序启发式
DOI：
10.1007/978-3-642-12029-9_22
复制
发表时间：
2010
影响因子：
19.6
通讯作者：
G. Agha
中科院分区：
文献类型：
--
作者：
Steven Lauterburg;Rajesh K. Karmani;D. Marinov;G. Agha
演员程序由许多称为参与者的并发对象组成，这些对象通过交换消息来通信。参与者中的非确定性是由处理可用消息的不同命令所产生的。 Actor程序的系统测试探讨了各种可行的消息处理时间表。动态局部减少（DPOR）技术通过修剪勘探空间的一部分加速系统测试。根据对时间表的探索，DPOR算法可能会发现它不需要探索其他时间表。但是，使用DPOR可以实现的潜在修剪高度取决于考虑处理消息的顺序。本文评估了许多启发式方法，以选择探索参与者计划的消息的顺序，并总结其优势和缺点。
Actor programs consist of a number of concurrent objects called actors, which communicate by exchanging messages. Nondeterminism in actors results from the different possible orders in which available messages are processed. Systematic testing of actor programs explores various feasible message processing schedules. Dynamic partial-order reduction (DPOR) techniques speed up systematic testing by pruning parts of the exploration space. Based on the exploration of a schedule, a DPOR algorithm may find that it need not explore some other schedules. However, the potential pruning that can be achieved using DPOR is highly dependent on the order in which messages are considered for processing. This paper evaluates a number of heuristics for choosing the order in which messages are explored for actor programs, and summarizes their advantages and disadvantages.