---
tags: homework
---

# Assignment1: RISC-V Assembly and Instruction Pipeline
contributed by < [`shangrex`](https://github.com/shangrex) >

###### tags: `RISC-V`, `jserv`

## [Binary Number with Alternating Bits](https://leetcode.com/problems/binary-number-with-alternating-bits/)

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Constraints:
* 1 <= n <= $2^{31}$ - 1

Example:

Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101

Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.

Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.

Input: n = 10
Output: true
Explanation: The binary representation of 10 is: 1010.

Input: n = 3
Output: false

## Implementaion

You can find the source code [here](https://github.com/kaeteyaruyo/Computer-Architecture/tree/master/hw1). Feel free to fork and modify it.

### C code

I use take 10 for example, since it's binary representation is 1010. Obviously, it has matched the problem requirements. You can modify the input in line 16, and change the `input` value.

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>

bool hasAlternatingBits(int n){
    bool t = n & 1;
    while(n != 0){
        n = n >> 1;
        if(t == (n&1))return false;
        t = n & 1;
    }
    return true;
}

int main(void){
    int input = 10;
    bool rst = hasAlternatingBits(input);
    printf("%d\n", rst);
    return 0;
}

### Assembly code

.data
str1:     .string "The answer is True."
str2:     .string "The answer is False."

.text
    addi a1, x0, 10           # input n = 10
    andi t0, a1, 1            # t = n&1
loop1:
    beq a1, x0, return_t      # while( n != 0 )
    srai a1, a1, 1            #  n = n >> 1
    andi t1, a1, 1            #  t1 =  (n&1)
    beq t0, t1, return_f      #  if(t == (n&1)) return false
    andi t0, a1, 1            #  t = n & 1
    jal ra, loop1
return_f:
    la a0, str2               #  print False
    jal ra, finish
return_t:
    la a0, str1               #  print True
finish:
    li a7, 4
    ecall
    nop

## Analysis

We test our code using [Ripes](https://github.com/mortbopet/Ripes) simulator.

### Pseudo instruction

Ripes will transform our Psuedo instruction to equivalent one. We can check detail in [RISC-V Assembly Programmer’s Manual](https://github.com/riscv-non-isa/riscv-asm-manual/blob/master/riscv-asm.md#a-listing-of-standard-risc-v-pseudoinstructions).

	.file	"Binary_Number_with_Alternating_Bits.c"
	.text
	.section	.rodata
.LC0:
	.string	"The answer is True."
.LC1:
	.string	"The answer is False."
.LC2:
	.string	"The answer is %s\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movl	$10, -28(%rbp)
	movl	-28(%rbp), %eax
	andl	$1, %eax
	testl	%eax, %eax
	setne	%al
	movb	%al, -29(%rbp)
	leaq	.LC0(%rip), %rax
	movq	%rax, -16(%rbp)
	leaq	.LC1(%rip), %rax
	movq	%rax, -8(%rbp)
	movq	-16(%rbp), %rax
	movq	%rax, -24(%rbp)
	jmp	.L2
.L4:
	sarl	-28(%rbp)
	movzbl	-29(%rbp), %eax
	movl	-28(%rbp), %edx
	andl	$1, %edx
	cmpl	%edx, %eax
	jne	.L3
	movq	-8(%rbp), %rax
	movq	%rax, -24(%rbp)
.L3:
	movl	-28(%rbp), %eax
	andl	$1, %eax
	testl	%eax, %eax
	setne	%al
	movb	%al, -29(%rbp)
.L2:
	cmpl	$0, -28(%rbp)
	jne	.L4
	movq	-24(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC2(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	 1f - 0f
	.long	 4f - 1f
	.long	 5
0:
	.string	 "GNU"
1:
	.align 8
	.long	 0xc0000002
	.long	 3f - 2f
2:
	.long	 0x3
3:
	.align 8
4:

###

### 5-stage pipelined processor
Ripes have provided 5-stage piplined processor. It contains the following stages.

1. `Instruction fetch (IF)`: Controller fetch the instruction from instruction memory.
2. `Instruction decode and register fetch (ID)`: Controller decode the instruction and fetch the rigister's value.
3. `Execute (EX)`: Controller carry out the arithmetic operation.
4. `MEM`: load/store value to/from memory if needed.
5. `Register write back (WB)`: write the memory to rigister.


The bus between tow stage can store value, and can foward the value to different bus.

### Data flow
Controller will store the value after `WB` stage.
To prevent data hazard, Ripes provides forwarding. In this example, ALU can get data From `WB` stage.

### Control Hazard

when encouter `jal` and `beq` instructions, after `EX` stage, the controller flush two instruction before, since controller should fetch new instrucion from different places.

### Structure Hazard


When the resource is busy, the controller need to wait.
`ecall` instruction will occupy two stage after execution.

## Reference

* [RISC-V Instruction Set Manual](https://riscv.org//wp-content/uploads/2017/05/riscv-spec-v2.2.pdf)
* [RISC-V Assembly Programmer's Manual](https://github.com/riscv-non-isa/riscv-asm-manual/blob/master/riscv-asm.md)
* [RISC-V Green Card](https://www.cl.cam.ac.uk/teaching/1617/ECAD+Arch/files/docs/RISCVGreenCardv8-20151013.pdf)
* [Environmental Calls](https://github.com/mortbopet/Ripes/wiki/Environment-calls)
* [Homework template Reference](https://hackmd.io/@kaeteyaruyo/risc-v-hw1)