Tomasulo’s Algorithm

An Efficient Algorithm for Exploiting Multiple Arithmetic Units, R. M. Tomasulo, IBM Journal, January 1967

instructions and it’s execution plan would be like this.

div Rg, Rb, Rc
add Rh, Rg, Rd (data hazard)
mul Rg, Re, Rf
add Ra, Rh, Rg (data hazard)

106670243_bb27bd269b.jpg

then, we should maintain RS(Reservation Station) for 2nd and 4th instructions because those instruction need to wait for previous result. and, RS may look like this. source operands of the 1st instruction are ready and the result would be tagged T1 for register Rg and then put this tag T1 and mark busy bit into register till the result comes out. but the first operand of 2nd instruction is not ready when this instruction decode. it need to wait for Rg which is tagged for T1 by previous instruction. by looking up the register, we can figure out. if busy bit is set, the register is not available. so, we should wait for this tagged result.

Ready Tag Contents Ready Tag Contents Register
Y Rb Y Rc T1
N T1 Y Rd T2
Y Re Y Rf T3
N T2 N T3 T4

RS and register will watch the result bus to get tagged result. for this example, we will get T1 first then 2nd instruction will be ready to go. when we got 2nd tagged result(T3), left operand of 4th instruction will be ready and the busy bit of the register Rg will be marked free(N).

busy Tab register
Y T4 Ra
Y T2 Rh
N T3 Rg
Advertisements

2 Responses to “Tomasulo’s Algorithm”

  1. pigtails roundasses

    ka-ka-sh-ka 2149192 Reviews on pigtails roundasses.

  2. hardcore bbw thumbnail galleries

    ka-ka-sh-ka 2149192 Description of hardcore bbw thumbnail galleries.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: