Quick question about hyper-threading

Quick question about hyper-threading

[Timothy Miller]

On a hyper-threaded CPU, it seems to me that there could be a lot of
cache-thrashing if the two processes running are completely unrelated.  On
the other hand, if one process has two threads, then they would benefit (or
hurt less) from the cache-sharing, because they share the same memory space.
Does the HT-aware scheduler attempt to take this into account by scheduling
two related threads to run simultaneously on the same CPU as often as
possible (unless you're in a multi-processor system and another CPU would
otherwise be idle)?

Re: Quick question about hyper-threading

[Robert Love]

On Sat, 2003-04-12 at 23:13, Timothy Miller wrote:
> On a hyper-threaded CPU, it seems to me that there could be a lot of
> cache-thrashing if the two processes running are completely unrelated.  On
> the other hand, if one process has two threads, then they would benefit (or
> hurt less) from the cache-sharing, because they share the same memory space.
> Does the HT-aware scheduler attempt to take this into account by scheduling
> two related threads to run simultaneously on the same CPU as often as
> possible (unless you're in a multi-processor system and another CPU would
> otherwise be idle)?


No, the current scheduler (HT or stock 2.5) does not do this.

Your theories are correct.  It would be interesting to try this and see.

It is nontrivial to do the ->mm checks in the scheduler though -
certainly they cannot be done easily (if at all) in constant-time (i.e.,
it won't be O(1)).

	Robert Love

Re: Quick question about hyper-threading

[Tony 'Nicoya' Mantler]

In article <20030413041007$6d72@gated-at.bofh.it>, Robert Love <rml@tech9.net> 
wrote:

: On Sat, 2003-04-12 at 23:13, Timothy Miller wrote:
[...]
: > Does the HT-aware scheduler attempt to take this into account by scheduling
: > two related threads to run simultaneously on the same CPU as often as
: > possible (unless you're in a multi-processor system and another CPU would
: > otherwise be idle)?
: 
: 
: No, the current scheduler (HT or stock 2.5) does not do this.
: 
: Your theories are correct.  It would be interesting to try this and see.
: 
: It is nontrivial to do the ->mm checks in the scheduler though -
: certainly they cannot be done easily (if at all) in constant-time (i.e.,
: it won't be O(1)).
[...]

Perhaps the same effect could be obtained by preferentially scheduling processes 
to execute on the "node" (a node being a single cpu in an SMP system, or an HT 
virtual CPU pair, or a NUMA node) that they were last running on.

I think the ideal semantics would probably be something along the lines of:

 - a newly fork()ed thread executes on the same node as the creating thread
 - calling exec() sets a "feel free to shuffle me elsewhere" flag
 - threads are otherwise only shuffled to other nodes when a certain load ratio 
is exceeded (current-node:idle-node)

Unfortunatley the whole idea would seem to fall apart in the case of a 
fast-spawning thread pool type load. Perhaps there's a way to handle that 
automatically, or perhaps it would best be left as a scheduler tunable, I don't 
know.

I seem to recall SGI found great benefit in writing the scheduler in IRIX to 
work somewhat like this, though the loads on most SGI machines tend to be slow 
spawning, long running and big memory - the textbook case for reduced node 
shuffling. Linux would tend to have a much greater variety of load profiles, 
some of which would be less pleasantly affected.


Cheers - Tony 'Nicoya' Mantler :)

-- 
Tony "Nicoya" Mantler - Renaissance Nerd Extraordinaire - nicoya@apia.dhs.org
Winnipeg, Manitoba, Canada           --           http://nicoya.feline.pp.se/

Re: Quick question about hyper-threading

[Chuck Ebbert]

Rovert Love wrote:


> No, the current scheduler (HT or stock 2.5) does not do
> this.
>
> Your theories are correct.  It would be interesting to try
> this and see.
>
> It is nontrivial to do the ->mm checks in the scheduler though -
> certainly they cannot be done easily (if at all) in constant-time
> (i.e., it won't be O(1)).


  Is the scheduler even the right place to do that?

  I was thinking maybe the task_struct could use a cpus_desired
field -- then other parts of the system could give the scheduler hints
about which CPU to schedule a task on.

  
--
 Chuck

Re: Quick question about hyper-threading

[Martin J. Bligh]

> Perhaps the same effect could be obtained by preferentially scheduling 
> processes to execute on the "node" (a node being a single cpu in an SMP 
> system, or an HT virtual CPU pair, or a NUMA node) that they were last 
> running on.

We do that already. In fact, they always do that unless they're explicitly
migrated (in both NUMA and SMP cases) by the rebalancer.

> I think the ideal semantics would probably be something along the lines of:
> 
>  - a newly fork()ed thread executes on the same node as the creating thread
>  - calling exec() sets a "feel free to shuffle me elsewhere" flag
>  - threads are otherwise only shuffled to other nodes when a certain load ratio 
> is exceeded (current-node:idle-node)

Read the code. It does pretty much exactly this already ;-)
Especially look at sched_balance_exec(), and balance_node()

> Unfortunatley the whole idea would seem to fall apart in the case of a 
> fast-spawning thread pool type load. Perhaps there's a way to handle that 
> automatically, or perhaps it would best be left as a scheduler tunable, 
> I don't know.

It does, kind of ... in fact they all stay on the same runqueue. We need
to train the numa rebalancer to move multiple tasks in the case of heavy
imbalances, but it needs some care to avoid migrating short load spikes.
Moving from nr_running snapshots to load averages will probably fix it.

> I seem to recall SGI found great benefit in writing the scheduler in IRIX to 
> work somewhat like this, though the loads on most SGI machines tend to be slow 
> spawning, long running and big memory - the textbook case for reduced node 
> shuffling. Linux would tend to have a much greater variety of load profiles, 
> some of which would be less pleasantly affected.

Right - that's why it's hard ;-) Fixing any one case is easy ... fixing
all of them simultaneously is extremely difficult ;-)

M.