About Me
Michael Zucchi
B.E. (Comp. Sys. Eng.)
also known as Zed
to his mates & enemies!
< notzed at gmail >
< fosstodon.org/@notzed >
how ffast can a fmadd fm & add?
Someone asked on the parallella forums how to get that 1-cycle-per fused multiply-add thing to work. I'm pretty sure it's impossible to get it out of the compiler as it stands right now so I didn't even try but I had a look at doing it in assembly language. I was going to post this there but i remembered it doesn't use pre-formatting for code blocks, and it's kind of interesting anyway.
The basic technique is straightforward: double-word loads must be used to load every floating point value otherwise there are too may ialu ops, and once that is established one just needs enough of a calculation to fit in a loop to remove all dependency stalls by unrolling it some number of times.
The details are important though, my first cut didn't delay the fmadd's enough - but ezetime showed this very obviously so it was easy enough to fix.
Actually it's not that straightforward: the inner loop itself also needs to be pipelined - so not only is it unrolled 8 times the 8 steps have been split into two stages temporally separated by half a loop each so it's "effectively" been unrolled 16x. Infact it's a bit better than that because no amount of loop unrolling could hide the data loads completely if each loop were independent. In this case it just needs to perform 0.75 loops incoming (all the loads and half the flops) and 0.25 loops outgoing (the remaining half the flops) outside of the loop to prepare/complete the calculation so the loop count is set to one less than required.
So here's a dump from running ezetime over the assembled code. Of interest is the inner loop where every instruction pair dual-issues and a new fmadd is issued every cycle.
0123456789012345678901234567890123456789012345678901234567890123
_fmadd:
00000000: movts.l special.0.5,r2 | ---1 |3
00000004: mov.l r2,#0x0000 | ---1 |3
00000008: movts.s special.0.6,r2 | ---1 |3
0000000a: mov.l r2,#0x0000 | ---1 |3
0000000e: movts.s special.0.7,r2 | ---1 |3
00000010: mov.l r16,#0x0000 | ---1 |3
00000014: mov.l r17,#0x0000 | 1 |
00000018: mov.l r18,#0x0000 | 1 |
0000001c: mov.l r19,#0x0000 | 1 |
00000020: mov.l r20,#0x0000 | 1 |
00000024: mov.l r21,#0x0000 | 1 |
00000028: mov.l r22,#0x0000 | 1 |
0000002c: mov.l r23,#0x0000 | 1 |
00000030: ldrd.l r48,[r0],#+1 | 12 |
00000034: ldrd.l r56,[r1],#+1 | 12 |
00000038: ldrd.l r50,[r0],#+1 | 12 |
0000003c: ldrd.l r58,[r1],#+1 | 12 |
00000040: ldrd.l r52,[r0],#+1 /| 12 |
00000044: fmadd.l r16,r48,r56 \| 1234 |
00000048: ldrd.l r60,[r1],#+1 /| 12 |
0000004c: fmadd.l r17,r49,r57 \| 1234 |
00000050: ldrd.l r54,[r0],#+1 /| 12 |
00000054: fmadd.l r18,r50,r58 \| 1234 |
00000058: ldrd.l r62,[r1],#+1 /| 12 |
0000005c: fmadd.l r19,r51,r59 \| 1234 |
hw_loop_s:
00000060: ldrd.l r48,[r0],#+1 /| 12 |
00000064: fmadd.l r20,r52,r60 \| 1234 |
00000068: ldrd.l r56,[r1],#+1 /| 12 |
0000006c: fmadd.l r21,r53,r61 \| 1234 |
00000070: ldrd.l r50,[r0],#+1 /| 12 |
00000074: fmadd.l r22,r54,r62 \| 1234 |
00000078: ldrd.l r58,[r1],#+1 /| 12 |
0000007c: fmadd.l r23,r55,r63 \| 1234 |
00000080: ldrd.l r52,[r0],#+1 /| 12 |
00000084: fmadd.l r16,r48,r56 \| 1234 |
00000088: ldrd.l r60,[r1],#+1 /| 12 |
0000008c: fmadd.l r17,r49,r57 \| 1234 |
00000090: ldrd.l r54,[r0],#+1 /| 12 |
00000094: fmadd.l r18,r50,r58 \| 1234 |
00000098: ldrd.l r62,[r1],#+1 /| 12 |
0000009c: fmadd.l r19,r51,r59 \| 1234 |
hw_loop_e:
000000a0: fmadd.l r20,r52,r60 | 1234 |
000000a4: fmadd.l r21,r53,r61 | 1234 |
000000a8: fmadd.l r22,r54,r62 | 1234 |
000000ac: fmadd.l r23,r55,r63 | 1234 |
000000b0: fadd.l r16,r16,r17 | 1234 |
000000b4: fadd.l r18,r18,r19 | 1234 |
000000b8: fadd.l r20,r20,r21 | 1234 |
000000bc: fadd.l r22,r22,r23 | -1234 |1
000000c0: fadd.l r16,r16,r18 | -1234 |1
000000c4: fadd.l r20,r20,r22 | --1234 |2
000000c8: fadd.l r0,r16,r20 | ----1234 |4
000000cc: jr.l r14 | 1 |
Over 2048 data elements it executes in 2089 cycles plus a couple dozen for the function invocation and hardware timer setup overheads. I used 2x8k buffers one in bank 1 and the other in bank 2.
Once it finishes the inner loop it completes the calculations for the data pre-loaded during the final iteration and then sums across the 8 partial sums in 3 parallel steps.
A compatible/equivalent C function taking the same args would be:
// len8s1 == element count / 8 - 1
float fmadd(const float *a, const float *b, int len8s1) {
int count = (len8s1+1)*8; // 'unroll' the count
float c = 0;
for (int i=0; i < count; i++)
c += a[i] + b[i]; (oops)
c += a[i] * b[i];
return c;
}
I haven't validated that it produces the correct calculation but apart from a typo or something it should be correct.
The movts instructions near the start of the listing above are lc, ls, and le respectively (loop count, loop start, loop count) for the hardware loop feature; ezetime doesn't output the register aliases. This is also for an unlinked object so the addresses are all zero - but it sets ls to (hw_loop_e-4) for those who might understand what that means, i just put the label where it is to make the loop more readable. I fiddled with the size of the movts instructions till i got the alignment right so it doesn't need any nops for that alignment. Also, the movts instruction cycle timing isn't meant to be correct.
PS Another 8 cycles could be knocked off if the first loop just used fmul since the 8xloads of 0.0 could be removed; but then it would need 1.75 loops before starting the inner loop
JavaFX Task interface
I've been doing a bit of work on a JavaFX application turning it from a very rough prototype to a very rough product (i mean, what can one really accomplish in two weeks?). I already had a bunch of background tasks running using threads but because the original was thrown together in a rush for a small side-project I just hand-rolled everything using familiar techniques (combination of threads and ExecutorService).
I'd seen JavaFX's Task and wasn't really sure what the point was - sure it simplified a couple of things but Platform.runLater() is easy enough to use and so on.
But I found things got messy pretty fast and behaviour started leaking between abstraction layers.
So as part of this re-work I decided to "use it in anger" and see how it turned out. Quite well, if you're prepared to let JavaFX control the middle-tier of the application by using Task everywhere (and for a JavaFX application, there's no reason not to). Encapsulating the work in a Task object allows the decisions about what to do with the user interface to be decided wherever it is used; e.g. does it bother to start a spinny thing or just run silently and so on. And it handles some of the fiddly stuff so that you don't end up with a busy spinner that never runs out.
Having tasks as immutable single-use objects is how I usually write multi-thread code anyway so it wasn't much of a change (IMHO it's the only way which works). Basically all transient state needs to be captured in the job object so it can be worked on independently of the rest of the application, and all outputs are collected in a result object (memory permitting, and the size of modern memory systems makes them very permissive). If incremental updates are desirable then they can be communicated via some other mechanism although it is perhaps surprising how often incremental update just doesn't work very well for a user.
There are still some small gotchas. Say for example that you're firing off a calculation based on interaction with a slider. Ideally you want the result to update as fast as the slider does but this is often not possible. You can't just let every job run to completion because otherwise it will quickly start to lag and just feel wrong. You can't cancel every job if a new one arrives because you may never have one complete leaving the user staring at stale results. One hack is to just update the result when the user releases the slider knob but that removes most of the interactivity from the GUI and defeats the purpose.
Previously i've solved it by implementing a greedy consumer. Jobs are indivisible units which always run to completion (and to the user interface) but whenever the worker thread polls for incoming jobs it throws away all but the last one if more are queued. ExecutorService doesn't directly allow this granularity of job control but it can be emulated easily enough by something like the following.
ExecutorService queue;
Task task;
void dowork() {
if (task != null && !task.isDone() && !task.isRunning()) {
task.cancel();
}
task = new WorkTask( ... );
task.setOnSucceeded( ... );
queue.submit(task);
}
(is there another way? I don't know, this is what I found ...).
This isn't used for tasks which might take a very long time to complete but for ones which are already interactive speed or close to it (roughly, under 0.5s). It lets any already running jobs finish but cancels any waiting in the queue.
This makes the application "feel" much lighter and more responsive even if it does slightly more calculation than necessary. Unless the work is very trivial almost all such work needs to be thrown into a thread otherwise sliders start to feel unresponsive. This is pretty much the same for any toolkit (or os).
post weekend
I did a bit more work on the ezetool code - most improvements to the output. Added labels, each function has the cycle counters reset, and branch targets are calculated.
As a bit of an experiment I wrote a tiny bit of a simulator - just enough to simulate all the instructions in isqrt().
Simulation of calculating an approximation to iqsrt(9) (i.e. 1/3):
000000: mov.l r2,#0x0000 r2 <- 00000000 0.000000
000004: movt.l r2,#0x3f00 r2 <- 3f000000 0.500000
000008: mov.l r1,#0x59df r1 <- 000059df 0.000000
00000c: fmul.s r2,r0,r2 r2 <- 40900000 4.500000
00000e: movt.l r1,#0x5f37 r1 <- 5f3759df 13211836172961055000.000000
000012: asr.s r0,r0,#0x0001 r0 <- 20880000 41100000
000014: sub.s r0,r1,r0 r0 <- 3eaf59df
000016: mov.l r1,#0x0000 r1 <- 00000000 0.000000
00001a: movt.l r1,#0x3fc0 r1 <- 3fc00000 1.500000
00001e: fmul.s r2,r2,r0 r2 <- 3fc5451b 1.541171
000020: fmsub.s r1,r2,r0 r1 <- 3f78e082 0.972176
000022: fmul.s r0,r1,r0 r0 <- 3eaa78d8 0.332953
000024: jr.l r14
But it was just using the string names of the instructions in a switch statement and was a bit bulky so I started looking into ways of making it easier to write and ended up falling down a pretty deep rabbit hole before I decided I don't really want to write a simulator anyway (well, probably not).
One thing I was looking at was including the instruction operation in the instruction definition file directly, so i started playing with an expression parser. I came up with a pretty novel (or perhaps, just shit) non-recursive parser implemented using a hand-coded state machine and a few stacks but it wasn't anything more than a bit of piss farting about.
But this playing with an expression parser got me thinking about a programmers calculator. I mostly fire up a random xterm and run gdb whenever I want to do some sort of calculation (going by ps i currently have 9 littered across 4 virtual desktops amongst 38 xterms and 8 copies of emacs) but although that serves most of my needs very well sometimes it just doesn't. Sometimes I need to write little C or java snippets or resort to an old Sharp calculator.
Today mostly out of curiosity I had a look at some compiler generator tools - i found that bison has a Java output which although it doesn't seem to be actively developed appears to function ok. I started with my own lexical analyser but that quickly got messy so I tried jflex which did the job fine. These are the sort of tools I play with out of curiosity every few years but never do anything useful with - i think they're kinda nifty but never seem to have a real need for them.
gdb also has has a command line. Thus deeper down the rabbit hole I went looking for a readline equivalent for Java. I looked at one but it had a few external dependencies and uses maven to resolve them (which means: just no). So ... I mucked about for a couple of hours writing my own. Using stty to set the terminal to raw mode and then creating a stream which decodes the escape sequences. Of course I've forgotten everything i did with zvt (gnome-terminal 1.0) but it didn't take long to get a single-line editor going with basic functions like navigation, editing, and history. But probably it may as well just have it's own window so that was mostly just a bit of pointless mucking about and I probably should've just been playing with doing it with a gui toolkit.
Then the weekend ended.
I dunno, maybe I'll keep playing around with it, or maybe I wont.
At least I finally pruned the roses and re-trained some of them onto stakes. Kinda been letting them go a bit. Did a bit of other gardening stuff too - it turned out to be an ok enough day with a bit of sunshine and a little warmth although it didn't last long.
instruction matching
This was an interesting little diversion.
One of the requirements of a disassembler or code translator is to work out from the machine code what instruction is at a given address. Most instruction sets are variable in size so it has to determine that as well.
Depending on how the instruction set was designed this can either be a simple table lookup, ... or get somewhat more involved. It usually can't just be all a simple lookup though as there are usually some instructions that want to use most of the bits for data.
Linear
The current implementation in ezetool uses a simple linear search. For each instruction it sees if all the selector bits for the instruction match the test bits. This is trivial:
boolean match = (select_mask & opcode) == select_bits;
It has to be executed up to two times because it doesn't know the instruction size yet. Bit 3 has that information for many instructions but not all.
Linear split
An obvious improvement that I didn't have time for initially is to split the search into two separate lists. One for 16-bit instructions and one for 32-bit instructions. Because it just Has To Be, all 32-bit instructions will be different in their first 16-bits to all 16-bit instructions so the lists can be separated.
This amounts to a pre-indexing of the instructions based on their size and lead to over 100% performance increase.
List of Hash Tables
A hashtable can't be used directly because you don't know in advance which of the bits are significant.
This can be shown by displaying the instructions which use the same selector bits as i'm using them. Some of the 'selector' bits here are separating instructions into different addressing modes which could be handled in a different way (the high-bits of the ldr and mov instructions) but this is the way i've written it so far.
0000000f: b b (16/32 bit variants)
0000001f: ldr str ldr str ldr str mov lsr lsl asr bitr
0000007f: add sub add sub add sub and orr eor asr lsr lsl fadd fsub fmul fmadd fmsub
0000030f: mov
000003ff: float fix fabs movts movfs jr jalr gie gid nop idle bkpt mkpt sync rti wand trap
000f001f: lsr lsl asr bitr
000f007f: add sub and orr eor asr lsr lsl fadd fsub fmul fmadd fmsub
000f030f: mov
000f03ff: float fix fabs movts movfs jr jalr
0200001f: ldr str ldr str
0060001f: ldr str testset ldr str
1000001f: mov movt
A solution here would perform a linear search across all select-bit combinations, and each of those would be accessed via a hash table. Given the simplicity of the comparison test though it may as well just be a linear search.
I didn't try implementing this but as it removes the smask de-reference outside of the inner loop it may be ok.
Radix/index M-tree
Looking at the output above it is clear that at least 0x0f is used as a selector bit in every instruction. This can be used to create a first-level index and reduce the search space.
Indexing by the first nybble:
0 [ 1]: b
1 [ 2]: ldr str
2 [15]: mov movts movfs jr jalr gie gid nop idle bkpt mkpt sync rti wand trap
3 [ 3]: mov add sub
4 [ 2]: ldr str
5 [ 2]: ldr str
6 [ 2]: lsr lsl
7 [ 8]: fadd fsub fmul fmadd fmsub float fix fabs
8 [ 1]: b
9 [ 3]: ldr str testset
a [ 8]: add sub and orr eor asr lsr lsl
b [ 4]: mov movt add sub
c [ 4]: ldr str ldr str
d [ 2]: ldr str
e [ 2]: asr bitr
f [25]: lsr lsl asr bitr add sub and orr eor asr lsr lsl fadd fsub fmul fmadd
fmsub float fix fabs mov movts movfs jr jalr
Well, it's simple ... but not very effective.
I did some analysis of the longer sets above and found most instructions use either 0x70 or 0xf0 as selector bits so a further level of m-tree can be added for those. For the others I just dump them into a linear search.
This reduces the worst-case to:
f: lsr lsl asr bitr mov
0: eor fadd movts
1: add fsub movfs
2: lsl fmul
3: sub fmadd
4: lsr fmsub jr
5: and float jalr
6: asr fix
7: orr fabs
Which involves: a direct radix-index based on the first 4 bits, a 2 or 3 element linear search from a 3-bit radix, and a 5-element linear search across the 'leftovers'. This turned out to be very fast - about 6x faster than the linear search, but did require a bit of human input for the tree sizes.
Radix/sparse tree
I'm not really sure what to call this but i guess its a sort of radix search but with a sparse tree. I was seeing if i could fully automate the tree building.
Each significant bit is indexed from the lsb upwards. Each tree node has a list of child nodes which specify which bit and bit-value they correspond to. The first 4 levels of the tree are fully filled but as the selector bits change it becomes a sparse tree.
My initial naive thought was that this could find a solution in one pass like a huffman code but of course this isn't the case: it still has to perform a fairly wide search because, again, it doesn't know which bits are significant (if it did, then it would work in one pass).
I implemented this as a 4-bit radix (i.e. index) into 16 separate trees. It was faster than a linear search but not as fast as the split-linear. I didn't think it was worth the effort to try to optimise the tree so that it would resemble the indexed m-tree.
8-bit index
So at this point I had a pretty good/quick implementation but wondered if i could get any better.
I tried using 8 bits for the first-stage index rather than 4. This complicates matters a little bit because many (most?) instructions don't use the first 8-bits as a selector which means they will alias to multiple locations. The solution: just alias them. So for example 'b' uses only 4 bits as a selector so one ends up with 16 copies.
Here's a part of the table.
0: b
1: ldr
2: mov movts
3: mov
4: ldr
5: ldr
6: lsr
7: fadd
8: b
9: ldr testset
10: eor
11: mov movt
12: ldr ldr
13: ldr
14: asr
15: lsr asr eor fadd mov movts
The worst case (over the whole table) is a single 8-bit indexed lookup followed by 6-element linear search.
Simple code, needs moderate space, and runs really fast ... well most of the time. At least in Java it has some strange cache-related effects so depending on the memory layout its runtime varies by nearly 100%.
Since most instructions don't use all 8-bits as a selector i also tried using 7 or 6 bits. For 7 bits the maximum run is still 6: i.e. well wasn't using 8 silly but with the half the index size. For 6-bits a couple of the runs got slightly longer but it takes half of the index size again.
Micro-Optimisations
I also looked at a bunch of micro-optimisations to the data-structures.
For the linear search, rather than iterating through a list of objects which require a dereference, iterate through a single array of integers which contain the selector mask and bits together. This could be applied anywhere a linear search is although other cases also need to include the instruction index.
Very slight improvement - Java seems good at object dereferences but it might be applicable to c.
I also tried flattening one of the array of lists implementations into a single list of integers. The first N elements are just indices into the array and then the structure at each array is a count followed by { mask, value, index } triplets. Well Java didn't really like this so it wasn't an improvement.
Numbers
I realised all implementations require two lookups so I did timed that. I didn't bother timing the ones which weren't competitive for a single lookup pass.
This is for 100 000 iterations of looking up every instruction in order (84 using my splits). So even the slowest implementation is only 120ns 18ns in Java on a Kaveri CPU. In all cases any lists required during building were collapsed to arrays of exactly the right size - arrays are much smaller than lists and iterate faster.
time memory alg
1.013 0 linear search
0.449 2 linear split search
0.157 (2+64*2)*2+84 344 0x3f index + linear search
0.153 (2+128*2)*2+84 600 0x7f index + linear search
0.180 6*(2+6)+72+84 204 multi-stage radix + linear search
The memory is the approximate extra words required to store the indices. An array is counted as 2 words + space for the contents (length+pointer+data). The multi-stage thing needs the bit number/mask and two arrays and I might have an error there.
Based on that I would probably go with the 0x3f indexed version. The building of the indices is easier than the multi-stage radix algorithm and it doesn't require an additional object (it just uses a 2d array) and memory requirements are modest compared to the 0x7f version with much the same runtime.
Still, it's only about 2.8x faster which is surprising given that the search is an order of magnitude less work, between 0 and 9 linear steps compared to 84 (or on average 4.5 vs 42). The benchmark is probably just not a good one.
Addendum
So there is a very cheap way to determine if the instruction is 16-bits or 32-bits. The first nybble is enough to determine this - i vaguely recall something like that but for some reason I thought it required a bigger table.
boolean isShortInstruction(int opcode) {
return ((0x44ff >> (opcode&0x0f)) & 1) == 1;
}
I added it and re-ran the benchmarks. It makes a measurable but pretty insignificant difference to the indexed implementations. The lookup is already fast enough that loop overheads and other scaffolding must be the dominating factor.
The linear search gained a lot because for a 32-bit instruction all 16-bit instructions had to be scanned before you could determine it wasn't one of them.
time memory alg
1.013 0 linear search (original)
0.296 2 split linear split search
0.156 (2+64*2)*2+84 344 split 0x3f index + linear search
0.149 (2+128*2)*2+84 600 split 0x7f index + linear search
TBH the linear search is fast for the purposes of a command-line tool but I rolled these improvements into the implementation anyway.
It's time ... it's time for some e-zed-e-time
I just uploaded the current state of the epiphany cpu instruction timing tool i've been working on.
It was supposed to be a super-quick chuck-together of what I had but I cleaned up the code and did a big re-factor (everything was in one namespace) and a bunch more. Toolification, building, packaging, readme, webpage, ... so this post will be short.
I haven't done much testing/verification beyond a few small test-cases, so bugs are a given.
It's on the ezetool (now with ezetime(tm)) home page, as is an example of the current outputs.
more tooling around
So i've done a bit more work on the tools and am getting pretty close to the first cut of the timing tool. I did some code tidying and created a separate disassembler tool.
I improved the disassembler output to include the machine code and symbols and handle all addressing modes properly. Yet to do is adding symbols for branch targets (or displaying branch target addresses) and showing aliases for the special registers.
01: 1 SHT_PROGBITS .text 00000000 00000038 000001a0 0 0 0 0000008 SHF_ALLOC SHF_EXECINSTR
_e_build_wtable:
0: 070094fc strd.l r4,[r13],#-1
4: 0400d47c strd.l r6,[r13,#+0]
8: 2002800b mov.l r12,#0x0000
c: a40090ec ldrd.l r44,[r12,#+1]
10: 8023 mov.s r4,#0x0001
12: a400d16c ldrd.l r46,[r12,#+2]
16: 400a312f lsl.l r17,r4,r2
1a: c40011ec ldrd.l r48,[r12,#+3]
1e: a5ba sub.s r5,r1,r3
20: c400526c ldrd.l r50,[r12,#+4]
Pipeline simulator
I did get the timing tool pretty close to functional but then the edge cases started getting messy and I tried reworking it a couple of times.
My current pipeline is something like this:
-> fetch [1] [0] instructions decoded into a 2-element queue
| |
decode and issue detect dual issue, assign pipeline
\ /
X cross-bar switch/router
/ \
DE DE implement RA stall logic. pair stalls together.
| |
RA RA implement E1 stall logic
| |
E1 E1 execute stages
| |
E2 E2
|
E3
|
E4
alu fpu alu = ialu, load/store, control
Note: This is a software-based model of the hardware so doesn't necessarily reflect the physical hardware; it just has to behave the same.
The pipeline is executed from the end backwards - serialising the inherently parallel process of a hardware pipeline but in a way which reaches the same result after each cycle. At each point an instruction only advances if the next pipeline slot is empty. Stalls can happen before RA or E1. I don't know if this is hardware-correct but the timings don't come out right otherwise.
At the fetch stage the next two instructions are read and decoded. Mainly this determines if each a 16-bit or 32-bit instruction and does some setup for the scheduling task. This approximates the way the hardware loads 8-byte instruction blocks and is required to implement the dual-issue logic. There are some fiddly details with the physical hardware that I haven't fully discovered yet (to do with instruction size, alignment, etc) but Andreas says it will probably change in future hardware and is not that important just yet.
The dual issue decision simply decides if both of the next instructions can be executed together. If they can they are then assigned to their respective pipelines and the fetch code is told to grab 2 new instructions. Dual issue rules are quite simple: no written register dependencies and one instruction must be an alu or load/store instruction and the other a floating point op. If they can't be dual-issued then only one instruction advances and the fetch code is told to get only one new one.
The next pipeline stage checks to see if the instructions have the registers they need. This is presumably meant to be in the 'RA' stage but if I put it there instructions are retired too early. If both pipelines contain an instruction (i.e. dual-issue) then they both must pass their register checks before either advance. To calculate if the registers are busy all the instructions present in all the other stages are scanned to determine what registers are still busy. There are some complications here because the answer depends on who's asking.
The next stage then checks for any registers read in E1. AFAIK this is only needed for the store instruction. Each pipeline is tested separately.
The instructions then pass through the pipeline stages until they retire.
My initial cut at the code had each instruction decide when it should reserve a register for itself and when it should mark the register as available (i.e. instruction completed). The decision was mostly based on addressing mode and the scheduling class (fpu/alu/load/control) with some hard-coded 'hacks' to handle specific variations like fmadd. This still wasn't enough as different instructions have different latencies depending upon which instruction is accessing it, and it also varies because some instructions can update two values. The code also tried to incrementally update the 'register busy' set but this was messy and error prone and multiple values needed to be maintained separately.
It got messy.
So i've been working on trying to convert it to a table-driven algorithm with fewer special cases.
After a few iterations this is some output from the current code:
code 0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef
mov.l r1,#0x0000 | 1 |
nop.s | 1 |
ldr.s r0,[r1,#-0] | 123 |
fadd.s r0,r0,r0 | 1234 |
fadd.s r0,r0,r0 | 1234 |
str.s r0,[r1,#-0] | 1 |
The display needs a bit of tweaking but the execution start times and total running time of each instruction match what i'm getting out of the hardware counters (17 cycles total time).
The other output format I have shows the stalls are happening in the right place. There are 3 E1 stalls and 3+6 total register stalls which matches the hardware counters too. (It displays the alu ops continuing through the pipeline although most are retired after E1.)
DE RA E1 E2 DE RA E1 E2 E3 E4
alu: 0 mov - - - fpu: - - - - - -
alu: 1 nop 0 mov - - fpu: - - - - - -
alu: 2 ldr 1 nop 0 mov - fpu: - - - - - -
alu: - 2 ldr 1 nop 0 mov fpu: 3 fadd - - - - -
alu: - - 2 ldr 1 nop fpu: 3 fadd - - - - -
alu: - - - 2 ldr fpu: 3 fadd - - - - -
alu: - - - - fpu: 6 fadd 3 fadd - - - -
alu: - - - - fpu: 6 fadd - 3 fadd - - -
alu: - - - - fpu: 6 fadd - - 3 fadd - -
alu: - - - - fpu: 6 fadd - - - 3 fadd -
alu: - - - - fpu: 6 fadd - - - - 3 fadd
alu: 11 str - - - fpu: - 6 fadd - - - -
alu: 12 jr 11 str - - fpu: - - 6 fadd - - -
alu: 12 jr 11 str - - fpu: - - - 6 fadd - -
alu: 12 jr 11 str - - fpu: - - - - 6 fadd -
alu: 12 jr 11 str - - fpu: - - - - - 6 fadd
alu: 16 nop 12 jr 11 str - fpu: - - - - - -
alu: 17 b 16 nop 12 jr 11 str fpu: - - - - - -
alu: 18 b 17 b 16 nop 12 jr fpu: - - - - - -
I've annotated each instruction+addressing mode pair with a few pieces of information:
- srcRA
- Set of which registers rd,rn,rm are read by the instruction in RA
- srcE1
- Set of which registers rd,rn,rm are read by the instruction in E1, used by str instruction. I had to add a stall test in E1 to implement this.
- dALU, nALU
- How many cycles the d or n register is reserved in terms of alu instructions reading them. I've implemented this as a bit-mask but since every bit is set from 0-x it could just be a number.
- dFPU, nFPU
- How many cycles the d or nregister is reserved in terms of fpu instructions reading them.
Still a bit left like write-after-write stalls but I think that can use a similar mechanism. Things like double-loads or stores can be handled by seeing if the instruction has the appropriate size bits and using rd and rd+1. Because it's only a static analysis tool branches penalties and external loads are not required (although something for the latter might be nice, at least for special register access).
Time passes ... I added write-after-write stalls now (and double load/stores).
So, I think I now have enough guts; but I have go through a few tables and define correct values and then probably convert them into a resource file.
kettle + bucket
Hmm, no wonder my gas bill has always been high, and rising to stupid levels. Big gas leak :-/ Well plumber came, checked, turned it off. Given the volume of the leak i'm surprised I couldn't smell it more but it's underground in a steel pipe.
I've been thinking of getting solar hot water so maybe it's time to finally do that but I just don't want to have to sort anything out right now (i.e. my life; the story so far).
Perhaps cold showers will get me thinking faster. Although it's not bloody likely i'll have any of those; middle of winter and just washing your hands in cold water is ... well cold. Last time I had a hot-water problem was also in the middle of winter and it was an electric kettle and a bucket for a while (I was just about to sell the house and it needed a lot of renovation so getting it replaced wasn't worth it).
just bit of a tool
Weather turned south so I ended up hacking all afternoon again.
After posting the last article I went and had a look at the instruction decoder I was working on. First I was hand-coding it all but then I realised how silly it was so I put it into a simple table. I was going to make a code-generator from that but it's really not necessary.
Here's a tiny bit of the table (it's only 84 lines long anyway). It has 3 fields, instruction name, addressing mode, bit format.
; branches
b 7 i{7-0},c{3-0},v{0000}
b 7 i{23-0},c{3-0},v{1000}
; load/store
ldr 8 d{2-0},n{2-0},i{2-0},b{1-0},v{00100}
str 8 d{2-0},n{2-0},i{2-0},b{1-0},v{10100}
; alu
add 3 d{5-3},n{5-3},m{5-3},x{000},v{1010},d{2-0},n{2-0},m{2-0},v{0011111}
; etc.
The bit format just defines the bits in order as they are displayed in the instruction decode table, so were easy enough to enter.
From this table it's only about 10 lines of code to decode an instruction and not much more to display it - most of it is just handling the different addressing modes (ok it's a lot more but it's all a simple switch statement). It just searches for the instruction that matches all bits in the v{} sections; first in 16-bit instructions and if none are found then reads another 16 bits and looks in the 32-bit instructions. I still have some sign extension stuff to handle properly but here's some example output.
09: 1 SHT_PROGBITS .text.2
strd.l r4,[r13],#-2
strd.l r6,[r13,#+1]
strd.l r8,[r13,#+0]
mov.l r12,#0x0000
ldrd.l r44,[r12,#+0]
mov.s r4,#0x0001
ldrd.l r46,[r12,#+1]
lsl.l r17,r4,r2
ldrd.l r48,[r12,#+2]
sub.s r5,r1,r3
ldrd.l r50,[r12,#+3]
sub.s r6,r5,#0x0002
ldrd.l r52,[r12,#+4]
lsl.s r7,r4,r6
Here's the output from objdump for comparison.
Disassembly of section .text.2:
00000000 <_e_build_wtable2>:
0: 957c 0700 strd r4,[sp],-0x2
4: d4fc 0400 strd r6,[sp,+0x1]
8: 147c 2400 strd r8,[sp]
c: 800b 2002 mov r12,0x0
10: 906c a400 ldrd r44,[r12,+0x0]
14: 8023 mov r4,0x1
16: d0ec a400 ldrd r46,[r12,+0x1]
1a: 312f 400a lsl r17,r4,r2
1e: 116c c400 ldrd r48,[r12,+0x2]
22: a5ba sub r5,r1,r3
24: 51ec c400 ldrd r50,[r12,+0x3]
28: d533 sub r6,r5,2
2a: 926c c400 ldrd r52,[r12,+0x4]
2e: f32a lsl r7,r4,r6
Because I wrote this in Java, before I could even test it ... I had to write an elf library as well. But elf is simple so it was just a few 'struct' accessors for a memory mapped Java ByteBuffer and only took half an hour via some referencing of the code in ezesdk and elf.h.
A simple static analysis tool should be relatively straightforward at this point although to be useful it needs to do some more complicated things like determine dual-issue and so on. For that my guess is that i'll need a relatively complete pipeline simulator - it doesn't need to simulate the cpu instructions, just the register dependencies. A more dynamic analysis tool would require a simulator but I guess that's possible since the cpu is so simple (performance might be a factor at that point though).
But I don't really know and i'm just piss farting about - I haven't written tools like this for ... forever. Last time was probably a dissasembler I wrote in assembly language for the Commodore 64 about 25 years ago so I could dump the roms. Ahh those were the days. Actually these days aren't much different for me apart from different shit to be anxious about.
Productive enough afternoon anyway, I suppose i'd better go find some food and decide if i'm going to stay up to watch the soccer after watching some local footy and maybe the tour. 5am is a bit too late, or early, and tbh i don't really care too much who wins.
Update: Hacked a bit more last night, came up with a really shitty pipeline simulator.
From this code:
fmadd.l r0,r0,r0
fmadd.l r0,r0,r0
add r17,r16,r16
add r17,r16,r16
add r17,r16,r16
add r17,r16,r16
add r17,r16,r16
add r17,r16,r16
fmadd.l r0,r0,r0
rts
Assembled, then loaded from the elf:
de ra e1 de ra e1 e2 e3 e4
alu: - - - fpu: 0 fmadd - - - - -
alu: 1 add - - fpu: 1 fmadd 0 fmadd - - - -
alu: 2 add 1 add - fpu: 1 fmadd - 0 fmadd - - -
alu: 3 add 2 add 1 add fpu: 1 fmadd - - 0 fmadd - -
alu: 4 add 3 add 2 add fpu: 1 fmadd - - - 0 fmadd -
alu: 5 add 4 add 3 add fpu: 1 fmadd - - - - 0 fmadd
alu: 6 add 5 add 4 add fpu: 6 fmadd 1 fmadd - - - -
alu: 7 jr 6 add 5 add fpu: 6 fmadd - 1 fmadd - - -
alu: - 7 jr 6 add fpu: 6 fmadd - - 1 fmadd - -
alu: - - 7 jr fpu: 6 fmadd - - - 1 fmadd -
alu: - - - fpu: 6 fmadd - - - - 1 fmadd
alu: - - - fpu: - 6 fmadd - - - -
alu: - - - fpu: - - 6 fmadd - - -
alu: - - - fpu: - - - 6 fmadd - -
alu: - - - fpu: - - - - 6 fmadd -
alu: - - - fpu: - - - - - 6 fmadd
alu: - - - fpu: - - - - - -
The number infront of the instruction is when it entered the pipeline.
Oops, so bit of a bug there, once it dual-issues the first add/fmadd pair it just keeps issuing the ialu ops, which shouldn't happen. I've go the register dependency test in the wrong spot. I can fiddle with the code to fix that up but I need to find out a bit more about how the pipeline works because there some other details the documentation doesn't really cover in enough detail.
Update: After a bit of work on the house I had another look at the pipeline and did some hardware tests. So it looks like as soon as an instruction sequence arrives which might dual-issue, it gets locked into a 'dual issue' pair which will stall both instructions until both are ready to proceed - regardless of the order of the instructions and whether the first could advance on it's own anyway.
So for example, these sequences all execute as dual-issue pairs (all else being equal, there are other alignment related things but I haven't worked them out yet).
fmadd.l r0,r0,r0 fmadd.l r0,r0,r0 mov r16,r16 fmadd.l r0,r0,r0
mov r16,r16 mov r16,r16 fmadd.l r0,r0,r0 mov r16,r16
fmadd.l r0,r0,r0 mov r16,r16 mov r16,r16 mov r16,r16
mov r16,r16 fmadd.l r0,r0,r0 fmadd.l r0,r0,r0 fmadd.l r0,r0,r0
Anyway, so re-running the timing tool with these new changes give a better result:
alu: - - - fpu: 0 fmadd - - - - -
alu: 1 add - - fpu: 1 fmadd 0 fmadd - - - -
alu: 1 add - - fpu: 1 fmadd - 0 fmadd - - -
alu: 1 add - - fpu: 1 fmadd - - 0 fmadd - -
alu: 1 add - - fpu: 1 fmadd - - - 0 fmadd -
alu: 1 add - - fpu: 1 fmadd - - - - 0 fmadd
alu: 6 add 1 add - fpu: - 1 fmadd - - - -
alu: 7 add 6 add 1 add fpu: - - 1 fmadd - - -
alu: 8 add 7 add 6 add fpu: - - - 1 fmadd - -
alu: 9 add 8 add 7 add fpu: - - - - 1 fmadd -
alu: 10 add 9 add 8 add fpu: 10 fmadd - - - - 1 fmadd
alu: 11 jr 10 add 9 add fpu: - 10 fmadd - - - -
alu: - 11 jr 10 add fpu: - - 10 fmadd - - -
alu: - - 11 jr fpu: - - - 10 fmadd - -
alu: - - - fpu: - - - - 10 fmadd -
alu: - - - fpu: - - - - - 10 fmadd
alu: - - - fpu: - - - - - -
I also have another output format which is like the spu timing tool which shows each instruction in sequence with time horizontal. I don't have the correct labels yet but it shows the dual issue pairs more clearly. The register checking/writing might be in the wrong spot too but the delays look right.
fmadd dr1234
fmadd dr1234
add dr1
add dr1
add dr1
add dr1
add dr1
add dr1
fmadd dr1234
jr dr1
Still a few other details which can wait for another day.
Copyright (C) 2019 Michael Zucchi, All Rights Reserved.
Powered by gcc & me!