Procesowanie równoległe dla szerokiej publiki

· blog
Authors

(Powróciłem do wordpress, bo poprzednią, szerszą wersję poniższej notki wcięło mi, gdy pisałem wprost w buzzie – naraz Mac się sam wyłączył, akurat gdy tekst zakończyłem, i klops. KLOPS!)

Nie chodzi o prowadzenie sprawy sądowej równolegle, jednocześnie, jednej przeciwko teściowej, drugiej – przeciwko szefowi w pracy. Chodzi o jednoczesne, liczne wyliczenia, do wykonania których służy system SIMD – Single Instruction, Multiple Data (każda pojedyncza instrukcja wykonywana jest na licznych danych jednocześnie). SIMD jest tylko jednym z podejść do procesowania równoległego; właśnie na nim się skupię.

Zacznijmy od von Neumanna. Z jednej strony był jednym z głównych twórców klasycznej architektury komputerowej, często zwanej architekturą von Neumanna. Z drugiej strony, po wprowadzeniu przez Ulama błyskotliwej i podstawowej definicji automatu wielokomórkowego, właśnie von Neumann rozwinął jego teorię. Celem była analiza pojęcia życia. Von Neumann pojął czym życie różni się od martwoty! Po pierwsze, żywy organizm potrzebuje środowiska bogatego w odżywcze (choć na ogół martwe) elementy. Po drugie, taki organizm, żeby zasługiwać na bycie żywym, musi być złożony, czyli musi zawierać uniwersalną maszynę Turinga (jest ich wiele różnych); wreszcie po trzecie, musi mieć zdolność rozmnażania się. Von Neumann myślał o inżynieryjnym rozwiązaniu, o jakimś inżynieryjnym wodnym organiźmie, z monstrualnym ramieniem, wyłapującym z wody proste składniki, i budującym swojego następcę według tabliczki z przepisem, która to tabliczka byłaby częścią organizmu naszego inżynieryjnego stworzenia. Ponieważ środowisko jest bogate, to unoszą się w nim różne duperele, a między innymi takie tabliczki. Przez wmontowanie kopii tabliczki w następcę (zgodnie z przepisem zapisanym w samej tabliczce), ten następca znowu by produkował swojego następcę, według swojej kopii tego samego przepisu, dokładnie tak, jak to uczynił jego rodzic. Czysty geniusz(!) ten von Neumann. Ale technologia, która by umożliwiła zbudowanie takiego inżynieryjnego, żywego organizmu, nie istniała. Tu wtrącił się błyskotliwie Stan Ulam, który jakby powiedział: pal licho inżynierię!, i zaproponował symulację matematyczną czyli automat komórkowy. 1-wymiarowe były za proste, by symulować życie, a 3-wymiarowe – przesadnie ciężkie, skomplikowane. Więc, bardzo zajęty różnymi obowiązkami, von Neumann skupił się na 2-wymiarowych, i nim umarł, to projekt doprowadził niemal do końca – jest opisany w monografiach. Jego konstrukcja była naturalna, więc ciężkawa. Z czasem specjaliści uzyskali znacznie prostsze rozwiązania – żywe automaty (w sensie von Neumanna). Doceńcie geniusz von Neumanna, który pojął zagadkę życia!!! Życie polega na zanurzeniu meta-materii w materii, na ich zrównaniu: tabliczka z jednej strony jest materialną częścią życia, a z drugiej jest opisem życia, czyli jest meta-materialna. W biologii ta tabliczka to DNA.

Gdy cwaniaki z Columbia Uniwersity nazwały swoją głupią architekturę równoległą – nonVon, to czułem się tym zniesmaczony, byłem oburzony. Wbrew brzydkiemu pomówieniu wielkiego człowieka przez tych malutkich z Columbia, John von Neumann doceniał potencjał paralellizmu, dobrze go rozumiał. Jedynie stwierdził, że na danym etapie technologii (kiedy to konstruktorzy komputerów mieli do dyspozycji tylko LAMPY elektronowe) rozwiązania równoległe były nierealne, mało efektywne.


Klasyczny komputer był jak dziwna armia, skłądająca sie z jednego generała, z jednego super-komandosa, oraz z magazynu. W informatyce i w języku komputerowego hardware, nazywani oni są odpowiednio kontroler (generał), ALU (Aruthmetic-Logical Unit, czyli super-komandos), i pamięć (magazyn; łącznie z _portami_ – dla komunikowania się ze światem zewnętrznym). Na ogół ta pamięć, to RAM plus szereg registrów (łącznie z portami). Większość informatyków i programistów lubi taką armię, bo łatwo jest dyrygować, poprzez generała, za pomocą złożonych instrukcji, super-komandosem.

Natomast SIMD system przypomina regularną armię. Dalej ma tylko jednego generała, ale ma wielu, nawet setki tysięcy, szeregowych, z których każdy ma własny magazyn. Generał wykrzykuje jeden po drugim rozkazy (instrukcje), a szeregowi, w sposób zsynchronizowany z tempem generała, wszyscy jednocześnie instrukcje po instrukcji wykonują, coś tam manipulując w swoim magazynie (w przypadku geometrycznym – najważniejszym – szeregowcy także przekazują jedni drugim dane; napiszę o tym sporo w przyszłych notkach). Wszyscy szeregowi są tacy sami, i mają takie same magazyny. Więc mogą się wszyscy stosować do jednej i tej samej instrukcji generała (kontrolera). Jednak efekt tej samej instrukcji w różnych komórkach, złożonych z szeregowego i jego magazynu, jest różny, gdyż zależny jest on od zawartości magazynu – a ta mogła być różna w momencie startu programu.

