Computer Architecture Task 2

Authority

This is the second homework of Computer Architecture, and the author is Lmxyy.

Aim

• Implement a Risc-v CPU using hardware description language(HDL), and then download the CPU on FPGA.
• Using C++ to simulate the memory via the USB-UART protocol.

Instructions [100%]

• [X] LUI
• [X] AUIPC
• [X] JAL
• [X] JALR
• [X] BEQ
• [X] BNE
• [X] BLT
• [X] BGE
• [X] BLTU
• [X] BGEU
• [X] ADDI
• [X] SLTI
• [X] SLTIU
• [X] XORI
• [X] ORI
• [X] ANDI
• [X] SLLI
• [X] SRLI
• [X] SRAI
• [X] ADD
• [X] SUB
• [X] SLL
• [X] SLT
• [X] SLTU
• [X] XOR
• [X] SRL
• [X] SRA
• [X] OR
• [X] AND
• [X] LB
• [X] LH
• [X] LW
• [X] LBU
• [X] LHU
• [X] SB
• [X] SH
• [X] SW

Memory [50%]

• [-] UART-USB Protocol
  • [X] buf_que module
  • [X] uart_com module
  • [ ] encoder module
  • [ ] decoder module
• [X] FPGA Communication
  • [X] adapter.cpp
  • [X] adapter.hpp
  • [X] env_iface.hpp
  • [X] environment.hpp
  • [X] main.cpp

Design Idea

According to the book 《自己动手写CPU》, implemented a riscv32 cpu which adopted Von Neumann Architecture. More details are following:

Feature

General

• The instruction set arthitecture(ISA) is RV32I Base Integer Instruction Set, Version 2.0.
• The implementation technology is FPGA.
• The HDL is Verilog HDL.
• The communication protocol is UART-USB.

Branch Predictor

pdt module is a branch predictor, which use tournament to predict the result:

• According to the 2nd to 11th bits in pc address, choose an alloyed branch predictor, and the then by its saturating counter decide which predictor I would use.
• If I decide the global one, I would choose a saturating counter according to the latest 10 branch results.
• If I decide the local one, I would choose a saturating counter by both the 2nd to 11th bits in pc address and the latest 3 branch results(I guessed this would be more accurate).

Prediction will be done in the if stage, and I will pass the predicting results to pc and id. After id knows the branch results, it would deliver the feedback the the predictor.

Cache

• 2 way set-associative cache, 8 bytes in each block, and the length of index is adjustable;
• Replace strategy: LRU;
• Write strategy: write through;
• If replacement is needed, the cache will stop the cpu till the replacement finishes and the requiring data are read out from the memory(icache only stalls if, while dcache stalls all stages except wb);
• Because the memory is just a simulator, so I connect both icache and dcache to memories which make them able to read data simultaneously.

Thanks

• Evensgn’s data support.
• kzoacn’s technology support.

Reference

• 《自己动手写CPU》
• project-v1.0.pdf
• Branch Prediction Wikipedia
• 助教的MIPS CPU实现
• cpu-judge
• Basys3-FPGA-开发板实验参考资料

Appendix

Format of Riscv32 Assembler

Instruction	Format
LUI	lui rd, imm(20bits)
ADDI	addi rd, rs, (signed)imm(11bits)
SLTI	slti rd, rs, (signed)imm(11bits)
SLTIU	sltiu rd, rs, (signed)imm(11bits)
XORI	xori rd, rs, (signed)imm(11bits)
ORI	ori rd, rs, (signed)imm(11bits)
ANDI	andi rd, rs, (signed)imm(11bits)
SLLI	slli rd, rs, (signed)imm(5bits)
SRAI	srai rd, rs, (signed)imm(5bits)
ADD	add rd, rs1, rs2
SUB	sub rd, rs1, rs2
SLL	sll rd, rs1, rs2
SLT	slt rd, rs1, rs2
SLTU	sltu rd, rs1, rs2
XOR	xor rd, rs1, rs2
SRL	srl rd, rs1, rs2
SRA	sra rd, rs1, rs2
OR	or rd, rs1, rs2
AND	and rd, rs1, rs2
JAL	jal rd, label
JALR	jalr rd, (signed)12-bit-offset(rs)
BEQ	beq rs, rt, lable
BNE	bne rs, rt, lable
BLT	blt rs, rt, lable
BGE	bge rs, rt, lable
BLTU	bltu rs, rt, lable
BGEU	bgeu rs, rt, lable
LB	lb rd, (signed)12-bit-offset(rs)
LBU	lbu rd, (signed)12-bit-offset(rs)
LH	lh rd, (signed)12-bit-offset(rs)
LHU	lhu rd, (signed)12-bit-offset(rs)
LW	lw rd, (signed)12-bit-offset(rs)
SB	sb rs, (signed)12-bit-offset(rs)
SH	sh rs, (signed)12-bit-offset(rs)
SW	sw rs, (signed)12-bit-offset(rs)

