Multithreading in codechef

I saw this video of gkcs today.

It is about multithreading. I tried to solve FCTRL2 using this method, and it worked. But my serial program ran faster than the parallel one. Then I found some programs of gkcs which run faster when using multiple processors. I have two doubts.

  1. Is multithreading allowed on all platforms like Topcoder, Codeforces, etc…

  2. If my program was using 1 unit of memory, will using 4 processors make it 4 units?

Also, is there a bug in my code? I can’t understand why the first solution ran slower than the second.

1 Like

Hi saphira. FCTRL2 doesn’t have too much scope for a parallel algorithm. The most compute intensive operation is finding all factorials, and that step has a pipeline structure. The other problem you have mentioned requires lots of I/O, so multithreading nearly doubled the efficiency compared to the standard program.

  1. I am not sure on it being allowed on all platforms. However, I can’t see how a person can be stopped from using multiple processors, so my guess is : no.

  2. If your threads all require the separate memory with size equal to that of the serial program, then yes: memory usage will shoot up.

I went through your parallel program. Seems alright. :slight_smile: