pHP-F支持多范例并行计算的并行编译技术

1、 计 算 机 学 报 图 整理 后 的 存 储 形式 主 程 序 中 数组 的 存 储 形 式 上 豢 整理后的形式： 数 组 组 数 图 结点 上的数据存储和整理过程 全局与 局部信 息 的交换 调 用 算模 型 的 外 部过 程 时 ， 计 如 ， 外部过 程之 间存 在显式 的通 信 ， 常 通 计 全局 数组 形状 ；包括数 组 各维 的上 下界 、 步长 、 分 布方 式等 处理 器 信息 算模型程序的编写者， 自己进行数据分布的， 是 而当 进行 调 用时 ， 局数据 及数 据 的 分布情 况 是 由 全 主程 序分 布 好 了的 因此 必 须 实现 全 局 信息 和 局部 信息

2、的交 换 ， 使 外部 过 程 了解 数 组 的 全 局和 局部分 布情况 ， 才能 正确 实现 外 部过 程 的通信 ， 完成 计算 实现全局和局部信息的交换 ， 有两种方式 ； 一 种是 传递 参数 数组 的分布 状况 分布数 组描述 子 （ ， ） ，一 种 是 传 递 参数 数组的 首址 处 理器 维 数 ：多维 处理 器组 在运 行 支持 中也 被 拉 平 成 一 维 ， 个 处 理 器 被 赋于 一 个 全 局 唯 一 的 每 编号 ； 处理器形 状 ： 括处理 器组 备维 大 小 、 长等 包 步 通过 实现 全 局和 局部 的 信 息交换 有 两 种 是 实现 编 译 器 的重

3、 要 数 据 结 构 ， 实 际上 对分 布 数组 的描 述 是 网络 并行 计 算 必 不可 少 的 环 节 在采 用 运 行 支 持 策 略 的 编 译 器 中， 以句 柄 的形 式 存在 并 且构 成 了编 译 和 运 行 支 持 的桥梁 ， 姬 常 包括 如下信 息 ： 方式 ， 一种是 句柄 局部调用支持库 的方法， 种是 传递 数组 的方 法 句 柄 局部 调用支 持库 的方 法 这种方式是 句 柄 传 递 给 外 部 过 程 ， 部 外 过 程 通 过 句 柄 以及 提 供 的外 部过 程调 用支持库得到全局信息和局部信息， 实现对局部数 据 的遍 历 这种 方式 如 图 所示

4、一 数组 基本 信 息 数组维 数在运 行 支持 中 ， 多维 数组 被拉平 用 一 句 柄 主 程序 算 模 计 型 的外 部 过程 （ ， ， 维 数组表 示 ； 元素类型 ； 直接作用于所有运算操作和空间分配 ； 局部数组基 址 ： 源 程序仅 涉 及逻辑 全局数 组， 对数组元素 的访 问必须通 过本地 物理地址进行 编 译 运 行 支 持 系 统 （ ， 等 ） 磐） 底 层通信支持 （ ， ） 图 调用 原 理 期 胡长军等 ： 支持 多范倒并行计算 的并行编译技术 这种 方式 实现 的关键 是局 部调用 支持 库 函数的 确 定 和实 现问 题 应提 供 足够 的函数 使 得 外

5、部 过 它 一 ， ） 返 回数 组 某 （ ， ： 维 在给定 处理器 上 的块数 上界 有 了这 些 函 数 ， 部 过 程 的 编 写 者 就 可 以在 外 程编写者 以 句柄为参 数， 能够查询处理器组 的形 式、 组 分 布、 齐 等全 局 信 息 ， 数 对 以及 各 结点 上 的数据 元 素个 数 、 下 界 、 上 跳步 等 局部 信 息 ， 能 方 并 便 地遍 历 局部 数组 ， 实现 全 局 下标和 局 部 下标 的转 换 我们 在实现 对 外部过 程时 ， 确定 了如 下 函数 ： 主 程序 给 定 的 全 局 数 据 分 布 下 ， 自由 的 编 写 算模 型的 外部

6、 过程 了 于 一 些 计 对 难 以 处 理 的 非 规 则 问 题 ， 们 可 以 用 写 成 我 外部 过程 ， 通过 调 用解决这 些 问题 直 接 传递 数组 的方法 （）查询 类 函数 （ ， ） ， 并行程序库是并行计算软件的宝贵资源， 实现 对典 型并 行 算 法 库 的调 用 ， 于 提 高 的 对 计算 能力 ， 并行 软件 的重 用具有 积极 意 义 多可扩 许 展并 行算 法库 （ 等都带有 自己的通 如 ） 信 函数库 和 格式 ， 因此 ， 调 用 时要 为算 法库 生成 信 息 是 一 个 典 型 的 线 性 代 数 求 解 的 可 扩 展并 行 算法 库 ， 它

7、是 在 的 基 础 上 发 展而 来 得 ， 串行 语 言 调用 要 求 调用 者 负责 将 数据 分 布到 各 结 点 上 去 ， 了方 便程 序 员 ， 为 这 一 操 作 是 在 全 局 程 序 中 完 成 的 ， 法 是 通 过 方 函 数得 到处 理 器 的行 列 信 息 ， 在全 局 （ ） ， ） ， ， （ 用来 获得 数组 的全局对 齐 、 布 、 板 的信 息 分 模 （ ， ） ）， （ 用来 获取全 局 数组 的大小和形 状 （）转 换类 函数 （ ， ， ） ， ， ， ） （ 用来确定 逻辑处理 器与 物理 处理器的相互对应 ， ， ） （ ， ， （ ， ， ，

8、） ， 用来 实现全 局 下标 和局 部 下标的转 换 （）局部 数据 的遍历类 函数 （ ： 回本结 点的处理 器号 ）返 （ ： 回 总 的 处 理 器 ） 返 个 数 程 序 中通 过 判别 不 同 处 理 器 号 执行 不 同 赋 值 语 句 实 现 数据 分 布 要求 程 序 自己计 算 局部 信 息而 这 这 些 在 编译 器 中是 自动 完 成 的 ， 也 是 这 调 用 的意义 所 在 和许 多 典型 的并 行 算 法库 一 样 ， 也 带 有 自 己的通 信 支 持 系统 ， 且有 自己的 并 格式 ， 它 们 的调 用要 求 对 编 译 器按 照外 部 过 程 的 要 求

9、填写 好 并 ， 将 数 组首 址 传 给 外 部 过 程 的 信 息是 以数组形 式 描 述 的 ， 内容 如表 示 所 表 的 ， ）返 回数组 每一 （ ， ： 维 在给定 处理器 上 的块数 ， ） 返 回 数 组 某 （ ， ： 一 维在 给定 处理器 上 的块数 下界 在 语 句 执 行前 ， 译器 要 负责 填 写这些 信 编 息 ， 了 两 项外 ， 除 ， 其它 各项信息 很容 易得到 ， 两项的信息和分布形式密切相关 ： 设实参为 ， ， ， 处理 器个 数 为 则 当 为 分 布 时 ， ， ， 行 列 的分 布 单 位 分 别 为 当 为 ， ； 布 时 ， 分 行列分

10、 布单 位分 别填 写为 值 得 指 出的 是 ， 然 的 数据 分 布 虽 形式 （ 涵 盖 了 的 ） ， 计 算 机 学 报 两 种形 式 ， 是 由于 但 中有 对 齐模 板 的 存 在 在 调 用前 ， 然 需要 判 断形 参 和 实参 的分 布形 式 是 否 仍 一 （ ， “ ） “ （ ， 定义 一个和 ） 同形 的数组 用来 动态计算 和存放各维的大小 （ （ ）（ ， ） ） （ （ ） ） 致 要时进 行参 数 的重分 布 必 调 用 型 的 外部 过 程 时 ， 给 每个 模 传 数 组参数 的上下界 问题 结点 上 行 的外 部过 程 的参 数 ， 执 是分 布 在每

11、 一 （ ： 指定 它为 传递方式 ， ） 将各维 长度 传 给 外 部 过 程 的 整 型 形 参 个 结点 上 的全 局数 组 片 段 而局 部 数组 的上 下界 与全 局数 组 的 界、 理 器个 数 、 布方 式 、 用 参数 处 分 调 等 相关 是难 以静 态计算 的 ， 且各 结 点上的 上下 界 并 也 可 能 不 同在 主程 序 中说 明 外 部过 程 时 ， 可 以采 用僭 取 形数 组说 明方 式 回避 这 一 问题 ， 在如 下 倒 程 中 ， 明的形 参 数 组 说 就是 僭 取 形 数 组 ， 的 它 语 义是 上下 界取过 程调 用时 实参 的上 下界 （ ， ）

12、 相应 的外 部过 程头应 写为 ， ） 的值通过 （ 传递方 式 由 形参获得 （ ） 静态定义和僭取形实 参相 对 应 的 数组 ， ￥ （ ， ） 实例 与结论 外部 过 程 调 用 的 编 译 处理 技 术 已在 我 们 的 编 译 器 中得 到 成 功 实 现 ， 用 利 实 现 了对 和 行 的 ， 执 行 的 执 、 行算 法 库 的调用 ， 于 并 对 一 ￥ ， （ “ ” “ ） ） （， （ ， （ 一 （ ） ， ） ） 些通 信 复 杂 ， 实 现 不 易取 得 高 性 能 的 问 题 ， 采用 外 部过 程 调用 的 方法 取 得 了很 好 的效 果 ， 通过 外部

