Memory Complexity Analysis on Numerical Programs
Yun Zhang · Chinese Journal of Computers · 2000
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.