《深入理解计算机系统》实验四Architecture Lab
《深入理解计算机系统》实验四Architecture Lab(满分)
·
前言
《深入理解计算机系统》实验四Architecture Lab下载和官方文档机翻请看：
《深入理解计算机系统》实验四Architecture Lab下载和官方文档机翻
我觉得这个文档对整个实验很有帮助。
如果你的Y86-64环境还没安装好可以看：
《深入理解计算机系统》Y86-64实验四Architecture Lab环境安装：
《深入理解计算机系统》Y86-64实验四Architecture Lab环境安装
C部分的CPE
12.70->12.55->11.55->9.06->8.34->8.19->7.80->7.49(满分)。
建议看完第五章在来写C部分
A部分
在本部分中，您将在sim/misc目录下工作。
您的任务是编写并模拟下面三个Y86-64程序。这些程序所需的行为由examples.c中的示例C函数定义。确保把你的名字和ID放在每个程序开始的注释中。你可以先用YAS程序组装你的程序，然后用指令集模拟器YIS运行它们。
在所有Y86-64函数中，都应该遵循x86-64约定来传递函数参数、使用寄存器和使用堆栈。这包括保存和恢复您使用的所有调用保存寄存器。
第一题sum.ys
编写Y86-64程序求和。sum.ys迭代地对链表的元素求和。您的程序应该由一些代码组成，这些代码设置堆栈结构，调用函数，然后停止。在本例中，函数应该是函数(sum_list)的Y86-64代码，该函数在功能上与下面的C函数sum_list等效。使用下面的三个元素列表来测试你的程序:
/* linked list element */
typedef struct ELE {
long val;
struct ELE *next;
} *list_ptr;
/* sum_list - 对链表的元素求和 */
long sum_list(list_ptr ls)
{
long val = 0;
while (ls) {
val += ls->val;
ls = ls->next;
}
return val;
}
参照sim/y86-code/asum.yo(CS:APP3e图4.8)的格式。编写sum_list的Y86-64汇编代码
sum.ys:
.pos 0
irmovq stack,%rsp
call main
halt
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
main:
irmovq ele1,%rdi
call sum_list
ret
# long sum_list(list_ptr ls)
# ls in %rdi
sum_list:
xorq %rax,%rax # val = 0
mrmovq (%rdi),%rsi
andq %rsi,%rsi # Set CC
jmp test # Goto test
loop:
addq %rsi,%rax #累加
mrmovq 8(%rdi),%rdi #指向下一个节点
andq %rdi,%rdi #set CC 下一个节点是否是0
mrmovq (%rdi),%rsi #(%rdi)表示节点的值
test:
jne loop # Stop when 0
ret # Return
.pos 0x200
stack:
要把sum.ys文件放入sim/y86-code下。
根据simguguide.pdf中的提示进行如下操作
linux> make sum.yo
linux> ../misc/yis sum.yo
如下图所示，可以看到返回值(%rax)是0xcba，说明程序正确。
第二题rsum.ys
编写一个Y86-64程序rsum.ys，递归地对链表的元素求和。这段代码应该类似于sum.ys中的代码，除了它应该使用一个函数rsum_list来递归地求和一个数字列表，如下面的C函数rsum_list所示。使用第一题测试用的三个元素列表来测试。
/* linked list element */
typedef struct ELE {
long val;
struct ELE *next;
} *list_ptr;
/* rsum_list - sum_list的递归版本 */
long rsum_list(list_ptr ls)
{
if (!ls)
return 0;
else {
long val = ls->val;
long rest = rsum_list(ls->next);
return val + rest;
}
}
编写rsum_list的y86-64汇编代码
rsum.ys
.pos 0
irmovq stack,%rsp
call main
halt
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0
main:
irmovq ele1,%rdi
call rsum_list
ret
# long rsum_list(list_ptr ls)
# ls in %rdi
rsum_list:
pushq %rbx
xorq %rax,%rax # val = 0
rrmovq %rdi,%rsi
andq %rsi,%rsi #判断当前节点是否为0
je exit
mrmovq (%rdi),%rbx #获取当前节点的值val
mrmovq 8(%rdi),%rdi #指向下一节点
call rsum_list #递归。返回值(%rax)即rest
addq %rbx,%rax #val+rest
popq %rbx
ret # Return
exit:
popq %rbx
ret
.pos 0x200
stack:
运行如下(同第一题同)：
如下图所示，可以看到返回值(%rax)是0xcba，说明程序正确。
第三题copy.ys
编写一个程序(copy.ys)，将一块单词从内存的一部分复制到内存的另一部分(非重叠区域)，计算所有被复制单词的校验和(Xor)。你的程序应该由建立堆栈框架，调用函数复制块，然后停止的代码组成。该函数在功能上应该与下所示的C函数复制块相同。使用以下三个元素的源和目标块来测试你的程序:
/* copy_block - 将src拷贝到dest并返回xor校验和 */
long copy_block(long *src, long *dest, long len)
{
long result = 0;
while (len > 0) {
long val = *src++;
*dest++ = val;
result ^= val;
len--;
}
return result;
}
编写copy_block的y86-64汇编代码
copy.ys:
.pos 0
irmovq stack,%rsp
call main
halt
.align 8
src:
.quad 0x00a
.quad 0x0b0
.quad 0xc00
dest:
.quad 0x111
.quad 0x222
.quad 0x333
main:
irmovq src,%rdi
irmovq dest,%rsi
irmovq $3,%rdx #有3个要复制
call copy_block #copy_block(%rdi,%rsi,%rdx)
ret
copy_block:
pushq %rbx #%rbx是被调用者保护，入栈
xorq %rax,%rax
irmovq $8,%r8 #常数8.指向下一个
irmovq $1,%r9 #常数1.
andq %rdx,%rdx
jle exit #<=0退出
loop:
mrmovq (%rdi),%rbx #获取src第一个词
addq %r8,%rdi #指向下一个词
rmmovq %rbx,(%rsi) #把src的复制给dest
addq %r8,%rsi #指向下一个复制区
xorq %rbx,%rax #计算所有被复制单词的校验和(Xor)
subq %r9,%rdx #还剩下几个
andq %rdx,%rdx #>0继续循环
jg loop
exit:
popq %rbx
ret
.pos 0x200
stack:
运行如下：
可以看到校验和%rax，是对的。
dest也被改变为src的值，说明复制过去了。程序正确
B部分
在这一部分中，您将在目录sim/seq中工作。
你在B部分的任务是扩展SEQ处理器以支持iaddq，在家庭作业问题4.51和4.52中描述了这一点。要添加此说明，您需要修改文件seq-full.hcl。它实现了CS:APP3e教科书中描述的SEQ版本。此外，它还包含解决方案所需的一些常量的声明。
家庭作业
4.51：练习题4.3介绍了iaddq指令，即将立即数与寄存器相加。描述实现该指令所执行的计算。参考irmovq和OPq指令的计算
4.52：文件seq- full.hcl包含SQL的HCL描述，并将常数IIADDQ声明为十六进制c，也就是iaddq的指令代码。修改实现iaddq指令的控制逻辑块的HCl描述，就像练习题4.3和家庭作业4.51中描述的那样。可以参考实验资料获得如何为你的解答生成模拟器以及如何测试模拟器的指导。
练习题4.3：机器级程序中常见的模式之一是将一根常数值与一根寄存器相加。利用目前已给出的Y86-64指令，实现这个操作需要一条irmovq指令把常数加载到寄存器，然后一条addq指令把这个寄存器值与目标寄存器值相加。假设我们想增加一条新指令iaddq，格式如下：
该指令将常数值V与寄存器rB相加。这就是我们要做的事情。
根据这些提示
写出了iaddq在顺序实现中的计算
| 阶段 | iaddq V,rB |
|---|---|
| 取值 | icode:ifun<-M1[PC] rA:rB<-M1[PC+1] valC<-M8[PC+2] valP<-PC+10 |
| 译码 | valB<-R[rB] |
| 执行 | valE<-valB+valC Set CC |
| 访存 | |
| 写回 | R[rB]<-valE |
| 更新PC | PC<-valP |
现在要做的事情，就是修改seq-full.hcl。
打开可以看见
往下翻可以看到已经添加上了iaddq的指令代码(下面的修改可以参考《CS:APP3e》图4.18~4.21)
在往下翻可以看到取值阶段(Fetch Stage)(可参考《CS:APP3e》P278)
iaddq v,rB的取值阶段的操作是
icode:ifun<-M1[PC] #需要是合法的Y86-64指令
rA:rB<-M1[PC+1] #有寄存器
valC<-M8[PC+2] #有常数值
valP<-PC+10
所以更改取值阶段(Fetch Stage)内容为：
在往下翻可以看到译码和写回阶段(Decode Stage)(可参考《CS:APP3e》P279)
我们写的iaddq v,rB在译码阶段的操作是
valB<-R[rB] #rB
在写回阶段是
R[rB]<-valE #valE和rB
所以更改译码和写回阶段(Decode Stage)为：
在往下翻可以看到执行阶段(Execute Stage)(可参考《CS:APP3e》P280)
我们的iaddq指令在执行阶段进行的操作是：
valE<-valB+valC
可知aluB为valB，aluA为valC。条件码需要更新
所以更改执行阶段(Execute Stage)为：
访存阶段(Memory Stage )和更新PC阶段(Program Counter Update)都不用改动。
根据archlab.pdf的内容来测试我们的方案
如下所示：
测试成功
最终的seq-full.hcl文件
#/* $begin seq-all-hcl */
####################################################################
# HCL Description of Control for Single Cycle Y86-64 Processor SEQ #
# Copyright (C) Randal E. Bryant, David R. O'Hallaron, 2010 #
####################################################################
## Your task is to implement the iaddq instruction(您的任务是实现iaddq指令)
## The file contains a declaration of the icodes(该文件包含一个icode的声明)
## for iaddq (IIADDQ)
## Your job is to add the rest of the logic to make it work(你的工作是添加剩下的逻辑使它工作)
####################################################################
# C Include's. Don't alter these #
####################################################################
quote '#include <stdio.h>'
quote '#include "isa.h"'
quote '#include "sim.h"'
quote 'int sim_main(int argc, char *argv[]);'
quote 'word_t gen_pc(){return 0;}'
quote 'int main(int argc, char *argv[])'
quote ' {plusmode=0;return sim_main(argc,argv);}'
####################################################################
# Declarations. Do not change/remove/delete any of these #
####################################################################
##### Symbolic representation of Y86-64 Instruction Codes #############
wordsig INOP 'I_NOP'
wordsig IHALT 'I_HALT'
wordsig IRRMOVQ 'I_RRMOVQ'
wordsig IIRMOVQ 'I_IRMOVQ'
wordsig IRMMOVQ 'I_RMMOVQ'
wordsig IMRMOVQ 'I_MRMOVQ'
wordsig IOPQ 'I_ALU'
wordsig IJXX 'I_JMP'
wordsig ICALL 'I_CALL'
wordsig IRET 'I_RET'
wordsig IPUSHQ 'I_PUSHQ'
wordsig IPOPQ 'I_POPQ'
# Instruction code for iaddq instruction(iaddq指令的指令代码)
wordsig IIADDQ 'I_IADDQ'
##### Symbolic represenations of Y86-64 function codes #####
wordsig FNONE 'F_NONE' # Default function code
##### Symbolic representation of Y86-64 Registers referenced explicitly #####
wordsig RRSP 'REG_RSP' # Stack Pointer
wordsig RNONE 'REG_NONE' # Special value indicating "no register"
##### ALU Functions referenced explicitly #####
wordsig ALUADD 'A_ADD' # ALU should add its arguments
##### Possible instruction status values #####
wordsig SAOK 'STAT_AOK' # Normal execution
wordsig SADR 'STAT_ADR' # Invalid memory address
wordsig SINS 'STAT_INS' # Invalid instruction
wordsig SHLT 'STAT_HLT' # Halt instruction encountered
##### Signals that can be referenced by control logic ####################
##### Fetch stage inputs #####
wordsig pc 'pc' # Program counter
##### Fetch stage computations #####
wordsig imem_icode 'imem_icode' # icode field from instruction memory
wordsig imem_ifun 'imem_ifun' # ifun field from instruction memory
wordsig icode 'icode' # Instruction control code
wordsig ifun 'ifun' # Instruction function
wordsig rA 'ra' # rA field from instruction
wordsig rB 'rb' # rB field from instruction
wordsig valC 'valc' # Constant from instruction
wordsig valP 'valp' # Address of following instruction
boolsig imem_error 'imem_error' # Error signal from instruction memory
boolsig instr_valid 'instr_valid' # Is fetched instruction valid?
##### Decode stage computations #####
wordsig valA 'vala' # Value from register A port
wordsig valB 'valb' # Value from register B port
##### Execute stage computations #####
wordsig valE 'vale' # Value computed by ALU
boolsig Cnd 'cond' # Branch test
##### Memory stage computations #####
wordsig valM 'valm' # Value read from memory
boolsig dmem_error 'dmem_error' # Error signal from data memory
####################################################################
# Control Signal Definitions. #
####################################################################
################ Fetch Stage ###################################
# Determine instruction code(确定指令代码)
word icode = [
imem_error: INOP; #INOP：nop的指令代码
1: imem_icode; # Default: get from instruction memory
];
# Determine instruction function(确定指令功能)
word ifun = [
imem_error: FNONE; #FNONE：默认功能码
1: imem_ifun; # Default: get from instruction memory
];
#这个字节对应于一个合法的Y86-64指令吗？这个信号用来发现不合法的指令
bool instr_valid = icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ,IIADDQ};
# 这个指令包括一个寄存器指示符字节吗？
# Does fetched instruction require a regid byte?
bool need_regids =
icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
IIRMOVQ, IRMMOVQ, IMRMOVQ,IIADDQ};
#这个指令包括一个常数字吗?
# Does fetched instruction require a constant word?
bool need_valC =
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL,IIADDQ};
################ Decode Stage ###################################
# 什么寄存器应该用作A源?
## What register should be used as the A source?
word srcA = [
icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : rA;
icode in { IPOPQ, IRET } : RRSP;
1 : RNONE; # Don't need register
];
# 什么寄存器应该用作B源?
## What register should be used as the B source?
word srcB = [
icode in { IOPQ, IRMMOVQ, IMRMOVQ,IIADDQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
# E目的地应该使用什么寄存器?
## What register should be used as the E destination?
word dstE = [
icode in { IRRMOVQ } && Cnd : rB;
icode in { IIRMOVQ, IOPQ,IIADDQ} : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't write any register
];
# M目的地应该使用什么寄存器?
## What register should be used as the M destination?
word dstM = [
icode in { IMRMOVQ, IPOPQ } : rA;
1 : RNONE; # Don't write any register
];
################ Execute Stage ###################################
#选择输入A到ALU
## Select input A to ALU
word aluA = [
icode in { IRRMOVQ, IOPQ } : valA;
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ ,IIADDQ} : valC;
icode in { ICALL, IPUSHQ } : -8;
icode in { IRET, IPOPQ } : 8;
# Other instructions don't need ALU
];
#选择输入B到ALU
## Select input B to ALU
word aluB = [
icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
IPUSHQ, IRET, IPOPQ ,IIADDQ} : valB;
icode in { IRRMOVQ, IIRMOVQ } : 0;
# Other instructions don't need ALU
];
#设置ALU功能。默认加法
## Set the ALU function
word alufun = [
icode == IOPQ : ifun;
1 : ALUADD;
];
#条件码是否需要更新?
## Should the condition codes be updated?
bool set_cc = icode in { IOPQ ,IIADDQ};
################ Memory Stage ###################################
## Set read control signal
bool mem_read = icode in { IMRMOVQ, IPOPQ, IRET };
## Set write control signal
bool mem_write = icode in { IRMMOVQ, IPUSHQ, ICALL };
## Select memory address
word mem_addr = [
icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : valE;
icode in { IPOPQ, IRET } : valA;
# Other instructions don't need address
];
## Select memory input data
word mem_data = [
# Value from register
icode in { IRMMOVQ, IPUSHQ } : valA;
# Return PC
icode == ICALL : valP;
# Default: Don't write anything
];
## Determine instruction status
word Stat = [
imem_error || dmem_error : SADR;
!instr_valid: SINS;
icode == IHALT : SHLT;
1 : SAOK;
];
################ Program Counter Update ############################
## What address should instruction be fetched at
word new_pc = [
# Call. Use instruction constant
icode == ICALL : valC;
# Taken branch. Use instruction constant
icode == IJXX && Cnd : valC;
# Completion of RET instruction. Use value from stack
icode == IRET : valM;
# Default: Use incremented PC
1 : valP;
];
#/* $end seq-all-hcl */
C部分
这一部分推荐看完第五章再来完成。
在这一部分中，您将在目录sim/pipe中工作。
图2中的ncopy函数将len元素整数数组src复制到一个不重叠的dst，重新计算src中包含的正整数数。
在C部分中，您的任务是修改ncopy.ys和pipe-full.hcl，以创建ncopy。让我们尽可能快地运行。
测试了一下默认版本的(即自带的图3)，CPE平均为15.18，和文档写的一样，只是熟悉下流程。文档中写道他们最好的版本平均为7.48。
实现iaddq
看了下图3可以发现可以实现iaddq来提高性能，iaddq实现和B部分的一样。参考B部分的seq-full.hcl。
| 阶段 | iaddq V,rB |
|---|---|
| 取值 | icode:ifun<-M1[PC] rA:rB<-M1[PC+1] valC<-M8[PC+2] valP<-PC+10 |
| 译码 | valB<-R[rB] |
| 执行 | valE<-valB+valC Set CC |
| 访存 | |
| 写回 | R[rB]<-valE |
| 更新PC | PC<-valP |
取值阶段(Fetch Stage)
译码阶段(Decode Stage)
执行阶段(Execute Stage)
其他就不用改了
源文件pipe-full.hcl
#/* $begin pipe-all-hcl */
####################################################################
# HCL Description of Control for Pipelined Y86-64 Processor #
# Copyright (C) Randal E. Bryant, David R. O'Hallaron, 2014 #
####################################################################
## Your task is to implement the iaddq instruction
## The file contains a declaration of the icodes
## for iaddq (IIADDQ)
## Your job is to add the rest of the logic to make it work
####################################################################
# C Include's. Don't alter these #
####################################################################
quote '#include <stdio.h>'
quote '#include "isa.h"'
quote '#include "pipeline.h"'
quote '#include "stages.h"'
quote '#include "sim.h"'
quote 'int sim_main(int argc, char *argv[]);'
quote 'int main(int argc, char *argv[]){return sim_main(argc,argv);}'
####################################################################
# Declarations. Do not change/remove/delete any of these #
####################################################################
##### Symbolic representation of Y86-64 Instruction Codes #############
wordsig INOP 'I_NOP'
wordsig IHALT 'I_HALT'
wordsig IRRMOVQ 'I_RRMOVQ'
wordsig IIRMOVQ 'I_IRMOVQ'
wordsig IRMMOVQ 'I_RMMOVQ'
wordsig IMRMOVQ 'I_MRMOVQ'
wordsig IOPQ 'I_ALU'
wordsig IJXX 'I_JMP'
wordsig ICALL 'I_CALL'
wordsig IRET 'I_RET'
wordsig IPUSHQ 'I_PUSHQ'
wordsig IPOPQ 'I_POPQ'
# Instruction code for iaddq instruction
wordsig IIADDQ 'I_IADDQ'
##### Symbolic represenations of Y86-64 function codes #####
wordsig FNONE 'F_NONE' # Default function code
##### 引用的Y86-64寄存器的符号表示 #####
wordsig RRSP 'REG_RSP' # 堆栈指针
wordsig RNONE 'REG_NONE' # 表示“无寄存器”的特殊值
##### ALU函数被显式引用 ##########################
wordsig ALUADD 'A_ADD' # ALU should add its arguments
##### 可能的指令状态值 #####
wordsig SBUB 'STAT_BUB' # 泡沫阶段
wordsig SAOK 'STAT_AOK' # 正常执行
wordsig SADR 'STAT_ADR' # 无效的内存地址
wordsig SINS 'STAT_INS' # 无效的指令
wordsig SHLT 'STAT_HLT' # 停止指令遇到
##### 控制逻辑可以引用的信号 ##############
##### 流水线寄存器F ##########################################
wordsig F_predPC 'pc_curr->pc' # PC预测值
##### 取值阶段的中间值 ###########################
wordsig imem_icode 'imem_icode' # 指令存储器中的代码字段
wordsig imem_ifun 'imem_ifun' # 指令存储器中的ifun字段
wordsig f_icode 'if_id_next->icode' # (可能修改过的)指令代码
wordsig f_ifun 'if_id_next->ifun' # 获取指令功能
wordsig f_valC 'if_id_next->valc' # 被取指令的固定数据
wordsig f_valP 'if_id_next->valp' # 下条指令的地址
boolsig imem_error 'imem_error' # 来自指令存储器的错误信号
boolsig instr_valid 'instr_valid' # 获取的指令有效吗?
##### 流水线寄存器D ##########################################
wordsig D_icode 'if_id_curr->icode' # 指令码
wordsig D_rA 'if_id_curr->ra' # 指令的rA字段
wordsig D_rB 'if_id_curr->rb' # 指令的rB字段
wordsig D_valP 'if_id_curr->valp' # 递增PC
##### 译码阶段的中间值 #########################
wordsig d_srcA 'id_ex_next->srca' # srcA来自译码指令
wordsig d_srcB 'id_ex_next->srcb' # srcB来自译码指令
wordsig d_rvalA 'd_regvala' # 从寄存器文件读取的valA
wordsig d_rvalB 'd_regvalb' # 从寄存器文件读取的valB
##### 流水线寄存器E ##########################################
wordsig E_icode 'id_ex_curr->icode' # 指令码
wordsig E_ifun 'id_ex_curr->ifun' # 指令功能
wordsig E_valC 'id_ex_curr->valc' # 常量数据
wordsig E_srcA 'id_ex_curr->srca' # 源A寄存器ID
wordsig E_valA 'id_ex_curr->vala' # 源 A 值
wordsig E_srcB 'id_ex_curr->srcb' # 源B寄存器ID
wordsig E_valB 'id_ex_curr->valb' # 源 B 值
wordsig E_dstE 'id_ex_curr->deste' # 目的E寄存器ID
wordsig E_dstM 'id_ex_curr->destm' # 目的M寄存器ID
##### 执行阶段的中间值 #########################
wordsig e_valE 'ex_mem_next->vale' # 由ALU产生的valE
boolsig e_Cnd 'ex_mem_next->takebranch' # 这个条件成立吗？
wordsig e_dstE 'ex_mem_next->deste' # dstE(可能修改为RNONE)
##### 流水线寄存器M #########################
wordsig M_stat 'ex_mem_curr->status' # 指令状态
wordsig M_icode 'ex_mem_curr->icode' # 指令码
wordsig M_ifun 'ex_mem_curr->ifun' # 指令功能
wordsig M_valA 'ex_mem_curr->vala' # 源 A 值
wordsig M_dstE 'ex_mem_curr->deste' # 目的E寄存器ID
wordsig M_valE 'ex_mem_curr->vale' # ALU E值
wordsig M_dstM 'ex_mem_curr->destm' # 目的M寄存器ID
boolsig M_Cnd 'ex_mem_curr->takebranch' # 状态标志
boolsig dmem_error 'dmem_error' # 来自指令存储器的错误信号
##### 访存阶段的中间值 ##########################
wordsig m_valM 'mem_wb_next->valm' # 由内存产生的valM
wordsig m_stat 'mem_wb_next->status' # stat(可能修改为SADR)
##### 流水线寄存器W ##########################################
wordsig W_stat 'mem_wb_curr->status' # 指令状态
wordsig W_icode 'mem_wb_curr->icode' # 指令码
wordsig W_dstE 'mem_wb_curr->deste' # 目的E寄存器ID
wordsig W_valE 'mem_wb_curr->vale' # ALU E值
wordsig W_dstM 'mem_wb_curr->destm' # 目的M寄存器ID
wordsig W_valM 'mem_wb_curr->valm' # 内存M值
####################################################################
# 控制信号的定义。 #
####################################################################
################ 取值阶段(Fetch Stage) ###################################
## 指令应该在哪个地址取
word f_pc = [
# 预测失误的分支。在递增的PC上获取(Mispredicted branch. Fetch at incremented PC)
M_icode == IJXX && !M_Cnd : M_valA;
# 完成RET指令
W_icode == IRET : W_valM;
# 默认值：使用PC的预测值
1 : F_predPC;
];
## 确定所取指令的代码
word f_icode = [
imem_error : INOP;
1: imem_icode;
];
# 确定ifun
word f_ifun = [
imem_error : FNONE;
1: imem_ifun;
];
# 指令有效吗?
bool instr_valid = f_icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ ,IIADDQ};
# 确定所取指令的状态代码
word f_stat = [
imem_error: SADR;
!instr_valid : SINS;
f_icode == IHALT : SHLT;
1 : SAOK;
];
# 获取的指令是否需要寄存器指示符字节？
bool need_regids =
f_icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
IIRMOVQ, IRMMOVQ, IMRMOVQ ,IIADDQ};
# 获取的指令需要一个常数字吗?
bool need_valC =
f_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL ,IIADDQ};
# 预测PC的下一个值
word f_predPC = [
f_icode in { IJXX, ICALL } : f_valC;
1 : f_valP;
];
################ 译码阶段(Decode Stage) ######################################
## 什么寄存器应该用作A源?
word d_srcA = [
D_icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : D_rA;
D_icode in { IPOPQ, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## 什么寄存器应该用作B源?
word d_srcB = [
D_icode in { IOPQ, IRMMOVQ, IMRMOVQ ,IIADDQ} : D_rB;
D_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## E目的地应该使用什么寄存器?
word d_dstE = [
D_icode in { IRRMOVQ, IIRMOVQ, IOPQ,IIADDQ} : D_rB;
D_icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't write any register
];
## M目的地应该使用什么寄存器?
word d_dstM = [
D_icode in { IMRMOVQ, IPOPQ } : D_rA;
1 : RNONE; # Don't write any register
];
## A值应该是多少?
## valA进入译码阶段
word d_valA = [
D_icode in { ICALL, IJXX } : D_valP; # 使用递增PC
d_srcA == e_dstE : e_valE; # 从execute(执行)转发valE
d_srcA == M_dstM : m_valM; # 从Memory(访存)转发valM
d_srcA == M_dstE : M_valE; # 从Memory(访存)转发valE
d_srcA == W_dstM : W_valM; # 从write back(写回)转发valM
d_srcA == W_dstE : W_valE; # 从write back(写回)转发valE
1 : d_rvalA; # 使用从寄存器文件读取的值
];
word d_valB = [
d_srcB == e_dstE : e_valE; # 从execute(执行)转发valE
d_srcB == M_dstM : m_valM; # 从Memory(访存)转发valM
d_srcB == M_dstE : M_valE; # 从Memory(访存)转发valE
d_srcB == W_dstM : W_valM; # 从write back(写回)转发valM
d_srcB == W_dstE : W_valE; # 从write back(写回)转发valE
1 : d_rvalB; # 使用从寄存器文件读取的值
];
################ 执行阶段(Execute Stage) #####################################
## 选择输入A到ALU
word aluA = [
E_icode in { IRRMOVQ, IOPQ } : E_valA;
E_icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ ,IIADDQ} : E_valC;
E_icode in { ICALL, IPUSHQ } : -8;
E_icode in { IRET, IPOPQ } : 8;
# 其他指令不需要ALU
];
## 选择输入B到ALU
word aluB = [
E_icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL,
IPUSHQ, IRET, IPOPQ ,IIADDQ} : E_valB;
E_icode in { IRRMOVQ, IIRMOVQ } : 0;
# 其他指令不需要ALU
];
## 设置ALU功能
word alufun = [
E_icode == IOPQ : E_ifun;
1 : ALUADD;
];
## 条件码是否需要更新?
bool set_cc = (E_icode == IOPQ || E_icode == IIADDQ) &&
# 状态仅在正常操作期间更改
!m_stat in { SADR, SINS, SHLT } && !W_stat in { SADR, SINS, SHLT };
## 在执行阶段生成valA
word e_valA = E_valA; # Pass valA through stage
# 在未采取有条件移动的情况下，将dstE设置为RNONE
## Set dstE to RNONE in event of not-taken conditional move
word e_dstE = [
E_icode == IRRMOVQ && !e_Cnd : RNONE;
1 : E_dstE;
];
################ 访存阶段(Memory Stage) ######################################
## 选择内存地址
word mem_addr = [
M_icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : M_valE;
M_icode in { IPOPQ, IRET } : M_valA;
# Other instructions don't need address
];
## 设置读控制信号
bool mem_read = M_icode in { IMRMOVQ, IPOPQ, IRET };
## 设置写控制信号
bool mem_write = M_icode in { IRMMOVQ, IPUSHQ, ICALL };
#/* $begin pipe-m_stat-hcl */
## 更新状态
word m_stat = [
dmem_error : SADR;
1 : M_stat;
];
#/* $end pipe-m_stat-hcl */
## 设置E端口寄存器ID
word w_dstE = W_dstE;
## 设置E端口值
word w_valE = W_valE;
## 设置M端口寄存器ID
word w_dstM = W_dstM;
## 设置M端口值
word w_valM = W_valM;
## 更新处理器状态
word Stat = [
W_stat == SBUB : SAOK;
1 : W_stat;
];
################ 流水线寄存器控制(Pipeline Register Control) ##################
# 我应该暂停还是向管道寄存器F中注入气泡？
# 其中至多有一个是真的。
bool F_bubble = 0;
bool F_stall =
# 加载/使用数据冒险条件
E_icode in { IMRMOVQ, IPOPQ} &&
E_dstM in { d_srcA, d_srcB } ||
# 当ret通过管道时，在获取时延迟
IRET in { D_icode, E_icode, M_icode };
# 我应该暂停还是向管道寄存器D中注入气泡？
# 其中至多有一个是真的。
bool D_stall =
# 加载/使用数据冒险条件
E_icode in { IMRMOVQ, IPOPQ} &&
E_dstM in { d_srcA, d_srcB };
bool D_bubble =
# Mispredicted branch(预测失误分支)
(E_icode == IJXX && !e_Cnd) ||
# 当ret通过管道时，在获取时延迟
# 但不是加载/使用数据冒险条件
!(E_icode in { IMRMOVQ, IPOPQ} && E_dstM in { d_srcA, d_srcB }) &&
IRET in { D_icode, E_icode, M_icode };
# 我应该暂停还是向管道寄存器E中注入气泡？
# 其中至多有一个是真的。
bool E_stall = 0;
bool E_bubble =
# Mispredicted branch(预测失误分支)
(E_icode == IJXX && !e_Cnd) ||
# 加载/使用数据冒险条件
E_icode in { IMRMOVQ, IPOPQ} &&
E_dstM in { d_srcA, d_srcB};
# 应该暂停还是向管道寄存器M中注入气泡？
# 其中至多有一个是真的。
bool M_stall = 0;
# 一旦异常通过内存阶段，就开始注入气泡
bool M_bubble = m_stat in { SADR, SINS, SHLT } || W_stat in { SADR, SINS, SHLT };
# 应该暂停还是向管道寄存器W中注入气泡？
bool W_stall = W_stat in { SADR, SINS, SHLT };
bool W_bubble = 0;
#/* $end pipe-all-hcl */
在sim/pipe中输入一下命令，测试
linux> ./psim -t ../y86-code/asumi.yo
linux> (cd ../ptest;make SIM=../pipe/psim TFLAGS=-i)
linux> (cd ../ptest;make SIM=../pipe/psim)
测试成功。
CPE：12.70
实现了iaddq指令接下来修改ncopy.ys文件。把这种
irmovq $1, %r10
addq %r10, %rax
改为这种
iaddq $1,%rax
ncopy.ys如下所示
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len <= 0?
jle Done # if so, goto Done:
Loop:
mrmovq (%rdi), %r10 # read val from src...
rmmovq %r10, (%rsi) # ...and store it to dst
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
iaddq $1, %rax # count++
Npos:
iaddq $-1, %rdx # len--
iaddq $8, %rdi # src++
iaddq $8, %rsi # dst++
andq %rdx,%rdx # len > 0?
jg Loop # if so, goto Loop:
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
根据文档每次修改ncopy.ys，可以通过键入重建驱动程序
linux> make drivers
将构造一下两个有用的驱动程序：
- sdriver.yo:一种小型驱动程序，它在带有4个元素的小数组上测试ncopy函数。如果您的解决方案是正确的，那么这个程序将在复制src数组后在寄存器%rax中以2的值停止。
- ldriver.yo:一个大型驱动程序，它在带有63个元素的较大数组上测试一个ncopy函数。如果您的解决方案是正确的，那么在复制src数组之后，这个程序将在寄存器%rax中的值为31 (0x1f)时停止
用小的4元素数组测试解决方案
linux> ./psim -t sdriver.yo
测试正确
用大的63元素数组测试解决方案
linux> ./psim -t ldriver.yo
测试正确
在进行其他测试
使用ISA模拟器在块长度范围内测试代码。Perl脚本correctness.pl生成的驱动程序文件块长度从0到某个限制(默认值为65)，再加上一些更大的块长度。它模拟它们(默认情况下使用YIS)，并检查结果。它生成一个报告，显示每个块长度的状态:
linux> ./correctness.pl
会出现一大堆OK
没问题
在基准程序上测试管道模拟器。一旦你的模拟器能够正确地执行sdriver.ys和ldriver.ys，你应该在…/y86-code中测试Y86-64基准程序:
linux> (cd ../y86-code;make testpsim)
这将在基准测试程序上运行psim，并将结果与YIS进行比较。
没问题
使用大量回归测试测试管道模拟器。一旦可以正确地执行基准测试程序，就应该使用…/ptest中的回归测试来检查它。例如，如果您的解决方案实现了iaddq指令，那么
linux> (cd ../ptest;make SIM=../pipe/psim TFLAGS=-i)
没问题
使用流水线模拟器在一定范围的块长度上测试代码。最后，您可以在管道模拟器上运行与前面使用ISA模拟器所做的相同的代码测试
linux> ./correctness.pl -p
会出现一堆OK
也没问题。
最后来计算CPE值
linux> ./benchmark.pl
从15.18进步到12.70。但是还是0分(尴尬哈哈哈哈)
熟悉了流程。
CPE：12.55
因为采取的是总是选择分支的预测策略，所以这个总是去到ret处。
而很明显的是len<=0的概率肯定没len>0的高，所以改成
上面的测试流程走一遍
最后是CPE：12.55
分数：0
CPE：11.55
注意到这里，第一条指令从内存中读出寄存器%rdi的值，而下一条指令需要该值作为源操作数。所以这里会将下一条指令暂停一个周期，导致执行阶段中插入一个气泡。
每一次循环都要插入一个气泡，对于性能来说是很有点糟糕的。
所以我们可以在两条指令中间插入一条指令。
移动后面的指令，修改为：
可以看到这次就没有暂停了，变成了iaddq指令
运行的CPE为：11.55（0分）
CPE：9.06
老实说，从CPE来看上面都是一些小改动。最主要的是这个循环次数。根据文档上的提示，看了下第五章关于循环的部分。我想到了，一次循环我复制两块的值，整体循环就可以减少差不多一半。2 X 1循环展开
就可以两两复制。根据该思想写出如下代码：
ncopy.ys
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
iaddq $-2,%rdx
andq %rdx,%rdx
jl remian
Loop:
mrmovq (%rdi), %r10
mrmovq 8(%rdi),%r11 #避免加载使用冒险
rmmovq %r10, (%rsi)
andq %r10, %r10 # val <= 0?
jle NLoop2
iaddq $1,%rax
NLoop2:
rmmovq %r11,8(%rsi)
andq %r11,%r11
jle nextLoop
iaddq $1,%rax
nextLoop:
iaddq $16,%rdi #src=src+2
iaddq $16,%rsi #dst=dst+2
iaddq $-2,%rdx
jge Loop
remian:
iaddq $2,%rdx #恢复
iaddq $-1,%rdx
jl Done
mrmovq (%rdi), %r10 #
iaddq $8, %rdi # src++
rmmovq %r10, (%rsi) #
iaddq $8, %rsi # dst++
iaddq $-1,%rdx
andq %r10, %r10 # val <= 0?
jle Done
iaddq $1, %rax # count++
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
测试一遍没问题。
最后的CPE为：9.06(28.8分。终于有分了)
CPE：8.34
上面经过2 X 1展开CPE降低了很多，后面我又试了3 X 1，4 X 1…到了把寄存器用完就是9 X 1展开，9 X 1展开最后可能剩下8-个元素，对这8-个元素在使用2 X 1展开，使CPE到达了8.34。
代码如下：
ncopy.ys
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy.ys:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len != 0?
jne start
ret
start:
iaddq $-9,%rdx #判断是否有9个数(含)以上
andq %rdx,%rdx
jl LoopLNine
Loop:
mrmovq (%rdi), %r8
mrmovq 8(%rdi),%r9
mrmovq 16(%rdi),%r10
mrmovq 24(%rdi),%r11
mrmovq 32(%rdi),%r12
mrmovq 40(%rdi),%r13
mrmovq 48(%rdi),%rcx
mrmovq 56(%rdi),%rbx
mrmovq 64(%rdi),%rbp
iaddq $72, %rdi #src+9
rmmovq %r8, (%rsi)
rmmovq %r9,8(%rsi)
rmmovq %r10,16(%rsi)
rmmovq %r11,24(%rsi)
rmmovq %r12,32(%rsi)
rmmovq %r13,40(%rsi)
rmmovq %rcx,48(%rsi)
rmmovq %rbx,56(%rsi)
rmmovq %rbp,64(%rsi)
iaddq $72, %rsi #dst+9
andq %r8, %r8
jle two
iaddq $1,%rax
two: #判断9个数是否＞0
andq %r9,%r9
jle three
iaddq $1, %rax
three:
andq %r10,%r10
jle four
iaddq $1,%rax
four:
andq %r11,%r11
jle five
iaddq $1,%rax
five:
andq %r12,%r12
jle six
iaddq $1,%rax
six:
andq %r13,%r13
jle seven
iaddq $1,%rax
seven:
andq %rcx,%rcx
jle eight
iaddq $1,%rax
eight:
andq %rbx,%rbx
jle nine
iaddq $1,%rax
nine:
andq %rbp,%rbp
jle Npos
iaddq $1,%rax
Npos:
iaddq $-9, %rdx #下一轮循环
andq %rdx,%rdx
jge Loop
LoopLNine: #两两复制：
#iaddq $9,%rdx #恢复
#iaddq $-2,%rdx #判断是否有2个数(含)以上
iaddq $7,%rdx #两iaddq二合一
andq %rdx,%rdx
jl remian
Loop2:
mrmovq (%rdi),%r10
mrmovq 8(%rdi),%r11
rmmovq %r10,(%rsi)
andq %r10,%r10
jle NLoop2
iaddq $1,%rax
NLoop2:
rmmovq %r11,8(%rsi)
andq %r11,%r11
jle nextLoop2
iaddq $1,%rax
nextLoop2:
iaddq $16,%rdi
iaddq $16,%rsi
iaddq $-2,%rdx
jge Loop2
remian:
#iaddq $2,%rdx #恢复
#iaddq $-1,%rdx #判断是否有一个数
iaddq $1,%rdx #两iaddq二合一
jl Done
mrmovq (%rdi), %r10 #
iaddq $8, %rdi # src++
rmmovq %r10, (%rsi) #
iaddq $8, %rsi # dst++
iaddq $-1,%rdx
andq %r10, %r10 # val <= 0?
jle Done
iaddq $1, %rax # count++
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
测试一遍没问题。
最后的CPE为：8.34(43.2分。)
后面我还进行了10 X 1、11 ** X ** 1和12 X 1循环展开，性能已经到了瓶颈了都是8.34
优化了上面的代码，不然寄存器不够用
10 X 1循环展开+剩下的数2 X 1循环展开代码如下：
ncopy.ys:
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len != 0?
jne start
ret
start:
iaddq $-10,%rdx #判断是否有10个数(含)以上
andq %rdx,%rdx
jl LoopLTen
Loop:
mrmovq (%rdi), %r8
mrmovq 8(%rdi),%r9
rmmovq %r8, (%rsi)
rmmovq %r9,8(%rsi)
andq %r8, %r8
jle two
iaddq $1,%rax
two:
andq %r9,%r9
jle three
iaddq $1, %rax
three:
mrmovq 16(%rdi),%r8
mrmovq 24(%rdi),%r9
rmmovq %r8,16(%rsi)
rmmovq %r9,24(%rsi)
andq %r8,%r8
jle four
iaddq $1,%rax
four:
andq %r9,%r9
jle five
iaddq $1,%rax
five:
mrmovq 32(%rdi),%r8
mrmovq 40(%rdi),%r9
rmmovq %r8,32(%rsi)
rmmovq %r9,40(%rsi)
andq %r8,%r8
jle six
iaddq $1,%rax
six:
andq %r9,%r9
jle seven
iaddq $1,%rax
seven:
mrmovq 48(%rdi),%r8
mrmovq 56(%rdi),%r9
rmmovq %r8,48(%rsi)
rmmovq %r9,56(%rsi)
andq %r8,%r8
jle eight
iaddq $1,%rax
eight:
andq %r9,%r9
jle nine
iaddq $1,%rax
nine:
mrmovq 64(%rdi),%r8
mrmovq 72(%rdi),%r9
rmmovq %r8,64(%rsi)
rmmovq %r9,72(%rsi)
andq %r8,%r8
jle ten
iaddq $1,%rax
ten:
andq %r9,%r9
jle Npos
iaddq $1,%rax
Npos:
iaddq $80, %rdi #src+10
iaddq $80, %rsi #dst+10
iaddq $-10, %rdx #下一轮循环
andq %rdx,%rdx
jge Loop
LoopLTen: #剩下的10-两两复制：
#iaddq $10,%rdx #恢复
#iaddq $-2,%rdx #判断是否有2个数(含)以上
iaddq $8,%rdx #两iaddq二合一
andq %rdx,%rdx
jl remian
Loop2:
mrmovq (%rdi),%r8
mrmovq 8(%rdi),%r9
rmmovq %r8,(%rsi)
rmmovq %r9,8(%rsi)
andq %r8,%r8
jle NLoop2
iaddq $1,%rax
NLoop2:
andq %r9,%r9
jle nextLoop2
iaddq $1,%rax
nextLoop2:
iaddq $16,%rdi
iaddq $16,%rsi
iaddq $-2,%rdx
jge Loop2
remian:
#iaddq $2,%rdx #恢复
#iaddq $-1,%rdx #判断是否有一个数
iaddq $1,%rdx #两iaddq二合一
jl Done
mrmovq (%rdi), %r10 #
iaddq $8, %rdi # src++
rmmovq %r10, (%rsi) #
iaddq $8, %rsi # dst++
iaddq $-1,%rdx
andq %r10, %r10 # val <= 0?
jle Done
iaddq $1, %rax # count++
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
CPE：8.19
既然10 X 1的大头已经遇到性能瓶颈，那就只能从经过10 X 1循环展开剩下的元素下手，把10 X 1 + 2 X 1 循环展开改成10 X 1 + 3 X 1 + 2 X 1循环展开
ncopy.ys:
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
xorq %rax,%rax # count = 0;
andq %rdx,%rdx # len != 0?
jne start
ret
start:
iaddq $-10,%rdx #判断是否有10个数(含)以上
andq %rdx,%rdx
jl LoopLTen
Loop:
mrmovq (%rdi), %r8
mrmovq 8(%rdi),%r9
rmmovq %r8, (%rsi)
rmmovq %r9,8(%rsi)
andq %r8, %r8
jle two
iaddq $1,%rax
two:
andq %r9,%r9
jle three
iaddq $1, %rax
three:
mrmovq 16(%rdi),%r8
mrmovq 24(%rdi),%r9
rmmovq %r8,16(%rsi)
rmmovq %r9,24(%rsi)
andq %r8,%r8
jle four
iaddq $1,%rax
four:
andq %r9,%r9
jle five
iaddq $1,%rax
five:
mrmovq 32(%rdi),%r8
mrmovq 40(%rdi),%r9
rmmovq %r8,32(%rsi)
rmmovq %r9,40(%rsi)
andq %r8,%r8
jle six
iaddq $1,%rax
six:
andq %r9,%r9
jle seven
iaddq $1,%rax
seven:
mrmovq 48(%rdi),%r8
mrmovq 56(%rdi),%r9
rmmovq %r8,48(%rsi)
rmmovq %r9,56(%rsi)
andq %r8,%r8
jle eight
iaddq $1,%rax
eight:
andq %r9,%r9
jle nine
iaddq $1,%rax
nine:
mrmovq 64(%rdi),%r8
mrmovq 72(%rdi),%r9
rmmovq %r8,64(%rsi)
rmmovq %r9,72(%rsi)
andq %r8,%r8
jle ten
iaddq $1,%rax
ten:
andq %r9,%r9
jle Npos
iaddq $1,%rax
Npos:
iaddq $80, %rdi #src+10
iaddq $80, %rsi #dst+10
iaddq $-10, %rdx #下一轮循环
andq %rdx,%rdx
jge Loop
LoopLTen: #三三复制：
#iaddq $10,%rdx #恢复
#iaddq $-3,%rdx #判断是否有3个数(含)以上
iaddq $7,%rdx #两iaddq二合一
andq %rdx,%rdx
jl remian
Loop2:
mrmovq (%rdi),%r8
mrmovq 8(%rdi),%r9
mrmovq 16(%rdi),%r10
rmmovq %r8,(%rsi)
rmmovq %r9,8(%rsi)
rmmovq %r10,16(%rsi)
andq %r8,%r8
jle NLoop2
iaddq $1,%rax
NLoop2:
andq %r9,%r9
jle NLoop3
iaddq $1,%rax
NLoop3:
andq %r10,%r10
jle nextLoop2
iaddq $1,%rax
nextLoop2:
iaddq $24,%rdi
iaddq $24,%rsi
iaddq $-3,%rdx
jge Loop2
remian:
#iaddq $3,%rdx #恢复
#iaddq $-2,%rdx #判断是否有两个数
iaddq $1,%rdx #两iaddq二合一
jne one
mrmovq (%rdi), %r8 #
mrmovq 8(%rdi), %r9
rmmovq %r8, (%rsi)
rmmovq %r9, 8(%rsi)
andq %r8,%r8
jle rLoop2
iaddq $1,%rax
rLoop2:
andq %r9,%r9
jle Done
iaddq $1, %rax # count++
one:
iaddq $1,%rdx
jne Done
mrmovq (%rdi), %r10 #
iaddq $8, %rdi # src++
rmmovq %r10, (%rsi) #
iaddq $8, %rsi # dst++
andq %r10, %r10 # val <= 0?
jle Done
iaddq $1, %rax # count++
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
CPE：7.80
对CPE：8.19的代码进行了优化
- (%rax)的值默认是0，所以去掉开头的xorq %rax,%rax
- 仔细观察代码
andq %rdx,%rdx
jne start
ret
在one中也可以完成判断，所以去掉 - 以及各种iaddq %rdx后跟andq %rdx的，因为iaddq就会设置条件码，所以去掉andq %rdx,%rdx
iaddq $-10,%rdx
andq %rdx,%rdx
ncpoy.ys:
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
iaddq $-10,%rdx #判断是否有10个数(含)以上
jl LoopLTen
Loop:
mrmovq (%rdi), %r8
mrmovq 8(%rdi),%r9
rmmovq %r8, (%rsi)
rmmovq %r9,8(%rsi)
andq %r8, %r8
jle two
iaddq $1,%rax
two:
andq %r9,%r9
jle three
iaddq $1, %rax
three:
mrmovq 16(%rdi),%r8
mrmovq 24(%rdi),%r9
rmmovq %r8,16(%rsi)
rmmovq %r9,24(%rsi)
andq %r8,%r8
jle four
iaddq $1,%rax
four:
andq %r9,%r9
jle five
iaddq $1,%rax
five:
mrmovq 32(%rdi),%r8
mrmovq 40(%rdi),%r9
rmmovq %r8,32(%rsi)
rmmovq %r9,40(%rsi)
andq %r8,%r8
jle six
iaddq $1,%rax
six:
andq %r9,%r9
jle seven
iaddq $1,%rax
seven:
mrmovq 48(%rdi),%r8
mrmovq 56(%rdi),%r9
rmmovq %r8,48(%rsi)
rmmovq %r9,56(%rsi)
andq %r8,%r8
jle eight
iaddq $1,%rax
eight:
andq %r9,%r9
jle nine
iaddq $1,%rax
nine:
mrmovq 64(%rdi),%r8
mrmovq 72(%rdi),%r9
rmmovq %r8,64(%rsi)
rmmovq %r9,72(%rsi)
andq %r8,%r8
jle ten
iaddq $1,%rax
ten:
andq %r9,%r9
jle Npos
iaddq $1,%rax
Npos:
iaddq $80, %rdi #src+10
iaddq $80, %rsi #dst+10
iaddq $-10, %rdx #下一轮循环
andq %rdx,%rdx
jge Loop
LoopLTen: #三三复制：
#iaddq $10,%rdx #恢复
#iaddq $-3,%rdx #判断是否有3个数(含)以上
iaddq $7,%rdx #两iaddq二合一
jl remian
Loop2:
mrmovq (%rdi),%r8
mrmovq 8(%rdi),%r9
mrmovq 16(%rdi),%r10
rmmovq %r8,(%rsi)
rmmovq %r9,8(%rsi)
rmmovq %r10,16(%rsi)
andq %r8,%r8
jle NLoop2
iaddq $1,%rax
NLoop2:
andq %r9,%r9
jle NLoop3
iaddq $1,%rax
NLoop3:
andq %r10,%r10
jle nextLoop2
iaddq $1,%rax
nextLoop2:
iaddq $24,%rdi
iaddq $24,%rsi
iaddq $-3,%rdx
jge Loop2
remian:
#iaddq $3,%rdx #恢复
#iaddq $-2,%rdx #判断是否有两个数
iaddq $1,%rdx #两iaddq二合一
jne one
mrmovq (%rdi), %r8 #
mrmovq 8(%rdi), %r9
rmmovq %r8, (%rsi)
rmmovq %r9, 8(%rsi)
andq %r8,%r8
jle rLoop2
iaddq $1,%rax
rLoop2:
andq %r9,%r9
jle Done
iaddq $1, %rax # count++
one:
iaddq $1,%rdx
jne Done
mrmovq (%rdi), %r10 #
iaddq $8, %rdi # src++
rmmovq %r10, (%rsi) #
iaddq $8, %rsi # dst++
andq %r10, %r10 # val <= 0?
jle Done
iaddq $1, %rax # count++
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
CPE：7.49(满分)
上面的CPE：7.80就是前面的运行的太慢了
要优化这一部分才有降低CPE的可能，那就是从剩下的元素入手。
有一个方法就是让9个方法往下流，然后我们根据剩下的元素来跳转到从哪里开始流即可。然后我有了这个思路，刚好打开了百度查阅到了同思想。
像这样子流：
remain9:
mrmovq 64(%rdi),%r8
andq %r8,%r8
rmmovq %r8,64(%rsi)
remain8:
mrmovq 56(%rdi),%r8
jle remain82
iaddq $1,%rax
remain82:
rmmovq %r8,56(%rsi)
andq %r8,%r8
remain7:
mrmovq 48(%rdi),%r8
jle remain72
iaddq $1,%rax
remain72:
rmmovq %r8,48(%rsi)
andq %r8,%r8
remain6:
mrmovq 40(%rdi),%r8
jle remain62
iaddq $1,%rax
remain62:
rmmovq %r8,40(%rsi)
andq %r8,%r8
remain5:
mrmovq 32(%rdi),%r8
jle remain52
iaddq $1,%rax
remain52:
rmmovq %r8,32(%rsi)
andq %r8,%r8
remain4:
mrmovq 24(%rdi),%r8
jle remain42
iaddq $1,%rax
remain42:
rmmovq %r8,24(%rsi)
andq %r8,%r8
remain3:
mrmovq 16(%rdi),%r8
jle remain32
iaddq $1,%rax
remain32:
rmmovq %r8,16(%rsi)
andq %r8,%r8
remain2:
mrmovq 8(%rdi),%r8
jle remain22
iaddq $1,%rax
remain22:
rmmovq %r8,8(%rsi)
andq %r8,%r8
remain1:
mrmovq (%rdi),%r8
jle remain12
iaddq $1,%rax
remain12:
rmmovq %r8,(%rsi)
andq %r8,%r8
jle Done
iaddq $1,%rax
我们只要根据剩下多少个元素决定从哪里开始即可
这个要快，因为要判断，不可能按顺序判断(9 8 7…)这样1 2越少越慢。所以我们用查找树形结构来处理，像下面这样，。
代码如下
remain: #剩余的
iaddq $7,%rdx
jl left #len<3
jg right #len>3
je remain3 #len==3
left:
iaddq $2,%rdx #len==1
je remain1
iaddq $-1,%rdx #len==2
je remain2
ret #len==0
right:
iaddq $-3,%rdx #len<=6
jg rightRight
je remain6 #len==6
iaddq $1,%rdx
je remain5 #len==5
jmp remain4 #len==4
rightRight:
iaddq $-2,%rdx
jl remain7
je remain8
最后完整的代码
ncopy.ys:
#/* $begin ncopy-ys */
##################################################################
# ncopy.ys - Copy a src block of len words to dst.
# Return the number of positive words (>0) contained in src.
#
# Include your name and ID here.
#
# Describe how and why you modified the baseline code.
#
##################################################################
# Do not modify this portion
# Function prologue.
# %rdi = src, %rsi = dst, %rdx = len
ncopy:
##################################################################
# You can modify this portion
# Loop header
iaddq $-10,%rdx #判断是否有10个数(含)以上
jl remain
Loop:
mrmovq (%rdi), %r8
mrmovq 8(%rdi),%r9
rmmovq %r8, (%rsi)
rmmovq %r9,8(%rsi)
andq %r8, %r8
jle two
iaddq $1,%rax
two:
andq %r9,%r9
jle three
iaddq $1, %rax
three:
mrmovq 16(%rdi),%r8
mrmovq 24(%rdi),%r9
rmmovq %r8,16(%rsi)
rmmovq %r9,24(%rsi)
andq %r8,%r8
jle four
iaddq $1,%rax
four:
andq %r9,%r9
jle five
iaddq $1,%rax
five:
mrmovq 32(%rdi),%r8
mrmovq 40(%rdi),%r9
rmmovq %r8,32(%rsi)
rmmovq %r9,40(%rsi)
andq %r8,%r8
jle six
iaddq $1,%rax
six:
andq %r9,%r9
jle seven
iaddq $1,%rax
seven:
mrmovq 48(%rdi),%r8
mrmovq 56(%rdi),%r9
rmmovq %r8,48(%rsi)
rmmovq %r9,56(%rsi)
andq %r8,%r8
jle eight
iaddq $1,%rax
eight:
andq %r9,%r9
jle nine
iaddq $1,%rax
nine:
mrmovq 64(%rdi),%r8
mrmovq 72(%rdi),%r9
rmmovq %r8,64(%rsi)
rmmovq %r9,72(%rsi)
andq %r8,%r8
jle ten
iaddq $1,%rax
ten:
andq %r9,%r9
jle Npos
iaddq $1,%rax
Npos:
iaddq $80, %rdi #src+10
iaddq $80, %rsi #dst+10
iaddq $-10, %rdx #下一轮循环
jge Loop
remain: #剩余的
iaddq $7,%rdx
jl left #len<3
jg right #len>3
je remain3 #len==3
left:
iaddq $2,%rdx #len==1
je remain1
iaddq $-1,%rdx #len==2
je remain2
ret #len==0
right:
iaddq $-3,%rdx #len<=6
jg rightRight
je remain6 #len==6
iaddq $1,%rdx
je remain5 #len==5
jmp remain4 #len==4
rightRight:
iaddq $-2,%rdx
jl remain7
je remain8
remain9:
mrmovq 64(%rdi),%r8
andq %r8,%r8
rmmovq %r8,64(%rsi)
remain8:
mrmovq 56(%rdi),%r8
jle remain82
iaddq $1,%rax
remain82:
rmmovq %r8,56(%rsi)
andq %r8,%r8
remain7:
mrmovq 48(%rdi),%r8
jle remain72
iaddq $1,%rax
remain72:
rmmovq %r8,48(%rsi)
andq %r8,%r8
remain6:
mrmovq 40(%rdi),%r8
jle remain62
iaddq $1,%rax
remain62:
rmmovq %r8,40(%rsi)
andq %r8,%r8
remain5:
mrmovq 32(%rdi),%r8
jle remain52
iaddq $1,%rax
remain52:
rmmovq %r8,32(%rsi)
andq %r8,%r8
remain4:
mrmovq 24(%rdi),%r8
jle remain42
iaddq $1,%rax
remain42:
rmmovq %r8,24(%rsi)
andq %r8,%r8
remain3:
mrmovq 16(%rdi),%r8
jle remain32
iaddq $1,%rax
remain32:
rmmovq %r8,16(%rsi)
andq %r8,%r8
remain2:
mrmovq 8(%rdi),%r8
jle remain22
iaddq $1,%rax
remain22:
rmmovq %r8,8(%rsi)
andq %r8,%r8
remain1:
mrmovq (%rdi),%r8
jle remain12
iaddq $1,%rax
remain12:
rmmovq %r8,(%rsi)
andq %r8,%r8
jle Done
iaddq $1,%rax
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
ret
##################################################################
# Keep the following label at the end of your function
End:
#/* $end ncopy-ys */
测试：
linux> ./correctness.pl
CPE：7.49(60分。满分)
那个树(以3为根)不一定是最优的我还试了以5为根，CPE大概是7.51左右，差了一点点，我觉得可能是因为64的1 2 3 4的原因，总体来看要最短的。可能还有其他的方法能快那么一点点。
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
23
0- 0
已为社区贡献5条内容
所有评论(0)