[Insight-developers] Threading Model already had Deadlock issues

[Bradley Lowekamp]

Hello,

I have been working with Dan trying to change the ITK threading model to use OpenMP. We have been very concerned about potential deadlock conditions arising around the use of itk::Barrier, or other threading methodologies to wait for N thread. However, in looking through ITK current threading model, I also see a large flaw which became apparent after looking at the following code:


// Callback routine used by the threading library. This routine just calls                                                                         
// the ThreadedGenerateData method after setting the correct region for this                                                                       
// thread.                                                                                                                                         
template< class TOutputImage >
ITK_THREAD_RETURN_TYPE
ImageSource< TOutputImage >
::ThreaderCallback(void *arg)
{
  ..

  threadId = ( (MultiThreader::ThreadInfoStruct *)( arg ) )->ThreadID;
  threadCount = ( (MultiThreader::ThreadInfoStruct *)( arg ) )->NumberOfThreads;

  str = (ThreadStruct *)( ( (MultiThreader::ThreadInfoStruct *)( arg ) )->UserData );

  // execute the actual method with appropriate output region                                                                                      
  // first find out how many pieces extent can be split into.                                                                                      
  typename TOutputImage::RegionType splitRegion;
  total = str->Filter->SplitRequestedRegion(threadId, threadCount,
                                            splitRegion);

  if ( threadId < total )
    {
    str->Filter->ThreadedGenerateData(splitRegion, threadId);
    }
  // else                                                                                                                                          
  //   {                                                                                                                                           
  //   otherwise don't use this thread. Sometimes the threads dont                                                                                 
  //   break up very well and it is just as efficient to leave a                                                                                   
  //   few threads idle.                                                                                                                           
  //   }                                                                                                                                           

  return ITK_THREAD_RETURN_VALUE;
}


This say that currently, IITK does not guarantee that ThreadedGenerateData will be executed by N Threads. The default splitter splits orthogonal to the slowest axis. So if you have more threads then slices you are already bound for deadlock. Or in more general if S is the number of slices, there will be a not calling thread if (S%N)<N/2, and again on the right filter bound for deadlock. As N gets bigger this has a greater potential to occur.  It's amazing this hasn't been encountered more frequently.

Brad