Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #1620 > unrolled thread

Re: Why is complex lea slow?

Back to article view | Back to comp.arch

Contents

  Re: Why is complex lea slow? "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-05-16 11:02 -0700
    Re: Why is complex lea slow? MitchAlsup <MitchAlsup@aol.com> - 2011-05-16 22:01 -0700
      Re: Why is complex lea slow? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-16 22:50 -0700
        Re: Why is complex lea slow? Piotr Wyderski <peter.pan@neverland.mil> - 2011-05-17 14:42 +0200
          Re: Why is complex lea slow? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-17 08:17 -0700

#1620 — Re: Why is complex lea slow?

On Monday, May 16, 2011 5:43:20 AM UTC-4, Piotr Wyderski wrote:
> W dniu 2011-05-13 15:00, Quadibloc pisze:
> 
> > So Sandy Bridge could well have a fundamentally lower cycle time -
> > that is, a cycle which is equal to fewer gate delays, so that many
> > instructions have higher latencies
> 
> It would be credible in case of e.g. multiplies, but lea is
> composed of two simple additions + a very limited shift
> doable with an ultra-simple mux.

Adding three gate delays (how much would a carry save adder 
and small shift cost?) to a 14 gate delay cycle is a 20% 
cycle time penalty (I do not know how fast SandyBridge's 
cycle is, but even two added gate delays on a 20 gate delay 
cycle would be a significant penalty, it seems to me).  As 
Mitch Alsup indicated, if more than one cycle would be 
required, the next best latency might be three cycles.

By the way, do the high performance processors take 
advantage of the common use of immediate shift amounts to 
warm-up the shifter?  (ISTR reading that some Itanium 
processor had different latency for immediate shifts versus 
register-based shifts.)  Early warm-up for register-based 
shifts might be possible by early operand read (and storing 
the register operand as an immediate in the instruction 
payload) and very limited width pipelining/forwarding 
optimization (only requiring the six LSbits which would 
usually be available early [rotate and right shift being 
possible exceptions]).

[toc] | [next] | [standalone]

#1625

On May 16, 1:02 pm, "Paul A. Clayton" <paaronclay...@gmail.com> wrote:
> On Monday, May 16, 2011 5:43:20 AM UTC-4, Piotr Wyderski wrote:
> > W dniu 2011-05-13 15:00, Quadibloc pisze:
>
> > > So Sandy Bridge could well have a fundamentally lower cycle time -
> > > that is, a cycle which is equal to fewer gate delays, so that many
> > > instructions have higher latencies
>
> > It would be credible in case of e.g. multiplies, but lea is
> > composed of two simple additions + a very limited shift
> > doable with an ultra-simple mux.
>
> Adding three gate delays (how much would a carry save adder
> and small shift cost?) to a 14 gate delay cycle is a 20%
> cycle time penalty (I do not know how fast SandyBridge's
> cycle is, but even two added gate delays on a 20 gate delay
> cycle would be a significant penalty, it seems to me).

A "good" 64-bit adder/ALU will have 11-gates of delay
Making that adder do 3-input adds is 2 more gate dalays (13 total).

> By the way, do the high performance processors take
> advantage of the common use of immediate shift amounts to
> warm-up the shifter?

I never did, the data-path gets setup to deal with the latest data
arrival (non-constant shifts), so the mux doing the choosing is placed
somewhat late in the path congruent to the arrival of data. At best,
instruction decode logic can get the constant to the shifter, but any
timing of the shifter (dynamic logic, latches, output drivers...) will
be timed for the dynamic <late> data.


>  (ISTR reading that some Itanium
> processor had different latency for immediate shifts versus
> register-based shifts.)  Early warm-up for register-based
> shifts might be possible by early operand read (and storing
> the register operand as an immediate in the instruction
> payload)

It is my opinion that you are chasing timing ghosts, and that you will
make more forward progress, faster, by consentrating on the hard (i.e.
late) stuff rather than trying to eak out a gat delay on the easy
stuff.

Mitch

[toc] | [prev] | [next] | [standalone]

#1626

On 5/16/2011 10:01 PM, MitchAlsup wrote:
> On May 16, 1:02 pm, "Paul A. Clayton"<paaronclay...@gmail.com>  wrote:

