[CS311] Computer Organization, Fall 2024, Prof.
Soontae Kim
Homework #1
TA in charge: Sihyun Kim
E-mail: [Link]@[Link]
I. Goal of this assignment
Understanding how computers work at a low level, bridging the gap between high-level
programming languages and the hardware.
Implementing procedures with recursive calls in MIPS ISA.
II. What to implement
You need to implement a program that performs a Depth-First Search (DFS) and
Breadth-First Search (BFS) on a graph.
The graph contains vertices numbered from 1 to N.
There cannot be more than one edge between any two vertices
Each edge can be traversed in both directions.
If multiple vertices are available to visit, prioritize the vertex with the smaller
number.
Graph traversal ends when no more vertices can be visited.
Here is the input format you should follow:
The number of vertices N (1 ≤ N ≤ 300) is given in the first line.
The number of edges M (1 ≤ M ≤ 10,000) is given in the second line.
The start vertex number V (1 ≤ V ≤ N) is given in the third line.
The two vertices of the k-th edge (1 ≤ k ≤ M) are given in the (2k + 2)-th and
(2k + 3)-th lines, respectively.
Here is the output format you should follow:
The first line displays the graph traversal results of the DFS.
The second line displays the graph traversal results of the BFS.
1
[CS311] Computer Organization, Fall 2024, Prof. Soontae Kim
Example of input and output:
Input Output
6 214356
10 214563
2
4
Graph
2
3
4
4
6
2
6
3
5
4
5
1
4
1
6
2
5
1
2
III. Constraints
The number of vertices N: 1 ≤ N ≤ 300
The number of edges M: 1 ≤ M ≤ 10,000
The start vertex number V: 1 ≤ V ≤ N
We will use the SPIM simulator to check if your assembly program runs correctly.
Your program must be runnable on the simulator. Otherwise, you will not get any points
except for the report. Please check your program before submission.
2
[CS311] Computer Organization, Fall 2024, Prof. Soontae Kim
IV. Submission and grading
Your submission should include: (Total 100 pts)
A. Source code file of your assembly program [hw1_StudentID.s]
The source code should contain:
i. Implementation of the given algorithm in assembly language (20 pts)
ii. Comments explaining the details of your implementation (10 pts)
iii. Code that correctly receives integer input and prints graph traversal results to
the simulator console
We will check whether the correct results are produced for test cases. (40 pts)
B. Brief report [hw1_StudentID.pdf]
The content of the report should describe:
i. Stack allocation layout for each procedure (10 pts)
Describe the content of the stack space for each procedure; show the position
of each data in the stack space using offset to the stack pointer of each procedure.
ii. Brief explanation of your implementation (20 pts)
What you have considered for your implementation, implementation issues, etc.
There is no specific format for the report. You should submit your code and report
in either English or Korean.
Upload these two files on KLMS.
V. Due date
23:59, Oct. 8th (Tue.)
Late submission due date: 23:59, Oct. 9th (Wed.)
For late submissions, there will be a 50% penalty on your total score.
You cannot submit after the late submission due date.
VI. Cheating
If there are any cheatings in your submission, you will get 0 points.
We will do a similarity check on the submitted code files to catch plagiarism between
students.
Followings will be regarded as cheating:
A. Copying other students’ simulation results or report
3
[CS311] Computer Organization, Fall 2024, Prof. Soontae Kim
B. Modifying other students’ results and using them as if they were your own
C. Using other sources without any references
D. All other sorts of inappropriate behaviors.
VII. Tips & Notes
Since SPIM does not simulate a delay slot in the default configuration, you can ignore
it for this assignment.
The simulator may not be able to load your code if it contains non-English characters.
You can use pseudo-instructions supported in SPIM for your convenience.
You would need to review how to implement procedure calls with MIPS assembly.
It would be helpful to first implement the assignment in C language.
If you have little experience with assembly programming, this assignment could take
much longer than expected. If you think this is your case, we recommend you begin
this assignment as early as possible.
If you have any questions, please use the KLMS Q&A board.
You can use SPIM(terminal version) to test your code. You can download it from
[Link]
Directory tree:
├─ bin
├─ CPU
│ └─ exceptions.s
├─ Documentation
├─ Setup
├─ spim
│ ├─ Makefile
│ ├─ spim
│ └─ pathfinder.s
└ Tests
Testing command:
make spim
./spim -ef ../CPU/exceptions.s -file pathfinder.s