一、可重构造网孔机器上常数时间的最优异或算法及应用（论文文献综述）
杨际祥[1]（2012）在《并行与分布式计算负载均衡问题研究》文中认为多核计算、集群计算以及新兴的云计算成为当前的主要计算模式。多核大众化并行计算成为未来计算的主流已成为工业界与学术界的共识,基于多核节点的多核集群成为高性能计算（HPC）的一种发展趋势,而云计算作为一种特定的分布式计算,近年来受到了工业界和学术界的广泛关注。随着多核、集群系统的核数与计算节点数目的不断增长,以及要求提供云服务的用户数量不断增多,对计算的性能和可扩展性的需求从来没有像目前这样迫切过。负载均衡作为提高并行与分布式计算性能和可扩展性的一个关键技术,相关问题亟待得到研究与解决。本文主要从可应用性驱动、结构驱动和软件驱动三个方面对并行与分布式计算的负载均衡问题展开了研究。本文的主要研究工作如下：（1）针对动态负载均衡（DLB）的基本问题,给出了DLB的主要目标和基本定义,在此基础之上,给出了DLB问题的一种形式化描述；根据DLB策略的主要特征提出了-个综合分类方法。（2）针对负载均衡策略的可应用性问题,研究了在简单性和性能之间可获得一个较好折中的贪婪动态负载均衡（GDLB）策略。将GDLB策略应用于基于BP和SVM的大规模交通流并行预测问题,可提高预测速度和规模。（3）传统的Work-Stealing（简称WS）策略在面临需要传输大量数据的应用和具有层次结构的平台时,它的通讯时间通常令人无法忍受。针对该问题以及分治计算问题,本文提出了一种层次结构的WS （DaCHWS）策略,实验结果验证了DaCHWS策略性能优于Work-Sharing和Satin-CRS策略。（4）考虑了大规模分布式计算系统的通讯延迟开销和延迟时变性特征,提出一种基于广义神经网络的层次结构动态负载均衡（GNNDLB）策略,仿真实验验证了GNNDLB策略优于同类策略：针对多核集群通讯的层次结构特征,考虑了节点内冲突代价,提出了以最小化计算代价、节点间通讯代价和节点内冲突代价的总代价为目标的多核集群任务分配问题,通过建立任务分配问题与最小费用流问题的等价关系来分析并证明节点内冲突代价对问题复杂性的影响关系,并给出了一个求解模型,理论分析和实验结果验证了相应理论结果的正确性和求解模型的有效性。（5）针对多核大众化并行计算的提高多核应用程序开发产能同时获得并行性能收益这个核心目标,设计并实现了一个轻量级的基于用户层次的WS调度策略的多核多线程并行编程库（UCMLib）。该库基于任务原语概念,提供了数据并行性和任务并行性两种并行模式,对多线程编程的复杂性进行了封装和抽象,为开发者提供高级的编程方法而不必显示地考虑锁和竞争,简化并行编程难度,提高开发效率。性能测试表明,当计算规模较大时,UCMLib在数据并行性与任务并行性两方面获得了比TPL库略优的加速比。此外,分析了未来多核软件研究的几个关键问题。
赵建勇,许胤龙,陈龙斌[2]（2004）在《可重构造网孔机器上k-近邻并行算法》文中指出最近邻问题是计算几何学中的基本问题之一 ,k 近邻是最近邻的扩展 ,它在VLSI设计、数据库检索、模式匹配以及图像处理等领域有着广泛的应用背景 对于点数为N的平面点集S ,在规模为N×N的可重构造网孔机器上 ,提出了时间复杂度为O（k）的求S中所有点k 近邻的并行算法 该算法的时间复杂度已达到了该问题本身固有时间复杂度的下界
王高才[3]（2004）在《Mesh网络容错性的概率分析研究》文中提出Mesh网络是迄今为止最为重要和最具吸引力的并行计算机系统网络拓扑结构之一。本文提出全新的基于概率模型研究Mesh网络的容错性问题的理论,提出了k-Mesh子网结构的方法,本文基于k-Mesh子网结构研究了二维和三维Mesh网络的容错性,并基于k-Mesh子网结构提出了高效的二维和三维Mesh网络单播和广播容错路由算法,从概率的角度分析了各种算法的有效性。 本文首先在每个结点具有独立的出错概率的情形下研究Mesh网络的容错性,提出基于k-Mesh子网结构的概念:即k-Mesh子网连通性。证明了当网络结点出错概率给定时,随着网络规模的增加,Mesh网络的连通概率将任意地趋向无穷小。因此,对于以Mesh网络为拓扑结构的并行计算机系统的研究者和制造商提出一个实际而重要的课题:当网络连通概率和网络规模给定时,网络结点的出错概率的下界应控制在多大的范围之内。本文严格推导出Mesh网络的连通概率的一个下界。研究结果表明实际规模的以Mesh网络为拓扑结构的并行计算机系统是能容许相当多的出错结点的,因此也是相当可靠的。研究结果也表明了三维Mesh网络有优于其它流行的网络拓扑结构的优势。与规模相当的二维Mesh网络相比,三维Mesh网络在保持较高的连通概率的同时能容许更多的网络结点出错。而与规模相当的超立方体网络相比,三维Mesh网络在保持较高的连通概率的同时享有更低的结点度。 本文基于k-Mesh子网结构提出了基于局部信息的和分布式的二维和三维Mesh网络单播容错路由算法。因为容错路由算法是基于k-Mesh子网结构设计的,所以本文从概率的角度研究了单播容错路由算法的有效性,推导出容错路由算法的成功概率。本文运用严格的数学推理,证明了二维Mesh网络结点出错概率只要控制在1.8%以内,则对于多达250000个结点的二维Mesh网络,路由算法具有99%的概率确保找到正确结点组成的路径。当结点出错概率不大于2.5%时,即使对于规模达到373248个结点的三维Mesh网络,路由算法仍具有99%的成功概率。路由算法的时间复杂性是线性的,模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度。
李庆华,蒋廷耀[4]（2004）在《基于LARP BS模型的最大值查找算法》文中提出具备可重配置流水线总线的线性阵列LARPBS（linear arrays with a reconfigurable pipelined bus systems）是近来出现的一种高效的并行计算模型,与理想的PRAM模型不同,LARPBS是现实可行的。基于LARPBS模型,Y.Pan介绍了2种宽度和精度任意的数据项的最大值查找算法:算法1使用了N2/2个处理机、O（1）时间,它是目前时间最优的算法;算法2使用了N个处理机、O（loglogN）时间。本文介绍了2种最大值查找算法,时间复杂度同Y.Pan的算法,但所用处理机数减少了一半,这是对Y.Pan算法的重要改进。
王国军[5]（2002）在《具有大量错误结点的超立方体网络容错模型和容错路由算法研究》文中指出超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结构之一。本文提出了两种全新的基于子立方体结构的超立方体网络中的局部连通性网络容错模型，基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法，提出了一种全新的、有效的和强有力的基于子立方体结构的超立方体网络容错模型和容错路由算法的概率分析方法和技术。 本文提出了两种基于子立方体结构的局部连通性网络容错模型：即局部K维子立方体连通性和局部子立方体连通性。证明了在结点错误比例任意接近50.0％时，局部连通的超立方体网络是全局连通的，即超立方体网络的局部连通性隐含了整个网络的全局连通性。所要求的局部连通性条件可以用基于局部管理的分布式方式进行检测和维护。 本文基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法。所设计的容错路由算法都是基于局部信息的，因而具有很好的实际意义。特别地，对于单播容错路由算法，不管所给定的超立方体网络是否满足局部连通性条件，算法都能适用：在满足要求的条件时，算法将成功地构造一条路由路径；在不满足要求的条件时，如果算法不能成功地构造一条路径，则算法将正确地报告出给定的超立方体网络不满足要求的条件。 本文还对局部连通性网络容错模型和网络容错路由算法进行了概率分析研究。大量的实验与经验表明超立方体网络具有很强的容错性。但是，当前国内外已经提出的超立方体网络容错模型只能表示一些极端的不大可能的情形，也就是说这些容错模型明显低估了超立方体网络的容错能力。本文使用概率分析的方法研究在给定结点错误概率的情况下，推导出局部连通性网络容错模型的容错性和网络容错路由算法的容错性概率。本文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达10.0％的错误结点而具有99.0％的概率确保正确结点的连通性，而如果结点的错误概率不超过0.1％，则所有实际规模的超立方体网络能够具有99.9％的概率确保正确结点的连通性。这是当前国内外对超立方体网络进行概率分析的最好结果。该方法在确定网络容错模型和网络容错路由算法的容错性概率的下界时具有普遍意义。该方法也能够用于研究其它层次结构的网络和其它的网络通信问题。
许胤龙,陈国良,陈龙斌,万颖瑜[6]（2002）在《可重构造网孔机器上常数时间的最优异或算法及应用》文中提出逻辑异或和前缀异或是基本的逻辑运算 ,经常应用于各种算法中 .该文在规模为 N× N的可重构造网孔机器上提出了求 N个逻辑位的并行异或和并行前缀异或算法 ,其运行时间均为常数 .基于该并行异或算法 ,文中还提出了相同的模型下在常数时间判定一给定点是否在 N条边构成的平面多边形中和判定一给定点是否在 N个平面构成的空间多面体中的并行算法 .就实质而言 ,这些算法都是相应问题的第一个处理器数为线性、运行时间为常数的并行算法
万颖瑜,许胤龙,顾晓东,陈国良[7]（2000）在《可重构造网孔机器上最小生成森林的边更新算法》文中提出最小生成森林的边更新在网络路由等方面有着重要的应用价值 .给定 n个结点的无向加权单图 G,该文首先在 n× n的二维可重构造网孔机器上提出了在 O（1）时间内判断 n个结点的无向图的连通性和在 O（logn）时间内求 n个结点的内向树中任一结点到根的路径两个算法 ,并在 n× n× n的三维可重构造网孔机器上提出了 O（1）时间内求 n个结点内向树中任一结点到根的路径的算法 .然后在上述算法的基础上提出了两个 G的最小生成森林的边更新算法 ,一个运行在 n× n的二维可重构造网孔机器上 ,时间复杂度是 O（logn） ,另一个运行在 n× n× n的三维可重构造网孔机器上 ,时间复杂度是 O（1） .
二、可重构造网孔机器上常数时间的最优异或算法及应用（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、可重构造网孔机器上常数时间的最优异或算法及应用（论文提纲范文）
（1）并行与分布式计算负载均衡问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 研究背景和意义 |
| 1.2 动态负载均衡(DLB)策略研究现状 |
| 1.2.1 分布式DLB策略 |
| 1.2.2 集中式DLB策略 |
| 1.2.3 混合／层次DLB策略 |
| 1.2.4 支持DLB策略的软件环境 |
| 1.2.5 小结 |
| 1.3 本文主要研究内容 |
| 1.4 本文组织结构 |
| 2 动态负载均衡(DLB)问题 |
| 2.1 基本定义 |
| 2.2 DLB 问题的形式化描述 |
| 2.3 加速比和可扩展性分析 |
| 2.4 DLB策略分类方法 |
| 2.5 DLB策略有效性分析 |
| 2.5.1 信息陈旧性的影响 |
| 2.5.2 拓扑结构的影响 |
| 2.5.3 负载分布的影响 |
| 2.6 小结 |
| 3 贪婪动态负载均衡(GDLB)策略及其应用 |
| 3.1 贪婪调度问题 |
| 3.2 GDLB策略 |
| 3.3 基于GDLB算法的并行BP交通流预测方法 |
| 3.3.1 DP-BP方法的计算效率分析 |
| 3.3.2 实验 |
| 3.3.3 小结 |
| 3.4 基于GDLB算法的大规模实时交通流并行SVR预测方法 |
| 3.4.1 支持向量机预测模型 |
| 3.4.2 路网交通流预测模型 |
| 3.4.3 大规模路网多路段短时交通流的并行预测方法 |
| 3.4.4 实验 |
| 3.4.5 小结 |
| 4 层次Work-Stealing(WS)动态负载均衡策略 |
| 4.1 层次结构WS策略的理论分析 |
| 4.2 并行分治计算中的一种层次WS(DaCHWS)策略 |
| 4.2.1 分治计算问题 |
| 4.2.2 DaCHWS策略 |
| 4.2.3 任务划分 |
| 4.2.4 DaCHWS算法 |
| 4.2.5 实验 |
| 4.3 小结 |
| 5 一种大规模分布式计算动态负载均衡策略 |
| 5.1 智能神经元预测模型 |
| 5.2 基于GNN的延迟预测模型及其学习算法 |
| 5.3 基于GNN的层次结构动态负载均衡(GNNDLB)策略 |
| 5.4 GNNDLB策略的负载均衡过程 |
| 5.5 实验 |
| 5.5.1 GNNDLB策略与传统集中式策略的性能比较 |
| 5.5.2 GNNDLB策略与传统分布式策略的性能比较 |
| 5.5.3 GNNDLB策略与随机延迟策略的性能比较 |
| 5.6 小结 |
| 6 多核集群任务分配问题(MCTAP) |
| 6.1 基本定义和假设 |
| 6.2 MCTAP复杂性分析 |
| 6.2.1 单节点上的节点间通讯和节点内冲突代价分析 |
| 6.2.2 一致代价的多核集群任务分配问题复杂性分析 |
| 6.2.3 非一致代价的多核集群任务分配问题复杂性分析 |
| 6.2.4 MCTAP解法及其定理结论可应用性与有效性讨论 |
| 6.3 MCTAP求解模型 |
| 6.3.1 传统TAP的0-1整数规划模型 |
| 6.3.2 MCTAP求解模型 |
| 6.3.3 应用极大独立集优化MCTAP求解模型 |
| 6.3.4 计算结果 |
| 6.4 小结 |
| 7 多核多线程编程及未来多核软件的几个关键问题 |
| 7.1 多核多线程编程环境 |
| 7.2 UCMLib多核多线程编程库 |
| 7.2.1 线程池与调度器 |
| 7.2.2 实验 |
| 7.2.3 小结 |
| 7.3 未来多核软件的几个关键问题 |
| 7.3.1 应用问题 |
| 7.3.2 并行编程模型 |
| 7.3.3 多核算法 |
| 7.3.4 多核计算模型 |
| 7.3.5 小结 |
| 结论与展望 |
| 参考文献 |
| 攻读博士学位期间发表学术论文情况 |
| 致谢 |
| 作者简介 |
（3）Mesh网络容错性的概率分析研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 Mesh网络简介 |
| 1.2 课题的研究意义 |
| 1.3 国内外研究现状与分析 |
| 1.3.1 Mesh网络拓扑结构的研究 |
| 1.3.2 Mesh网络容错模型的研究 |
| 1.3.3 Mesh网络容错路由算法的研究 |
| 1.3.4 Mesh网络的概率分析研究 |
| 1.4 课题的主要研究内容 |
| 1.5 论文的结构 |
| 第2章 基于概率模型的二维Mesh网络容错性的分析 |
| 2.1 概述 |
| 2.2 二维Mesh网络连通性的概率分析 |
| 2.2.1 二维Mesh网络连通概率的上界 |
| 2.2.2 k-Mesh子网连通性定义 |
| 2.2.3 k-Mesh子网连通的二维Mesh网络连通概率的下界 |
| 2.2.4 二维Mesh网络连通性的概率计算 |
| 2.3 一种邻接k-Mesh子网方法研究二维Mesh网络的容错性 |
| 2.3.1 相邻k-Mesh子网的连通概率 |
| 2.3.2 二维Mesh网络全局连通性的概率 |
| 2.4 模拟结果 |
| 2.5 本章小结 |
| 第3章 基于概率模型的三维Mesh网络容错性分析 |
| 3.1 概述 |
| 3.2 三维Mesh网络连通性的概率分析 |
| 3.2.1 三维Mesh网络的不连通概率 |
| 3.2.2 三维Mesh网络的连通概率 |
| 3.2.3 更大k-Mesh子网的计算方法及连通概率的计算 |
| 3.3 三维Mesh网络与其它网络的相互比较 |
| 3.4 模拟结果 |
| 3.5 本章小结 |
| 第4章 二维Mesh网络容错路由算法及其概率分析 |
| 4.1 概述 |
| 4.2 维序路由算法容错性的概率 |
| 4.3 二维Mesh网络容错路由算法设计及其概率分析 |
| 4.4 具有更高成功概率的二维Mesh网络容错路由算法 |
| 4.5 模拟结果 |
| 4.6 本章小结 |
| 第5章 三维Mesh网络容错路由算法及其概率分析 |
| 5.1 概述 |
| 5.2 三维Mesh网络容错路由算法 |
| 5.3 三维Mesh网络容错路由算法的概率分析 |
| 5.4 模拟结果 |
| 5.5 本章小结 |
| 第6章 二维Mesh网络广播容错路由算法及其概率分析 |
| 6.1 概述 |
| 6.2 二维Mesh网络广播容错路由算法FRBR |
| 6.3 算法FRBR容错性的概率分析 |
| 6.4 模拟结果 |
| 6.5 本章小结 |
| 第7章 三维Mesh网络广播容错路由算法及其概率分析 |
| 7.1 概述 |
| 7.2 三维Mesh网络广播容错路由算法SRBR |
| 7.3 算法SRBR容错性的概率分析 |
| 7.4 模拟结果 |
| 7.5 本章小结 |
| 第8章 结束语 |
| 8.1 工作总结 |
| 8.2 进一步研究方向 |
| 8.2.1 在Mesh网络上的进一步研究 |
| 8.2.2 在移动自组网和传感器网络上的应用 |
| 参考文献 |
| 致谢 |
| 攻博期间参与科研项目情况及发表论文情况 |
（5）具有大量错误结点的超立方体网络容错模型和容错路由算法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 超立方体网络简介 |
| 1.2 课题的研究意义 |
| 1.3 国内外研究现状与分析 |
| 1.3.1 超立方体网络拓扑结构的研究 |
| 1.3.2 超立方体网络容错模型的研究 |
| 1.3.3 超立方体网络容错路由算法的研究 |
| 1.3.4 超立方体网络的概率分析研究 |
| 1.4 课题的主要研究内容 |
| 1.5 论文的结构 |
| 第2章 超立方体网络容错模型 |
| 2.1 概述 |
| 2.2 局部连通性网络容错模型 |
| 2.3 实验结果 |
| 2.4 本章小结 |
| 第3章 超立方体网络单播容错路由算法 |
| 3.1 概述 |
| 3.2 单播容错路由算法及其算法分析 |
| 3.2.1 局部k维子立方体连通的n维超立方体中的单播容错路由算法 |
| 3.2.2 局部子立方体连通的n维超立方体中的单播容错路由算法 |
| 3.2.3 局部3维子立方体连通的n维超立方体中的单播容错路由算法 |
| 3.3 实验结果 |
| 3.4 本章小结 |
| 第4章 超立方体网络广播容错路由算法 |
| 4.1 概述 |
| 4.2 广播容错路由算法及其算法分析 |
| 4.3 实验结果 |
| 4.4 本章小结 |
| 第5章 超立方体网络并行容错路由算法 |
| 5.1 概述 |
| 5.2 并行容错路由算法及其算法分析 |
| 5.3 实验结果 |
| 5.4 本章小结 |
| 第6章 容错模型和容错路由算法的概率分析 |
| 6.1 概述 |
| 6.2 容错模型的概率分析 |
| 6.3 容错路由算法的概率分析 |
| 6.4 本章小结 |
| 第7章 结束语 |
| 7.1 工作总结 |
| 7.2 研究展望 |
| 致谢 |
| 攻博期间参与科研项目情况及发表论文情况 |
| 参考文献 |
（6）可重构造网孔机器上常数时间的最优异或算法及应用（论文提纲范文）
| 1 引 言 |
| 2 可重构造的网孔机器 (RMESH) |
| 3 并行异或算法和并行前缀异或算法 |
| 4 点在多边形和多面体中的判定 |
| 5 总 结 |
四、可重构造网孔机器上常数时间的最优异或算法及应用（论文参考文献）
- [1]并行与分布式计算负载均衡问题研究[D]. 杨际祥. 大连理工大学, 2012(10)
- [2]可重构造网孔机器上k-近邻并行算法[J]. 赵建勇,许胤龙,陈龙斌. 计算机研究与发展, 2004(09)
- [3]Mesh网络容错性的概率分析研究[D]. 王高才. 中南大学, 2004(11)
- [4]基于LARP BS模型的最大值查找算法[J]. 李庆华,蒋廷耀. 计算机科学, 2004(03)
- [5]具有大量错误结点的超立方体网络容错模型和容错路由算法研究[D]. 王国军. 中南大学, 2002(04)
- [6]可重构造网孔机器上常数时间的最优异或算法及应用[J]. 许胤龙,陈国良,陈龙斌,万颖瑜. 计算机学报, 2002(01)
- [7]可重构造网孔机器上最小生成森林的边更新算法[J]. 万颖瑜,许胤龙,顾晓东,陈国良. 计算机学报, 2000(01)