Re: multi-queue scheduler update

Re: multi-queue scheduler update

[Jesse Pollard]

Mark Hahn <hahn@coffee.psychology.mcmaster.ca>:
> 
> > >                            microseconds/yield
> > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > ------------   ---------         --------     ---------------
> > > 16               18.740            4.603         1.455
> > 
> > I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> 
> isn't the normal case (as in "The Right Case to optimize") 
> where there are close to zero runnable tasks?  what realistic/sane
> scenarios have very large numbers of spinning threads?  all server
> situations I can think of do not.  not volanomark -loopback, surely!

How about massively parallel compute jobs when synchronizing.

-------------------------------------------------------------------------
Jesse I Pollard, II
Email: pollard@navo.hpc.mil

Any opinions expressed are solely my own.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [Lse-tech] Re: multi-queue scheduler update

[Andi Kleen]

On Fri, Jan 19, 2001 at 01:26:16AM +0100, Andrea Arcangeli wrote:
> I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> scheduler with over 7 tasks in the runqueue (actually I'm not sure if the
> number was 7 but certainly it was under 10). So if you also use a O(1)
> scheduler too as I guess (since you have a chance to run fast on the lots of
> tasks running case) the most interesting thing is how you score with 2/4/8
> tasks in the runqueue (I think the tests on the O(1) scheduler patch was done
> at max on a 2-way SMP btw). (the argument for which Davide's patch wasn't
> included is that most machines have less than 4/5 tasks in the runqueue at the
> same time)

They seem to have tried that in a separate patch:
http://lse.sourceforge.net/scheduling/PrioScheduler.html

Very nice literate programming style btw @-)


-Andi 
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[John Clemens]

While I agree that this is probably only a win for very specialized tasks,
I'd be interested in seeing this patch implemented on a NUMA machine, with
one runqueue per node... anybody willing to try it? I don't have access to
one. How about from the Linux Scalability project at SGI? any comments?

john.c

-- 
John Clemens          http://www.deater.net/john
john@deater.net     ICQ: 7175925, IM: PianoManO8
      "I Hate Quotes" -- Samuel L. Clemens


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

multi-queue scheduler update

[Mike Kravetz]

I just posted an updated version of the multi-queue scheduler
for the 2.4.0 kernel.  This version also contains support for
realtime tasks.  The patch can be found at:

http://lse.sourceforge.net/scheduling/

Here are some very preliminary numbers from sched_test_yield
(which was previously posted to this (lse-tech) list by Bill
Hartner).  Tests were run on a system with 8 700 MHz Pentium
III processors.

                           microseconds/yield
# threads      2.2.16-22           2.4        2.4-multi-queue
------------   ---------         --------     ---------------
16               18.740            4.603         1.455
32               17.702            5.134         1.456
64               23.300            5.586         1.466
128              47.273           18.812         1.480
256             105.701           71.147         1.517
512               FRC            143.500         1.661
1024              FRC            196.425         6.166
2048              FRC              FRC          23.291
4096              FRC              FRC          47.117

*FRC = failed to reach confidence level

-- 
Mike Kravetz                                 mkravetz@sequent.com
IBM Linux Technology Center
15450 SW Koll Parkway
Beaverton, OR 97006-6063                     (503)578-3494
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Andrea Arcangeli]

On Thu, Jan 18, 2001 at 03:53:11PM -0800, Mike Kravetz wrote:
> Here are some very preliminary numbers from sched_test_yield
> (which was previously posted to this (lse-tech) list by Bill
> Hartner).  Tests were run on a system with 8 700 MHz Pentium
> III processors.
> 
>                            microseconds/yield
> # threads      2.2.16-22           2.4        2.4-multi-queue
> ------------   ---------         --------     ---------------
> 16               18.740            4.603         1.455

I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
scheduler with over 7 tasks in the runqueue (actually I'm not sure if the
number was 7 but certainly it was under 10). So if you also use a O(1)
scheduler too as I guess (since you have a chance to run fast on the lots of
tasks running case) the most interesting thing is how you score with 2/4/8
tasks in the runqueue (I think the tests on the O(1) scheduler patch was done
at max on a 2-way SMP btw). (the argument for which Davide's patch wasn't
included is that most machines have less than 4/5 tasks in the runqueue at the
same time)

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Mark Hahn]

> >                            microseconds/yield
> > # threads      2.2.16-22           2.4        2.4-multi-queue
> > ------------   ---------         --------     ---------------
> > 16               18.740            4.603         1.455
> 
> I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)

isn't the normal case (as in "The Right Case to optimize") 
where there are close to zero runnable tasks?  what realistic/sane
scenarios have very large numbers of spinning threads?  all server
situations I can think of do not.  not volanomark -loopback, surely!

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Andi Kleen]

