Strumenti Utente

Strumenti Sito


A case study

2D Cellular Automata

CA with periodic boundary conditions is a simple example suitable for our purpose

  • fine grained parallelism, domain decomposition, high rate of local communications

Algorithm and parallel approach are similar to other problems in computational physics

  • e.g. Finite Difference Method, Computational Fluid Dynamics, Lattice QCD, etc.

As a simple example of this method we implement the game of life.

In a bidimensional grid the cellS are either “alive” or “dead” and their state is updated in synchrony; the new state is determined by the following rules:

  • If a cell is empty (“dead”) and has exactly 3 neighbors, it has enough resources to be born without being overcrowded, and the next turn will be “alive”
  • If a cell is alive and has 3 or 4 neighbors, it has resources without being overcrowded and will stay “alive”.
  • If a cell has less than 2 neighbors, it cannot get enough resources to survive and the next turn will be “dead”.
  • If a cell has more than 4 neighbors, it will be overcrowded and the next turn will be dead.

Serial implementation

openMP implementation

Example: a Whole Node 4 cores

  • 1D domain decomposition
  • Rows and columns are exchanged via memory transfers by a single thread

MPI implementation

Example: 4 MPI processes (2 on node1, 2 on node2)

  • Rows and columns are exchanged via Mpi messages

Hybrid openMP and MPI implementation

Example: 2 MPI processes with 4 threads each

openMP 1D horizontal domain decomposition

  • Columns are exchanged via memory transfers

MPI 1D vertical domain decomposition

  • Rows are exchanged via MPI messages

/var/www/html/dokuwiki/data/pages/grid/life.txt · Ultima modifica: Y/m/d H:i da