In this project, you are required to convert the C++ codes to MIPS instructions in assembly language and finish the process of compiling, running, debugging the assembly codes, and passing the test using the MARS simulator. In this project, you are expected to understand how to convert the algorithms in the high-level language to assembly language, how the hardware structure in the MIPS processor implements the instructions, and how to program and debug the assembly code.

There are two parts for this project: the basic exercise and the applied practice.

In the basic exercise part, you will practice the common operations in MIPS, and learn how to program the assembly code. In the applied practice part, you should accomplish the assembly code with the given C codes of three different algorithms.

Upload the compressed files to WEB learning before 2023/04/30 23:59. The name should be “your ID_your name.xxx”. “xxx” is the compression format. The zip format is recommended, and other common compression formats, such as rar and 7z, can be also used. The unzipped files should include:

A “report.pdf”. The contents are required to be brief and divided into two parts:

A “exp1” folder including “exp1_1.asm”, “exp1_2.asm”, “exp1_3.asm” and

“exp1_4.asm” (four files in total);

A “exp2” folder including “sssp_bellman.asm”, “sssp_dijkstra.asm” and

“sssp_dfs.asm” (three files in total).

The appeared letters of all files (including the filename extension) above should be lowercase.

Note: Partial scores of this project are given by the script automatically. If the script fails to find the codes for evaluation due to the incorrect format, corresponding scores will be deducted.

3.Notes

1.For all assembly codes in MIPS for this project, corresponding C/C++ codes have been provided (in the folders exp1 and exp2). The assembly codes should correspond to the provided C/C++ codes. No other C/C++ codes can be used.

2.The project should be finished independently, and no cheating is tolerated,including but not limited to copying the codes of any other students, copying the open-source codes in networks, copying the codes generated by ChatGPT, etc. If we find you cheating, you will get the score 0 for this project, and be punished strictly.

Part 1: Basic Exercise

Exercise 1-1: System Call (exp1_1.asm)

Learn to use the system call (syscall) in the MARS simulator, including file read/write, command read/write (standard input and output), memory allocation, etc.

The basic usage of the system call includes:

For more detailed usage, please refer to the contents in Help of the MARS simulator. The codes in exp1_1.cpp mainly include:

Input file and output file format: The input file name is “a.in”, and the output file name is “a.out”. Both these two files are in binary format. In the folder “exp1”, there is a file “a.in” including two integers (1 and 10) as the test example.

Hint: for the instructions for opening files in MIPS, = 0 for the read-only mode; = 1 for the write-only mode; = 2 for the write-read mode.

Exercise 1-2: Loop and Branch (exp1_2.asm)

Achieve the functions in exp1_2.cpp using the assembly language in MIPS and upload the assembly codes. It is good to add the annotations in the codes for better readability. The codes in exp1_2.cpp mainly include:

Output format requirement: The final result should be stored in register $v0 at the end of the program. The scores will be deducted if you fail to output the final results as required.

Exercise 1-3: Array and Pointer (exp1_3.asm)

Achieve the functions in exp1_3.cpp using the assembly language in MIPS and upload the assembly codes. It is good to add the annotations in the codes for better readability. The codes in exp1_3.cpp mainly include:

Hint: The system call 9 in MIPS has similar functionality to the new in C language. This instruction can allocate the memory space for n integers, and the input parameters are n*4. The return value is the first address of this memory space.

Exercise 1-4: Function Call (exp1_4.asm)

The C++ codes for the Fibonacci sequence are provided in exp1 4.cpp. Covert them into the assembly codes in MIPS.

Part 1: Applied Practice

Definition

On a weighted graph, a path length is defined as the sum of the weight on this path. Single-Source Shortest Path (SSSP) is to find the shortest path (the smallest sum of the weight) from a given source vertex to another destination vertex. The problem required to be solved in this project is as follows:

Given the adjacent matrix of a directed graph with n vertices (3 ≤ ≤ 32) = {}, , = 0,1, ⋯ , − 1, where and are vertices satisfies the following relationship: