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

Memory Complexity Analysis on Numerical Programs

作　　者：张云泉[1] 孙家昶[1] 迟学斌[1] 唐志敏[2] 

机构地区：[1]中国科学院软件研究所,北京100080 [2]中国科学院计算技术研究所,北京100080

出　　处：《计算机学报》2000年第4期362-373,共12页Chinese Journal of Computers

基　　金：国家攀登B计划;国家自然科学基金!(69883006);国家"八六三"高技术研究发展计划项目!(863-306-ZT06-02

摘　　要：由于越来越多的技术用于缩小处理器与存储器之间日益加大的速度差距，计算机的存储系统变得日趋复杂．现在，任何一个程序设计者，尤其是数值计算程序的设计者，若不考虑其所用计算平台存储系统的特点是很难获取高性能的．因此仅仅用传统的算法评价方法，从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异，显然是不够的．计算平台存储系统的特点必须在分析算法的复杂性时加以考虑．孙家昶１９９６年首先提出了存储复杂性的概念，提出一个算法的复杂性应包含计算复杂性和存储复杂性，其中的计算复杂性包含传统的时间复杂性和空间复杂性，是一个算法的基本属性；而存储复杂性却是一个随实现的不同而改变的算法属性．用户对算法进行优化的目的即是对算法存储复杂性的不断降低．而若想降低计算复杂性则必须进行新算法的研究．作者试图通过把对算法的存储复杂性分析和数据移动与浮点操作的比值分析相结合，对同一算法的不同实现进行相对精确的评价并对其可能达到的性能进行预测，以便帮助用户进行算法改进和指出可能的改进方向．目前，作者的分析仅限于单处理器的串行算法，对多处理器上的并行算法的分析是下一步的研究方向。Memory systems become more and more complicated with so many efforts on bridging the large speed gap between processor and main memory. It is now difficult to gain high performance from a processor or a large parallel processing systems without considering the specific memory system features. Thus it becomes not enough just to use the time and space complexity to explain why different forms of one algorithm explore so different performance on one same platform. The complexity of memory systems must be incorporated into the analysis of algorithms. In 1996, Sun Jiachang first presented a new concept on memory complexity. It is believed that the complexity of an algorithm should consist of its computational complexity and memory complexity, among them, computational complexity consists of time complexity and space complexity, which are the basic characteristics of algorithm; while memory complexity is a varying characteristic, which will change with different implementations of the same algorithm and different platforms. The purpose of algorithmic optimization is to reduce the memory complexity, while the reduction of computational complexity needs new algorithmic research activity. In this paper, we try to analyze the different implementations of an algorithm and to predict the relative performance differences among them through combining the memory complexity analysis and the data movement/floating point operation ratio analysis. Further analysis with remote communication in parallel processing will be our future work.

关 键 词：存储复杂性 数值计算程序 存储系统 计算机 

分 类 号：O241[理学—计算数学]