Multidimensional Arrays and the nArray Package

Please use this identifier to cite or link to this publication: http://hdl.handle.net/1926/553
At the Johns Hopkins University’s Engineering Research Center for Computer-Integrated Surgical Systems and Technology (ERC-CISST) laboratory, we have designed and developed a platformindependent C++ software package, called the nArray library, that provides a unified framework for efficiently working with multidimensional data sets. In this paper, we present and discuss the core elements of the library, including its intuitive and uniform API, efficient arithmetic engine algorithm, and efficient sub-volume algorithm. We then compare the performance of the nArray library with that of an existing multidimensional array toolkit, ITK. We conclude that the nArray library is more efficient than ITK in many situations, especially in operations on sub-arrays, and that the two packages have comparable performance in many other scenarios. The underlying algorithms, if incorporated in ITK, can help improve its performance.
Data
minus 3 Files (2Mb)
Code
minus Automatic Testing Results by Insight-Journal Dashboard on Mon Jul 2 20:56:38 2007 for revision #2
starstarstarstarstar expertise: 5 sensitivity: 4.7
yellow This project was submitted with no test cases.
Click here for more details.

Go here to access the main testing dashboard.

Reviews
minus Great Open Source Spirit by Luis Ibanez on 09-12-2007 for revision #2
starstarstarstarstar expertise: 5 sensitivity: 4.3
yellow

Summary:

This paper describes nArray, and open source library for manipulating N-Dimensional arrays, and compares it usage with equivalent operations in N-Dimensional images in ITK.


Hypothesis:

N/A

Evidence:

N/A


Open Science:

The paper fully complies with the requirements of Open Science. The authors provide their source code and detailed instructions (in the form of well configured tests) on how to run the same benchmarks that are presented in the paper.


Reproducibility:

It was straight forward to reproduce the work that the authors describe in their paper.

The source code of the library was provided with the paper, along with the source code of the benchmarks that compared nArray performance against ITK.

It was very easy to configure, build and run the code.

I build it on Debian Linux, in a dual processon Xeon 2.4GHz, 3Gb RAM, build with gcc 4.1, for Release

 

Given that the machine I used is different from what the authors used, the actual numerical output of the Benchmarks are different from what appears in the paper.

 However, this simply highlight how important is that benchmark comparisons have to be performed by providing readers the means of repeating the benchmark on their own local environment.

The authors did a great job of organizing and configuring the benchmark test s in such a way that they are almost trivial to execute.

The outputs in my system are:

  • ImageAdd_ITK_Benchmark Window Extract 21032 Sum 18100 WindowsExtract and sum 39119
  • ImageAdd_nArray_Benchmark SumOf time 7488 operator + time 14076
  • Subarray_ITK_Benchmark Fill time 416537 Window time 10926 Slice time 478 Permute time 231274
  • Subarray_nArray_Benchmark Fill time  360814  Window time 5225  Slice time 214  Permute time 192745

It wasn't obvious how to map these numbers into the corresponding cells of the Table 3, in page 13 of the paper....

 

The benchmark conclusions are a bit misleading in the abstract and the conclusions sections. Specially given that several of the comparison showed that nArray methods are faster in some cases and slower in some other cases.  In any case, the advantage of the paper is that the source code for both ITK and nArray is available, and the authors made the benchmarks available for inspections to the readers. This makes possible to verify how the code performs in other platform combinations. 


Use of Open Source Software:

The authors used ITK as a reference to compare the performance of nArray.

nArray was also configured using CMake 


Open Source Contributions:

The authors provide the source code of nArray and distribute it under a thoughtful license.

The code is very well organized, and it was straight forward to use.


Code Quality:


The source code is very well written. It uses a consistent coding style. The coding style is different from ITK's but that's not a concern given that nArray is a library and if used from ITK it will probably be included in the Utilities directory and then its functionalities will be invoked from there.

I build the code only in Linux, so I didn't verified the portability of the code. However the authors present results for Linux and Windows, and from the structure of the code there are no reasons to believe that it couldn't be widely portable.


Applicability to other problems:

Since the nArray library provide such a fundamental functionality of storage, data access and basic data processing there is an endless list of applications for it.

It is certainly worth to explore mechanisms for integrating this library with ITK, whether by making easy for users to use simultaneously ITK images and nArrays, for example via ImageAdaptors, or via specialized version of the nArray___Ref classes that could actually point to an ITK image allocated buffer.


Suggestions for future work:

Exploring combinations of ITK and nArray are probably the most interesting next step. This will make possible for application developers to take advantage of nArray qualities in certain operations of their applications, while using ITK for other operations, and in this way get the best of each world. This could be implemented as

  • An itkImage-like class that reuses the memory allocated by an nArray, maskarading the nArray iterations as an itkPixelContainer
  • An nArray___Ref class that connects to an ITK image buffer instead of an actual memory block allocated by an nArray class.


Requests for additional information from authors:

I missed from the paper some comments regarding the impact of multi-threading. Specially considering the fact that one of the machines used by the authors is a dual processor, and that the AddImageFilter in ITK is multi-threaded. We assume that the nArray algorithms are multi-threaded, but there is no explicit mention of it in the paper. If nArray, is not multi-threader, then the timing reported are even more impressive, since it will mean that (at least in one platform) their speed more that doubled ITK performance.

A quick grepping on the source code of the authors seem to indicate that no multi-threading is being used in nArray. If that's the case, the results of the benchmark must be re-analized under this light, and,.... it also becomes interesting to consider multi-threading nArray, in order to get even better performance.


Additional Comments:

It will be very interesting, and very useful to the ITK community to explore mechanisms for bringing the advantages of nArray into ITK.

Several mechanisms come to mind

  • Creating specialized ITK filters whose internal implementation uses nArray
  • Studying the internal implementation of nArray and compare it to ITK image iterators, to improve the implementation of the ITK iterators. Such improvements will then automatically improve the performance of ITK filters since almost all of them are based on image iterators.
  • Making easy to combine ITK images and nArray via ImageAdaptors (or nArray adaptors), so that an existing nArray could be accessed as an ITK image, or an ITK image be access like an nArray. Both options seem to be perfectly feasible.
minus Interesting Multidimensional Array Package by Joel Zuhars on 09-11-2007 for revision #2
starstarstarstarstar expertise: 3 sensitivity: 4.7
yellow

Summary:

The authors describe a multidimensional array package that both has a uniform interface across all levels of dimensionality for ease of usability, and is comparable or superior in performance to existing packages, such as ITK. This was done using a templated interface approach and some novel implementation techniques.
 
Evidence:

Table 1 provides a sampling of the API, and discussions on nArray engines and iterators, plus the associated code samples, illustrate key aspects of the API usage and support the notion that the interface is generally easy to use.

I would have liked to see a more complete treatment of the API in the paper, rather than referring to the package itself for more details, and more specific examples of how the API is superior to ITK, given that the ease of use improvement was one of the primary goals.

Section 4 details the performance benchmarking strategy versus ITK, provides references to the source code used, identifies the two system configurations used, and provides the numerical performance results along with a results analysis.

The performance results and analysis supported the claim that the package is at least comparable to ITK, but I would have liked to see that done more conclusively, given that this was a primary goal of the work. Although it can be exceptionally difficult or impossible to hunt down the root causes for the wide variability in performance in such packages, a serious effort in this regard, including platform specific optimizations, if necessary, could possibly take this package to the level of a standard.

Open Science:

A link to the CISST Software Package is provided in the references. I assumed it would be straightforward to locate and compile the nArray library from the package, but did not do so myself. References to the source code used for benchmarking are provided in the text. I assumed these are located in the CISST Software Package.

Reproducibility:

I have not attempted to reproduce the author’s work.

Use of Open Source Software:

The authors directly compared their work to ITK.

Open Source Contributions:

The authors provide links to their source code. I did not see a reference to the applicable licenses for the code, which would be an improvement if added.

Code Quality:

The code is clearly suitable for multi-platform use. The implementation discussion leads one to assume that the code is of excellent quality, in particular, the appropriate use of templates, and the stated accomplishment of conformance with STL’s specification for a random access iterator.

Applicability to other problems:

The authors are attempting to improve on a fundamental aspect of image analysis programming. This work would be applicable to a wide variety of problems, not limited to the image analysis domain.

Suggestions for future work:

See evidence section.

Also, it was not clear if the recursive function in section 3.3 was actual code from the package or presented to support the explanation only. If it represents the actual code, I would be interested in seeing if any performance difference can be derived by using a much less elegant non-recursive version, since use of recursion in such cases can be inefficient.

Additional Comments:

In general, I felt as though this has the potential to be a valuable contribution to the field, and that the ITK implementation could indeed be improved through the use of the described methods. The paper, however, seemed to lose focus from its objectives somewhat, in that it shifts to detailing the novelties of the implementation, rather than proving out it’s goals, which seemed the more appropriate use of the reader’s time at this level. The implementation details were, of course, also very interesting.

 

Add a new review
Quick Comments


Resources
backyellow
Download All

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

Information more
backyellow
Categories: CMake, Code memory optimization, Code speed optimization, Data Representation, Extreme Programming, Generic Programming, Image, Iterators, Linear Algebra, Mathematics, Programming, Spatial Objects
Keywords: software toolkit, API, software library, C++, object-oriented, multidimensional data, generic programming, template library, scientific computing, data structures, multidimensional arrays, vectors and matrices
Toolkits: ITK, CMake
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.
Automatic Junction Detection for Tubular Structures Automatic Junction Detection for Tubular Structures
by Xiong G., Xing L., Taylor C.

View license
Loading license...

Send a message to the author
main_flat
ISSN 2327-770X
Powered by Midas