Tech Stack & Toolchain

• Languages: Verilog, MIPS Assembly, Makefile
• Simulation: MARS (MIPS), Icarus Verilog
• Debugging: GTKWave

System Requirements

• OS: Linux (Developed & Tested on Fedora 43)
• Runtime: OpenJDK 25 (Required for MARS Simulator)
• Shell: Bash / Zsh

MIPS SIMULATOR - MARS

MARS (MIPS Assembler and Runtime Simulator) is an IDE for programming in MIPS assembly, intended for educational use with Patterson and Hennessy's Computer Organization and Design. Official Website

To open the simulator using the provided .jar file, ensure you have Java installed and run:

java -jar Mars4_5.jar

Pro Tip: You can create an alias in your shell (.bashrc or .zshrc) to run it simply by typing mars: alias mars='java -jar /path/to/Mars4_5.jar'

QUICKSORT

Quicksort is a sorting algorithm that adopts the divide-and-conquer strategy that has a worst-case value of O(n²) and a best-case value of O(n log n), operating as follows:

1. Choose a pivot, an element of the array, from one of these options:

• First element of the array. (less efficient)
• Using the formula (low + high)/2, where low and high are the values ​​of the first and last element of the array respectively. (takes the middle element, being more efficient)
• Using the formula low + (high - low)/2, where low and high are the values ​​of the first and last element of the array respectively. (also takes the middle element, but avoids overflow if the values ​​are too high)

2. Partition the array, rearranging the list so that all elements before the pivot are smaller than it, and all elements after the pivot are larger than it. At the end of the process, the pivot will be in its final position and there will be two unsorted sublists.

3. Make two recursive calls, in one sorting the sublist of smaller elements and in the other sorting the sublist of larger elements.

QUICKSORT MIPS

The Quicksort performed uses a dynamic array (size defined in memory and elements defined during execution, receiving input from the keyboard), the pivot is the first element of the array and uses Hoare partitioning which uses two pointers that converge (move towards each other) coming from the ends of the array.

Given this, it can be said that this Quicksort is not the most efficient possible, as it could have a better choice of pivot and use other partitioning techniques, such as 3-Way and Dual-Pivot. However, it operates in an average way, is easy to understand and practical to code.

quicksort_execution.mp4

XRAY

MIPS X-RAY is a tool provided by the Mars IDE that allows you to visualize the processor components, the wiring and connections that an instruction requires, and also analyze whether that instruction is native or a pseudo-instruction, that is, whether it is an abstraction of one or more native instructions.

xray_execution.mp4

MIPS PROCESSOR

This project implements a MIPS32 Single-Cycle Processor. Defines the core Instruction Set Architecture (ISA) including Arithmetic, Logical, Memory Access, and Control Flow instructions. Does not feature:

• Pipelining (No Hazard Unit or Forwarding).
• Multicycle execution.
• Cache memory or Virtual Memory management (TLB).

ADAPTATION OF THE QUICKSORT

Unlike the code written to run on MARS, adaptation was necessary to avoid the use of pseudo-instructions and to use only instructions supported by the processor:

• R-Type instructions: add, sub, and, or, nor, slt, jr, sll.
• I-Type instructions: lw, sw, beq, bne, addi.
• J-Type instructions: j, jal.

Consequently, the array was allocated statically in the processor's instruction memory to bypass the lack of system calls. Its visualization was then handled by the $display function of Verilog – as observed in the testbench.

TESTING THE PROCESSOR

To execute the simulation, simply run make in the terminal. This command triggers the Makefile workflow using Icarus Verilog.

The output will display three key verification steps:

1. The Array before sorting: Array: {30, 5, 0, -12, 124, 6}
2. The Array after sorting: Array: {-12, 0, 5, 6, 30, 124}
3. The Register Dump: The final numerical values stored in each register after the sorting concludes.

The displayed register values serve as proof that both the Quicksort algorithm and the Processor Datapath executed correctly. Below is the breakdown of the final state:

• Register 2 ($v0): 0

  • Remained zero throughout execution as no system calls (syscall) were utilized.

• Register 3 ($v1): 2

  • Holds the return value of the partition function (index of the last manipulated value).

• Register 4, 10, 24 ($a0, $t2, $t8): 5

  • These three registers represent the index of the last element being manipulated and positioned.

• Register 5 ($a1): 5

  • Represents low. Started at 0, but reached 5 after the final partition comparison (5 < 5), triggering the loop exit.

• Register 6 ($a2): 5

  • Represents high (Array Size - 1), maintained from the beginning.

• Registers 8, 9, 12, 13, 14, 15 ($t0, $t1, $t4, $t5, $t6, $t7): Various

  • Contain the ALU results from the algorithm's final iteration.

• Register 16 ($s0): 0

  • Preserved (Callee-saved). Remained untouched, holding the reference value 0.

• Register 18 ($s2): 6

  • Preserved (Callee-saved). Remained untouched, holding the array size.

• Register 29 ($sp): 403

  • Stack Pointer. Confirms stack integrity. After all push/pop operations (subtractions and additions), the pointer successfully returned to its initial memory address.

• Register 31 ($ra): 24

  • Return Address. Successfully jumped to the infinite_loop instruction (halt state) after traversing the entire Quicksort logic.

CONCLUSIONS

This project serves as a proof-of-concept for a functional MIPS32 Single-Cycle architecture. By executing a non-trivial algorithm like Quicksort, the project went beyond simple instruction testing to validate the processor's capability to handle loops, recursion, and memory manipulation in a real-world scenario.

Key takeaways include:

• ISA Compliance: The transition from MARS to Verilog required stripping away software abstractions (pseudo-instructions), ensuring the code ran on pure hardware constraints.
• Deterministic Execution: The register dump provides concrete evidence of the processor's accuracy, with the stack pointer ($sp) and return address ($ra) confirming precise flow control.

In essence, this project demonstrates the complete cycle of computing: from high-level algorithmic logic down to the switching of logic gates.

References & Bibliography

The architectural design and datapath implementation were heavily based on the standard reference for Computer Architecture:

Computer Organization and Design: The Hardware/Software Interface (4th Edition) Authors: David A. Patterson & John L. Hennessy Publisher: Morgan Kaufmann (2011)

Specific focus on Chapter 4 (The Processor) for the Control Unit and Datapath design logic.