- A new concurrent SkipList algorithm - 1 Update
- cmsg cancel <mq2sll$75n$1@dont-email.me> - 3 Updates
- Scalability prediction... - 1 Update
- A concurrent SkipList version 1.02 - 1 Update
| Ramine <ramine@1.1>: Aug 07 05:26PM -0700 Hello... If you ask me a question like: Amine, is there any new parallel Skiplist algorithm that is more efficient than your conccurrent algorithm that uses a distributed read-writer mutex ? I have thought more, and i have come with a new Parallel Skiplist algorithm that is scalable on a read mostly workload, this algorithm uses only an mfence on the reader side, that's really cool ! and it elevates the weakness of the distributed reader-writer mutex that becomes slower and slower on the writer side with more an more threads, in my new concurrent Skiplist algorithm i am using one SeqlockX between the search() and the insert() methods , you will find my SeqlockX algorithm that avoids livelock when there is many writers here: https://sites.google.com/site/aminer68/scalable-seqlockx and i am also using one distributed reader-writer mutex between the delete() and the search() methods... This new algorithm is faster than my previous concurrent SkipList algorthm, but i have made a scalability prediction for my new algorithm and i have noticed that since the serial part of the Amdahl's law of the writer side is a little bit expensive since the average search in a Skiplist can become a little bit expensive, so my calculation has proved that you will not get much improvement with this new algorithm compared to my previous algorithm, you will get around 3x improvement max, so i have finally decided to not implement my new concurrent SkipList algorithm, so i will stay with my current concurrent SkipList algorithm that gives a decent scalability. Thank you, Amine Moulay Ramdane. |
| bleachbot <bleachbot@httrack.com>: Aug 07 08:17PM +0200 |
| bleachbot <bleachbot@httrack.com>: Aug 07 10:48PM +0200 |
| bleachbot <bleachbot@httrack.com>: Aug 07 11:23PM +0200 |
| Ramine <ramine@1.1>: Aug 07 04:48PM -0700 Hello, As you have noticed i have implemented a concurrent Skiplist, the interface of my concurrent Skiplist is very fexible, and as you have noticed i am using one distributed reader-writer mutex to implement my concurrent algorithm, so i am not using RCU or SMR or VZoom, so i have done a scalability prediction for this algorithm, and i have noticed that on a 32 NUMA nodes computer and 50 millions of read , write and delete requests, with a workload of 0.5% of writes and ~99% of reads, it will give a throughput of 50 millions request per 10 seconds , that's cool. On a non-NUMA Quadcore it will give 4X scalability. You can download my new concurrent Skiplist version 1.02 from: https://sites.google.com/site/aminer68/concurrent-skiplist Thank you, Amine Moulay Ramdane. |
| Ramine <ramine@1.1>: Aug 07 02:20PM -0700 Hello, A concurrent SkipList version 1.02 I have updated my concurrent Skiplist , i have just corrected a bug inside the next() method, now when you want to call next() method to get a sorted list, please call the Enter() method before getting the sorted list with the next() method and call the Leave() method after you get the sorted list, please look at how to do it by looking at the test examples inside the zip file. Authors: Amine Moulay Ramdane (Based on Duncan Murdoch's sequential Skiplist) Description: I propose a new concurrent skip list algorithm distinguished by a combination of simplicity and scalability. This parallel algorithm makes the search() method scalable and it makes the insert() method of a decent throughput. This parallel algorithm employs one distributed reader-writer mutex that makes the search() method scales to 250X on NUMA architecture and on multicores, unlike some other concurrent skip list algorithms, this algorithm preserves the skiplist properties at all times, which facilitates reasoning about its correctness. Experimental evidence shows that this parallel algorithm performs well. You can download my concurrent Skiplist version 1.02 from: https://sites.google.com/site/aminer68/concurrent-skiplist Thank you, Amine Moulay Ramdane. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com. |
No comments:
Post a Comment