Homework

1100012749

---

Homework 10

6.23

磁盘容量 ~ xr(1 - x)
--> x = 0.5

6.25

Taccess= Tavgseek + Tavgrotation + Tavgtransfer
Tavgrotation = 1/2 x(60 secs/15000 RPM) x1000 ms/sec = 2 ms.
定位时间 = 3 + 2 = 5 ms
A. 5 + 4000 / 1000 * 4 = 21ms
B. 5 * 4000 = 20000ms

6.27

Cache	C	B	E	S	t	s	b
1.	2048			256
2.		4	4
3.					25	6
4.		32					5

6.29

A. 无
B. 0x18F0, 0x18F1, 0x18fF2, 0x18F3, 0xB0, 0xB1, 0xB2, 0xB3
C. 0xE34, 0xE35, 0xE36, 0xE37
D. 0x1BDC, 0x1BDD, 0x1BDE, 0x1BDF

6.46

void transpose(int *dst,int *src,int dim)
{
    int i, j, ii, jj, i_;
    int Dim = dim*4;
    for(i = 0, ii = 0; i < dim-3; i += 4, ii += Dim)
    {
        for(j = 0, jj = 0; j < dim-3; j += 4, jj += Dim)
        {
            dst[jj + i] = src[ii + j];
            dst[jj + i+1] = src[ii+dim + j];
            dst[jj + i+2] = src[ii+dim*2 + j];
            dst[jj + i+3] = src[ii+dim*3 + j];
            dst[jj+dim + i] = src[ii + j+1];
            dst[jj+dim + i+1] = src[ii+dim + j+1];
            dst[jj+dim + i+2] = src[ii+dim*2 + j+1];
            dst[jj+dim + i+3] = src[ii+dim*3 + j+1];
            dst[jj+dim*2 + i] = src[ii + j+2];
            dst[jj+dim*2 + i+1] = src[ii+dim + j+2];
            dst[jj+dim*2 + i+2] = src[ii+dim*2 + j+2];
            dst[jj+dim*2 + i+3] = src[ii+dim*3 + j+2];
            dst[jj+dim*3 + i] = src[ii + j+3];
            dst[jj+dim*3 + i+1] = src[ii+dim + j+3];
            dst[jj+dim*3 + i+2] = src[ii+dim*2 + j+3];
            dst[jj+dim*3 + i+3] = src[ii+dim*3 + j+3];
        }
    }
    i_ = i;//j
    for(i = 0; i < dim; i++)
        for(j = i_; j < dim; j++)
            dst[j*dim + i] = src[i*dim + j];
    for(i = i_;i < dim;i++)
        for(j = 0;j < i_;j++)
            dst[j*dim + i] = src[i*dim + j];
} 

---

Homework 7

4.43

A. 当REG是%esp时，这段代码将会把REG-4压入栈中。
B.

movl REG,-4(%esp)
subl $4,%esp

---

4.45

A.

void bubble_a(int *data,int count) {
    int i, last;
    for (last = count-1; last > 0; last--) {
        for (i = 0; i < last; i++)
            if (*(data+i+1) < *(data+i)) {
                int t = *(data+i+1);
                *(data+i+1) = *(data+i);
                *(data+i) = t;
            }
    }
}
int main(){
    int data[3] = {3,2,1};
    bubble_a(data,3);
    return 0;
}

B.

    .pos 0
init:
    irmovl Stack, %esp  # Set up Stack pointer
    irmovl Stack, %ebp  # Set up base pointer
    call Main            # Execute main program
    halt
# Array of 4 elements
    .align 4    
array:
    .long 5
    .long 2
    .long 0
    .long 1
Main:
    pushl %ebp 
    rrmovl %esp,%ebp
    irmovl $4,%eax 
    pushl %eax      # Push count=4
    irmovl array,%edx
    pushl %edx          # Push array
    call bubble_a       # bubble_a(array, 4)
    rrmovl %ebp,%esp
    popl %ebp
    ret 
bubble_a:
    pushl %ebp
    rrmovl %esp, %ebp
    mrmovl 12(%ebp), %esi  
    mrmovl 8(%ebp), %edx   # edx = data
    irmovl  $-1,%eax
    addl %eax, %esi # esi = last == count-1
    jle L1
#innerLoop
L10:
    xorl %eax, %eax # i = 0
