Parallelism IQ Challenge


SHOW YOUR STUFF - Answers to the Parallelism IQ Challenge

To help you along with this challenge, here are the answers to the questions and a brief explanation. Our job at the Threading for Multi-Core Developer Community is to help you learn more about multi-threading.  Don’t forget to submit your entry at the Intel booth for the T-shirt and the daily prize drawing.

1. A critical region is defined as: (Choose one)

(a) A code segment that can be executed atomically

(b) A code segment that accesses shared resources

(c) A portion of a source file containing static declarations

(d) Any part of the code that uses variables declared as “volatile”

Answer:   (b)

A critical region is any code that would run concurrently and access shared resources (e.g., memory, files).  This includes both read and update accesses.  While code in a critical region must be run by a single thread at any time, almost any part of a program can be executed atomically. 

2.  What is the most common error in multithreaded code? (Choose the best answer):

(a) Deadlock

(b) Thread stall

(c) Race condition

(d) Pragma ambiguity

Answer: (c)

Race conditions are the most common errors that will be found in threaded code.  Deadlock requires four necessary conditions to occur and thread stalls, especially due to a master thread waiting for workers to complete assigned tasks, aren’t usually considered errors unless they are unexpected.

3.  For a reduction operation to be done in parallel, the operation should be (pick least restrictive answer):

(a) commutative

(b) associative

(c) commutative and associative

(d) one of +, *, &, |, ^, min, max

Answer: (b)

The operation needs to be associative, but not necessarily commutative.  For example, string concatenation is a reduction operation that can be parallelized, but is not commutative. 

4. In task stealing, each thread works from its own task pool when possible and steals from other thread’s pools otherwise.  To support task stealing, what is typically the best policy for task pools?

(a)              treat own pool as LIFO; other pools as FIFO

(b)              treat own pool as FIFO; other pools as LIFO

(c)              treat all pools as LIFO

(d)              treat all pools as FIFO

(e)              randomly choose task from randomly chosen poo l


Answer: (a) or (b)

Local pools should be treated in the opposite way than other thread’s task pools.  In this way, threads will access their local pool from one end and tasks will be stolen by other threads from the other end.  This will help avoid clashes of threads trying to retrieve tasks from the same source.

5. Let T(p) be the application time when run on p cores.  The speed-up on a new Quad-Core desktop or server compared with the equivalent single core desktop or server is:

(a)              T(4)/T(1)

(b)              T(1)/T(4)

(c)              T(4)/T(1), but T(1) must be for best serial version of the application

(d)              T(4)/T(1), but T(4) must be shared-memory version of application

(e)              sqrt(T(4)*T(1))

Answer: (c)

The restriction to “best serial version” is important; comparing against the parallel version on a single core is usually unfair because the parallel version typically has extra overhead.

Is parallelism harder than you thought? Intel® TBB makes it easier!

For more information on parallelism and multi-core visit the Threading for Multi-Core Developer Community. Meet your fellow developers and participate in our blogs, discussion forums, and contests.   Need a quick fix? Check out our Knowledge Base and Code Samples



For more complete information about compiler optimizations, see our Optimization Notice.


Dmitry Vyukov's picture

Question 4.
If own pool is FIFO then thread accesses BOTH ends of it (head - to push, tail - to pop). So it's actually doesn't matter how other threads will access it - clashes will be.
This is why no framework uses this strange policy (option b). If own pool is FIFO, so it's better to use FIFO for stealing too, because it at least gives substantial degree of fairness.

anonymous's picture

David - precisely right. The right answer should have the terms flipped on (c): "T(1)/T(4), but T(1) must be for best serial version of the application". We used this quiz for conversation at our OSCON booth - and this error on the final copy for the quiz stirred up more conversation.

A serial (single core) running a program in 600 seconds, which sees time go to only 200 seconds on a quad-core... would definitely say that they saw a 3X speed-up (600/200).

Thank you for pointing this out!

anonymous's picture

Regarding question #5, Amdahl's Law for speedup is typically expressed as T_old/T_new. For discussions of serial vs. parallel systems it is typically expressed as T_serial/T_parallel, with the provision that the serial version is the best.

In other words, you're making the quad-core processors look pretty bad if the answer is (c).

Add a Comment

Have a technical question? Visit our forums. Have site or software product issues? Contact support.