Skip to content

Instantly share code, notes, and snippets.

@hakatashi hakatashi/report.md
Created Jul 4, 2019

Embed
What would you like to do?

「コンピュータアーキテクチャ」レポート課題

  • 学生証番号: 03-170512
  • 氏名: 高橋光輝

課題1

この授業で設計したプロセッサのアセンブラを Perl で実装せよ

Perlで実装せよとあるが、講義において各々好きなプログラミング言語を用いてよいとの指示を受けたため、本課題では自らが得意とするRust言語を用いて実装を行った。

課題2

1で作ったアセンブラで、自分で作った短いプログラムをアセンブルし、その結果として得られる機械語プログラムを示せ。1+1=2などでよい。

以下のとおり1+1の演算結果をr3レジスタに代入するプログラムを作成した。

addi r1, r0, 1
addi r2, r0, 1
add r3, r1, r2

これを上に実装したアセンブラを用いてアセンブルしたところ、以下の出力が得られた。

000001_00000_00001_0000000000000001
000001_00000_00010_0000000000000001
000000_00001_00010_00011_00000000000

課題3

このプロセッサに、次に示す2つの動作を行うI型命令 bgt0_sub (branch on greater than zero with subtract) を追加したい。これは、ループの実現に便利な複合命令である。

rt <- rt - rs ;
if (rt > 0) PC <- PC + dpl else PC <- PC + 1 ;

課題3.1

命令の仕様(名称、アセンブリ言語による表現、動作、書式、コード)を定め、これを記せ。

以下の通り定めた。

  • 名称 (ニーモニック): bgt0_sub

  • アセンブリ言語による表現: bgt0_sub rt, rs, dpl

  • 書式

    ビット数 内容
    bgt0_sub 6 命令 (機械語による表現は36)
    rt 5 代入先のレジスタ
    rs 5 演算元のレジスタ
    dpl 16 ジャンプ先の相対アドレス
  • コード

    rt <- rt - rs ;
    if (rt > 0) PC <- PC + dpl else PC <- PC + 1 ;
    

課題3.2

この命令を機械語に翻訳できるようにアセンブラを改良せよ。改良したアセンブラのソースを示せ。

上の仕様を満たすようアセンブラに改良を加えた。改良後のアセンブラの全文は以下の通りである。

なお、変更部分を蛍光マーカーで示した。

use std::io::BufReader;
use std::io::BufRead;
use std::error::Error;
use std::env;
use std::fs::File;
use std::collections::HashMap;

#[derive(Debug)]
struct Instruction {
    mnemonic: String,
    args: Vec<String>,
}

