A Massively Parallel Re-Configurable Mesh Computer Emulator: Design, Modeling and Realization

ABSTRACT

Emulating massively parallel computer architectures represents a very important tool for the parallel programmers. It allows them to implement and validate their algorithms. Due to the high cost of the massively parallel real machines, they remain unavailable and not popular in the parallel computing community. The goal of this paper is to present an elaborated emulator of a 2-D massively parallel re-configurable mesh computer of size n x n processing elements (PE). Basing on the object modeling method, we develop a hard kernel of a parallel virtual machine in which we translate all the physical properties of its different components. A parallel programming language and its compiler are also devel-oped to edit, compile and run programs. The developed emulator is a multi platform system. It can be installed in any sequential computer whatever may be its operating system and its processing unit technology (CPU). The size n x n of this virtual re-configurable mesh is not limited; it depends just on the performance of the sequential machine supporting the emulator.

Emulating massively parallel computer architectures represents a very important tool for the parallel programmers. It allows them to implement and validate their algorithms. Due to the high cost of the massively parallel real machines, they remain unavailable and not popular in the parallel computing community. The goal of this paper is to present an elaborated emulator of a 2-D massively parallel re-configurable mesh computer of size n x n processing elements (PE). Basing on the object modeling method, we develop a hard kernel of a parallel virtual machine in which we translate all the physical properties of its different components. A parallel programming language and its compiler are also devel-oped to edit, compile and run programs. The developed emulator is a multi platform system. It can be installed in any sequential computer whatever may be its operating system and its processing unit technology (CPU). The size n x n of this virtual re-configurable mesh is not limited; it depends just on the performance of the sequential machine supporting the emulator.

KEYWORDS

Parallel processing, Object Modeling, Re-Configurable Mesh Computer, Emulation, XML, Parallel Virtual Machine

Parallel processing, Object Modeling, Re-Configurable Mesh Computer, Emulation, XML, Parallel Virtual Machine

Cite this paper

nullM. YOUSSFI, O. BOUATTANE and M. BENSALAH, "A Massively Parallel Re-Configurable Mesh Computer Emulator: Design, Modeling and Realization,"*Journal of Software Engineering and Applications*, Vol. 3 No. 1, 2010, pp. 11-26. doi: 10.4236/jsea.2010.31002.

nullM. YOUSSFI, O. BOUATTANE and M. BENSALAH, "A Massively Parallel Re-Configurable Mesh Computer Emulator: Design, Modeling and Realization,"

References

[1] R. Miller. et al, “Geometric algorithms for digitized pic-tures on a mesh connected computer,” IEEE Transactions on PAMI, Vol. 7, No. 2, pp. 216–228, 1985.

[2] V. K. Prasanna and D. I. Reisis, “Image computation on meshes with multiple broadcast,” IEEE Transactions on PAMI, Vol. 11, No. 11, pp. 1194–1201, 1989.

[3] H. LI, M. Maresca, “Polymorphic torus network,” IEEE Transaction on Computer, Vol. C-38, No. 9, pp. 1345– 1351, 1989.

[4] T. Hayachi, K. Nakano, and S. Olariu, “An O ((log log n)2) time algorithm to compute the convex hull of sorted points on re-configurable meshes,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 12, 1167– 1179, 1998.

[5] R. Miller, V. K. Prasanna-Kummar, D. I. Reisis, and Q. F. Stout, “Parallel computation on re-configurable meshes,” IEEE Transactions on Computer, Vol. 42, No. 6, pp. 678–692, 1993.

[6] J. P Gray and T. A. Kean, “Configurable hardware: A new paradigm for computation,” Proceedings of 10th Cal. Tech. conference on VLSI, pp. 279–295, 1989.

[7] H. Li and M. Maresca, “Polymorphic torus architecture for computer vision,” IEEE Transactions on PAMI, Vol. 11, No. 3, pp. 233–242, 1989.

[8] D. B. Shu, G. Nash, and C. Weems, “Image understand-ing architecture and applications, in advances in machine vision, J. L. C. SANZ, Ed. Springer-Verlag, NY, pp. 297– 355, 1989.

[9] H. M. Alnuweiri et al., “Re-configurable network switch- models,” Technical Report, CICSR, Univ. British Co-lumbia, 1993.

