A new spinlock for multicore (>16) platform

A new spinlock for multicore (>16) platform

[Shi-Wu, Lo（Gmail）]

Dear Linux Contributors,
I am a Linux enthusiast from Taiwan, and I hope to contribute to the
Linux kernel. We have developed a new spinlock method that has been
validated on AMD 64-core and AMD 32-core processors. Compared to
previous methods, this new method is optimized in the following areas:

Motivation and Approaches:
1. As the number of cores increases, there is a need for more refined
optimization of the data transmission paths between cores.
2. Data transmission usually involves lock-unlock wrapping.
3. Performance improvement can be achieved using a shortest path
approximation algorithm.
   A detailed introduction to this method can be found in the following paper:
https://www.usenix.org/conference/osdi23/presentation/lo

Our laboratory is currently developing a system that can apply the
same optimization strategy to all multi-core processors. Below is our
plan.

The New Method and Its Compatibility with qspinlock:
1. The default algorithm in the Linux kernel remains qspinlock.
2. A new file is created in /proc/routing_path, where a shortest path
can be input, for example:
sudo echo 1,2,3,4,16,17,18,19,5,6,7,8,11,12,13,14 > /proc/routing_path
3. After inputting the shortest path, the kernel switches to using the
RON algorithm.

Expected Outcomes:
According to our measurements on AMD 32-core and AMD 64-core
processors, Google LevelDB can achieve a 3-4% speed improvement.

