非规则计算是许多重要科学应用的主要的问题，计算流体力学、计算分子动力学等经典计算科学中的非规则计算问题已经成为高性能计算重要的挑战性问题并得到广泛的研究。目前生物信息学和计算社会学等新兴的计算科学逐渐成为高性能计算应用的重要课题，而这类应用中最明显的特征就是大量的非规则计算。非规则计算问题表现为算法和程序的计算依赖关系和访存模式的非规则，从而其局部性和并行性受到限制，而且随着计算机体系结构向大规模片上多核、更深存储层次的方向发展，使得对非规则计算问题的局部性和并行性挖掘问题变得尤其突出和更加重要。　　 本论文围绕生物信息学和计算社会学中两个重要的核心算法—动态规划和图遍历算法—在现代高性能计算机体系结构上展开如何开发局部性和并行性方法的研究。结合计算机体系结构特异性和多样性的特点，论文首先提出在高性能计算机上分析和设计高性能算法的基本方法、框架和模型，然后针对不同的体系结构提出了有效的策略优化动态规划和图遍历算法的局部性和并行性，同时给出了全面系统的性能评价，是国内外首次在类似IBM Cyclops64众核体系结构上的高性能算法研究。其中主要工作包括：　　 ●系统总结了Cache存储层次体系结构的高性能算法设计模型和方法，结合体系结构向多核发展的趋势，提出了一种新的并行算法设计技术-延迟容忍模型。　　 ●分析动态规划算法中的计算依赖关系，设计了一种新的数据依赖关系转换策略，变换后的依赖关系更加适用于改善计算中局部性和并行性。　　 ●对变换计算依赖关系后的动态规划矩阵分块，采用分而治之的方法，首次提出了一种Cache无关算法用于计算动态规划矩阵，并证明了其Cache复杂性是最优的。　　 ●大规模机群系统和多核代表了两种高性能计算体系结构的主流，网络延迟和片外存储访问延迟分别是大规模机群系统和众核体系结构的性能瓶颈。基于提出的延迟容忍算法模型，设计的并行算法获得了计算和通信、计算和存储访问的重叠，有效地隐藏了网络通信和片外存储访问的开销，从而提高并行算法在曙光4000和IBM Cyclops64上的可扩展性。　　 ●大规模图分析问题中的典型实例是图遍历，由于其极少的局部性/数据重用、动态非连续存储访问和细粒度并行的特点，很难在通用的体系结构上获得高性能，甚至会出现负加速比。在新的众核体系结构上，提出构造非规则存储访问中即时局部性的新技术，并基于延迟容忍模型隐藏构造局部性开销。同时，利用开发的并行性和体系结构支持的细粒度同步减少同步开销。在IBM Cyclops64160核平台上的实验结果证明了新的优化技术的有效性，其性能也优于其他多线程体系结构如Sun Niagara和Cray MTA-2。