Remember, we have no pipeline hazards in this design. There are more separate threads being fed down a given pipeline than there are pipeline stages, so that by the time a given thread has another instruction issued, write-back is complete. This means that there isn't even any need for branch prediction. Conditional branch and conditional move are equally easy in our design. The difference is that with conditional branch, we can have branch divergence, while with conditional move, we cannot. And branch divergence (horizontally across warps) is very bad in a GPU.
On Wed, Jun 6, 2012 at 6:20 PM, Nicolas Boulay <[email protected]> wrote: > On f-cpu project, we project to use predicat on register state, it's > easier to pipeline, the condition (is_zero, ...) are calculated in the > same time as the register is written, so there is less latency for the > read of the status. > > Becarreful on conditionnal move, a post of Linus Torvalds remember > that branche prediction is quite easy to do but data prediction is > really hard. This means that you coulde accelerate branches but not > cmove. If you use a lot cmove, you do a lot of unused job (remember > itanium). > > 2012/6/6 Timothy Normand Miller <[email protected]>: >> Andre and I had debated over whether the shader pipeline should >> support condition codes (like most processors) or not (like MIPS). >> With MIPS, this reduces the amount of state that flows from one >> instruction to the next. But our GPU shader doesn't need any >> restrictions on this since we do away with pipeline hazards by having >> more round-robin threads than there ere iare pipeline stages. After some >> discussion, I am entertaining the idea of not only having condition >> codes but also predicating every instruction's execution based on >> them, just like ARM's 32-bit ISA. Predicating like Itanium didn't >> work our well, because it has rather limited utility for such an >> elaborate system, but in the limited scope to which ARM has put it, it >> has worked out well. So, what conditions? I didn't bother looking up >> ARM's conditions. Instead, I pulled out an MC68000 manual. We need a >> 4-bit field in the instruction, plus a 5th bit to indicate whether or >> not the instruction changes the codes. >> >> >> ~C -- carry clear >> C -- carry set >> ~Z -- not equal >> Z -- equal >> ~V -- not overflow >> V -- overflow >> ~N -- non-negative >> N -- negative >> N&V + ~N&~V -- greater than or equal (for signed ints) >> N&~V + ~N&V -- less than (signed) >> ~C&~Z -- greater than (unsigned) >> Z + N&~V + ~N&V -- less than or equal (signed) >> C + Z -- less than or equal (unsigned) >> N&V&~Z + ~N&~V&~Z -- greater than (signed) >> T -- always true >> F -- always false (no-op) >> >> FCMP will generate codes that have equivalent meaning. >> >> The hardware for this requires an 8-input MUX and an additional XOR >> for the output: >> >> D0 = 1 >> D1 = C >> D2 = Z >> D3 = V >> D4 = N >> D5 = N xor V >> D6 = C or Z >> D7 = (N xor V) or Z >> >> >> BTW, when I say that I recommend something like this, what I mean is >> that I suggest adding it as an option that can be enabled. At the >> very least, we'll want predicated move and we'll want min/max >> instructions to avoid branching. In a GPU, conditional branching is >> to be avoided, because it can lead to branch divergence. >> >> >> >> On a completely unrelated note, when I was studying fuzzy logic back >> in the 90's, I came up with these formulas, which we'd probably never >> want to use in a hardware implementation. They're just helpful for >> doing algebra with min/max fuzzy logic. >> >> min(a,b) = (a + b - abs(a-b)) / 2 >> max(a,b) = (a + b + abs(a-b)) / 2 >> >> >> >> -- >> Timothy Normand Miller >> http://www.cse.ohio-state.edu/~millerti >> Open Graphics Project >> _______________________________________________ >> Open-graphics mailing list >> [email protected] >> http://lists.duskglow.com/mailman/listinfo/open-graphics >> List service provided by Duskglow Consulting, LLC (www.duskglow.com) -- Timothy Normand Miller http://www.cse.ohio-state.edu/~millerti Open Graphics Project _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
