SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

C++ 11 Concurrency

August 28th, 2015, 9:21 am

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
 
User avatar
ExSan
Posts: 4552
Joined: April 12th, 2003, 10:40 am

C++ 11 Concurrency

August 28th, 2015, 10:27 am

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 !
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 28th, 2015, 11:13 am

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
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 28th, 2015, 11:15 am

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
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 28th, 2015, 11:18 am

QuoteOriginally posted by: outrunQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: outrunYes, futi.get() are blocking till the i-th thread finished. First launch all threads with std::future, then futi.get() all threads, when the first thread finished, the first get will stop blocking and at that time the other 3 threads should be ready too.Indeed. In this case since there is no shared data we can define the rendezvous point after firing up all futures. Now I get the same results as expected, both for C+11 and PPL.Pff! Indeed, if you have shared data and dependencies between threads like "thread 2 is waiting for thread 1s result" then this won't work! The order of gets will then be important.I must say I like simple threads better than future/get, but maybe it's "what the farmer doesn't know he doesn't eat"In the beginning I also found future non-intuitive until I use a task graph to visualize it. I think one can write the sequential version and then look for potential parallelism. It is almost 1:1 mapping to code and that is cool IMO. Sure beats ad-hoc experimentation.I think that can be done for any problem of any size.BTW the answer from the code is 42.
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
 
User avatar
Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

August 28th, 2015, 11:34 am

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
 
User avatar
Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

August 28th, 2015, 11:36 am

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
 
User avatar
ExSan
Posts: 4552
Joined: April 12th, 2003, 10:40 am

C++ 11 Concurrency

August 28th, 2015, 6:59 pm

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
 
User avatar
Polter
Posts: 2526
Joined: April 29th, 2008, 4:55 pm

C++ 11 Concurrency

August 28th, 2015, 7:45 pm

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...
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 29th, 2015, 9:03 am

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
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 29th, 2015, 12:43 pm

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
 
User avatar
Cuchulainn
Topic Author
Posts: 61593
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ 11 Concurrency

August 29th, 2015, 1:15 pm

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
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On