13、 过程 调 用 ， 实现 了 对 一些典 型 并 行算 法 库 的 也 但 是 ， 行 的外 部过 程 一 个 执 是 重用 下面 实例 是一个 调 用 实现 过程 ， 它不 支持 僭取 形数 组 的说 明形 式 ， 不支 也 持 动 态数 组 ， 以在 外部 过 程 中 必须静 态 显式声 明 所 维 的 上 下界 么这 个 上 下界 的值 怎样 取 呢 ？ 各 那 我们采 用如 下做法 进行 处理 ： （ ）增 加一 个 和 僭 取 形 数 组 同形 的形 参 ， 指 并 矩 阵转置 的 计算 实例 ， 例 验 证 了 不同 的 参数 传递 该 方 式 、 存 转 换 方 式 、 下 界

14、处理 等 技 术 ， 外 部 内 上 其 过程 中也使 用 了我 们设 计 的局 部 支持 函 数 实 例 运 行 正 确 ， 证 了 我 们 编 译 技 术 的 正 该 验 确性 定其 传递方 式 “ ” 由编 译 器生 成 ， 态计算 出 ， 动 每 一 维 的 局 部 大 小 的 代 码 ， 记 录 在 该 参 数 中 并 “ 例 调用 求矩 阵 的转置 传递 方 式 的含 义是 将 数 组各 维值 赋给 相 应 ” （）程序 员 定 义 外部 过 程 时 ， 负责 定 义各 维 大 ： （ ） ： ： （ ： ） ： （ ， ： ） 的整型数 小的形 式参 数 （ 型 数）并 用 此

15、参 数 定 义和 主程 序 整 ， 中的僭取形 数 组形参 相对 应 （ ）编译 器 负责 参数 的传递 按照这 一 思想 ， 上面 的过 程应 写 成如 下形式 ： 这 ￥ （ ， ） ￥ （ ， ） ￥ （ ， × （ × ） ！ ￥ （ （ ） ，） 样既解决 了参 数 传递 的问题 ， 又和 规 范的基本 思想一致 （ ， ） （ ， ） 调 用一个 模式 执行 的外部过程 （： ） ： （ 一 ） （ ： ） ： ， ！ ￥ （ ） ￥ ， 的大 小在运行 时 有实参 大 小确定 实参 将 的首 地址 传给形 参 ， 传递 前将 数组 存储 方式 期 胡长军 等

16、； 支 持多范例并 行计 算的并 行编译技术 转 变 为 形 式 ， （ ， ） （ ：， ） （ ） ： ： 加速 比 ， 个 处理 器时 加速 比大 于 且 非常 稳 定 ， 而 当 处 理 器 个 数 为 时 ， 加速 比接 近 可 扩 展 性 很 ， 好， 其效 率 达到 ， 是 非常理 想 的 这 图 是 两 类程 序 的加速 比 的对 比， 该 图 可 以 从 看 出， 对 于该 问 题 的 加 速 比还 是 可 以接 受 的传递方式 为传 数组 的形状 ， 即编 译器 动 态 确 定 各 维 太 小 ， ： ， ） （ ） （ ）： ： 的， 但采 用调 用 的方法 ， 增加 了

17、一些 编程 的复 杂性 ， 但是换 取 的加速 比提 高还 是可 观 的 对 于 数组传 的句柄 ￥ （ ， ） ： 。 ： ， 越 馏 曩 ：， ： 一 （ × 十 （一 ） （ ） ） 一 ， （ ， ） 一 ） ， ， ， ） （ 问题 规 模 图 时 和 一 调 用 求 解 问题 的 加 速 比 对 照 表 【 口， ） ， 一 实现 以 为 核 心的 多范例 并行计 算 ， 仅 可 不 以 弥补 数 据并 行本 身 的 一些 缺 点 ， 大提 高 并行 计 大 算 的 应 用能力 ， 且对 于提 高大 型 并 行 系统 的 开发 而 效率 都有 很大 意义 究和应 用表 明

18、 ， 研 通过 编译 技术 为程序 员提 供 语言级 的多 范例 并行 系统开 发手段 是 实 现多 范例 并 行计 算 的有效 途 径 一步 将在 此 基 下 础上 ， 深入 研 究不 同范 例 的并 行 类库 和 并 行构 件 的 构筑 等 并行 软 件工 程 问 题 ， 在更 高 层 次上 支 持不 同 ， “ ，）， 例 调 用 ， 求 解 问题 用 数 据 并行 的方 法 求 解 问题 涉及 的 接点之 间的通 信量 较大 ， 许多 的 均 将 其包 含之 中 ， 以验证 编译 器 的处理 能力 是 由 但 于 问题 本身 的特 点 ， 依靠 编 译器 取得高教 率 是 困难 的 ， 是 如果 采 用 但 进 行 数 据分 布 而通 过 范例并行计算模式的集成 参 考 文 献 十 过 程 由程 序 员 自己处 理通 信 问题 ， 果 效 又如何 呢 ？ 通过 该 实例验证 实现技术 的