Processor Scheduling on Parallel Computers

Authors: Mohammad S. Laghari, Gulzar A. Khuwaja

Abstract:

Many problems in computer vision and image processing present potential for parallel implementations through one of the three major paradigms of geometric parallelism, algorithmic parallelism and processor farming. Static process scheduling techniques are used successfully to exploit geometric and algorithmic parallelism, while dynamic process scheduling is better suited to dealing with the independent processes inherent in the process farming paradigm. This paper considers the application of parallel or multi-computers to a class of problems exhibiting spatial data characteristic of the geometric paradigm. However, by using processor farming paradigm, a dynamic scheduling technique is developed to suit the MIMD structure of the multi-computers. A hybrid scheme of scheduling is also developed and compared with the other schemes. The specific problem chosen for the investigation is the Hough transform for line detection.

Keywords: Hough transforms, parallel computer, parallel paradigms, scheduling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085080

References:

[1] T. L. Casavant and J. G. Kuhl, "A Taxonomy of Scheduling in General- Purpose Distributed Computing Systems," IEEE Trans. on Software Engineering, vol. 14, no. 2, Feb. 1988.
[2] P. V. C. Hough, "Method and means for recognising complex patterns," U.S. Patent No.3069654, 1962.
[3] R. O. Duda and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," CACM, vol. 15, no. 1, Jan. 1972.
[4] Z. Zivkovic, R. Kleihorst, A. Danilin, and H. Corporaal, "Real-time implementations of Hough Transform on SIMD architecture," in Proc. 2nd ACMIEEE Int. Conf. on Distributed Smart Cameras, Palo Alto, California, 2008, pp. 1-8.
[5] A. Epstein, G. U. Paul, B. Vettermann, C. Boulin, and F. Klefenz, "A Parallel Systolic Array ASIC for Real-Time Execution of the Hough Transform," IEEE Trans. on Nuclear Science, vol. 49, no. 2, pp. 339- 346, Apr. 2002.
[6] R. Strzodka, I. Ihrke, and M. Magnor, "A Graphics Hardware Implementation of the Generalized Hough Transform for fast Object Recognition, Scale, and 3D Pose Detection," in Proc. 12th Int. Conf. on Image Analysis and Processing, Mantova, Italy, 2003.
[7] S. S. Sathyanarayana, R. K. Satzoda, and T. Srikanthan, "Exploiting Inherent Parallelisms for Accelerating Linear Hough Transform," IEEE Trans. on Image Processing, vol. 18, no. 10, pp. 2255-2264, Oct. 2009.
[8] M. J. Flynn, "Very high-speed computing systems," in proc. of the IEEE, vol. 54, no. 12, pp. 1901-1909, 1966.
[9] M. Dongdong, L. Jinzong, Z. Bing, and Z. Fuzhen, "Research on the Architectures of Parallel Image Processing Systems," in proc.2nd Int. Symp. on Intelligent Information Technology Application, Shanghai, China, Dec. 2008, pp. 146-150.
[10] N. Zhang and J. Wang, "Image parallel processing based on GPU," in proc. 2nd Int. Conf. on Advanced Computer Control, Shenyang, China, 2010, pp. 367-370.
[11] Y. Krishnakumar, T. D. Prasad, K. V. S. Kumar, P. Raju, and B. Kiranmai, "Realization of a parallel operating SIMD-MIMD architecture for image processing application," in proc. Int. Conf. on Computer, Communication and Electrical Technology, Tirunelveli, Tamilnadu, India, 2011.
[12] H. Liu, Y. Fan, X. Deng, and S. Ji, "Parallel Processing Architecture of Remotely Sensed Image Processing System Based on Cluster," in proc. 2nd Int. Congress on Image and Signal Processing, Tianjin, China, 2009, pp. 1-4.
[13] A. G. Vicente, I. B. Mu├▒oz, P. J. Molina, and J. L. L. Galilea, "Embedded Vision Modules for Tracking and Counting People," IEEE Trans. on Instrumentation and Measurement, vol. 58, no. 9, pp. 3004- 3011, Sep. 2009.
[14] D. J. Pritchard, "Transputer Applications on Supernode," in proc. Int. Conf. on Application of Transputers, Liverpool, U.K., Aug. 1989.
[15] M. S. Laghari and F. Deravi, "Static vs. Dynamic Scheduling in Cellular Automaton," in proc. of Fall meeting # 4, North American Transputer User Group, Ithaca, New York, October 1990.
[16] A. S. Wagner, H. V. Sreekantaswamy, and S. T. Chanson, "Performance Models for the Processor Farm Paradigm," IEEE Trans. on Parallel and Distributed Systems, vol. 8, no. 5, pp. 475- 489, May 1997.
[17] A. Walsch, "Architecture and Prototype of a Real-Time Processor Farm Running at 1 MHz," Ph.D. Thesis, University of Mannheim, Mannheim, Germany 2002.
[18] Y. S. Yang, J. H. Bahn, S. E. Lee, and N. Bagherzadeh, "Parallel and Pipeline Processing for Block Cipher Algorithms on a Network-on- Chip," in proc. 6th Int. Conf. on Information Technology: New Generations, Las Vegas, Nevada, Apr. 2009, pp. 849-854.