L7: 
    pushl %esi
    rrmovl %eax, %esi
    addl %esi, %esi
    addl %esi, %esi
    addl %edx, %esi
    mrmovl 4(%esi), %ecx #movl  4(%edx,%eax,4), %ecx
    mrmovl (%esi), %ebx #movl   (%edx,%eax,4), %ebx
    subl %ebx, %ecx
    jge L3
    addl %ebx, %ecx
    rmmovl %ebx, 4(%esi)  
    rmmovl %ecx, (%esi)
L3:
    popl %esi
    irmovl $1,%ecx
    addl %ecx, %eax
    rrmovl %eax, %ecx
    subl %esi, %ecx
    jl L7
#innerLoop
    irmovl $-1, %ecx
    addl %ecx, %esi
    jne L10
L1:
    rrmovl %ebp,%esp
    popl %ebp
    ret
    .pos 0x200 
Stack:

4.46

#innerLoop
L10:
    xorl %eax, %eax # i = 0
L7: 
    pushl %esi
    rrmovl %eax, %esi
    addl %esi, %esi
    addl %esi, %esi
    addl %edx, %esi
    mrmovl 4(%esi), %ecx #movl  4(%edx,%eax,4), %ecx
    mrmovl (%esi), %ebx #movl   (%edx,%eax,4), %ebx
    pushl %esi
    rrmovl %ecx, %esi   
    subl %ebx, %esi
    rrmovl %ecx, %esi
    cmovl %ebx, %ecx
    cmovl %esi, %ebx
    popl %esi
    rmmovl %ecx, 4(%esi)
    rmmovl %ebx, (%esi)
L3:
    popl %esi
    irmovl $1,%ecx
    addl %ecx, %eax
    rrmovl %eax, %ecx
    subl %esi, %ecx
    jl L7
#innerLoop

4.49

# Stage iaddl V, rB
#
# Fetch:
#   icode:ifun <- M1[PC]
#   rA:rB <- M1[PC+1]
#   valC <- M4[PC+2]
#   valP <- PC+6
#
# Decode:
#   valB <- R[rB]
#
# Execute:
#   valE <- valB+valC
#   Set CC
#
# Memory 
#
# Write back:
#    R[rB] <- valE
#
# PC update:
#   PC <- valP
#
#/* $begin seq-all-hcl */
####################################################################
#  HCL Description of Control for Single Cycle Y86 Processor SEQ   #
#  Copyright (C) Randal E. Bryant, David R. O'Hallaron, 2010       #
####################################################################
## Your task is to implement the iaddl and leave instructions
## The file contains a declaration of the icodes
## for iaddl (IIADDL) and leave (ILEAVE).
## 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 'int 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 Instruction Codes #############
intsig INOP     'I_NOP'
intsig IHALT    'I_HALT'
intsig IRRMOVL  'I_RRMOVL'
intsig IIRMOVL  'I_IRMOVL'
intsig IRMMOVL  'I_RMMOVL'
intsig IMRMOVL  'I_MRMOVL'
intsig IOPL 'I_ALU'
intsig IJXX 'I_JMP'
intsig ICALL    'I_CALL'
intsig IRET 'I_RET'
intsig IPUSHL   'I_PUSHL'
intsig IPOPL    'I_POPL'
# Instruction code for iaddl instruction
intsig IIADDL   'I_IADDL'
# Instruction code for leave instruction
intsig ILEAVE   'I_LEAVE'
##### Symbolic represenations of Y86 function codes                  #####
intsig FNONE    'F_NONE'        # Default function code
##### Symbolic representation of Y86 Registers referenced explicitly #####
intsig RESP     'REG_ESP'       # Stack Pointer
intsig REBP     'REG_EBP'       # Frame Pointer
intsig RNONE    'REG_NONE'      # Special value indicating "no register"
##### ALU Functions referenced explicitly                            #####
intsig ALUADD   'A_ADD'     # ALU should add its arguments
##### Possible instruction status values                             #####
intsig SAOK 'STAT_AOK'      # Normal execution
intsig SADR 'STAT_ADR'  # Invalid memory address
intsig SINS 'STAT_INS'  # Invalid instruction
intsig SHLT 'STAT_HLT'  # Halt instruction encountered
##### Signals that can be referenced by control logic ####################
##### Fetch stage inputs        #####
intsig pc 'pc'              # Program counter
##### Fetch stage computations      #####
intsig imem_icode 'imem_icode'      # icode field from instruction memory
intsig imem_ifun  'imem_ifun'       # ifun field from instruction memory
intsig icode      'icode'       # Instruction control code
intsig ifun   'ifun'        # Instruction function
intsig rA     'ra'          # rA field from instruction
intsig rB     'rb'          # rB field from instruction
intsig valC   'valc'        # Constant from instruction
intsig 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     #####
intsig valA 'vala'          # Value from register A port
intsig valB 'valb'          # Value from register B port
##### Execute stage computations    #####
intsig valE 'vale'          # Value computed by ALU
boolsig Cnd 'cond'          # Branch test
##### Memory stage computations     #####
intsig valM 'valm'          # Value read from memory
boolsig dmem_error 'dmem_error'     # Error signal from data memory
####################################################################
#    Control Signal Definitions.                                   #
####################################################################
################ Fetch Stage     ###################################
# Determine instruction code
int icode = [
    imem_error: INOP;
    1: imem_icode;      # Default: get from instruction memory
];
# Determine instruction function
int ifun = [
    imem_error: FNONE;
    1: imem_ifun;       # Default: get from instruction memory
];
bool instr_valid = icode in 
    { INOP, IHALT, IRRMOVL, IIRMOVL, IRMMOVL, IMRMOVL,
           IOPL, IJXX, ICALL, IRET, IPUSHL, IPOPL, IIADDL, ILEAVE };
