A new implementation of itk::ImageToImageFilter for efficient parallelization of image processing algorithms using Intel Threading Building Blocks
logo

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3560
Modern medical imaging makes use of high performance computing to accelerate image acquisition, image reconstruction, image visualization and image analysis. Software libraries that provide implementations of key medical imaging algorithms need to efficiently exploit modern CPU architectures. In particular, workstations with small numbers of cores are being replaced by very high core count architectures, and by many integrated core architectures, which offer acceleration by vectorization and multi-threading.

The Insight Toolkit (ITK) is the premier open source implementation of medical imaging algorithms, with a generic design for image processing filters that allows for many developers to rapidly incorporate these algorithms in to new applications. While ITK filters benefit from a generic, platform independent multithreading capability, the current implementation is difficult to exploit to achieve very high performance. Specifically, ITK relies on a static decomposition of the image into subsets of equal size which can be highly inefficient. Threads that terminate early due to uneven work throughout the image finish early and do not contribute further to the processing of more complex regions, leading to idle computational resources and longer execution times. Performance is also difficult to coordinate across multiple algorithms, as the ITK filter assumes each filter operates independently but the global implementation has an impact across filters.

In this work, we propose a novel, simple to use, high performance multithreading capability for ITK that accelerates the itk::ImageToImageFilter. We utilise a workpile data decomposition strategy, and leave the task of optimal job scheduling on CPU cores to the library called Threading Building Blocks (TBB). We demonstrate the efficacy of multi-threading with TBB in comparison to the itk::Multithreader class, through three simple example image analysis algorithms.

Our implementation provides a new multi-threaded itk::ImageToImageFilter that can be conveniently reused to provide simple and efficient multi-threaded code across applications and algorithm libraries. Our new implementation is distributed as open-source software to the community and is straightforward to adopt.
Data
minus 1 Dataset (245b)
Code
There is no code review at this time.

Reviews
minus Valuable contribution by Dženan Zukić on 2016-07-28 15:40:50 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 5
yellow
Summary:

Authors modernize filter parallelization infrastructure.

Hypothesis:

Usage of dynamic domain splitting enables higher efficacy of parallel filters with unbalanced workload.

Evidence:

The authors tested their method on 3 different examples, to showcase the extent of the improvement.

Open Science:

The authors provide source code, input images and bash scripts to generate quantitative results.

Reproducibility:

The source code was quick and easy to compile (I already had a compiled version of TBB). The provided readme was sufficient.

Use of Open Source Software:

The authors clearly explained that this class provides speedup only for unevenly balanced workloads (variable processing time for different pixels).


They mentioned thread recycling between executions in the classic parallel model, but did not explain whether TBB keeps the thread pool alive between different filter executions.


They neglected to mention that TBB is an inconveniently big dependency, and that unbalanced workloads are less common than (moslty) balanced ones.

Open source Contributions:

The main contribution is templated class implemented in a pair of headers, which makes it very usable. The test "examples" are non-trivial applications themselves.

Code Quality :

I only took a look at the main class, not the examples. The code was easy to read and surprisingly short.

Quality of the data :

I am not that familiar with DWI, so I cannot judge the quality of the supplied test data, but the data is in a convenient format.


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlawrencetheos Ken: yellow


Comment by Ntlawrencetheos Ken: yellow


Comment by Ntlawrencetheos Ken: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Aaccajohn Holland: yellow


Comment by Aaccajohn Holland: yellow


Comment by Aaccajohn Holland: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Lithrailesmered Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow

Add a new review
Quick Comments
Comment by Matthew Mccormick yellow
In this article, the authors summarize challenges related to parallelism
in modern high performance computing and present improvements to the Insight
Toolkit (ITK) with Threading Building Blocks (TBB).

The hypothesis is that threads in many-core CPUs are starved for work given
the way that data is divided and distributed among threads. A more
fine-grained and dynamic data decomposition and improved job scheduling will
improve performance.

The authors provide source code, data, and bash scripts for a quality,
reproducible open science publication. Proposed improvements to ITK image
processing filters with TBB are described, and evidence for the improvements
are provided with example, realistic DWI processing.

Overall, this is an excellent publication that describes the high performance
computing challenges in ITK well and touches on an appropriate solution with
TBB. While the hypothesis that performance gains are likely partially related
to idle threads as proposed, much of the performance gains are also likely due
to reduce overhead from spawning and destroying threads. This work has the
potential to be very high impact. The improvements to a very large number of
algorithms available in ITK are significant. While the benchmarking performed
was on a 12-core Xeon system, which is a common system today, systems are coming
available, like the Knight's Landing Phi processor, which will experience
even greater performance improvements.

The following improvements and next steps will ensure this work is high
impact:

The main code should be submitted to the Gerrit code review system, and
improvements should be made to ensure it works on all supported platforms,
follows ITK style guidelines, etc. This process is described here:

https://itk.org/ITKSoftwareGuide/html/Book1/ITKSoftwareGuide-Book1ch10.html


In practice, it is not possible to have a hard dependency on TBB for ITK. TBB
cannot be bundled with ITK because of its size, its license, and its build
system. It can be difficult to obtain and configure against. It does not
support all platforms that people use with ITK. So, the addition should be an
optional ITK configuration setting enabled with CMake.

Since it is not practical to maintain two duplicate version of all filters,
the proposed code should be added to itk::ImageSource when TBB is available
which will not require duplication or modification of existing filters.

It may be possible for existing filters to re-use their
ThreadedGenerateData method by passing the tbb::block_range::begin() value as a
substitute for the ThreadIdType argument. While this is not the thread id, it
may fulfill the needs of how many filters, which currently use the
argument to conditionally performing operations when its value is 0, perform
progress reporting, etc. An optional specialized TBB method could be
implemented by filters and used when available.

In terms of data division, another improvement would implement the proposed
strategy as an implementation of the itk::ImageRegionSplitterBase or
itk::ThreadedDomainPartitioner class, and set this new class as the default when TBB
is enabled. This will make it possible to override the strategy with other
implementations in the future.


Resources
backyellow
Download All
Download Paper , View Paper
Download Source code

Statistics more
backyellow
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating:
Paper Quality: plus minus
1 comment

Information more
backyellow
Categories: Diffusion Tensor Imaging, Image, Parallelization, SMP, Statistics on tensors, Tensor image reconstruction
Keywords: Multithreading, ImageToImageFilter, TBB, dynamic scheduling
Toolkits: ITK, CMake, VTK
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Efficient multithreading for manycore processor: Multidimensional domain decomposition using... Efficient multithreading for manycore processor: Multidimensional domain decomposition using...
by St-Onge E., Scherrer B., Warfield S.K.
RLEImage: run-length encoded memory compression scheme for an itk::Image RLEImage: run-length encoded memory compression scheme for an itk::Image
by Zukić D., McCormick M., Gerig G., Yushkevich P.

View license
Loading license...

Send a message to the author
main_flat
Powered by Midas