Porównanie architektury klasycznej (SISD) i równoległej (SIMD)

· blog
Authors

Przede wszystkim wspomnę, nim zapomnę, że automat komórkowy von Neumanna-Ulama jest geometrycznym SIMD systemem, wykonującym (iterującym w kółko) jedną i tę samą instrukcję czyli operację na obrazie (powiedzmy 100 milionów razy na sekundę). Output każdego wykonania operacji, cyklu, zastępuje input, stając się inputem dla następnego cyklu).


Przewagą klasycznego komputera jest przyzwyczajenie, elastyczność, i łatwość programowania na wszelakie sposoby. W przypadku SIMD, dla wydajnego procesowania, programista (algorytmista) musi głębiej zdawać sobie sprawę z natury danych. W przypadku obrazów, danych jako dwuwymiarowe tablice “punktów”, na ogół programista rozpisuje wszelakie pętle po punktach, przy czym, powiedzmy w przypadku koloru zielonego, punkt po punkcie rozpatrywane są liczby (8-bitowe liczby całkowite) kolejnych punktów, odpowiadające intensywności zielonego w każdym z punktów. W przypadku SIMD na ogół główna pętla przebiego od najmniej ważnego bitu zieloności wszystkich punktów, aż po bit najważniejszy (czasem w przeciwną stronę: od najważniejszego do najmniej ważnego); zamiast jednej 8-bitowej tabeli liczb zielonych rozpatruje się osiem tabel 1-bitowych. Czasem (często?) takie podejście algorytmiczne ma przewagą nad tradycyjnym nawet, gdy algorytm lata na klasycznym komputerze, dostaje się szybszy algorytm! Programowanie jest jednak wtedy trudniejsze. Należy bazę danych zorganizować według płaszczyzn bitowych, a nie według punktów czy innych records (i dopiero 1-bitowe płaszczyzny są zorganizowane według punktów lub jakie by records nie były).

Zauważmy, że nawet klasyczny komputer, powiedzmy 64-bitowy, jest w pewnym stopniu SIMD, jako że można na nim równolegle (czyli jednocześnie) dokonywać 64 operacji 1-bitowych na bitach od jednego do trzech registrów. Wykorzystywałem to na całego do super-szybkich symulacji GAPPa na 32-bitowych komputerach VAX i PeCetach.


Poznaliśmy przewagę klasycznej architektury nad SIMD. Jedną jedyną, ale wystarczyła, by SIMD w zasadzie z PeCetami przegrały wyścig sromotnie. Jednak SIMD komputer (zwłaszcza geometryczny SIMD) ma swoje zalety, tak że wyścig nie jest jeszcze zakończony. Powinien zakończyć się symbiozą, co objaśnię później.

W przybliżeniu zachodzi zdrowo-rozsądkowy wzór (prawo 🙂 )

wydajność komputera

=  (szybkość obliczeń) / (koszt hardware’owy)

=  (ilość obliczeń) / (czas * (koszt hardware’owy))

Wynika z powyższego wzoru konieczność maksymalnego wykorzystania hardware’u w każdym momencie. W przypadku architektuty klasycznej, ALU ma wiele wyspecjalizowanych modułów, które przez większość czasu nic nie robią. Oznacza to marnotrawstwo (niską wydajność). Pokazuje też ta obserwacja, że wydajniejsze są zgrabne komponenty ogólne, zawsze przydatne, od kompopnent wyspecjalizowanych. Jednak żeby komponenta była uniwersalna (i wydajna), to musi być prosta, co oznacza wyższe wymagania względem programisty/algorytmisty lub – by było znacznie lepiej – systemu oprogramowania.


W przypadku klasycznej architektury, gdy zamiast jednego obliczenie chcemy jednocześnie dokonać dwóch, to zamiast jednego komputera potrzeba dwóch, czyli dwa kontrolery, dwa ALU, i dwie pamięci – wszystko podwójnie. W przypadku SIMD, na ogół można użyć ten sam kontroler, a powiększa się jedynie wymiary xy procesora równoległego (podwaja się liczbę komórek).

Ogólnie, w przypadku SIMD jeden kontroler dyryguje całą armią setek tysięcy malutkich procesorów; w przypadku klasycznym, jeden kontroler dyryguje jednym procesorem – o wiele potężniejszym, ale tylko jednym (którego złożoność nie tłumaczy się proporcjonalnie na wydajność w przypadku intensywnych obliczeń, które operują na wielkiej bazie danych).


Klasyczny komputer, by dorównać SIMD, musiałby mieć procesor setki tysięcy razy szybszy od procesora pojedynczej komórki systemu SIMD. Jednak w przypadku bardzo prostych, a często spotykanych obliczeń może on być wręcz wolniejszy nawet od pojedynczego procesora pojedynczej komórki (lub mogą mieć porównywalną szybkość). Porównanie architektur zależy od rodzaju zastosowań. Z tym, że programiści często nie podejrzewają skrytych możliwości podejścia geometrycznego SIMD.

Dlaczego potężne ALU może być wolniejsze od mikrusa? Tak jak Herakles nie musi być szybszy od brzdąca, gdy trzeba przewlekać nitkę przez ucho igielne. Mięśnie mogą nawet przeszkadzać.


Patrząc na świat obliczeń z dystansu, uważam, że gdy problem ma wielkiego rozmiaru input, oraz podobnego – output, to główną część obliczeń powinien najefektywniej wykonać geometryczny system typu SIMD. Wyzwaniem jest znalezienie efektywnego programu. Jest to według mnie możliwe dlatego, że w praktyce nawet nie jesteśmy w stanie sformułować tak złożonych zadań, żeby nie poddały się regularnemu podejściu. Zwłaszcza, że dla zastosowań nie jest koniecznym rozwiązać zadanie dokładnie tak, jak się problem sformułowało. Ba, mówiąc nieco filozoficznie, na ogół dokładne sformułowanie problemu w praktyce nawet nie istnieje. Po zastanowieniu się, zawsze problem można formułować na szereg zupełnie nierównoważnych obliczeniowo sposobów, ale równoważnych pod kątem zastosowania.

Przy procesowaniu obrazów rzeczywiście mamy wielki input (obraz) i wielki output (znowu obraz). W innych zastosowaniach input może być wielki, ale za output chcemy tylko jeden bit TAK/NIE. Takie problemy efektywnie powinien rozwiązywać system typu piramidy, zaczynający się od geometrycznego SIMD o wielkim rozmiarze (i o bardzo prostych komórkach), i prowadzący poprzez kolejne geometryczne SIMD podsystemy (o coraz bardziej złożonych komórkach), o coraz mniejszym wymiarze xy, aż do klasycznego komputera (jakby SIMD zdegenerowane do wymiaru 1 na 1). System ten stopniowo redukowałby wymiar geometryczny kolejnych stadiów obliczeń.

UWAGA: W różnych zastosowaniach do matematyki i fizyki, sieć komórek systemu SIMD może modelować układy, które niekoniecznie są płaskie. Więcej o tym w następnych postach.

W następnych odcinkach będę już prezentował bardziej techniczny materiał.

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: