<div dir="ltr">Hi,<br><div class="gmail_extra">Nice catch, Tobias<br><div class="gmail_quote">On Fri, Dec 6, 2013 at 10:10 AM, Tobias Pietzsch <span dir="ltr"><<a href="mailto:pietzsch@mpi-cbg.de" target="_blank">pietzsch@mpi-cbg.de</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word">Hi,<div><br></div><div>
Problem: Did anyone think about the possibility of deadlocks?</div>
<div><br></div><div>Lets take the scenario that Lee mentioned. We enqueue a lot of tasks that each trigger computation of a set of features for an image each.</div><div>Probably the features can be computed in parallel, so basically what a single task does is: create subtasks, submit to ExecutorService, then block until they complete.</div>

<div>The subtask for a single feature of a single image might again create subtasks for parts of the image and block until they complete.</div><div>This may easily lead to the situation that all threads in the ExecutorService block because they wait for subtasks that are not executed because all threads block… Right?</div>

<div><br></div></div></blockquote><div> They block AND are idle for no good reason - doubly bad.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word">
<div></div><div>So unfortunately, in my opinion that rules out both ExecutorService and SJC ThreadService (unless heavily modified).</div><div><br></div><div><br></div><div>How to solve this? The perfect solution is ForkJoin from java.util.concurrent, <a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html" target="_blank">http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html</a></div>

<div>Unfortunately this was introduced only in Java 7 and thats a problem because we want to be 1.6 compatible.</div></div></blockquote><div><br></div><div>There have been recent attempts to solve this in  Python (e.g. <a href="http://greenlet.readthedocs.org/en/latest/">http://greenlet.readthedocs.org/en/latest/</a>). If you have a language with lightweight pseudo-stacks and pseudo-threads, it's easy to just swap "stacks" when you hit one of the blocking states and trade for a task that's unblocked. For Java and C, true stacks are big (1MB) and the swapping is not so good.</div>
<div><br></div><div>One semi-elegant solution is for the service to check whether the thread requesting redemption of a future is a worker thread. If so, the function that blocks just takes some work to be done off of the work queue, choosing the work queued by its thread and completes it. An idle thread is also allowed to take stuff off of this queue. So you need to attach thread identity to the objects being enqueued. There's no downside to making a worker thread complete the items queued by itself - the work has probably been queued  up optimally at a higher level.</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><br></div><div>So what should we do?</div><div>There seems to be the option of using the Fork/Join framework from jdk1.6 <a href="http://homes.cs.washington.edu/~djg/teachingMaterials/grossmanSPAC_forkJoinFramework.html#installation" target="_blank">http://homes.cs.washington.edu/~djg/teachingMaterials/grossmanSPAC_forkJoinFramework.html#installation</a>. If I understand correctly, this is the exact implementation as used in jdk1.7.</div>

<div>The other option is to reinvent that particular wheel in scijava-common or imglib2.</div><div><br></div><div>best regards,</div><div>Tobias</div><div><br></div><div><br></div><div><div><div><div>On Dec 6, 2013, at 2:27 PM, Lee Kamentsky <<a href="mailto:leek@broadinstitute.org" target="_blank">leek@broadinstitute.org</a>> wrote:</div>

<br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra">Hi all,<br><br><div class="gmail_quote">On Fri, Dec 6, 2013 at 3:29 AM, Jean-Yves Tinevez <span dir="ltr"><<a href="mailto:jean-yves.tinevez@pasteur.fr" target="_blank">jean-yves.tinevez@pasteur.fr</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi all<br>
<br>Each frame of a movie can be processed concurrently: I generate a task for each frame, and can feed this task to any interface we are discussing right now. For this, I do not need to know how many threads are allocated to the service: it will decide how to process the tasks I generated.<br>



<br>
By there are many algorithms in imglib2 that can process a single image in a multithreaded way, by splitting it into small pieces. For instance, you can compute the Gauss convolution on 2 threads, and it will split the source image in 2. For this, the algorithm needs to have some info on the "multitasking resources" available right? If you have 24 workers, and that each worker receives one frame to segment, the segmenter needs to know it is unwise to split the source image over several extra workers. No?<br>



<br>
How is this achieved in real world applications?<br></blockquote><div>I think we're in a lucky sweet spot where the size of our data is big and the number of processors is small. I think you want to amortize the cost of enqueueing the work, thread signaling and thread context switching over a pretty big chunk of data - and that's operating-system and processor-specific in my experience, so it's best to benchmark. If I remember correctly, as an example, Ilastik 0.5 breaks its images into chunks of 10K pixels and runs perhaps 100 filters on each, plus a random-forest evaluation. In that case, the large-grain operation makes the optimization question pretty moot since the computation is so expensive (and doing the chunking at the top level might be a good design choice).</div>


<div><br></div><div>It would be kind of cool if the service could give you an idea of the cost of running one future and of the size of the thread pool. This is notoriously difficult to measure, but a rough cut might be to find the minimum time from enqueing a future until its execution and multiply that by 2. If you knew the cost of running your algorithm on N pixels, you could figure out how to slice it. It would also be kind of cool if your imglib data container (or some helper class that encapsulated this expertise) could give you a collection of iterators appropriate for the cost of your operation and the thread service it would be run on.</div>


<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
best<br>
jy<span><font color="#888888"><br>
<span><font color="#888888"><br>
--<br>
--<br>
Please avoid top-posting, and please make sure to reply-to-all!<br>
<br>
Mailing list web interface: <a href="http://groups.google.com/group/fiji-devel" target="_blank">http://groups.google.com/group/fiji-devel</a><br>
<br>
---<br>
You received this message because you are subscribed to the Google Groups "Fiji-devel" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:fiji-devel%2Bunsubscribe@googlegroups.com" target="_blank">fiji-devel+unsubscribe@googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/groups/opt_out" target="_blank">https://groups.google.com/groups/opt_out</a>.<br>
</font></span></font></span></blockquote></div><span><font color="#888888"><br></font></span></div></div>
</blockquote></div><br></div></div></div></blockquote></div><br></div></div>