您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

CPU中的高速缓存与置换算法

时间:2020-05-25 13:38:22  来源:  作者:

早期计算机仅限于固定用途的程序,程序是固定在电路板上的,修改程序的话,需要重新设计电路,冯诺依曼体系确立了通用的计算机结构。

1.2 冯诺依曼体系概述

CPU中的高速缓存与置换算法

 

  • 输入设备:用于完成数据的接收,将数据送入到运算器中
  • 控制器:控制器是整个计算机的指挥控制中心,通过向其他设备发出控制信号来控制、控制计算机,使其能自动、协调地工作。
  • 运算器:在控制器的统一控制下,负责对数据进行加工、完成各种运算,如算术运算、逻辑运算、位移、比较等。其数据取自存储器,运算结果又内送往存储器。
  • 存储器:计算机系统中用于保存信息的记忆设备,存放计容算机中所有数据的场所
  • 输出设备:将运算结果输出、展示给用户
  • 控制器和运算器共同构成了中央处理器(cpu)

根据冯诺依曼体系构成的计算机,必须具有如下功能:

  • 能够把需要的程序和数据送至计算机中
  • 能够长期记忆程序、数据、中间结果及最终运算结果的能力
  • 能够具备算术、逻辑运算和数据传送等数据加工处理的能力
  • 能够按照要求将处理结果输出给用户

2. 现代计算机体系

由于cpu的运算速率远远高于存储器,因此cpu经常空转等待数据的传输,造成资源的浪费,这种现象被叫做冯诺依曼瓶颈。

现代计算机在冯诺依曼体系结构的基础上进行了修改,主要是为了解决cpu与存储设备之间的性能差异问题。

CPU中的高速缓存与置换算法

 

现代计算机体系中的cpu由 高速存储器 + 运算器 + 控制器构成。

存储器被拆分成两部分:高速存储器和低速存储器。高速存储器包括内存、寄存器等,用于处理运算过程中的数据存储。低速存储器包括磁盘、磁带等,用于存储需要长期保存的设备,现代计算机结构可以理解为以存储器为核心的结构。

3. 计算机存储器

3.1 存储器的分类

按照存储介质来划分,存储器可分为:

  • 半导体存储器 (半导体元器件组成的存储设备)
  • 磁存储器(磁性材料构成的存储设备)

按照存取方式来划分,存储器可分为:

  • 随机存储器(随机读取、与位置无关)
  • 串行存储器(与位置有关,按顺序查找)
  • 只读存储器(只读不写)

3.2 存储器的层次结构

选择存储器时,一般从读写速度、存储容量、价格三个维度来考量。相同的价格下,读写速度越快越好,存储容量越大越好。

计算机中的存储设备根据成本考虑划分为三个层次:

1 缓存

cpu中的寄存器以及高速的缓存,速度最快,成本最高。

2.主存

计算机中的内存条,速度适中,成本适中。

3.辅存

U盘、硬盘等设备,速度最慢,成本最低。

存储器的层次结构如下图所示:

CPU中的高速缓存与置换算法

 

cpu可以直接往高速缓存、主存中读写信息,高速缓存和主存之间可以相互读写信息(缓存信息的置换),主存可以往辅存读写信息。

3.3 高速缓存的置换算法

为了解决主存速度不足的问题,在cpu和主存之间增加了一层速度快、容量小的缓存。程序经常访问的内存,一般存在于一个较小的连续区域中,因此只需要把这段内存中的数据放置到高速缓存中,即可大大提升cpu运转效率。

衡量高速缓存效率的常用指标有缓存命中率和访问效率。

缓存命中率,侧重于访问缓存次数与总访问次数的比例,计算公式如下:

缓存命中率 = 缓存取数据次数 / (缓存取数据次数 + 内存取数据次数)

访问效率,侧重于访问缓存耗时与平均访问时间的比例,计算公式如下:

