Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
VIOS: A Variation-Aware I/O Scheduler for Flash-Based Storage Systems Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Toward a Parallel Turing Machine Model

Authors : Peng Qu, Jin Yan, Guang R. Gao

Published in: Network and Parallel Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter QIM: Quantifying Hyperparameter Importance for Deep Learning
next chapter On Determination of Balance Ratio for Some Tree Structures
Footnotes
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.
 
Literature
1.
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.
van Boas, P.E.: Machine models and simulations. Handb. Theor. Comput. Sci. A, 1–66 (2014)MATH
3.
Bouknight, W.J., Denenberg, S.A., McIntyre, D.E., et al.: The Illiac IV system. Proc. IEEE 60(4), 369–388 (1972)CrossRef
4.
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.
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.
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.
Dennis, J.B.: Programming generality, parallelism and computer architecture. Inf. Process. 68, 484–492 (1969)MATH
8.
9.
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.
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.
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.
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.
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.
Dennis, J.B., Van Horn, E.C.: Programming semantics for multiprogrammed computations. Commun. ACM 9(3), 143–155 (1966)CrossRefMATH
15.
Dubois, M., Scheurich, C., Briggs, F.: Memory access buffering in multiprocessors. ACM SIGARCH Comput. Architect. News 14(2), 434–442 (1986)CrossRef
16.
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.
Gao, G.R.: An efficient hybrid dataflow architecture model. J. Parallel Distrib. Comput. 19(4), 293–307 (1993)CrossRefMATH
18.
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.
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.
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.
Gao, G.R., Suetterlein, J., Zuckerman, S.: Toward an execution model for extreme-scale systems-runnemede and beyond. CAPSL Technical Memo 104 (2011)
22.
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.
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.
Hemmerling, A.: Systeme von Turing-Automaten und Zellularräume auf rahmbaren pseudomustermengen. Elektronische Informationsverarbeitung und Kybernetik 15(1/2), 47–72 (1979)MathSciNetMATH
25.
Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, San Francisco (2011)MATH
26.
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.
Iannucci, R.A.: Toward a dataflow/von Neumann hybrid architecture. ACM SIGARCH Comput. Architect. News 16(2), 131–140 (1988)CrossRef
28.
Ito, T.: Synchronized alternation and parallelism for three-dimensional automata. Ph.D. thesis. University of Miyazaki (2008)
29.
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
30.
31.
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRefMATH
32.
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.
Mattson, T., Cledat, R., Budimlic, Z., et al.: OCR: the open community runtime interface version 1.1.0 (2015)
35.
McCarthy, J.: LISP 1.5 programmer’s manual (1965)
36.
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.
Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society, pp. 230–265, London (1936)
38.
Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)CrossRef
39.
40.
Wiedermann, J.: Parallel Turing machines. Research Report (1984)
41.
42.
Wirth, N.: Modula: a language for modular multiprogramming. Softw. Pract. Experience 7(1), 3–35 (1977)MathSciNetMATH
43.
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)
Metadata
Title
Toward a Parallel Turing Machine Model
Authors
Peng Qu
Jin Yan
Guang R. Gao
Copyright Year
2016
Book
Network and Parallel Computing

Print ISBN: 978-3-319-47098-6

Electronic ISBN: 978-3-319-47099-3

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-47099-3_16

Premium Partner

    Image Credits