http://semipublic.comp-arch.net/wiki/Non-speculative_or_less_speculative_versus_more_speculative
When discussing [[speculative execution]] techniques such as [[speculative multithreading]] (or [[skipahead]], or [[slipahead]], or ... )
we often need to talk about less speculative and more speculative threads or instructions.
E.g. a later, younger, more speculative load instruction may be blocked by an earlier, older, less speculative store instruction to the same address.
E.g. in [[SpMT]] or [[SkMT]] a less speculative thread may fork a more speculative thread.
Often in early work we only talk about non-speculative threads forking,
and do not discuss the possibility of a speculative thread forking.
Late, it is realized that it is entiirely reasonable for speculative threads to fork.
Thus, often we need to read "non-speculative" in early work,
and implicitly substitute "less speculative".
E.g. a common [[speculative thread management policy]] is to always keep the least speculativethreads,
and cancel any more speculativethreads,
when there is an opportunity to spawn a less speculative thread.
---
Note that "less speculative" is not necessarily the same as "older".
E.g. in a [[fork-on-call]] thread, certain instructions may beindependent of the skipped code,
and be guaranteed to be executed;
whereas other instructions, inside a skipped function,
or older in the [[Von Neumann instruction sequence]],
but are actually more speculative, as in less likely to be executed.
However, it is often too hard to track this, so often discussions
will implicitly assume "less speculative" is "older".
---
Note that it is not always possible to determine the order of speculative threads or instructions.
E.g. one may fork loop bodies out of order, with no known order,
and later string them together as memory items iterated on by the loop are encountered.
However, arbitrarily imposing an order simplifies many speculative algorithms,
even at the cost of potential performance.
---
* See[[spawning versus forking a thread]].
Wednesday, February 09, 2011
Skipahead Multithreading
http://semipublic.comp-arch.net/wiki/SkMT
[[Skipahead multithreading (SkMT)]] is a form of [[speculative multithreading (SpMT)]]
characterized by "skipping ahead" at certain points in
[[non-speculative or less speculative versus more speculative|non-speculative or less speculative execution to more speculative execution]].
Typically these "certain points" in thecode are places
where there is a well characterized [[control independence or convergence]] point:
* the instruction after a CALL instruction
* end of loop
* later iterations of loop
* IF convergence
I, Andy Glew, coined the term [[SkMT]]
when it became evident that the term [[SpMT]],
which was itself coined by Antonio Gonzales and promoted by me,
was more generic.
I.e. you can imagine creating speculative threads
that do not really skip that far ahead,
but which, e.g. execute past a place where execution would bee blocked,
either an in-order blockage, or where an OOO window would be full.
See [[non-skipahead speculative multithreading]].
In much the same way, I had earlier used the term [[implicit multithreading (IMT)]],
and replaced it by [[speculative multithreading (SpMT)]],
which I am now (after, 10 years ago, 2000) specializing to [[skipahead multithreading (SkMT)]].
The term [[skipahead]] is intended to be contrasted with [[lookahead]],
a term which was once used to characterize all [[out-of-order (OOO)]] execution.
[[Skipahead multithreading (SkMT)]] is a form of [[speculative multithreading (SpMT)]]
characterized by "skipping ahead" at certain points in
[[non-speculative or less speculative versus more speculative|non-speculative or less speculative execution to more speculative execution]].
Typically these "certain points" in thecode are places
where there is a well characterized [[control independence or convergence]] point:
* the instruction after a CALL instruction
* end of loop
* later iterations of loop
* IF convergence
I, Andy Glew, coined the term [[SkMT]]
when it became evident that the term [[SpMT]],
which was itself coined by Antonio Gonzales and promoted by me,
was more generic.
I.e. you can imagine creating speculative threads
that do not really skip that far ahead,
but which, e.g. execute past a place where execution would bee blocked,
either an in-order blockage, or where an OOO window would be full.
See [[non-skipahead speculative multithreading]].
- Oooo.... I just created a new term: [[slip-ahead multithreading]].
It rather nicely encapsulates what I just described,
and is consistent with published project names such as [[slipstream]].
In much the same way, I had earlier used the term [[implicit multithreading (IMT)]],
and replaced it by [[speculative multithreading (SpMT)]],
which I am now (after, 10 years ago, 2000) specializing to [[skipahead multithreading (SkMT)]].
The term [[skipahead]] is intended to be contrasted with [[lookahead]],
a term which was once used to characterize all [[out-of-order (OOO)]] execution.
- Look-ahead processors.
Robert M. Keller, Princeton.
ACM Computing Surveys,
Vol 7, Issue 4, Dec 1975.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5118&rep=rep1&type=pdf
Sunday, February 06, 2011
Managing branch prediction history: copying short history versus pointing to large history
http://semipublic.comp-arch.net/wiki/Managing_branch_prediction_history:_copying_short_history_versus_pointing_to_large_history
When [[branch prediction history]] was short, 8-12 bits, and global,
then it was not unreasonable to manage the history by copying it.
E.g. in one simulator I actually arranged so that a branch [[uop]]
wrote back, as its result
* an indication of whether it was mispredicted or not
* the taken [[target IP]]
* the branch predictor history to be restored on a branch misprediction.
I.e. the branch prediction history was propagated, in this simulator, from the [[instruction fetch front end]]
across the scheduler to execution, and back again.
While simple, this involves a lot of unnecessary data movement - both for the history, but also for the [[target IP]].
Most machines of my acquaintance create a [[branch information table (BIT)]], holding information for branches in flight.
This avoids copying the history from the front end to execution and back again,
but nevertheless may involve making copies of the history.
Making copies of the history seems silly if, as in a TNT history, they differ only by 2 bits:
new_history := (old_history << 1) | new_branch_taken_or_not
But making copies seems to be required if we want to be able to restore to any mispredicted branch point, i.e. if we want to do [[instantaneous versus incremental branch misprediction repair]].
Making copies works well enough if the branch prediction history is small enough - 8 bits, etc.
But by the time we are talking about 16 bit histories and 32 or 64 bit IPs, we are talking about quite a few bits.
Furthermore, in the late 1990s and early 2000s branch predictors arose with hitherto unseen long histories,
such as Seznec's OGEHL predictor (with multiple history lengths 9, 2, 4, 8, 16, 32, 64, 128, ...).
Copying around a 128 bit history, even to a [[BIT]], is wasteful;
copying around the even larger 1000+ bit histories that have been proposed is even worse.
Hence the interest in pointing to a position in a branch prediction history,
rather than copying the entire history.
On a branch misprediction one would restore the pointer, rather than overwriting the history with a savedcopy.
This would be straightforward for a long [[TNT]] history, since only 1 bit depends on any branch.
You would simply keep a history of total length TL=PHL+BIF, the sum of predictor history length plus branches in flight.
On a misprediction you would restore the pointer in this circular buffer.
(Or equivalently shift the buffer- I suspect that shifting is too power hungry.)
This could scale to almost any length of history, potentially thousands of bits.
Unfortunately, modern [[stew]] histories are more complicated than [[TNT]] histories.
The [[branch IP]], or even both [[from IP]] and [[to IP]], may be [[hashed, e.g. XORed]] into the stew.
This means that several of the youngest bits in the history may change on every branch.
Simply restoring a pointer will not suffice.
TBD: explain stew management in more detail.
Simple strategy: constrain the stew to have only the N youngest bits affected by the most recent branch. Bits TL..N are unaffected by the most recent branch, except for shifting.
One can then keep a copy of the parts of the history affected by recent branches, the N youngest bits, and a pointer that locates the older bits.
= See Also =
* [[How to use a really long predictor history]]
When [[branch prediction history]] was short, 8-12 bits, and global,
then it was not unreasonable to manage the history by copying it.
E.g. in one simulator I actually arranged so that a branch [[uop]]
wrote back, as its result
* an indication of whether it was mispredicted or not
* the taken [[target IP]]
* the branch predictor history to be restored on a branch misprediction.
I.e. the branch prediction history was propagated, in this simulator, from the [[instruction fetch front end]]
across the scheduler to execution, and back again.
While simple, this involves a lot of unnecessary data movement - both for the history, but also for the [[target IP]].
Most machines of my acquaintance create a [[branch information table (BIT)]], holding information for branches in flight.
This avoids copying the history from the front end to execution and back again,
but nevertheless may involve making copies of the history.
- I confess an ulterior motive for copying the history and other branch information around: this naturally leads to the number of branches in flight scaling with the window size. Many early OOO designs were crippled by supported too few branches in flight.
Making copies of the history seems silly if, as in a TNT history, they differ only by 2 bits:
new_history := (old_history << 1) | new_branch_taken_or_not
- (Note: when shifting a branch history, we will often say h<
But making copies seems to be required if we want to be able to restore to any mispredicted branch point, i.e. if we want to do [[instantaneous versus incremental branch misprediction repair]].
Making copies works well enough if the branch prediction history is small enough - 8 bits, etc.
But by the time we are talking about 16 bit histories and 32 or 64 bit IPs, we are talking about quite a few bits.
Furthermore, in the late 1990s and early 2000s branch predictors arose with hitherto unseen long histories,
such as Seznec's OGEHL predictor (with multiple history lengths 9, 2, 4, 8, 16, 32, 64, 128, ...).
Copying around a 128 bit history, even to a [[BIT]], is wasteful;
copying around the even larger 1000+ bit histories that have been proposed is even worse.
Hence the interest in pointing to a position in a branch prediction history,
rather than copying the entire history.
On a branch misprediction one would restore the pointer, rather than overwriting the history with a savedcopy.
This would be straightforward for a long [[TNT]] history, since only 1 bit depends on any branch.
You would simply keep a history of total length TL=PHL+BIF, the sum of predictor history length plus branches in flight.
On a misprediction you would restore the pointer in this circular buffer.
(Or equivalently shift the buffer- I suspect that shifting is too power hungry.)
This could scale to almost any length of history, potentially thousands of bits.
Unfortunately, modern [[stew]] histories are more complicated than [[TNT]] histories.
The [[branch IP]], or even both [[from IP]] and [[to IP]], may be [[hashed, e.g. XORed]] into the stew.
This means that several of the youngest bits in the history may change on every branch.
Simply restoring a pointer will not suffice.
TBD: explain stew management in more detail.
Simple strategy: constrain the stew to have only the N youngest bits affected by the most recent branch. Bits TL..N are unaffected by the most recent branch, except for shifting.
One can then keep a copy of the parts of the history affected by recent branches, the N youngest bits, and a pointer that locates the older bits.
= See Also =
* [[How to use a really long predictor history]]
Branch Prediction Stew
{{Terminology Term}}
http://semipublic.comp-arch.net/wiki/Stew
The [[stew]] is a form of history used by certain branch predictors.
See, for example, US patent 7143273,
Method and apparatus for dynamic branch prediction utilizing multiple stew algorithms for indexing a global history,
Mile, Slade, and Jourdan,
filed March 31, 2003,
assignee Intel.
A simple [[branch predictor history]] might be a simple [[TNT]] history,
with 0s corresponding to non-taken and 1s corresponding to taken.
Such a simple TNT history cannot distinguish some convergeing paths,
and indirect branches.
US7143273
describes one embodiment of a stew as
stew = ((stew << 1)|new_bit ^ ip)
A stew formed in this way can distinguish converging paths such as ("if true" means a condition that evaluates as true, not an unconditional branch):
L1: if true got L2
L2: if true goto L99
L10: if true goto L11
L11: if true goto L
L: if ?? goto L99
However, it does not distinguish multiple branch targets and paths out of an indirect branch, such as
L1: Reg:= IL1; if true goto L2
L2: if true goto L99
L10: Reg:=IL2; if true goto L11
L11: if true goto L
L: if ?? goto [Reg]
IL1: ...
IL2: ...
It can be seen that mixing in arc information as well as node information remedies this situation,
and distinguishes different paths so long as the hashes do not collide:
stew <<= number_of_bits_to_discard
stew = hash( stew, from_IP, to_IP, taken/not_taken, ...)
Issue: how many bits to use? Which may vary as a function of the type of branch: e.g. a direct conditional branch
may not need as many to_ip bits to be hashed in
as a completely random indirect branch.
Similarly, indirect calls and returns may be handled separately.
(TBD-IP)
http://semipublic.comp-arch.net/wiki/Stew
The [[stew]] is a form of history used by certain branch predictors.
See, for example, US patent 7143273,
Method and apparatus for dynamic branch prediction utilizing multiple stew algorithms for indexing a global history,
Mile, Slade, and Jourdan,
filed March 31, 2003,
assignee Intel.
A simple [[branch predictor history]] might be a simple [[TNT]] history,
with 0s corresponding to non-taken and 1s corresponding to taken.
Such a simple TNT history cannot distinguish some convergeing paths,
and indirect branches.
US7143273
describes one embodiment of a stew as
stew = ((stew << 1)|new_bit ^ ip)
A stew formed in this way can distinguish converging paths such as ("if true" means a condition that evaluates as true, not an unconditional branch):
L1: if true got L2
L2: if true goto L99
L10: if true goto L11
L11: if true goto L
L: if ?? goto L99
However, it does not distinguish multiple branch targets and paths out of an indirect branch, such as
L1: Reg:= IL1; if true goto L2
L2: if true goto L99
L10: Reg:=IL2; if true goto L11
L11: if true goto L
L: if ?? goto [Reg]
IL1: ...
IL2: ...
It can be seen that mixing in arc information as well as node information remedies this situation,
and distinguishes different paths so long as the hashes do not collide:
stew <<= number_of_bits_to_discard
stew = hash( stew, from_IP, to_IP, taken/not_taken, ...)
Issue: how many bits to use? Which may vary as a function of the type of branch: e.g. a direct conditional branch
may not need as many to_ip bits to be hashed in
as a completely random indirect branch.
Similarly, indirect calls and returns may be handled separately.
(TBD-IP)
Monday, January 31, 2011
Slow :-(
Minor bitching: writing in the comp-arch wiki is so slow.
Hard to get big chunks of time.
Hard to write big chunks when I don't have big chunks of time.
But at least my present employer allows me to write this. And does not forbid me, like my past employer.
I wish that I could average 1 new page a day. Instead, I am averaging less than half a page a day, and probably less than 1 substantial page a week.
Hard to get big chunks of time.
Hard to write big chunks when I don't have big chunks of time.
But at least my present employer allows me to write this. And does not forbid me, like my past employer.
I wish that I could average 1 new page a day. Instead, I am averaging less than half a page a day, and probably less than 1 substantial page a week.
OOO_versus_Runahead_versus_Log-based_replay_for_runahead
http://semipublic.comp-arch.net/wiki/OOO_versus_Runahead_versus_Log-based_replay_for_runahead
In the era of Willamette I suffered a moral dilemma - or, rather, a dilemma of morale.
I had evangelized [[OOO execution]] with P6.
But I had been introduced to runahead.
And runahead execution seemed to be asymptotically as good as OOO execution,
as memory latencies got longer - i.e. as we entered the era of [[MLP (memory level parallelism)]], which I was then starting to evangelize.
OOO execution is ... well, I'll assume you know what OOO is, or can read about it [[OOO|elsewhere]].
= What Runahead Is ==
[[Runahead]] consists essentially of
* executing
* when an unpredictable, long-latency, event such as a cache miss occurs
** take a checkpoint
** mark the result invalid
* continue executing past the checkpoint in a speculative manner
** saving speculative values into registers
** saving speculative values into a store buffer, or similar [[memory speculation datastructure]]
* when the cache miss returns
** discard all speculative state, registers and memory
** restore from the checkpoint.
= Runahead and OOO are asymptotically equal =
Runahead is a comparatively simple action.
And, in some sense, it gets nearly all of the benefit of OOO.
I.e. as memory latencies increase to infinity and execution latencies becomeinfinitesimal by comparison,
runahead execution will approach OOO execution in performance.
Normally, barring funny effects, runahead will always be lower performance than OOO.
For the same size of instruction window.
But runahead is much cheaper in hardware, and can potentially runahead much farther than OOO for the same hardware cost.
Both runahead and OOO are limited by the [[memory speculation datastructure]];
but runahead need build no large physical register file, etc., save only for a number of RF checkpoints.
= [[log-based]] =
Confounded by OOO/run-ahead, I looked for something better than runahead in some asymptotic sense.
Hence [[log-based]] execution - specifically [[log-based verify re-execution]].
Although subsequently I applied [[log-based]] to [[speculative multithreading]],
at first I thought about it only wrt the same [[single sequencer microarchitecture]]
as OOO or runahead:
Imagine that you are executing in a runahead manner.
However, instead of re-executing all of the instructions after a cache miss returns and a checkpoint is restored,
instead you (1) record all of the results of runahead execution in a log,
and (2) you execute instructions out of the log.
This raises several questions:
Why would this be any faster than runahead?
Why would it be any "larger" than OOO or as large as runahead?
Why would it be as cheap as runahead?
Let;'s answer them out of order.
;Why would this be as cheap as runahead?
Well, if you had a dedicated log [[hardware datastructure]] it would not be.
However, the log is accessed sequentially during [[verify re-execution]].
Sequential access patterns can be easily prefetched.
therefore, you could put the log in slow memory - potentially in main memory.
you might need some fast hardware log to "start off" the verify re-execution,
sufficient to tolerate the latency to main memory.
Equivalently, you might manage cache replacement to ensure that the oldest entries in the log are not displaced from a cache of main memory,
as they normally would be in LRU.
;Why would it be any "larger" than OOO or as large as runahead?
As explained above, the log need not be a small size hardware datastructure. It could potentially scale in size as main memory.
;Why would this be any faster than runahead?
Two reasons.
First, [[verify re-execution]] is inherently more parallel than normal execution.
I like to explain this using repeatedly increment a register as an example:
r9 := load(cache misss)
INC r9
INC r9
...
INC r9
If INC is unit latency, then runhead re-execution would take N cycles to re-execute N such INCrements of a register.
However, in [[log-based verify re-execution]],
the example code above would be rewritten in the log as
r9 := load(cache misss)
assert(r9 = 1042)
INC r9 // assert(r9=1042); r9:= 1043
INC r9 // assert(r9=1043); r9:= 1044
INC r9 // assert(r9=1044); r9:= 1045
...
INC r9 // assert(r9=1042+N); r9:= 1042+N+1
i.e. the instructions rewritten for storage in the log,
and for [[verify re-execution]] out of the log, consist of nothing except moves of a cionstant to a register.
Rather than N cycles, these would take N/IF cycles, where IF is the instruction width.
Furthermore, there are many optimizations that can be applied to the log:
removing redundant asserts and redundant overwrites, etc.
In general, for a block of register based code,
[[log-based verify re-execution]] has one assert for every live-in,
and one constant to register move for every live-out.
Assuming the assertions are met.
(And if the assertions are not met, fall back to normal (re-)execution.
The second reason for log-based verify re-execution being faster is this:
Normal runahead re-execution is limited by cache associativity.
If you have N independent memory references that were cachemisses prefetched by the runahead speculative execution epoch,
they are normally independent, and all prefetched.
EXCEPT when they happen to collide in the cache, e.g. in the limited associativity cache.
In which case, another runahead/checkpoint/re-execution would begin.
Log-based verify re-execution suffers this not at all.
If a cache missing load is thrashed out of the cache,
its value is still present in the log,
and dependent instructions can still be executed - or, rather, verify re-executed.
You will need to pay the memory latency to fetch it and verify, but that can be overlapped.
= Conclusion =
Log-based verify re-execution, or`replay, for runahead
is asymptotically faster than ordinary runahead in two senses:
non-cache miss execution latency,
and cache thrashing.
Ultimately, the fashion or fad of runahead petered out.
Runahead did not replace OOO, although it caused much heartburn.
Runahead did not replace OOO because, although asymptotically better than OOO, we aren't at the asymptote.
Execution unit latencies are not 0, and cache misses infinite.
OOO handles both.
Also, runahead may consume more power than OOO. This is somewhat debatable:
OOO's hardware datastructures may waste power, e.g. leakage,
whereas runahead may consume static power.
Probably the biggest reason why runahead did not supplant OOO in the late 1990s and early 2000s is this:
runhead is only as good as OOO.
It doesn't do anything new.
OOO was an already established and well understood technology by the time runahead appeared on the scene.
Although runahead has putative benefits, they were not enough to warrant a switch-over.
Be this as it may, log-based verify re-execution is a technique that rose out of the [[Runahead versus OOO]] debate.
It is better than runahead in some asymptotic senses. And it has application to other areas, such as [[SpMT]].
= Hybrids =
Of course it is possible to create hybrids of OOO, runahead, and log-based.
For example, one need not record all instruction results in the log. One can re-execute that which is fast,
and only record in the log that which is slow.
Similarly, an OOO machine need not record all speculative results in the instruction window.
Onur Mutlu and others have proposed hybrids that fill an OOO instruction window, and then use runahead.
In the era of Willamette I suffered a moral dilemma - or, rather, a dilemma of morale.
I had evangelized [[OOO execution]] with P6.
But I had been introduced to runahead.
And runahead execution seemed to be asymptotically as good as OOO execution,
as memory latencies got longer - i.e. as we entered the era of [[MLP (memory level parallelism)]], which I was then starting to evangelize.
OOO execution is ... well, I'll assume you know what OOO is, or can read about it [[OOO|elsewhere]].
= What Runahead Is ==
[[Runahead]] consists essentially of
* executing
* when an unpredictable, long-latency, event such as a cache miss occurs
** take a checkpoint
** mark the result invalid
* continue executing past the checkpoint in a speculative manner
** saving speculative values into registers
** saving speculative values into a store buffer, or similar [[memory speculation datastructure]]
* when the cache miss returns
** discard all speculative state, registers and memory
** restore from the checkpoint.
= Runahead and OOO are asymptotically equal =
Runahead is a comparatively simple action.
And, in some sense, it gets nearly all of the benefit of OOO.
I.e. as memory latencies increase to infinity and execution latencies becomeinfinitesimal by comparison,
runahead execution will approach OOO execution in performance.
Normally, barring funny effects, runahead will always be lower performance than OOO.
For the same size of instruction window.
But runahead is much cheaper in hardware, and can potentially runahead much farther than OOO for the same hardware cost.
Both runahead and OOO are limited by the [[memory speculation datastructure]];
but runahead need build no large physical register file, etc., save only for a number of RF checkpoints.
= [[log-based]] =
Confounded by OOO/run-ahead, I looked for something better than runahead in some asymptotic sense.
Hence [[log-based]] execution - specifically [[log-based verify re-execution]].
Although subsequently I applied [[log-based]] to [[speculative multithreading]],
at first I thought about it only wrt the same [[single sequencer microarchitecture]]
as OOO or runahead:
Imagine that you are executing in a runahead manner.
However, instead of re-executing all of the instructions after a cache miss returns and a checkpoint is restored,
instead you (1) record all of the results of runahead execution in a log,
and (2) you execute instructions out of the log.
This raises several questions:
Why would this be any faster than runahead?
Why would it be any "larger" than OOO or as large as runahead?
Why would it be as cheap as runahead?
Let;'s answer them out of order.
;Why would this be as cheap as runahead?
Well, if you had a dedicated log [[hardware datastructure]] it would not be.
However, the log is accessed sequentially during [[verify re-execution]].
Sequential access patterns can be easily prefetched.
therefore, you could put the log in slow memory - potentially in main memory.
you might need some fast hardware log to "start off" the verify re-execution,
sufficient to tolerate the latency to main memory.
Equivalently, you might manage cache replacement to ensure that the oldest entries in the log are not displaced from a cache of main memory,
as they normally would be in LRU.
;Why would it be any "larger" than OOO or as large as runahead?
As explained above, the log need not be a small size hardware datastructure. It could potentially scale in size as main memory.
;Why would this be any faster than runahead?
Two reasons.
First, [[verify re-execution]] is inherently more parallel than normal execution.
I like to explain this using repeatedly increment a register as an example:
r9 := load(cache misss)
INC r9
INC r9
...
INC r9
If INC is unit latency, then runhead re-execution would take N cycles to re-execute N such INCrements of a register.
However, in [[log-based verify re-execution]],
the example code above would be rewritten in the log as
r9 := load(cache misss)
assert(r9 = 1042)
INC r9 // assert(r9=1042); r9:= 1043
INC r9 // assert(r9=1043); r9:= 1044
INC r9 // assert(r9=1044); r9:= 1045
...
INC r9 // assert(r9=1042+N); r9:= 1042+N+1
i.e. the instructions rewritten for storage in the log,
and for [[verify re-execution]] out of the log, consist of nothing except moves of a cionstant to a register.
Rather than N cycles, these would take N/IF cycles, where IF is the instruction width.
Furthermore, there are many optimizations that can be applied to the log:
removing redundant asserts and redundant overwrites, etc.
In general, for a block of register based code,
[[log-based verify re-execution]] has one assert for every live-in,
and one constant to register move for every live-out.
Assuming the assertions are met.
(And if the assertions are not met, fall back to normal (re-)execution.
The second reason for log-based verify re-execution being faster is this:
Normal runahead re-execution is limited by cache associativity.
If you have N independent memory references that were cachemisses prefetched by the runahead speculative execution epoch,
they are normally independent, and all prefetched.
EXCEPT when they happen to collide in the cache, e.g. in the limited associativity cache.
In which case, another runahead/checkpoint/re-execution would begin.
Log-based verify re-execution suffers this not at all.
If a cache missing load is thrashed out of the cache,
its value is still present in the log,
and dependent instructions can still be executed - or, rather, verify re-executed.
You will need to pay the memory latency to fetch it and verify, but that can be overlapped.
= Conclusion =
Log-based verify re-execution, or`replay, for runahead
is asymptotically faster than ordinary runahead in two senses:
non-cache miss execution latency,
and cache thrashing.
Ultimately, the fashion or fad of runahead petered out.
Runahead did not replace OOO, although it caused much heartburn.
Runahead did not replace OOO because, although asymptotically better than OOO, we aren't at the asymptote.
Execution unit latencies are not 0, and cache misses infinite.
OOO handles both.
Also, runahead may consume more power than OOO. This is somewhat debatable:
OOO's hardware datastructures may waste power, e.g. leakage,
whereas runahead may consume static power.
Probably the biggest reason why runahead did not supplant OOO in the late 1990s and early 2000s is this:
runhead is only as good as OOO.
It doesn't do anything new.
OOO was an already established and well understood technology by the time runahead appeared on the scene.
Although runahead has putative benefits, they were not enough to warrant a switch-over.
Be this as it may, log-based verify re-execution is a technique that rose out of the [[Runahead versus OOO]] debate.
It is better than runahead in some asymptotic senses. And it has application to other areas, such as [[SpMT]].
= Hybrids =
Of course it is possible to create hybrids of OOO, runahead, and log-based.
For example, one need not record all instruction results in the log. One can re-execute that which is fast,
and only record in the log that which is slow.
Similarly, an OOO machine need not record all speculative results in the instruction window.
Onur Mutlu and others have proposed hybrids that fill an OOO instruction window, and then use runahead.
Saturday, January 29, 2011
Cygwin X multidisplay bug
Today I figured out a problem that has been plaguing me on Cygwin for a year or two, since things broke in an update. (I probably figured it out before, but neglected to record or remember it.)
When I start up Xwin -multiwindow, using windows manipulated by MS Windows rather than a desktop in an MS Window window (try saying that fast), the initial xterm was always invisible.
Eventually I realized that if I maximized it from the MS Windows task bar, I could see it.
Apparently, this window was being created at location (0,0) in a bounding box for my multi-display configuration. (That's multiple physical displays, not multiple X displays.) However, location (0,0) was invisible - since my multi-display configuration has a big tall portrait mode window in the middle for reading PDFs, with flat landscape displays on either side for webpages. The portrait display rising above landscape displays.
By the way, it is actually +1+1 asthe default location, not +0+0. Minor difference.
I need to play around and see if I can find a guaranteed visible place.
Removing the geometry spec seems to work okay for me.
When I start up Xwin -multiwindow, using windows manipulated by MS Windows rather than a desktop in an MS Window window (try saying that fast), the initial xterm was always invisible.
Eventually I realized that if I maximized it from the MS Windows task bar, I could see it.
Apparently, this window was being created at location (0,0) in a bounding box for my multi-display configuration. (That's multiple physical displays, not multiple X displays.) However, location (0,0) was invisible - since my multi-display configuration has a big tall portrait mode window in the middle for reading PDFs, with flat landscape displays on either side for webpages. The portrait display rising above landscape displays.
By the way, it is actually +1+1 asthe default location, not +0+0. Minor difference.
I need to play around and see if I can find a guaranteed visible place.
Removing the geometry spec seems to work okay for me.
Subscribe to:
Posts (Atom)