Software Tools for High-Performance Graph ... - Blue Sky eLearn

2 downloads 150 Views 13MB Size Report
Feb 15, 2012 - don't know how to program a supercomputer. • Easy-‐to-‐use Python interface. • Runs on a laptop a
Software Tools for High-Performance Graph Computation John R. Gilbert University of California, Santa Barbara

SIAM Parallel Processing for Scientific Computing February 15, 2012 1

Support: Intel, Microsoft, DOE Office of Science, NSF

Top 500 List (November 2011)

Top500 Benchmark: Solve a large system of linear equations by Gaussian elimination

P

A 2

=

L

x

U

Graph 500 List (November 2011) Graph500 Benchmark: Breadth-first search in a large power-law graph 1

2

4

7

3

3

6

5

Floating-Point vs. Graphs, November 2011

254 Gigateps

10.5 Petaflops

P

A

=

L

x

U

1

2

4

7

3

6

10.5 Peta / 254 Giga is about 41,000!

4

5

Floating-Point vs. Graphs, November 2010

6.6 Gigateps

2.5 Petaflops

P

A

=

L

x

U

1

2

4

7

3

6

2.5 Peta / 6.6 Giga is about 380,000!

5

5

Middleware for scientific computation

Continuous physical modeling

Discrete structure analysis

Linear algebra

Graph theory

Computers

6

Computers

!*31,)5()$ "%&>37)+0$ #33,/3?$

