Community
cancel
Showing results for 
Search instead for 
Did you mean: 
aminer10
Beginner
29 Views

Let's talk computer science...

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 Hashlist 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.


 

Tags (1)
0 Kudos
0 Replies
Reply