[10] J. L. Trahan, R. K. Thiruchelvan, and R. Vaidyanathan, “On the power of segmenting and fusing buses, Proc. Int. Parallel Processing Symposium, pp. 79–83, 1993.

[11] R. Miller and Q. F. Stout, “Mesh computer algorithms for computational geometry,” IEEE Transactions on com-puter, Vol. 38, No. 3, pp. 321–340, 1989.

[12] J. Elmesbahi, O. Bouattane, and Z. Benabbou, “O(1) time quadtree algorithm and its application for image geomet-ric properties on a Mesh Connected Computer (MCC), IEEE Trans. On Systems, Man, and Cybernetics, Vol. 25, No. 12, pp. 1640–1648, 1995.

[13] J. Elmesbahi, O. Bouattane, A. Raihani, M. Elkhaili, A. Rabbaa, “Parallel algorithms representation of points and curvilinear data,” International Journal of SAMS, Vol. 33, pp. 479–494, 1998.

[14] O. Bouattane, J. Elmesbahi, M. Khaldoun, and A. Rami, “A fast algorithm for k-nearest neighbor problem on a reconfigurable mesh computer,” Journal of Intelligent and Robotic Systems, Kluwer academic Publisher, Vol. 32, pp. 347–360, 2001.

[15] R. Miller et al, “Meshes with re-configurable Buses,” Proceedings of 5th MIT Conference on Advanced Re-search in VLSI, Cambridge, MA, pp. 163–178, 1988.

[16] Ling Tony et al, Efficient parallel processing of image contours,” IEEE Transactions on PAMI, Vol. 15, No. 1, pp. 69–81, 1993.

[17] O. Bouattane, J. Elmesbahi, and A. Rami, “A fast parallel algorithm for convex hull problem of multi-leveled im-ages,” Journal of Intelligent and Robotic Systems, Kluwer academic Publisher, Vol. 33, pp. 285–299, 2002.

[18] A. Errami, M. Khaldoun, J. Elmesbahi, and O. Bouattane, “O(1) time algorithm for structural characterization of multi-leveled images and its applications on a re-config-urable mesh computer,” Journal of Intelligent and Robotic Systems, Springer, Vol. 44, pp. 277–290, 2006.

[19] M. Migliardi and V. Sunderam, “Emulating parallel pro-gramming environments in the harness meta computing system,” Parallel Processing Letters, Vol. 11, No. 2 & 3, pp. 281–295, 2001.

[20] D. Kurzyniec, V. Sunderam, and M. Migliardi, “PVM emulation in the harness metacomputing framework -design and performance evaluation,” Proc. of the Second IEEE International Symposium on Cluster Computing and the Grid (CCGrid), Berlin, Germany, pp. 282–283, May 2002.

[21] M. Migliardi, P. Baglietto, and M. Maresca, “Virtual parallelism allows relaxing the synchronization con-straints of SIMD computing paradigm, Proceedings of HPCN98, Amsterdam (NL), pp. 784–793, April 1998.

[22] M. Migliardi and M. Maresca, “Modeling instruction level parallel architectures efficiency in image processing applications,” Proceedings of of HPCN97, Lecture Notes in Computer Science, Springer Verlag, Vol. 1225, pp. 738–751, 1997.

[23] M. Migliardi and R. Podesta, “Parallel component de-scriptor language: XML based deployment descriptors for grid application components,” Proc. of the 2007 Interna-tional Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, pp. 955–961, June 2007.

[1] R. Miller. et al, “Geometric algorithms for digitized pic-tures on a mesh connected computer,” IEEE Transactions on PAMI, Vol. 7, No. 2, pp. 216–228, 1985.

[2] V. K. Prasanna and D. I. Reisis, “Image computation on meshes with multiple broadcast,” IEEE Transactions on PAMI, Vol. 11, No. 11, pp. 1194–1201, 1989.

[3] H. LI, M. Maresca, “Polymorphic torus network,” IEEE Transaction on Computer, Vol. C-38, No. 9, pp. 1345– 1351, 1989.

[4] T. Hayachi, K. Nakano, and S. Olariu, “An O ((log log n)2) time algorithm to compute the convex hull of sorted points on re-configurable meshes,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 12, 1167– 1179, 1998.

[5] R. Miller, V. K. Prasanna-Kummar, D. I. Reisis, and Q. F. Stout, “Parallel computation on re-configurable meshes,” IEEE Transactions on Computer, Vol. 42, No. 6, pp. 678–692, 1993.

