Simulation of Tomasulo Algorithm

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

This work is an extension for existing implementation of tomasulo algorithm with 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 have done following,

1. Modified the existing python implementation of tomasulo algorithm to support issuing multiple instructions, write-back multiple completed instructions and committing multiple instructions. (supports variable issue width)
2. I have tested my modification with a set of hard-ware configurations and sample test-cases.

What Works

• Supports for multiple issue, write-back, and commit.
• Functional units are pipe-lined.
• Implemented in-order execution, with multiple issue.
• This implementation supports multiple functional units and multiple load-store units; thus, changing configuration with functional units and load-store units more than one will also work.
• This implementation supports Load store unit is not pipe-lined and pipe-lined.

Limitations

• This implementation doesn’t support the branch-predictions, so inputs with branch commands such as beq and bne in fail when the issue-width is greater than 1.

The implementation can be found in the repository.