Dual-Issue Out-of-Order Superscaler Processor Using Tomasulo's algorithm in Logisim

Project GitHub

This article discusses my implementation of Tomasulo's algorithm on a simple simulated processor in Logisim and how I was able to extend it to allow for dual-issuing of instructions. If you are unfamiliar with Tomasulo's algorithm, I'd strongly recommend checking out my previous post describing the algorithm. Before I get started, here's some quick definitions of everything in the very long title:

• Dual-Issue - Two instructions are being fetched from memory each clock cycle
• Out-of-Order - Instructions can be queued up and ran out-of-order from how they appeared in the program in order to prevent stalls when one instruction takes too long but others do not depend on it. This also allows multiple instructions to be ran at the same time, given they don't depend on each other.
• Superscaler - Multiple instructions are able to be executed in each clock cycle using multiple execution units
• Tomasulo's algorithm - The process which is used to manage dependencies between instructions and determine which ones can be run and when. This will be explored throughout the course of this article.

Alright, on to the article...

After reading through some more of Computer Architecture: A Quantitative Approach, I got inspired to have a hand at my own implementation of Tomasulo's algorithm, which allows for processors to handle running and queueing multiple instructions at once. Once I got the basic algorithm down, it was pretty straightforward to expand the processor to be able to commit multiple instructions per clock cycle and fetch multiple instructions from memory per clock cycle (hence the "dual-issue" in the title).

As with the other simulated processor I put together (link), I used Logisim to design this whole thing and tried to keep everything else simple in order to maintain focus on the algorithm itself in the project. The ISA I implemented was from a digital electronics class my school offers and is very minimalistic (see image for description). Since jump addresses can only be 6 bits long, this limits all programs to being only 64 instructions, which makes the ISA a bit impractical, but again, the point of this was just to study the theory of instruction-level parallelism.

The very simple ISA. Instructions are 8-bit and operate on 4 16-bit registers.

The Processor/Implemenation in Logisim

Top-level overview of the processor. You may need to open it in a new tab and zoom in to see the detailed text.

Here is the root level of the entire processor where everything connects. The bulk of Tomasulo's algorithm comes from the Reservation Stations, the Issue Logic, the Common Data Bus, and the Register Stats blocks.

Since the processor is dual-issue, the Instruction Memory contains 16-bit words so two 8-bit instructions can be fetched each clock cycle.

Here is a basic overview of the responsiblities of each part:

• Program Counter/Instruction memory - Keeps track of where you are in the program and fetch instructions from memory. In the case that the program is fetching from an odd memory address, only the second instruction will be read in (back half of the 16-bit memory word) and the other will be served as a nop.
• Reservation stations - Hold instructions waiting to be executed/being executed and tell execution units (ALUs, Memory Controller, Branch Manager) when to execute. These must also be able to clear themselves when they see their result written on the common data bus.
• Register Stats / Registers - Keep track of which reservation station each register is waiting on and update when the relevant reservation station is seen on the common data bus.
• Issue logic - Generate data used to place instructions inside of reservation stations and manage dependancies between the two instructions being issued.
• Common data bus - Allow for up to two execution units per clock cycle to send their data down the common data bus and complete operation.

Preformance

To demonstrate the preformance of the processor I ran the following simple endless fibonacci sequence calculator program which places fibonacci numbers starting with the second term (1, 2, 3, 5, ...) in memory consecutively.

ldi R0,0     # current memory address to write to
ldi R1,1     # constant 1
ldi R2,1     # prior fibonacii value #1
ldi R3,1     # prior fibonacci value #2
t0: st R3,R0 # mem[R0] = R3
add R0,R1    # R0 = R0 + 1
add R2,R3    # R2 = R2 + R3
st R2,R0     # mem[R0] = R2
add R0,R1    # R0 = R0 + 1
add R3,R2    # R3 = R3 + R2
jmp t0       # loop

# compiled: 0e5e 9ede cb12 b28b 12e2 1000

The time to place 46,368—the largest fibonacci number able to be represented with 16 bits—in memory for this processor and other simple ones is listed below:

Architecture	Cycles to store 46,368	Average cycles per number after setup
This processor	47 cycles	2 cycles/num
Single cycle processor	82 cycles	3.5 cycles/num
Pipelined processor from the digital electronics course (see image below)	83 cycles	3.5 cycles/num

The old aquarium themed pipelined processor I made for the digital electronics course. The red numbers are the 4 16-bit registers.

Resulting sequence placed in memory

No comments here yet. You should write one!