Reflective-Folding Data Mapping onto a Parallel Mesh of Processors.pdf

Re ective-Folding Data Mapping onto a Parallel Meshof ProcessorsPeter Chodyra and Binh PhamSchool of Computing and Information Technology, Grith UniversityNathan, Brisbane, 4111, AustraliaAbstractExisting techniques for mapping image data onto the processors of a SIMDmachine are suitable for algorithms which operate on data of spatially regularpatterns. However, many algorithms for image analysis deal with data on irregularand/or dynamically varying regions. We present a new data mapping techniquecalled re ective-folding which can cater eectively for these situations. An exampleto show how the technique is applied to a practical problem is also given.Technical areas: Image analysis, Parallel Computing.1 IntroductionEcient parallel image processing on SIMD machines greatly relies on an eectivemapping of the image data onto the processors. There exists a number of com-monly used data mapping techniques which can be used for mapping data onto a1D or 2D processor array (see for example [1, 2, 4]). However these techniques donot cater adequately for algorithms which operate on irregular and/or dynamicallyvarying regions. Some examples of such algorithms are contour following [3], andimage segmentation using region growing approach [6]. The aim of this paper isto present a new data mapping technique called re ective-folding that caters forsuch algorithms. The eectiveness of the technique is achieved by keeping neigh-bouring data in neighbouring processors to minimise the cost of communication.The next section describes the technique, the associated mapping formulae andthe complexity of the algorithm. Section 3 gives an example that shows how themapping technique can be used for a practical problem. Finally we evaluate theresults and discuss some ongoing work. 1 2 Re ective-Folding Data MappingIn order to utilise the capabilities of a SIMD style parallel computer, it is naturalto distribute the image data by dividing the image into equal-sized subimages andmapping the