Skip to main content

2016 | OriginalPaper | Buchkapitel

Toward a Parallel Turing Machine Model

verfasst von : Peng Qu, Jin Yan, Guang R. Gao

Erschienen in: Network and Parallel Computing

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the field of parallel computing, the late leader Ken Kennedy, has raised a concern in early 1990s: “Is Parallel Computing Dead?” Now, we have witnessed the tremendous momentum of the “second spring” of parallel computing in recent years. But, what lesson should we learn from the history of parallel computing when we are walking out from the bottom state of the field?
To this end, this paper examines the disappointing state of the work in parallel Turing machine models in the past 50 years of parallel computing research. Lacking a solid yet intuitive parallel Turing machine model will continue to be a serious challenge. Our paper presents an attempt to address this challenge — by presenting a proposal of a parallel Turing machine model — the PTM model. We also discuss why we start our work in this paper from a parallel Turing machine model instead of other choices.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
The term token, is from a familiar terminology of dataflow literature. In the rest of this paper, we use the term events to denote signal tokens (or event tokens) present on certain arcs.
 
Literatur
1.
Zurück zum Zitat Arvind, K., Nikhil, R.S.: Executing a program on the MIT tagged-token dataflow architecture. IEEE Trans. Comput. 39(3), 300–318 (1990)CrossRefMATH Arvind, K., Nikhil, R.S.: Executing a program on the MIT tagged-token dataflow architecture. IEEE Trans. Comput. 39(3), 300–318 (1990)CrossRefMATH
2.
Zurück zum Zitat van Boas, P.E.: Machine models and simulations. Handb. Theor. Comput. Sci. A, 1–66 (2014)MATH van Boas, P.E.: Machine models and simulations. Handb. Theor. Comput. Sci. A, 1–66 (2014)MATH
3.
Zurück zum Zitat Bouknight, W.J., Denenberg, S.A., McIntyre, D.E., et al.: The Illiac IV system. Proc. IEEE 60(4), 369–388 (1972)CrossRef Bouknight, W.J., Denenberg, S.A., McIntyre, D.E., et al.: The Illiac IV system. Proc. IEEE 60(4), 369–388 (1972)CrossRef
4.
Zurück zum Zitat Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., et al.: Cilk: an efficient multithreaded runtime system. J. Parallel Distrib. Comput. 37(1), 55–69 (1996)CrossRef Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., et al.: Cilk: an efficient multithreaded runtime system. J. Parallel Distrib. Comput. 37(1), 55–69 (1996)CrossRef
5.
Zurück zum Zitat Chen, C., Manzano, J.B., Gan, G., Gao, G.R., Sarkar, V.: A study of a software cache implementation of the OpenMP memory model for multicore and manycore architectures. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010. LNCS, vol. 6272, pp. 341–352. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15291-7_31 CrossRef Chen, C., Manzano, J.B., Gan, G., Gao, G.R., Sarkar, V.: A study of a software cache implementation of the OpenMP memory model for multicore and manycore architectures. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010. LNCS, vol. 6272, pp. 341–352. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15291-7_​31 CrossRef
6.
Zurück zum Zitat Culler, D.E., Karp, R.M., Patterson, D., et al.: LogP: a practical model of parallel computation. Commun. ACM 39(11), 78–85 (1996)CrossRef Culler, D.E., Karp, R.M., Patterson, D., et al.: LogP: a practical model of parallel computation. Commun. ACM 39(11), 78–85 (1996)CrossRef
7.
Zurück zum Zitat Dennis, J.B.: Programming generality, parallelism and computer architecture. Inf. Process. 68, 484–492 (1969)MATH Dennis, J.B.: Programming generality, parallelism and computer architecture. Inf. Process. 68, 484–492 (1969)MATH
9.
Zurück zum Zitat Dennis, J.B.: A parallel program execution model supporting modular software construction. In: Proceedings of the 1997 Working Conference on Massively Parallel Programming Models, MPPM 1997, pp. 50–60. IEEE, Los Alamitos (1997) Dennis, J.B.: A parallel program execution model supporting modular software construction. In: Proceedings of the 1997 Working Conference on Massively Parallel Programming Models, MPPM 1997, pp. 50–60. IEEE, Los Alamitos (1997)
10.
Zurück zum Zitat Dennis, J.B., Gao, G.R.: An efficient pipelined dataflow processor architecture. In: Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, SC 1988, pp. 368–373. IEEE Computer Society Press, Florida (1988) Dennis, J.B., Gao, G.R.: An efficient pipelined dataflow processor architecture. In: Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, SC 1988, pp. 368–373. IEEE Computer Society Press, Florida (1988)
11.
Zurück zum Zitat Dennis, J.B., Misunas, D.P.: A preliminary architecture for a basic data-flow computer. In: Proceedings of the 2nd Annual Symposium on Computer Architecture, pp. 126–132. IEEE Press, New York (1975) Dennis, J.B., Misunas, D.P.: A preliminary architecture for a basic data-flow computer. In: Proceedings of the 2nd Annual Symposium on Computer Architecture, pp. 126–132. IEEE Press, New York (1975)
12.
Zurück zum Zitat Dennis, J.B.: Fresh breeze: a multiprocessor chip architecture guided by modular programming principles. ACM SIGARCH Comput. Archit. News 31(1), 7–15 (2003)CrossRef Dennis, J.B.: Fresh breeze: a multiprocessor chip architecture guided by modular programming principles. ACM SIGARCH Comput. Archit. News 31(1), 7–15 (2003)CrossRef
13.
Zurück zum Zitat Dennis, J.B., Fosseen, J.B., Linderman, J.P.: Data flow schemas. In: Ershov, A., Nepomniaschy, V.A. (eds.) International Symposium on Theoretical Programming. LNCS, vol. 5, pp. 187–216. Springer, Heidelberg (1974). doi:10.1007/3-540-06720-5_15 CrossRef Dennis, J.B., Fosseen, J.B., Linderman, J.P.: Data flow schemas. In: Ershov, A., Nepomniaschy, V.A. (eds.) International Symposium on Theoretical Programming. LNCS, vol. 5, pp. 187–216. Springer, Heidelberg (1974). doi:10.​1007/​3-540-06720-5_​15 CrossRef
14.
Zurück zum Zitat Dennis, J.B., Van Horn, E.C.: Programming semantics for multiprogrammed computations. Commun. ACM 9(3), 143–155 (1966)CrossRefMATH Dennis, J.B., Van Horn, E.C.: Programming semantics for multiprogrammed computations. Commun. ACM 9(3), 143–155 (1966)CrossRefMATH
15.
Zurück zum Zitat Dubois, M., Scheurich, C., Briggs, F.: Memory access buffering in multiprocessors. ACM SIGARCH Comput. Architect. News 14(2), 434–442 (1986)CrossRef Dubois, M., Scheurich, C., Briggs, F.: Memory access buffering in multiprocessors. ACM SIGARCH Comput. Architect. News 14(2), 434–442 (1986)CrossRef
16.
Zurück zum Zitat Eckert Jr., J.P., Mauchly, J.W.: Automatic high-speed computing: a progress report on the EDVAC. Report of Work under Contract No. W-670-ORD-4926, Supplement (1945) Eckert Jr., J.P., Mauchly, J.W.: Automatic high-speed computing: a progress report on the EDVAC. Report of Work under Contract No. W-670-ORD-4926, Supplement (1945)
17.
Zurück zum Zitat Gao, G.R.: An efficient hybrid dataflow architecture model. J. Parallel Distrib. Comput. 19(4), 293–307 (1993)CrossRefMATH Gao, G.R.: An efficient hybrid dataflow architecture model. J. Parallel Distrib. Comput. 19(4), 293–307 (1993)CrossRefMATH
18.
Zurück zum Zitat Gao, G.R., Hum, H.H.J., Monti, J.-M.: Towards an efficient hybrid dataflow architecture model. In: Aarts, E.H.L., Leeuwen, J., Rem, M. (eds.) PARLE 1991. LNCS, vol. 505, pp. 355–371. Springer, Heidelberg (1991). doi:10.1007/BFb0035115 CrossRef Gao, G.R., Hum, H.H.J., Monti, J.-M.: Towards an efficient hybrid dataflow architecture model. In: Aarts, E.H.L., Leeuwen, J., Rem, M. (eds.) PARLE 1991. LNCS, vol. 505, pp. 355–371. Springer, Heidelberg (1991). doi:10.​1007/​BFb0035115 CrossRef
19.
Zurück zum Zitat Gao, G.R., Tio, R., Hum, H.H.: Design of an efficient dataflow architecture without data flow. In: Proceedings of the International Conference on Fifth Generation Computer Systems, FGCS 1988 (1988) Gao, G.R., Tio, R., Hum, H.H.: Design of an efficient dataflow architecture without data flow. In: Proceedings of the International Conference on Fifth Generation Computer Systems, FGCS 1988 (1988)
20.
Zurück zum Zitat Gao, G.R., Sarkar, V.: Location consistency – a new memory model and cache consistency protocol. IEEE Trans. Comput. 49(8), 798–813 (2000)CrossRef Gao, G.R., Sarkar, V.: Location consistency – a new memory model and cache consistency protocol. IEEE Trans. Comput. 49(8), 798–813 (2000)CrossRef
21.
Zurück zum Zitat Gao, G.R., Suetterlein, J., Zuckerman, S.: Toward an execution model for extreme-scale systems-runnemede and beyond. CAPSL Technical Memo 104 (2011) Gao, G.R., Suetterlein, J., Zuckerman, S.: Toward an execution model for extreme-scale systems-runnemede and beyond. CAPSL Technical Memo 104 (2011)
22.
Zurück zum Zitat Garcia, E., Orozco, D., Gao, G.R.: Energy efficient tiling on a many-core architecture. In: Proceedings of 4th Workshop on Programmability Issues for Heterogeneous Multicores, MULTIPROG 2011; 6th International Conference on High-Performance and Embedded Architectures and Compilers, HiPEAC 2011, pp. 53–66, Heraklion (2011) Garcia, E., Orozco, D., Gao, G.R.: Energy efficient tiling on a many-core architecture. In: Proceedings of 4th Workshop on Programmability Issues for Heterogeneous Multicores, MULTIPROG 2011; 6th International Conference on High-Performance and Embedded Architectures and Compilers, HiPEAC 2011, pp. 53–66, Heraklion (2011)
23.
Zurück zum Zitat Gharachorloo, K., Lenoski, D., Laudon, J., et al.: Memory consistency and event ordering in scalable shared-memory multiprocessors. In: Proceedings of the 25th International Symposium on Computer Architecture, ISCA 1998, pp. 376–387. ACM, Barcelona (1998) Gharachorloo, K., Lenoski, D., Laudon, J., et al.: Memory consistency and event ordering in scalable shared-memory multiprocessors. In: Proceedings of the 25th International Symposium on Computer Architecture, ISCA 1998, pp. 376–387. ACM, Barcelona (1998)
24.
Zurück zum Zitat Hemmerling, A.: Systeme von Turing-Automaten und Zellularräume auf rahmbaren pseudomustermengen. Elektronische Informationsverarbeitung und Kybernetik 15(1/2), 47–72 (1979)MathSciNetMATH Hemmerling, A.: Systeme von Turing-Automaten und Zellularräume auf rahmbaren pseudomustermengen. Elektronische Informationsverarbeitung und Kybernetik 15(1/2), 47–72 (1979)MathSciNetMATH
25.
Zurück zum Zitat Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, San Francisco (2011)MATH Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, San Francisco (2011)MATH
26.
Zurück zum Zitat Humy, H.H., Maquelin, O., Theobald, K.B., et al.: A design study of the EARTH multiprocessor. In: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, PACT 1995, pp. 59–68, Limassol (1995) Humy, H.H., Maquelin, O., Theobald, K.B., et al.: A design study of the EARTH multiprocessor. In: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, PACT 1995, pp. 59–68, Limassol (1995)
27.
Zurück zum Zitat Iannucci, R.A.: Toward a dataflow/von Neumann hybrid architecture. ACM SIGARCH Comput. Architect. News 16(2), 131–140 (1988)CrossRef Iannucci, R.A.: Toward a dataflow/von Neumann hybrid architecture. ACM SIGARCH Comput. Architect. News 16(2), 131–140 (1988)CrossRef
28.
Zurück zum Zitat Ito, T.: Synchronized alternation and parallelism for three-dimensional automata. Ph.D. thesis. University of Miyazaki (2008) Ito, T.: Synchronized alternation and parallelism for three-dimensional automata. Ph.D. thesis. University of Miyazaki (2008)
29.
Zurück zum Zitat Ito, T., Sakamoto, M., Taniue, A., et al.: Parallel Turing machines on four-dimensional input tapes. Artif. Life Rob. 15(2), 212–215 (2010)CrossRef Ito, T., Sakamoto, M., Taniue, A., et al.: Parallel Turing machines on four-dimensional input tapes. Artif. Life Rob. 15(2), 212–215 (2010)CrossRef
31.
Zurück zum Zitat Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRefMATH Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRefMATH
32.
Zurück zum Zitat Lauderdale, C., Khan, R.: Position paper: towards a codelet-based runtime for exascale computing. In: Proceedings of the 2nd International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era, EXADAPT 2012, pp. 21–26. ACM, London (2012) Lauderdale, C., Khan, R.: Position paper: towards a codelet-based runtime for exascale computing. In: Proceedings of the 2nd International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era, EXADAPT 2012, pp. 21–26. ACM, London (2012)
33.
34.
Zurück zum Zitat Mattson, T., Cledat, R., Budimlic, Z., et al.: OCR: the open community runtime interface version 1.1.0 (2015) Mattson, T., Cledat, R., Budimlic, Z., et al.: OCR: the open community runtime interface version 1.1.0 (2015)
35.
Zurück zum Zitat McCarthy, J.: LISP 1.5 programmer’s manual (1965) McCarthy, J.: LISP 1.5 programmer’s manual (1965)
36.
Zurück zum Zitat Okinaka, K., Inoue, K., Ito, A.: A note on hardware-bounded parallel Turing machines. In: Proceedings of the 2nd International Conference on Information, pp. 90–100, Beijing (2002) Okinaka, K., Inoue, K., Ito, A.: A note on hardware-bounded parallel Turing machines. In: Proceedings of the 2nd International Conference on Information, pp. 90–100, Beijing (2002)
37.
Zurück zum Zitat Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society, pp. 230–265, London (1936) Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society, pp. 230–265, London (1936)
38.
Zurück zum Zitat Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)CrossRef Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)CrossRef
39.
40.
Zurück zum Zitat Wiedermann, J.: Parallel Turing machines. Research Report (1984) Wiedermann, J.: Parallel Turing machines. Research Report (1984)
42.
Zurück zum Zitat Wirth, N.: Modula: a language for modular multiprogramming. Softw. Pract. Experience 7(1), 3–35 (1977)MathSciNetMATH Wirth, N.: Modula: a language for modular multiprogramming. Softw. Pract. Experience 7(1), 3–35 (1977)MathSciNetMATH
43.
Zurück zum Zitat Zuckerman, S., Suetterlein, J., Knauerhase, R., et al.: Using a codelet program execution model for exascale machines: position paper. In: Proceedings of the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era, EXADAPT 2011, pp. 64–69. ACM, San Jose (2011) Zuckerman, S., Suetterlein, J., Knauerhase, R., et al.: Using a codelet program execution model for exascale machines: position paper. In: Proceedings of the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era, EXADAPT 2011, pp. 64–69. ACM, San Jose (2011)
Metadaten
Titel
Toward a Parallel Turing Machine Model
verfasst von
Peng Qu
Jin Yan
Guang R. Gao
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-47099-3_16