Digest for comp.programming.threads@googlegroups.com - 1 update in 1 topic

comp.programming.threads@googlegroups.com

Google Groups

Topic digest
View all topics

• About scalability and parallel hashtables - 1 Update

About scalability and parallel hashtables

Ramine <ramine@1.1>: Dec 12 01:37PM -0800 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.

Back to top

You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com.