3

I am writing a piece of code which takes the difference between two numbers, finds that location in memory, and then sets the location to true.

Currently my method of performing this is as follows. Note the function i_jlocation just does the comparison.

    #pragma omp parallel for collapse(2)
    for(int particleRow = 0; particleRow < numberOfDipolesI; particleRow++)
    {
        for(int particleColumn = 0; particleColumn < numberOfDipolesJ; particleColumn++)
        {
            int ijx , ijy , ijz;
            //
            // Find location
            //
            i_jlocation(objData.dimensions,dipolePositionsI,dipolePositionsJ,particleRow,particleColumn,&ijx,&ijy,&ijz);

            int truePos = ijx*2*2*objData.dimensions[1]*objData.dimensions[2]+ijy*2*objData.dimensions[2]+ijz;
            //#pragma omp critical (flipCrit)
            {
                temp[truePos] = true;
            }

        }
    }

Now in this piece of code I recognise that if I am to write true to that data block, there are many possible combinations of particleRow and particlecolumn which could lead to a race condition to any cell of memory. If I use the critical section above then the code will take ~180 seconds to complete using 12 cores, whereas without a critical section it is ~5 seconds. Now from my understanding of a race condition you get write-write and read-write races which could cause problems if different data is being input/read. However, I can guarantee that the data being input will always be the same. This means that no matter which order this occurs in, the outcome will never change.

Would this be considered an acceptable time to ignore a race condition? Personally I feel this is not acceptable, but I am struggling to find an algorithmic way to avoid hitting the same cell twice, and the speed increase is a necessity due to the HPC nature of the problem I am trying to tackle.

  • Depends on the language. I think in C++11, a data race is undefined behaviour, so you have to use relaxed atomics or something. – Bwmat Dec 13 '18 at 7:14
8

If you are sure that the result is consistent, then it is perfectly fine to do this. You've hit upon one of the main strategies for improving concurrency, in fact. Eliminating locks is a key to improving performance for concurrent algorithms. One approach that allows for this is to design things to be tolerant to race conditions. For example, if you can arrange things such that it doesn't matter whether one thread overwrites the result of another, then you have avoided the need for a lock. You shouldn't feel bad about this. It's an achievement.

I have not evaluated whether this is correct. If there is a subtle flaw in your reasoning, it could make your algorithm incorrect/unstable. Testing is unfortunately not good enough for this kind of thing.

  • 1
    Maybe you can prove it with TLA+ or some other prover... Cloud service providers use it for things like this. – Erik Eidt Dec 12 '18 at 18:14
  • There are some games that did that, but regretted it. It made network multiplayer impossible because shared game state would randomly diverge. Also very much related, bug reproduction by replaying game actions is impossible. And at least one racing game where recorded track runs would randomly drive off the track and explode. – Zan Lynx Dec 13 '18 at 6:47
  • But to add to my comment after re-reading your answer, those examples I gave are of different values being written into a shared location. Values that were "close enough" to not matter, but cause cascading divergence over time. – Zan Lynx Dec 13 '18 at 6:50
  • @ZanLynx Right. The caveat in my answer is that the assertion that the same value is being written to the same place by multiple threads. If that's not strictly true, then all kinds of havoc could break loose. – JimmyJames Dec 13 '18 at 15:34
  • @ErikEidt Thanks for pointing me to TLA+; really nice stuff. I'm a little puzzled that it isn't just HTML instead of the Hyperbook but content is great. – JimmyJames Dec 14 '18 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.