Groups | Search | Server Info | Login | Register

Groups > comp.arch > #5948

Re: Single Thread Performance

Message-ID <4F3B75C3.40708@SPAM.comp-arch.net> (permalink)
Date 2012-02-15 01:07 -0800
From "Andy (Super) Glew" <andy@SPAM.comp-arch.net>
Organization comp-arch.net
Newsgroups comp.arch
Subject Re: Single Thread Performance
References (9 earlier) <4F392235.1020804@SPAM.comp-arch.net> <16314332.739.1329152301273.JavaMail.geo-discussion-forums@ynnk21> <ae37e65b-43ea-42b6-80cf-d7ba5598bbdc@j14g2000vba.googlegroups.com> <21210493.750.1329240371457.JavaMail.geo-discussion-forums@ynt13> <6c4s09-g6d1.ln1@ntp6.tmsw.no>

Show all headers | View raw

On 2/14/2012 11:44 PM, Terje Mathisen wrote:
> MitchAlsup wrote:
>> In particular, if one knows how many CPUs are contending for entries
>> in a run queue, one can access different portions fo the run queue
>> and end up interference free. So from the above example: The first
>> access is<basically> thrown away detecting interference in the cache
>> (avoiding the latency of the ARU). When interference has been
>> detected, the CPU changes mode and the nest ASF prolog is done in a
>> "slow and methodological" way directing its lock requests to the ARU.
>> The third trip thruogh the logic remains in the "S&M" mode, but this
>> time the SW takes the conflict number and marches down the run queue
>> to an element that will not be under contention. So on the 3rd pass
>> all 17 processors grab all 17 entries from the queue conflict free.
>> Presto O(3) time.
>
> Mitch, how does this compare with an XADD-based approach?
>
> I.e. all 17 cpus tries to do a fetch&add on the queue index, one of them
> wins immediately, the other 16 will do a hw retry, another one succeeds
> etc.
>
> I guess the total number of bus attempts/transactions would be
> 17+16+15..., i.e. O(n^2) instead of O(3)?

(0) Yes, that O(N^2) pattern is what happens when you blindly implement 
any test-and-set. Including XADD.

(1) However, Alan Kagi showed that by adding delays, and/or queues in 
the lock controller, you can make it O(n) - 1 request per winner.

Alain's work descended from the QOLB, Queue on Lock Bit, work.  But the 
key is, those queues don't need to be architectural - you can just do it 
in the lock controller.

(2) For extra credit, you can imagine a fetch-and-op combining style 
thing, making it O(1) in cost.

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