模型与下界.PPT

现代密码学理论与实践之五 * P=?NC （P-NC问题） 现在的估计 如果 ，则PC问题无好的并行算法 P=NC NC PC P 现代密码学理论与实践之五 * End of Chapter 20 现代密码学理论与实践之五  Parallel Algorithms  Chapter 20 Models and Bounds Spring, 2018 现代密码学理论与实践之五 * 主要内容 不同的PRAM模型的相互模拟 PRAM-EREW模拟PPRAM-CRCW PRAM-CRCW之间的模拟 下界 算法研究的两个方向：优化（上界）、可能性（下界） Gates的工作 理想的PRAM模型与下界 PRAM模型的下界 NP完全理论导引 P完全理论 现代密码学理论与实践之五 * 不同的PRAM模型的相互模拟 不同的PRAM模型 PRAM-EREW PRAM-CREW PRAM-CRCW CPRAM-CRCW：允许所有处理器并发写同一数 APRAM-CRCW：允许任意处理器自由写 PPRAM-CRCW：允许优先级高的处理器写 结论：计算能力是相当的 现代密码学理论与实践之五 * PRAM-EREW模拟PPRAM-CRCW 定理20.1：一条p-处理器PPRAM-CRCW模型上的指令，可在p-处理器PRAM-EREW模型上用O(logp)的时间实现。 证明：只要证明并发读指令和并发写指令的模拟 并发读指令的模拟： (PPRAM-CRCW) 并发读指令 ：处理器Pi读取Mji单元中的内容(i=1~p), 这些Mji单元中有相同的单元，相同的单元存在并发读 (PRAM-EREW)处理器Pi 设置数对ji, i , i=1~p ji, i 按照字典序排序：时间O(logp) 第一分量相同的数对组成块（通过树播送数据，完成Mji单元中的数据分布）： 时间O(logp) Pi读取分布于不同地址的与Mji单元内容相同的数据：时间O(1) 同样可证并发写指令的模拟： 使用三元组地址，处理器号，待写数据 推论： TEREW =O(TPCRCW logp ) 现代密码学理论与实践之五 * PRAM-CRCW之间的模拟 CPRAM_CRCW上算法可在APRAM_CRCW上正确执行 APRAM_CRCW上算法可在PPRAM_CRCW上正确执行 计算能力是按CPRAM_CRCW，APRAM_CRCW，PPRAM_CRCW依次增强的。在对共享存储的容量不加限制时，三个模型是等效的。 现代密码学理论与实践之五 * PRAM-CRCW之间的模拟（续） 定理20.2 运行在p-处理器PPRAM-CRCW上时间为T的算法，可在plogp-处理器CPRAM-CRCW上运行时间为O(T)。 定理20.3 p-处理器PPRAM-CRCW上的一条并发写指令，可在p-处理器CPRAM-CRCW模型上用O(logp/log logp)时间实现。 定理20.4 p-处理器PPRAM-CRCW上的一条并发写指令，可在p-处理器APRAM-CRCW模型上用O(log logp)时间实现。 现代密码学理论与实践之五 * 算法研究的两个方向 优化(对算法而言) 寻找更好的算法 设计技巧 一个新的算法（上界） 可能性(对问题而言) 说明难以得到更好的算法 证明技巧 对问题的更好认识（下界） 现代密码学理论与实践之五 * Gates, William H. and Christos H. Papadimitriou. Bounds for sorting by prefix reversal. Discrete Mathematics 27, 47-57, 1979. Harvard University(1973) Microsoft (1975) Princeton University (MS 1974 and PhD 1976) 现代密码学理论与实践之五 * 上界与下界 问题描述： 仅通过前缀翻转（prefix reversal）操作对n个大小不同的序列排序。 前缀翻转： 将包含首个元素的子序列进行翻转 结果： 给出算法，证明至多(5n+5)/3 次操作可以排序完成 给出例子，证明17n/16次操作无法完成排序 改进： 1995年，新的下界结果 现代密码学理论与实践之五 * 理想的PRAM模型的下界 理想的PRAM模型 n个处理器可访问无限的共享存储单元 每个处理器有无限的私有存储单元 一步计算分为三个阶段：读阶段、计算阶段、写阶段 每一步计算允许任意数量的局部计算 理想PRAM模型反映了通信的限制 理想PRAM模型的下界对于标准PRAM模型同样成立 现代密码学理论与实践之五 * PRAM模型的下界 P