Asp Forum - About scalability and parallel hashtable

Ramine

12/12/2014 9:38:00 PM

Hello,

Let's talk computer science...

I thought yesterday about parallel hashtables an there scalability,
and i have done a scalability prediction about my parallel hashlist
and my parallel varfiler, since in a parallel hashtable we are using
an "array" that permit also to reduce the access time to a time
complexity of O(1) in best case scenarios, this array is also a
bottleneck in scalability, cause on after you use a modulo that gives an
index on the array , this index on the array will be expensive in term
of running time , cause this will cause a cache miss and will cost
around 400 CPU cycles on x86, and since i am using a binary tree on
the buckets , so the height of the binary tree will be on average
a binary logarithm of the number of elements on the binary tree,
and since every element of the binary tree is allocated on a different
NUMA node this will parallelize the memory transfers from the memory to
the CPU when we are acessing the binary tree, but since the height of
the binary tree will be on average a binary logarithm of the number of
elements on the binary tree, so this will not scale perfectly, cause you
can get for example 4x scalability a bigger array of the hashtable and
on small data size, but if you want to get more scalability you can
increase the P (parallel) part of the Amdahl's law by doing more:
Increase the volume of data processed by the P part (and therefore the
percentage p of time spent in computing), This is Gustafson's Law and
you will get more scalability. That means the data on the binary tree
must be bigger, and since the data on the binary tree will be allocated
on different NUMA nodes, so the memory transfers of the data on the
binary tree from the memory to the CPU will be parallelized too.

You can download my Parallel Hahslist an my Parallel Varfiler from:

https://sites.google.com/site/aminer68/more-scalable-paralle...

https://sites.google.com/site/aminer68/more-scalable-paralle...

Thank you,
Amine Moulay Ramdane.

comp.programming

About scalability and parallel hashtable

Ramine

x Login to ForumsZone