Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2779 > unrolled thread

About scalability and parallel hashtables

Back to article view | Back to comp.programming.threads

Contents

  About scalability and parallel hashtables Ramine <ramine@1.1> - 2014-12-12 13:37 -0800

#2779 — About scalability and parallel hashtables

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-parallel-varfiler

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




Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web