Comparison with Previous NUMA-aware algorithms:
Compared to NUMA-aware results, since such systems may contain more
than two processors, the communication cost between processors is much
higher than the communication cost between cores (within the same
processor). Our method focuses on multiple cores within a single
processor, making it multicore-aware. If a NUMA-aware algorithm is
used in a multicore environment, it is not as effective as a
multicore-aware algorithm. (Please refer to the paper,
https://www.usenix.org/conference/osdi23/presentation/lo)

Assistance Needed:
I would like to understand if the Linux kernel community is interested
in this new spinlock method. As a teacher, I cannot complete all the
work by myself. Is anyone willing to collaborate with me on this
project?

Sorry to bother you:
I apologize for taking up so much of your time with this letter.
Although I am quite old, this is the first time I feel that my
research results are good enough to contribute to the Linux community.
I have read the relevant documentation, and it made me realize that my
time and abilities are insufficient to write the high-quality code
required by the Linux community. Therefore, I ask for your guidance.

All the best to you all

shiwu

Re: A new spinlock for multicore (>16) platform

[Bagas Sanjaya]

[-- Attachment #1: Type: text/plain, Size: 3042 bytes --]

On Mon, Jul 15, 2024 at 01:07:40AM +0800, Shi-Wu, Lo（Gmail） wrote:
> Dear Linux Contributors,
> I am a Linux enthusiast from Taiwan, and I hope to contribute to the
> Linux kernel. We have developed a new spinlock method that has been
> validated on AMD 64-core and AMD 32-core processors. Compared to
> previous methods, this new method is optimized in the following areas:
> 
> Motivation and Approaches:
> 1. As the number of cores increases, there is a need for more refined
> optimization of the data transmission paths between cores.
> 2. Data transmission usually involves lock-unlock wrapping.
> 3. Performance improvement can be achieved using a shortest path
> approximation algorithm.
>    A detailed introduction to this method can be found in the following paper:
> https://www.usenix.org/conference/osdi23/presentation/lo
> 
> Our laboratory is currently developing a system that can apply the
> same optimization strategy to all multi-core processors. Below is our
> plan.
> 
> The New Method and Its Compatibility with qspinlock:
> 1. The default algorithm in the Linux kernel remains qspinlock.
> 2. A new file is created in /proc/routing_path, where a shortest path
> can be input, for example:
> sudo echo 1,2,3,4,16,17,18,19,5,6,7,8,11,12,13,14 > /proc/routing_path
> 3. After inputting the shortest path, the kernel switches to using the
> RON algorithm.
> 
> Expected Outcomes:
> According to our measurements on AMD 32-core and AMD 64-core
> processors, Google LevelDB can achieve a 3-4% speed improvement.
> 
> Comparison with Previous NUMA-aware algorithms:
> Compared to NUMA-aware results, since such systems may contain more
> than two processors, the communication cost between processors is much
> higher than the communication cost between cores (within the same
> processor). Our method focuses on multiple cores within a single
> processor, making it multicore-aware. If a NUMA-aware algorithm is
> used in a multicore environment, it is not as effective as a
> multicore-aware algorithm. (Please refer to the paper,
> https://www.usenix.org/conference/osdi23/presentation/lo)
> 
> Assistance Needed:
> I would like to understand if the Linux kernel community is interested
> in this new spinlock method. As a teacher, I cannot complete all the
> work by myself. Is anyone willing to collaborate with me on this
> project?
> 
> Sorry to bother you:
> I apologize for taking up so much of your time with this letter.
> Although I am quite old, this is the first time I feel that my
> research results are good enough to contribute to the Linux community.
> I have read the relevant documentation, and it made me realize that my
> time and abilities are insufficient to write the high-quality code
> required by the Linux community. Therefore, I ask for your guidance.

I can't really say about this topic (as I'm not subject-matter expert here),
so Cc: relevant maintainers.

Thanks!

-- 
An old man doll... just what I always wanted! - Clara

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: A new spinlock for multicore (>16) platform

[Waiman Long]

On 7/14/24 19:45, Bagas Sanjaya wrote:
> On Mon, Jul 15, 2024 at 01:07:40AM +0800, Shi-Wu, Lo（Gmail） wrote:
>> Dear Linux Contributors,
>> I am a Linux enthusiast from Taiwan, and I hope to contribute to the
>> Linux kernel. We have developed a new spinlock method that has been
>> validated on AMD 64-core and AMD 32-core processors. Compared to
>> previous methods, this new method is optimized in the following areas:
>>
>> Motivation and Approaches:
>> 1. As the number of cores increases, there is a need for more refined
>> optimization of the data transmission paths between cores.
>> 2. Data transmission usually involves lock-unlock wrapping.
>> 3. Performance improvement can be achieved using a shortest path
>> approximation algorithm.
>>     A detailed introduction to this method can be found in the following paper:
>> https://www.usenix.org/conference/osdi23/presentation/lo
>>
>> Our laboratory is currently developing a system that can apply the
>> same optimization strategy to all multi-core processors. Below is our
>> plan.
>>
>> The New Method and Its Compatibility with qspinlock:
>> 1. The default algorithm in the Linux kernel remains qspinlock.
>> 2. A new file is created in /proc/routing_path, where a shortest path
>> can be input, for example:
>> sudo echo 1,2,3,4,16,17,18,19,5,6,7,8,11,12,13,14 > /proc/routing_path
>> 3. After inputting the shortest path, the kernel switches to using the
>> RON algorithm.
>>
>> Expected Outcomes:
>> According to our measurements on AMD 32-core and AMD 64-core
>> processors, Google LevelDB can achieve a 3-4% speed improvement.
>>
>> Comparison with Previous NUMA-aware algorithms:
>> Compared to NUMA-aware results, since such systems may contain more
>> than two processors, the communication cost between processors is much
>> higher than the communication cost between cores (within the same
>> processor). Our method focuses on multiple cores within a single
>> processor, making it multicore-aware. If a NUMA-aware algorithm is
>> used in a multicore environment, it is not as effective as a
>> multicore-aware algorithm. (Please refer to the paper,
>> https://www.usenix.org/conference/osdi23/presentation/lo)
>>
>> Assistance Needed:
>> I would like to understand if the Linux kernel community is interested
>> in this new spinlock method. As a teacher, I cannot complete all the
>> work by myself. Is anyone willing to collaborate with me on this
>> project?
>>
>> Sorry to bother you:
>> I apologize for taking up so much of your time with this letter.
>> Although I am quite old, this is the first time I feel that my
>> research results are good enough to contribute to the Linux community.
>> I have read the relevant documentation, and it made me realize that my
>> time and abilities are insufficient to write the high-quality code
>> required by the Linux community. Therefore, I ask for your guidance.
> I can't really say about this topic (as I'm not subject-matter expert here),
> so Cc: relevant maintainers.

After a quick look at the algorithm of the paper, I believe there are 2 
major issues with this algorithm.

1) Each lock requires a routing table of size num_possible_cpus() for 
the routing table. There can be thousands of spinlocks in the kernel and 
it may be problematic to manage this extra memory.

2) Beside lock contention performance, the Linux kernel also has to 
provide good uncontended spinlock performance. The unlock code currently 
scan the routing table to find the next one to allocate the lock to 
which may slow down the uncontended spinlock performance.

