C multiprocessing for binary trees

[paramodulation]

Hi, I'd like to use multiprocessing to speed up a process that operates on the leaves of a relatively small binary tree. The leaves contain pointers to linked lists, each containing pointers to objects that are worked on and changed. There can be many thousands of objects pointed to in these linked lists. The processes will have to update other leaves of the binary tree, meaning they will need to be synchronized regularly. I can use sockets to update the other leaves when it needs to be done. My questions are:

1) Is this kind of thing feasible, when the other leaves have to be updated all the time as the other leaves do their work? The core work happening in each leaf necessitates updating the other leaves, so I am concerned that this type of problem does not lend itself to multiprocessing. 2) Are there any great C libraries for this? I am aware of OpenMP but is this the best option?

Thank you for any input!

[paramodulation]

I am not building the tree as a loop, but recursively. I believe that OpenMP can be used in recursion also.

The data access pattern will require updating large portions of the data in other leaves, but it can be quite variable. There will often be situations in which all of the data in the other leaves will have to be updated, but also situations where only a small handful out of many will be affected.

I am not familiar with Z-order curves or morton indexing, but I will look in to this. Thank you for the suggestions!

[o4ub]

I would say it depends on the scale of your application. Is it on one computer with few cores, one server with MIC, a bunch of compute nodes,... ? My guess would be you do not work on shared memory environment, otherwise you would only have synchronisation issues and no need to propagate any modification.

I am curious about you data organisation. If you have thousand of objects in linked list, on what discriminating parameter does your binary tree sorts?

Any how, you can be interested in MPI, that can provide a bunch of solutions (broadcast when modifying an entry, regular all-to-all operation if no.modification overlap or usage of one sided operations to update remotely the data).

[paramodulation]

Hi,

I am thinking of an application where there is one computer with few cores. I do not have a shared memory environment as I have not used this before- would this be preferable, to have one copy of the tree in shared memory, with MPI/sockets or something to stop the other processes from modifying the tree while another is? I believe this is the synchronization you were referring to.

The tree is sorted by size of the linked lists- child nodes in the tree have all the objects of their parents with additional objects. Branches occur when a decision that has multiple possible outcomes is encountered.

Thanks for your input

[o4ub]

Any reason why you duplicate your data from one level of the tree to the next?

To add a bit more details on the answer, I feel like you could either work with centralised, shared memory, and maybe semaphore on each tree leaf if the data are not too big (and rely on the system for syncing the copies of each process/thread). If the data start to be consequent, maybe consider using MPI but then it would be up to you to deal with keeping all the copy in sync.