平均访问时间 = 缓存命中率 × 访问缓存耗时 + (1 - 缓存命中率) × 访问内存耗时 访问效率 = 访问缓存耗时 / 平均访问时间

良好的缓存置换算法能够大大提升缓存的访问效率,常用的缓存置换算法有:

  • 先进先出算法(FIFO)
  • 最不经常使用算法(LFU)
  • 最近最少使用算法(LRU)

3.3.1 FIFO 先进先出算法

  • 原理: FIFO算法,将缓存看做一个先进先出的队列,优先替换掉最先进入队列的字块
  • 示意图:

3.3.2 LFU最不经常使用算法

  • 原理 LFU算法,额外记录了字块的使用频率,优先替换掉最不经常使用的字块
  • 示意图

3.3.3 LRU 最近最少使用算法

  • 原理 优先替换最长时间未被使用的字块,有多种实现方法,一般使用双向链表,把当前访问节点放到链表头部,当链表空间满了之后,最先删除链表尾部的元素。
  • 示意图

3.3.4 缓存算法的通用性

以上算法不仅适用于cpu高速缓存的实现,当我们存在高速设备与低速设备需要进行数据交互的时候,也可以借鉴这部分的实现,比较常用的一种场景是,程序读取硬盘中的数据,例如数据库、文件等,可以将部分数据,缓存到内存中,提升访问效率。

4. 置换算法JAVA模拟实现

4.1 通用代码

定义通用缓存接口,具有存值、取值两个功能

public interface Cache<E> {
    /**
     * 从缓存中获取元素
     * @param key 缓存键
     * @return 缓存数据
     */
    E get(String key);

    /**
     * 往缓存中插入数据
     * @param key 缓存键
     * @param value 缓存值
     */
    void put(String key,E value);
}

置换算法底层依靠双向链表来实现,采用双向链表的原因是,双向链表能够很简单的实现:获取头部节点、获取尾部节点、增删头部节点、增删尾部节点、中间插入节点、中间删除节点等功能。

依托于双向链表,能够很方便的实现队列、栈等线形数据结构。

关于链表的基础知识,可以查看另一篇文章: 数据结构基础-链表(java实现)

双向链表代码实现如下:

public class DoubleLinkedList<E> {
    static class Node<E> {
        /**
         * 键
         */
        private String key;
        /**
         * 值
         */
        private E value;

        public Node(String key, E value) {
            this.key = key;
            this.value = value;
        }

        /**
         * 指向前一个节点
         */
        private Node<E> prev;
        /**
         * 指向后一个节点
         */
        private Node<E> next;

        public String getKey() {
            return key;
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return String.format("{%s:%s}", key, value.toString());
        }
    }

    /**
     * 链表容量
     */
    private final int capacity;
    /**
     * 链表头部
     */
    private Node<E> head;
    /**
     * 链表尾部
     */
    private Node<E> tail;
    /**
     * 当前元素个数
     */
    private int size;

    public DoubleLinkedList() {
        this(Integer.MAX_VALUE);
    }