On Thu, Jan 18, 2001 at 08:00:16PM -0500, Mark Hahn wrote:
> > >                            microseconds/yield
> > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > ------------   ---------         --------     ---------------
> > > 16               18.740            4.603         1.455
> > 
> > I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> 
> isn't the normal case (as in "The Right Case to optimize") 
> where there are close to zero runnable tasks?  what realistic/sane
> scenarios have very large numbers of spinning threads?  all server
> situations I can think of do not.  not volanomark -loopback, surely!

I think the main point of Mike's patch is decreasing locking and cache line
bouncing overhead of multi cpu scheduling, not optimizing lots of runnable tasks.


-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Mike Kravetz]

On Fri, Jan 19, 2001 at 02:08:52AM +0100, Andi Kleen wrote:
> On Thu, Jan 18, 2001 at 08:00:16PM -0500, Mark Hahn wrote:
> > > >                            microseconds/yield
> > > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > > ------------   ---------         --------     ---------------
> > > > 16               18.740            4.603         1.455
> > > 
> > > I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> > 
> > isn't the normal case (as in "The Right Case to optimize") 
> > where there are close to zero runnable tasks?  what realistic/sane
> > scenarios have very large numbers of spinning threads?  all server
> > situations I can think of do not.  not volanomark -loopback, surely!
> 
> I think the main point of Mike's patch is decreasing locking and cache line
> bouncing overhead of multi cpu scheduling, not optimizing lots of runnable tasks.
> 
> 
> -Andi

Andi is correct.  Although the results I posted may seem to indicate
we are concentrating on high thread counts, this is really secondary
to reducing lock contention within the scheduler.  A co-worker down
the hall just ran pgbench (a postgresql db) benchmark and saw
contention on the runqueue lock at 57%.  Now, I know nothing about this
benchmark, but it will be interesting to see what happens after
applying my patch.

-- 
Mike Kravetz                                 mkravetz@sequent.com
IBM Linux Technology Center
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Davide Libenzi]

On Thursday 18 January 2001 17:33, Mike Kravetz wrote:
> On Fri, Jan 19, 2001 at 02:08:52AM +0100, Andi Kleen wrote:
> > On Thu, Jan 18, 2001 at 08:00:16PM -0500, Mark Hahn wrote:
> > > > >                            microseconds/yield
> > > > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > > > ------------   ---------         --------     ---------------
> > > > > 16               18.740            4.603         1.455
> > > >
> > > > I remeber the O(1) scheduler from Davide Libenzi was beating the
> > > > mainline O(N)
> > >
> > > isn't the normal case (as in "The Right Case to optimize")
> > > where there are close to zero runnable tasks?  what realistic/sane
> > > scenarios have very large numbers of spinning threads?  all server
> > > situations I can think of do not.  not volanomark -loopback, surely!
> >
> > I think the main point of Mike's patch is decreasing locking and cache
> > line bouncing overhead of multi cpu scheduling, not optimizing lots of
> > runnable tasks.
> >
> >
> > -Andi
>
> Andi is correct.  Although the results I posted may seem to indicate
> we are concentrating on high thread counts, this is really secondary
> to reducing lock contention within the scheduler.  A co-worker down
> the hall just ran pgbench (a postgresql db) benchmark and saw
> contention on the runqueue lock at 57%.  Now, I know nothing about this
> benchmark, but it will be interesting to see what happens after
> applying my patch.

Yep, the patch work in a different way and if these are the numbers it seems 
to be interesting.
Could You post results for a fewer number of tasks ?
I mean what is the performance loss for 1,2,..,5 tasks ?

To test You can use lmbench ( I don't remember the link ) and I should have 
the program I've used to test my patch somewhere.


- Davide
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Andrea Arcangeli]

On Thu, Jan 18, 2001 at 08:00:16PM -0500, Mark Hahn wrote:
> > >                            microseconds/yield
> > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > ------------   ---------         --------     ---------------
> > > 16               18.740            4.603         1.455
> > 
> > I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> 
> isn't the normal case (as in "The Right Case to optimize") 
> where there are close to zero runnable tasks?  what realistic/sane
> scenarios have very large numbers of spinning threads?  all server
> situations I can think of do not.  not volanomark -loopback, surely!

This is why the numbers with 2/4/8 threads in the runqueue are the most
interesting ones 8)

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Andi Kleen]

On Fri, Jan 19, 2001 at 02:35:02AM +0100, Andrea Arcangeli wrote:
> On Thu, Jan 18, 2001 at 08:00:16PM -0500, Mark Hahn wrote:
> > > >                            microseconds/yield
> > > > # threads      2.2.16-22           2.4        2.4-multi-queue
> > > > ------------   ---------         --------     ---------------
> > > > 16               18.740            4.603         1.455
> > > 
> > > I remeber the O(1) scheduler from Davide Libenzi was beating the mainline O(N)
> > 
> > isn't the normal case (as in "The Right Case to optimize") 
> > where there are close to zero runnable tasks?  what realistic/sane
> > scenarios have very large numbers of spinning threads?  all server
> > situations I can think of do not.  not volanomark -loopback, surely!
> 
> This is why the numbers with 2/4/8 threads in the runqueue are the most
> interesting ones 8)

