最近两天有幸接受Intel公司的培训。然后培训的时候讲到cache命中的问题。了解到cpu在从memory中load数据的时候其实是将memory中的地址连续的一段数据都load到cache中的,而这时基于这样一个设想:即当要用到的数据附近的数据就是下一次或者下面几次将要进行的操作的数据。。所以将地址连续的一段数据load到cache中,这样将来操作的时候就可以直接从cache而不是内存中取数据,增加cache命中率,减少数据传输的时间。进而提高程序性能。
当时还讲到一个具体的例子,,最典型的就是矩阵加法。。因为矩阵加法必须有二重循环,形式如下:
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
C[i][j] = A[i][j] + B[i][j];
}
}
这是一个不好的实现,因为内层循环变量时j递增时,我们可以具体看看循环里面的操作:
C[j][i]的访问是跳跃式的前进的(stride),比如j = 1时,我们将会访问C[1][i],这样,C[1][i]附近的数据将会被load到cache,但是j递增之后。我们下一个操作访问的数据时C[2][i],它和C[1][i]地址差距为i,这样C[2][i]不一定在缓存中。还得重新到memory中load。减缓了速度。。
相反,我们再看看另外一种实现:
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
C[i][j] = A[i][j] + B[i][j];
}
}
针对此种实现,对于每一次递增的j,内存地址的增加都是挨着的,所以内存访问效率更高,当然程序速度更快。。
以下是本人基于上述两种方法对矩阵加法的实现,并对比给出执行时间的差距:
1.跳跃式访问:
#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#define WIDTH 20000
#define HEIGHT 20000
#define MAX 100
template<typename size>
size** matAdd(size** A, size** B){
/*
size height = sizeof(A)/sizeof(A[0]);
printf("sizeof(A) is :%d\n",sizeof(A));
printf("sizeof(A[0]) is:%d\n",sizeof(A[0]));
printf("height is: %d\n", height);
size width = sizeof(A[0])/sizeof(A[0][0]);
printf("width is :%d\n", width);
*/
size** C = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
C[i] = new size[WIDTH];
}
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
int main(){
typedef int size;
size** A = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
A[i] = new size[WIDTH];
}
srand((int)time(0));
size** B = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
B[i] = new size[WIDTH];
}
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
A[i][j] = rand() % MAX;
B[i][j] = rand() % MAX;
}
}
size** C = matAdd(A, B);
}
执行时间如下所示:
time ./matAdd
real 0m57.507s
user 0m54.718s
sys 0m2.781s
相对比下:连续访问内存实现方式如下:
#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#define WIDTH 20000
#define HEIGHT 20000
#define MAX 100
template<typename size>
size** matAdd(size** A, size** B){
/*
size height = sizeof(A)/sizeof(A[0]);
printf("sizeof(A) is :%d\n",sizeof(A));
printf("sizeof(A[0]) is:%d\n",sizeof(A[0]));
printf("height is: %d\n", height);
size width = sizeof(A[0])/sizeof(A[0][0]);
printf("width is :%d\n", width);
*/
size** C = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
C[i] = new size[WIDTH];
}
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
int main(){
typedef int size;
size** A = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
A[i] = new size[WIDTH];
}
srand((int)time(0));
size** B = new size*[HEIGHT];
for(size i = 0; i < HEIGHT; ++i){
B[i] = new size[WIDTH];
}
for(size i = 0; i < HEIGHT; ++i){
for(size j = 0; j < WIDTH; ++j){
A[i][j] = rand() % MAX;
B[i][j] = rand() % MAX;
}
}
size** C = matAdd(A, B);
}
执行时间如下所示:
time ./matAdd
real 0m22.881s
user 0m20.197s
sys 0m2.680s
由此可见,性能相差一倍有余。这也更加体现出连续访问内存的重要性。。
分享到:
相关推荐
由于多处理器的性能取决于许多以不同方式影响性能的参数,因此在指令执行级使用定时Petri网对基于共享内存总线的多处理器进行建模,并使用已开发的模型来研究处理器随系统中处理器数量的变化而变化。 结果很好地...
AdaptMemBench提供了一个框架来模拟特定于应用程序的内存访问模式。一组模板管理标准计时和测量任务。构建系统适应多面体模型,使框架为潜在的代码优化提供了方便的测试平台。 AdaptMemBench支持实验结果的可重复性...
动态内存管理的问题对无锁动态数据结构的性能尤为关键, 因为多线程环境下的动态内存管理涉及开销... 平衡算法在很大程度上决定内存消耗量, 内存池在高负载下的扩展性也受到它所用的数据结构自身多线程访问性能的影响。
针对当前OrangeFS中所存在的性能瓶颈,讨论分布式文件系统的优化方式,分析文件大小以及文件布局对分布式文件系统吞吐率的影响,提出一种采用共享内存与消息传递相结合的本地数据访问模型,减少了OrangeFS对网络带宽...
比如在不需要物化视图的地方使用的物化视图表,那么会对源表的增删改性能造成影响。 数据库设计准则及方法论全文共5页,当前为第2页。数据库设计准则及方法论全文共5页,当前为第2页。 数据库设计准则及方法论全文共...
提出一种提高访问性能的优先级仲裁策略,按照不同类型的内存访问优先级进行分层仲裁,并通过隐藏bank预充电时延提高了内存访问效率。本方法应用于网络处理器(XD-NP)的可配置SDRAM控制器的设计中,并在FPGA平台上...
云计算实施方法论 云计算的9个特征—来自IBM IT能力以服务形式提供 网络化访问 用户自助服务 提供开放的服务访问和管理接口 持续的服务更新 资源聚合成池 自动化管理与快速交付 弹性扩展 资源使用计量 2 云计算经济...
通过对用户查询负载的分析模块和索引服务管理模块改变传统的由数据库管理员人工管理索引的模式,同时借助于协处理器和内存云技术提高索引服务的性能和灵活性。实验测试结果表明,索引服务机制能够有效地提高索引存储...
算法基于层次分析法(Analytic Hierarchy Process,AHP),通过建立综合评估指标体系,从可用存储空间、可用CPU、可用内存和访问热度四个方面,计算各个存储节点的综合负载,并据此对数据存取进行均衡调度。...
分别是GPU并行的遗传-模拟退火算法,多条马尔可夫链并行的退火算法,基于BLOCK分块的GPU并行模拟退火算法,并通过对GPU端的程序采取合并内存访问,避免bank冲突,归约法等方式进一步提升了性能。实验中选取了11个...
多核处理器遵循以LLC(Last Level Cache,最后一级cache)大小为中心的优化技术,而众核处理器,如Phi、GPU协处理器,则采用较小的cache并以更多的硬件级线程来掩盖内存访问延迟的设计。随着处理核心数量的增长,...
Blog 作为一种新的生活方式、新的工作方式、新的学习方式已经被越来越多的人所接受,并且在改变传统的网络和社会结构:网络信息不再是虚假不可验证的,交流和沟通更有明确的选择和方向性,单一的思想和群体的智慧...
其次, 采用读1写n 的方式优化读性能, 通过master 对 n 的自动调整,保证在存在失效副本的情况下, 写操作的顺利完成; 再次, 保证读写操作与重构操作可以并发进行; 最后, 本算法可容忍n-1 个存储节点失效.
该文件系统基于FUSE框架实现,解决了因磁盘控制器有限,多个内核实例无法同时访问磁盘资源的问题,通过共享内存的方式,保证了通信的稳定,提高了文件系统的效率,进而促进了多个内核的操作系统整体性能的提升。
面向结构体数据布局优化的内存池由于自身的使用特点,在传统的内存管理方式下,扩展内存需要移动数据,代价很高。为了避免移动数据,提高内存池性能,该文设计实现了基于共享内存地址映射技术的零数据移动内存管理...
虚拟机GC垃圾回收收集算法(内存回收方法论) 虚拟机GC垃圾回收收集器(内存回收具体实现) 对象内存分配 虚拟机性能监控与故障处理工具 内存溢出问题及调优 类文件结构 虚拟机类加载机制 编译期编译优化 运行期优化 ...
Memory是一种内存监视工具,能够识别与内存相关的编程错误,例如未初始化内存的访问,对不可寻址内存的访问(包括分配的堆单元之外的堆以及堆下溢和溢出),对释放的内存的访问,两次释放,内存泄漏,并(在Windows...
Memcached在呼叫中心系统中的应用,曾海军,詹舒波,Memcached是一个高性能的分布式的内存对象缓存系统,它通过在内存中缓存数据对象来减少访问数据库的次数,从而提高了获取数据的速度
综上所述,“认我测”在线认证检测系统,率先填补了认证检测领域移动端的空缺,提供了Web浏览器+移动端的双端访问模式,给用户提供了多种访问途径,真正实现了用户和检测机构的随时随地在线下单检测。 关键词:...
网包分类算法HyperSplit采用了二分查找树结构进行查找, 其决策树深度较大, 规则复制较多, 无法保证算法的时间性能。...仿真结果表明, MP2S的平均决策树深度约为HyperSplit的60%, 内存访问次数比HyperSplit降低了约10%。