精华内容
下载资源
问答
  • 时间局部性和空间局部性

    千次阅读 2019-05-29 15:56:22
    在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理。 时间局部性(temporal locality) :被引用过一次的存储器位置在未来会被多次引用(通常在循环中)。 空间...

    在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理。 
    时间局部性(temporal locality) :被引用过一次的存储器位置在未来会被多次引用(通常在循环中)。 
    空间局部性(spatial locality):如果一个存储器的位置被引用,那么将来他附近的位置也会被引用。

    展开全文
  • 局部性原理的一点理解

    千次阅读 2016-01-23 19:02:59
    一个编写良好的计算机程序常常具有良好的局部性。也就是说。它们倾向于引用临近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。这汇总倾向性,就被称为局部性原理,这是一个持久的概念,对硬件和...
        一个编写良好的计算机程序常常具有良好的局部性。也就是说。它们倾向于引用临近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。这汇总倾向性,就被称为局部性原理,这是一个持久的概念,对硬件和软件系统的设计和性能都有着极大的影响。
    

    局部性通常有两种不同的形式:时间局部性空间局部性。在一个具有良好时间局部性的程序中,被引用一次的存储器位置很有可能在接下来时间内再被多次引用。在已给具有良好空间局部性的程序中,若一个存储器位置被引用了一次,那么在接下来时间内将引用附近的一个存储器位置。

    一般而言,优良好局部性的程序比局部性差的程序运行的更快。现代计算机系统的各个层次,从硬件到OS、再到应用程序,它们的设计都利用了局部性。在硬件层,cache的引入就是利用了局部性,将最近被引用的指令和数据项存在cache中,从而提高了对主存的访问速度。在OS级,局部性原理允许使用主存作为虚拟地址空间作为最近被引用块的高速缓存;类似的使用主存来缓存磁盘文件系统中最近被使用磁盘快。在应用程序设计中,Web浏览器将最近被引用的文件放在本地磁盘中,就是利用的时间局部性。
    

    下面是一个简单的函数:

    int sum1(int v[])
    {
        int i, sum = 0;
        int length = sizeof(v);
        for(i = 0; i < length; i++)
            sum += v[i];
        return sum;
    }

    该函数中,变量sum在每次循环迭代时被引用一次,因此对sum来说,有好的时间局部性。对变量v来说,它是一个int类型数组,循环时按顺序访问v[i],因而有很好的空间局部性,但时间局部性不好,因为每个元素只被访问了一次。这就有点像一个程序的时间复杂度和空间复杂度一样,二者是不可兼得的,所以只要满足时间和空间局部性二者之一,就可以说符合程序的局部性原则。

    像上面这样顺序访问一个数组中的每个元素,称为具有*步长为1的的引用模式*,有时称该模式为顺序引用模式。一个连续数组中,每隔k个元素进行访问,称为*步长为k的引用模式*,一般来说,随着步长增加,空间局部性下降。
    

    之前有一篇写展开循环的,通过减少循环的次数来节省运行时间。

    http://blog.csdn.net/sinat_31508159/article/details/50541726

    虽然说展开循环增加了步长,使空间局部性变差,但同时也减少了运行时间,所以说这是维持程序性能的一个折中选择。

    下面是一个读取二位数组的例子:

    int sum2(int array[][])//假设是一个 M*N 的二维数组
    {
        int i, j, sum = 0;
        for(i = 0; i < M; i++)
        {
            for(j = 0; j < N; j++)
                sum += array[i][j];
        }   
        return sum;
    }

    该函数对一个二维数组求和,双重嵌套循环按照行有限顺序读取数组中的元素。该函数有很好的空间局部性,因为它按照数组被存储的的行优先顺序来访问数组。
    这里写图片描述

    一个数组a[3][4]存储着1~12。虽然数组是二维的,但仍然是按照顺序存储在存储器中的。按行优先顺序读取该数组时,读出数据为1,2,3,4……11, 12,数据对应的存储位置分别为0, 1, 2, 3…… 恰好相当于读取一个顺序文件,这样有良好的空间局部性。

    有时一些很小的改动会对程序产生很大的影响。下面的代码仅仅将行优先改为列优先:
    
    int sum2(int array[][])//假设是一个 M*N 的二位数组
    {
        int i, j, sum = 0;
        for(j = 0; i < M; i++)
        {
            for(i = 0; j < N; j++)
                sum += array[i][j];
        }   
        return sum;
    }

    以列优先读取时,顺序是这样的:1, 5, 9, 2, 6, 10……8, 12
    对应存储位置分别为:0, 4, 8, 1, 5, 9…… 7, 11

    这个小改动不会改变程序的运行结果,但是改为列优先后,函数sum1按列顺序遍历数组,这样一来,相当于由步长为k = 1的引用模式变成了步长为k = 4的引用模式,导致空间局部性变差。
    

    原因:是C数组在存储器中是按行顺序来存放的。

    小结:
    
    • 重复引用同一个变量的程序有良好的时间局部性。
    • 对于具有步长为k的引用模式的程序来说,步长k越小,空间局部性越好。步长为1的程序有很好的空间局部性。以上面按列读取数组为例,在存储器以大步长跳来跳去的程序空间局部性会很差。
    • 对于取指令来说,循环有很好的时间和空间局部性。循环体越小,循环迭代次数越多,局部性越好。

    小结引自CSAPP第六章6.2.3局部性小结

    展开全文
  • 时间空间局部性原理

    万次阅读 2017-02-21 23:47:55
    今天在工作中听到同事说到了时间,,空间局部性原理,这是一个从来没有听到过的名词,所以自己上网查找学习了一下,在此做个总结。一、定义 在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续...

    今天在工作中听到同事说到了时间,,空间局部性原理,这是一个从来没有听到过的名词,所以自己上网查找学习了一下,在此做个总结。

    一、定义
    在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理。
    时间局部性(temporal locality)
    时间局部性指的是:被引用过一次的存储器位置在未来会被多次引用(通常在循环中)。
    空间局部性(spatial locality)
    如果一个存储器的位置被引用,那么将来他附近的位置也会被引用。

    二、例子

    int a[N] = {0, 1, 2, 3, 4};
    int sum = 0;
    
    for (int i = 0; i < 5; ++i)
    {
        sum = sum + a[i];
    }

    在这个例子中,变量在内存中的存储结构如下:

    这里写图片描述
    可以看出从a[0]到a[4]的地址位是连续的,而且程序中访问这些变量频率较高,所以对与a来说,其具有良好的空间局部性,但是每个a成员只被访问一次,所以并不具有良好的时间局部性。
    但是对于变量sum来说,其由于其是一个标量,也就是说通过其地址只能得到一个值,故其不具有良好的空间局部性,但是由于其访问频率较高,所以有良好的时间局部性。
    通过以上结论可以推出,对于向量a来说,如果其访问顺序和存储顺序一致,那么a的变量之间距离太远,那么其空间局部性越差,因为CPU没办法在其附近找到其他变量,所以空间局部性和a的步长有很大的关系,步长越长,空间局部性越差。
    同理,如果一个变量被访问的频率越高,其时间局部性就越好。

    取指令的局部性
    指令存子啊存储器中,CPU要读取指令必须取出该指令,所以就可以评价取指令的局部性。
    在for循环中,循环体内的指令多次被执行,所以有良好的时间局部性,
    循环体中的指令是按顺序执行的,有良好的空间局部性(指令在存储器中是顺序存放的)。

    小结
    评价局部性的简单原则:
    1.重复引用同一个变量具有良好的时间局部性。
    2.对于步长位k的引用程序,步长越小,空间局部性越小。步长为1的引用具有良好的空间局部性。k越大,空间局部性越差。
    3.对于取指令来说、循环有良好的时间和空间局部性。

    参考资料:(http://www.cnblogs.com/yanlingyin/)

    展开全文
  • 局部性原理的一点点理解

    千次阅读 2017-02-14 21:40:24
    局部性原理是指CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋于聚集在一个较小的连续区域中。 三种不同类型的局部性: 时间局部性(Temporal Locality):如果一个信息项正在被访问,那么在...

    书本概念:

    局部性原理是指CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋于聚集在一个较小的连续区域中。

    三种不同类型的局部性:

    时间局部性(Temporal Locality):如果一个信息项正在被访问,那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。

    空间局部性(Spatial Locality):在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。

    顺序局部性(Order Locality):在典型程序中,除转移类指令外,大部分指令是顺序进行的。顺序执行和非顺序执行的比例大致是5:1。此外,对大型数组访问也是顺序的。指令的顺序执行、数组的连续存放等是产生顺序局部性的原因。


    先抛开晦涩的书本概念,谈谈缓存。我们先将计算机分为一下这些层次:

    寄存器 64位

    一级缓存L1 4×64KB

    二级缓存L2 4×256KB

    三级缓存L3 8MB

    内存 8GB

    磁盘 1TB

    可以看到这些层次一个比一个更大。寄存器,既是CPU的工作台,是存放计算数据的地方CPU要工作了,它需要数据或者地址,从哪里来?先从一级缓存里面找,找不到就从二级缓存里面找,依次类推。假如CPU到磁盘才有,那么这个数据就会存入内存,再存入三级缓存、二级缓存、一级缓存,最后存入寄存器,CPU用它来计算了。所以说,可以这么看, L1是寄存器的缓存,L2是L1的缓存,依次这样下去,下面一层是上面一层的缓存。


    现在来讲局部性原理:

    CPU的工作要高速,我们希望CPU需要的数据更多的就在L1里面,一找就找着。不希望更多的跑到下面内存乃至磁盘里面去找,这样会花更多的时间。所以当CPU用了一个数据,计算机会遇见性的存入其他等会儿CPU可能会用到的数据到L1、L2、L3内存,用到的可能性越大,就能存到越接近寄存器的层次。这也才是缓存的真正意义。那么,计算机怎样才能判断一个数据接下来可能被用到?
    这就要用到两种不同类型的局部性:
    时间局部性:如果一个信息项正在被访问,那么在近期它很可能还会被再次访问。这当然是正确的,用过的数据当然可能再次被用到。
    空间局部性:在最近的将来将要用到的信息很可能与现在正在使用的信息在空间地址上是临近的。正在使用的这个数据地址旁边的数据,当然也是很可能被用到的,比如说数组。

    如有错误之处欢迎指点。



    展开全文
  • 通过这两个方面,我想表达的意思是,一段程序的执行效率,是很难从表面现象得出结论的,至少从一些简单的层面,如代码的长度是几乎难以说明任何问题——因此一定要进行Profiling才能做到有效的优化。而现在,我们...
  • 什么全局变量,局部变量,静态局部变量,静态全局变量 到这里,我们就可以很容易区分上面的变量类型了。实际上这里只是换了一种说法: 全局:具有文件作用域的变量 静态:具有静态存储期或内部链接属性 局部:具有...
  • !function($){}(window.jQuery) 是什么意思

    千次阅读 2015-07-24 18:29:43
    function($){}(window.jQuery)是什么意思. 求详细解释。 JavaScript code 就是返回值取反,等价(function(){})()匿名函数直接执行了,只是用取反的标志可以活力匿名函数左右的括号!!? 1 2 3 4 5 ...
  • 就是误差曲面局部凹陷点。学过函数曲线的极小值和最小值的概念吧,局部最佳和...事实上只要是随机搜索的算法,都会出现这种情况,只是可能的大小不同罢了。可以使用全局寻优能力强的先行搜索,再用局部搜索能力强的算
  • 分布式是什么意思

    千次阅读 2014-08-20 14:51:48
    什么是分布式智能? NI LabVIEW 8的分布式智能结合了相关的技术和工具,解决了分布式系统开发会碰到的一些挑战。更重要的是,NI LabVIEW 8的分布式智能提供的解决方案不仅令这些挑战迎刃而解,且易于实施。LabVIEW 8...
  • 图像局部不变特征描述

    千次阅读 2015-06-13 02:04:09
    图像局部不变特征描述chapter 2 2.2.1 multi scale and multi resolution (size of image) pyramid – multi resolutionscale space – same resolution – 图像局部结构可以用简单形式在不同尺度上描述出来2.2.2 ...
  • 本节将实数域上的完备局部紧致推广到欧几里得空间上的向量上. 0 首先回忆几个概念: (i) 收敛 设{ak}为一数列,如果: 则称{ak}收敛于a,记做: (ii)柯西列 柯西列是满足: ...
  • 企业中的设计研发过程是按照从整体到局部逐步细化的设计路线展开,而生产制造等过程是按照从局部到整体的制造、装配过程来进行,而企业的最终产品正是这两个从不同路线和领域展开的过程连接的结果。 处理业务之间...
  • slam是什么意思?一文带你读懂SLAM

    万次阅读 2018-09-17 14:11:10
    SLAM可以快速构建局部3D地图,并与地理信息系统(GIS)、视觉对象识别技术相结合,可以辅助无人机识别路障并自动避障规划路径,曾经刷爆美国朋友圈的Hovercamera无人机,就应用到了SLAM技术。   无人驾驶领域...
  • 2 模块局部数据结构测试; 3 模块边界条件测试; 4 模块中所有独立执行通路测试; 5 模块的各条错误处理通路测试。; IT是集成测试,Integration Test 集成测试阶段是以黑盒法为主,在自底向上集成的早期,...
  • LBP是一种针对灰度图像任意单调变换(monotonic transformation)具有不变的鲁棒特征算子。除了鲁棒外,另一个突出特点就是计算量小,实现时只需在很小的邻域内使用少量的算子和查询表。
  • 在软件测试中,UT,IT,ST,UAT分别是什么意思

    万次阅读 多人点赞 2018-08-09 14:34:27
    2、模块局部数据结构测试; 3、模块边界条件测试; 4、模块中所有独立执行通路测试; 5、模块的各条错误处理通路测试。; IT(集成测试,Integration Test): 也称系统集成测试(System Integration Test)或结合...
  • 1. 什么是注解(百度百科) 注解,可以看作是对 一个 类/方法 的一个扩展的模版,每个 类/方法 按照注解类中的规则,来为 类/方法 注解不同的参数,在用到的地方可以得到不同的 类/方法 中...
  • 印刷行业中过UV是什么意思?

    千次阅读 2008-11-25 10:36:00
    (包括全面上光及局部上光),多数采用此种方式。它的投资额较小,且多数为上 光厂所投资,如此印刷公司不必投资,而上光厂因为设备可以发挥效率而较划算。 缺点为生产过程长,且品质不稳定。又因传统平版印刷使用...
  • 局部特征

    万次阅读 2012-12-24 16:18:14
    局部特征(1)——入门篇  局部特征 (local features),是近来研究的一大热点。大家都了解全局特征(global features),就是方差、颜色直方图等等。如果用户对整个图像的整体感兴趣,而不是前景本身感兴趣的话...
  • 在程序开发中,特别是网站类开发,会接触到单点登录(SSO),什么是单点登录?,单点登录(SSO)有什么用?下面软币网小编来来介绍一下: 一、什么是单点登录? 单点登录的英文名叫做:Single Sign On(简称SSO)。 ...
  • Java中static为什么不能修饰局部变量?

    千次阅读 2017-12-15 20:49:22
    Java中static为什么不能修饰局部变量? 与c/c++不同
  • 并且对该环境模型的动态更新能够随时进行校正,局部规划方法将对环境的建模与搜索融为一体,要求机器人系统具有高速的信息处理能力和计算能力,对环境误差和噪声有较高的鲁棒,能对规划结果进行实时反馈和校正,...
  • div id与div class什么意思用法讲解

    千次阅读 2018-07-05 11:31:18
    div id与div class什么意思?div id和div class用法有什么讲究呢?在div、span、p标签、h1、h2等标签中看见id和class使用,id和class是非常常用的标签内属性。&lt;div id="header"&gt;&lt;/...
  • 局部图像处理

    千次阅读 2017-11-23 20:29:54
    局部特征(1)——入门篇  局部特征 (local features),是近来研究的一大热点。大家都了解全局特征(global features),就是方差、颜色直方图等等。如果用户对整个图像的整体感兴趣,而不是前景本身感兴趣的话,...
  • html中div id与div class什么意思用法讲解

    万次阅读 多人点赞 2017-09-06 14:42:28
    div id与div class什么意思?div id和div class用法有什么讲究呢? 在div、span、p标签、h1、h2等标签中看见id和class使用,id和class是非常常用的标签内属性。 div id="header">div> div class="menu">div>...
  • 本文提出了一种利用不断调大学习率的方法试图跳出SGD优化过程中的局部极小值或者鞍点的方法,并提出了两种具体的方法:随机漫步起跳法和历史最优起跳法,实验证明相对常规优化方法有一定性能提升。
  • 在AlexNet中LRN 局部响应归一化的理解

    万次阅读 多人点赞 2018-03-03 14:32:59
    二、为什么要有局部相应归一化(Local Response Normalization)? 三、LRN计算公式的介绍 Hinton在2012年的Alexnet网络中给出其具体的计算公式如下:   这个公式中的a表示卷积层(包括卷积操作...
  • 在我的上一篇博客 深入理解Java中为什么内部类可以访问外部类的成员 中, 通过使用javap工具反编译内部类的字节码, 我们知道了为什么内部类中可以访问外部类的成员, 其实是编译器在编译内部类的class文件时,偷偷...
  • Fluent截取局部

    千次阅读 2020-11-23 20:54:54
    fluent中截取局部面一、正常create plane二、bounded 建立局部面三、create iso/surface四、在画网格时,就在需要的地方建立面 在使用fluent模拟时,我们经常需要对某一个面监测或者计算某一个面的物理量,直接...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 113,789
精华内容 45,515
关键字:

局部性是什么意思