With Arjan's patch to use prefetching for the runqueue scan the numbers
will be likely different [at least on cpus that can benefit from prefetching
like p2+ or athlon] 

-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Mike Kravetz]

As promised, here are some numbers for low thread counts from the
benchmark Andrew and Davide provided.  I ran the benchmark for
1,2,4 and 8 threads.  I ran the test 5 times for each thread count
and used 60 seconds as the measure time in each case.

2.4.0
-----
1               1785408         1785408         0               0.000000
1               1786130         1786130         0               0.000000
1               1786156         1786156         0               0.000000
1               1781575         1781575         0               0.000000
1               1780079         1780079         0               0.000000
2               1873405         936702          0               0.000000
2               2006473         1003236         0               0.000001
2               1953842         976921          0               0.000004
2               1951338         975669          0               0.000000
2               1887887         943943          0               0.000004
4               1936350         484087          0               0.000055
4               1814430         453607          0               0.000087
4               1972681         493170          0               0.000055
4               1951748         487937          0               0.000206
4               1862182         465545          0               0.000283
8               2917216         364652          0               0.000008
8               2655834         331979          0               0.000018
8               3026734         378341          0               0.000005
8               3010204         376275          0               0.000004
8               2569647         321205          0               0.000014

2.4.0-multi-queue
-----------------
1               1295498         1295498         0               0.000000
1               1295011         1295011         0               0.000000
1               1296768         1296768         0               0.000000
1               1296053         1296053         0               0.000000
1               1296472         1296472         0               0.000000
2               1999043         999521          0               0.000000
2               1410636         705318          0               0.000000
2               1414476         707238          0               0.000000
2               2014664         1007332         0               0.000001
2               1414509         707254          0               0.000000
4               2046182         511545          0               0.000232
4               2101535         525383          0               0.000115
4               2094828         523707          0               0.000155
4               2097406         524351          0               0.000144
4               2057331         514332          0               0.000132
8               3795829         474478          0               0.000185
8               4058329         507291          0               0.001871
8               3845934         480741          0               0.000248
8               3715243         464405          0               0.000084
8               3777303         472162          0               0.000194

As expected the single thread numbers for the multi-queue scheduler
are not as good as those of the existing scheduler.  However, at 2
threads it is getting pretty close and from 4 threads up, the
multi-queue scheduler does better.

In this multi-queue implementation, the amount of overhead is
related to the number of processors in the system.  Therefore,
I would expect the numbers to 'be better' for low thread counts
on systems with lower (<8) processor counts.  It would be
interesting to see if the point at which the multi-queue does
better stays at aprox CPUs/2 as we change system configurations.
Hopefully we will have some more extensive benchmark results in
the not too distant future.  Until then, we'll be looking into
optimizations to help out the multi-queue scheduler at low
thread counts.

-- 
Mike Kravetz                                 mkravetz@sequent.com
IBM Linux Technology Center
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: multi-queue scheduler update

[Gerhard Mack]

What affect does this scheduler have on 1 - 5 tasks??

	Gerhard


On Thu, 18 Jan 2001, Mike Kravetz wrote:

> I just posted an updated version of the multi-queue scheduler
> for the 2.4.0 kernel.  This version also contains support for
> realtime tasks.  The patch can be found at:
> 
> http://lse.sourceforge.net/scheduling/
> 
> Here are some very preliminary numbers from sched_test_yield
> (which was previously posted to this (lse-tech) list by Bill
> Hartner).  Tests were run on a system with 8 700 MHz Pentium
> III processors.
> 
>                            microseconds/yield
> # threads      2.2.16-22           2.4        2.4-multi-queue
> ------------   ---------         --------     ---------------
> 16               18.740            4.603         1.455
> 32               17.702            5.134         1.456
> 64               23.300            5.586         1.466
> 128              47.273           18.812         1.480
> 256             105.701           71.147         1.517
> 512               FRC            143.500         1.661
> 1024              FRC            196.425         6.166
> 2048              FRC              FRC          23.291
> 4096              FRC              FRC          47.117
> 
> *FRC = failed to reach confidence level
> 
> -- 
> Mike Kravetz                                 mkravetz@sequent.com
> IBM Linux Technology Center
> 15450 SW Koll Parkway
> Beaverton, OR 97006-6063                     (503)578-3494
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> Please read the FAQ at http://www.tux.org/lkml/
> 

--
Gerhard Mack

gmack@innerfire.net

<>< As a computer I find your faith in technology amusing.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/