Learning Parallel Computing Concepts via a Turing Machine Simulator
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.
Referências
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.
