基于直接相联映象形式的Cache设计

1.请勿转载，本人对该文章保留有所有权利，如果需要转载请联系gavingog@qq.com，经本人同意后才可转载。

2.非常感谢中山大学何朝东老师的指导，这篇博客很大程度上是基于何老师的实验指导文档上发展而来的。

3.该文仅供参考，其中也许很多bug，请注意
4.仅供复习，学习用，若有问题或者建议请在评论区留言，我会尽快回复

直接相联映象方式的介绍

直接相联映象方式，这种变换方式简单而直接，硬件实现很简单，访问速度也比较快，但是块的冲突率比较高。其主要原则是：主存中一块只能映象到Cache的一个特定的块中。假设主存的块号为B，Cache的块号为b，则它们之间的映象关系可以表示为：b = B mod Cb
其中，Cb是Cache的块容量。设主存的块容量为Mb，区容量为Me，则直接映象方法的关系如下图所示。把主存按Cache的大小分成区，一般主存容量为Cache容量的整数倍，主存每一个分区内的块数与Cache的总块数相等。直接映象方式只能把主存各个区中相对块号相同的那些块映象到Cache中同一块号的那个特定块中。例如，主存的块0只能映象到Cache的块0中，主存的块1只能映象到Cache的块1中，同样，主存区1中的块Cb（在区1中的相对块号是0），也只能映象到Cache的块0中，看图1。根据上面给出的地址映象规则，整个Cache地址与主存地址的低位部分是完全相同的。

直接映象方式的地址变换过程如下图所示，主存地址分为三个部分：区号E、块号B和块内地址W；Cache地址分为两部分：块号b和块内地址w。主存地址中的块号B与Cache地址中的块号b是完全相同的。同样，主存地址中的块内地址W与Cache地址中的块内地址w也是完全相同的，主存地址比Cache地址长出来的部分称为区号E。

在程序执行过程中，当要访问Cache时，为了实现主存块号到Cache块号的变换，需要有一个存放主存区号的小容量存储器（称为区表存储器），这个存储器的容量与Cache的块数相等，字长为主存地址中区号E的长度，另外再加一个有效位（命中/失效）。
从主存地址到Cache地址的变换过程中，首先用主存地址中的块号B去访问区表存储器（用块号B作为区表存储器的地址，访问它），然后，将读出来的区号与主存地址中的区号E进行比较，比较结果相等，有效位为1，则Cache命中，表示要访问的那一块已经装入到Cache中了，可以直接用块号及块内地址组成的缓冲地址到缓存Cache中取数，把读出来的数据送往CPU；如果比较结果不相等，有效位为1，可以进行替换，如果有效位为0，可以直接调入所需块。至于比较不相等情况，不论有效位是1或0均为Cache没有命中，或称为Cache失效，表示要访问的那个块还没有装入到Cache中，这时，要用主存地址去访问主存储器，先把该地址所在的块读到Cache中，然后再读取Cache中该地址的数据送CPU。

Cache和CPU以及存储器的关系

基于关系图更加详细的分解图

实现思路的细节

实现Cache的存储体的方法是先实现一个8位的存储单元，然后用这个8位的存储单元来构成一个256Kb X 8位的Cache（地址18位）。

再实现一个15位（14+1）的存储单元，然后，用这个15位的存储单元来构成一个16k X 15位的区表存储器（地址14位与块号B相同），用来存放区号（14位）和有效位M(1位)。在这个部分中，还要实现一个区号E比较器，也就是如果主存地址的区号E和区表存储器中按块号B为地址取出的相应单元中的区号E相等，有效位标志为M，且有效位M=1时，则Cache命中，否则Cache失效，M=0时表示Cache失效。

当Cache命中时，就将Cache存储体中相应单元的数据送往CPU，这个过程比较简单。当Cache失效时，就将主存中相应块中的数据读出写入Cache中，这样Cache控制器就要产生主存储器的读信号MRd（为1，读），由于每个Cache块占十六个单元，按32 位（4个字节）为访问存储器单位，那么需要连续访问4次主存，读取存储器中该块的数据，即16个字节，然后写入Cache相应块中，最后再修改区表存储器。至于访问主存的方法，要用到计数器。写数据时，如果Cache中有该地址数据，则修改，然后修改存储器该地址内容（MWr为1，写，为主存的写信号）；如果Cache中无该地址数据，就直接修改存储器该地址单元内容。

实现中的信号说明

32位主存地址为AB31..AB0（地址总线），32位数据为DB31..DB0（数据总线），RD（为0，读）为Cache的读信号，MWr（为1，写）为主存的写信号，MRd（为0，读）为主存的读信号，D31..D0为Cache送往CPU的数据信号（出口处经过一个三态缓冲器然后再输出），MD31..MD0为存储器RAM送往Cache的数据信号。
实现中：
对于blockAddr正如上边所讲的那样，是块号Addr[17:4]
对于regionCode指的是区号Addr[31:18]
而Offset指的是块内地址Addr[3:0]
cpu_data: 指的是CPU传送的写入数据
output_data: 指的是从Cache中读取的数据
count_enable: 用于控制计数器计数
cpuDataWr: 指示是否从cpu_data中写数据到Cache的Data中
ramDataRW: 指示从Cache中读数据或者从RAM中写数据进入Cache的Data中
count_num: 指的是在RAM中读取到了哪一块（每次读取32个字节，需要读取4次）
reset: 重置table中的有效端valid为0，Counter的计数为0
hit: Cache是否命中
tableWr: 是否在Table中写区号和有效端

