Are you familiar with thread-safe lock based data-structures? Yes. I am comfortable with the implementation and usage of thread-safe lock

Hi Vicente, Thanks for your detailed reply. Here is some more background about me. based data structures such as queue, stack, list, and map.

lock-free data structures? No. But I can learn <atomic> quickly. Is lock-free data structures going to be used a lot for this project? Which compiler(s) are you using? gcc 4.8/Apple LLVM version 5.0 Which platform(s)? Linux/Mac OS X Do you use already Boost? Only a bit.

Following your suggestion, I will proceed to implement a prototype of a thread pool having specific queue for each thread that make use of the sync_queue in Boost.Thread as part of my proposal. Hopefully, it will be in shape next week. Best, Haoyue Vicente J. Botet Escriba writes:

...

Hi, Hi, I am Haoyue, a PhD student in geophysics at MIT. I used C++11 to write parallel finite element codes in my research and had some coursework on concurrent programming.

Boost is such a powerful and efficient library. I sincerely hope I could contribute to it this summer and beyond.

I am interested in the standalone GSoC Projects under Boost.Thread. Particularly, the Work-Stealing-Thread-Pool project is a great one that I expect to learn a lot from.

I understand that there could be much more to discuss once I have a preliminary proposal. Here I just want to ask if I am heading in the right direction.

I think a good point to start is chapter 6, 7, and 9 of the book C++ Concurrency in Action: Practical Multithreading and the Executors and Schedulers revision 3 from http://www.open-std.org/. Yes, this is a good starting point. I haven't used Executor before but I am ware of its existence in Java for a while. Maybe I could go through some Executor and fork/join Java examples to see how they are used in practice. I don't think this is a good idea. Why not start with the executors included in Boost.Thread library (develop/master branches) Finally, I will read and understand the executors codes on GitHub. The executors directory included already some executors. One of them the basic_thread_pool is a good starting point. The work-stealing

Le 06/03/14 04:06, Haoyue Wang a écrit : thread_pool could be based on it and the implementation provided in CCIA 9.1.5.

...

I hope I could put up a good first draft proposal next Monday. If there is any advice, please let me know.

I would need to know more about your background. Are you familiar with thread-safe lock based data-structures? lock-free data structures?

Your first proposal should be as complete as possible and you will need to probe that you are knowledgeable of the problem domain, of Boost environment and of C++11. Showing a prototype of a thread pool having specific queue for each thread (See CCIA 9.1.4) that make use of the sync_queue in Boost.Thread would be really nice.

Which compiler(s) are you using? Which platform(s)? Do you use already Boost?

Best, Vicente

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

...

...

lock-free data structures? No. But I can learn <atomic> quickly. Is lock-free data structures going to be used a lot for this project? The work-stealing thread pool would have less contention if we use a lock-free dequeue. Of course, we can use Boost.LockFree if it provides already whatever we need.

actually, there are work-stealing queue data structures, with private 'push'/'pop' and a public 'steal' function. i do have a prototype of a textbook-implementation from herlihy/shavit, which is pretty efficient, although it is bounded (the maximum number of elements has to be defined in advance) and optimistic (under certain conditions a 'steal' operation may fail). it would make sense to integrate such a data structure into boost.lockfree as part of a GSOC regarding a work-stealing thread-pool. cheers, tim

...

...

...

No. But I can learn <atomic> quickly. Is lock-free data structures going to be used a lot for this project? The work-stealing thread pool would have less contention if we use a lock-free dequeue. Of course, we can use Boost.LockFree if it provides already whatever we need. actually, there are work-stealing queue data structures, with private 'push'/'pop' and a public 'steal' function. i do have a prototype of a textbook-implementation from herlihy/shavit, which is pretty efficient, although it is bounded (the maximum number of elements has to be defined in advance) and optimistic (under certain conditions a 'steal' operation may fail). Thanks Tim for the info. I have not yet analyzed how a thread_pool could work with bounded queues. Do we want to block when the queue is full?

blocking is probably not a good idea, but one could use a global dynamically-sized queue for jobs if the local work-stealing queue is full. one might loose some properties regarding lock-freedom, though that is not necessarily a porblem ...

...

it would make sense to integrate such a data structure into boost.lockfree as part of a GSOC regarding a work-stealing thread-pool.

If we found a consensus on what to do when the queue is full, yes this can be done during the GSoC project.

that would be wonderful! cheers, tim

Tim, would you like to co-mentor this project?

The tricky part of this project is more on the implementation off lock free deque. I would take care of the work-stealing thread pool of course.