    public DoubleLinkedList(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 添加头部节点
     *
     * @return 添加后的节点信息
     */
    public Node<E> addHead(Node<E> node) {
        if (size == capacity) {
            throw new IllegalArgumentException("链表空间已满");
        }
        if (head == null) {
            // 处理当前不存在节点的情况,将当前节点设置为头节点、尾节点
            head = node;
            tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;
        }
        size++;
        return node;
    }

    /**
     * 添加尾部节点
     *
     * @return 添加后的节点信息
     */
    public Node<E> addTail(Node<E> node) {
        if (size == capacity) {
            throw new IllegalArgumentException("链表空间已满");
        }
        if (tail == null) {
            tail = node;
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
        return node;
    }

    /**
     * 删除头部节点
     *
     * @return 被删除的头部节点数据
     */
    public Node<E> delHead() {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        Node<E> resultNode = head;
        if (head.next == null) {
            tail = null;
            head = null;
        } else {
            head.next.prev = null;
            head = head.next;
        }
        size--;
        return resultNode;
    }

    /**
     * 删除尾部节点
     *
     * @return 被删除的尾部节点数据
     */
    public Node<E> delTail() {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        Node<E> resultNode = tail;
        if (tail.prev == null) {
            tail = null;
            head = null;
        } else {
            tail.prev.next = null;
            tail = tail.prev;
        }
        size--;
        return resultNode;
    }

    /**
     * 删除任意节点
     *
     * @return 删除的节点数据
     */
    public Node<E> delNode(Node<E> node) {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        if (node == null) {
            // 默认删除尾部节点
            node = tail;
        }
        if (node.equals(tail)) {
            return delTail();
        } else if (node.equals(head)) {
            return delHead();
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
            return node;
        }
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("DoubleLinkedList: ");
        Node<E> node = head;
        while (node != null) {
            stringBuilder.Append(node.toString());
            if (node != tail) {
                stringBuilder.append("-->");
            }
            node = node.next;
        }
        return stringBuilder.toString();
    }

4.2 FIFO 先进先出算法实现

实现思想:

  • hashMap维护键、缓存节点之间的关系
  • 双向链表维护缓存队列,当容量耗尽时,优先从队列头部删除元素
public class FIFOCache<E> implements Cache<E> {
    /**
     * 存放缓存结果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 缓存队列,用于置换
     */
    private final DoubleLinkedList<E> list;

    public FIFOCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList<>(capacity);
    }

    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        return map.get(key).getValue();
    }

    @Override
    public void put(String key, E value) {
        if (list.getCapacity() == 0) {
            throw new IllegalArgumentException("缓存容量为空");
        }
        DoubleLinkedList.Node<E> node = new DoubleLinkedList.Node<>(key, value);
        if (map.containsKey(key)) {
            // 已经存在数据,先移除掉队列中数据,然后再将数据添加到队尾
            list.delNode(map.get(key));
            map.put(key, node);
            list.addTail(node);
        } else {
            if (list.getSize() >= list.getCapacity()) {
                // 如果队列已满,删除队首元素
                DoubleLinkedList.Node<E> delNode = list.delHead();
                map.remove(delNode.getKey());
            }
            // 队列尾部添加元素
            list.addTail(node);
            map.put(key, node);
        }
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

4.3 LRU 最近最少使用算法实现

实现思想:

  • hashMap维护键、缓存节点之间的关系
  • 双向链表维护缓存队列
  • 当使用键命中缓存时,将队列中的节点移除掉,往队列头部重新添加节点
  • 当容量耗尽时,优先从队尾删除元素
public class LRUCache<E> implements Cache<E> {
    /**
     * 存放缓存结果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 缓存队列,用于置换
     */
    private final DoubleLinkedList<E> list;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList<>(capacity);
    }

    /**
     * 访问缓存
     */
    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        // 被访问后,放到链表头
        DoubleLinkedList.Node<E> node = map.get(key);
        list.delNode(node);
        list.addHead(node);
        return node.getValue();
    }

    @Override
    public void put(String key, E value) {
        if (list.getCapacity() == 0) {
            throw new IllegalArgumentException("缓存容量为0");
        }
        DoubleLinkedList.Node<E> newNode = new DoubleLinkedList.Node<>(key, value);
        if (map.containsKey(key)) {
            // 如果缓存中已经存在,删除原来的值
            DoubleLinkedList.Node<E> eNode = map.get(key);
            list.delNode(eNode);
        } else {
            if (list.getSize() >= list.getCapacity()) {
                // 缓存已满,清空链表尾部元素
                DoubleLinkedList.Node<E> eNode = list.delTail();
                map.remove(eNode.getKey());
            }
        }
        list.addHead(newNode);
        map.put(key, newNode);
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

4.4 LFU 最近最少使用算法实现

实现思想:

  • hashMap维护键、缓存节点之间的关系
  • hashMap维护访问频率、该频率对应的节点队列之间的关系
  • 当使用键命中缓存时,将缓存访问频率加1,从之前的节点队列中移除,再新的访问频率对应的队列中尾部插入新节点。
  • 当容量耗尽时,优先从最低访问频率的队首删除元素
public class LFUCache<E> implements Cache<E> {
    private final int capacity;
    private int size;
    private Map<String, DoubleLinkedList.Node<E>> map;
    private Map<Integer, DoubleLinkedList<E>> freqMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        freqMap = new HashMap<>();
    }


    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        LFUNode<E> node = (LFUNode<E>) map.get(key);
        updateFreq(node);
        return node.getValue();
    }

    @Override
    public void put(String key, E value) {
        if (capacity == 0) {
            throw new IllegalArgumentException("缓存容量为0");
        }

        if (map.containsKey(key)) {
            // 修改节点,更新值,并更新命中频率
            LFUNode<E> node = (LFUNode<E>) map.get(key);
            node.setValue(value);
            updateFreq(node);
        } else {
            // 新增节点
            if (size >= capacity) {
                // 节点满了,从最小频率队列里移除头节点
                DoubleLinkedList<E> minFreqDoubleLinkedList = freqMap.get(getMinFreq());
                DoubleLinkedList.Node<E> delNode = minFreqDoubleLinkedList.delHead();
                if(minFreqDoubleLinkedList.getSize() == 0){
                    freqMap.remove(getMinFreq());
                }
                map.remove(delNode.getKey());
                size--;
            }
            // 添加节点
            LFUNode<E> newNode = new LFUNode<>(key,value);
            newNode.freq = 1;
            map.put(key,newNode);
            // 将节点添加到访问频率为1的队列中
            if(!freqMap.containsKey(1)){
                freqMap.put(1,new DoubleLinkedList<>());
            }
            size++;
            freqMap.get(1).addTail(newNode);
        }
    }

    /**
     * 获取最小访问频率
     */
    private Integer getMinFreq(){
        int min = Integer.MAX_VALUE;
        for (Integer freq : freqMap.keySet()) {
            min = Math.min(freq,min);
        }
        return min;
    }

    /**
     * 更新节点频率、频率散列表
     *
     * @param node 节点
     */
    private void updateFreq(LFUNode<E> node) {
        // 从当前频率链表中删除节点
        int freq = node.freq;
        DoubleLinkedList<E> freqDoubleLinkedList = freqMap.get(freq);
        freqDoubleLinkedList.delNode(node);
        if(freqDoubleLinkedList.getSize() == 0){
            // 如果频率对队列为空,移除频率
            freqMap.remove(freq);
        }

        // 更新节点访问频率,并添加到频率对应的链表中
        freq++;
        LFUNode<E> newNode = new LFUNode<>(node.getKey(),node.getValue());
        newNode.freq = freq;
        if (!freqMap.containsKey(freq)) {
            freqMap.put(freq, new DoubleLinkedList<>());
        }
        DoubleLinkedList.Node<E> addNode = freqMap.get(freq).addTail(newNode);
        map.put(addNode.getKey(),newNode);
    }

    /**
     * 带使用频率的节点信息
     *
     * @param <E>
     */
    private static class LFUNode<E> extends DoubleLinkedList.Node<E> {
        /**
         * 使用频率
         */
        private int freq;

        public LFUNode(String key, E value) {
            super(key, value);
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("nprintStart---------------------------------------------n");
        for (Integer freqKey : freqMap.keySet()) {
            str.append("freq[").append(freqKey).append("] ---> ");
            DoubleLinkedList<E> freqList = freqMap.get(freqKey);
            str.append(freqList.toString());
            str.append("n");
        }
        str.append("printEnd------------------------------------------------n");
        return str.toString();
    }
}


Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条