Intel® Moderncode for Parallel Architectures
Support for developing parallel programming applications on Intel® Architecture.
This community is designed for sharing of public information. Please do not share Intel or third-party confidential information here.

Let's talk computer science...



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:

Thank you,
Amine Moulay Ramdane.


1 Reply
Good Morning :
Iam so happy to introduce my self to improve my experience with IBM as Future Developer IAppreciate your thread ifind it excellent advanced iam Mentor in data visualisation with illinois university since 2018 iam interest to understand and work
Best wishes,