答案集编程的并行引擎

### 答案集编程的并行引擎 在答案集编程（ASP）领域，为了提高计算效率，并行计算成为了一个重要的研究方向。本文将深入探讨ASP中的并行计算，特别是垂直并行性的利用，并介绍相关的算法、数据结构和性能优化策略。 #### 1. 基本执行周期和扩展过程 首先，我们来看ASP的基本执行周期和扩展过程。以下是相关的算法代码： ```python function compute(Π:Program, A:Literals) begin B := expand( Π, A ); while ( (B consistent) and (B not complete) ) l := choose_literal( Π, B ); B := expand( Π, A ∪ { l } ); endwhile if (B is stable model of Π ) then return B; end function expand ( Π: Program; A: Literals) begin B := A; B’ = ∅ ; while (B ≠ B’ ) do B’ := B; B := apply_rules( Π, B); endwhile; return B; end ``` 在这个算法中，`compute`函数是核心的计算函数，它接收一个程序`Π`和一组文字`A`作为输入。首先，调用`expand`函数对`A`进行扩展，得到集合`B`。然后，在`B`一致且不完整的情况下，通过`choose_literal`函数选择一个文字`l`，并将其加入到`A`中，再次调用`expand`函数进行扩展。当`B`是`Π`的稳定模型时，返回`B`。 `expand`函数则是不断应用程序`Π`的规则，直到集合`B`不再发生变化。这个过程可以看作是对当前文字集合的不断扩展，以确定更多文字的真值。 非确定性源于`choose_literal`函数的执行。该函数选择一个满足特定条件的原子`l`：原子`l`在程序`Π`中以否定形式出现，并且`l`及其否定都不在当前集合`B`中。选择的原子会以其“猜测”的真值加入到部分答案集中，然后重新开始扩展过程。 每个非确定性计算可能以三种不同的方式终止： 1. **成功终止**：当前集合`B`为所有原子分配了真值，并且`B`确实是原始程序`Π`的答案集。 2. **冲突终止**：检测到冲突，即存在一个原子`a`在当前集合`B`中同时被赋值为真和假。 3. **非答案集终止**：当前集合`B`已完全扩展（即已为每个原子分配了真值且无冲突），但它不是程序`Π`的答案集。这种情况通常发生在正文字`a`被引入`B`，但程序规则无法为`a`的真值提供“支持”时。 与传统逻辑编程的执行类似，非确定性通过回溯到`choose_literal`生成的选择点来处理。每个`choose_literal`产生的选择点只有两个选择：一个将所选文字赋值为真，另一个将其赋值为假。 #### 2. ASP中的并行性 ASP计算的结构可以很容易地解释为基于约束的计算实例。其中，扩展规则的应用（`expand`）代表约束计算的传播步骤，而文字的选择（`choose_literal`）代表标记步骤。从这个角度来看，计算中存在两种非确定性： 1. **水平非确定性**：源于选择下一个要应用的扩展规则（在`expand`中）。 2. **垂直非确定性**：源于选择要添加到部分答案集中的文字（在`choose_literal`中）。 这两种非确定性与逻辑编程中识别的非确定性形式有很强的相似性。本项目的目标是探索从这些非确定性来源中利用并行性的途径。我们使用“垂直并行性”表示使用单独的计算线程来探索垂直非确定性产生的替代方案，使用“水平并行性”表示使用单独的计算线程同时对部分答案集应用不同的扩展规则。 然而，从ASP计算中利用并行性存在一些困难： - 已经在设计快速计算答案集的算法上投入了大量研究，我们希望保留这些技术。 - 计算结构（看作搜索树，其中非确定性点对应于树的节点）可能不规则且不平衡。分支的大小可能变得非常小，因此需要粒度控制和动态调度。 - 两种非确定性形式都不占主导地位。某些ASP程序进行很少的文字选择（即对`choose_literal`的调用），而大部分时间用于扩展；而其他程序则探索大量的选择。有些程序可以直接得到答案集，几乎不需要选择；而有些程序则花费大量时间在搜索大量文字上。 ASP不允许直接重用在逻辑程序并行执行上下文中开发的类似技术。现有的机制需要进行调整，以处理动态负载平衡和粒度控制。需要采用技术来动态搜索任务，并避免对小计算进行并行化。此外，垂直和水平并行性需要在同一系统中共存，并且在执行不同程序甚至单个程序时，可能需要交替使用这两种并行性。 #### 3. 利用ASP中的垂直并行性 在推导答案集的过程中，文字的替代选择（图1中的`choose_literal`）是独立的，可以同时进行探索。每个线程都可能导致一个不同的答案集，因此垂直并行性可以并行计算不同的答案集。 我们设想的垂直并行ASP引擎的架构基于多个ASP引擎（代理）的使用，这些代理同时探索ASP计算生成的搜索树，特别是由`choose_literal`过程执行生成节点的搜索树。每个代理探索树的一个不同分支，空闲代理可以获取其他代理生成的未探索替代方案。 这个架构设计的主要问题是提供有效的机制来支持代理之间未探索替代方案的共享。树的每个节点`P`都与一个部分答案集`B(P)`相关联，即节点`P`之前的分支部分计算得到的部分答案集。从节点`P`获取未探索替代方案的代理需要通过扩展`B(P)`和节点`P`中`choose_literal`选择的文字来继续执行。 由于ASP计算可能不平衡且不规则，我们需要采用动态调度方案。在运行时，空闲代理在系统中导航以搜索可用任务。因此，可用任务在代理之间的划分是动态进行的，由空闲代理发起。这就解释了为什么选择设计不同的代理能够遍历搜索树的共享表示以获取未探索替代方案。 #### 4. 系统实现概述 系统被组织为一组代理，它们合作计算程序的答案集。每个代理是一个独立的ASP引擎，拥有一组用于计算答案集的私有数据结构。此外，还引入了一些全局数据结构，供所有代理访问，以支持代理之间的合作。这种系统结构意味着我们首先依赖共享内存架构。 不同的代理