选择网络延迟时间的一个新上界.pdf

1 9 9 0 g 2月 计算 机学报 第 2期 选择 网络延迟时间的一个新上界 沈 鸿 陈 目 良 中国科 学技术 大学计算 枉系 A NEW UPPER BoUND oF DELAY TI ME l N SELECTI o N NETW ORK S he n Hon g an d Che n Guo l i a ng un i v e r s i t y o l i e u e e a n d Te c h n o l o g y f j 4 Ab s h a c t T h r o u g h t r e e r e p r e s e n t a t i o n o f t h e r e c u r s i v e n e t wo r k a n d t h e c o m b i n a t o r i a l e n u me r a t i o n a n e w u p p e r b o u n d o i d e l a y t i me i n t h e m s e l e c t i o n e t wo r k 1 m 4 m l 0 g L l o g mJ l ogl og n m O 1og l ogl ogn wh e n m a n d 0 1 o g w h e n 2 m 4 m I t i s a n i mp r o v e me n t o r e r A C Ya o s b e s i r e s u l t 摘要毒 文通过将建 归网络 E 册 一 按 树彤展开 应 用组合计数方 法导 出 了 选择 网络 1 拼 和l g L 1 0 gmJ lo g log n 0 1 o g l o g log n 当 一 引 言 m 选择 网络是实现从 个数 输 人数 选 出 个最小数 输 出数 的 网络 在硬件上它可 由若干比较元件所构成 选择 网络的复杂度可 由两个指标来描述 延迟 时 阃 和比较元件数 目 随 着 v LS I技 术的进展 网络的延迟 时间越来越 引起人们的 重视 本文系国家 自熟科学基盎资助项目 拄一 8 5 2 1 7 2 本文中 l 均指 l o g t 本文 l 9 8 8 年 1月 2 9日收到 维普资讯 2 期 沈鸿等 选择 网络延 迟时 间的 一 个 新上 界 本文 通过将递归 网络 冒 m 按 树形展开 揭示 了网络内部的组合计数 规律 从而 导 出 了 选择 网络延迟时间的一个新上 界 改进 了 A C Y a o提出的上 界 二 已 有 的 结 果 一 个 m 选择 网络可 由图 1所示的四级 网络组成 其 中 r m 为包含所选 m 个最小 者的 子集 中元 素 个 数 显然 f m 一 r m 0 一 砘 l 撕 一 啦 1 此网络 的意 义 为 经 过 五 m 网络从 中选 出 f m 一 个包 含 m个最小 者的元素 再经过 E m 从 嘞 中选 出 撕 冒 l 从 1 圭 f 卅 I c m no c m c l l J m4 州 月 J J 图 1 选 择网络 的四 级组 我 冲 选 出 最后从 中选 出 m个最小 者 此时 啦应充分接近 m 网络E 2 m 是 由图 2所示的递归方 法所构成的 对于m一 1和 m 的两种边界情 形见 文献 1 图 2网络 五 埘 的 递归 构造 注 意经过虚线框 中的 一次并行 比较 形成两个子 集 MI N 和MAX 其 中 子 集 M A X 中 至 多 包 含 詈 J 个 属 于 所 选 m 个最小 者中的元素 由 l 可 知 f c m 一 r 1 詈 J l 号 J m f 詈 1 z m f 1 一 l 1 f l 一 r E l 的延迟 时间至 多为 r 1 0 g A C Y a o得 到 l 的一个上 界值 为 l 一 0 1 o g 2 l 2 曲 此他得 出 l 选择网络的延迟时间之上 界为 g n l o gmJ bg l o g lo g n 0 1 g r a l o g l o g L o g n O 1 o g l o g l o g n 一 3 丁 l L l 0 g l J 1 0 g l Ya o的上 界在理论上是 目前 所知可构 造的 选择 网络最好 的延 迟时间上 界 维普资讯 计 算 机 学 报 1 9 9 0篷 三 新 的 结 果 本节将通过对递归网络树形展开的手段 用组合 计数 的方 法求得一 个比 Y a o更好的 上 界 从而 导出一个 m 选 择网络新的延迟 时间上界 为方便起见 首先在假定m一 2 一 2 0 l D 下进行讨论 然 后再 推广到 一 般的情 形 3 1 E m n 的树形晨开 设 表示从 y个元素 中选择 个最 小元素的 问题 1 y 则 可 按其递归构造性质 图 2 分解成一棵高度为 l o g n的展开树 如图 3 所示 其中 为 腰开树 中结点 1 1 m 为树之 根结点 r r 为树之叶结 点 1 r 1 注意对 1 2 的分解是 詈 一 一 即经 I o g y 次并行比较后归结为 1 1 此时已完成选择 其中每次并行比较均是删去一 半较 大元素 MAX 子 集 而 在另一半较小元素 MI N 子集 中继续做下一次比较 E m 的树形展开如图 3所 示 图 给 出了一个E 3 2 2 5 6 树形展开的实倒 图3 E j的树 形展 开 3 2 E m n 的内部组合计数规律 在 E m 的展开树中 我们所关心 的是 其中叶结 点 r 1 r 的组 合 计数 规律 用 表示在 根结点 为 如 y o 的展开树 子树 中叶结点 r 出现的个数 其 中 l r o 根据 E m 展开树 中结点的 分解 规则 即每个 可 分解 成 詈 号 和 号 观 察 和 分 析 图 3 可 得 维普资讯 l 躬 沈鸸 等 选 择 厨络延 迟时 间的 一 个新上 界 t 器 r 一 I s 一1 一 里 一 一 2 j 图 E 3 2 2 5 6 的 树 彤展开 一 喑 1 一 s 一 j i 十 一 弓 喑 十 1 og n 二 墨 三 一 一 一 十 T 4 一 弓 i i i s 应 用 的结果于上式 1 1 0 唁 一 维普资讯 计 算 机 学 报 I 9 9 0年 一 1 i 蝗 喑 i i i i 项 一 尊 2 3 1 0 g 州 一 1 r 一 一 一 s 哥 一 8 B 8 8 B 一 咭 R 8 j i 应用 s 的结果于上式 一 蹬 项 十f 1 1 i f 1 1 百 f 1 1 i 项 项 1 项 兰 日 l 峙 一 维普资讯 2期 沈鸿等 选择网络延迟时间的一个新上界 i l q 唁 高 一 和 L f j 扰 用 丢 让 明 还 51 埋1 引理 1 展开树 中叶 结点 r 1 r m 的个数 为 f 卵 一1 一 i 证 s 一 l由s 本身的意义显 知为真 k m 1 2 s时 一 蓦 由 前 面 的 直 接 推 导 潞 设 当 一 m 时 一 篓 k 即 一 鬻 一p 誓 一 1og 暑 l 一 由 每 个 y 均 可 分 解 成 专 一 和 f 詈 署 仿 s 时 的 推 导 可 得 注意到 一 1 当 一 p 1时 卜2 一 维普资讯 9 4 计 算 机 学 报 9 9 0 隼 j 一 一 警 尘1 一 l P p s s s 应 用 s 善 的 结 果 于 上 式 s 二 一 l i p 1j 至 项 i P ri p 二 喾 l lo g p s 项 s 二 一 p I 溪 顼 篁 p I 喜 项 s 一 1 喾 i i 一 二 二 睡 堕 和 溪 十 一 耋 一 十 三J p p J l 毫 砉 维普资讯 2期 沈鸡 等 选择 网络 延迟 对阃 的一 个 新上 界 悃 此 当 一 P 1时 式也成立 由归纳法卸 对于 任意的1 l o g 引理 1均成立 引理 1揭示了 E 网络 内部的组 合计数 规律 3 3 m n 的解析表达式及 其上界 如第一 节所述 f m n 是E 网络从 n个输入元素 中选 出的 包含 m个最 小 者的元素个数 下面我们将 由 m 的组合意义来导出 f m n 的解析表达式 由 E m 的树 形分 解知 m 经各层分解后 诸子选择不断地深 凡 直至 出现 十 结点 为止 1 此时每个叶结点 的 r个结果元素即 为其选得的 元素 因此分解树 中所有叶结点 r r 之结 果元 素即构成 了 E m 最终 所选 出的元 素集合 其 元素个数 即为 之 值 显然每个叶结点 r 之 结果元素 个数为 r 由 中的 的组合 计数 j 戈 4 可得 一 蓦 罢 一 m I 誉 骞 H k 1 2 J 0 l l f 蓦 吨 1 一 z 州 1 1 11 女 a t l 一 口l 用递推式逼近可求得 5 式的 一个上 界值 考察 l 0 女 l o g m 得 廿 走 1 圭 埘 女 1 一 一 竺三 一a 一 2 一k 而 一 不言而喻 其 条件 为 2 m 当 4 m 时 取公 比 口一 显然 1 刚 Z一 由 e 0 可知 口 l 口 口 t 即可取m 口 旧 作为 5 式的 t U 0 式 赵 的 式 令 维普资讯 计 算 机 学 报 I 一 个上界 值 为一等比级数 其和为 因而 有 一 一 錾 1 I o g m l og 三f 10 g 旦 8 m 卅 2 一 一2 m 8 m 2 m I 9 0 年 一 z m 对 于 一 m cm 一 m 薹 去 雹 的 值 可 直 接 求 得 对 于 一 4m m 一 m m J 的 值 可 直 接 求 得 0 令 一 m 薹 薹 一 一 一 暑 导 一 1 一 1 十 1 十 等 卜 l o g m 扣 一2 一 一 一 6 l 蓐 t 量 j 一 I 一 一 0 卅 一 卅 一 卅 孽 口 一 小 卅 h g 窖 一 一 一 维普资讯 2期 执鸿 等 选择 网 络延 迟时 间的 一个 新上 界 综合 6 7 两式得 一 n 4m D m 2 ra 4 m 引理 2是在假定 m 一 2 一 2 下得 出的 现将其推广到一般的情形 对于一般的 1 m 按图 2对 E 进行树形 分解 注意对 y 的每次分 舟 早 是 1专 J l 詈 j 和 f考 因 此 E 分 解 树 中 的 叶 结 点 叱 j 一 m l l鲁 一 因 为l j 且 l 为 整 数 即l 三 j m 故 有 L 10 g m J 因 而 由 引 理 推 论 一 0 I 一 D 2 r a 4 r a 9 式即是在一般 的 l m 4 m 时 r 啦 一 r 1 L l o g J l o g l o g 兰 I f 1 f l l 0 g f十 第三级 E 维普资讯 计 算 机 学 报 州 枷 叫 一 l o g m J lo g l o g m j l o g l o g 旦一l o g m 1 L 1 m J 10 L 1 J 10 1 一 1 l o g L l o gmJ l o g 10g f lo g lo g 一 l0 g 钟 J 10 g L 10 g 钟 J L lo g m J l g l0 g 10 g 当2 怫 4 m 时 r l o g 1 l o g 2 第 四级 N m m 采用双调选 择 网络 实现 m 双调选择 网络的时间复杂性为 0 1 o g m l o g 故 m 啦 所 需的延迟 时间为 当 4 m 时 一 s 一 一 m 一r 故 延迟 时间 为 0 1 o g ml o g 一 Ll o gm l o g m s os m 一 l o g m l o g l o gm q l o g 2 m l o g l o g j 当 2 r a 4 m 时 0 1 o gml o g m 0 J o g 2 m 翅 此整个 m 选择 网络的延迟 时间为 当 4 m 时 T m o g L l o gmJ l o gl o g 维普资讯 2期 亢鸿 等 选择 髓络 延 迟时 间的 一 十新上 界 o g 2m lo g lo g m 上式 中的第一项是 第一级 网络的 延迟 第二项 是第二级 网络的延迟 而后两项可解释 如 下 由于在渐近情况下 第三级 网络延迟的第一 项小于第 二级 网络的延 迟 而第三级 网 绍 延迟的第二项小于 第四级 网络延迟的 第一项但大 于其第二项 故 m 一 中的后两项 最 终 取 为 I g l g 1 g m L Io g m l0 g 10 g l0 g 三 当 m 时 相对于 可忽略 故 T m 一 之最后项 中起支 配 作 用 的 是 l 0 g 1 0 g l 0 g 延 迟 时 间 为 m l o g I L l o g l J 1 0 g l 0 g三 0 1 0 g l 0 g l 0 g 当 2 4 m 时 丁 l o g 2 l o g l o g 0 1 0 1 0 g 上面仅讨论了 2 m 时的 m 选择网络的延迟情况 对于 一 m r V 哩 哩 卅 嚷 H 0 维普资讯 1 0 0 计 算 机 学 报 1 O 军 四 结 论 从 个元素 中选取前 m个最小元素的 选择 问题 是计算机科学 中具 有广泛应 用背景的研究课题 求解 选择 问题 的方 法可分 为两大类 网络 求解 和算 法求解 在选择 网络的研究中延迟时间上界是一个关 键的理论 课题 它无论是对 于选 择 网络本身还是与其相关的并行选择算法都具 有重 要的 意义 本文提 出了一种将递归 网络 E 按树形展开的方 法 通过对 展开 树 中叶结点的 组台计数揭示了 网络 内部的数据聚集 规则 求得了反映 E m 工作 结果形态 的重要函 数 m 的 解释 表示 及其上 界 从而 导出了 选择 网络延迟时问的一个新的上 界 本文所给 出的延迟时间新上 界与 A C Y a o的上 界相 比较 具有 较好 的改进 其时间 1 r 一 上界降低了 L l o g J 1 0 g lo g 卅k gl o g 坍lo gl o g m 在木文的成稿过程中曾与中国科技太学计算机 袭者策 善副教授进行了有盐的讨论 数学系李乔教授曾给予作者 鼓 励和支 持 对 于他们 的 帮助 怍者 在此 一并致 静 参 考 文 献 A C Yao Bou ds el e e t i e t wo r ks 盯 M Co m p 9 1 950 5 6 6 5 82 V E Al e k s e y v s 0 n n g g 0 r I t b ms wl t h i i m me mo f y Ki b f j f 5 5 1 9 6 9 l 9 9 1 0 3 B W W a h nd K L C n A pan i t i oni ng a ppl a c h l 口 t he de s i g f e l e c t i o n