4005-730 Distributed Systems
Lecture Notes -- Module 9. Supercomputing

An Example Problem

• A toxic spill contaminates the soil

  Initial spill		The pollutant starts diffusing		After a longer time

• Partial differential equation: ∂u/∂t = D (∂²u/∂x² + ∂²u/∂y²)

• Computation
  • Given diffusion coefficients D(x,y) . . .
  • And given initial pollutant concentration u(x,y) . . .
  • Compute pollutant concentration as a function of time . . .
  • On an N×N spatial grid (N might be several thousand) . . .
  • For many, many small time steps (thousands or millions) . . .
  • And make a movie to visualize the results

• Class ToxicSpillSeq (download)

SMP Parallel Programming

• OpenMP Home Page. http://www.openmp.org/

• Parallel Java Library. http://www.cs.rit.edu/~ark/pj.shtml

• Class ToxicSpillSmp (download)

• Running times (msec) on one node of the tardis.cs.rit.edu computer
  • N = Grid size
  • NT = Number of parallel threads
  • SMP computation amount = Sequential computation amount ("strong scaling")
  • Ideally, SMP time = (1/NT)×sequential time
  • Speedup = Sequential time/SMP time
  • Efficiency = Speedup/NT

  $ java ToxicSpillSeq 142857 $N 0.01 50 400
  $ java -Dpj.nt=$NT ToxicSpillSmp 142857 $N 0.01 50 400
  
     N   NT      T1      T2      T3       T  Spdup  Effic
  1000  seq  262621  262497  262944  262497
  1000    1  264094  265627  262970  262970  0.998  0.998
  1000    2  159800  160433  158530  158530  1.656  0.828
  1000    3  118103  117248  123653  117248  2.239  0.746
  1000    4  106365   98636  100802   98636  2.661  0.665
  

Cluster Parallel Programming

• The Message Passing Interface (MPI) Standard. http://www-unix.mcs.anl.gov/mpi/

• Parallel Java Library. http://www.cs.rit.edu/~ark/pj.shtml

• Class ToxicSpillClu (download)

• Running times (msec) on 1 to 10 nodes of the tardis.cs.rit.edu computer
  • N = Grid size
  • NP = Number of parallel processes
  • Cluster computation amount = NP×Sequential computation amount ("weak scaling")
  • Ideally, cluster time = sequential time
  • Efficiency = Sequential time/Cluster time
  • Sizeup = Efficiency×NP

  $ java ToxicSpillSeq 142857 $N 0.01 50 400
  $ java -Dpj.np=$NP ToxicSpillClu 142857 $N 0.01 50 400
  
     N   NT      T1      T2      T3       T  Sizup  Effic
  1000  seq  262621  262497  262944  262497
  1000    1  265259  263263  263973  263263  0.997  0.997
  1414    2  273991  273570  277884  273570  1.919  0.960
  1732    3  267582  268205  267738  267582  2.943  0.981
  2000    4  280138  279639  277523  277523  3.783  0.946
  2236    5  281795  282604  281097  281097  4.669  0.934
  2449    6  292899  292335  293445  292335  5.388  0.898
  2646    7  292031  291103  291091  291091  6.312  0.902
  2828    8  301575  303670  303386  301575  6.963  0.870
  3000    9  274363  272176  273202  272176  8.680  0.964
  3162   10  293309  292879  294578  292879  8.963  0.896
  

Hybrid SMP Cluster Parallel Programming

• Parallel Java Library. http://www.cs.rit.edu/~ark/pj.shtml

• Class ToxicSpillHyb (download)

• Running times (msec) on 1 to 10 nodes of the tardis.cs.rit.edu computer
  • N = Grid size
  • NP = Number of parallel processes
  • NT = Number of parallel threads per process
  • Cluster computation amount = NP×Sequential computation amount ("weak scaling")
  • Ideally, cluster time (for NT = 1) = sequential time
  • Efficiency (for NT = 1) = Sequential time/Cluster time
  • Sizeup = Efficiency×NP
  • Speedup = NP×Sequential time/Cluster time
  • Efficiency (of speedup) = Speedup/(NP×NT)

  $ java ToxicSpillSeq 142857 $N 0.01 50 400
  $ java -Dpj.np=$NP -Dpj.nt=$NT ToxicSpillHyb 142857 $N 0.01 50 400
  
     N   NT   NT      T1      T2      T3       T  Sizup  Effic   Spdup  Effic
  1000  seq  seq  262621  262497  262944  262497
  
  1000    1    1  263261  263282  264324  263261  0.997  0.997   0.997  0.997
  1000    1    2  160303  159772  160856  159772                 1.643  0.821
  1000    1    3  120658  122926  119118  119118                 2.204  0.735
  1000    1    4   99424   99687   99130   99130                 2.648  0.662
  
  1414    2    1  277448  277208  278598  277208  1.894  0.947   1.894  0.947
  1414    2    2  159554  160026  159646  159554                 3.290  0.823
  1414    2    3  112005  112904  114167  112005                 4.687  0.781
  1414    2    4   99666  100582   99661   99661                 5.268  0.658
  
  1732    3    1  271478  268783  265674  265674  2.964  0.988   2.964  0.988
  1732    3    2  156087  157186  155149  155149                 5.076  0.846
  1732    3    3  129195  128524  130292  128524                 6.127  0.681
  1732    3    4  108991  109581  110394  108991                 7.225  0.602
  
  2000    4    1  278789  280878  282309  278789  3.766  0.942   3.766  0.942
  2000    4    2  174955  176111  176490  174955                 6.001  0.750
  2000    4    3  126928  126807  126678  126678                 8.289  0.691
  2000    4    4  119312  119057  117192  117192                 8.960  0.560
  
  2236    5    1  278990  282125  283478  278990  4.704  0.941   4.704  0.941
  2236    5    2  182128  182006  181720  181720                 7.223  0.722
  2236    5    3  139134  142793  139247  139134                 9.433  0.629
  2236    5    4  118087  117748  119232  117748                11.147  0.557
  
  2449    6    1  294478  292990  295282  292990  5.376  0.896   5.376  0.896
  2449    6    2  179972  180410  181517  179972                 8.751  0.729
  2449    6    3  144379  143871  144403  143871                10.947  0.608
  2449    6    4  126528  127588  128717  126528                12.448  0.519
  
  2646    7    1  290527  293894  292735  290527  6.325  0.904   6.325  0.904
  2646    7    2  180141  179757  181923  179757                10.222  0.730
  2646    7    3  147671  145664  146435  145664                12.615  0.601
  2646    7    4  128993  129066  135903  128993                14.245  0.509
  
  2828    8    1  301686  305434  301451  301451  6.966  0.871   6.966  0.871
  2828    8    2  190790  190606  191097  190606                11.017  0.689
  2828    8    3  154367  153908  155279  153908                13.644  0.569
  2828    8    4  138931  137272  136388  136388                15.397  0.481
  
  3000    9    1  274849  274722  274109  274109  8.619  0.958   8.619  0.958
  3000    9    2  189491  189447  190114  189447                12.470  0.693
  3000    9    3  154827  154031  155999  154031                15.338  0.568
  3000    9    4  139038  142835  139624  139038                16.992  0.472
  
  3162   10    1  295506  291521  292335  291521  9.004  0.900   9.004  0.900
  3162   10    2  180689  179803  179719  179719                14.606  0.730
  3162   10    3  156541  157270  158890  156541                16.769  0.559
  3162   10    4  141045  140720  135661  135661                19.349  0.484
  

