Processor Scheduling on Parallel Computers

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.

Authors:

• Mohammad S. Laghari
• Gulzar A. Khuwaja

Keywords:

• Hough transforms
• parallel computer
• parallel paradigms
• scheduling.

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.