知识表示层面的并行性及逻辑编程并行架构解析

### 知识表示层面的并行性及逻辑编程并行架构解析 #### 1. 知识表示层面的并行性 在系统中，为了增强并行性，知识的分布式表示是较为优选的方式。例如，Petri网就是一种结构模型，其中每个前件和后件子句由库所表示，前件和后件子句之间的“如果 - 那么”关系由变迁表示。通过这种表示方式，一个由库所表示的子句可以被多个规则共享。将知识片段分布在物理单元（这里指库所和变迁）上，可以提高系统的容错程度。除了Petri网，其他用于知识表示和推理的连接主义方法还包括神经网络、框架、语义网络等。 #### 2. 产生式系统中的并行性 产生式系统由一组规则、一个或多个工作内存以及一个用于操作和控制规则触发顺序的推理引擎组成。通过同时触发多个规则，可以提高产生式系统的效率。然而，如果第二条规则的前件和第一条规则的后件有共同项，那么这两条规则处于流水线关系，不应并行触发。一个常见的问题是如何选择可以同时触发的规则。一种简单直观的方案是允许那些在顺序触发控制下能产生相同推理结果的规则并行执行。为了正式确定可同时触发的规则，使用以下定义： 设 $L_i$ 和 $R_i$ 分别表示产生式规则 $PR_i$ 的前件和后件，并且令 $K_i = L_i ∩ R_i$。 - **定义22.1**：如果规则 $PR_1$ 的后件与规则 $PR_2$ 触发后添加到数据库中的元素有共同元素，即 $R_1 ∩ (R_2 - K_2) ≠ ∅$，则称规则 $PR_1$ 输出依赖于规则 $PR_2$。 - **定义22.2**：如果规则 $PR_1$ 的前件与规则 $PR_2$ 触发后消除的数据元素部分有共同元素，即 $L_1 ∩ (L_2 – K_2) ≠ ∅$，则称规则 $PR_1$ 输入依赖于规则 $PR_2$。 - **定义22.3**：如果两条规则 $PR_1$ 和 $PR_2$ 的持久部分有共同元素，即 $K_1 ∩ K_2 ≠ ∅$，则称一条规则与另一条规则接口依赖。 - **定义22.4**：如果规则 $PR_1$ 的前件与规则 $PR_2$ 触发后添加到数据库中的元素有共同元素，即 $L_1 ∩ (R_2 - K_2) ≠ ∅$，则称规则 $PR_1$ 输入 - 输出依赖于规则 $PR_2$。 - **定义22.5**：如果规则 $PR_1$ 的后件与规则 $PR_2$ 触发后消除的数据元素有共同元素，即 $R_1 ∩ (L_2 - K_2) ≠ ∅$，则称规则 $PR_1$ 输出 - 输入依赖于规则 $PR_2$。 - **定义22.6**：如果两条规则 $PR_1$ 和 $PR_2$ 在两个方向上既不是输入依赖也不是输出 - 输入依赖，则称它们是兼容的。 - **定义22.7**：如果规则是兼容的，那么规则 $PR_1$ 接着 $PR_2$ 触发或反之，与 $PR_1$ 和 $PR_2$ 同时触发，从数据库的变化角度来看是等价的。 产生式系统中可同时触发的规则列表可以根据定义22.7，借助一个称为并行矩阵的矩阵轻松获得。在一个有 $n$ 条规则的产生式系统中，一个 $(n x n)$ 维的二进制方阵 $P$ 称为并行矩阵，其中： $p_{ij} = 0$，当规则 $PR_i$ 和规则 $PR_j$ 兼容时； $p_{ij} = 1$，否则。 通过检查 $P$ 矩阵的以下性质，可以轻松确定最大的兼容规则集：当 $p_{ij} = p_{ji} = 0$ 时，规则 $PR_i$ 和 $PR_j$ 是兼容的。 例如，考虑一个有6条规则的产生式系统，其并行矩阵 $P$ 如下： ```plaintext 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 ``` 根据矩阵的性质，可以确定以下兼容规则集： - $S_1 = \{ PR_3, PR_4, PR_6\}$ - $S_2 = \{ PR_1, PR_2, PR_4, PR_6\}$ - $S_3 = \{ PR_1, PR_5\}$ 为了高效执行基于规则的系统，一组兼容规则中的元素应该映射到不同的处理元素上。如果没有将兼容规则映射到不同的处理元素，可能会导致并行性的潜在损失。在将规则映射到处理元素时，还必须考虑处理元素之间的通信开销。当两条规则是输入依赖或输入 - 输出依赖时，它们必须映射到地理位置相近的处理元素上，从而减少通信时间。 #### 3. 逻辑程序中的并行性 逻辑程序，特别是PROLOG，由于其固有的表示和推理形式，包含四种不同类型的并行性： - **AND并行性**：在一个逻辑程序中，如果一个子句的主体由多个谓词（也称为AND子句）组成，这些谓词在归结过程中可以与其他子句的头部进行合一。通常，AND子句的归结是顺序执行的。然而，在有足够计算资源的情况下，这些归结可以并发执行，这种并行性通常称为AND并行性，它是执行树中AND子树的并行遍历。例如，考虑以下程序： ```plaintext 1. Parent ( Mo, Fa, X) ← Father (Fa, X), Mother (Mo, X). 2. Mother (jaya, tom) ← 3. Mother (ipsa, bil) ← 4. Father (asit, tom) ← 5. Father (amit, bil) ← ``` 查询：$← Parent (Mo, Fa, bil)$ 如果执行树的AND子树并行执行，产生的合一替换有时可能会冲突，这通常称为绑定冲突。例如，在以下逻辑程序中： ```plaintext 1. F(X) ← A (X), B (X). 2. A (1) ← 3. B (2) ← ``` 第一个子句主体中的文字 $A(X)$ 和 $B(X)$ 可以分别与第二个和第三个子句的头部同时进行归结。然而，绑定变量 $X$ 取值为 $\{1 / X, 2 / X\}$，这是冲突的。在AND并行性中，如果允许包含共享变量的目标/子目标独立并行地进行归结，通常称为无限制AND并行性。为了正确回答查询，需要对共享变量进行某种同步，并从变量绑定集中进行过滤。由于实现这种方案会引入相当大的运行时开销，因此只有当变量绑定无冲突时，才允许进行AND并行性，这种AND并行性称为受限AND并行性。为了检测变量绑定的无冲突性，使用程序注释来表示哪些目标/子目标产生或消费变量值。 - **OR并行性**：在顺序PROLOG程序中，子句主体中的每个文字在归结步骤中按顺序与其他子句的头部进行合一。例如，考虑以下程序： ```plaintext 1. main ← A (X), P(X). 2. A(1) ← b, c, d. 3. A(2) ← e, f, g. 4. A (3) ← h, i. 5. P (3) ← p, q. ``` 为了满足目标 `main`，首先尝试将第一个子目标 $A(x)$ 与 $A(1)$ 进行合一，设置 $X = 1$ 后，开始在其他子句的头部搜索 $P(1)$，但未找到。然后对 $X = 2$ 重复相同的过程，同样未找到 $P(2)$。最后，通过将 $A(X)$ 和 $P (X)$ 分别与最后