An Automated Approach to Generating Efficient Constraint Solvers

Presentation on theme: "An Automated Approach to Generating Efficient Constraint Solvers"— Presentation transcript:

1 An Automated Approach to Generating Efficient Constraint Solvers
Dharini Balasubramaniam Christopher Jefferson St Andrews, UK

2 Motivation Combinatorial problem 参数，变量，域，约束和约束之间的联系
解决方法：constrain solve 1，对问题建模，包括决策变量和约束 2，对模型约束求解

3 Motivation Drawback 1，现在的约束求解较复杂，难以与新技术结合；
2，现在的约束求解对输入模型的分析很少，甚至没有，导致不能利用模型来进行更好的求解过程

4 Motivation 解决方法： 手工进行求解的过程 Drawback 需要丰富的思考经验，阻碍了约束求解的推广。

5 Contribution 实现了名为Dominion的约束求解框架，该框架可以分析问题，然后利用companents来产生约束的求解。
1，使细粒度的优化可行，使得可以求解更大更困难的问题； 2，该框架可以和更多的技术结合，使得求解器的功能更加强大。

6 Process DIL： Dominion Input Language
Grasp： architecture description languages

7 Process A, architecture description languages：
1, the specification of components in Grasp as elements at the architectural level 2, corresponding implementation of these components at the code level

8 Process B, Problem Component Generation
DOL& problem component generator tool problem component与支持指定接口和满足条件的变量和constraint components相连接

9 Process C, Determining Valid Solvers（not necessary） D, Analyser
利用component library 产生一系列的candidate solver architectures，然后利用人工智能技术从中选择最好的。 Hill climbing

10 Process E, Solver generation 1，导入被选结构需要的Component files
2，示例包含的components和合适的参数 3，产生代码来读取执行时间参数，配置 4，执行约束求解

11 Experiments 程序：N-Queens，BIBD， Golomb， Graceful，NMR，Msquare
比较目标：Dominion，Minion 比较内容：执行时间，内存消耗

12 Experiments 时间

13 Experiments 内存

14 Axis: Automatically Fixing Atomicity Violations through Solving Control
Peng Liu Charles Zhang The Hong Kong University of Science and Technology

15 Motivation Atomicity The violations are difficult for developers to fix
先前的工作：Afix 缺点：性能的下降甚至导致死锁

16 Contribution 1，提出了一种自动化方法，可以修正原子性违反问题，同时可以保证对程序并发度的干扰最小，没有死锁；
2，减少了原子性违反的fixing，以进行约束求解，可以用于并发； 3，提出了一种新的Petri网模型，包括动态调用文本信息和静态程序代码。该模型对修正原子性违法问题更加完整，精确和适用。

17 Petri Net Petri网是对离散并行系统的数学表示。

18 Process 1, On-Demand Petri Net Construction
single-variable, multi-variables Atomicity violation sα and sβ are executed by the same thread and sγ is a remote statement

19 Process B. Control Constraints

20 Process

21 C, Solving the Control Constraints

22

23 Evaluation 1，对于修复原子性违反是否有效 2，对于原程序并发性的影响 3，是否会引入新的死锁

24 Evaluation

25 Evaluation

26 Evaluation

27 Q&A THANKS