>> By the way, do the high performance processors take
>> advantage of the common use of immediate shift amounts to
>> warm-up the shifter?
>
> I never did, the data-path gets setup to deal with the latest data
> arrival (non-constant shifts), so the mux doing the choosing is placed
> somewhat late in the path congruent to the arrival of data. At best,
> instruction decode logic can get the constant to the shifter, but any
> timing of the shifter (dynamic logic, latches, output drivers...) will
> be timed for the dynamic<late>  data.

I agree with Mitch, I have never seen immediate shift count get 
optimized for.


>>   (ISTR reading that some Itanium
>> processor had different latency for immediate shifts versus
>> register-based shifts.)  Early warm-up for register-based
>> shifts might be possible by early operand read (and storing
>> the register operand as an immediate in the instruction
>> payload)
>
> It is my opinion that you are chasing timing ghosts, and that you will
> make more forward progress, faster, by consentrating on the hard (i.e.
> late) stuff rather than trying to eak out a gat delay on the easy
> stuff.

I won't go so far as Mitch, though: some of my research for the Ph.D. 
that I never completed at Wisconsin[*] was on taking advantage of 
inter-operand arrival time skew.  One operand arriving before the other. 
Immediate shift count would be an example.

However, I only really tried to take advantage of skews on the order of 
a cycle.  The best example was the [[Dynamic Instruction Rewriting]] or 
[[Flattening]] that I've talked about here before; other examples 
included skew in multiplier operands, preparing the Booth encodings 
and/or 3X, 5X, etc. products so that you could use higher radix 
multipliers.  (Usually the products.)

Taking advantage of skews on the order of immediate shift count would be 
difficult on a machine that only had a single shifter.   If shift 
immediate were 1 cycle, and shift variable were 2 cycles, then you would 
have a writeback port collision "hazard" (what do you call this), if 
your workload intermixed 1 and 2 cycle operations on the same pipeline.

(By the way, the difficulty/performance impact of intermixing operations 
of different latencies may explain the 3 cycle LEA discussed  in another 
thread.)

You could take advantage of immediate shiftcount to, for example, 
convert shift by 1 into an ADD - you may have more adders than shifters. 
  But that should already be done by the compiler.

If you had lots of EUs you could have multiple pipelines of different 
latencies.  Multiple shifters.

Heck, you could have two writeback ports for any single shifter, 1 or 2 
cycles.

But these all cost.

I must admit that this tyranny of pipeline latency frustrates me.  One 
of the things that first attracted me to OOO execution was the 
possibility of being able to take advantage of data dependent latencies. 
  But you can only really do this if you are not acgeiving higher 
throughput by pipelining.   In some ways, pipeling is a bandwidth 
optimization, while OOO is a latency optimization, and they conflict.

I've similarly been attracted to asynchronous logic - but the same 
problem occurs.  Asynchronous logic can take advantage of many data 
dependent timings - but when you pipeline the asynchronous logic, there 
is a lossage.  Short latency operations may get stuck behind long 
latency operations in the same asynchronous pipeline.  Q: what does 
asynchronous bypassing look like?

[toc] | [prev] | [next] | [standalone]

#1634

Andy "Krazy" Glew wrote:

> I must admit that this tyranny of pipeline latency frustrates me. One of
> the things that first attracted me to OOO execution was the possibility
> of being able to take advantage of data dependent latencies. But you can
> only really do this if you are not acgeiving higher throughput by
> pipelining.

Being a big fan of the dataflow approach, a question arises: does
it make sense to make an OOO engine in a purely dataflow manner?
Maybe decoding should be excluded, but I can imagine a blob which
execution spawns more blobs which finally get combined into the
final result.

     Best regards
     Piotr Wyderski

[toc] | [prev] | [next] | [standalone]

#1637

On 5/17/2011 5:42 AM, Piotr Wyderski wrote:
> Andy "Krazy" Glew wrote:
>
>> I must admit that this tyranny of pipeline latency frustrates me. One of
>> the things that first attracted me to OOO execution was the possibility
>> of being able to take advantage of data dependent latencies. But you can
>> only really do this if you are not acgeiving higher throughput by
>> pipelining.
>
> Being a big fan of the dataflow approach, a question arises: does
> it make sense to make an OOO engine in a purely dataflow manner?
> Maybe decoding should be excluded, but I can imagine a blob which
> execution spawns more blobs which finally get combined into the
> final result.

