SERVING THE QUANTITATIVE FINANCE COMMUNITY

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

Quiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Other
Last edited by Cuchulainn on August 27th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

ExSan
Posts: 4552
Joined: April 12th, 2003, 10:40 am

C++ 11 Concurrency

QuoteOriginally posted by: CuchulainnQuiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Otherat most 0.25, for sure no more !

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

QuoteOriginally posted by: outrunOne of the 4 sequences can have a worst case pre-sort order and the others can be sorted already (or ... resulting in minimal run-time).In general, for the average case, you have variable run times for each thread. Since all threads run on a single processor they'll get time-sliced and give a slightly worse performance than sequential code due to the task-switches during time slicing. Ahmad's law is about improvement, so a negative value?I got a speedup of 2 in general for all libraries. Applying Amdahl I get serial fraction = 0.333. Of course, the bottleneck is that std::sort() is sequential, not parallel.Quote Since all threads run on a single processor Each thread is on a single processor, we can see 100% utilization on Task Manager. Summary:The serial fraction is 0.33 which is very bad (but not the point).
Last edited by Cuchulainn on August 27th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

QuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Otherat most 0.25, for sure no more !You are an optimist. You mean 'no less'??
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

Last edited by Cuchulainn on August 27th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

Cuch: Take a look at Boost.Thread futures (implementing Concurrency TS proposal), continuations are pretty cool:http://www.boost.org/doc/libs/master/do ... tures.then

Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

Folly Futures (Facebook's implementation of futures for C++11) is also worth a look:http://code.facebook.com/posts/16619820 ... positional Building Blocks (go far beyond sequential composition using then):http://github.com/facebook/folly/blob/m ... ing-blocks

ExSan
Posts: 4552
Joined: April 12th, 2003, 10:40 am

C++ 11 Concurrency

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Otherat most 0.25, for sure no more !You are an optimist. You mean 'no less'??depends on your point of view, whether you are on the left/right side

Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

QuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Otherat most 0.25, for sure no more !You are an optimist. You mean 'no less'??depends on your point of view, whether you are on the left/right sideWell...

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

QuoteOriginally posted by: PolterQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: ExSanQuoteOriginally posted by: CuchulainnQuiz:We sort 4 independent vectors using 4 threads/processors (each thread calls std::sort()). What is the serial fraction using Amdahl's Law. Is it:1 0.12. 0.253. 0.34. Otherat most 0.25, for sure no more !You are an optimist. You mean 'no less'??depends on your point of view, whether you are on the left/right sideWell...I am just the messenger, :DI ran the code and got a speedup of two. So far, so good.I reversed engineered Amdahl's law to get f = 1/3.So, 33% of the code is serial. Throwing more processors at the problem will probably slow it down (the magic f ~ 0.1).Of course, std::sort() is a serial algorithm that gets called 4 times.
Last edited by Cuchulainn on August 28th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

QuoteOriginally posted by: outrunThis author is working on submitting parallel_sort to boost. He might appreciate your benchmarks?https://github.com/fjtapia/sort_parallelGood tip. Will look into it. Thanks. My hope would be to do nested parallelization and then improve the speedup from 2 to 3.3456789 or thereabouts(?).
Last edited by Cuchulainn on August 28th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Cuchulainn
Topic Author
Posts: 61537
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

Two more solution to the bespoke task graph:1. Using std::thread and promises, maybe give the feeling of more control?2. Using boost future continuations based on polter's tip; it's very intuitive and probably good for optimization.Some solution are more intuitive then others I suppose.What are the views of the people?Answer: 42
Last edited by Cuchulainn on August 28th, 2015, 10:00 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget