并行计算的一体化研究现状与发展趋势

在过去的20多年里, 中国科学技术大学的研究团队逐渐形成了并行计算“结构-算法-编程-应用”一体化的研究体系, 也就是所谓的并行计算研究的生态环境. 该文就并行计算的一体化研究现状进行简要的综述, 并结合多核系统、云计算、个人高性能计算机等对于并行计算一体化研究的影响, 概要的展望了其发展趋势.     

LAMOST观测星表覆盖算法模型

介绍了几种针对LAMOST巡天战略的覆盖算法，在理论上分析这些算法的优劣，并通过模拟的手段证明了分析的结果是正确的。     

带有缓冲区的资源受限调度问题的滚动时域求解算法

研究带有缓冲区的资源受限调度问题,设计了两种使用滚动时域策略的启发式算法TWBA和FWBA,通过依次处理一定量任务,尽可能使得调度所产生的费用最小.为了评估算法性能,进行了大量模拟研究,在不同条件下找出相应的最优的处理周期或者是最优决策时刻,仿真结果表明了新算法在应用中有较好的性能,并且得到比在线算法更优的调度结果.     

有通信冲突的异构系统上的任务调度

在新的系统模型上，提出了一个任务调度算法．该系统模型考虑了通信冲突，即在任何时刻，一个处理器只能接收一条消息，发送一条消息．新的算法包括异构系统中任务优先级的高效排序和基于任务复制的处理器分配两部分．随机产生的任务图和一个具体应用的任务图进行调度试验的结果表明，该算法比已有调度算法的性能有了显著的提高．     

未知网络中可分负载的分布式调度

针对未知网络参数的异构网络系统,提出了一个基于探测技术的多阶段负载调度策略.该策略首先将整个负载分成一些子负载,每个阶段将一个子负载分配给各个处理器.在不知道网络性能参数或网络性能随时间动态变化的情况下,从子负载中分出一小部分负载作为探测片段来探测网络的当前性能参数,作为调度的基础.实验结果表明,该算法的优越性明显.在同样的调度时间复杂度下,其调度结果较已有算法最好时可以缩短调度时间超过20%,平均缩短调度时间约15%.     

路网上异步并行加权A*最短路径算法

图上最短路径问题是一个经典问题,应用广泛.对于路网路径的计算,要求程序能够在有限的时间内找到一条尽量短的路径,且允许运行的时间越长,找到的路径越短.由于传统的最短路径算法在设计时未考虑这一约束条件,故不能满足应用需求.为此提一种APWA*(asynchronous parallelism weighted A*)算法,该算法能够响应用户的中断信号并返回当前找到的最短的路径.在多个地图数据上的实验表明,APWA*能够很好地满足实际需求.     

最大节约原则下单体型推导问题的复杂性

基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题,证明了该问题是NP-hard以及MAX-SNP完全的,从而解决了该问题在计算上的复杂性.这一结果显示,除非P等于NP,否则,该问题不存在多项式时间算法;甚至存在一个常数e> 0,该问题不存在比1 e好的近似算法.     

GROMOS96分子动力学模拟的并行优化算法

介绍了流行的分子动力学软件GROMOS96中的MD算法 ,分析了制约GRO MOS96性能的原因 ,并提出一种优化的算法 ,将邻域原子搜索的时间复杂度从O(N2 )降低到O(NlogN) ;同时并行化了GROMOS96算法 ,并进一步在国产曙光并行机上开发了基于MPI的软件 ,证实了性能的改进     

一种求解点到点的最短路径的高效下界算法（英文）

在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25%左右.     

KD-50-I—E平台的FCD并行计算与交通动态诱导

随着社会和经济的发展,城市交通需求的迅速增长导致了交通拥塞现象日益严重,制约了城市化进程和国民经济的发展.