I believe this new lock can certain improve performance in a highly 
contended case, but I am not sure if it is a gain or loss in the 
uncontended or some less contended cases. Anyway, the 3-4% performance 
improvement in a contended lock may not be good enough for the 
performance loss in an uncontended lock.

There were attempts to introduce numa-awareness to qspinlock in the past.

https://lore.kernel.org/lkml/20210514200743.3026725-1-alex.kogan@oracle.com/

It was not accepted at the time because the of the increase in code 
complexity and the unfairness aspect of the implementation.

Thanks,
Longman

Re: A new spinlock for multicore (>16) platform

[Peter Zijlstra]

On Mon, Jul 15, 2024 at 06:45:16AM +0700, Bagas Sanjaya wrote:
> On Mon, Jul 15, 2024 at 01:07:40AM +0800, Shi-Wu, Lo（Gmail） wrote:
> > Dear Linux Contributors,

> >    A detailed introduction to this method can be found in the following paper:
> > https://www.usenix.org/conference/osdi23/presentation/lo

So if I understand this right, the algorithm basically boils down to a
circular path and unlock will iterate this path looking for the next CPU
waiting.

The worst case wait-time is one full circle of the rotor, which is
bounded, so that's good.

The immediate problem however is that O(n) iteration on unlock, given
Linux runs on many big machines with 1e3 order of CPUs, which would be
quite terrible on low to medium contention.

You mention in Future work, to alleviate this unlock issue by switching
to a linked-list, whereby unlock would then become O(1). The problem
then becomes lock() needs to an insertion-sort, which needs to know the
rotor position (eg. current lock owner).

I don't think that is a much easier proposition -- notably uncontended
fast path doesn't (want) to track the rotor position, and in the worst
case you're still iterating 1e3 order CPUs.

Hierachical rotors come to mind, but complexity -- is it warranted?

> > Our laboratory is currently developing a system that can apply the
> > same optimization strategy to all multi-core processors. Below is our
> > plan.
> > 
> > The New Method and Its Compatibility with qspinlock:
> > 1. The default algorithm in the Linux kernel remains qspinlock.
> > 2. A new file is created in /proc/routing_path, where a shortest path
> > can be input, for example:
> > sudo echo 1,2,3,4,16,17,18,19,5,6,7,8,11,12,13,14 > /proc/routing_path
> > 3. After inputting the shortest path, the kernel switches to using the
> > RON algorithm.

This is quite horrendous. If you cannot compute the OWCR from the
provided topology (CPUID on x86) 'nobody' is going to be using this.

Additionally, what locks are so contended that this gives a significant
performance gain, and can't we better rework the locking rather than the
lock implementation to alleviate this problem.

Eg. the futex hash lock is an oft cited example, but something like:

  https://lkml.kernel.org/r/20230721105744.434742902@infradead.org

can significantly reduce this.

That is, in general is helps more to reduce lock contention rather than
to optimize the contention behaviour.

So which locks do you see sufficient contention on to make this
worthwhile and how much do you gain by doing this?

Additionally, per the paper there are Linux patches (albeit for rather
old kernel versions), why aren't those included?

Re: A new spinlock for multicore (>16) platform

[Shi-Wu, Lo（Gmail）]

Here are my explanations for the two issues you mentioned:

1) Each lock requires a routing table of size num_possible_cpus() for
the routing table. There can be thousands of spinlocks in the kernel and
it may be problematic to manage this extra memory.

We have implemented this method in the Linux kernel.
(https://github.com/shiwulo/ron-osdi2023/blob/main/qspinlock.patch)
All locks share a single routing table, and all locks share a single
waiting array. This Linux kernel has been running for over a year
without any issues. Currently, we have implemented this method on the
AMD 2990WX (32 cores) and AMD 3995WX (64 cores).

This is because context switches cannot occur when the Linux kernel is
using spinlocks, so we can allow all cores to share a waiting array.
The space complexity of RON executed in the Linux kernel is O(#core),
which is the same as the space complexity of qspinlock. Since the
Linux kernel operates on all cores of a processor, we can allow all
spinlocks to share a routing table.

2) Beside lock contention performance, the Linux kernel also has to
provide good uncontended spinlock performance. The unlock code currently
scan the routing table to find the next one to allocate the lock to
which may slow down the uncontended spinlock performance.

We use a bit array to speed up the unlock execution. The nth bit
represents that the nth core wants to enter the critical section.
Therefore, the next core to enter the critical section can be quickly
determined using __ffs or __cnz. (page 29 in the document.
https://www.cs.ccu.edu.tw/~shiwulo/nxt+sh-RON.pdf) The new method's
(nxtRON) unlock time complexity is O(1). Under low contention, nxtRON
performs almost identically to GNU's pthread_spin_lock (TTAS).
Similarly, under low contention, qspinlock's performance is nearly the
same as GNU's pthread_spin_lock.

As shown in the pdf file (slides 56 to 59,
https://www.cs.ccu.edu.tw/~shiwulo/nxt+sh-RON.pdf), there can be a
3.8% improvement for the levelDB application.



Furthermore, the issues with multi-core (#core >16) processors and
NUMA system are different. NUMA-aware spinlocks assume that data
transfer between processors is slow, while data transfer within the
same processor is fast. Based on this assumption, NUMA-aware spinlocks
allow tasks on the same processor to enter the critical section before
allowing tasks on other cores to do so.

This approach (NUMA-aware spinlocks) has two main drawbacks. The first
drawback is the issue of fairness. The second drawback is that
NUMA-aware spinlocks do not optimize data transfer within the same
processor. The RON algorithm adheres to bounded waiting and can
optimize for multi-core processors.

Re: A new spinlock for multicore (>16) platform

[Shi-Wu, Lo（Gmail）]

Dear Peter Zijlstra,
To address the issues you mentioned, here are my explanations:

1. We currently use a bitArray to solve the time complexity problem
during unlock (https://www.cs.ccu.edu.tw/~shiwulo/nxt+sh-RON.pdf). If
the number of processors reaches thousands, a two-layer bitArray can
be used. The first layer bitArray records whether any group of cores
wants to enter the critical section, while the second layer bitArray
records which cores within that group want to enter the critical
section. After traversing a second layer bitArray, the first layer
bitArray determines the next second layer bitArray to be traversed.

2. Core-to-core transfer speed can be measured using code. In our
paper, the core-to-core transfer speeds were measured using our code.
There are already some websites providing information on core-to-core
transfer speeds, such as:
https://chipsandcheese.com/2023/11/07/core-to-core-latency-data-on-large-systems/.

3. Redesigning data structures to achieve higher performance is the
best approach, but not every problem can be solved with better data
structures. For example, many spinlocks are still used within the
current Linux kernel.

4. We have published the code on GitHub
(https://github.com/shiwulo/ron-osdi2023). This link is also available
on the first page of our paper. We did not apply for the USENIX
AVAILABLE badge because we believe that while our code is open, it is
not yet good enough.


shiwu

Peter Zijlstra <peterz@infradead.org> 於 2024年7月15日 週一 下午5:54寫道：
>
> On Mon, Jul 15, 2024 at 06:45:16AM +0700, Bagas Sanjaya wrote:
> > On Mon, Jul 15, 2024 at 01:07:40AM +0800, Shi-Wu, Lo（Gmail） wrote:
> > > Dear Linux Contributors,
>
> > >    A detailed introduction to this method can be found in the following paper:
> > > https://www.usenix.org/conference/osdi23/presentation/lo
>
> So if I understand this right, the algorithm basically boils down to a
> circular path and unlock will iterate this path looking for the next CPU
> waiting.
>
> The worst case wait-time is one full circle of the rotor, which is
> bounded, so that's good.
>
> The immediate problem however is that O(n) iteration on unlock, given
> Linux runs on many big machines with 1e3 order of CPUs, which would be
> quite terrible on low to medium contention.
>
> You mention in Future work, to alleviate this unlock issue by switching
> to a linked-list, whereby unlock would then become O(1). The problem
> then becomes lock() needs to an insertion-sort, which needs to know the
> rotor position (eg. current lock owner).
>
> I don't think that is a much easier proposition -- notably uncontended
> fast path doesn't (want) to track the rotor position, and in the worst
> case you're still iterating 1e3 order CPUs.
>
> Hierachical rotors come to mind, but complexity -- is it warranted?
>
> > > Our laboratory is currently developing a system that can apply the
> > > same optimization strategy to all multi-core processors. Below is our
> > > plan.
> > >
> > > The New Method and Its Compatibility with qspinlock:
> > > 1. The default algorithm in the Linux kernel remains qspinlock.
> > > 2. A new file is created in /proc/routing_path, where a shortest path
> > > can be input, for example:
> > > sudo echo 1,2,3,4,16,17,18,19,5,6,7,8,11,12,13,14 > /proc/routing_path
> > > 3. After inputting the shortest path, the kernel switches to using the
> > > RON algorithm.
>
> This is quite horrendous. If you cannot compute the OWCR from the
> provided topology (CPUID on x86) 'nobody' is going to be using this.
>
> Additionally, what locks are so contended that this gives a significant
> performance gain, and can't we better rework the locking rather than the
> lock implementation to alleviate this problem.
>
> Eg. the futex hash lock is an oft cited example, but something like:
>
>   https://lkml.kernel.org/r/20230721105744.434742902@infradead.org
>
> can significantly reduce this.
>
> That is, in general is helps more to reduce lock contention rather than
> to optimize the contention behaviour.
>
> So which locks do you see sufficient contention on to make this
> worthwhile and how much do you gain by doing this?
>
> Additionally, per the paper there are Linux patches (albeit for rather
> old kernel versions), why aren't those included?
>
>


-- 
羅習五
中正大學資工系，副教授
電話：(05)2720411轉33116
傳真：(05)2720859

Re: A new spinlock for multicore (>16) platform

[Shi-Wu, Lo（Gmail）]

Dear Linux Contributors,
Yesterday, I did not inform you that I added the mailing list of the
Operating Systems Laboratory at National Chung Cheng University,
Taiwan, to this discussion. I apologize for this discourtesy. The
mailing list has since been removed.

Could you please give me more advice? For example, should we implement
RON in the kernel under the current circumstances? Or should we
conduct more research before implementing RON in the kernel?
Additionally, is the current approach (where the superuser sets the
routing table) feasible?


shiwu

Re: A new spinlock for multicore (>16) platform

[Bagas Sanjaya]

[-- Attachment #1: Type: text/plain, Size: 902 bytes --]

On Wed, Jul 17, 2024 at 02:10:59AM +0800, Shi-Wu, Lo（Gmail） wrote:
> Dear Linux Contributors,
> Yesterday, I did not inform you that I added the mailing list of the
> Operating Systems Laboratory at National Chung Cheng University,
> Taiwan, to this discussion. I apologize for this discourtesy. The
> mailing list has since been removed.
> 
> Could you please give me more advice? For example, should we implement
> RON in the kernel under the current circumstances? Or should we
> conduct more research before implementing RON in the kernel?
> Additionally, is the current approach (where the superuser sets the
> routing table) feasible?

Show us the actual code (send the actual patch series). For information
on how to submit patches, see Documentation/process/submitting-patches.rst
in the kernel sources.

Bye!

-- 
An old man doll... just what I always wanted! - Clara

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]