OOO Processor Simulator

Project Overview

This project simulates a simple out-of-order processor, modeled after the MIPS R10000. It focuses on a cycle-exact simulation of the processor's internal data structures during the execution of a subset of the RISC-V instruction set. The simulator reads an assembly program, updates internal data structures at the end of every cycle, and continues until execution completes.

Pipeline Structure

File Structure

main.py

The entry point of the simulator. It handles command-line arguments, reads input assembly instructions, and manages the flow of execution to the processor.

processor.py - The Core Processor Class

The Processor class in processor.py is the centerpiece of the simulation, orchestrating the entire instruction cycle and integrating various components of the processor:

Initialization (__init__): The constructor initializes a plethora of essential components like BusyBitTable, DecodedPCs, ExceptionFlag, FreeList, IntegerQueue, ProgramCounter, PhysicalRegisterFile, and RegisterMapTable. Each component is vital for different aspects of the processor's operation, from handling exceptions to managing physical registers.
Instruction Parsing: It parses the given assembly instructions into a structured format suitable for processing. This parsing is a critical step in preparing the instructions for the simulation pipeline.
Stage Integration: The class integrates different stages of the processor's pipeline - Fetch and Decode, Rename and Dispatch, Issue, Execution, and Commit. Each stage is represented by a dedicated class, and Processor manages their interaction and data flow.
Simulation Run (run_simulation): This method is the heart of the simulation. It iteratively executes each stage in the instruction cycle, handling the intricate details of processor operations like instruction fetch, decode, execution, and commit. The method also handles exceptions and ensures the proper progression of the program counter.
Output Generation (write_output): This function compiles the current state of various components into a structured format. It is essential for tracking the state of the simulation at each cycle, providing insights into the internal workings of the processor.
Complex Control Flow: The simulation involves complex control logic to ensure that each stage of the instruction cycle is executed in the correct order and that the processor state is accurately maintained throughout the simulation.

The Processor class, with its intricate design and comprehensive control over the simulation, exemplifies a sophisticated model of a processor, capturing the complexity and dynamism of modern CPU operations.

datastructures.py - Core Data Structures Implementation

This file implements a range of complex data structures critical for simulating the processor's operation:

Instruction Class: Represents an individual assembly instruction. It includes attributes like mnemonic, destination register, source operands, program counter, and immediate value. The class also offers methods for parsing text into an instruction and renaming instructions during the register renaming stage.
RenamedInstruction Class: A specialized version of the Instruction class, designed to handle the post-renaming stage of instructions. It includes logic for updating destination and source registers based on the physical register mappings.
PhysicalRegisterFile Class: Simulates the processor's physical register file. It manages register values and ready flags, providing functionalities to read, write, and check the readiness of registers.
ActiveListEntry and ActiveList Classes: These represent the processor's active list, which tracks the state of instructions as they progress through the pipeline. The ActiveListEntry class encapsulates the state of individual instructions, while the ActiveList class manages the collection of these entries.
IntegerQueueEntry and IntegerQueue Classes: Represent the processor's integer queue. The IntegerQueueEntry class holds information about individual entries, such as operand readiness, register tags, and operation codes. The IntegerQueue class manages these entries, supporting operations like adding, removing, and updating entries based on readiness.
BusyBitTable Class: Manages the busy status of physical registers. It keeps track of which registers are currently busy and associates instructions with busy registers. This is vital for handling data hazards in the processor.
ProgramCounter, FreeList, RegisterMapTable Classes: These classes simulate crucial components of the processor. ProgramCounter tracks the current instruction address. FreeList manages the pool of free physical registers. RegisterMapTable maintains the mapping between architectural and physical registers.
DecodedPCs, ExceptionFlag, and ExceptionPC Classes: These specialized classes handle the processor's control flow. DecodedPCs tracks the program counters of decoded instructions. ExceptionFlag and ExceptionPC manage exception signaling and exception program counters, respectively.

Each class in this file is meticulously crafted to emulate specific aspects of the processor's architecture and behavior, contributing significantly to the cycle-accurate simulation of the processor.

stages.py

This file encapsulates the complex logic of different stages in the processor's instruction cycle:

FetchAndDecode Class: Manages the initial fetching and decoding of instructions. It maintains a list of program counters (PCs) and executes decoding logic based on the current state of the program counter and exception flags.
RenameDispatch Class: Handles the renaming and dispatching of instructions to free up processor resources and avoid conflicts. It involves complex checks for resource availability (physical registers, active list, integer queue, busy bit table), renaming logic based on register mappings, and updating various data structures like the Busy Bit Table and the Physical Register File.

Picture of Data Paths:

Issue Class: Responsible for issuing instructions to the Arithmetic Logic Units (ALUs). It involves sorting instructions based on their readiness (determined by operand availability), handling operand forwarding, and removing instructions from the queue once they are issued.
Execution Class: Simulates the actual execution of instructions. This includes cycle-based execution handling, result calculation for different operations (addition, subtraction, multiplication, division, remainder), handling exceptions during execution, and forwarding paths management.
Commit Class: Deals with committing the results of executed instructions back to the register files. This involves managing the active list, restoring processor state in case of exceptions, and updating the busy bit table and free list.

Each class represents a distinct stage in the instruction processing pipeline, contributing to the cycle-accurate simulation of the processor. The stages are interconnected, passing information and updating shared data structures, thereby mimicking the behavior of an out-of-order processor.

Visualization Tool - How to Use visualization.html

The visualization.html tool is an interactive web-based visualizer designed to display the state of the processor at each cycle of the simulation. Here's how to use it:

File Upload: Start by uploading the output file generated from main.py. This file contains the data representing the state of the processor at each cycle.
Navigation: Use the left and right arrow buttons to navigate through the different cycles. This allows you to observe how the data structures evolve cycle by cycle.
Data Structures Visualization: The tool displays key processor components like the Program Counter (PC), Decoded PCs, Active List, Physical Register File, Integer Queue, etc. It provides a clear and detailed view of the processor's internal state.
Exception Handling: The tool also indicates if the processor is under an exception and shows the Exception Program Counter (Exception PC) when applicable.

This visualization tool is an invaluable resource for understanding the dynamic operations of the processor during the simulation.

Testing and Verification

The project includes a comprehensive testing suite located in the "test" folder. It is designed to test various cases such as Read-After-Write (RAW) dependencies, exceptions, and long chains of data dependencies. The testing framework includes:

build.sh: A script to install necessary dependencies, including jsonschema. It ensures the testing environment is correctly set up.
run.sh: A convenient script to run the processor simulation on a specified input file. This allows for individual test runs and quick checks.
runall.sh: This script executes the processor simulation on all input.json files within the test folder. It's useful for bulk testing and ensuring consistent performance across multiple test cases.
testall.sh: A comprehensive testing script that compares the output files generated by runall.sh with their respective correct output.json files. It uses the compare.py file for comparing the actual output to the expected output, ensuring accuracy and correctness of the simulation.
Test Cases: The test folder contains a variety of test cases, each focusing on different aspects of the processor's functionality. These cases are critical for verifying the correct implementation of the processor's features, including handling of data dependencies and exceptions.

The testing suite is a crucial component of the project, providing the tools and framework necessary for rigorous verification of the processor simulator's functionality and correctness.

Author

Andrew Shusterman