Exposing data-level parallelism in sequential image processing algorithms

As new computer architectures are developed to exploit large-scale data-level parallelism, techniques are needed to retarget legacy sequential code to these platforms. Sequential programming languages force programmers to include sequential artifacts in their code, particularly with respect to how the source code expresses data references (generally assuming a linear address space). In contrast, data-parallel programs apply many operations in parallel to elements in two-dimensional data sets, and a given data parallel operation can access other spatially local elements along either dimension. Of key importance in exposing data parallelism is determining these two-dimensional data dependencies among elements of a matrix. This paper presents a reverse engineering technique for identifying such dependencies in sequential image processing code, using pattern matching on an attributed dataflow representation of the program. The technique is applied to common image filtering algorithms. The technique is validated by retargeting to a Matlab program and matching the results against those of the original source.