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

Elixirにおける
データ並列スケルトンに基づく
SIMD並列化の性能評価

 Elixirにおける
データ並列スケルトンに基づく
SIMD並列化の性能評価

我々は Pelemay Super-Parallelism と称する,関数型言語 Elixir からC言語へのコード生成・最適化を行う処理系を研究開発している.これは,ElixirにはElixirのコードをASTに変換する機能が備わることを利用し,データ並列スケルトンに基づいて並列化可能なコードを検出してC言語コードを生成し,Clang や GCC の Auto Vectorization を利用して SIMD 並列化を行う処理系である.本研究の貢献は,Elixirの標準ライブラリであるEnumや先行事例Flowに準じたデータ並列スケルトンに基づいてSIMD命令を含むネイティブコードを生成・最適化することで,Enumに比べて,整数演算で2.25倍,浮動小数点数演算で4.48倍,文字列置換で3.85倍の性能向上,Flowに比べて,整数演算で21.0倍,浮動小数点数演算で247倍,文字列置換で 7.26×10^3倍の性能向上を達成したことである.リストの各要素を素体のロジスティック写像を算出する整数演算について,演算カーネルのループ内の命令カウントの中でSIMD命令が占める割合は,x86_64アーキテクチャで58.2%であった.perfで演算カーネルを実行した時にキャッシュミス率は24.3%,分岐予測ミスは4.56%,フロントエンドのストールサイクル率は6.18%,バックエンドのストールサイクル率は29.6%であった.

Susumu Yamazaki (ZACKY)

July 30, 2020
Tweet

More Decks by Susumu Yamazaki (ZACKY)

Other Decks in Research

