Simulation of Tomasulo Algorithm

In this post, I share some details on my extension to a simple simulation for the Tomasulo algorithm as part of the assignment for COSC 6385 course at the University of Houston.

This work extends an existing implementation of the Tomasulo algorithm from 1-issue to n-issues, where n = 1, 2, 3, 4.

Tomasulo Algorithm

Tomasulo’s algorithm is used for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units.

In this implementation, I made the following changes:

1. Modified the existing Python implementation of the Tomasulo algorithm to support issuing multiple instructions, writing back multiple completed instructions, and committing multiple instructions (supports variable issue width).
2. Tested the modification with a set of hardware configurations and sample test cases.

What Works

• Supports multiple issue, write-back, and commit.
• Functional units are pipelined.
• Implements in-order issue with multiple-issue support.
• Supports multiple functional units and multiple load-store units; configurations with more than one of each will also work.
• Supports both pipelined and non-pipelined load-store units.

Limitations

• This implementation does not support branch prediction, so inputs with branch commands such as beq and bne will fail when the issue width is greater than 1.

The implementation can be found in the repository.