首页 | 本学科首页   官方微博 | 高级检索  
     

数值计算程序的存储复杂性分析
引用本文:张云泉,孙家昶,唐志敏,迟学斌.数值计算程序的存储复杂性分析[J].计算机学报,2000,23(4):362-373.
作者姓名:张云泉  孙家昶  唐志敏  迟学斌
作者单位:1. 中国科学院软件研究所,北京,100080
2. 中国科学院计算技术研究所,北京,100080
基金项目:国家攀登B计划,国家自然科学基金!(69883006),国家“八六三”高技术研究发展计划项目!(863-306-ZT06-02
摘    要:由于越来越多的技术用于缩小处理器与存储器之间的日益加大的速度差距,计算机的存储系统变得日趋复杂.现在,任何一个程序设计者,尤其是数值计算程序的设计者,若不考虑其所用计算平台存储系统的特点是很难获取高性能的.因此公用传统的算法评价方法,从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异,显然是不够的.计算平台存储系统的特点必须在分析算法的复杂性时加以考虑.孙家昶199

关 键 词:存储复杂性  数值计算程序  存储系统  计算机
修稿时间:1999-01-18

Memory Complexity Analysis on Numerical Programs
ZHANG YunQuan,SUN JiaChang,TANG ZhiMin,CHI XueBin.Memory Complexity Analysis on Numerical Programs[J].Chinese Journal of Computers,2000,23(4):362-373.
Authors:ZHANG YunQuan  SUN JiaChang  TANG ZhiMin  CHI XueBin
Abstract: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.
Keywords:algorithm complexity  algorithm optirnization  memory complexity  computational complexity  high performance computing  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号