Upgrade to Pro — share decks privately, control downloads, hide ads and more …

近未来的並列 LL

近未来的並列 LL

Forecast on the near future programming paradigm, issues, and challenges in parallel processing.
Movie: http://vimeo.com/29903448

At LL Tiger, Jul, 2010.

Motohiro Takayama

January 28, 2012
Tweet

More Decks by Motohiro Takayama

Other Decks in Programming

Transcript

  1. @mootoh ߴࢁ ੐େ ฒྺ 5೥ ࠷ۙ͸ ݚڀऀ : ΤϯδχΞ =

    7:3 http://deadbeaf.org ݸਓͷҙݟɺݟղͰ͢
  2. ͸͡Ίʹ mootoh ฒྻϓϩάϥϛϯάͷೖ໳ˍ͓͞Β͍తͳ࿩ wraith13 ϩʔϨΠϠʔͰͷฒྻॲཧͷઃܭ goyoki STM hayamiz ฒྻ HPU

    ݴޠ MUDA syoyo ϚϧνίΞ࣌୅ͷ Lock-free ೖ໳ yamasa Haskell पΓ shelarcy ͦͷଞ ???
  3. ଴ͪ࣌ؒ •ྫ: Eclipse.app Λىಈ͢Δ࣌ؒ • on iMac Core 2 Duo

    3GHz 4GB RAM • ॳճ: 33s, 2ճ໨Ҏ߱: 7s (628,702ਓ * 33s * 365೔) / (60 * 60 * 24 * 30) => 2,921 ਓ݄/೥
  4. •Native thread • 5.6 ͔Β ithread • thread ͝ͱʹ VM

    • default Ͱ shared nothing •6.0 ͔Β STMͳͲͨ͘͞Μ •ϥΠϒϥϦ • POE, AnyEvent, Coro, ...
  5. •Native & green thread (࣮૷ʹΑΔ) • ruby1.8: green • ruby1.9:

    native, GIL ͋Γ • JRuby, MacRuby: native, GIL ͳ͠ \o/ •ϥΠϒϥϦ • Revactor, EventMachine, NeverBlock, ...
  6. •Thread • CPython: GVL ͋Γ • Jython, IronPython : ͳ͛͞

    • Jython: system 216% cpu 12.285 total
  7. ݱঢ়·ͱΊ Perl Ruby Python PHP Haskell Erlang Scala go Javascript

    Native thread ˕ ˚ ˚ × ̋? ˕ ˕ ˕ ̋? Model, Paradigm Thread, STM Thread, Fiber Thread Process STM ͍͢͝Կ͔ Message Passing Thread, Message Passing Message Passing Message Passing ಛهࣄ߲ shared- nothing by default ݚڀ೤৺ ϚϧνίΞ Ͱ΋ Ϋϥελ Ͱ΋ ͍͍ͱ͜ ͲΓ goroutine Web Workers
  8. λεΫΩϡʔ •ฒྻʹ࣮ߦ͍ͨ͠λεΫΛ ͲΜͲΜΩϡʔʹͭͬ͜Ή • :) ෼͔Γ΍͍͢ • :( ґଘؔ܎͕͋Δͱ...? •ྫ:

    • Grand Central Dispatch → Mac • Java 7 → JVM ϕʔεͷॲཧܥ • OpenCL http://en.wikipedia.org/wiki/File:Gcd_icon20090608.jpg http://www.khronos.org/opencl/ http://images.apple.com/macosx/technology/docs/ GrandCentral_TB_brief_20090903.pdf
  9. σʔλϑϩʔ • ґଘؔ܎Λͭͳ͙ • ඞཁͳσʔλ͕ͦΖͬͨΒɺࣗಈతʹ࣍ͷॲཧʹਐΉ • Out of Order •

    Future ύλʔϯ • ౤͛ͬͺͳ͠δϟʔϚϯ • ผεϨουʹܭࢉͤ͞ͱ͍ͯɺࣗ෼͸ͦͷ··࣮ߦΛܧଓ • ผεϨου͕ऴΘͬͨΒ௨஌Λ΋Β͏ : value resolved : value not resolved yet : executable Atom : pending Atom
  10. Mol • એݴతɺσʔλϑϩʔ • ͍͍ͪͪಉظॻ͔ͳ͍ • Atom (௚ྻίʔυ) Λ஗Ԇฒྻ࣮ߦɺϝϞԽ •

    C Έ͍ͨͳ Haskell Έ͍ͨͳ ฒྻ DSL main() { frame(frame_no, input) { local loop; local edge[-1..9] outside(0); local pocs[-1..9] outside(0); local ccr [-1..9] outside(0); loop = loop_count(); edge[i] := edge_atom(input, i); ccr [i] := ccr_atom(edge[i-1], edge[i], edge[i+1], i); pocs[i] := i % 2 == 0 ? pocs_even_atom(ccr [i-1], ccr[i], ccr [i+1], loop, i) : pocs_odd_atom (pocs[i-1], ccr[i], pocs[i+1], loop, i); return &pocs; } sync for (i in [0..30]) put_frame_atom(frame(i, get_frame_atom())); }
  11. Runtime •֤ίΞʹ VM ͕͍Δ •͕͜͜ΩϞ Runtime Atom Waiting Atom Shared

    Memory Global Lock Runtime Context waiting for runtime lock arguments, return value update runtime context Mol Atom Wait ଓ͖͸࿦จͰ
  12. FAQ •ͦΜͳͨ͘͞Μ͋ͬͯԿʹ࢖͏ͷ? P = f V^2 1MHz ͕ 1000 ίΞ

    → 1GHz ฒͷੑೳ͕! ిݯ೉ຽ໰୊Λղܾ http://www.speedia.co.jp/~namisato/2008_05.html
  13. Memory Wall •༰ྔ͕૿͑ͳ͍ •ిؾΛ৯͏ •ଳҬ͕଍Γͳ͍ • 100ίΞΛ௒͑Δͱμϝ͛ • by “Can

    Manycores Support the Memory Requirements of Scientific Applications?” / A4MMC 2010
  14. Memory Wall •ڞ༗ϝϞϦ → ෼ࢄϝϞϦ •ྫ: Intel SCC • ڞ༗ϝϞϦ஗͍

    • ϝοηʔδύογϯά ͷ HW ͕͋Δ http://techresearch.intel.com/articles/Tera-Scale/1826.htm
  15. ϝοηʔδύογϯά •Actor Ϟσϧ • Erlang, Scala, go, Javascript (HTML5, WebWorkers)

    • ଞͷ LL Ͱ΋ϥΠϒϥϦ͕͋Δ CC-by : http://www.flickr.com/photos/punkscrapper/4276443469/
  16. ۙະདྷ Timeline 2010 2015 2020 ϚϧνίΞ ϝχʔίΞ ྔࢠίϯϐϡʔλ JVM ϕʔε

    Α͛Μͷॻ λεΫΩϡʔ εϨου Πϕϯτ Message passing
  17. ํ޲ੑ: ฒྻ DSL •௚ྻίʔυΛͭͳ͙ฒྻ LL • ௚ྻίʔυ: C, Ruby, Perl,

    PHP, ... • Communicating Sequential Process •LL ޲͖ͷฒྻੑ • ཻ౓͓͓͖Ί •Glue ͱͯ͠ͷ LL, ϝλ LL