[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

A concurrent SkipList version 1.0

Ramine

3/26/2015 10:32:00 PM


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/concurren...


Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freep...

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.
3 Answers

Ramine

3/26/2015 10:41:00 PM

0


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 !


Thank you,
Amine Moulay Ramdane.

Ramine

3/27/2015 12:45:00 AM

0


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/concurren...


Thank you,
Amine Moulay Ramdane.

Ramine

3/31/2015 8:05:00 PM

0

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

> 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/concurren...
>
>
> Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freep...
>
> 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.
>