Groups | Search | Server Info | Login | Register

Groups > comp.arch > #5753

Re: Single Thread Performance

Show all headers | View raw

On 2/6/2012 12:42 PM, nmm1@cam.ac.uk wrote:
> In article<bDVXq.20080$Sh7.12987@newsfe15.iad>,
> Robert Myers<rbmyersusa@gmail.com>  wrote:
>> On 2/6/2012 8:06 AM, nmm1@cam.ac.uk wrote:
>>> In article<ggtgp-3295E4.05551006022012@netnews.mchsi.com>,
>>> Brett Davis<ggtgp@yahoo.com>   wrote:
>>>>
>>>> Intel has built a 40 billion dollar a year company with 10 billion
>>>> in profits a year out of pursuing Single Thread Performance.
>>>
>>> Well, perhaps.  Sort of.
>>>
>>> Something that you miss is that even Intel has started to realise
>>> that it has hit an immovable obstacle, and to pursue multi-thread
>>> performance.  But the message has to travel from the ground to
>>> the brain and then back to where the action is, and Intel is as
>>> much a Diplodocus as IBM was in the 1970s.  Things don't happen
>>> fast.
>>
>> I'm fairly certain (in fact, absolutely certain) that there are people
>> who believe that the obstacle is not immovable.  Just how far it can be
>> moved and at what cost is another matter.
>
> There are people who believe that the earth is flat, too.  The
> fact that the obstacle has an exponential cliff and not a strictly
> asymptotic one doesn't mean that it's movable.
>
>
> Regards,
> Nick Maclaren.

A while back I corresponded witgh Uzi Vishkin, the PRAM guy, about the 
following:

I created a theoretical computation model I call the ILP-PRAM. 
Basically, a PRAM, with extensions to model what a really aggressive ILP 
processor could do.

I don't know if I have those notes any more - I may have thrown them 
away, as I did so much, when I changed jobs. (Wanting to avoid any 
suspicion of NDA violations, I left behind much that was really personal).

But basically I assumed that an ILP RAM had features such as
a) if a compiler could parallelize, it could parallelize
b) even if a compiler could not parallelize, it could parallelize using 
techniques familiar to those in this group.

And then I proved that an ILP-PRAM and a PRAM were equivalent in power. 
  At least to within polynomial.

In the theory classes I had just taken, proofs of equivalence typically 
involved emulation.   I suspect that you all can see how an implicitly 
ILP-PRAM can emulate an explicitly parallel PRAM, with equivalent 
efficiency, without even having to resort to an OOO tricks:

Basically, have the ILP-PRAM execute a program that simulates the PRAM. 
Something along the lines of

for each cycle
     for each processing element of the PRAM, p
          simulate_1_cycle(p)

Since by definition the ILP-PRAM can execute independent code, such as 
the loop body of the simulation, in parallel, then the body of the 
simulation loop executes "efficiently".

If you hypothesize that the ILP PRAM is less efficient than the PRAM, 
the inefficiency can only lie in the control.  i.e. the for loops. And 
classic PRAMs have essentially the same "loops" - the cycle explicly. 
The for each processor kloop, not really - assuming that the work has 
already been distributed.  But, the ILP-PRAM definition allows the same 
distribution.

I.e. an ILP-PRAM can simulate a PRAM "efficiently".  They are models of 
equivalent computational power. for this definition.

---

Now, I admit that this somewhat begs the question: a logically single 
threaded ILP-RAM is as "efficient" as an explicitly parallel PRAM, if 
you have an explicitly parallel program.

But I think it is interesting.

---

Perhaps somebody here can help me out: years ago, around the dawn of the 
web, I found a paper that talked about incorporating communications cost 
into theoretical models of parallel computation.  As I recall, they 
proved that with any realistic model of parallel computation, a similar 
equivalence in efficiency.

However, for the life of me I can't find the reference.

===

Anyway, theoretical equivalence aside: both parallel and serial 
computation run into the same walls.  However, computer architecture is 
a place where we worry about the constant multipliers for O(n) 
equivalent stuff.  I do not mean to say that explicit parallelism is not 
a good thing.  I just think that it is not as much of a savior as many 
would think.  Parallelism can solve bigger problems, but it won't solve 
fundamentally hard problems.

---

This being said, I keep thinking about "How does the world compute 
itself?" if not in parallel, with communication costs. I think that, 
unless quantum computation is fundamental (which may well be - but I 
think that you can define a quantum-ILP-RAM as well), and barring faster 
than light communication, that the fact that the world seems to compute 
itself must mean that the problems that it asking of itself are 
fundamentally solvable on whatever is the appropriate parallel model of 
computation and costs.

Which is the thing that causes me to wonder against Rob Myer's diatribes 
about physical modelling.

