并行文件系统的特点 计算机科学基础知识(一)The Memory Hierarc(3)

1、数据访问的局部性分析

int sumvec(int v[N])
{
  int i, sum = 0;
  
  for (i = 0; i < N; i++)
    sum += v[i];
    
  return sum;
}

i和sum都是栈上的临时变量，由于i和sum都是标量，不可能表现出好的空间局部性，不过对于sumvec的主loop，i、sum以及数组v都可以表现出很好的时间局部性。虽然，i和sum没有很好的空间局部性，不过编译器会把i和sum放到寄存器中，从而优化性能。数组v在loop中是顺序访问的，因此可以表现出很好的空间局部性。总结一下，上面的程序可以表现出很好的局部性。

按照上面的例子对数组v进行访问的模式叫做stride-1 reference pattern。下面的例子可以说明stride-N reference pattern：

int sumarraycols(int v[M][N])
{
  int i, j; sum = 0;
  
  for(j = 0; j < N; j++)
    for (i = 0; i < M; i++)
      sum += a[i][j];
      
  return sum;
}

二维数组v[i][j]是一个i行j列的数组，在内存中，v是按行存储的，首先是第1行的j个列数据，之后是第二行的j个列数据……依次排列。在实际的计算机程序中，我们总会有计算数组中所有元素的和的需求，在这个问题上有两种方式，一种是按照行计算，另外一种方式是按照列计算。按照行计算的程序可以表现出好的局部性，不过sumarraycols函数中是按照列进行计算的。在内循环中，累计一个列的数据需要不断的访问各个行，这就导致了数据访问不是连续的，而是每次相隔N x sizeof（int），这种情况下，N越大，空间局部性越差。

2、程序访问的局部性分析

对于指令执行而言，顺序执行的程序具备好的空间局部性。我们可以回头看看sumvec函数的执行情况，这个程序中，loop内的指令都是顺序执行的，因此，有好的空间局部性，而loop被多次执行，因此同时又具备了好的时间局部性。

3、经验总结

我们可以总结出3条经验：

（1）不断的重复访问同一个变量的程序有好的时间局部性

（2）对于stride-N reference pattern的程序，N越小，空间局部性越好，stride-1 reference pattern的程序最优。好的程序要避免以跳来跳去的方式来访问memory，这样程序的空间局部性会很差

（3）循环有好的时间和空间局部性。循环体越小，循环次数越多，局部性越好

四、存储体系

1、分层的存储体系

现代计算机系统的存储系统是分层的，主要有六个层次：

（1）CPU寄存器

（2）On-chip L1 Cache （一般由static RAM组成，size较小，例如16KB）

（3）Off-chip L2 Cache （一般由static RAM组成，size相对大些，例如2MB）

（4）Main memory（一般是由Dynamic RAM组成，几百MB到几个GB）

（5）本地磁盘（磁介质，几百GB到若干TB）

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-87804-3.html