[6] J. P Gray and T. A. Kean, “Configurable hardware: A new paradigm for computation,” Proceedings of 10th Cal. Tech. conference on VLSI, pp. 279–295, 1989.

[7] H. Li and M. Maresca, “Polymorphic torus architecture for computer vision,” IEEE Transactions on PAMI, Vol. 11, No. 3, pp. 233–242, 1989.

[8] D. B. Shu, G. Nash, and C. Weems, “Image understand-ing architecture and applications, in advances in machine vision, J. L. C. SANZ, Ed. Springer-Verlag, NY, pp. 297– 355, 1989.

[9] H. M. Alnuweiri et al., “Re-configurable network switch- models,” Technical Report, CICSR, Univ. British Co-lumbia, 1993.

[10] J. L. Trahan, R. K. Thiruchelvan, and R. Vaidyanathan, “On the power of segmenting and fusing buses, Proc. Int. Parallel Processing Symposium, pp. 79–83, 1993.

[11] R. Miller and Q. F. Stout, “Mesh computer algorithms for computational geometry,” IEEE Transactions on com-puter, Vol. 38, No. 3, pp. 321–340, 1989.

[12] J. Elmesbahi, O. Bouattane, and Z. Benabbou, “O(1) time quadtree algorithm and its application for image geomet-ric properties on a Mesh Connected Computer (MCC), IEEE Trans. On Systems, Man, and Cybernetics, Vol. 25, No. 12, pp. 1640–1648, 1995.

[13] J. Elmesbahi, O. Bouattane, A. Raihani, M. Elkhaili, A. Rabbaa, “Parallel algorithms representation of points and curvilinear data,” International Journal of SAMS, Vol. 33, pp. 479–494, 1998.

[14] O. Bouattane, J. Elmesbahi, M. Khaldoun, and A. Rami, “A fast algorithm for k-nearest neighbor problem on a reconfigurable mesh computer,” Journal of Intelligent and Robotic Systems, Kluwer academic Publisher, Vol. 32, pp. 347–360, 2001.

[15] R. Miller et al, “Meshes with re-configurable Buses,” Proceedings of 5th MIT Conference on Advanced Re-search in VLSI, Cambridge, MA, pp. 163–178, 1988.

[16] Ling Tony et al, Efficient parallel processing of image contours,” IEEE Transactions on PAMI, Vol. 15, No. 1, pp. 69–81, 1993.

[17] O. Bouattane, J. Elmesbahi, and A. Rami, “A fast parallel algorithm for convex hull problem of multi-leveled im-ages,” Journal of Intelligent and Robotic Systems, Kluwer academic Publisher, Vol. 33, pp. 285–299, 2002.

[18] A. Errami, M. Khaldoun, J. Elmesbahi, and O. Bouattane, “O(1) time algorithm for structural characterization of multi-leveled images and its applications on a re-config-urable mesh computer,” Journal of Intelligent and Robotic Systems, Springer, Vol. 44, pp. 277–290, 2006.

[19] M. Migliardi and V. Sunderam, “Emulating parallel pro-gramming environments in the harness meta computing system,” Parallel Processing Letters, Vol. 11, No. 2 & 3, pp. 281–295, 2001.

[20] D. Kurzyniec, V. Sunderam, and M. Migliardi, “PVM emulation in the harness metacomputing framework -design and performance evaluation,” Proc. of the Second IEEE International Symposium on Cluster Computing and the Grid (CCGrid), Berlin, Germany, pp. 282–283, May 2002.

[21] M. Migliardi, P. Baglietto, and M. Maresca, “Virtual parallelism allows relaxing the synchronization con-straints of SIMD computing paradigm, Proceedings of HPCN98, Amsterdam (NL), pp. 784–793, April 1998.

[22] M. Migliardi and M. Maresca, “Modeling instruction level parallel architectures efficiency in image processing applications,” Proceedings of of HPCN97, Lecture Notes in Computer Science, Springer Verlag, Vol. 1225, pp. 738–751, 1997.

[23] M. Migliardi and R. Podesta, “Parallel component de-scriptor language: XML based deployment descriptors for grid application components,” Proc. of the 2007 Interna-tional Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, pp. 955–961, June 2007.