Welcome to the cult! Here, have a glass of kool-aid.

Modern OOO engines are dataflow - but they are a limited form of 
dataflow.  Every dataflow node gets executed once and only once - with 
the  possible exception of replay.

This isn't even really Dennis' static dataflow, where a node could be 
executed more than once, e.g. for iterations of a loop.  But in a funny 
way, Dennis' static  dataflow nodes were in-orderr - each node tended to 
produce results in iteration order - whereas when a loop is unrolled 
into the (dataflow) instruction window on a modern OOO machine, the 
iterations of an instruction can execute out-of-order.

But, certainly, modern OOO machines are not generating new  blobs. 
Unless you count branch prediction - which is really the in-order 
instruction fetch engine generating new dataflow nodes.  Or speculative 
multithreading.

There have been attempts to create more dataflow-like mechanisms.  E.g. 
I seem to remember Bob Wedig and Augustus Uht having a paper design 
where each scheduler entry could represent several iterations of a variable.

Also, Dick Wilmot (?) had his data surfer.   On the more academic side, 
Amir Roth has stuff like  this, although he tends to start less 
aggressive than dataflow.

I chose my advisor for my abandoned-when-my-daughter-was-born Ph.D. 
because he was  the only guy other than me who admitted that he was 
trying to build a dataflow machine.  I thought that DMT and SpMT would 
have been built by 2000, and that dataflow would be the step after 
speculative threading.  Instead, I got bogged down in details of how to 
build a large instruction window (hence my L1/L2 instruction window).

Now, if Mikko Lipasti et al are correct with the work recently discussed 
here, perhaps I should not have been so hasty.  I was assuming that the 
dataflow hardware is expensive, so you would want to build a really 
large amount of L2 instruction window, with a small amount of L1 
instruction window (actually, probably several). But Mikko almost has me 
persuaded that the cost equation haschanged, so that you want to leave 
the data in place, even in fairly complex circuit blocks.  Almost... it 
still seems to me that if you have large data, you might be better 
communicating it around a bypass network of a small number of ALUs, 
communicating small instructions rather than large data.

Ultrascalar, Wavescalar ... many of these folk may not appreciate me 
saying that they are similar to dataflow.  And some are only in a small way.

Most of my work has been based on implicitlt dataflow-izing existing 
code --- because I worked for existing companies.

I think that the best opportunities may arise if you shed this 
straitjacket, and figure out what a real dataflow instruction set looks 
like. Who are  the blobs that spawn more blobs?  Like I said, at the 
moment the dataflow nodes are generated by a non-dataflow instruction 
sequence.  Even plural.

At the very least, I think that we may need to have very, very, dynamic 
thread forking.  E.g. a thread fork where the number of threads to fork 
is dynamic.  Possibly even tree driven - fork for all non-null children. 
  This gets us into the dataflow nodes spawning instruction sequencers, 
which themselves spawn dataflow nodes.

Or you can get into the coarse grain dataflow world.  Instead of single 
instruction dataflow blobs, multi-instruction dataflow blobs.  But this 
is where the old dataflow machines went awry: they basically became 
coarse-grain dataflow, or fine grain multithreaded, and they said that 
they did not need OOO because they were getting lots of parallelism at 
the coarse grain of their threadlets.   Well, history says otherwise.

It seems to me that it should be possible to reconcile the instruction 
level dataflow of OOO, with a larger dataflow level.  In some ways, this 
is what I want my L2 scheduler instruction window to do.

---

Last words in this rant:  dataflow never really figured out how to 
handle memory.  They handle memory by making believe it doesn't exist: 
single use memory locations, etc.  Wrap a monad round it.

But memory seems to be fundamental.  We have bitcells, and they can 
change their value.

Perhaps we have reached a point where this is now reasonable:  single 
assignment, functional. Or maybe the real advance is garbage collection: 
  just blindly act as if you have infinte memory, and garbage collect 
the stuff no longer needed.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.arch

csiph-web