How to Install and Use Riscv Toolchain

Clone the toolchain locally.

If you could climb over the wall:

Run the following codes:

$ git clone --recursive https://github.com/riscv/riscv-gnu-toolchain

or alternatively:

$ git clone https://github.com/riscv/riscv-gnu-toolchain
$ cd riscv-gnu-toolchain
$ git submodule update --init --recursive

The source codes are somewhat large, please wait patiently.

If you couldn’t climb over the wall:

Download the package at https://jbox.sjtu.edu.cn/link/view/8971e3226df74d35b2dcbe588397958f(Provided by Zhanghao Wu). Remember to depackage with the command:

tar -zxvf riscv-gnu-toolchain.tar.gz

If you use git directly, maybe you couldn’t clone all source codes which may cause that your toolchain cannot work normally.

Make the source code.

Run the following command to get riscv32.

sudo ./configure --prefix=/opt/riscv --with-arch=rv32gc --with-abi=ilp32d
sudo make

Modify your path variable.

First run the command

sudo gedit /etc/profile

Then add

export PATH="$PATH:/opt/riscv/bin"

Next, reboot or logout.

Tranform the assembler to riscv instructions.

Use the following command

if [ $# -eq 0 ]; then
    riscv32-unknown-elf-as -o instr.o -march=rv32i instr.s 
    riscv32-unknown-elf-ld instr.o -o instr.om
    riscv32-unknown-elf-objcopy -O binary instr.om instr.bin
    ../Tools/Bin_to_Text instr.bin > instr.data
    cat instr.data
    rm instr.o instr.om instr.bin    
elif [ $# -eq 1 ]; then
    riscv32-unknown-elf-as -o $1.o -march=rv32i $1.s 
    riscv32-unknown-elf-ld $1.o -o $1.om
    riscv32-unknown-elf-objcopy -O binary $1.om $1.bin
    ../Tools/Bin_to_Text $1.bin > instr.data
    cat instr.data
    rm $1.o $1.om $1.bin
else
    echo "Please input less than 2 paraments!"
fi

which was included in get_instr.sh. You need run the bash with exactly one parament which shows that your assembler source code’s name is “$1.s”. And you will get an file named instr.data which contains your hexadecimal riscv32 instructions. Attention: Please modify the path of Bin_to_Text according to your current directory.

Transform a binary file to a text file.

The source code was Bin_to_Text.cpp.

#include<cstring>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<fstream>
using namespace std;

typedef long long ll;
const int NSIZE = 8;

inline ll convert(ll num)
{
    ll a[4] = {0,0,0,0},ret = 0;
    for (int i = 0;i < 4;++i,num >>= 8)
        a[i] = num&((1<<8)-1);
    for (int i = 0;i < 4;++i)
        ret = (ret<<8)|a[i];
    return ret;
}

int main(int argc,char *argv[])
{
    if (argc == 1||argc > 2)
    {
        cerr << "Please input an binary file." << endl;
        return 0;
    }
    ifstream ifile(argv[1],ios::in|ios::binary);
    if (!ifile)
    {
        cerr << "Cannot open file." << endl;
        return 0;
    }
    int head = ifile.tellg(),tail = (ifile.seekg(0,ios::end)).tellg();
    ifile.seekg(0,ios::beg);
    int N = (tail-head)/4;
    while (N--)
    {
        ll num = 0; int now = 0;
        for (int k = 0;k < 4;++k)
        {
            char c; ifile.read((char *)&c,sizeof(char));
            for (int i = 0;i < NSIZE;++i,c >>= 1)
                num |= ((ll)(c&1))<<(now++);
        }
        cout.width(8); cout.fill('0');
        cerr.width(8); cerr.fill('0');
        cout << hex << convert(num) << endl;
        cerr << hex << num << endl;
    }
    cerr << "Congratulations, convert successfully!." << endl;
    return 0;
}

Install C++ Serial Communication Library and Boost.

• Serial Communication Library
• Boost or you could run the following command in Ubuntu

  sudo apt install libboost-program-options-dev 
      

• To compile the cpp, you need to run the following command in the correspondent directory:

  g++ *.cpp -c -std=c++14 -I /tmp/usr/local/include/
  g++ *.o -o cpu-judge -L /tmp/usr/local/lib/ -lboost_program_options -lserial