Valiant并行归并及排序时间复杂性的分析研究.pdfVIP

维普资讯 第 22卷第4期 广西大学学报 (自然科学版) VoI．22No．4 1997年 l2月 JournalofGuangxiUniversity(NatSciEd) C． 1997 一 响 S 秀 钟诚 6 (广西大学计算机利每 再 i面 32岁，男，副教授) 摘 要 深入分析研究著名的Valiant并行归并及排序算法，并推导其关于EREW (异步读写)，CREW (-~发读异步写)和cRcw (并发读-~)tt算模型的修正的时闾复 杂性结果． 关镀词 Valiant归并 !盐生； 生苎生 ．塑皇查丝． 分类号 TP301．6 排序与查找是计算机处理数据中重要且基本的工作 ．LG．VMiant研究了多处理器并 行系统上的归并及排序算法，这一算法对于人们设计与分析并行算法在理论和方法上具有重 要的意义 ．许多研究并行排序、查找和选择问题的学者都借鉴了Valiant排序的思想或引用 其结果 ” 本文深入分析研究Valiant并行归并及排序算法，并给出其在 EREW (~步读 写)，CREW (并发读异步写)和CRCW (并发读写)计算模型上的修正的时间复杂性结果． 1 Valiant并行归并及排序的分析研究 Valiant归并的第2步需要将 序列中所有打*号的元素与y序列中所有打*号的元素 同时比较．对于 =r√ 1的情形，这 X } ， … √ Y： … ，’ … … ’0 其中符号一代表比较操作 (下同)． 显然，存在着 √ 个处理器需同时读取 √ “一1，2，…，√m妯g值，即存在着存取冲突 问题．同理，也有 √ 个处理器需同时读取 0T(j 1，2，…，J—)的值的问题．这样，实际上 在一个比较步即0(1)时间内就不一定能完成此 比较过程． 另一方面，Valiant归并的第3步需要将 序列中所有打*号的元素同时与它们应插入 的Y序列某段中的每一个元索(打*号的元素除外)进行比较．对于 =r√ i1的情形，这一 * 香港王宽诚教育基金会和广西教委及广西大学科研基金资助项 目 收藕Ft期t1盼6—10—17 维普资讯 286 广西大学学报 (自然科学版) 第22卷 比较过程为 X ： 面 … … √ … 。 Y ： yl … 4 一ly — … Y；4 情形 l 每个∞√‘ “=1，2．…，√ )应插入的y序列的段均不相同．此时，仅会出现 (√—一1)个处理器需要同时读取 √ 的值的冲突现象，而不会出现多个处理器需要同时读 取y序列中某段内某个元索值的冲突现象． 情形2 设 序列中有 个打*号的元素 √ (1≤z≤ √m)均应插入y序列中同一段 (2≤≤ √ )，这样除了出现有(√—一1)个处理器需要同时读取 序列中这 个打*号的元 素中某一个 √ 的值的冲突现象之外，还会出现有 1个处理器需要同时读取y序列中某段 内某一个元素 ( √ +≤ ≤ ”I)4 -)的值的冲突现象- 情影3 序列中所有打*号的元素均应插入y序列中同一段．这时，除出现(√ 一1) 个处理器需同时读取z “=1，2．…，√ )的值的冲突现象外，还出现 √ 个处理器需要 同时读取y序列中某一段内某个元素值的冲突现象． 因此 ．无论是哪种情形，在一个比较步即O(1)时间内就不一定能完成Valiant归并的第 3 步． 对于 ^一Fr√mn](r1)的情形，上述分析仍适用． 2 Valiant归并及排序修正的时间复杂性 2．1 EREW 计算模型 EREW模型的并行系统不允许