.O-X``@528&3;+>)=3+()8*)2`$

$

'>2;',,0$)?%&28$$Y$5%+)>2)5$(+'-.$%&$%&363+-.%>$23$'$&-

!"#$%&$'$()*)+',$(+'-.$,%/+'+0$1%2.$(+' #. -+37%5)&$'*$)'&0:23:;&)$3,,'/3+'43*$'63*($EFGHD$I' 7)

#)>.*%>',$F36-;4*(8$#.)$&3L1'+)$ #.)$HIYG$5)T*)5$'$&2'*5'+5$%*2)+='>)$=3+$*;6)+%>' M+'-.$HIYGÄD$'$&2'*5'+5$&)2$3=$(+'-.$-+%6%47)&8$G) 5'2'$'>>)&&$-'O)+*&$'&$1),,:@*31*$&-'+&)$,%*)'+$',( 3-)+'43*&$'+)$',()/+'%>D$*3+$'+)$',,$',()/+'%>$HIYG$3

A  general  graph  library  with   opera1ons  based  on  linear   $ !/A)&('!J)9&23+&$+)-+)&)*2$7)+4>)&D$1%2.$2.)%+$),)6)*2&$/)%*($ #.)$+)&;,2$%&$6;,4-,)$,)7),&$3=$-'+',,),%&6X$7)+4>)&D$ 7)+2)?$'O+%/;2)&8$K'2+%?$3-)+'43*&$'+)$;&)5$=3+$(+'-.$2+'7)+&',&8$Q3+$ Y$&-'+&)$%*>%5)*>)$6'2+%?$>'*$',&3$+)-+)&)*2$'$.0-) )?'6-,)D$'$G-'+&)$K'2+%?:P)>23+$6;,4-,%>'43*$%&$;&)5$23$2+'7)+&)$',,$ +),) Y*$%*&-%+'43*$=3+$2.)$M+'-.$HIYG$%&$3;+$)'+,%)+$5%&2 3;2(3%*($)5()&$=+36$'$7)+2)?8$#+'7)+&',$,3(%>$%&$.'*5,)5$/0$&)6%+%*($ 1.%>.$-31)+&$2.)$>;++)*2$7)+&%3*$3=$!"#8$ 3/R)>2&$1.%>.$>3++)&-3*5$1%2.$2.)$6;,4-,0$'*5$'55$3-)+'43*&$3=$'$ 2+'5%43*',$K'2+%?:P)>23+$6;,4-,%>'43*8$

@')*!)AA*,;&2)+$1%2.$BCDCCC$-+3>)&&3 +)

P) !"#$%&$'$>3,,'/3+'43*$'63*($EFGHD$I' 7)

#)>.*%>',$F36-;4*(8$#.)$&3L1'+)$ #.)$HIYG$5)T*)5$'$&2'*5'+5$%*2)+='>)$=3+$*;6)+%>' M+'-.$HIYGÄD$'$&2'*5'+5$&)2$3=$(+'-.$-+%6%47)&8$G) 5'2'$'>>)&&$-'O)+*&$'&$1),,:@*31*$&-'+&)$,%*)'+$',( 3-)+'43*&$'+)$',()/+'%>D$*3+$'+)$',,$',()/+'%>$HIYG$3

A  general  graph  library  with   opera1ons  based  on  linear   $ !/A)&('!J)9&23+&$+)-+)&)*2$7)+4>)&D$1%2.$2.)%+$),)6)*2&$/)%*($ #.)$+)&;,2$%&$6;,4-,)$,)7),&$3=$-'+',,),%&6X$7)+4>)&D$ 7)+2)?$'O+%/;2)&8$K'2+%?$3-)+'43*&$'+)$;&)5$=3+$(+'-.$2+'7)+&',&8$Q3+$ •  Easy-­‐to-­‐use  Python  interface   Y$&-'+&)$%*>%5)*>)$6'2+%?$>'*$',&3$+)-+)&)*2$'$.0-) )?'6-,)D$'$G-'+&)$K'2+%?:P)>23+$6;,4-,%>'43*$%&$;&)5$23$2+'7)+&)$',,$ +),) • 3;2(3%*($)5()&$=+36$'$7)+2)?8$#+'7)+&',$,3(%>$%&$.'*5,)5$/0$&)6%+%*($ Runs  on  a  laptop  as  well  as  a  cluster  wY*$%*&-%+'43*$=3+$2.)$M+'-.$HIYG$%&$3;+$)'+,%)+$5%&2 ith  10,000  processors   1.%>.$-31)+&$2.)$>;++)*2$7)+&%3*$3=$!"#8$ 3/R)>2&$1.%>.$>3++)&-3*5$1%2.$2.)$6;,4-,0$'*5$'55$3-)+'43*&$3=$'$ 2+'5%43*',$K'2+%?:P)>23+$6;,4-,%>'43*8$

 

@')*!)AA*,;&2)+$1%2.$BCDCCC$-+3>)&&3 +)

P) !"#$%&$'$>3,,'/3+'43*$'63*($EFGHD$I' 7)

#)>.*%>',$F36-;4*(8$#.)$&3L1'+)$ #.)$HIYG$5)T*)5$'$&2'*5'+5$%*2)+='>)$=3+$*;6)+%>' M+'-.$HIYGÄD$'$&2'*5'+5$&)2$3=$(+'-.$-+%6%47)&8$G) 5'2'$'>>)&&$-'O)+*&$'&$1),,:@*31*$&-'+&)$,%*)'+$',( 3-)+'43*&$'+)$',()/+'%>D$*3+$'+)$',,$',()/+'%>$HIYG$3

A  general  graph  library  with   opera1ons  based  on  linear   $ !/A)&('!J)9&23+&$+)-+)&)*2$7)+4>)&D$1%2.$2.)%+$),)6)*2&$/)%*($ #.)$+)&;,2$%&$6;,4-,)$,)7),&$3=$-'+',,),%&6X$7)+4>)&D$ 7)+2)?$'O+%/;2)&8$K'2+%?$3-)+'43*&$'+)$;&)5$=3+$(+'-.$2+'7)+&',&8$Q3+$ •  Easy-­‐to-­‐use  Python  interface   Y$&-'+&)$%*>%5)*>)$6'2+%?$>'*$',&3$+)-+)&)*2$'$.0-) )?'6-,)D$'$G-'+&)$K'2+%?:P)>23+$6;,4-,%>'43*$%&$;&)5$23$2+'7)+&)$',,$ +),) • 3;2(3%*($)5()&$=+36$'$7)+2)?8$#+'7)+&',$,3(%>$%&$.'*5,)5$/0$&)6%+%*($ Runs  on  a  laptop  as  well  as  a  cluster  wY*$%*&-%+'43*$=3+$2.)$M+'-.$HIYG$%&$3;+$)'+,%)+$5%&2 ith  10,000  processors   1.%>.$-31)+&$2.)$>;++)*2$7)+&%3*$3=$!"#8$ 3/R)>2&$1.%>.$>3++)&-3*5$1%2.$2.)$6;,4-,0$'*5$'55$3-)+'43*&$3=$'$ • 2+'5%43*',$K'2+%?:P)>23+$6;,4-,%>'43*8$ A  collabora1on  among  UCSB,  UCB,  Lawrence  Berkeley  Lab,  and    

MicrosoI  Technical  Compu1ng   • @')*!)AA*