# Does fetched instruction require a regid byte?
bool need_regids =
    icode in { IRRMOVL, IOPL, IPUSHL, IPOPL, 
             IIRMOVL, IRMMOVL, IMRMOVL, IIADDL };
# Does fetched instruction require a constant word?
bool need_valC =
    icode in { IIRMOVL, IRMMOVL, IMRMOVL, IJXX, ICALL, IIADDL };
################ Decode Stage    ###################################
## What register should be used as the A source?
int srcA = [
    icode in { IRRMOVL, IRMMOVL, IOPL, IPUSHL  } : rA;
    icode in { IPOPL, IRET } : RESP;
    icode in { ILEAVE } : REBP;
    1 : RNONE; # Don't need register
];
## What register should be used as the B source?
int srcB = [
    icode in { IOPL, IRMMOVL, IMRMOVL, IIADDL  } : rB;
    icode in { IPUSHL, IPOPL, ICALL, IRET } : RESP;
    icode in { ILEAVE } : REBP;
    1 : RNONE;  # Don't need register
];
## What register should be used as the E destination?
int dstE = [
    icode in { IRRMOVL } && Cnd : rB;
    icode in { IIRMOVL, IOPL, IIADDL} : rB;
    icode in { IPUSHL, IPOPL, ICALL, IRET, ILEAVE } : RESP;
    1 : RNONE;  # Don't write any register
];
## What register should be used as the M destination?
int dstM = [
    icode in { IMRMOVL, IPOPL } : rA;
    icode in { ILEAVE } : REBP;
    1 : RNONE;  # Don't write any register
];
################ Execute Stage   ###################################
## Select input A to ALU
int aluA = [
    icode in { IRRMOVL, IOPL } : valA;
    icode in { IIRMOVL, IRMMOVL, IMRMOVL, IIADDL } : valC;
    icode in { ICALL, IPUSHL } : -4;
    icode in { IRET, IPOPL, ILEAVE } : 4;
    # Other instructions don't need ALU
];
## Select input B to ALU
int aluB = [
    icode in { IRMMOVL, IMRMOVL, IOPL, ICALL, 
              IPUSHL, IRET, IPOPL, IIADDL, ILEAVE } : valB;
    icode in { IRRMOVL, IIRMOVL } : 0;
    # Other instructions don't need ALU
];
## Set the ALU function
int alufun = [
    icode == IOPL : ifun;
    1 : ALUADD;
];
## Should the condition codes be updated?
bool set_cc = icode in { IOPL, IIADDL };
################ Memory Stage    ###################################
## Set read control signal
bool mem_read = icode in { IMRMOVL, IPOPL, IRET, ILEAVE };
## Set write control signal
bool mem_write = icode in { IRMMOVL, IPUSHL, ICALL };
## Select memory address
int mem_addr = [
    icode in { IRMMOVL, IPUSHL, ICALL, IMRMOVL } : valE;
    icode in { IPOPL, IRET, ILEAVE } : valA;
    # Other instructions don't need address
];
## Select memory input data
int mem_data = [
    # Value from register
    icode in { IRMMOVL, IPUSHL } : valA;
    # Return PC
    icode == ICALL : valP;
    # Default: Don't write anything
];
## Determine instruction status
int Stat = [
    imem_error || dmem_error : SADR;
    !instr_valid: SINS;
    icode == IHALT : SHLT;
    1 : SAOK;
];
################ Program Counter Update ############################
## What address should instruction be fetched at
int 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 */