A.D.A. Amiga Demoscene Archive

        Welcome guest!




log in with SceneID


Demos Amiga Demoscene Archive Forum / Coding / Branch cache


Author Message
#1 - Posted: 14 Aug 2008 21:21
Reply Quote
Hi people,

I'm looking for branch cache information, i know the cache has 256 entries but i'm not sure how it is managed.

I have an innerloop with 6 comparaisons and i don't know if the condition result is important or if it's just the 256 entries table who is important.

if you have information on this subject it will be really appreciate.

#2 - Posted: 14 Aug 2008 22:39
Reply Quote
Hi Jamie,

Section 5.11 and 8.4.7 of the 68060UM contain a little information on the cache. There's also an article in IEEE Micro (april 1995) which has some more detailed info. I'll mail a scanned version to you.

Here follows my interpretation of those documents. I haven't done much testing of this in practice.

The branch cache has 256 entries. These are split up as 4 x 64 entries (so it is a 4-way set-associative cache). Each cache entry has the following data:
branch source
branch target address
prediction state
condition code  (in case it is a conditional bran 

Prediction state has 5 possible values:
Not predicted
Strongly not taken
Weakly not taken
Weakly taken
Strongly taken

If a branch instruction lacks an entry in the branch cache, its status will be "not predicted". When the instruction is added to the branch cache, it will be added as "Strongly taken" or "Strongly not taken", depending on whether it was taken or not during this 1st run. After that, taking/not taking the instruction will bump its state one notch up/down along the "taken"/"not taken" ladder. The instruction will not go back to "Not predicted" state.
I don't know if branches with dynamic targets (such as "jmp (a0)") are predicted.

The branch cache lookup is done on the source instruction. Here is an example of how branch cache entries will be created:

	moveq	#1,d0
	moveq	#0,d1
	moveq	#64,d7
	ad d.l	d0,d1
	add.l	d0,d1
	beq.s	earlyexit		<= branch cache entry 1
	add.l	d0,d1
	add.l	d0,d1
	add.l	d0,d1
	subq.l	# 1,d7			<= branch cache entry 2
	bne.s	loop

The first branch (the one inside the loop) will initially get predicted as "not taken", and will remain that way for all iterations of the loop. It is a 1-cycle, not-taken type branch. Those branch instructions get attached to the location of the branch instruction.

The second branch will get predicted as "taken", and will remain so for all iterations of the loop. It is a 0-cycle, taken type branch. Those get attached to the address of the instruction *before* the branch instruction.

Now, your question. The condition codes in the branch cache seem to be used only to simplify the testing of whether or not the prediction was correct. So you don't need to worry about the condition codes themselves; just make sure that the prediction logic (the 5-state prediction value for each branch entry) gets most of the predictions correct.


  Please log in to comment





A.D.A. Amiga Demoscene Archive, Version 3.0