启发式算法与在线式解析

1、 本文由0q8u0yzm1b贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第 卷 第 期 年 月 信 息 工 程 大 学 学 报 启 发 式 算 法 与在 线 式 解 析 罗 颖 ， 肖梓 祥 （ 息 工 程 大学 信息 工 程 学 院 ， 南 郑 州 ， 信 河 ） 摘 要 ： 对在 线 式芯 片解析 方法 中数据 的特 点 ， 针 分析 了经 典逻 辑综 合算 法 的不适 用 性和启 发 式 算 法 的可行性 。 同 时， 对逻 辑综 合软 件 实现过 程 中要解 决 的问题进 行 了分 析。 关 键 词 ： 线 式解 析 ； 发 式算 法 ；

2、 辑综 合软 件 在 启 逻 中图 分类 号 ： 文献 标识 码 ： 文 章编 号 ： ） （ ， （ ， ， ） ， ： ： ； ； 和 启发式 算 法两类 。 引 言 在 线 式 解 析法 是 在 脱 机式 解 析 法遇 到 极 大 的 困难 下提 出 的。在脱 机式 解析 法 中 ， 明芯 片需 从 不 设 备上 取下 来插 到一 个专 门的硬件 平 台上 ， 输 入 从 经典 逻辑 综合 算法 分析 经 典 的逻辑综 合算 法 是先 求 出质蕴 涵项 ， 再求 最 小覆盖 。常用 的算 法有 ： 进 的 算 法 、 义 改 广 相 容算 法和 锐积 法等 。 以下结 合这 种算 法对

3、“ 在 线 式” 集到 的数 据进 行逻 辑综 合处 理时 的适 用性 采 做 简单 分析 。 改进 的 算 法 端 施加 激励 ， 输 出端 收集 数 据 ， 集 到 的 数 据 与 从 采 芯 片输 入 端 施 加 的激 励 相 关 ， 有 连 续 性 和 唯 一 具 性， 而且是 芯片 的工 作全 集 。该方 法采 集 和处理 的 数据 量随着 不 明芯 片 引脚数 的增 加而 成指 数增 长 。 该 算 法是 将 数 值最 小 的最 小 项 和数 值 最 大 的 最 小项相 合并 ， 到 覆盖 函数 最 大 的 多 维体 ， 得 目的 是 将尽 可能 多 的 （ 点 与 或 ） 点 相

4、合 并 ， 从 而得 到最简 的质 蕴涵 项集 合 。 该算 法 不受 数据 离散性 的影 响 ， 但综 合 过程 中 在 这种 情况 下 ， 大规 模 引脚数 的芯 片解 析几 乎不 可 能 。在“ 线式 ” ， 片 不从 设 备 上 取 下 来 ， 是 在 中 芯 而 采 用逻 辑分 析仪 实 时 采 集 芯 片在 目标 系统 中的 工 作 数据 ， 且对 其 分 析 处理 ， 据采 集 过 程 与 目标 并 数 系统 的工 作状 态相关 ， 集到 的数 据是 芯 片的 工作 采 集 ， 有 随机性 、 具 离散 性 和非 全集 等特点 。 必 须得 到全 部 的 点 集合 和 点集 合

5、， 即必 须 是 数据 全集 ， 则 综 合 出来 的质 蕴 涵 项 就 会 出错 。 否 因此 ， 改进 的 算 法 不适 合 “ 线 式 ” 的数 据 在 中 处理。 启 发 式 算 法 与 在 线 式 解 析 目前 国 内外 采用 的逻 辑综 合 算 法有 经典 算 法 收稿 日期 ： 广 义相 容算 法 广 义相 容算 法综 合数 据 的特 点是 ： 从数 据集 的 某 一端 元 素不 同的蕴 涵项 开 始合 并 ， 后逐 次 与其 然 作者简介： 罗颖 （一） 女 ， 南 淮 阳 人 ， 息 工 程 大学 硕 士 研 究 生 ， 究 方 向 为 数 字 系统 设 计 自动化 。 ，

6、河 信 研 第 期 罗 颖 等 ： 发 式 算 法 与在 线 式 解 析 启 它 原始蕴 涵项 进行 比较 ， 同 时将 能合并 的蕴 涵项 并 个 芯片 内的 多输 出函 数解耦 成单 输 出 函数 ， 即综 合 合并 ， 复处 理 ， 至 不能进 一 步处理 ， 求得 全部 反 直 便 质 蕴涵项 。 出每一 条 输 出腿 的 质 蕴 涵 项 集 合 ， 求 出 最 小 覆 并 盖 。 因此 ， 们就 必 须 根 据采 集 到 的 数据 ， 行 芯 我 进 广 义相 容算 法在 对数 据的处 理过 程 中 ， 受数 不 据 离散性 的影 响 ， 每 次都 要 将 其余 但 点 集合 和 点

