Share
Embed
疎行列圧縮フォーマットの紹介
CompML勉強会での発表資料.
- 成分のほとんどがゼロであるような疎行列の圧縮フォーマットの紹介.
- 主要な圧縮フォーマット(CSR)を用いたSparse Matrix Vector Multiplicationの紹介.
ryoherisson
May 28, 2021
Transcript
25 slides
-
CompML ૄߦྻͷ֓ཁ • ͷଟ͕͘ඇθϩͰ͋ΔΑ͏ͳߦྻΛີߦྻɼͷଟ͕͘θϩͰ͋ΔΑ͏ͳߦྻΛૄߦྻͱ͍͏ɽ • ີߦྻͰɼߦྻͷ֤͕ଟ࣍ݩྻʹ֨ೲ͞ΕΔɽ • ૄߦྻͷ߹ɼඇθϩͷͱͦͷߦྻͰͷ࠲ඪใΛ֨ೲ͢Δ͜ͱͰɼσʔλΛѹॖ͢Δ͜ͱ͕Ͱ ͖ɼϝϞϦͷઅߦྻԋࢉͷߴԽ͕ՄೳͱͳΔɽ 0
0 0 0 2 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 3 2 7 7 1 5 8 4 6 4 3 4 3 1 2 2 6 7 9 1 ີߦྻ ૄߦྻ ѹॖ ʁ 2 -
CompML ૄߦྻѹॖϑΥʔϚοτ ෳ͋ΔૄߦྻͷѹॖϑΥʔϚοτͷ͏ͪɼҎԼͷख๏Λհɽ • Dense • DIA • COO •
CSR • CSC • ELL • Hybrid • BSR • BSRX • CSB 4 -
CompML %FOTF ີߦྻΛ֨ೲ͢Δͱ͖ͷϑΥʔϚοτɽߦྻͷશͯͷ͕֨ೲ͞ΕΔɽ 5 𝑑𝑎𝑡𝑎 = 0 0 0 0
2 5 8 0 0 0 … 0 6 0 0 1 0 0 0 0 2 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 -
CompML %*" %JBHPOBM ඇθϩཁૉ͕ɼগͷର֯ઢ্ʹ͋Δ߹ʹద͍ͯ͠ΔϑΥʔϚοτɽ σʔλྻͱΦϑηοτྻ͔Βߏ͞ΕΔɽσʔλྻʹඇθϩཁૉͷɼΦϑηοτྻʹத ԝͷର֯ઢ͔ΒͷΦϑηοτ͕֨ೲ͞ΕΔɽ 6 4 0 0
0 0 0 8 0 5 0 0 0 3 0 9 6 0 0 7 0 𝑑𝑎𝑡𝑎 = 6 ∗ ∗ ∗ 4 8 3 7 ∗ 5 9 ∗ 𝑜𝑓𝑓𝑠𝑒𝑡 = −3 0 2 PGGTFU PGGTFU PGGTFU -
CompML %*"͕ෆదͱͳΔέʔε ҎԼͷΑ͏ͳέʔεͰɼ%*"ෆదͱͳΔɽ 7 0 0 0 0 1 0
0 0 2 0 0 0 3 0 0 0 4 0 0 0 𝑑𝑎𝑡𝑎 = ∗ 4 ∗ ∗ ∗ ∗ 3 ∗ ∗ 2 ∗ ∗ 1 ∗ ∗ ∗ 𝑜𝑓𝑓𝑠𝑒𝑡 = −2 0 2 4 0 0 1 0 0 0 0 2 0 5 0 3 0 0 0 6 7 0 4 0 𝑑𝑎𝑡𝑎 = 6 ∗ ∗ ∗ ∗ 7 ∗ ∗ ∗ 3 ∗ ∗ ∗ ∗ ∗ 4 ∗ 2 ∗ ∗ 1 ∗ ∗ ∗ ∗ 5 ∗ ∗ 𝑜𝑓𝑓𝑠𝑒𝑡 = −3 −2 −1 0 1 2 3 -
CompML $00 $PPSEJOBUF ඇθϩཁૉͷͷྻͱɼͦͷཁૉͷߦΠϯσοΫεͱྻΠϯσοΫεͷྻͰߏ͞ΕΔɽ ඇθϩཁૉͷ͕ͦͷߦྻͷʹຬͨͳ͍߹ʹͷΈɼີߦྻΑΓσʔλྔΛݮ͢Δ͜ͱ͕Ͱ͖Δɽ 8 𝑑𝑎𝑡𝑎 = 1 5
8 3 6 1 0 0 0 0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 𝑟𝑜𝑤_𝑖𝑛𝑑 = 0 1 1 2 3 3 𝑐𝑜𝑙_𝑖𝑛𝑑 = 4 0 1 2 1 4 -
CompML $43 $PNQSFTTFE4QBSTF3PX ඇθϩཁૉͷ͕֨ೲ͞ΕͨσʔλྻɼඇθϩཁૉͷྻΠϯσοΫε͕֨ೲ͞ΕͨྻΠϯσοΫε ྻɼ֤ߦͷ࠷ॳʹग़ͯ͘Δඇθϩཁૉ͕ɼඇθϩཁૉશମͷԿ൪͔ද͢ΦϑηοτΛ֨ೲͨ͠ߦϙΠ ϯλྻɼͷͭͷྻͰߏ͞ΕΔɽ 9 0 0 0
0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 𝑑𝑎𝑡𝑎 = 1 5 8 3 6 1 𝑟𝑜𝑤_𝑝𝑡𝑟 = 0 1 3 4 6 𝑐𝑜𝑙_𝑖𝑛𝑑 = 4 0 1 2 1 4 SPX@QUS -
CompML $4$ $PNQSFTTFE4QBSTF$PMVNO $43ϑΥʔϚοτͰѹॖ͍ͯͨ͠ߦΠϯσοΫεͷΘΓʹɼྻΠϯσοΫεΛѹॖ͢Δܗࣜɽ 10 0 0 0 0 1
5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 𝑑𝑎𝑡𝑎 = 5 8 6 3 6 1 1 𝑐𝑜𝑙_𝑝𝑡𝑟 = 0 1 3 4 4 6 𝑟𝑜𝑤_𝑖𝑛𝑑 = 1 1 3 2 0 3 DPM@QUS -
CompML &-- &--1"$, ߦ͝ͱͷඇθϩཁૉͷΈΛ֨ೲͨ͠σʔλྻͱɼσʔλྻʹ֨ೲ͞ΕͨඇθϩཁૉͷྻΠϯσοΫ εΛ֨ೲ͢ΔΠϯσοΫεྻͰߏ͞ΕΔɽ σʔλྻͷྻͷ͞,ɼߦ͝ͱͷඇθϩཁૉͷ࠷େͱͳΓɼߦͷ͞ݩͷߦྻͷߦͱͳΔɽ 11 0 0 0
0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 𝑑𝑎𝑡𝑎 = 1 ∗ 5 8 3 ∗ 6 1 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 = 4 ∗ 0 1 2 ∗ 1 4 L L L L NBYL, -
CompML &-- &--1"$, ͕ෆదͱͳΔέʔε ߦ͝ͱͷඇθϩཁૉͷ࠷େ͕ฏۉͱେ͖͘ҟͳΔ߹ɼ&--ෆదͳදݱํ๏ͱͳΔɽ &--ͱ$00ͷΈ߹Θͤͷ)ZCSJEͱ͍͏ख๏ɽ 12 0 0
0 0 1 5 8 3 7 2 0 0 4 9 0 0 6 0 0 0 𝑑𝑎𝑡𝑎 = 1 ∗ ∗ ∗ ∗ 5 8 3 7 2 4 9 ∗ ∗ ∗ 6 ∗ ∗ ∗ ∗ 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 = 4 ∗ ∗ ∗ ∗ 0 1 2 3 4 2 3 ∗ ∗ ∗ 1 ∗ ∗ ∗ ∗ L L L L NBYL,BWFSBHFL -
CompML ):# )ZCSJE ඇθϩཁૉͷେ෦Λ&--ʹ֨ೲ͠ɼΓΛ$00ʹ֨ೲ͢ΔϋΠϒϦουͳϑΥʔϚοτɽ 13 0 0 0 0 1
5 8 3 7 2 0 0 4 9 0 0 6 0 0 0 𝑑𝑎𝑡𝑎 = 1 ∗ 5 8 4 9 6 ∗ 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 = 4 ∗ 0 1 2 3 1 ∗ L L L L NBYL,BWFSBHFL ELL COO 𝑑𝑎𝑡𝑎 = 3 7 2 𝑟𝑜𝑤_𝑖𝑛𝑑 = 1 1 1 𝑐𝑜𝑙_𝑖𝑛𝑑 = 2 3 4 -
CompML #43 #MPDL$PNQSFTTFE4QBSTF3PX ߦྻΛαΠζ͕ಉ͡ϒϩοΫʹ্ׂͨ͠Ͱɼ$43ϥΠΫͳϑΥʔϚοτʹ֨ೲɽ ඇθϩཁૉͷؚ͕·ΕΔϒϩοΫͷશͯͷΛؚΉσʔλྻɼඇθϩཁૉؚ͕·ΕΔϒϩοΫͷ ྻΠϯσοΫε͕֨ೲ͞ΕͨྻΠϯσοΫεྻɼ֤ߦͷ࠷ॳʹग़ͯ͘ΔϒϩοΫ͕ɼඇθϩཁૉؚ͕ ·ΕΔϒϩοΫશମͷԿ൪͔ද͢ΦϑηοτΛ֨ೲͨ͠ߦϙΠϯλྻɼͷͭͷྻͰߏ͞ΕΔɽ 14 0 0
0 0 1 0 5 8 0 0 0 2 0 0 3 0 0 0 0 6 0 0 0 0 𝑏𝑙𝑘_𝑟𝑜𝑤_𝑝𝑡𝑟 = 0 2 4 𝑏𝑙𝑘_𝑐𝑜𝑙_𝑖𝑛𝑑 = 0 2 0 1 CML@SPX@QUS 𝑑𝑎𝑡𝑎 = 0 0 5 8 1 0 0 2 0 0 0 6 3 0 0 0 -
CompML #439 &YUFOEFE#43 #43ϑΥʔϚοτͷߦϙΠϯλྻΛɼͭͷྻʹׂ͢Δɽͭͷྻʹ֤ߦͷ࠷ॳͷඇθϩཁ ૉΛؚΉϒϩοΫͷϙΠϯλɼͭͷྻʹ֤ߦͷ࠷ޙͷඇθϩཁૉΛؚΉϒϩοΫͷϙΠϯλ͕֨ ೲ͞ΕΔɽ CML@SPX@QSUͱCML@FOE@QUSΛมߋ͢Δ͚ͩͰɼݩͷߦྻͷҰ෦ͷϒϩοΫ͚ͩΛͨ͠ߦྻΛ࡞Δ͜ͱ ͕Ͱ͖Δɽ 15 0
0 0 0 1 0 5 8 0 0 0 2 0 0 3 0 0 0 0 6 0 0 0 0 𝑏𝑙𝑘_𝑟𝑜𝑤_𝑝𝑡𝑟 = 0 2 𝑏𝑙𝑘_𝑐𝑜𝑙_𝑖𝑛𝑑 = 0 2 0 1 𝑑𝑎𝑡𝑎 = 0 0 5 8 1 0 0 2 0 0 0 6 3 0 0 0 𝑏𝑙𝑘_𝑒𝑛𝑑_𝑝𝑡𝑟 = 2 4 -
CompML #439 &YUFOEFE#43 ͷར CML@SPX@QSUͱCML@FOE@QUSΛมߋ͢Δ͚ͩͰɼݩͷߦྻͷҰ෦ͷϒϩοΫ͚ͩΛͨ͠ߦྻΛ࡞Δ͜ͱ ͕Ͱ͖Δɽ 16 0 0 0
0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 𝑏𝑙𝑘_𝑟𝑜𝑤_𝑝𝑡𝑟 = 0 2 𝑏𝑙𝑘_𝑐𝑜𝑙_𝑖𝑛𝑑 = 0 2 0 1 𝑑𝑎𝑡𝑎 = 0 0 5 8 1 0 0 2 0 0 0 6 3 0 0 0 𝑏𝑙𝑘_𝑒𝑛𝑑_𝑝𝑡𝑟 = 0 3 -
CompML $4# $PNQSFTTFE4QBSTF#MPDLT ߦྻΛϒϩοΫʹׂɽඇθϩཁૉͷ͕֨ೲ͞ΕͨσʔλྻɼϒϩοΫͰͷඇθϩཁૉͷߦΠϯ σοΫεɾྻΠϯσοΫεΛ֨ೲ͢Δྻɼ֤ϒϩοΫͷ࠷ॳʹग़ͯ͘Δඇθϩཁૉ͕ɼඇθϩཁૉશ ମͷԿ൪͔ද͢ΦϑηοτΛ֨ೲͨ͠ϒϩοΫϙΠϯλྻͰߏ͞ΕΔɽ సஔߦྻͷԠ༻Մೳɽ 17 0 0
0 0 1 0 5 8 0 0 0 2 0 0 3 0 0 0 0 6 0 0 0 0 CML@QUS 𝑑𝑎𝑡𝑎 = 5 8 1 2 6 3 𝑏𝑙𝑘_𝑟𝑜𝑤_𝑖𝑛𝑑 = 1 1 0 1 1 0 𝑏𝑙𝑘_𝑐𝑜𝑙_𝑖𝑛𝑑 = 0 1 0 1 1 0 𝑏𝑙𝑘_𝑝𝑡𝑟 = 0 2 2 4 5 6 6 গͳ͍ϏοτͰ ූ߸Խ -
CompML ٖࣅίʔυ 19 #VMVÇ " 'JOFNBO +5 'SJHP . (JMCFSU
+3 -FJTFSTPO $& "VHVTU 1BSBMMFMTQBSTFNBUSJYWFDUPSBOENBUSJYUSBOTQPTFWFDUPSNVMUJQMJDBUJPOVTJOHDPNQSFTTFE TQBSTFCMPDLT*O1SPDFFEJOHTPGUIFUXFOUZGJSTUBOOVBMTZNQPTJVNPO1BSBMMFMJTNJOBMHPSJUINTBOEBSDIJUFDUVSFT QQ -
CompML DV4QBSTFΛͬͨ4Q.7 21 DV4QBSTFϋϯυϧ࡞ σόΠεϝϞϦ֬อ σεΫϦϓλͷઃఆ
ϗετ͔ΒσόΠεʹϝϞϦΛίϐʔ ඇθϩཁૉͷΧϯτ %FOTF͔Β$43ʹม ߦྻϕΫτϧࢉ σόΠε͔Βϗετʹసૹʢ͜ͷ࣌Ͱ%FOTF ϑΥʔϚοτԽ͞ΕΔʣ ϝϞϦղ์ ˞ ίʔυলུ δϣϯ νΣϯ ΄͔ גࣜձࣾΫΠʔϒ ༁ $6%"$ϓϩϑΣογϣφϧϓϩάϥϛϯάΠϯϓϨε -
CompML ࣮ߦ࣌ؒͷൺֱ 22 CPU GPU 0.008600s 0.000043s $16ஞ࣍ॲཧͱ(16ฒྻॲཧͰɼഒͷࠩɽ ˞4Q.7ɿ ߦྻ
Y ͱϕΫτϧ ͷੵɽ ࣮ߦڥɿ (F'PSDF359461&3 $6%" -
CompML 3FGFSFODF • #FMM / (BSMBOE . &GGJDJFOUTQBSTFNBUSJYWFDUPSNVMUJQMJDBUJPOPO$6%" 7PM
/P /WJEJB5FDIOJDBM3FQPSU/73 /WJEJB$PSQPSBUJPO • #VMVÇ " 'JOFNBO +5 'SJHP . (JMCFSU +3 -FJTFSTPO $& "VHVTU 1BSBMMFM TQBSTFNBUSJYWFDUPSBOENBUSJYUSBOTQPTFWFDUPSNVMUJQMJDBUJPOVTJOHDPNQSFTTFETQBSTF CMPDLT*O1SPDFFEJOHTPGUIFUXFOUZGJSTUBOOVBMTZNQPTJVNPO1BSBMMFMJTNJOBMHPSJUINTBOE BSDIJUFDUVSFT QQ • +PIO$IFOH .BY(SPTTNBO 5Z.D,FSDIFS 1SPGFTTJPOBM$6%"$1SPHSBNNJOH8SPY δϣϯ νΣϯ ϚοΫε άϩεϚϯ λΠ ϚοΧʔνϟʔ גࣜձࣾΫΠʔϒ ༁ $6%" $ϓϩϑΣογϣφϧϓϩάϥϛϯάגࣜձࣾΠϯϓϨε 24