impl Instruction {
    fn dump_r3(&self, inst_number: u8, inst_indicator: u16) {
        let mut components = vec![];

        components.push(format!("{:06b}", inst_number));
        let registers = self.args.iter().map(|arg|
            arg.trim_start_matches("r").parse().unwrap()
        ).collect::<Vec<u8>>();

        match registers.len() {
            1 => {
                components.push(format!("{:05b}", registers[0]));
                components.push(format!("{:05b}", 0));
                components.push(format!("{:05b}", 0));
            },
            2 => {
                components.push(format!("{:05b}", registers[1]));
                components.push(format!("{:05b}", 0));
                components.push(format!("{:05b}", registers[0]));
            },
            3 => {
                components.push(format!("{:05b}", registers[1]));
                components.push(format!("{:05b}", registers[2]));
                components.push(format!("{:05b}", registers[0]));
            },
            _ => panic!("Invalid argument length"),
        }

        components.push(format!("{:011b}", inst_indicator));

        println!("{}", components.join("_"));
    }
    fn dump_r2i(&self, inst_number: u8) {
        let mut components = vec![];

        components.push(format!("{:06b}", inst_number));

        let (imm, args) = self.args.split_last().unwrap();
        let registers = args.to_vec().iter().map(|arg|
            arg.trim_start_matches("r").parse().unwrap()
        ).collect::<Vec<u8>>();

        match registers.len() {
            1 => {
                components.push(format!("{:05b}", 0));
                components.push(format!("{:05b}", registers[0]));
            },
            2 => {
                components.push(format!("{:05b}", registers[1]));
                components.push(format!("{:05b}", registers[0]));
            },
            _ => panic!("Invalid argument length"),
        }

        components.push(format!("{:016b}", imm.parse::<u16>().unwrap()));

        println!("{}", components.join("_"));
    }
    fn dump_r2b(&self, inst_number: u8, labels: &HashMap<String, usize>, index: usize) {
        let mut components = vec![];

        components.push(format!("{:06b}", inst_number));

        let (_label, args) = self.args.split_last().unwrap();
        let registers = args.to_vec().iter().map(|arg|
            arg.trim_start_matches("r").parse().unwrap()
        ).collect::<Vec<u8>>();

        components.push(format!("{:05b}", registers[0]));
        components.push(format!("{:05b}", registers[1]));
        let address: i16 = *labels.get(self.args.last().unwrap()).unwrap() as i16;
        components.push(format!("{:016b}", address - index as i16 - 1));

        println!("{}", components.join("_"));
    }
    fn dump_addr(&self, inst_number: u8, labels: &HashMap<String, usize>) {
        let mut components = vec![];

        components.push(format!("{:06b}", inst_number));

        let address: i32 = *labels.get(self.args.last().unwrap()).unwrap() as i32;
        components.push(format!("{:026b}", address));

        println!("{}", components.join("_"));
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let file_path = match env::args().nth(1) {
        Some(path) => path,
        None => panic!("Please specify input file as args"),
    };

    let file = File::open(file_path)?;
    let file_reader = BufReader::new(&file);

    let mut labels = HashMap::new();
    let mut instructions = Vec::new();

    for raw_line in file_reader.lines() {
        let line = raw_line?.trim().to_string();
        if line.ends_with(":") {
            let label_name = line.trim_end_matches(":").trim().to_string();
            labels.insert(label_name, instructions.len());
        } else {
            let instruction = line.split_whitespace().map(|w|
                w.trim_end_matches(",").to_string()
            ).collect::<Vec<String>>();

            if instruction.len() == 0 {
                continue;
            } else {
                instructions.push(Instruction {
                    mnemonic: instruction[0].clone(),
                    args: instruction[1..].to_vec(),
                });
            }
        }
    }

    for (index, instruction) in instructions.iter().enumerate() {
        match instruction.mnemonic.as_str() {
            "add" => instruction.dump_r3(0, 0),
            "addi" => instruction.dump_r2i(1),
            "sub" => instruction.dump_r3(0, 2),
            "lui" => instruction.dump_r2i(3),
            "and" => instruction.dump_r3(0, 8),
            "andi" => instruction.dump_r2i(4),
            "or" => instruction.dump_r3(0, 9),
            "ori" => instruction.dump_r2i(5),
            "xor" => instruction.dump_r3(0, 10),
            "xori" => instruction.dump_r2i(6),
            "nor" => instruction.dump_r3(0, 11),
            "sll" => instruction.dump_r3(0, 16),
            "srl" => instruction.dump_r3(0, 17),
            "sra" => instruction.dump_r3(0, 18),
            "lw" => instruction.dump_r2i(16),
            "lh" => instruction.dump_r2i(18),
            "lb" => instruction.dump_r2i(20),
            "sw" => instruction.dump_r2i(24),
            "sh" => instruction.dump_r2i(26),
            "sb" => instruction.dump_r2i(28),
            "beq" => instruction.dump_r2b(32, &labels, index),
            "bne" => instruction.dump_r2b(33, &labels, index),
            "blt" => instruction.dump_r2b(34, &labels, index),
            "ble" => instruction.dump_r2b(35, &labels, index),
            "bgt0_sub" => instruction.dump_r2b(36, &labels, index),
            "j" => instruction.dump_addr(40, &labels),
            "jal" => instruction.dump_addr(41, &labels),
            "jr" => instruction.dump_r3(42, 0),
            _ => panic!("Illegal Instruction")
        }
    }

    Ok(())
}

課題3.3

この命令を処理できるようにプロセッサの設計を変更せよ。答えは、Verilog HDL で記述せよ。

上の仕様を満たすようアセンブラに改良を加えた。以下に unified diff 形式で変更部分のみを示す。

--- computer.v	Fri Jun 28 13:20:46 2019
+++ computer-1.v	Fri Jul 05 04:04:08 2019
@@ -40,11 +39,14 @@
 			6'd4:	opr_gen = 5'd8;
 			6'd5:	opr_gen = 5'd9;
 			6'd6:	opr_gen = 5'd10;
+			6'd36:	opr_gen = 5'd2; // subtraction
 			default: opr_gen = 5'h1f;
 		endcase
 	endfunction
@@ -74,7 +76,7 @@
 		input	[5:0]	op;
 		input	[31:0]	alu_result, dpl_imm, dm_r_data, pc;
 		case (op)
-			6'd0, 6'd1, 6'd4, 6'd5, 6'd6:	calc = alu_result;
+			6'd0, 6'd1, 6'd4, 6'd5, 6'd6, 6'd36:	calc = alu_result;
 			6'd3:	calc = dpl_imm << 16;
 			6'd16:	calc = dm_r_data;
 			6'd18:	calc = {{16{dm_r_data[15]}}, dm_r_data[15:0]};
@@ -90,8 +92,9 @@
 			6'd33:	npc = (reg1 != reg2) ? branch : nonbranch;
 			6'd34:	npc = (reg1 < reg2)  ? branch : nonbranch;
 			6'd35:	npc = (reg1 <= reg2) ? branch : nonbranch;
+			6'd36:	npc = (reg1 > reg2)  ? branch : nonbranch;
 			6'd40, 6'd41:	npc = addr;
 			6'd42:	npc = reg1;
 			default:	npc = nonbranch;
@@ -100,10 +103,11 @@