7、集 合进 行 比较 ， 而 导 致 时 间复 杂 度 加 大 ， 从 并且 中间过程 的 点 集 合 和 点 集 合 要 一 直 保 留到算 法结 束 ， 又导 致 空 间 复 杂 度 变大 ， 以在 所 进 行大规 模 芯片 的数 据处 理时 ， 用该 算 法会使 解 析 片输 入输 出 引脚信 息 的相关 性分 析 ， 出 相关 的输 找 入输 出信息 ， 而 确 定 出 我 们最 终 要 综 合 的数 据 。 从 这样 ， 就有 了两 类 数 据 格 式 ， 们 定 义 了 如下 数 据 我 结构 。 解耦 前 的数据 结构 在“ 在线式 ” 析 中 ， 解 采用 逻 辑分 析仪来 实

8、时采 集 芯片 的工作 集 ， 是这 些数 据 具有很 大 的离散 性 但 和重 复性 ， 了 满 足 启 发 式 算 法 对 数 据 处 理 的 要 为 的时空效 率 不堪 忍 受 。 而在 线 式 解 析 法 是 针对 大 规 模多腿 芯 片而研 制 的 ， 以该 算法 同样 不适 用 。 所 锐积 法 该算 法 是一个 求 补 的过程 ， 目的是从 数据 全集 中逐 一去 掉 或 顶 点 ， 而将 数据 全 集 分 （ ） 从 求 ， 们首 先对 数 据 进 行 冗余 处 理 ， 我 然后 再 进 行 数 据格 式化 的转 化 ， 即将 数据 以状 态真值 表 的形式 存 放 到存储 器

9、 中 。其 中 ， 对芯 片状 态真值 表 的存储 我 采用 字 节存 储 ， 个 引脚 的 信息 占一 位 ， 满 每 不 一 裂 成多个 质蕴 涵 项 。 锐 积运 算 是 通 过 产 生 的 中 间 结 果 与剩 余 的多 维体 集合 继续 进行综 合 化简 ， 是 但 在线 式解 析 法 中采集 的数据 离 散度 大 ， 以中间处 所 理 过程 中产 生 的中间 结果 迅猛 增长 ， 由于锐 积 运 再 个 字 节的用 填充 。具 体格 式 如图 。 有效输入变量 充 位 填 一 状态输入变量 。 输出变量 算 是最 复杂 的一 种综 合运算 ， 以采用 锐积 法处理 所 离 散度 大

10、的 数据 会造 成解 析过 程时 间太 长 ， 至使 甚 填 充 位 按 字节存储 一 按 字节存储 综 合处理 成 为不 可能 。 启 发 式算 法基 本思 想 针 对在线 式解 析 法 中数据 的特点 ， 经典 的逻辑 图 引 脚 信 息 存 储 结 构 解耦 后 的数据 结构 综 合算 法 已不适 用 ， 过实 践 中的 综 合 比较 ， 们 经 我 采用 启发 式算 法 。其 中 最 具 有 代表 性 ， 它 求取 逻辑 函数 厂覆 盖 的特 点 是 把 一 个 给 定 的 定 义 在一 个 维 布 尔空 间 的 个输 出函数 的逻 辑 函数 厂的 覆 盖 ， ， ， 换 成 厂 ，

11、， 转 的一个 含多 维体 数 较 少 的质 覆 盖 我 们 称 此 过 ， 由 引脚信息 的存 储结 构 我们 知道 ， 是 由 正 于启 发式 算 法是针 对 大规模 芯 片的解 析 而提 出的 ， 其 中包括 若 干个 输 出 引脚 ， 此 ， 具 体实 现 过 程 因 在 中 ， 了方 便逻 辑 综 合 ， 们 将 具 有 多 个 输 出 函数 为 我 的不 明芯片解 耦 ， 即将 多输 出 函数解 耦为 单输 出 函 数， 解耦 后 的数据 存储 格式 如 图 。 程 为扩 展过 程 。此过 程包 含两 个运 算 ， 一是 对每 个 用 包 含它 的质 蕴 涵项 （ “ ） 替 换

12、； “ 来 二 是将 中被 所包 含 的 多维 体 删 去 。这样 ， 通 过 扩展可 期 望得 到一 个含 较少 多维 体 的覆盖 。 启 发 式算 法是 针 对 某个 选 定 的 多 维体 进 行 扩 一 ： ： ： ！ ： ！ ！ ： ！ ！ ！ ： ！ 。 按字节存储 图 解耦 后 的输 出 引脚 状 态 真 值 表 格 式 展， 其最 终 产生 的近 似最小 覆 盖 的大小 与分 析系 统 所 选定 的待 扩展 的 多维 体有关 ， 定原 则 由算法 实 选 现 人员 自己确 定 。在 运 算 过 程 中 随着 多维 体 的 不 断 扩展 ， 其所 产 生 的 中 间结 果 逐 渐

