Scribd
Upload
11 views

hpc_intro

Uploaded by

Rajul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views

hpc_intro

Uploaded by

Rajul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

A Taste of Scientific Computing

Victor Eijkhout

2022

Eijkhout: HPC taste


What is Scientific Computing about?

You know the science; what more is there?

Science often gives an implicit description.


How do you turn it into something computational.
Algorithms are not unique:
There are many ways to solve a linear system

? : Ax = b
x

What are pros and cons of the choices?


Algorithms can be implemented multiple ways, depending on your
processor.

Eijkhout: HPC taste


Algorithmic choices

Eijkhout: HPC taste


Summing forces

Eijkhout: HPC taste


Particle interactions

for each particle i


for each particle j
let r̄ij be the vector between i and j;
then the force on i because of j is
mm
fij = −r̄ij |ri | j
ij
(where mi , mj are the masses or charges) and
fji = −fij .

Naive all-pairs algorithm: O (N 2 )

Eijkhout: HPC taste


Clever algorithms: O (N log N ), sometimes even O (N )

Eijkhout: HPC taste


Algorithm aspects

Eijkhout: HPC taste


Linear algebra

? : Ax = b
x

Inversion: N 3 operations, unstable


Gaussian elimination: N 3 but lower constant, stable
Sparse Gaussian elimination: N 3/2 , hard to program
Iterative methods: N · κ1/2 , not always successful
Multigrid: O (N ), very limited applicability.

Eijkhout: HPC taste


Sparse matrices

Eijkhout: HPC taste


Permuting the matrix

Eijkhout: HPC taste


The influence of your
architecture

Eijkhout: HPC taste


Fitting data to cache

for (j=0; j<size; j++)


array[j] = 2.3*array[j]+1.2;

12 2.0

10
1.8

8
Cache miss fraction

1.6

cycles per op
6
1.4
4

1.2
2

00 5 10 15 20 25 301.0
dataset size

Eijkhout: HPC taste


Matrix-matrix product

Lots of small optimizations add up:

Eijkhout: HPC taste


Computer arithmetic

Computer numbers are not real numbers. If you don’t pay attention to this you
may lose you a race car, or a rocket

Eijkhout: HPC taste


So what is scientific computing
about?

Eijkhout: HPC taste


Between science and computing

Modeling
Numerical analysis
Linear algebra
Computer architecture
. . . and the interaction between any and all of these.

Eijkhout: HPC taste

You might also like