📄 bpred.c
字号:
//==============================================================================
//写文件的人： (sha)fish
//联系方式： wahaha_nescafe@hotmail.com
//
//系统说明： 这是一个32位微处理器的模拟程序，属于原型，实现的功能有限。
// 参考了MIPSR10000、POWPC620处理器的结构，以及体系结构
// 中的圣经《计算机体系结构——量化研究方法》。
// 实现了指令的4发射、乱序执行。
//版权说明： Copyright (C) 2004-2005 by (sha)fish
// All Rights Not Reserved!
// （没有版权，随便折腾——不能用于商业目的）
//==============================================================================
#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include "system.h"
#include "config.h"
#include "bpred.h"
//******************************************************************************
//创建分支方向预测器
/*
(1)函数名：
(2)接收参数：
type ： 采用什么类型的分支方向预测
hreg_num ： 使用的分支历史寄存器的个数
history_width ： 使用的分支历史寄存器的长度
pht_num ： PHT表的个数
pht_entry_num ： 每个PHT表的项数
(3)返回值：
(4)函数过程说明：
分支历史寄存器的最大长度是32位
(5)修改于：
2005-8-28 0:30
(6)作者：
(sha)fish
*/
struct bpred_dir_t*
bpred_dir_create ( enum BPRED_TYPE type, //预测的类型
word_t hreg_num, //分支历史寄存器的个数
word_t history_width,//分支历史寄存器的长度
word_t pht_num, //PHT表的个数
word_t pht_entry_num //PHT表入口的个数
)
{
struct bpred_dir_t* bpdir = NULL;
struct bpred_hreg_t* bphreg = NULL;
struct bpred_pht_t* bppht = NULL;
byte_t* tdata;
word_t i, j;
//分支历史寄存器的个数是2的幂次
ASSERT(hreg_num>=1 && ((hreg_num & (hreg_num-1))==0));
//由于是利用一个无符号整数保存分支历史因此分支历史最大32位
ASSERT(history_width>=0 && history_width<=32);
//PHT表也是一样的道理
ASSERT( (pht_num>=1) && ((pht_num & (pht_num-1))==0 ) );
ASSERT( (pht_entry_num>=1) && ((pht_entry_num & (pht_entry_num-1))==0 ) );
//给分支方向预测器分配空间
bpdir = (struct bpred_dir_t*)malloc(sizeof(struct bpred_dir_t));
if(!bpdir)
system_error("ERROR When create branch prediction predictor\n");
//得到分支方向预测器的类型
bpdir->type = type;
//分支历史寄存器分配空间
bphreg = (struct bpred_hreg_t*)
malloc( sizeof(struct bpred_hreg_t) * hreg_num );
if(!bphreg)
system_error("ERROR When create branch history register\n");
//初始化分支历史寄存器
for(i=0; i<hreg_num; i++)
(bphreg+i)->reg = 0;
bpdir->hreg = bphreg;
bpdir->hreg_num = hreg_num;
bpdir->hreg_width = history_width;
//分配分支模式历史表的空间
bppht = (struct bpred_pht_t*)
malloc( sizeof(struct bpred_pht_t) * pht_num );
if(!bppht)
system_error("ERROR When create pht \n");
//然后要在每一个PHT表中分配存放预测数据的具体的空间
//先判断类型，再for循环的效率高点
for(i=0; i<pht_num; i++)
{
//如果是神经网络预测
if(type == BPRED_NEURAL)
{
//在这儿可以看出，基于神经网络的权重最大为-128-127
//使用时要进行无符号数和有符号数之间的转换
tdata = (byte_t*)
malloc( sizeof(byte_t) * history_width * pht_entry_num );
if(!tdata)
system_error("ERROR When create data\n");
//然后需要初始化其中的数据
for(j=0; j<(history_width*pht_entry_num); j++)
{
(byte_t)(*(tdata+i)) = 0;
}
}
else
{
tdata = (byte_t*)malloc( sizeof(byte_t) * pht_entry_num );
if(!tdata)
system_error("ERROR When create data\n");
//然后需要初始化其中的数据
for(j=0; j<pht_entry_num; j++)
{
(byte_t)(*(tdata+i)) = 0;
}
}
(bppht+i)->data = tdata;
}
bpdir->pht = bppht;
bpdir->pht_num = pht_num;
bpdir->pht_entry = pht_entry_num;
bpdir->pred_taken = 0;
bpdir->actual_taken = 0;
bpdir->pred_ntaken = 0;
bpdir->actual_ntaken = 0;
return bpdir;
}
//******************************************************************************
//创建分支地址预测器
/*
(1)函数名：
(2)接收参数：
btb_entry_num ： BTB表项的数目
btb_associative ： BTB的相联度
policy ： BTB的替换方法
(3)返回值：
(4)函数过程说明：
这个BTB表可以使用数组实现的
(5)修改于：
2005-8-28 0:39
(6)作者：
(sha)fish
*/
struct bpred_addr_t*
bpred_addr_create( word_t btb_entry_num, //BTB表项的数目
word_t btb_associative, //BTB的相联度
enum BPRED_BTB_POLICY policy //BTB的替换方法
)
{
struct bpred_addr_t* bpaddr;
struct bpred_btb_t* bpbtb;
struct bpred_btb_set_t* bpset;
struct bpred_btb_entry_t* bpentry;
struct bpred_btb_entry_t* temp_bpentry;
word_t i, j;
word_t nsets;
//确保他们为2的幂
ASSERT((btb_entry_num & (btb_entry_num-1))==0);
ASSERT((btb_associative & (btb_associative-1))==0);
//分配了分支地址预测器的空间
bpaddr = (struct bpred_addr_t*)malloc( sizeof(struct bpred_addr_t) );
if(!bpaddr)
system_error("ERROR When create address prediction \n");
bpaddr->addr_hits = 0;
bpaddr->lookups = 0;
bpaddr->pred_hits = 0;
//分配BTB表的空间
bpbtb = (struct bpred_btb_t*)malloc( sizeof(struct bpred_btb_t) );
if(!bpbtb)
system_error("ERROR When create address prediction \n");
bpaddr->btb = bpbtb;
//求出一共有多少组
nsets = btb_entry_num/btb_associative;
//分配组
bpset = (struct bpred_btb_set_t*)
malloc( sizeof(struct bpred_btb_set_t) * nsets );
if(!bpset)
system_error("ERROR When create address prediction set\n");
//在组中没有建立连接的机制，访问的话就是＋1访问类型的
//设置BTB表的属性
bpbtb->set = bpset;
bpbtb->policy = policy;
bpbtb->associative = btb_associative;
bpbtb->nsets = nsets;
//在BTB表的每一个组内部进行处理
for(i=0; i<nsets; i++)
{
//每个组内部分配若干个表项
bpentry = (struct bpred_btb_entry_t*)
malloc( sizeof(struct bpred_btb_entry_t) * btb_associative );
if(!bpentry)
system_error("ERROR When create address prediction set\n");
//各个组的头尾指针指好了
(bpset+i)->head = bpentry;
(bpset+i)->tail = bpentry + (btb_associative-1);
(bpset+i)->tail->next = NULL;
//组中的各个块赋值
for(j=0; j<btb_associative; j++)
{
(bpentry+j)->valid = 0;
(bpentry+j)->source_addr = 0;
(bpentry+j)->target_addr = 0;
(bpentry+j)->counter = 0;
}
//组中各个块连接成链表结构
j = 0;
while( j<(btb_associative-1) )
{
temp_bpentry = bpentry+1;
bpentry->next = temp_bpentry;
bpentry = temp_bpentry;
j++;
}
}
return bpaddr;
}
//******************************************************************************
//以下为读取BTB中的某个entry
/*
(1)函数名：
(2)接收参数：
bp_addr ： 分支地址预测器
addr ： 分支指令地址，即利用这个地址查找BTB表
entry ： 寻找到的相应的块
(3)返回值：
(4)函数过程说明：
如果在BTB中找到addr地址对应的项，就返回相应的entry
得到的entry存放在传入的参数“entry”中
如果没有找到，就返回NULL
因此，需要entry参数在传进来的时候为NULL，这样才能进行判断
(5)修改于：
2005-8-28 10:05
(6)作者：
(sha)fish
*/
void
bpred_read_btb_entry( struct bpred_addr_t* bp_addr,
addr_t addr,
struct bpred_btb_entry_t** entry
)
{
byte_t n;
struct bpred_btb_t* bp_btb;
struct bpred_btb_set_t* bp_set;
struct bpred_btb_entry_t* bp_entry;
struct bpred_btb_entry_t* bp_entry2;
ASSERT(bp_addr!=NULL);
ASSERT((*entry)==NULL);
bp_addr->lookups++;
//得到BTB表
bp_btb = bp_addr->btb;
//得到BTB表内的某一个组
bp_set = (struct bpred_btb_set_t*)
(bp_btb->set + BPRED_GET_BTB_SET(bp_btb, addr));
//得到组内的entry
bp_entry = bp_set->head;
ASSERT(bp_entry!=NULL);
//在一个组内循环比较地址（如果组比较多，可以使用HASH方法摆放组）
for(n=0; n<bp_btb->associative; n++)
{
//发现了就break
if( (bp_entry->source_addr==addr) && (bp_entry->valid==1) )
break;
else
bp_entry = bp_entry->next;
}
//如果找到了我们所需要的entry
if(bp_entry)
{
bp_addr->addr_hits++;
//在一个组进行替换算法的处理
if(bp_btb->policy==BTB_LRU)
{
bp_entry2 = bp_set->head;
for(n=0; n<bp_btb->associative; n++)
{
//如果其他的计数器的值比较小，则需要加“1”
if( (bp_entry2->valid==1)
&& (bp_entry2->counter<bp_entry->counter) )
{
bp_entry2->counter++;
}
bp_entry2 = bp_entry2->next;
}
//找到的这个块的计数器设置为“0”
bp_entry->counter = 0;
}
//然后返回找到的块
*entry = bp_entry;
}
//如果没有找到块
else
{
*entry = NULL;
}
return;
}
//******************************************************************************
//以下为在BTB中的某个set中选择将要被替换出来的entry
/*
(1)函数名：
(2)接收参数：
bp_addr ： 分支地址预测器
addr ： 分支指令地址
entry ： 寻找到的相应的块
(3)返回值：
(4)函数过程说明：
这个函数是在更新BTB表的时候使用的，在取指令周期，进行分支地址预测时，
不会使用这个函数。而更新BTB表则是在第四个周期即完成周期进行的
利用完成周期时处理的的分支指令地址，
此时的结果不可能为NULL
(5)修改于：
2005-9-6 11:06
(6)作者：
(sha)fish
*/
void
bpred_replaced_entry( struct bpred_addr_t* bp_addr,
addr_t addr,
struct bpred_btb_entry_t** entry
)
{
byte_t n;
byte_t nx;
long k;
long max;
struct bpred_btb_t* bp_btb;
struct bpred_btb_set_t* bp_set;
struct bpred_btb_entry_t* bp_entry;
struct bpred_btb_entry_t* bp_entry2;
ASSERT(bp_addr!=NULL);
ASSERT((*entry)==NULL);
bp_addr->lookups++;
//得到BTB表
bp_btb = bp_addr->btb;
//得到BTB表内的某一个组
bp_set = (bp_btb->set + BPRED_GET_BTB_SET(bp_btb, addr));
//得到组内的entry
bp_entry = bp_set->head;
ASSERT(bp_entry!=NULL);
for(n=0; n<bp_btb->associative; n++)
{
if(bp_entry->valid==0)
break;
else
bp_entry = bp_entry->next;
}
//如果有空位置
if(bp_entry)
{
if( (bp_btb->policy==BTB_LRU)||(bp_btb->policy==BTB_FIFO) )
{
bp_entry2 = bp_set->head;
ASSERT(bp_entry2!=NULL);
//因为要新调进来块
//因此对其他块来说，计数器的值要变化
for(n=0; n<bp_btb->associative; n++)
{
if(bp_entry2->valid==1)
{
bp_entry2->counter++;
}
bp_entry2 = bp_entry2->next;
}
ASSERT(bp_entry2==NULL);
bp_entry->counter = 0;
}
*entry = bp_entry;
}
//如果没有空位置
else if(bp_entry==NULL)
{
if(bp_btb->policy==BTB_RANDOM)
{
k = random(bp_btb->associative);
//得到将要被替换出去的块
bp_entry = bp_set->head + k;
}
else if((bp_btb->policy==BTB_LRU)||(bp_btb->policy==BTB_FIFO) )
{
//寻找计数器最大的一个块准备替换
bp_entry = bp_set->head;
max = bp_entry->counter;
nx = 0;
for(n=1; n<bp_btb->associative; n++)
{
bp_entry2 = bp_entry+1;
//此时可以不判断valid的值，因为这儿的前提是
//没有空位置，也就是说valid都为1
if((counter_t)max < bp_entry2->counter)
{
max = bp_entry2->counter;
nx = n;
}
bp_entry = bp_entry2;
}
//得到计数器最大的一个块
bp_entry = bp_set->head+nx;
ASSERT(bp_entry!=NULL);
//现在得到了计数器最大的一个块
//然后把这个块的计数器值置为0，其他块的计数器值加“1”
bp_entry2 = bp_set->head;
for(n=0; n<bp_btb->associative; n++)
{
if(n!=nx)
{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -