[Insight-developers] Threading Model already had Deadlock issues

[Bradley Lowekamp]

On Jul 12, 2011, at 2:06 PM, Williams, Norman K wrote:
> 
> 
> 1. Divvy up work into at most MaxThreads chunks, & save chunk count.
> 2. Start chunk_count - 1 threads that call ThreadedGenerateData.
> 3. Call ThreadedGenerateData in main program.
> 4. Wait for chunk_count - 1 threads to exit.

I agree with this. Having a light wait thread pool for rapid spawning of threads should make this the new paradigm.

> 
> 
> On 7/12/11 12:58 PM, "Daniel Blezek" <Blezek.Daniel at mayo.edu> wrote:
> 
>> 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
>> 
> 
> 
> 
> ________________________________
> 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.
> ________________________________

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20110712/97c04027/attachment.htm>