Load balancing requirements in parallel implementations of image feature extraction tasks
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 4 (9) , 994-1013
- https://doi.org/10.1109/71.243527
Abstract
Load balancing requirements in parallel image analysis are considered and results on theperformance of parallel implementations of two image feature extraction tasks on theConnection Machine and the iPSC/2 hypercube are reported and discussed. A loadredistribution algorithm, which makes use of parallel prefix operations and one-to-onepermutations among the processors, is described and has been used. The expectedimprovement in performance resulting from load balancing has been determinedanalytically and is compared to actual performance results obtained from the aboveimplementations. The analytical results demonstrate the specific dependence of theexpected improvement in performance on the computational and communicationrequirements of each task, characteristic machine parameters, a characterization of priorload distribution in terms of parameters which can be computed dynamically at the startof task execution, and the overhead incurred by load redistribution.Keywords
This publication has 19 references indexed in Scilit:
- Parallel implementation and evaluation of motion estimation system algorithms on a distributed memory multiprocessor using knowledge based mappingsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient embedding of interprocessor communications in parallel implementations of intermediate level vision tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Histogram computation on distributed memory architecturesConcurrency: Practice and Experience, 1989
- Benchmarking the iPSC/2 hypercube multiprocessorConcurrency: Practice and Experience, 1989
- Algorithmic techniques for computer vision on a fine-grained parallel machinePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Scans as primitive parallel operationsIEEE Transactions on Computers, 1989
- A concurrent on-board vision system for a mobile robotPublished by Association for Computing Machinery (ACM) ,1988
- The power of parallel prefixIEEE Transactions on Computers, 1985
- Generalizing the Hough transform to detect arbitrary shapesPattern Recognition, 1981
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977