13、减 少 ， 而 使 算 从 封 锁 矩 阵 和 覆 盖 矩 阵 由于多 输 出 函数 的 解 耦 ， 于 每 一个 输 出 ， 对 我 们 都有 一张 状 态 真值 表 与 之 对 应 。在 状 态 真值 表 法 的空 间复 杂 度进一 步 降低 ， 因而 该算 法适 合处 理 离 散度 大 的数据 。 逻辑 综合 软件 实现 过程 中需解 决的 问题 多输 出函数 的解耦 中 ， 含有 仅 点集 合 和 点集 合 ， 不考 虑 而 集 合 。我们 知道 ， 启发 式算 法 实质 上就是 对 （ 或 点集 合 的各项 进 行 逐 位提 升 ， 到 质 蕴 涵项 ， ） 得 并 从 中直接 求得

14、 近似 最小 覆 盖 。所 以 ， 在具 体程 序 实 现过 程 中 ， 必须 定 义封 锁矩 阵 和覆 盖 矩 阵 ， 经 过 比较 ， 我们 决定 采用 适合 大规 模芯 片解 析 的启 发式算 法 。依据 逻辑 综合 的理论 ， 逻辑 综合 算 使 得扩 展过 程变 得简 单 ， 同时 降低算 法 的时空 复 杂 度 ， 能满足 大规 模引 脚芯 片的 解析 需求 。 更 法 的任务 是对 采集 到 的数 据进 行综 合 ， 将设 计在 一 信 息 工 程 大 学 学 报 正 封锁矩阵 我 们 知道 ， 任何 一多维 体 的扩展 都 不能是 任 意 后不 需要 再考 虑 ； 中删 去 此

15、 行 集 是 因 为 中 在 对应 的多 维体 一 定 不 能 被 所 蕴 涵 ， 因此 可 删 除 不作 考虑 。 正是 由于定 义 了封锁 矩 阵和覆 盖矩 阵 ， 的， 它受 到 一定 的约束 ， 即 与给 定 函数 厂的 点集合 之交 必 须 为 空 （ ） 否 则 ， 将 含有 厂的 集合 中的最 小 项 而 不成 为 厂的 蕴 涵 使得 启发 式算 法更 加 系统 和有效 。 项 。因此 ， 进 行 扩 展 时 ， 们 除 了需 用 给 定 在 我 结语 启 发 式 算 法 占用 空 间 小 ， 初 始 点 集 合 为 、 点集合 足 以及封锁 矩 阵 和覆盖 矩阵 占 用 的空

16、间之 和 ， 而且 随着 多维 体 的扩展 不 断消 去矩 阵 中的行 和列 ， 而 使 算 法 的 空 间 复杂 度 逐 渐 减 从 小 。 由于在线 式采 集 到的数 据都 是零 维体 ， 法不 算 点集合 外 ， 需 要 用 到 点 集 合 。而 封 锁 还 矩 阵 是 由 及 中 的所 有 多维 体 定 的 决 矩阵 ， 其每 一列 与 的一元 素对 应 ， 每一 行 与 中 一 多维 体对 应 ， 其元 素 由下 式 决定 ： ， 或 而 一 而 ， 【， 它 。 其 由封 锁矩 阵定 义可 以看 出 ， 义它 的最 大 目的 定 就是 当 扩 展 为 时避 免 了扩展 过 渡 。

17、覆 盖矩 阵 要求 对 多维体 进 行排 序 ， 是扩 展 的顺 序 不 同， 只 综 合 出来 的结果 也就 有所 不 同 ， 在 函数 功 能上 是完 但 全等 效 的。启 发式 算法 只与 器件 工作 集有关 ， 考 不 虑无关 项 集合 ， 不受 在线 式采 集 的数 据离散 性 的影 响， 能够满 足大规模 引 脚芯 片解析 的需 要 。 参考文献 ： ， 定 义 ： 为 中 待扩 展 的多 维 体 ， 设 以后 的 多维 体组 成集 合 ， 盖矩 阵 是 一个 由 及 决 覆 定的 阵， 矩 每一 列 与 的元 素 对应 ， 一行 每 与 中的 多维体 对应 。覆盖 矩 阵 的作 用 是 为 了 使 涵 中尽 可 能 多 的 其 它 多 维 体 。定 义 如 蕴 下： ， 而 或 而 ， ， 其它 。 借 助 于这 两个矩 阵 ， 在扩 展 过 程 中， 们 将 我 和 中各 列 的元 素分别 归 人提 升 集 和非 提 升集 。一旦 将某 一 列组 合 归人 非 提 升 集