W następnej naiwnej nocie wymienię przewagi SIMD nad architekturą kalsyczną, mimo że dziś klasyczna wygrała z SIMD w 90%. Nie w 100%, bo równoległość wkradła się do środka klasycznych komputerów, a raczej ich następców w prostej linni, jak te wszystkie PeCety, Macs i stacje. Z czystych geometrycznych SIMD konkurencję komercjalnie przeżył tylko następca mojego GAPP. Powód przegranej SIMD nie jest jednak w pełni obiektywny, jest przypadkowo-ewolucyjny.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  1. WhoWheWha (in progress)
  2. The sharpest minds ever
  3. California – State – USA – Knol Authors – Knols – Education
  4. Money — economy (part 1)
  5. “california rains”
  6. Pairs, Kuratowski pairs, and reality
  7. Number Theory — congruences
  8. Matematyka – esej
  9. Congruence x^2 ≡ -1 mod p (Euler), and a super-Wilson theorem.
  10. Dabanese – dictionary (1)
  11. Dabanese syntax
  12. Dabanese — a general introduction
  13. Tentative dabanese dictionary (1)
  14. Fractions and diophantine approximations, I
  15. Mathematics — index
  16. Reflections on mathematics (migma)
  17. Special characters & HTML strings
  18. Infinitude of primes – 1
  19. Reference
  20. Geometric progression
  21. Ergänzungssatz: x^2 ≡ 2 mod p; and more.
  22. Primes in arithmetic progressions (part I)
  23. Euler introduction to Gauss quadratic reciprocity
  24. Trigonometry of a triangle–sinus & cosinus
  25. Wlodzimierz Holsztynski, knolog
  26. Tichonov product
  27. Factorization in semigroups
  28. Nowe knole
  29. Knole w języku polskim
  30. Metric spaces — introduction
  31. Topology — compact spaces II
  32. Topology–singular spaces
  33. the last summer concert in san jose
  34. California in poetry
  35. threeway
  36. san jose blues
  37. san francisco blues
  38. open your arcs
  39. Tom Wachtel, [I was running out of …]
  40. Tom Wachtel, [on the sand at…]
  41. “september”
  42. Topological sequences and convergence
  43. Topology–Arkhangelskii nets
  44. Topology–compact spaces I
  45. Topological product of two spaces. Hausdorff spaces.
  46. Trigonometry
  47. Total logarithmic series
  48. “affinity”
  49. [close your eyes…]
  50. “San Jose”
  51. willow girl
  52. heaven california
  53. “phase transitions”
  54. “california?”
  55. “dimensions”
  56. bachelor life
  57. “spring in california”
  58. [day -]
  59. Singular product of two spaces. Double limit.
  60. Art of Agreeing — painless tax
  61. The Birkhoff lattice of topologies
  62. Left topologies
  63. Topology — Kolmogorov axiom
  64. Topological subbases and bases
  65. Complexity of sorting
  66. ∞-Metrics
  67. Even perfect numbers and Mersenne primes
  68. Fermat sequence base b
  69. Harmonic series & Euler’s gamma
  70. 4-Baroque numbers with utmost 4 different prime divisors
  71. 3-Baroque numbers with utmost 3 different prime divisors
  72. Mathematical notation
  73. Baroque numbers – 2
  74. Number theory — ideals in Z, and the greatest common divisor
  75. Baroque numbers – 1
  76. Infinitude of primes – 2
  77. Number theory — Gothic numbers
  78. log and exp–a constructive and an axiomatic approaches
  79. Aleksandrov 2-point space
  80. Topology — short-short introduction
  81. Art of Agreeing — patent law
  82. Topology — the closure operation
  83. Integration of monotone functions
  84. The ground level properties of integral
  85. Metric spaces universal for 2-point spaces
  86. Products of bounded primes
  87. Sequences of pairwise coprime integers
  88. Mathematics — right triangles
  89. Art of Agreeing — United Nations
  90. Mathematics — two definitions
  91. Government wa(steful wa)ys
  92. Art of Agreeing — index
  93. Metric universality of (R^n d_m) — part 2
  94. Iso-graphs of metric maps into R (part 1)
  95. Metric universality of (R^n d_m) — part 1
  96. Metric spaces universal for 3- and 4-point spaces
  97. Number theory–units, composites, and primes
  98. Social life & energy saving
  99. Topological spaces and continuous mappings. Isolated points.
  100. Topological weight
  101. Mathematics — Euclid-Heron area of a triangle
  102. Connected spaces
  103. Art of Agreeing — marriage versus law & government
  104. Art of Agreeing — introduction
  105. Dabanese — index
  106. Linear orders in topological spaces
  107. Topological cuts and miscuts
  108. Closed sets. T1-spaces.
  109. Topology — the interior operation
  110. Mathematics — triangles
  111. Continuity of the piecewise continuous functions
  112. Topological subspaces
  113. Art of Agreement — medical insurance
  114. Art of Agreeing — business & stock market
%d bloggers like this: