Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
A concurrent SkipList version 1.0
17 views
Skip to first unread message
Ramine
Mar 26, 2015, 3:26:54 PM3/26/15
to
Hello,
A concurrent SkipList version 1.0
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
descent 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 concurrent SkipList from:
https://sites.google.com/site/aminer68/concurrent-skiplist
Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/
Operating Systems: Windows, Mac OSX , Linux...
Required FPC switches: -O3 -Sd -dFPC -dFreePascal
-Sd for delphi mode....
Required Delphi switches: -$H+ -DDelphi
The defines options inside defines1.inc are:
{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems
{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems
Thank you,
Amine Moulay Ramdane.
A concurrent SkipList version 1.0
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
descent 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 concurrent SkipList from:
https://sites.google.com/site/aminer68/concurrent-skiplist
Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/
Operating Systems: Windows, Mac OSX , Linux...
Required FPC switches: -O3 -Sd -dFPC -dFreePascal
-Sd for delphi mode....
Required Delphi switches: -$H+ -DDelphi
The defines options inside defines1.inc are:
{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems
{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems
Thank you,
Amine Moulay Ramdane.
Ramine
Mar 26, 2015, 3:35:16 PM3/26/15
to
Hello,
I have benchmarked it on an Intel Quadcore Q6600 and it has given a 4X
scalability on read-mostly workloads and it gives up to 250X scalability
on NUMA architecture and on more cores.
This concurrent SkipList is amazing ! try it and be happy !
Ramine
Mar 26, 2015, 5:41:41 PM3/26/15
to
Hello,
I have just discovered a bug in the delete() method of the Duncan
Murdoch's sequential Skiplist and i have just corrected it, and now my
concurrent SkipList is working correctly.
You can download the new version 1.01 of my concurrent SkipList from:
https://sites.google.com/site/aminer68/concurrent-skiplist
Ramine
Mar 31, 2015, 1:00:28 PM3/31/15
to
On 3/26/2015 3:32 PM, Ramine wrote:
> Hello,
>
>
> A concurrent SkipList version 1.0
>
>
> 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
> descent throughput. This parallel algorithm employs one distributed
i mean: it makes the insert() method of a decent throughput
> Hello,
>
>
> A concurrent SkipList version 1.0
>
>
> 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
> descent throughput. This parallel algorithm employs one distributed
0 new messages