Unless... the universe has hidden dimensions that are used to increase 
the effective bandwidth of communication between the entities that 
constitute the world.

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Single Thread Performance "Unspecified" <partha@perfectvips.com> - 2012-02-04 21:54 +0530
  Re: Single Thread Performance Brett Davis <ggtgp@yahoo.com> - 2012-02-06 05:55 -0600
    Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-06 13:06 +0000
      Re: Single Thread Performance Robert Myers <rbmyersusa@gmail.com> - 2012-02-06 14:12 -0500
        Re: Single Thread Performance BGB <cr88192@hotmail.com> - 2012-02-06 13:36 -0700
          Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-06 20:47 +0000
            Re: Single Thread Performance BGB <cr88192@hotmail.com> - 2012-02-06 15:07 -0700
              Re: Single Thread Performance Brett Davis <ggtgp@yahoo.com> - 2012-02-06 16:32 -0600
                Re: Single Thread Performance Robert Wessel <robertwessel2@yahoo.com> - 2012-02-06 17:45 -0600
                Re: Single Thread Performance Brett Davis <ggtgp@yahoo.com> - 2012-02-07 06:01 -0600
                Re: Single Thread Performance BGB <cr88192@hotmail.com> - 2012-02-07 13:32 -0700
                Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-09 19:08 +0000
                Re: Single Thread Performance BGB <cr88192@hotmail.com> - 2012-02-10 08:56 -0700
        Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-06 20:42 +0000
          Re: Single Thread Performance Robert Myers <rbmyersusa@gmail.com> - 2012-02-06 19:36 -0500
          Re: Single Thread Performance "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-02-06 18:28 -0800
            Re: Single Thread Performance Robert Myers <rbmyersusa@gmail.com> - 2012-02-06 22:23 -0500
            Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-07 06:52 +0000
        Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-06 12:10 -0800
          Re: Single Thread Performance Thomas Womack <twomack@chiark.greenend.org.uk> - 2012-02-07 10:13 +0000
            Re: Single Thread Performance Brett Davis <ggtgp@yahoo.com> - 2012-02-20 23:58 -0600
          Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-07 17:33 +0000
            Re: Single Thread Performance nedbrek <nedbrek@yahoo.com> - 2012-02-15 08:10 -0500
    Re: Single Thread Performance Robert Myers <rbmyersusa@gmail.com> - 2012-02-06 14:17 -0500
      Re: Single Thread Performance del cecchi <delcecchi@gmail.com> - 2012-02-25 22:07 -0800
    Re: Single Thread Performance jgk@panix.com (Joe keane) - 2012-02-07 17:57 +0000
  Re: Single Thread Performance Quadibloc <jsavard@ecn.ab.ca> - 2012-02-05 13:13 -0800
  Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-05 21:35 -0800
    Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-07 17:38 +0000
      Re: Single Thread Performance Stephen Sprunk <stephen@sprunk.org> - 2012-02-07 14:54 -0600
        Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-07 21:33 +0000
          Re: Single Thread Performance Stephen Sprunk <stephen@sprunk.org> - 2012-02-07 23:13 -0600
            Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-08 18:54 +0000
              Re: Single Thread Performance Stephen Sprunk <stephen@sprunk.org> - 2012-02-08 15:17 -0600
                Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-09 08:13 +0100
                Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-09 17:08 +0000
                Re: Single Thread Performance Stephen Sprunk <stephen@sprunk.org> - 2012-02-09 16:01 -0600
              Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-09 07:56 +0100
                Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-09 17:18 +0000
          Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-08 10:17 +0100
        Re: Single Thread Performance Jon <jon@beniston.com> - 2012-02-08 05:32 -0800
      Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-07 16:00 -0800
        Re: Single Thread Performance timcaffrey@aol.com (Tim McCaffrey) - 2012-02-08 18:35 +0000
    Re: Single Thread Performance Partha <parthaspanda22@gmail.com> - 2012-02-10 11:32 -0800
      Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-10 20:31 +0000
        Re: Single Thread Performance "Unspecified" <partha@perfectvips.com> - 2012-02-11 02:12 +0530
          Re: Single Thread Performance nmm1@cam.ac.uk - 2012-02-10 21:04 +0000
          Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-10 16:43 -0800
            Re: Single Thread Performance "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-02-10 19:48 -0800
              Re: Single Thread Performance EricP <ThatWouldBeTelling@thevillage.com> - 2012-02-12 14:31 -0500
            Re: Single Thread Performance Stefan Monnier <monnier@iro.umontreal.ca> - 2012-02-12 21:50 -0500
              Re: Single Thread Performance "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-02-12 19:45 -0800
                Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-12 20:36 -0800
                Re: Single Thread Performance "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-02-13 06:46 -0800
                Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-13 08:58 -0800
                Re: Single Thread Performance "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-02-13 16:19 -0800
                Re: Single Thread Performance Rick Jones <rick.jones2@hp.com> - 2012-02-14 03:55 +0000
                Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-14 10:30 +0100
                Re: Single Thread Performance Andrew Reilly <areilly---@bigpond.net.au> - 2012-02-14 10:49 +0000
                Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-14 13:21 +0100
                Re: Single Thread Performance Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-02-14 13:11 -0800
                Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-14 09:29 -0800
                Re: Single Thread Performance EricP <ThatWouldBeTelling@thevillage.com> - 2012-02-14 12:40 -0500
                Re: Single Thread Performance EricP <ThatWouldBeTelling@thevillage.com> - 2012-02-14 16:12 -0500
                Re: Single Thread Performance Rick Jones <rick.jones2@hp.com> - 2012-02-14 21:14 +0000
                Re: Single Thread Performance Rick Jones <rick.jones2@hp.com> - 2012-02-14 21:16 +0000
                Re: Single Thread Performance Rick Jones <rick.jones2@hp.com> - 2012-02-14 21:09 +0000
                Re: Single Thread Performance MitchAlsup <MitchAlsup@aol.com> - 2012-02-14 09:26 -0800
                Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-15 08:44 +0100
                Re: Single Thread Performance "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-02-15 01:07 -0800
                Re: Single Thread Performance Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-02-14 10:16 +0100
  Re: Single Thread Performance Michael S <already5chosen@yahoo.com> - 2012-02-08 01:04 -0800

csiph-web