フカシギおねえさん問題の高速計算アルゴリズム
|
|
|
- しおり のあき
- 5 years ago
- Views:
Transcription
1 JST ERATO 2013/7/26 Joint work with 1 / 37
2 / 37
3 / 37
4 : 4 / 37
5 / 37
6 Bousquet-Mélou (2005) GHz Alpha 8 Iwashita (Sep 2012) GHz Xeon 1 Spaans (Feb 2013) 24 24??? 30 Iwashita (Apr 2013) GHz Xeon 30 6 / 37
7 Sequence A of the On-Line Encyclopedia of Integer Sequences n #path : : : / 37
8 / 37
9 a b e j {a, b, e, j} c f d b e j {b, c, d, e, f, j} / 37
10 / 37
11 11 / 37
12 / 37
13 13 / 37
14 14 / 37
15 1: count 0 ; n+1 { }} { 2: count[ ] 1; 3: for i = 1 to n + 1 do 4: for j = 1 to n do 5: tmp 0 ; 6: for all s do 7: s 0 j s ; 8: s 1 j s ; 9: tmp[s 0 ] tmp[s 0 ] + count[s]; 10: tmp[s 1 ] tmp[s 1 ] + count[s]; 11: end for 12: count tmp; 13: end for 14: end for { n+1 }} { 15: return count[ ]; 15 / 37
16 / 37
17 Simpath S 17 / 37
18 18 / 37
19 19 / 37
20 Motzkin Motzkin M 0 = M 1 = 1 M n = 3(n 1)M n 2 + (2n + 1)M n 1 n + 2 M n 3 (1, 0), (1, 1), (1, 1) (0, 0) (n, 0) M 7 = / 37
21 Motzkin = (1, 0), = (1, 1), = (1, 1) (0, 1) L (M L+1 M L ) 21 / 37
22 n n n + 1 : (M n+2 M n+1 ) 1 n + 1 n : (M n+1 M n ) (M n+2 M n ) 22 / 37
23 S φ : S {1, 2,..., S } {s k s S, k } count[φ(s)] 23 / 37
24 In-place 5 24 / 37
25 In-place 1: count 0 ; n+1 { }} { 2: count[ ] 1; 3: for i = 1 to n + 1 do 4: for j = 1 to n do 5: tmp 0 ; 6: for all s do 7: s 0 j s ; 8: s 1 j s ; 9: tmp[s 0 ] tmp[s 0 ] + count[s]; 10: tmp[s 1 ] tmp[s 1 ] + count[s]; 11: end for 12: count tmp; 13: end for 14: end for { n+1 }} { 15: return count[ ]; 25 / 37
26 In-place count In-place tmp 26 / 37
27 : = = = = = = = = = + 27 / 37
28 : / 37
29 : / 37
30 : m 1 m n m 2 ID 2 m 0 1 or m = 2 00 = 01 = or 10 = or 11 = or or 30 / 37
31 m 1, m 2,..., m k a 1, a 2,..., a k x a 1 (mod m 1 ) x a 2 (mod m 2 ). x a k (mod m k ) x m 1 m 2 m k 64 1/8 31 / 37
32 / 37
33 4 Original Grid-BS In-place Grid-FS Grid-BS Grid-FP Grid-FS CPU: Intel Xeon E / 2.67GHz / 32 cores Memory: 1.5TB / 37
34 CPU 1/3 1/3 12 1/10 34 / 37
35 In-place 1/5 35 / 37
36 / 37
37 In-place Intel Xeon E / 2.67GHz / 32 cores / 1.5TB memory = 1 480GB GB 37 / 37
素数ものさしの考察
( ) 2015 7 12 (2016.3.22 ) 1 / 18 18cm 2 3 5 7 11 13 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18cm 18 cm 1cm 18cm 1cm 2 / 18 1? 3 / 18 1? Yes 20 : (0),2,3,5,7,11,13,17,19,(20) (5 13 ) 42 : (0),2,3,5,7,11,13,17,19,23,29,31,37,41,(42)
2009 SEP. No.664 9 18 100460345 209710798 %0.11 3350955 9750799 12.1 0.93 100350 19 100600453 209700800 %0.03 3200065 9740873 11.0 0.98 90490 20 100750364 209680396 %0.81 321 844 978 591 11.6
P-12 P-13 3 4 28 16 00 17 30 P-14 P-15 P-16 4 14 29 17 00 18 30 P-17 P-18 P-19 P-20 P-21 P-22
1 14 28 16 00 17 30 P-1 P-2 P-3 P-4 P-5 2 24 29 17 00 18 30 P-6 P-7 P-8 P-9 P-10 P-11 P-12 P-13 3 4 28 16 00 17 30 P-14 P-15 P-16 4 14 29 17 00 18 30 P-17 P-18 P-19 P-20 P-21 P-22 5 24 28 16 00 17 30 P-23
2 2 ( M2) ( )
2 2 ( M2) ( ) 2007 3 3 1 2 P. Gaudry and R. Harley, 2000 Schoof 63bit 2 8 P. Gaudry and É. Schost, 2004 80bit 1 / 2 16 2 10 2 p: F p 2 C : Y 2 =F (X), F F p [X] : monic, deg F = 5, J C (F p ) F F p p Frobenius
P P P P P P P OS... P P P P P P
SAS Visual Analytics on MapR Converged Data Platform 2015 12 1. 1.1... P2 1.2... P2 2. 2.1... P3 2.2... P6 2.2.1... P6 2.2.2... P6 2.3... P10 3. 3.1 OS... P11 3.2... P12 3.3... P13 3.4... P13 3.5... P14
28/32/36D2700_H1_H4
DLTV 23552074 28D3000,32D3000 28D3000 32D3000 8 7 9 5 4 6 2 1 WOWOW BS955 DS9 3 12 11 /0 10 DS10 DS11 BS DS8 BS DS7 BS DS6 BS DS5 DS2 BS DS4 NHK 1 DS1 NHK 2 DS3 NHK h / / 12 11 10 10
ê ê ê 2007 ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê b b b b b b b b b b b ê ê ê b b b b ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê b
untitled
186 17 100160250 1 10.1 55 2 18.5 6.9 100 38 17 3.2 17 8.4 45 3.9 53 1.6 22 7.3 100 2.3 31 3.4 47 OR OR 3 1.20.76 63.4 2.16 4 38,937101,118 17 17 17 5 1,765 1,424 854 794 108 839 628 173 389 339 57 6 18613
untitled
1. 3 14 2. 1 12 9 7.1 3. 5 10 17 8 5500 4. 6 11 5. 1 12 101977 1 21 45.31982.9.4 79.71996 / 1997 89.21983 41.01902 6. 7 5 10 2004 30 16.8 37.5 3.3 2004 10.0 7.5 37.0 2004 8. 2 7 9. 6 11 46 37 25 55 10.
CPU Levels in the memory hierarchy Level 1 Level 2... Increasing distance from the CPU in access time Level n Size of the memory at each level 1: 2.2
FFT 1 Fourier fast Fourier transform FFT FFT FFT 1 FFT FFT 2 Fourier 2.1 Fourier FFT Fourier discrete Fourier transform DFT DFT n 1 y k = j=0 x j ω jk n, 0 k n 1 (1) x j y k ω n = e 2πi/n i = 1 (1) n DFT
- 1 - - 0.5%5 10 10 5 10 1 5 1
- - - 1 - - 0.5%5 10 10 5 10 1 5 1 - 2 - - - - A B A A A B A B B A - 3 - - 100 100 100 - A) ( ) B) A) A B A B 110 A B 13 - 4 - A) 36 - - - 5 - - 1 - 6-1 - 7 - - 8 - Q.15 0% 10% 20% 30% 40% 50% 60% 70%
求人面接資料PPT
Hair Salon TV etc. 250" 250" 200" 200" 150" 150" 100" 100" 50" 50" 0" 0" Nov)13" Dec)13" Jan)14" Feb)14" Mar)14" Apr)14" May)14" Jun)14" Jul)14" Dec)12" Jan)13" Feb)13" Mar)13" Apr)13"
GPGPU
GPGPU 2013 1008 2015 1 23 Abstract In recent years, with the advance of microscope technology, the alive cells have been able to observe. On the other hand, from the standpoint of image processing, the
untitled
A = QΛQ T A n n Λ Q A = XΛX 1 A n n Λ X GPGPU A 3 T Q T AQ = T (Q: ) T u i = λ i u i T {λ i } {u i } QR MR 3 v i = Q u i A {v i } A n = 9000 Quad Core Xeon 2 LAPACK (4/3) n 3 O(n 2 ) O(n 3 ) A {v i }
untitled
A = QΛQ T A n n Λ Q A = XΛX 1 A n n Λ X GPGPU A 3 T Q T AQ = T (Q: ) T u i = λ i u i T {λ i } {u i } QR MR 3 v i = Q u i A {v i } A n = 9000 Quad Core Xeon 2 LAPACK (4/3) n 3 O(n 2 ) O(n 3 ) A {v i }
23_33.indd
23 16 26 25 24 2 30 2 19 20 1 21 1 22 9 11 15 14 23 2 3 5 1 6 12 14 29 P.26 P.26 P.26 P.26 P.2 P.26 P.2 P.2 P.2 P.2 P.2 P.2 P.24 P.24 P.24 P.24 P.24 MAC 10. 10.6 10.5 1TB 2TB XP XP MAC 10. 10. 10.6 10.5
_2009MAR.ren
ISSN 0389-5254 2009 No.2 MAR JAPAN AIRCRAFT PILOT ASSOCIATION C O N T E N T S No.313 2009 No.2 MAR é 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR 2009 MAR
初めに：
2 Copyrightc2008 JETRO. All rights reserved. FAX 03-5572-7044 ...5...6 (1)...7... 11... 11...12...14...15...15...16...17...18 (4)...21 (5)...21 (6)...23 4 Copyrightc2008 JETRO. All rights reserved. 5 Copyrightc2008
NEC All rights reserved 1
NEC All rights reserved 1 NEC All rights reserved 2 NEC All rights reserved 3 (Founder) (Langchao Langchao) NEC All rights reserved 4 2.1 GB/s 64 bits wide 266 MHz 4 MB L3 on board, 96k L2, 32k L1 on -die
2 FLC5F-P
70mm 168 32 167 247 BSC45R-SET MASter of PROduction! e2! 1 2 FLC5F-P 3 4 3 1 2 FLC5F-P FP4 5 BSC45R 18 db/k 17 16 15 14 13 12 11.7 12.75GHz 36 db 35 34 33 32 11.7 12.75GHz 58 db 56 54 52 50 48 46 1 0.9
L4331/4431_000-.\..
LV-6/LV-3 P.6 P.56 P.66 P.70 P. 3 4 5 UHF VHF 6 7 8 4 5 3 3 4 5 6 7 8 9 0 BS CS/ 6 7 8 9 0 3 4 5 6 7 8 9 0 BS CS/ 3 3 4 5 6 7 8 9 0 BS CS/ 4 q w e r t y u i o!0!!!3 q w e!0 r!3 t y ui o!! o 5 6 7 8
DO 時間積分 START 反変速度の計算 contravariant_velocity 移流項の計算 advection_adams_bashforth_2nd DO implicit loop( 陰解法 ) 速度勾配, 温度勾配の計算 gradient_cell_center_surface 速
1 1, 2 1, 2 3 2, 3 4 GP LES ASUCA LES NVIDIA CUDA LES 1. Graphics Processing Unit GP General-Purpose SIMT Single Instruction Multiple Threads 1 2 3 4 1),2) LES Large Eddy Simulation 3) ASUCA 4) LES LES
459
459 40 5 200606-1,940 7 - - - 480.2 3.6+0.8 40 4,00010 0.791 50 5 200608-2,740 5 - - - 600.2 4.1+0.8 51 4,00010 1.122 65 5 200610-3,500 5 - - - 760.3 4.1+0.8 67 4,00010 1.445 75 5 200611-5,360 3 - - -
untitled
16 4 1 17 1 50 -1- -2- -3- -4- -5- -6- -7- 1 2-8- -9- -10- -11- Web -12- (1) (2)(1) (3) (4) (1)()(2) (3)(4) -13- -14- -15- -16- -17- -18- -19- -20- -21- -22- -23- (2)(1) (3) -24- -25- -26- -27- -28- -29-
23_33.indd
23 2TB 1TB 6TB 3TB 2TB 3TB 3TB 2TB 2TB 1TB 1TB 500GB 4TB 1TB 1TB 500GB 2TB 2TB 1TB 1TB RT RT RT RT RT RT RT MAC 10. 10. 10.6 10.5 MAC 10. 10. 10.6 10.5 MAC 10. 10.6 10.5 MAC 10. 10. 10.6 10.5 MAC 10. 10.6
MATLAB® における並列・分散コンピューティング ~ Parallel Computing Toolbox™ & MATLAB Distributed Computing Server™ ~
MATLAB における並列 分散コンピューティング ~ Parallel Computing Toolbox & MATLAB Distributed Computing Server ~ MathWorks Japan Application Engineering Group Takashi Yoshida 2016 The MathWorks, Inc. 1 System Configuration
/ / LIN X*** Y*** Z*** A*** F***; END; " " " " TB V10.jtd-2
2011/05/24 1 Y Y TB04-2394-V10.jtd-1 / / 1 1 2 3 4 5 6 6 6 5 1 2 4 5 1 1 1 4 3 4 3 1 2 1 2 LIN X*** Y*** Z*** A*** F***; END; " " " " TB04-2394-V10.jtd-2 1 LIN X1400 Y-1400 Z12 A0 F3000; LIN X0 Y-4000
Itanium2ベンチマーク
HPC CPU mhori@ile.osaka-u.ac.jp Special thanks Timur Esirkepov HPC 2004 2 25 1 1. CPU 2. 3. Itanium 2 HPC 2 1 Itanium2 CPU CPU 3 ( ) Intel Itanium2 NEC SX-6 HP Alpha Server ES40 PRIMEPOWER SR8000 Intel
Plan of Talk CAS CAS 2 CAS Single Sign On CAS CAS 2 CAS Aug. 19, 2005 NII p. 2/32
CAS Single Sign On naito@math.nagoya-u.ac.jp naito@math.nagoya-u.ac.jp, Aug. 19, 2005 NII p. 1/32 Plan of Talk CAS CAS 2 CAS Single Sign On CAS CAS 2 CAS naito@math.nagoya-u.ac.jp, Aug. 19, 2005 NII p.
chapter4.PDF
4. 4.1. 4.2. 63 4 1 4.3. 4.3.1. 4 a) 1 5 b) 1 c) d) 1 4.3.2. a) b) c) a) 10 18 b) 2 17 2 1 54 2 1 c) 11 4 1 1 (TB) (FB) TB FB 4.3.3. 4.3.4. 1 18 16 4.3.5. a) b) 18 16 a) b) c) 1 18 16 2 1 18 16 3 18 16
01_OpenMP_osx.indd
OpenMP* / 1 1... 2 2... 3 3... 5 4... 7 5... 9 5.1... 9 5.2 OpenMP* API... 13 6... 17 7... 19 / 4 1 2 C/C++ OpenMP* 3 Fortran OpenMP* 4 PC 1 1 9.0 Linux* Windows* Xeon Itanium OS 1 2 2 WEB OS OS OS 1 OS
B 5 (2) VBA R / B 5 ( ) / 34
B 5 (2) VBAR / B 5 (2014 11 17 ) / 34 VBA VBA (Visual Basic for Applications) Visual Basic VBAVisual Basic Visual BasicC B 5 (2014 11 17 ) 1 / 34 VBA 2 Excel.xlsm 01 Sub test() 02 Dim tmp As Double 03
単位、情報量、デジタルデータ、CPUと高速化 ～ICT用語集～
CPU ICT mizutani@ic.daito.ac.jp 2014 SI: Systèm International d Unités SI SI 10 1 da 10 1 d 10 2 h 10 2 c 10 3 k 10 3 m 10 6 M 10 6 µ 10 9 G 10 9 n 10 12 T 10 12 p 10 15 P 10 15 f 10 18 E 10 18 a 10 21
-1-1 1 1 1 1 12 31 2 2 3 4
2007 -1-1 1 1 1 1 12 31 2 2 3 4 -2-5 6 CPU 3 Windows98 1 -3-2. 3. -4-4 2 5 1 1 1 -5- 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000-6- -7-1 Windows 2 -8-1 2 3 4 - - 100,000 200,000 500,000
L422277A_Xserve_Guide_01
2010 11 2 Apple 2011 1 31 Mac OS X Server Snow Leopard Server Mac Pro Snow Leopard Server Mac mini Apple2011 1 31 Apple 2 Snow Leopard Server Mac Pro Mac Pro Mac OS X ServerMac Pro 12U2 Snow Leopard Server
"CAS を利用した Single Sign On 環境の構築"
CAS Single Sign On (Hisashi NAITO) naito@math.nagoya-u.ac.jp Graduate School of Mathematics, Nagoya University naito@math.nagoya-u.ac.jp, Oct. 19, 2005 Tohoku Univ. p. 1/40 Plan of Talk CAS CAS 2 CAS Single
p03.dvi
301 3 : 1 (1) f(x) = 0 f(x) x.,, z. : 2 (2) z f(z) = a 0 z n +a 1 z n 1 + +a n 1 z +a n f(z) = 0 ( ),. a 0, a n. : 3 (3),, B(s) = b 0s m +b 1 s m 1 + +b 0 A(s) s n +a 1 s n 1 +a n, (s n +a 1 s n 1 +a n
untitled
facebook facebook facebook facebook http://www.toritsugimanabu.com/ facebook facebook http://www.facebook.com/social10000?v=app_4949752878&ref=sgm facebook facebook facebook facebook http://www.facebook.com/social10000?v=app_4949752878&ref=sgm
template.dvi
XXVI W I D E P R O J E C T 26 26 1 WIDE 2010 1 WIDE WIDE Cloud 2010 2 3 4 5 6 NAT64 7 2 2010 7 2 WIDE 2.1 WIDE WIDE WIDE WIDE 50 2.2 WIDE 13:00 14:45 IaaS 15:00 16:45 WIDE StarBED 17:00 19:00 2.3 193
3. XML, DB, DB (AP). DB, DB, AP. RDB., XMLDB, XML,.,,.,, (XML / ), XML,,., AP. AP AP AP 検索キー //A=1 //A=2 //A=3 返却 XML 全体 XML 全体 XML 全体 XMLDB <root> <A
PostgreSQL XML 1 1 1 1 XML,,, /. XML.,,, PostgreSQL.. Implementation of Yet Another XML-type for PostgreSQL Toshifumi Enomoto, 1 Gengo Suzuki, 1 Nobuyuki Kobayashi 1 and Masashi Yamamuro 1 There are various
ビッグデータアナリティクス - 第3回: 分散処理とApache Spark
3 : Apache Spark 2017 10 20 2017 10 20 1 / 32 2011 1.8ZB 2020 35ZB 1ZB = 10 21 = 1,000,000,000,000 GB Word Excel XML CSV JSON text... 2017 10 20 2 / 32 CPU SPECfp Pentium G3420 77.6 8,946 Xeon Gold 6128
広報さがみはら第1242号
LINE UP 3 1 5 6 1 NO.1242 S A G A M I H A R A 1 1 1 16 16 1 6 1 6 1 6 1 1 1 1 1 11 1 1 1 1 1 1 6 1 6 1 1 1 1 1 1 1 1 11 1 1 16 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 16 1 16 1 6 1 1 1 1 1 1
Microsoft Word - nvsi_100221jp_vdr_extended_partition.doc
Article ID: NVSI-100221JP Created: 2010/09/07 Revised: - VaultDR Offline で 大 きいディスクにリストアした 際 のディスクの 有 効 利 用 1. 概 要 VaultDR Offline でバックアップしたシステムで すでに 拡 張 パーティションが 作 成 されていたりするなどして パー ティションの 大 きさに 制 限 がされている
IBM Software Group DB2 Information Management Software DB2 V8 XML SQL/XML 2 XML XML UDF XMLExtender XML XML XMLCollection, XMLColumn XML UDF Informati
IBM Software Group XML Features in DB2 UDB V8 IBM Software Group DB2 Information Management Software DB2 V8 XML SQL/XML 2 XML XML UDF XMLExtender XML XML XMLCollection, XMLColumn XML UDF Information Integrator
Microsoft PowerPoint - GPUシンポジウム _d公開版.ppt [互換モード]
![Microsoft PowerPoint - GPUシンポジウム _d公開版.ppt [互換モード]](/thumbs/102/156675429.jpg "Microsoft PowerPoint - GPUシンポジウム _d公開版.ppt [互換モード]")
200/0/9 数値流体解析の並列効率とその GPU による高速化の試み 清水建設 ( 株 ) 技術研究所 PHAM VAN PHUC ( ファムバンフック ) 流体計算時間短縮と GPU の活用の試み 現 CPUとの比較によりGPU 活用の可能性 現 CPU の最大利用 ノード内の最大計算資源の利用 すべてCPUコアの利用 適切なアルゴリズムの利用 CPU コア性能の何倍? GPU の利用の試み
untitled
CA Easytrieve CA Technologies CA Easytrieve P 3 7 P 8 30 16 DB2 IMS IMS ADABAS JCL OS 2 Copyright 2012 CA. All rights reserved. CA Easytrieve CA Easytrieve CA Easytrieve CA Easytrieve COBOL,PL/I 3 Copyright
…_…C…L…fi…J…o†[fiü“ePDF/−mflF™ƒ
80 80 80 3 3 5 8 10 12 14 14 17 22 24 27 33 35 35 37 38 41 43 46 47 50 50 52 54 56 56 59 62 65 67 71 74 74 76 80 83 83 84 87 91 91 92 95 96 98 98 101 104 107 107 109 110 111 111 113 115