实现的代码

主模块Main.v

`timescale 1ns / 1ps

module Main(RD, MWr, Addr, reset, o_data, cpu_data);

    input RD, MWr, reset;
    input [31:0] cpu_data, Addr;
    output [31:0]o_data;

    wire [1:0] CountNum;
    wire MRd;
    wire [31:0] ram_data;
    reg CLK;

    initial begin  // 产生时钟信号
        CLK = 0;
        forever #50 begin
            CLK = !CLK;
        end
    end 

    MainCache MainCache(reset, CLK, MWr, Addr, RD, CountNum, MRd, ram_data, cpu_data, o_data);
    RAM RAM(cpu_data, Addr, MRd, CountNum, MWr, ram_data);

endmodule

RAM.v模块

`timescale 1ns / 1ps
module RAM (i_data, addr, MRd, countNum, MWr, o_data);
    input [31:0] i_data;
    input [31:0] addr;
     input [1:0] countNum;
    input MRd, MWr;
    output reg [31:0] o_data;
    reg [7:0] memory [0:1048575]; // 假设1M内存，因为4G模拟器跑不起来
     initial begin
        o_data = 0;
     end
    always @(addr or i_data or MRd or countNum or MWr) begin // 使用大端方式储存
      if (MRd == 1) begin // 读数据到cache
            o_data[31:24] = memory[addr[31:4] * 16+ countNum * 4 + 0];
         o_data[23:16] = memory[addr[31:4] * 16 + countNum * 4 + 1];
         o_data[15:8] = memory[addr[31:4] * 16 + countNum * 4 + 2];
         o_data[7:0] = memory[addr[31:4] * 16 + countNum * 4 + 3];
      end 
        if (MWr == 1) begin // 写数据
            memory[addr] = i_data[31:24];
         memory[addr+1] = i_data[23:16];
         memory[addr+2] = i_data[15:8];
         memory[addr+3] = i_data[7:0];
      end
    end
endmodule 

Cache主模块，分为四个小模块

`timescale 1ns / 1ps
module MainCache(reset, clk, MWr, Addr, RD, count_num, MRd, ram_data, cpu_data, o_data);

    input clk, MWr, RD, reset;
    input [31:0] Addr, ram_data, cpu_data;
    output [31:0] o_data;
    output [1:0] count_num;
    output MRd;

    wire hit, count_enable, ramDataRW, cpuDataWr, tableWr;

    CacheCtrl CacheCtrl(clk, RD, MWr, count_num, hit, count_enable, ramDataRW, cpuDataWr, MRd, tableWr);
    CacheCount CacheCount(reset, clk, count_enable, count_num);
    CacheTable CacheTable(Addr[17:4], Addr[31:18], reset, tableWr, hit);
    CacheData CacheData(hit, ram_data, cpu_data, ramDataRW, cpuDataWr, Addr[17:4], Addr[3:0], count_num, o_data);

endmodule

Cache子模块之CacheCtrl

`timescale 1ns / 1ps