 	function	[4:0]	wreg;
 		input	[5:0]	op;
-		input	[4:0]	rt, rd;
+		input	[4:0]	rt, rd, rs;
 		case (op)
 			6'd0:	wreg = rd;
 			6'd1, 6'd3, 6'd4, 6'd5, 6'd6, 6'd16, 6'd18, 6'd20:	wreg = rt;
+			6'd36:	wreg = rs;
 			6'd41:	wreg = 5'd31;
 			default:	wreg = 5'd0;
 		endcase
@@ -123,17 +127,18 @@
 	assign shift = ins[10:6];
 	assign operation = ins[4:0];
 	assign dpl_imm = {{16{ins[15]}}, ins[15:0]};
-	assign operand2 = (op == 6'd0) ? reg2 : dpl_imm;
+	assign operand2 = (op == 6'd0 || op == 6'd36) ? reg2 : dpl_imm;
 	assign alu_result = alu(opr_gen(op, operation), shift, reg1, operand2);

 	assign mem_address = (reg1 + dpl_imm) >>> 2;
@@ -133,7 +135,7 @@
 	data_mem data_mem_body2(mem_address[7:0], clk, reg2[23:16], wren[2], dm_r_data[23:16]);
 	data_mem data_mem_body3(mem_address[7:0], clk, reg2[31:24], wren[3], dm_r_data[31:24]);

-	assign wra = wreg(op, ins[20:16], ins[15:11]);
+	assign wra = wreg(op, ins[20:16], ins[15:11], ins[25:21]);
 	assign result = calc(op, alu_result, dpl_imm, dm_r_data, pc);

 	assign addr = ins[25:0];

課題3.4

bgt0_sub 命令を使わずに、1~N までの階和を求めるプログラムをアセンブリ言語で書き、機械語に翻訳せよ。

以下の通り、1からr1レジスタの値までの階和を求め、r2レジスタに代入するプログラムを作成した。

addi r1, r0, 12
addi r2, r0, 0
addi r3, r0, 0
loop:
addi r3, r3, 1
add r2, r2, r3
bne r1, r3, loop

これをアセンブルしたところ、以下のような機械語になった。

000001_00000_00001_0000000000001100
000001_00000_00010_0000000000000000
000001_00000_00011_0000000000000000
000001_00010_00010_0000000000000001
000000_00011_00010_00011_00000000000
100001_00001_00010_1111111111111101

課題3.5

bgt0_sub 命令を使って、3.4 と同じ階和を求めるプログラムをアセンブリ言語で書き、機械語に翻訳せよ。

課題3.4と同様のプログラムを以下の通り作成した。

addi r1, r0, 12
addi r2, r0, 0
add r3, r0, r1
addi r4, r0, 1
loop:
add r2, r2, r3
bgt0_sub r1, r4, loop

これをアセンブルしたところ、以下のような機械語になった。

000001_00000_00001_0000000000001100
000001_00000_00010_0000000000000000
000000_00000_00001_00011_00000000000
000001_00000_00100_0000000000000001
000000_00010_00011_00010_00000000000
100100_00001_00100_1111111111111110

課題3.6

新しい命令を導入することによる性能向上(クロック数)をNの関数として表現せよ。

改良前、改良後のそれぞれプログラムのloopラベルで示されるループは、求めるべき階和の項数、すなわちN回実行される。

また、改良前のループには3命令存在したのに対し、改良後のループには2命令が存在する。すなわち1ループあたりの1命令が削減される。

以上の2点を勘案し、N回のループで1命令が削減されることから、全体でNクロックが削減される。また、改良のオーダーはO(N)となる。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.