Concurrent data structures support

[biddisco]

Attempting to port some CMS (from CERN c.f. @felicepantaleo, @rovere) software to HPX from TBB has hit a problem - the CMS code makes fairly liberal use of tbb concurrent data structures that we do not have drop-in replacements for in hpx. These need to be created/included in HPX.

• [x] concurrent_queue (boost::lockfree::queue)
• [x] concurrent_unordered_map (see hpx::parcelset::policies::verbs where readers/writer mutex is implemented for concurrent unordered map).
• [ ] concurrent_unordered_set
• [ ] concurrent_vector

also possibly required are replacements for

• [ ] tbb_hash
• [ ] tbb_hasher

For reference - some TBB related functions/classes that are used in the CMS software stack are as follows (this list may be incomplete).

$ git gr "tbb::" | grep -o -E "tbb::.*" | tr '<'  ' '  | awk '{print $1}' | sort | uniq -c
      2 tbb::",
      3 tbb::blocked_range
      6 tbb::concurrent_queue
     27 tbb::concurrent_unordered_map
      7 tbb::concurrent_unordered_set
      8 tbb::concurrent_vector
      3 tbb::empty_task*
      1 tbb::parallel_for(
      1 tbb::parallel_for(tbb::blocked_range
      1 tbb::parallel_for(0UL,collseed_size,1UL,theLoop);
      1 tbb::parallel_for_each(tasks.begin(),tasks.end(),invoker
      1 tbb::parallel_for_each(tasksD.begin(),tasksD.end(),invoker
      4 tbb::task
     35 tbb::task*
      1 tbb::task*).
      1 tbb::task*>
      1 tbb::task::allocate_additional_child_of(*pWaitTask))
      9 tbb::task::allocate_root())
      1 tbb::task::destroy(*eventLoopWaitTask);
      6 tbb::task::destroy(*iTask);}
      1 tbb::task::destroy(*iWait);
      1 tbb::task::enqueue(
      1 tbb::task::spawn(*iTask);
      1 tbb::task::spawn(*nextTask);
      3 tbb::task::spawn(*t);
      1 tbb::task::spawn(calc);
      4 tbb::task>
      5 tbb::task_scheduler_init
      2 tbb::task_scheduler_init::default_num_threads();
      1 tbb::task_scheduler_init>
      1 tbb::task_scheduler_init>&
      1 tbb::task_scheduler_init>(1);
      1 tbb::task_scheduler_init>(static_cast
      3 tbb::tbb_hash
      1 tbb::tbb_hasher(iKey.get());
      1 tbb::thread::id()
      5 tbb::tick_count
      1 tbb::tick_count"));
      4 tbb::tick_count::interval_t
      1 tbb::tick_count::interval_t();
      1 tbb::tick_count::interval_t(-1.e9);
      1 tbb::tick_count::interval_t(1.e9);
      1 tbb::tick_count::interval_t>

[hkaiser]

As a first step, we could create interface-compatible classes which simply use a spinlock to ensure data consistency. That shouldn't take too much time.

[biddisco]

Just FYI : In the verbs parcelport branch, I have modified the concurrent::unordered_map to make use of a new readers_writers_lock mutex and unique_lock/scoped_lock - this gives us single writer and multiple reader support for map. Once the verbs PP branch is merged, this code can be moved into the hpx/concurrent directory where some work was started (in the concurrent_data_structures branch).

[diehlpk]

@biddisco Could you please add a project description here https://github.com/STEllAR-GROUP/hpx/wiki/GSoC-2017-Project-Ideas#concurrent-data-structures-support

[rishabhkumar296]

Hi,

Is this project currently working in progress under GSoC 2017 ? If anyone is not working on it, I am willing to take this up.

[hkaiser]

@rishabhkumar296: None of the selected GSoC projects are related to this (see: http://stellar-group.org/2017/05/gsoc-2017-participants-announced/). Please feel free to work on this. It might be a good idea if you joined our IRC channel (#ste||ar at freenode) to be able to discuss things in a more direct way.

[felicepantaleo]

Hi @rishabhkumar296 @hkaiser , in July at CERN we will have a summer student working for about 3 months on the implementation of a toy framework for HEP event reconstruction using HPX. We will be definitely interested in testing your data structures and helping in further developments.

[hkaiser]

@felicepantaleo Ohh, that's great! Please let us know if there is anything we can do to support that.

[biddisco]

BTW. I did not see the discussion here, but last night I created a branch and made a PR #2629 because I need to use this concurrent map in code outside of the parcelport.

[felicepantaleo]

hi @biddisco @hkaiser, @Element-126 just started working on HPX for us. We will let you know if we need any support!

[msimberg]

@felicepantaleo @Element-126 @rishabhkumar296 Just checking to see if there has been any progress on this? We're planning a release in the next few months and wondering if anything could make it into that release?

[SHANTAM29]

@msimberg Is someone still working on this project? I want to work on this project. If someone is not working on it, I would like to do it.

[hkaiser]

@SHANTAM29 feel free. I don't think anybody is actively working on this.

[biddisco]

@SHANTAM29 if you do begin work on it, please get in touch with me via email or other means for a chat. I have been poking around with this recently.

[mikaelmello]

What is the status of hpx::concurrent::vector on the concurrent_data_structures branch?

[hkaiser]

@MikaelMello both seem to be abandoned. Feel free to pick things up where others have left things.

[shantanudwvd]

Hi, i would like to work on this project.

[Guyanqi]

Hey, this project looks great, I'd like to commit to it!

[hkaiser]

@shantanudwvd, @Guyanqi: Please get in contact on IRC or the hpx-users mailing list (see https://github.com/STEllAR-GROUP/hpx/blob/master/.github/SUPPORT.md).