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

• 作者: 唐志敏 孙家昶 张云泉 迟学斌
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 算法复杂性 算法优化 存储复杂性 计算复杂性 高性能计算
• 年，卷（期）: 2000,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 363-373
• 页数: 11页
• 分类号: TP311
• 字数: 731字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2000.04.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	迟学斌	中国科学院软件研究所	101	634	14.0	21.0
2	张云泉	中国科学院软件研究所	69	542	15.0	21.0
3	唐志敏	中国科学院计算技术研究所	57	942	17.0	29.0
4	孙家昶	中国科学院软件研究所	24	142	6.0	11.0