发布网友 发布时间:2023-04-10 06:35
共1个回答
热心网友 时间:2023-09-14 07:46
1999 年 8 月 系统工程理论与实践 第 8 期 PD ES 信息管理的一种启发式算法 林 健, 毛晶莹 ( 北京航空航天大学管理学院, 北京 100083) 摘要 分析了并行离散事件仿真中同步信息的相关性, 并提出了对这些信息进行管理的一种启发式算 法, 该算法包括对信息的排序和分配. 最后用一个例子说明这种启发式算法. 关键词 并行离散事件仿真 PD ES; 同步信息; 启发式算法 A H euristic A lgo rithm fo r M essage M anagem en t in PD ES L I J ian, M AO J ingying N (T he M anagem en t Schoo l, B eijing U n iversity of A eronau tics & A stronau tics, B eijing 100083) Abstract T h is paper analyses the relation of synch ron ization m essages in parallel d iscrete even t si u lation. A heu ristic algo rithm u sed in m essage m anagem en t is then p resen ted, m w h ich includes m essage sche ling and m essage assignm en t. A case is detailed at the end to illu strate the heu ristic algo rithm. Keywords parallel d iscrete even t si u lation; synch ron ization m essages; heu ristic algo rithm m 1 引言 在 S I D (Single In struction and M u ltip le D ata) 并行结构中, 有 N 个处理器同步进行工作, 因而产生了调 M 度问题 [1, 2 ]. 调度是要决定每一个进程在哪个处理器上运行, 其目标通常是最小化并行算法总的执行时间和 所使用的处理器的数目. 基本上有两种处理器调度模型, 确定模型和随机模型. 在确定模型中, 任务之间的优先关系和各任务所 需的执行时间, 在进行调度之前是固定和已知的. 在随机模型中, 一个进程的执行时间是具有给定累积分布 函数的随机变量. 当一个进程正在处理器上运行时, 可能会遇到象中断那样的外部因素. 由于输入输出设备的*, 可能 需要对这种外部因素进行紧急服务. 如果正在运行的进程在它完成之前允许被中断, 然后再恢复运行, 那么 可以使用抢先 (p reem p tive) 调度方法. 如果在进程完成之前不允许被中断, 那么可以使用非抢先 ( non 2 re2 p 信息驱动的并行离散事件仿真是在 S I D 并行结构的基础上提出的. 在信息驱动的并行离散事件仿真 M 结构中, 信息的排序、 调度与分配是提高仿真效率的关键. 信息的排序、 调度与分配成为并行算法的主要任 务. 并行算法的研究一般有三种方法: 第一种方法是开发现有的串行算法中任何固有的并行性; 第二种方法 是发明一种新的并行算法; 第三种方法是修改一个已有的并行算法来解决一个类似的问题. 并行算法要达到仿真运行高效而准确的目的, 必须精确设计, 既要考虑有效利用并行结构, 又要保证执 行顺序正确. 本文在信息驱动的并行离散事件仿真结构中, 提出了一种启发式算法, 以信息为研究对象, 对 信息进行排序、 调度与分配, 合理地把信息分配到各个处理器中. α 收稿日期: 1998207209 资助项目: 国家自然科学基金项目 79670006 资助 em p tive) 调度方法. α ? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 第8期 PD ES 信息管理的一种启发式算法 11 2 同步信息的相关性分析 同步信息指的是具有相同优先级和时间标记的信息. 在并行离散系统中, 经常会出现一些同步信息, 即 多个信息具有相同的优先级和时间标记. 同步信息可分为两类: 一类是相关的同步信息; 另一类是不相关的 同步信息. 对于相关的同步信息, 由于信息之间有密切的相关性, 这些同步信息必须同时被处理. 如果这些 同步信息中的某些信息先被处理, 另一些信息后被处理, 就可能导致仿真结果不准确. 而不相关的同步信息 就没有这种*, 它们可以不同时接受处理. 在 PD ES 算法中, 对以上的两类同步信息要进行区分, 以便对这两类同步信息进行不同的调度与分配. 以前我们曾讨论过, 仿真系统中的信息可分为四类: 事件信息、 统计信息、 属性信息和状态信息 [3 ]. 同步信息 也同样包含这四类信息, 可以分两种情况来讨论同步信息的相关性: 一种情况是, 同步信息为同种类型的信 息; 另一种情况是, 同步信息为不同类型的信息. 先讨论同步信息为同种类型信息的情况. 如果同步信息都是事件信息, 则同步信息必定是相关的. 因 为单个事件信息会引起系统状态发生一次变化, 而多个事件同时发生也只引起系统状态发生一次变化. 如 果把同步事件信息串行化, 即不同时处理, 必定引起系统状态发生多次变化, 这与原来的事实不符. 而且在 每一次变化中, 有可能会影响同步事件信息中未处理的事件信息, 从而导致仿真结果不准确. 显然同步事件 信息是相关的, 必须同时接受处理. 如果同步信息都是统计信息, 其相关性取决于统计信息所统计的类别. 若同步统计信息所统计的是同一种统计值, 例如都是统计顾客在系统内的平均停留时间, 则其相关性很大. 因为同步统计只会产生一个统计结果, 而异步统计会产生多个统计结果, 虽然最终的统计值是正确的, 但异 步统计的过程中间产生的统计值有可能会影响仿真运行. 例如中间产生的系统内顾客平均停留时间超过了 某一规定值, 导致某些顾客不再排队等待, 这样就产生了新的事件信息. 而在同步统计中就不会出现这种情 况, 因而对这样的统计信息采用同步处理的方法. 若同步统计信息所统计的是不同的统计值, 则其相关性较 小, 可以采用异步处理的方法. 如果同步信息都是属性信息, 其相关性取决于属性信息是否是同一实体的属性信息. 如果是, 则其相关 性较大, 需要同时接受处理. 因为属性值的变化会引起系统状态的变化, 而同一实体的属性值之间相互关 联, 不同时处理可能会引起不必要的系统状态的变化. 如果同步属性信息不是同一实体的属性信息, 则其相 关性较小, 可以采用异步处理的方式. 如果同步信息都是状态信息, 则其相关性很大. 因为状态的变化通常会使原来条件不满足的事件满足 条件, 因而引起新的事件的发生. 同时处理几个状态信息, 系统的状态只变化一次, 而异步处理几个状态信 息, 系统的状态会变化多次, 在这些变化过程中, 可能会导致原本不该发生的事件因满足条件而发生, 这就使 得仿真结果失真. 所以对于同步状态信息的处理, 应该是同步的. 下面再讨论同步信息为不同类型信息的情况. 如果不同类型的同步信息中有事件信息, 则该事件信息 与其它类型的同步信息通常是相关的. 由于事件信息会引起实体的状态或属性发生变化, 从而引起系统状 态的变化, 有时还会引起统计值的变化, 因此事件信息的处理会影响其它的属性信息、 状态信息和统计信息. 反之也成立, 即其它三类信息的处理也会影响事件信息. 例如统计值的变化会导致某些事件的发生, 实体属 性以及系统状态的变化会引起新事件的发生. 如果同步信息中没有事件信息, 但有状态信息, 那么这些同步信息也是相关的. 因为实体属性的变化会 影响到系统的状态, 所以属性信息与状态信息密切相关. 而系统状态的变化会改变系统的某些统计数值, 因 此状态信息与统计信息也是相关的. 如果同步信息中只有属性信息和统计信息, 则这些同步信息不相关. 因为这两类信息的处理较独立, 不 会互相影响. 从以上的分析来看, 当同步信息为同种类型的信息时, 若其信息类型为事件信息或状态信息, 那么同步 信息相关; 若其信息类型为统计信息, 则统计相同统计值的同步统计信息相关, 而统计不同统计值的同步统 计信息不相关; 若其信息类型为属性信息, 则携带同一实体的属性的信息相关, 而携带不同实体的属性的信 ? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 12 系统工程理论与实践 1999 年 8 月 息不相关. 当同步信息为不同类型的信息时, 若同步信息中有事件信息, 则同步信息相关; 若同步信息中有 状态信息, 则同步信息也相关; 若同步信息中只有属性信息和统计信息, 则这两类信息互不相关. 3 信息的排序 在分析了同步信息的相关性之后, 下面研究进行 PD ES 信息管理的启发式方法. 算法的目标是使仿真 模型在 S I D 并行结构上总的执行时间最短, 且不考虑最小化处理器数目. 算法假设各种类型的信息的处 M 理时间是已知的, 但信息执行的先后顺序是未知的. 假设进程的运行采用非抢先的优先级调度方法, 即处理 器在处理信息时不允许被中断. 由于信息的处理不能违反因果关系, 我们规定信息必须严格地按先后顺序来执行. S I D 并行结构中的 M N 个处理器都有相同的结构和功能, 每个处理器中都有执行模块, 信息到达执行模块, 便驱动执行模块对信 息进行处理. PD ES 算法包括对信息的排序与分配, 本节先讨论信息的排序. 进行信息的排序要考虑的问题有信息的 分类和信息的优先级. 按信息的来源分类, 信息可分为内部信息和外部信息. 内部信息指的是仿真系统本 身产生的信息, 包括仿真开始时仿真模型给出的初始信息和仿真运行过程中产生的新信息. 外部信息指的 是用户交互信息. 在仿真过程中, 用户的交互行为会产生外部信息, 这些信息可以是更改仿真系统中的某些 参数, 也可以是要求仿真运行中断. 外部信息的优先级较高, 要求紧急中断的信息具有第一优先级, 而更改 参数等普通交互信息具有第二优先级. 同时规定内部信息具有第三优先级. 本文采用等待制排序规则, 即 信息到达时, 若所有处理器均被占用, 则该信息自动加入队列等待处理. 信息的排序规则设立如下: 1) 按信息的优先级进行排序, 优先级越高, 则信息的排列顺序越靠前; 2) 对同一优先级的信息, 按信息的时间标记 t 来排序 信息的 t 值越小, 则信息的排列顺序越靠前 . . 仿真过程中, 信息池中的信息就是按这个排序规则来排列的. 信息从信息池中出来, 以 F IFO 规则进行 传递, 最终到达 PD ES 算法. 信息在 PD ES 算法中的排列顺序与信息在信息池中的排列顺序相同. PD ES 算 法中的排序是对信息重新排序, 以确保信息的排列顺序正确. 这是因为仿真过程中有新信息产生, 而新信息 虽然后到达 PD ES 算法, 却有可能具有较高的优先级或较小的时间标记, 因而应排在队列靠前面的位置. 重 新排序较简单, 只需把新到达的信息按排序规则插入到已排好的队列中. 对于优先级不同或优先级相同而时间标记不同的信息, 就按上面的排序规则从前往后排列. 但对于优 先级与时间标记均相同的信息, 即同步信息, 它们应并列排在信息队中. 用 M {m 1 , m 2 , …, m s } 表示同步信息 集合, M 中有 s 个信息, 这 s 个信息的优先级相同. 用 t1 , t2 , …, ts 分别表示 m 1 , m 2 , …, m s 的时间标记, 则 t1 = 1 2 . . t2 = …= ts = t 按排序规则形成的信息队如图 1 所示 图中 i1, i2, …, ik 表示M , M , …, M 1 2 k k 同步信息集合 中的同步信息数量, i1, i2, …, ik Ε 1. 若 M , M , …, M 的优先级相同, 用 t , t , …, t 表示它们的时间标记, 则 t1 < t2 < …< tk. 1 2 k M k m k , m k , …, m k 1 2 ik 队尾 4 信息的分配 … … 信息的分配是 PD ES 算法的核心内容. 并行性的利用及仿真效率的 M M 2 1 m 2 , m 2 , …, m 22 1 2 i m 1 , m 1 , …, m 11 1 2 i 提高, 取决于信息的分配是否合理. 在介绍信息的分配步骤之前, 先说明 信息 M 接受分配的前提条件. 前提条件是, 信息 M 的优先级高于或等 队首 图 1 信息队 于系统内所有其它信息的优先级, 并且在优先级相同的信息中, M 的时间标记 t 最小. 前提条件是为了保证 信息的处理严格地按先后顺序来进行, 前面的假定中规定进程的运行采用非抢先调度方法, 即不允许中断, 所以在算法中要采用上面的保守策略. 再来说明处理器选择规则, 选择规则是为 M 中的 s 个信息选择处理 器. 已知信息 m 的类型, 尽可能为信息 m 选择与其信息类型相同的处理器, 这样必定能加快信息处理的速 度. 处理器的信息类型指的是处理器正在处理或刚处理完的信息的类型. 对于首次使用的处理器, 其信息 类型为任意. 处理器选择规则如下: ? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 第8期 PD ES 信息管理的一种启发式算法 13 信息选择信息类型相同的处理器, 并将 s 个信息 发送到所选的处理器; 2) 若 k < s , 判断 s 个同步信息是否相关: ① 若同步信息相关, 则将所有处理器按 tn 值 从小到大排列, 取一个尽可能小的 tm in , 使 k 1 Ε s, . k 1 表示 tn Φ tm in 的处理器数 在 k 1 个处理器中, 尽 理器; ② 若同步信息不相关, 则根据处理器的信息 闲的处理器, 直至将所有同步信息发送完毕. 信息的排序和分配可由图 2 来表示. 这就是 PD ES 启发式算法. 可能为每个信息选择信息类型相同的处理器, 然 后等待 tm in 时刻到达, 将 s 个信息发送到所选的处 类型选出 k 个信息, 尽可能为每个信息选择信息 类型相同的处理器, 将 k 个信息发送到所选的处 理器. 其余 s- k 个信息则等待, 当空闲处理器出 现时, 尽可能选信息类型一致的信息, 发送到空 用 P {P 1 , P 2 , …, P N } 表示并行机中的处理器 集合, 共有 N 个处理器. 在处理器 P 上分配信息 M 的步骤如下: 1) 信息 M 到来后重新排序, 形成信息队. 2) 若信息M 满足前提条件, 则转入下一步; 否则, 信息 M 回到信息队重新排序. 3 ) 计算 ? n = tn 1 接受处理的时刻, 即信息M 的时间标记. 4 ) C { P 1 , P 2 , …, P k , k Φ N } 表示 ? n ≤0 的处理器集 选择处理器, 直到 s 个信息都发送到所选的处理器. 合, D {P k+ 1 , P k+ 2 , …, P N } 表示 ? n> 0 的处理器集合. 5 ) 根据处理器选择规则, 为 M 集合中的每个信息 5 实例 下面用一个例子来说明 PD ES 启发式算法. 在一个 典型的并行机上进行仿真运行, 此并行机中的处理器数 为 3, 这三个处理器分别为 P 1 , P 2 和 P 3. 为便于说明, 本 例中给信息编了号. 假设系统中有十个信息, 这十个信 息分三个优先级, 分别用 1、、 来表示. 2 3 假设各类型信息的执行时间如下: 事件信息的执行 时间为 10, 状态信息和属性信息的执行时间为 8, 统计信 息的执行时间为 6. 每个处理器的时间标记 tn 初始值为 0, 在仿真过程中, tn 值为前一次所处理或正在处理的信 息的 tm 值与该信息的执行时间之和. 信息的类型、 优先 级及时间标记如表 1 所示. PD ES 启发式算法是这样进行的: 首先对所有到来的信息按排序规则进行排序, M 1 1 前面的信息. M 中只包含一个信息, 即 m 1 , 所以 s = 1, t = 0. M 从信息队出来, 到达前提条件. M ? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 1) 若 k Ε s , 在 k 个处理器中, 尽可能为每个 图 2 PD ES 启发式算法 tm , 其中: tn 表示第 n 个处理器最早可以开始处理信息的时刻; tm 表示信息 M 最早可 表 1 信息的类型、 优先级与时间标记 信息号 信息类型 信息优先级 时间标记 1 2 3 4 5 6 7 8 9 10 11 事件信息 属性信息 状态信息 事件信息 属性信息 事件信息 统计信息 属性信息 事件信息 事件信息 事件信息 3 3 3 3 3 3 3 3 3 2 3 0 2 4 10 10 10 20 20 24 26 28 1 为信息队中排在最 1 满足 14 系统工程理论与实践 1 1999 年 8 月 4 M , 此时 s= 3, t = 10. 计算 ? n: ? 1 = 10210= 0, ? 2 = 10 210 = 0, ? 3 = 12210 = 2, k = 2. 因为 k < s, 所以采用 4 m 4 选择 P 1 , 为 m 5 选择 P 2 , 为 m 6 选择 P 3. 等待 tm in = 12 到达, 把 m 4、 5 和 m 6 分别发送到 P 1、 2 和 P 3. m P 转入步骤 3, 计算 ? n. 计算结果是: ? 1 = ? 2 = ? 3 = 0, 所以 k = 3. 然后选择规则为 m 1 选择处 理器, 因为三个处理器都是首次使用的处理器, 它们的信息类型为任意, 所以任选一处理器 P 1. 最后将 m 1 发 前提条件, 把 M 送到 P 1. 十个信息的分配结果如图 3 所示. 图 3 信息的分配结果 m 2 和 m 3 的分配与 m 1 相似, m 2 被发送到 P 2 , m 3 被发送到 P 3. m 4、 5 和 m 6 为同步信息, 组成信息集合 m 选择规则中的规则 2 ). 分析这三个信息的相关性, m 4 与 m 6 均为事件信息, 它们是相关的, 而 m 5 为属性信 息, 属性信息与事件信息之间也相关, 所以 m 4、 5 和 m 6 均相关, 这三个信息必须同步接受处理. 取 tm in = m 12, 此时 k 1 = 3. P 1 的信息类型为事件信息, P 2 的信息类型为属性信息, P 3 的信息类型为状态信息, 所以为 5 5 m 7 与 m 8 也是同步信息, 组成信息集合 M , 此时 s= 2, t = 20. 计算 ? n: ? 1 = 22 - 20= 2, ? 2 = 20- 20= 0, ? 3 = 22- 20= 2, 所以 k = 1. 因为 k < s, 所以采用选择规则中的规则 2 ). 分析 m 7 与 m 8 的相关性, 它们分 别为统计信息和属性信息, 因此判断 m 7 与 m 8 不相关, 可以采用异步处理. 在 t= 20 时, 根据信息类型, 为 m 8 选择 P 2 , 先把 m 8 发送到 P 2 , 然后在 t= 22 时, P 1 与 P 3 处于 “空闲” 状态, 因为 m 7 与 P 1、 3 的信息类型均不相 P 同, 所以把 m 7 发送到其中任一处理器, 这里假设发送到 P 1. 在 m 9 接受处理之前, m 10 到达信息队. 由于 m 10 于 “空闲” , m 9 满足前提规则, 被发送到 P 2. m 11 按算法规则, 被发送到 P 1. 状态 的优先级比 m 9 的优先级高, 根据排序规则, m 10 排在 m 9 之前. 所以 m 10 被发送到 P 3. 在 t= 28 时, P 1 与 P 2 处 6 结论 调度与分配, 这是并行离散事件仿真结构中的 PD ES 启发式算法用于并行离散事件仿真中信息的排序、 核心内容. PD ES 算法的目标是最小化仿真运行总的执行时间, 有效利用并行性. 在本文所提出的 PD ES 启 发式算法中, 多个处理器的利用, 可以使非同步信息同时进行处理, 加快了仿真速度. 同时对同步信息的处 理较灵活, 相关的同步信息必须同时进行处理, 以保证仿真结果的准确性, 而不相关的同步信息可以不同时 进行处理, 以节省等待时间. 因此, 对于并行离散系统来说, PD ES 算法既加快了仿真速度, 又使仿真结果更 准确. 参考文献 [ 1 ] 黄铠, B riggs F A. 计算机结构与并行处理. 北京: 科学出版社, 1990 [ 2 ] 陈国良. 并行算法——排序和选择 合肥: 中国科学技术大学出版社, 1990 . 199 [ 3 ] 林健, 毛晶莹 一种新的串行离散事件仿真建模策略——信息驱动法 航空学报, 1998, 19 ( 2) : 195 . . ~ ? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.