Transcript

  1. #.' w ݱ୅ʹ͓͍ͯ͸ఆ൪ͱͳͬͨؔ਺ܕ ϓϩάϥϛϯάʹ͓͚ΔఆࣜԽ [2] Bird, R. S.: An Introduction

    to the Theory of Lists, Logic of Programming and Calculi of Discrete Design (Broy, M., ed.), NATO ASI Series (Series F: Computer and Systems Sciences), Vol. 36, Springer, Berlin, Heidelberg (1987). w جຊૢ࡞NBQ SFEVDFͳͲ w &MJYJSʹ͓͍ͯ΋&OVNϞδϡʔϧͱ ࣮ͯ͠૷͞Ε͍ͯΔ w ӈਤ#.'ͱͯ͠ͷ&MJYJSίʔυྫ  ˜4VTVNV:BNB[BLJ
  2. ฒྻϓϩάϥϛϯά͕ࠔ೉Ͱ͋Δཧ༝ w ҰํɼϚϧνίΞ$16ͷීٴʹΑͬͯɼฒྻܭࢉ؀ڥ͕೔ৗతʹਁಁ͍ͯ͠Δ w ͔͠͠ɼґવͱͯ͠ฒྻϓϩάϥϛϯά͸೉͍͠ w ͦͷཧ༝͸࣍ͷͱ͓ΓͰ͋Δ  ଟ͘ͷฒྻϓϩάϥϛϯάͰ͸ɼಉظɾഉଞ੍ޚ΍Ұ؏ੑϞσϧ΁ͷशख़Λඞཁͱ͢Δ 

    ฒྻΞϧΰϦζϜΛద੾ʹ࢖͍෼͚Δඞཁ͕͋Δ   ΑΓɼஞ࣍ϓϩάϥϛϯάʹൺ΂ֶͯशίετ͕ߴ͍  शख़ͨ͠ޙ΋ɼ৻ॏʹ͔ͭద੾ʹϓϩάϥϛϯά͢Δඞཁ͕͋ΔͨΊɼίʔυͷੜ࢈ੑ ͕མͪΔ   ͷ؍఺ͰϓϩάϥϜΛॻ͖Լ͢ඞཁ͕͋ΔͨΊɼίʔυͷՄಡੑ͕མͪΔ 5 ˜4VTVNV:BNB[BLJ
  3. ΞϧΰϦζϜɾεέϧτϯ w ฒྻܭࢉͰසग़͢ΔܭࢉύλʔϯΛදؔ͢਺ͱͯ͠ந৅Խͨ͠΋ͷ w ൥ࡶʹͳΓ͕ͪͳಉظɾഉଞ੍ޚɼҰ؏ੑϞσϧɼฒྻΞϧΰϦζϜͷهड़Λந৅Խ͢Δ w εέϧτϯฒྻϓϩάϥϛϯάεέϧτϯͷ૊Έ߹ΘͤʹΑͬͯฒྻϓϩάϥϜΛߏ੒ ͢Δ [4] Cole,

    M.: Algorithmic Skeletons: Structured Management of Parallel Computation, MIT Press (1989). w εέϧτϯͷछྨ w σʔλฒྻεέϧτϯ Ұ༷ͳཁૉΛ࣋ͭσʔλʹରͯ͠ɼ֤ཁૉʹಉ͡ૢ࡞Λߦ͏Α͏ͳύλʔϯ w λεΫฒྻεέϧτϯ ґଘؔ܎ʹͳ͍ಠཱͨ͠ܭࢉΛฒྻԽ͢ΔΑ͏ͳύλʔϯ 6 ˜4VTVNV:BNB[BLJ
  4. #.'ͱσʔλฒྻεέϧτϯɼ'MPX w #.'͕σʔλฒྻεέϧτϯͷͭͱͯ͠ฒྻॲཧʹ༗ޮʹػೳ [10] Skillicorn, D. B.: Foundation of Parallel

    Programming, Cambridge International Series on Parallel Computation, Cambridge University Press (1994). w &MJYJSͰ͸'MPX͕֘౰ w +BWBͰ͸4USFBNύοέʔδ͕֘౰ w ϦετॲཧΛϓϩηεʹ෼ׂ͠ɼ֤$16ίΞͰฒྻॲཧΛߦ͍ɼ ܭࢉ݁ՌΛϚʔδ͢Δ w ֤ϓϩηεʹׂΓ౰ͯΒΕͨܭࢉΛϚʔδ͢Δॱ൪͸ඇܾఆతʹ ͳΔ఺ʹ஫ҙ w ӈਤ͸'MPXͷϓϩάϥϛϯάྫ w ίʔυதʹಉظɾഉଞ੍ޚɼҰ؏ੑϞσϧɼฒྻΞϧΰϦζϜʹ ؔ͢Δෳࡶͳίʔυ͸ؚ·Ε͍ͯͳ͍఺ʹ஫ҙ w 'MPX͸*0ό΢ϯυͳॲཧͷ৔߹ʹ༏ΕͨੑೳΛൃش w ͔͠͠ɼ$16ό΢ϯυͳॲཧͷ࣌ʹ͸ஞ࣍ॲཧΑΓ͔͑ͬͯ஗͍ w ϓϩηεͷىಈͱϦετॲཧʹଟେͳΦʔόʔϔου͕ੜ͡Δ  ˜4VTVNV:BNB[BLJ
  5. )BTLFMMʹ͓͚Δ(1(16ฒྻԽ w 4LJMMJDPSOͷݪཧ<>ΛԠ༻͠ɼ$IBLSBWBSUZΒ<>͸ɼ#.'Λ ଟ༻͢Δ)BTLFMMϓϩάϥϜʹ͍ͭͯɼ֤ૢ࡞Λσʔλฒྻ εέϧτϯͱΈͳͯ͠(1(16ʹΑΔฒྻԽΛߦ͏ख๏ΛఏҊͨ͠  [10] Skillicorn, D. B.:

    Foundation of Parallel Programming, Cambridge International Series on Parallel Computation, Cambridge University Press (1994). [3] Chakravarty, M. M., Keller, G., Lee, S., McDonell, T. L. and Grover, V.: Accelerating Haskell Array Codes with Multicore GPUs, Proceedings of the Sixth Workshop on Declarative Aspects of Multicore Programming, DAMP’11, Vol. 6, No. 1, New York, NY, USA, Association for Computing Machinery, pp. 3–14 (online), DOI: 10.1145/1926354.1926358 (2011). 8 ˜4VTVNV:BNB[BLJ
  6. 1FMFNBZ w σʔλฒྻεέϧτϯͷߟ͑ํʹج͍ͮͯ$IBLSBWBSUZ Β<>ͷख๏Λ&MJYJSʹԠ༻ͨ͠΋ͷͱҐஔ෇͚ΒΕΔ w 'MPXͷऑ఺Ͱ͋Δ$16ό΢ϯυͳॲཧͷ৔߹ʹߴ଎ʹ ॲཧͰ͖ΔΑ͏ʹઃܭɾ࣮૷ w ӈਤ͸1FMFNBZͷίʔυྫ w

    ࠷େͰMJTUͷཁૉ਺ͷฒྻ౓Λ࣋ͭ͜ͱΛར༻ͯ͠ฒྻ Խ͢Δ w ಉظɾഉଞ੍ޚɼҰ؏ੑϞσϧɼฒྻΞϧΰϦζϜʹ ؔ͢Δෳࡶͳίʔυ͸ؚ·Ε͍ͯͳ͍͜ͱʹ஫ҙ w ݱঢ়Ͱ͸$MBOH΍($$ʹΑΔ"VUP7FDUPSJ[BUJPOΛ ༻͍ͯ4*.%໋ྩΛੜ੒͢ΔฒྻԽΛߦ͏ w কདྷతʹ͸$6%"౳Λ༻͍ͨ(1(16Λߦ͏Α͏ʹ֦ு ͢Δ༧ఆ w 0QFO$- $6%"ʹΑΔϓϩτλΠϓͰͷಈ࡞ݕূ͸ ࡁ·͍ͤͯΔ  ˜4VTVNV:BNB[BLJ
  7. 1FMFNBZʹΑΔฒྻԽ w ߦ໨͓Αͼߦ໨͸ɼ$MBOHʹର͠ "VUP7FDUPSJ[BUJPOΛࢦࣔ͢Δهड़ w ϕΫτϧԽΛ༗ޮʹ͢Δ w ϕΫλʔ෯ΛϚΫϩఆ਺ -001@7&$503*;&@8*%5)Ͱࢦఆ ͨ͠஋ʹ͢Δ

    w ϧʔϓΛ4*.%໋ྩΛؚΉωΠςΟ ϒίʔυʹม׵͢Δ w ࠷ۙͷ($$Ͱ͸ɼ͜ͷΑ͏ͳهड़͕ ͳ͘ͱ΋ɼίϯύΠϧΦϓγϣϯͰ 0΍0GBTUͳͲΛࢦఆͨ͠৔߹͸ɼ ࣗಈతʹϕΫτϧԽΛߦ͏  ˜4VTVNV:BNB[BLJ
  8. 1FMFNBZʹΑΔฒྻԽ w ߦ໨͓Αͼߦ໨͸ɼ$MBOHʹର͠ "VUP7FDUPSJ[BUJPOΛࢦࣔ͢Δهड़ w ϕΫλʔ෯ΛϚΫϩఆ਺ -001@7&$503*;&@8*%5)Ͱ ࢦఆͨ͠஋ʹ͢Δ w ࠷ۙͷ($$Ͱ͸ɼ͜ͷΑ͏ͳهड़͕

    ͳ͘ͱ΋ɼίϯύΠϧΦϓγϣϯͰ 0΍0GBTUͳͲΛࢦఆͨ͠৔߹ ͸ɼࣗಈతʹϕΫτϧԽΛߦ͏ ✴-001@7&$503*;&@8*%5)͸ $MBOHͰίϯύΠϧͨ࣌͠ͷΈ࡞༻͠ ($$ͷ࣌ʹ͸࡞༻͠ͳ͍  ˜4VTVNV:BNB[BLJ
  9. ੔਺ԋࢉϕϯνϚʔΫ w ੔਺ϕϯνϚʔΫͱͯ͠ɼૉମͷϩδε ςΟοΫࣸ૾Λճܭࢉ͢ΔԋࢉΛ࣮ࢪ [7] Miyazaki, T., Araki, S., Uehara,

    S. and Nogami, Y.: A Study of an Automorphism on the Logistic Maps over Prime Fields, Proc. of The 2014 International Symposium on Information Theory and its Applications (ISITA2014), pp. 727–731 (2014). w ԋࢉΧʔωϧ͸ճͷ&OVNNBQΛ ίϯύΠϧͯ͠ੜ੒ w ճͷMPHJTUJD@NBQؔ਺ݺग़͠Ͱճͷ Χʔωϧݺग़͠Λߦͳ͍ͬͯΔ w #FODIGFMMBΛ༻͍ͯճͷMPHJTUJD@NBQ ؔ਺ݺग़͠ʹཁ͢Δ࣌ؒΛܭଌ  ˜4VTVNV:BNB[BLJ
  10. ίϯύΠϥͱNBSDIOBUJWFΦϓγϣϯͷ༗ແ w ίϯύΠϥͱΦϓγϣϯΛม͑ͨ࣌ͷ࣮ݧ݁Ռ w ුಈখ਺఺਺ɼจࣈྻஔ׵ͷ࣌$MBOH w ਫ৭ w 44&໋ྩΛ࢖༻ w

    ੔਺ԋࢉͷ࣌($$NBSDIOBUJWF w ੺໼ҹ෦෼ w Ϗοτ੔਺ԋࢉ w 4*.%໋ྩΛੜ੒ͤͣʹ௨ৗͷ໋ྩ  ˜4VTVNV:BNB[BLJ
  11. 4*.%໋ྩͷׂ߹ w ਤ"ʙͷΞηϯϒϦίʔυΛ΋ͱʹ 4*.%໋ྩͷׂ߹Λܭଌ w ੔਺ԋࢉϕϯνϚʔΫʹ͍ͭͯɼ$MBOHͰ NBSDIΦϓγϣϯͳ͠ 44&໋ྩΛੜ੒  w

    -001@7&$503*;&@8*%5) w ࠷΋಺ଆͷϧʔϓʹண໨͠ɼ4*.%໋ྩͱ ͦΕҎ֎ͷ໋ྩΛͦΕͧΕΧ΢ϯτ w ԋࢉΧʔωϧͷ࠷಺ϧʔϓ಺ͷ໋ྩΧ΢ϯ τͰ4*.%໋ྩ͕઎ΊΔׂ߹͸  ˜4VTVNV:BNB[BLJ
  12. QFSGͷ࣮ߦ݁Ռ w QFSGTUBUͰ੔਺ԋࢉϕϯν ϚʔΫͷΧʔωϧΛ࣮ߦ w *1$͸લޙ w Ωϟογϡϛε཰͕ൺֱతେ͖ ͍ͷ͸ɼຊϕϯνϚʔΫ͕େ͖ ͳαΠζͷ഑ྻΛճ૸ࠪ͠ͳ

    ͕Βܭࢉ͢ΔͨΊ w όοΫΤϯυͷετʔϧ͕ൺֱ తଟ͘ൃੜ͍ͯ͠Δͷ͸ɼআࢉ Ͱ௕͍ϨΠςϯγ͕ൃੜ͍ͯ͠ ΔͨΊ  ˜4VTVNV:BNB[BLJ
  13. ·ͱΊ w 1FMFNBZͷֶज़తഎܠʹ͍ͭͯ·ͱΊͨ w ैདྷͷ&OVN'MPXͱൺ΂ͯ࣍ͷΑ͏ͳੑೳ޲্Λୡ੒ͨ͠ w ੔਺ԋࢉͰഒഒ w ුಈখ਺఺਺ԋࢉͰഒഒ w

    จࣈྻஔ׵Ͱഒഒ w -001@7&$503*;&@8*%5)͸͕࠷ળͰ͋ͬͨ w 44&໋ྩΛੜ੒ͨ͠$MBOH͕ුಈখ਺఺਺ɼจࣈྻஔ׵Ͱ࠷ળɼ Ϗοτ੔਺ԋࢉΛଟ༻͢Δͱ௨ৗ໋ྩΛੜ੒ͨ͠($$NBSDIOBUJWF͕࠷ળ w 4*.%໋ྩ͕઎ΊΔׂ߹͸ˋ w QFSGͰ੔਺ԋࢉΧʔωϧΛ࣮ߦͨ࣌͠ɼΩϟογϡϛε཰͸ˋɼόοΫΤϯυͷετʔϧαΠΫϧ ͸ˋͱߴ͘ɼ෼ذ༧ଌϛε͸ˋɼϑϩϯτΤϯυͷετʔϧαΠΫϧ཰͸ͱ௿͔ͬͨ *1$͸લޙͰ͋ͬͨ 29 ˜4VTVNV:BNB[BLJ