GPU Parallel Programming

• GPGPU: http://www.gpgpu.org/

• NVIDIA CUDA Zone: http://developer.nvidia.com/category/zone/cuda-zone

• OpenCL: http://www.khronos.org/opencl/

• Program ToxicSpillCpu (download)

• Program ToxicSpillGpu (download)

• Other source files
  • Random.cu (download)
  • Util.cu (download)
  • Makefile (download)

• Running times (msec) on a desktop CPU and on a GPU
  • Desktop: Intel Pentium, 2.7 GHz, 4 GB memory
  • GPU: NVIDIA Tesla C2050, 448 cores, 1.15 GHz, 3 GB global memory
  • N = Grid size
  • Speedup = ToxicSpillCpu time/ToxicSpillGpu time

  $ ToxicSpillCpu 142857 $N 0.01 50 400
  $ ToxicSpillGpu 142857 $N 0.01 50 400
  
        --------ToxicSpillCpu  ----ToxicSpillGpu
     N  pre     calc    total  pre   calc  total  Speedup
   100    2     5676     5678   61    899    960     5.91
   141    3    16095    16098   60    957   1017    15.83
   200    7    40180    40187   66   1095   1161    34.61
   283   11    56358    56369   66   1402   1468    38.40
   400   13    91177    91190   76   1857   1933    47.18
   566   30   169241   169271   90   2983   3073    55.08
   800   53   329403   329456  116   4656   4772    69.03
  1131  103   604256   604359  174   9073   9247    65.36
  1600  209  1120617  1120826  283  15743  16026    69.94
  

The Top 500 Supercomputers

• Processing speed
  • 1 flops = 1 floating point operation per second
  • 1 gigaflops = 10⁹ flops
  • 1 teraflops = 10¹² flops
  • 1 petaflops = 10¹⁵ flops
  • 1 exaflops = 10¹⁸ flops

• Memory capacity
  • 1 gigabyte = 10⁹ bytes
  • 1 terabyte = 10¹² byte
  • 1 petabyte = 10¹⁵ byte
  • 1 exabyte = 10¹⁸ byte

• Top500 List: http://www.top500.org/
  • Measures processing speed on the LINPACK linear algebra benchmark
  • CPU intensive benchmark

• Number One supercomputer: Titan (November 2012)
  • Location: Oak Ridge National Laboratory, USA
  • Manufacturer: Cray
  • Model: XK7
  • CPU: Opteron 6274 16C
  • Clock speed: 2.2 GHz
  • Cores: 560,640
  • Processing speed: 17.5 petaflops
  • RAM: 0.71 petabytes
  • Accelerators: 261,632 NVIDIA K20x

• Number Two supercomputer: Sequoia (November 2012)
  • Location: Lawrence Livermore National Laboratory, USA
  • Manufacturer: IBM
  • Model: BlueGene/Q
  • CPU: Power BQC 16C
  • Clock speed: 1.6 GHz
  • Cores: 1,572,864
  • Processing speed: 16.3 petaflops
  • RAM: 1.57 petabytes
  • Accelerators: None

• Number Three supercomputer: K Computer (November 2012)
  • Location: RIKEN Advanced Institute for Computational Science, Japan
  • Manufacturer: Fujitsu
  • CPU: SPARC64 CIIIfx
  • Clock speed: 2.0 GHz
  • Cores: 705,024
  • Processing speed: 10.5 petaflops
  • RAM: 1.41 petabytes
  • Accelerators: None

• Graph500 List: http://www.graph500.org/
  • Measures processing speed on selected graph algorithms
  • Data intensive benchmark

• Green500 List: http://www.green500.org/
  • Uses the Top500 List data
  • Ranks computers based on energy efficiency -- performance per watt

Distributed Systems 4005-730-01 Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 05-Feb-2013. Please send comments to ark­@­cs.rit.edu.