Parallel processing of multi-dimensional data with causal neighborhood dependencies

Abstract

In this paper, we investigate the problem of enabling block level parallelism, for multi-dimensional data sets, with arbitrary but static causal dependency between blocks that constitute the data set. As the use of video and other multidimensional data sets becomes more common place and the algorithms used to process them become more complex, there is greater need for effective parallelization schemes. We describe a method for synchronizing the execution of multiple processors to respect the dependency structure and calculate the total processing time as a function of the number of parallel processors. We also provide an algorithm to calculate the optimal starting times for each processor which enables them to continuously process blocks without the need for synchronizing with other processors, under the assumption that the time to process each block is fixed. © 2008 SPIE-IS&T.