マルチGPU環境におけるCRS形式疎行列・ベクトル積の入力行列の最適化による高速化

全文

(1)HPCS2014 2014/1/7. 2014年ハイパフォーマンスコンピューティングと計算科学シンポジウム High Performance Computing Symposium 2014. 䝬䝹䝏GPU⎔ቃ䛻䛚䛡䜛CRSᙧᘧ␯⾜ิ䞉䝧䜽䝖䝹✚䛾ධຊ⾜ิ䛾᭱㐺໬䛻䜘䜛㧗㏿໬ ᒸ⏣ ࿴ே(㟁Ẽ㏻ಙ኱Ꮫ)䠈ᒸᮏ ྜྷኸ(㟁Ẽ㏻ಙ኱Ꮫ)䠈௒ᮧ ಇᖾ(⌮໬Ꮫ◊✲ᡤ ィ⟬⛉Ꮫ◊✲ᶵᵓ). ◊✲┠ⓗ • • •. nVidia♫〇GPU䛾GPGPU㛤Ⓨ⎔ቃCUDA䛻䛚䛡䜛䜘䜚㧗㏿䛺␯⾜ิ䞉䝧䜽䝖䝹✚䛾ᐇ⿦ 䜘䜚኱つᶍ䛺␯⾜ิ䜈䛾ᑐᛂ 」ᩘ䛾GPU䜢ᦚ㍕䛧䛯ィ⟬ᶵ䜈䛾ᑐᛂ. CUDA䛻䛴䛔䛶. CUDAྥ䛡CRSᙧᘧ␯⾜ิ䞉䝧䜽䝖䝹✚ᐇ⿦ z. 1 0 െ1 0 0. z. z z z. CRSᙧᘧ␯⾜ิ᱁⣡᪉ᘧ. 6 2 0 െ2 0. 0 0 0 0 3 0 0 4 െ3 0. 0 CRSᙧᘧ䛿␯⾜ิ䜢⾜ඃඛ䛷୍ḟඖ㓄ิ䛻᱁⣡ 0 㻌㻌㻌㻌㻌㻌 0 㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌㻌 ྠ᫬䛻䛭䛾せ⣲䛾ิ䛾ሙᡤ䜢ྠᵝ䛻᱁⣡ 䛭䛾୍ḟඖ㓄ิෆ䛷⾜䛾୍␒᭱ึ䛾せ⣲䛻䛒 7 䛯䜛せ⣲䛾ῧᏐ䜢୍ḟඖ㓄ิ䛷᱁⣡ 5. z z. CUDAྥ䛡CRSᙧᘧ␯⾜ิ䞉䝧䜽䝖䝹✚ᐇ⿦ᴫせ䠄᪤Ꮡ◊✲䠅. ܾ଴ ܾ଴ ܾ଴ ܾ଴ ܾ଴. ‫ݐ‬଴. ‫ݐ‬଴. ‫ݐ‬ଵ. ‫ݐ‬଴. ܾ଴ ܾ଴ ܾ଴. ‫ݐ‬ଶ ‫ݐ‬ଷ ‫ݐ‬ଶ. ‫ݐ‬ଶ. ‫ݐ‬ଷ. ‫ݐ‬ଶ. ܾ଴ ܾ଴ ܾ଴ ܾ଴. ‫ݐ‬ସ ‫ݐ‬ହ ‫ݐ‬ସ ‫ݐ‬ହ. ‫ݐ‬ସ. ‫ݐ‬ହ. ‫ݐ‬ସ. ܾ଴. ‫଺ݐ‬. ‫଺ݐ‬. ‫ݐ‬ଵ. ‫ݐ‬଴. ‫ݐ‬ଵ. ‫ݐ‬଴. ᐇ㦂⎔ቃ. ‫଺ݐ‬. ܾଵ ܾଵ. 㻌ܾ. ଵ. ܾଵ ܾଵ ܾଵ. ܾଵ ܾଵ ܾଵ ܾଵ ܾଵ 䠍䝤䝻䝑䜽䛜」ᩘ⾜䜢ィ⟬. ྛ⾜䛾㒊ศ✚䜢䝇䝺䝑䝗䛤䛸䛻ィ⟬. ồ䜑䛯㒊ศ✚䛾⥲࿴䜢⾜䛤䛸䛻䝸䝎䜽䝅䝵䞁ィ⟬. 䜹䞊䝛䝹㛵ᩘ䠖GPU䛷ືస䛩䜛㛵ᩘ 䝇䝺䝑䝗䠖䜹䞊䝛䝹㛵ᩘ䜢ᐇ⾜䛩䜛᭱ᑠ༢఩ 䝤䝻䝑䜽䠖䝇䝺䝑䝗䜢䜎䛸䜑䛯䜒䛾 ྠ୍䝤䝻䝑䜽ෆ䛾䝇䝺䝑䝗䛺䜙䜀䝕䞊䝍䜢ඹ᭷䛩䜛䛣䛸䛜䛷䛝䜛 ୍⯡䛻䝤䝻䝑䜽㛫䛷䝕䞊䝍䛾ඹ᭷䛿୙ྍ 䜾䝻䞊䝞䝹䝯䝰䝸䠖GPU䛾䝯䜲䞁䝯䝰䝸䝅䜵䜰䞊䝗䝯䝰䝸䠖ྠ୍䝤䝻䝑䜽ෆ䛾䝇䝺䝑䝗䛷䝕䞊䝍䜢ඹ᭷䛷䛝䜛䝯䝰䝸 ᑠᐜ㔞䛰䛜䜾䝻䞊䝞䝹䝯䝰䝸䛾100ಸ㧗㏿. ྛ⾜䛾㒊ศ✚䛾⥲࿴䜢䝧䜽䝖䝹✚䛸䛧䛶᱁⣡. . OS䠖Fedora18 CPU䠖Intel Core i7 䝯䝰䝸䠖16GB GPU1䠖GeForce GTX 590 GPU2䠖GeForce GTX 590 䝁䞁䝟䜲䝷䠖Nvidia CUDA Compiler Ver.5.5. ᪤Ꮡ◊✲䛾ᛶ⬟䛸ㄢ㢟. ᪤Ꮡ◊✲䛾」ᩘGPU䛻䛚䛡䜛ᛶ⬟. 㻌 ᪤Ꮡ◊✲䛾ᐇ⿦䛻䛴䛔䛶ㄪ䜉䜛䛯䜑䠈⣙200䛾␯⾜ิ䛻㛵䛧䛶୍⾜ᙜ䛯䜚䛾ィ⟬䝇䝺䝑䝗ᩘ䠄NT䠅䜢ኚ䛘䛺䛜䜙ィ⟬㏿ᗘ䜢 ᐃ䛧䛯䠊㻌 ᐇ㦂⤖ᯝ䛛䜙䠈୍␒㧗㏿䛻ィ⟬䛷䛝䛯NT䛤䛸䛻䜎䛸䜑䛶⤖ᯝ䜢♧䛩䠊㻌䛺䛚䠈1䝤䝻䝑䜽ᙜ䛯䜚䛾䝇䝺䝑䝗ᩘ䛿256䝇䝺䝑䝗䛸䛩䜛. 㻌」ᩘ䛾GPU䛷ᐇ⿦䛧䛯ྠᵝ䛾ィ ⤖ᯝ䜢♧䛩䠊GPU䛜」ᩘ䛻䛺䜛䛸䠈䝍䝇䜽䜢ศ๭䛧䛺䛡䜜䜀䛺䜙䛺䛔䠊㻌䛣䛣䛷䛿༢⣧䛻䠈⾜ิ䛾ୖ䛛䜙㠀㞽せ⣲䛜༙䚻䛻䛺䜛䜘䛖䛻ୖୗ䛻ศ๭䛧䛯䠊 NT䛤䛸䛾ィ⟬㏿ᗘ(GPUx2) 3.50E+10. NT䛤䛸䛾ィ⟬㏿ᗘ 2.50E+10. 3.00E+10. 2.50E+10. 2.00E+10. NT=1 2.00E+10. FLOPS. NT=2 NT=4. NT=2. FLOPS. NT=1 1.50E+10. NT=4 NT=8. 1.50E+10. NT=16. NT=8. 1.00E+10. NT=16. NT=32. 1.00E+10. NT=32 5.00E+09. 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199 202 205. 0.00E+00 0.00E+00. 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199 202 205. 5.00E+09. ୖᅗ䛻䛚䛔䛶䛹䛾NT䛷䜒ィ⟬㏿ᗘ䛜ⴠ䛱䛶䛔䜛⾜ิ䛻䛴䛔䛶ㄪ䜉䛯䠊䛭䛾⤖ᯝ䠈௨ୗ䛾2䛴䛾ഴྥ䛜ぢ䜙䜜䛯䠊 ୍⾜䛤䛸䛾ẚ౛せ⣲ᩘ䛾᭱኱್䛸ᖹᆒ್䛻ᕪ䛜䛒䜛ሙྜ 㻌 GPUୖ䛷4䝤䝻䝑䜽䠈32䝇䝺䝑䝗ྠ᫬䛻ィ⟬䛷䛝䜛䛸䛩䜛䠊㻌 ᕥᅗ䛿␯⾜ิ䛾㠀㞽せ⣲䜢ᕥワ䜑䛻䛧䛶♧䛧䛯䜒䛾䛷䛒䜛䠊㻌 Ⰽ䛾䛴䛔䛯䝉䝹䛜㠀㞽せ⣲䛷䠈ኴᯟ 䛿1䝤䝻䝑䜽䛷ྠ᫬䛻ィ⟬䛩䜛せ⣲䜢♧ 䛧䠈୰ᯟ䛿䝤䝻䝑䜽ෆ䛷䝹䞊䝥ฎ⌮䜢⾜䛖せ⣲䛷䛒䜛䠊 NT䛜ᅛᐃ䛷䛒䜛ሙྜ䠈䛣䜜௨ୖ㐺ษ䛺 ๭䜚ᙜ䛶䛜䛷䛝䛺䛔䠊ୖᅗ䛾䛹䛾NT䛷䜒ィ⟬㏿ᗘ䛜ୖ䛜䜙䛺䛔㒊ศ䛾⾜ิ䛜䛣䜜䛻䛒䛯䜛䠊 NT=4䛾䛸䛝䠈୍⾜┠䛾ィ⟬䛿4ᅇ䛾䝹䞊䝥䛷⤊஢䛩䜛䛜䠈ྠ᫬䛻ィ⟬䛷䛝䜛䛾䛿8⾜ศ䛧䛛䛺䛔䠊. 㻌 GPU䛜ቑ䛘䜛䛸䠈GPU㛫䛾ྠᮇ䜔䝕䞊䝍䛾㌿㏦䛺䛹䛻᫬㛫䛜䛛䛛䜚䠈ィ⟬㔞䛜ᑠ䛥䛟䛺䜛䜋䛹ィ⟬㏿ᗘ䛜ⴠ 䛱䛶䛔䜛䠊㏫䛻ィ⟬㔞䛜ቑ䛘䜛䜋䛹䠈ィ⟬㏿ᗘ䛜ୖ᪼䛩䜛ഴྥ䛜䜟䛛䜛䠊㻌 ༢୍GPU䛷ィ⟬䛧䛯᫬䛸NT䛾ィ⟬㏿ᗘ䛾ഴྥ䛸␗䛺䜛䛾䛿䠈䜒䛸䜒䛸⾜䛤䛸䛾㠀㞽せ⣲ᩘ䛻೫䜚䛜䛒䜚䠈ィ ⟬䛩䜛␯⾜ิ䜢ศ๭䛧䛯㝿䛻㠀㞽せ⣲ᩘ䛻ᕪ䛜⏕䛨䛶䛧䜎䛳䛯䜒䛾䛸⪃䛘䜙䜜䜛䠊㻌. ゎỴ⟇ 㻌 ୍⾜䛾㠀㞽せ⣲ᩘ䛾᭱኱್䛸ᖹᆒ್䛻኱䛝䛺ᕪ䛾䛒䜛␯⾜ิ䛻ᑐ䛧䛶䠈௨ୗ䛾᪉ἲ䛷ධຊ⾜ิ䜢ᩚ⌮䛩䜛䛣䛸䛻䜘䜚䠈」ᩘ䛾GPU䜢⏝䛔䛯⎔ቃ䛷䛾㧗㏿໬䠈ᛶ⬟䛾Ᏻᐃ໬䜢ヨ䜏䛯䠊. NT=2䛾䛸䛝䠈୍ᗘ䛻16⾜ィ⟬䛷䛝䜛䛜䠈୍⾜┠䛾ィ⟬ 䛻8ᅇ䛾䝹䞊䝥䛜ᚲせ䛸䛺䜛䠊. ิ䜲䞁䝕䝑䜽䝇䛜ศᩓ䛧䛶䛔䜛ሙྜ. 㻌 ᕥᅗ䛿Ⰽ௜䛝䛾䝉䝹䛜㠀㞽せ⣲䛷䛒䜛␯⾜ิ䛸䝧䜽䝖䝹䛷䛒䜛䠊㻌 ౛䛘䜀ᕥᅗ䛾␯⾜ิ䞉䝧䜽䝖䝹✚䛾ሙྜ䠈䝯䝰䝸ୖ䛷ᕥ䛾␯⾜ิ䛸ྑ䛾䝧䜽䝖䝹䛻䜰䜽䝉䝇䛩䜛䠊CRSᙧᘧ䛾␯⾜ิ䞉䝧䜽䝖䝹✚䛷䛿䠈⾜䛤䛸䛻✚࿴₇ ⟬䜢䛩䜛䛾䛷䠈䛣䛾䜘䛖䛻␯⾜ิ䛾ิ䜲䞁䝕䝑䜽䝇䛻䜀䜙䛴䛝䛜䛒䜛䛸ィ⟬ 䛩䜛⾜䛜ኚ䜟䜛䛯䜃䛻䝧䜽䝖䝹䛾ู䛾せ⣲䛻䜰䜽䝉䝇䛩䜛䛣䛸䛻䛺䜛䠊䛧䛯䛜䛳䛶䠈䜻䝱䝑䝅䝳䛾฼Ⅼ䛜⏕䛛䛫䛺䛟䛺䜛䛯䜑䠈ィ⟬㏿ᗘ䛜ୖ䛜䜙䛺䛔䠊. ␯⾜ิᕥワ䜑䛻䛧䛯ᅗ. 㠀㞽せ⣲ᩘ㡰䛻䝋䞊䝖. 䛭䜜䛮䜜䜢ྛGPU䛻๭䜚ᙜ䛶䠈㐺䛧䛯NT䛷ィ⟬. 㻌 ୖグ䛾ᡭ㡰䛻䜘䜚䠈␯⾜ิ䝕䞊䝍䜢ィ⟬䛧䜔䛩䛔ᙧ䛻䛧䛶䛛䜙ィ⟬䜢⾜䛖䠊㻌ィ⟬㒊ศ䛿᪤Ꮡ◊✲䛾䜒䛾䜢䜒䛸䛻ᐇ⿦䛧䛶⏝䛔䜛䛣䛸䛸䛩䜛䠊㻌䛺䛚䠈㐺䛧䛯NT䛾ᐃ䜑᪉䜒ཧ⪃ᩥ⊩1䜘䜚䠈max(1,min(32,2 ୪୭୥మ (௡௢௡௭௘௥௢/௥௢௪) ))䛸䛧䛯䠊㻌 ௨ୗ䛻ྛ␯⾜ิ䛾䝅䞁䜾䝹GPU䛻䛚䛡䜛᭱㏿䛾⤖ᯝ䛸䝬䝹䝏GPU䛻䛚䛡䜛᭱㏿䛾⤖ᯝ䠈CUSPARSE䝷䜲䝤䝷䝸䛾⤖ᯝ䛸䛒䜟䛫䛶䠈䝋䞊䝖῭CRSᙧᘧ␯⾜ิ䞉䝧䜽䝖䝹ᖍ䛾ィ⟬㏿ᗘ䜢♧䛩䠊 3.50E+10. ೙೚೙೥೐ೝ೚ 㻌䛸䛧䛯ሙྜ䛾ィ⟬㏿ᗘ䛸䠈ୖグ䛾༢୍GPU ୪୭୥ max(1, min(32, 2 మ ೝ೚ೢ ) 䛻䛚䛡䜛᭱㏿䛾್䠈CUSPARSE䝷䜲䝤䝷䝸㛵ᩘ䛾㏿ᗘ䛸䛾ẚ㍑䜢♧䛩䠊. 㻌䜎䛯䠈ཧ⪃ᩥ⊩䠍䛻ᚑ䛳䛶NT䜢. 3.00E+10. 2.50E+10. ⮬ື䝏䝳䞊䝙䞁䜾䛷䛾ᛶ⬟䛸䝷䜲䝤䝷䝸㛵ᩘ䛾ᛶ⬟ 2.50E+10. 2.00E+10. 䝅䞁䜾䝹GPU᭱㏿(NTᅛᐃ) 䝬䝹䝏GPU᭱㏿(NTᅛᐃ). 2.00E+10. 䝋䞊䝖῭CRS䠇䝬䝹䝏GPU(NT⮬ື). 1.50E+10. CUSPARSE䝷䜲䝤䝷䝸 1.50E+10 FLOPS. NT=auto. 1.00E+10. 䝅䞁䜾䝹GPU᭱㏿(NTᅛᐃ) 1.00E+10. CUSPARSE䝷䜲䝤䝷䝸. 5.00E+09. 5.00E+09 0.00E+00 1 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199 202 205. 0.00E+00. 㻌 ༢୍GPU䛷䛾᭱㏿䛾್䛸䠈⮬ື䛷NT䜢ᐃ䜑䛯ሙྜ䜢ẚ㍑䛩䜛䛸䠈⮬ື䛷ᐃ䜑䛯ሙྜ䛿᭱㐺䛺NT䜢㑅ᢥ䛷䛝䛶䛔䛺䛔䛣䛸䛜䜟䛛䜛䠊䜎䛯䠈᭱㏿䛸䛺䜛NT䜢㑅ᢥ䛧䛯䛸䛧䛶䜒CUSPARSE䝷䜲䝤䝷䝸䛾㛵ᩘ䜘䜚㏿ᗘ䛜ฟ䛺䛔 ሙྜ䛜䛒䜛䠊. ⪃ᐹ䛸䛣䜜䛛䜙䛾ㄢ㢟 ༙ศ௨ୖ䛾⾜ิ䛷༢୍GPU䛻䛚䛡䜛ィ⟬䜘䜚䜒ᛶ⬟䛜ⴠ䛱䛯」ᩘ䛾GPU䜢⏝䛔䜛䛣䛸䛻䜘䜛ྠᮇ䜔䝯䝰䝸⟶⌮䛾ၥ㢟 ୍⾜䛾㞽せ⣲ᩘ㡰䛻䝋䞊䝖䛧䛶ィ⟬䛧䛶䜒㏫䛻㐜䛟䛺䛳䛯 ௒ᅇ⏝䛔䛯䝏䝳䞊䝙䞁䜾䛾᪉ἲ䛻ㄢ㢟䛜ṧ䜛 Kepler䜰䞊䜻䝔䜽䝏䝱ୖ䛻䛚䛡䜛᳨ド. ⓒ 2014 Information Processing Society of Japan. 5. 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113 117 121 125 129 133 137 141 145 149 153 157 161 165 169 173 177 181 185 189 193 197 201 205. 䜟䛪䛛䛷䛿䛒䜛䛜䠈NT䜢ᅛᐃ䛧䛯ᐇ⿦䜘䜚䜒㧗㏿䛻ィ⟬䛷䛝䛯⾜ิ䛜䛒䜛䠊ヲ⣽䛻ศᯒ䛧䛶䠈䜘䜚Ⰻ䛔ᐇ⿦䜢 ᥈䛳䛶䛔䛝䛯䛔䠊. ཧ⪃ᩥ⊩ 1. GPU䛻䛚䛡䜛㧗㏿䛺CRSᙧᘧ␯⾜ิ䝧䜽䝖䝹✚䛾ᐇ⿦䠈᳚ᮌ ኱ᆅ䠈㧗ᶫ ኱௓䠈᝟ሗฎ⌮Ꮫ఍◊✲ሗ࿌ Vol.2013-HPC-138 No.5䠈2013 2. CUDA BY EXAMPLE㻌 ỗ⏝GPU䝥䝻䜾䝷䝭䞁䜾ධ㛛䠈Jason Sanders, Edward Kandrot,㻌 ᰴᘧ఍♫䜲䞁䝥䝺䝇䝆䝱䝟䞁䠈2011 3. GPU䝥䝻䜾䝷䝭䞁䜾ධ㛛 CUDA5䛻䜘䜛ᐇ⿦䠈ఀ⸨ ᬛ⩏䠈ㅮㄯ♫䠈2013. 28.

(2)