数值计算程序的存储复杂性分析

摘要：

由于越来越多的技术用于缩小处理器与存储器之间日益加大的速度差距, 计算机的存储系统变得日趋复杂.现在,任何一个程序设计者,尤其是数值计算程序的设计者,若不考虑其所用计算平台存储系统的特点是很难获取高性能的.因此仅仅用传统的算法评价方法,从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异,显然是不够的.计算平台存储系统的特点必须在分析算法的复杂性时加以考虑.孙家昶1996年首先提出了存储复杂性的概念,提出一个算法的复杂性应包含计算复杂性和存储复杂性,其中的计算复杂性包含传统的时间复杂性和空间复杂性,是一个算法的基本属性; 而存储复杂性却是一个随实现的不同而改变的算法属性.用户对算法进行优化的目的即是对算法存储复杂性的不断降低.而若想降低计算复杂性则必须进行新算法的研究.作者试图通过把对算法的存储复杂性分析和数据移动与浮点操作的比值分析相结合, 对同一算法的不同实现进行相对精确的评价并对其可能达到的性能进行预测, 以便帮助用户进行算法改进和指出可能的改进方向.目前,作者的分析仅限于单处理器的串行算法, 对多处理器上的并行算法的分析是下一步的研究方向.

关键词：算法复杂性、算法优化、存储复杂性、计算复杂性、高性能计算

所属期刊栏目：23

分类号：TP311(计算技术、计算机技术)

资助基金：国家攀登计划69883006;新材料领域项目863-306-ZT06-02-1;中国科学院资助项目69883006

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：363-373