[Insight-developers] Threading Model already had Deadlock issues

[Daniel Blezek]

Hi Kent,

  ITK (implicitly?) assumes all N threads are running at once in
ThreadedGenerateData.  If you have a Barrier that waits for N threads, but
threadId < total, then only N-1 threads will be in ThreadedGenerateData at
any given time, leading to Deadlock because the last thread will never get
there.

  We have been working hard not to break this implicit assumption in the
re-write of ITK's threading, but it looks as though the assumption is
invalid...

-dan


On 7/12/11 12:52 PM, "Williams, Norman K" <norman-k-williams at uiowa.edu>
wrote:

> I don't see what you're saying at all.  This ThreaderCallback gets called
> _IN THE SPAWNED THREAD_ doesn't it?
> 
> If that's the case, the thread either calls ThreadedGenerateData, or
> returns, which eventually terminates the thread. The main thread of
> execution does its own call to ThreadedGenerateData, and then goes into a
> 'thread reaper' loop where it waits for all other threads.
> 
> I don't see where the deadlock occurs.  Please correct me if I'm wrong.
> 
> 
> 
> On 7/12/11 12:30 PM, "Bradley Lowekamp" <blowekamp at mail.nih.gov> wrote:
> 
>> 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
>> 
>> 
>> _______________________________________________
>> Powered by www.kitware.com
>> 
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>> 
>> Kitware offers ITK Training Courses, for more information visit:
>> http://kitware.com/products/protraining.html
>> 
>> Please keep messages on-topic and check the ITK FAQ at:
>> http://www.itk.org/Wiki/ITK_FAQ
>> 
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-developers
> 
> 
> 
> ________________________________
> Notice: This UI Health Care e-mail (including attachments) is covered by the
> Electronic Communications Privacy Act, 18 U.S.C. 2510-2521, is confidential
> and may be legally privileged.  If you are not the intended recipient, you are
> hereby notified that any retention, dissemination, distribution, or copying of
> this communication is strictly prohibited.  Please reply to the sender that
> you have received the message in error, then delete it.  Thank you.
> ________________________________

-- 
Daniel Blezek, PhD
Medical Imaging Informatics Innovation Center

P 127 or (77) 8 8886
T 507 538 8886
E blezek.daniel at mayo.edu

Mayo Clinic
200 First St. S.W.
Harwick SL-44
Rochester, MN 55905
mayoclinic.org
"It is more complicated than you think." -- RFC 1925