module CacheCtrl(clk, RD, MWr, count_num, hit, count_enable, ramDataRW, cpuDataWr, MRd, tableWr);

    input clk, RD, MWr, hit;
    input [1:0] count_num;

    output reg count_enable, ramDataRW, MRd, tableWr, cpuDataWr;

    always@(posedge clk) begin
        if (RD == 0) begin
            if (hit) begin
                ramDataRW = 0;
                MRd = 0;
                count_enable = 0;
                tableWr = 0;
            end
            else begin
                ramDataRW = 1;
                MRd = 1;
                count_enable = 1;
                tableWr = 0;
            end
        end

        if (count_num == 2'b11) begin // 状态11表示已经在RAM读完了所有的数据，这是最终状态
            count_enable = 0;
            tableWr = 1;
            ramDataRW = 0;
        end

        if (MWr) begin
            if (hit) begin
                cpuDataWr = 1;
            end else begin
                cpuDataWr = 0;
            end
        end else begin
            cpuDataWr = 0;
        end
    end

endmodule

Cache子模块之CacheCount

`timescale 1ns / 1ps

module CacheCount(reset, clk, enable, num);
    input reset, clk, enable;
    output reg[1:0] num;
    reg [1:0] count_num;

    always@(posedge clk) begin
        if (reset) count_num = 0;
        else if (enable) count_num = count_num + 1;

        num = count_num; // always do this
    end

endmodule

Cache子模块之CacheTable

`timescale 1ns / 1ps

module CacheTable(blockAddr, regionCode, reset, tableWr, hit);
    input [13:0] blockAddr, regionCode;
    input reset, tableWr;
    output hit;

    reg [13:0] region[0:16383];
    reg [0:0] valid [0:16383];
    reg [14:0] tempi;

    assign hit = (region[blockAddr] == regionCode && valid[blockAddr] == 1) ? 1 : 0;

    always@(reset) begin //  初始化设置有效位为0
        if (reset) begin
            for(tempi = 0; tempi <= 16383; tempi = tempi + 1)
                valid[tempi] = 0;
        end
    end

    always@(tableWr) begin
        if (tableWr) begin
            valid[blockAddr] = 1;
            region[blockAddr] = regionCode;
        end
    end

endmodule

Cache子模块之CacheData

`timescale 1ns / 1ps

module CacheData(hit, ram_data, cpu_data, ramDataRW, cpuDataWr, blockAddr, offset, countNum, o_data);

    input [31:0] ram_data, cpu_data;
    input [13:0] blockAddr;
    input [3:0] offset;
    input [1:0] countNum;
    input ramDataRW, cpuDataWr, hit;

    output reg[31:0] o_data;

    reg [7:0] data [0:262143];

    always@(cpuDataWr or blockAddr or ram_data or cpu_data or offset or countNum or ramDataRW or hit) begin
        if (ramDataRW == 1) begin // 写主存给与的数据
            data[(blockAddr * 16) + (countNum * 4) + 0] = ram_data[31:24];
            data[(blockAddr * 16) + (countNum * 4) + 1] = ram_data[23:16];
            data[(blockAddr * 16) + (countNum * 4) + 2] = ram_data[15:8];
            data[(blockAddr * 16) + (countNum * 4) + 3] = ram_data[7:0];
        end
        else if (ramDataRW == 0 && hit == 1) begin // 读数据
            o_data[31:24] = data[(blockAddr * 16) + offset + 0];
            o_data[23:16] = data[(blockAddr * 16) + offset + 1];
            o_data[15:8] = data[(blockAddr * 16) + offset + 2];
            o_data[7:0] = data[(blockAddr * 16) + offset + 3];
        end

        if (cpuDataWr == 1 && hit == 1) begin // 写CPU给与的数据
            data[(blockAddr * 16) + offset + 0] = cpu_data[31:24];
            data[(blockAddr * 16) + offset + 1] = cpu_data[23:16];
            data[(blockAddr * 16) + offset + 2] = cpu_data[15:8];
            data[(blockAddr * 16) + offset + 3] = cpu_data[7:0];
        end
    end

endmodule

测试模块test.v

`timescale 1ns / 1ps

module test;

    // Inputs
    reg RD;
    reg MWr;
    reg [31:0] Addr;
    reg reset;
    reg [31:0] cpu_data;

    // Outputs
    wire [31:0] o_data;

    // Instantiate the Unit Under Test (UUT)
    Main uut (
        .RD(RD), 
        .MWr(MWr), 
        .Addr(Addr), 
        .reset(reset), 
        .o_data(o_data), 
        .cpu_data(cpu_data)
    );

    initial begin
        // Initialize Inputs
        RD = 1;
        MWr = 0;
        Addr = 0;
        reset = 1;
        cpu_data = 0;

      #100; //开始初始化
          reset = 0;

        // 对块0写数据（此时cache没有数据）
        #500;
            MWr = 1;
            RD = 1;
            Addr = 32'b00000000000000000000000000000000;
            cpu_data = 32'b11100000111111111111111111111111;
        #500;
            MWr = 1;
            RD = 1;
            Addr = 32'b00000000000000000000000000000100;
            cpu_data = 32'b11111111111111111111111111111111;

        // 对块1写数据（此时cache没有数据）
        #500;
            MWr = 1;
            RD = 1;
            Addr = 32'b00000000000001000000000000011000;
            cpu_data = 32'b01110000111111110001111111000011;

        // 对块0读数据（此时cache没有数据）
        #500;
            RD = 0;
            MWr = 0;
            Addr = 32'b00000000000000000000000000000000;

        // 对块0读数据（此时cache有数据）
        #500;
            RD = 0;
            MWr = 0;
            Addr = 32'b00000000000000000000000000000100;

        // 对块1读数据（此时cache没有数据）
        #500;
            RD = 0;
            MWr = 0;
            Addr = 32'b00000000000001000000000000011000;

        // 对块1写数据（此时cache有数据）
        #500;
            RD = 1;
            MWr = 1;
            Addr = 32'b00000000000001000000000000011100;
            cpu_data = 32'b11110111111111110001111111000011;

        // 对块1读数据（此时cache有数据）
        #500;
            RD = 0;
            MWr = 0;
            Addr = 32'b00000000000001000000000000011100;
    end

endmodule

最后的一点体会

1. 这次的实验和CPU设计基本上都是基于模块化的思想的，这次我们把一个大的Cache分解为四个小模块，这样基于理论指导分解问题更加容易解决，可见模块化的思想是多麽的重要。
2. 另外这是自己第一次手动分解一个大模块，感觉分析的过程中非常有趣，如果读者有兴趣的话可以自己手动分解一下。
3. 最后再次感谢何朝东老师的实验指导。