sure! i do have some limited experience with work-stealing schedulers, and could definitely help out, mentoring this project! cheers, tim

Hi Vicente, A follow-up on your questions.

Do you have an thread-safe implementation of a map? Which synchronization mechanism do you use? The ones in Boost.Thread? Can you send it to me privately?

I am aware of several ways of implementing lock-based thread safe unordered map: 1) warp std::unordered_map in a class, and lock a method whenever it modifies the underlying map. There is no need of lock for concurrent read. However, this approach has little granularity and adding must be executed one at a time. 2) (CCIA 6.3.1.) Basically, unordered map in the raw form of vector > > is implemented. Each list has a boost::shared_lockboost::shared_mutex to ensure nonexclusive read access, and std::unique_lockboost::shared_mutex is used to ensure exclusive write. Since each list has its corresponding lock, there is more concurrency compared to 1). 3) Inspired by 1) and 2), I am thinking a structure of vector>. For each map, there is a corresponding std::mutex to ensure exclusive write access. Hash function is used to distribute data pairs in different maps evenly. In preliminary tests, I found 6 fold speed up when concurrent puts are tested on a 12 core machine. My implementation can be found at: https://github.com/whyzidane/threadsafe_map 4) If the overhead of one lock per list node is acceptable, implementation 2) can be more granulized.

Do you know how to build on Boost? How to run tests? How to build a quickbook? I know how to use header-only Libraries and separately built libraries. I haven't used Unit Test Framework-Boost and quickbook before. I can learn them soon though.

Best, Haoyue Vicente J. Botet Escriba writes:

Le 07/03/14 06:16, Haoyue Wang a écrit :

...

Hi Vicente,

Thanks for your detailed reply. Here is some more background about me.

...

Are you familiar with thread-safe lock based data-structures? Yes. I am comfortable with the implementation and usage of thread-safe lock based data structures such as queue, stack, list, and map. Do you have an thread-safe implementation of a map? Which synchronization mechanism do you use? The ones in Boost.Thread? Can you send it to me privately? lock-free data structures? No. But I can learn <atomic> quickly. Is lock-free data structures going to be used a lot for this project? The work-stealing thread pool would have less contention if we use a lock-free dequeue. Of course, we can use Boost.LockFree if it provides already whatever we need. Which compiler(s) are you using? gcc 4.8/Apple LLVM version 5.0 Which platform(s)? Linux/Mac OS X Do you use already Boost? Only a bit. Do you know how to build on Boost? How to run tests? How to build a quickbook?

Following your suggestion, I will proceed to implement a prototype of a thread pool having specific queue for each thread that make use of the sync_queue in Boost.Thread as part of my proposal. Hopefully, it will be in shape next week.

Great.

Vicente

...

Best, Haoyue

Vicente J. Botet Escriba writes:

...

...

Hi, Hi, I am Haoyue, a PhD student in geophysics at MIT. I used C++11 to write parallel finite element codes in my research and had some coursework on concurrent programming.

Boost is such a powerful and efficient library. I sincerely hope I could contribute to it this summer and beyond.

I am interested in the standalone GSoC Projects under Boost.Thread. Particularly, the Work-Stealing-Thread-Pool project is a great one that I expect to learn a lot from.

I understand that there could be much more to discuss once I have a preliminary proposal. Here I just want to ask if I am heading in the right direction.

I think a good point to start is chapter 6, 7, and 9 of the book C++ Concurrency in Action: Practical Multithreading and the Executors and Schedulers revision 3 from http://www.open-std.org/. Yes, this is a good starting point. I haven't used Executor before but I am ware of its existence in Java for a while. Maybe I could go through some Executor and fork/join Java examples to see how they are used in practice. I don't think this is a good idea. Why not start with the executors included in Boost.Thread library (develop/master branches) Finally, I will read and understand the executors codes on GitHub. The executors directory included already some executors. One of them the basic_thread_pool is a good starting point. The work-stealing

Le 06/03/14 04:06, Haoyue Wang a écrit : thread_pool could be based on it and the implementation provided in CCIA 9.1.5.

...

I hope I could put up a good first draft proposal next Monday. If there is any advice, please let me know.

I would need to know more about your background. Are you familiar with thread-safe lock based data-structures? lock-free data structures?

Your first proposal should be as complete as possible and you will need to probe that you are knowledgeable of the problem domain, of Boost environment and of C++11. Showing a prototype of a thread pool having specific queue for each thread (See CCIA 9.1.4) that make use of the sync_queue in Boost.Thread would be really nice.

Which compiler(s) are you using? Which platform(s)? Do you use already Boost?

Best, Vicente

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost