Learning Parallel Computing Concepts via a Turing Machine Simulator

  • Mônica Xavier Py UFRGS
  • Laira Vieira Toscani UFRGS
  • Luís C. Lamb UFRGS
  • Tiarajú Asmuz Diverio UFRGS

Resumo


lt is well-known that technology developments in Computing Science has led to new developments in Computing Theory and vice-versa. This work is a contribution towards the formalisation of Parallel Processing concepts. We exploit variations of the Turing Machine model, referred as natural extensions, which may be composed by several control units, tapes and heads in such a way that one can define a variety of Parallel Turing Machine models. Several notions and definitions of parallelism are identified including computability, complexity and performance of computations. A prototype of the Parallel Turing Machine model is presented. This prototype was used as a test bed for the assessment of the usefulness of these machine models as a parallel processing teaching tool, as well as a tool to facilitate the creation of a "culture" among students in high performance computing. Finally, we analyse the notions of performance, speedup, efficiency, load balancing, synchronisation and communication in parallel processing.

Palavras-chave: Parallel Turing Machine, parallel computing, parallel computing theory

Referências

ANDREWS, Gregory R. Concurrent programming: principies and practice. Redwood City: Benjamin/Cummings, 1991. 637p.

OIVERIO, T.; MENEZES, P. Teoria da computação: máquinas universais e computabilidade. Second.ed. Porto Alegre: Sagra-Luzzatto, 2000. (Livros Didáticos, v.5).

GOULART, Peter C. et al. Paralelismo: algoritmos e complexidade. [S.I.]: PPGC da UFRGS, 1995. (RP 306).

HWANG, K.; BRIGGS, F. A. Computer architecture and parallel processing. New York: McGraw-Hill, 1984. 846p.

JáJá, Joseph. An introduction to parallel algorithms. Reading: Addison-Wesley, 1992.

LEWIS, H.; PAPADIMITRIOU, C. Elements of the theory of computation. [S.I.]: Prentice Hall, 1999.

MARQUEZAN, C. C. et al. Learning concurrency using parallel Turing Machine. In: PROC. OF THE 7TH WORLD CONFERENCE ON COMPUTER EDUCATION, 2001. Copenhagen. Anais . .. [S.I.: s.n.], 2001.

MINSKY. M. L. Computation: finile and infinite machines. Englewood Cliffs: Prentice Hall. 1967.

ODIFREDDI, Piergiorgio. Classical recursion theory: the theory of functions and sets of natural numbers. Amsterdam: North-Holland, 1989. Studies in Logic and the Foundations of Mathematics.

ROGERS JR, H. Theory of recursive functions and effective computability. [S.I.): McGraw-Hill, 1967.

SHAY. William A. Sistemas operacionais. São Paulo: Makron Books do Brasil, 1996. 758p.

TANENBAUM, Andrew S. Sistemas operacionais modernos. Rio de Janeiro: Prentice Hall do Brasil. 1995. 493p.

VAN EMDE BOAS, P. Machine models and simulations. In: LEEUWEN, J. van (Ed.). Handbook of theoretical computer science. Amsterdam: Elsevier Science, 1990. v.A, p. 1-66.

WIEDERMANN, J. Quo vadetis, parallel machines models. In: LEEUWEN, J. van (Ed.). Computer scicnce today. Berlin: Springer, 1995. p. 101-114. (Lecture Notes in Computer Science, v. IOOO).

WORSCH, T. On parallel Turing Machines with multi-head control units. Parallel Computing, v.23, p. 1683-1697, 1997.
Publicado
10/09/2001
PY, Mônica Xavier; TOSCANI, Laira Vieira; LAMB, Luís C.; DIVERIO, Tiarajú Asmuz. Learning Parallel Computing Concepts via a Turing Machine Simulator. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 13. , 2001, Pirenópolis. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2001 . p. 134-139. DOI: https://doi.org/10.5753/sbac-pad.2001.22201.