Insight Journal (ISSN 2327-770X) - A new implementation of itk::ImageToImageFilter for efficient parallelization of image processing algorithms using Intel Threading Building Blocks

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

Jaberzadeh A., Scherrer B., Warfield S.

Harvard Medical School

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3560

Published in The Insight Journal - 2016 January-December.

Submitted by Amir Jaberzadeh on 07-21-2016.

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

1 Dataset (245b)

Link_To_Zipfile.txt (245b)

Code

There is no code review at this time.

Reviews

Valuable contribution by Dženan Zukić on 2016-07-28 15:40:50 for revision #1

expertise: 5 sensitivity: 5

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 Aollwaymyrt Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Ekjamerkend Ken:

Comment by Defeldanni Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Tsmccathedema Ken:

Comment by Lithrailesmered Olivier:

Comment by Umcglaufllind Olivier:

Comment by Lheeralalkris Olivier:

Comment by Ohnatowgabr Ken:

Comment by Bridesmaidbride Ken:

Comment by Itezziodiss Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Tnorthfor Olivier:

Comment by Lheeralalkris Olivier:

Comment by Aaccajohn Holland:

Comment by Milbluemelsherr Ken:

Comment by Rankeurensuan Ken:

Comment by Itezziodiss Holland:

Comment by Bridesmaidbride Ken:

Comment by Tsmccathedema Ken:

Comment by Mwangmajor Holland:

Comment by Lheeralalkris Olivier:

Comment by Rdeenrayro Ken:

Comment by Ntlnoel Holland:

Comment by Mwangmajor Holland:

Comment by Ebraselharl Holland:

Comment by Bridesmaidbride Ken:

Comment by Elissierdeon Olivier:

Comment by Milbluemelsherr Ken:

Comment by Latellireed Ken:

Comment by Rnseremmi Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Aeternaeterna Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Tyamatriley Vigorda:

Comment by Mwangmajor Holland:

Comment by Ohnatowgabr Ken:

Comment by Owigsonline Holland:

Comment by Lheeralalkris Olivier:

Comment by Umcglaufllind Olivier:

Comment by Lithrailesmered Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Dsfordthad Holland:

Comment by Ekjamerkend Ken:

Comment by Tnorthfor Olivier:

Comment by Lheeralalkris Olivier:

Comment by Aaccajohn Holland:

Comment by Defeldanni Vigorda:

Comment by Rankeurensuan Ken:

Comment by Nhuskinsaran Ken:

Comment by Mwangmajor Holland:

Comment by Elissierdeon Olivier:

Comment by Mwangmajor Holland:

Comment by Tyamatriley Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Milbluemelsherr Ken:

Comment by Defeldanni Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Defeldanni Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Elissierdeon Olivier:

Comment by Tyamatriley Vigorda:

Comment by Rankeurensuan Ken:

Comment by Tsmccathedema Ken:

Comment by Lithrailesmered Olivier:

Comment by Ekjamerkend Ken:

Comment by Lithrailesmered Olivier:

Comment by Defeldanni Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Lithrailesmered Olivier:

Comment by Ntlnoel Holland:

Comment by Ntlawrencetheos Ken:

Comment by Tyamatriley Vigorda:

Comment by Rnseremmi Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Mwangmajor Holland:

Comment by Pshopgolf Olivier:

Comment by Umcglaufllind Olivier:

Comment by Bridesmaidbride Ken:

Comment by Mwangmajor Holland:

Comment by Nhuskinsaran Ken:

Comment by Umcglaufllind Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Tsmccathedema Ken:

Comment by Defeldanni Vigorda:

Comment by Aaccajohn Holland:

Comment by Rnseremmi Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Umcglaufllind Olivier:

Comment by Pshopgolf Olivier:

Comment by Elissierdeon Olivier:

Comment by Lheeralalkris Olivier:

Comment by Itezziodiss Holland:

Comment by Elissierdeon Olivier:

Comment by Rnseremmi Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Milbluemelsherr Ken:

Comment by Pshopgolf Olivier:

Comment by Mwangmajor Holland:

Comment by Pshopgolf Olivier:

Comment by Ekjamerkend Ken:

Comment by Defeldanni Vigorda:

Comment by Rankeurensuan Ken:

Add a new review

Quick Comments

Comment by Matthew Mccormick

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


Download All
Download Paper , View Paper
Download Source code

Statistics more


Global rating:
Review rating:	[review]
Code rating:
Views:	18530
Downloads:	2749
Paper Quality:
1 comment

Information more


Paper Id:	974
Categories:	Diffusion Tensor Imaging, Image, Parallelization, SMP, Statistics on tensors, Tensor image reconstruction
Keywords:	Multithreading, ImageToImageFilter, TBB, dynamic scheduling
Toolkits:	ITK, CMake, VTK
Revision:
Export citation:
Status:	Open for public review

Share

Linked Publications more


Efficient multithreading for manycore processor: Multidimensional domain decomposition using... by St-Onge E., Scherrer B., Warfield S.K.
Computing Bone Morphometric Feature Maps from 3-Dimensional Images by Vimort J., McCormick M., Paniagua B.
Scalable Simple Linear Iterative Clustering (SSLIC) Using a Generic and Parallel Approach by Lowekamp B., Chen D., Yaniv Z., Yoo T.
A patch-based framework for new ITK functionality: Joint fusion, denoising, and non-local... by Tustison N., Avants B., Wang H., Xie L., Coupe P., Yushkevich P., Manjon J.
Providing values of adjacent voxel with vtkDiscreteMarchingCubes by Grothausmann R.
N-Dimensional Computation of Strain Tensor Images in the Insight Toolkit by McCormick M.
Computing Textural Feature Maps for N-Dimensional images by Vimort J., McCormick M., Budin F., Paniagua B.
RLEImage: run-length encoded memory compression scheme for an itk::Image by Zukić D., McCormick M., Gerig G., Yushkevich P.
Perturbing Mesh Vertices with Additive Gaussian Noise by Vigneault D.
ND morphological contour interpolation by Zukić D., Vicory J., McCormick M., Wisse L., Gerig G., Yushkevich P., Aylward S.

View license

Loading license...

Send a message to the author