`

关于计算机Cache的一道效率分析题

    博客分类:
  • C++
阅读更多
某型CPU的一级数据缓存大小为16K字节,cache块大小为64字节;二级缓存大小为256K字节,cache块大小为4K字节,采用二路组相联。经测试,下面两段代码运行时效率差别很大,请分析哪段代码更好,以及可能的原因。
为了进一步提高效率,你还可以采取什么办法?
A段代码:
int matrix[1023][15];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < 1023; i++)
   for(j = 0; j < 15; j++)
      sum += matrix[i][j] + tmp;
B段代码 :
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++)
   for(j = 0; j < 1025; j++)
      sum += matrix[j][i] + strlen(str);
A段代码效率要远远高于B段代码,原因有三:
1、  
B 效率低最要命的地方就是每次都要调用strlen()函数,这是个严重问题,属于逻辑级错误。假设A的两层循环都不改变,仅仅是把A的那个循环里面的 temp换成strlen()调用,在Windows 2000 (Intel 双) 下测试,竟然是A的执行时间的3.699倍。(这里没有涉及不同CPU有不同的Cache设计)仅仅是这一点就已经说明B段代码垃圾代码。
2、
       这也是一个逻辑级的错误。在这里我们再做个试验,A、B段代码分别采用大小一样的数组[1023][15]、[1023][16]、[1023][17],只是在循环上采取了不同的方式。两者在运行时间上也是有很大差异的了。B的运行时间大概是A的1.130倍。
       那么这是因为什么呢?其实也很简单,那就是A段代码中的循环执行语句对内存的访问是连续的,而B段代码中的循环执行语句对内存的访问是跳跃的。直接降低了B代码的运行效率。
       这里不是内层循环执行多少次的问题,而是一个对内存访问是否连续的问题。
3、
A的二维数组是[1023][15],B的二维数组是[1027][17],在这里B段代码有犯了一个CPU级错误(或者是Cache级的错误)。
因为在Cache中数据或指令是以行为单位存储的(也可以说是Cache块),一行又包含了很多字。如现在主流的设计是一行包含64Byte。每一行拥有一个Tag。因此,假设CPU需要一个标为Tag 1的行中的数据,它会通过CAM对Cache中的行进行查找,一旦找到相同Tag的行,就对其中的数据进行读取。
A的是15 *4B = 60B,一个Cache行刚好可以存储。B的是17*4B = 68B,超过了一个Cache行所存储的数据。很明显17的时候命中率要低于15的时候。
现在我们先不管A、B的循环嵌套的顺序,仅仅拿A段代码来做个试验,我们将会分三种情况来进行:
[1023][15]           [1023][16]     [1023][17]
运行结果并没有出乎意料之外 17 的时候的运行时间大概是 15 的时候的1.399倍,除去有因为17的时候多执行循环,17/15 = 1.133 。进行折算,17的时候大概是15的时候的1.265倍。
16的时候的执行时间要比15的时候的执行时间要短,因为是16的时候,Cache命中率更高。16/15 = 1.066 ,而15的执行时间却是16的1.068倍,加上16多执行的消耗,进行折算,15的时候大概是16的时候执行时间的1.134倍。
因为A段代码是15,而B段代码是17,在这一点上B段代码的效率要低于A段代码的效率。这是一个CPU级的错误(或者是Cache级的错误),这里涉及到Cache的块大小,也就涉及到Cache命中率,也就影响到代码效率。
不再假设什么,仅仅对A段和B段代码进行测试,B段代码的执行效率将是A段代码执行效率的3.95倍。当然最大的罪魁祸首就是B中的重复调用strlen()函数。后面两个错误告诉我们当需要对大量数据访问的时候,一定要注意对内存的访问要尽量是连续而且循环内层的访问接近Cache的块大小,以提高Cache的命中率,从而提高程序的运行效率。 
所以可以对代码进行一下修改:
#define XX    15  
#define YY    1023
int matrix[XX][YY];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < XX; i++)
   for(j = 0; j < YY; j++)
      sum += matrix[i][j] + tmp;
这个程序仅仅是把数组的声明给颠倒了一下,循环也颠倒了一下,看起来和运行起来和上面给出的A段代码没有多大的区别。但是如果当XX很小,比如:8,那么这段程序和给出的A段代码就有区别了。这是因为这样做可以提高Cache的命中率。
分享到:
评论
2 楼 shansun123 2009-05-11  
mengyou0304 写道

这是尹宝玲老师出的题吧?
我个人觉得就现阶段而言 稳定性比效率要高很多

而且这些东西在虚拟机上是不是可以由专门的程序来优化?

孟老大?
1 楼 mengyou0304 2009-05-11  
这是尹宝玲老师出的题吧?
我个人觉得就现阶段而言 稳定性比效率要高很多

而且这些东西在虚拟机上是不是可以由专门的程序来优化?

相关推荐

    计算机组成原理试题0000

    每一套试题都可能覆盖这些知识点,并通过不同形式的题目来测试学生的理解和应用能力,如选择题、填空题、简答题和综合题。解答这些试题不仅可以帮助学生复习理论知识,还能锻炼他们分析问题、解决问题的能力。通过...

    (完整word)计算机组成原理复习题.doc

    在浮点数运算部分,题目给出了一道关于浮点数加法的计算题。浮点数通常由阶码(也叫指数)和尾数(也叫 mantissa)两部分组成,题目中采用了双符号位的阶码和单符号位的尾数表示。浮点加法步骤包括对阶、尾数求和、...

    02318计算机组成原理202008.zip

    在准备考试的过程中,不仅要独立完成每一道题目,还要尝试分析答案的合理性,对比不同解题策略的优劣,以培养独立思考和批判性思维。此外,历年真题的复盘和总结也是提升学习效果的关键步骤,这将帮助考生更好地应对...

    软件水平考试《程序员》习题及答案.docx

    本资源摘要信息是关于软件水平考试《程序员》的习题及答案,涵盖了多方面的计算机科学和信息技术知识。 知识点1:Word文档编辑 在Word的编辑状态,文档窗口显示出水平标尺,拖动水平标尺上沿的“首行缩进"滑块,则...

    计算机系统结构教程

    此题未给出详细解答内容,但从题干可以看出这是一道涉及计算机系统结构基础知识的问题。 ##### 1.2 解析 本题考察了计算机系统中的缓存层次结构。题目给出了不同级别的缓存访问时间,并明确指出“第一级是最低的...

    2007年上信息系统项目管理师试题

    - **例题**:给出了一道关于考试日期的选择题示例,要求考生根据题目要求选择正确的选项并在答题卡上正确填涂。 - **解析**:通过这个示例,可以了解到考试的基本格式以及如何正确作答。 ##### 3. **考试知识点**...

    825 真题1

    【标题】825真题1中的主要知识点涵盖了计算机科学中的多个重要领域,包括数据结构、算法、缓存(Cache)以及LeetCode平台上的编程挑战。 【描述】825真题1可能是一道综合性的编程题目,它要求考生不仅理解并应用...

    电子技大学考研

    在使用这份资料时,考生应当结合教材和课堂笔记,对每一道题目进行深入理解和分析。不仅要知道正确答案,还要理解为什么这个答案是正确的,以及错误答案的误区在哪里。同时,考生可以通过解答过程来检验自己对知识点...

    IT笔试资源

    #### 三、阿里巴巴2014年校招笔试题(北京站)分析 阿里巴巴在北京站的笔试题同样侧重于以下几个关键领域: - **C++编程**:测试候选人在C++语言上的熟练程度,包括模板、异常处理等内容。 - **Java开发**:重点...

Global site tag (gtag.js) - Google Analytics