examples/mpi/overview.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prerequisites\n",
    "\n",
    "This notebook contains examples which are expected *to be run with exactly 4 MPI processes*; not because they wouldn't work otherwise, but simply because it's what their description assumes. For this, you need to:\n",
    "\n",
    "* Install an MPI distribution on your system, such as OpenMPI, MPICH, or Intel MPI (if not already available).\n",
    "* Install some optional dependencies, including `mpi4py` and `ipyparallel`; from the root Devito directory, run\n",
    "```\n",
    "pip install -r requirements-optional.txt\n",
    "```\n",
    "* Create an `ipyparallel` MPI profile, by running our simple setup script. From the root directory, run\n",
    "```\n",
    "./scripts/create_ipyparallel_mpi_profile.sh\n",
    "```\n",
    "\n",
    "## Launch and connect to an ipyparallel cluster\n",
    "\n",
    "We're finally ready to launch an ipyparallel cluster. Open a new terminal and run the following command\n",
    "```\n",
    "ipcluster start --profile=mpi -n 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the engines have started successfully, we can connect to the cluster"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ipyparallel as ipp\n",
    "c = ipp.Client(profile='mpi')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this tutorial, to run commands in parallel over the engines, we will use the %px line magic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[stdout:0] Hi, I'm rank 0.\n",
      "[stdout:1] Hi, I'm rank 1.\n",
      "[stdout:2] Hi, I'm rank 2.\n",
      "[stdout:3] Hi, I'm rank 3.\n"
     ]
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "\n",
    "from mpi4py import MPI\n",
    "print(f\"Hi, I'm rank %d.\" % MPI.COMM_WORLD.rank)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview of MPI in Devito\n",
    "\n",
    "Distributed-memory parallelism via MPI is designed so that users can \"think sequentially\" for as much as possible. The few things requested to the user are:\n",
    "\n",
    "* Like any other MPI program, run with `mpirun -np X python ...`\n",
    "* Some pre- and/or post-processing may be rank-specific (e.g., we may want to plot on a given MPI rank only, even though this might be hidden away in the next Devito releases, when newer support APIs will be provided.\n",
    "* Parallel I/O (if and when necessary) to populate the MPI-distributed datasets in input to a Devito Operator. If a shared file system is available, there are a few simple alternatives to pick from, such as NumPy’s memory-mapped arrays.\n",
    "\n",
    "To enable MPI, users have two options. Either export the environment variable `DEVITO_MPI=1` or, programmatically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "from devito import configuration\n",
    "configuration['mpi'] = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "# Keep generated code as simple as possible\n",
    "configuration['language'] = 'C'\n",
    "# Fix platform so that this notebook can be tested by py.test --nbval\n",
    "configuration['platform'] = 'knl7210'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An `Operator` will then generate MPI code, including sends/receives for halo exchanges. Below, we introduce a running example through which we explain how domain decomposition as well as data access (read/write) and distribution work. Performance optimizations are discussed [in a later section](#Performance-optimizations).\n",
    "\n",
    "Let's start by creating a `TimeFunction`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "from devito import Grid, TimeFunction, Eq, Operator \n",
    "grid = Grid(shape=(4, 4))\n",
    "u = TimeFunction(name=\"u\", grid=grid, space_order=2, time_order=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Domain decomposition is performed when creating a `Grid`. Users may supply their own domain decomposition, but this is not shown in this notebook. Devito exploits the MPI Cartesian topology abstraction to logically split the `Grid` over the available MPI processes. Since `u` is defined over a decomposed `Grid`, its data get distributed too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:5]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.691623",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 5,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "be623dbb-0af53fb3974a05e5fd4af3f6",
      "outputs": [],
      "received": "2019-06-19T06:09:47.697941",
      "started": "2019-06-19T06:09:47.630825",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.627346"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:5]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.688816",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 5,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "afa1298d-c544c999e9bfd8f5d50f311e",
      "outputs": [],
      "received": "2019-06-19T06:09:47.692250",
      "started": "2019-06-19T06:09:47.633054",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.628877"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:5]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.691360",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 5,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "311aaa94-6d55196070812886b5c43af4",
      "outputs": [],
      "received": "2019-06-19T06:09:47.695594",
      "started": "2019-06-19T06:09:47.633895",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.629936"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:5]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.685792",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 5,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "53662981-6edfce63f6ea574ae51e6193",
      "outputs": [],
      "received": "2019-06-19T06:09:47.690795",
      "started": "2019-06-19T06:09:47.633853",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.630523"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "u.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Globally, `u` consists of 4x4 points -- this is what users \"see\". But locally, as shown above, each rank has got a 2x2 subdomain. The key point is: **for the user, the fact that `u.data` is distributed is completely abstracted away -- the perception is that of indexing into a classic NumPy array, regardless of whether MPI is enabled or not**. All sort of NumPy indexing schemes (basic, slicing, etc.) are supported. For example, we can write into a slice-generated view of our data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "u.data[0, 1:-1, 1:-1] = 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:7]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [0., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.771650",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [0., 1.]]], dtype=float32)"
       },
       "execution_count": 7,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "5c509b04-8db27a4a07b0db9e6c850213",
      "outputs": [],
      "received": "2019-06-19T06:09:47.777526",
      "started": "2019-06-19T06:09:47.766800",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.761851"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:7]: \u001b[0m\n",
       "Data([[[0., 0.],\n",
       "       [1., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.771347",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0.],\n       [1., 0.]]], dtype=float32)"
       },
       "execution_count": 7,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "19cf6975-bf5d64517456ed65400aa06e",
      "outputs": [],
      "received": "2019-06-19T06:09:47.775594",
      "started": "2019-06-19T06:09:47.766688",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.762384"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:7]: \u001b[0m\n",
       "Data([[[0., 1.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.773682",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 1.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 7,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "fea95e24-6322c4aecf56747e4fab56ff",
      "outputs": [],
      "received": "2019-06-19T06:09:47.779465",
      "started": "2019-06-19T06:09:47.768161",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.763868"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:7]: \u001b[0m\n",
       "Data([[[1., 0.],\n",
       "       [0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:47.774008",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 0.],\n       [0., 0.]]], dtype=float32)"
       },
       "execution_count": 7,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "54a4dcac-6015bd942c9e607b3485a5b6",
      "outputs": [],
      "received": "2019-06-19T06:09:47.781382",
      "started": "2019-06-19T06:09:47.768244",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:47.764156"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "u.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only limitation, currently, is that a data access cannot require a direct data exchange among two or more processes (e.g., the assignment `u.data[0, 0] = u.data[3, 3]` will raise an exception unless both entries belong to the same MPI rank).\n",
    "\n",
    "We can finally write out a trivial `Operator` to try running something."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[stderr:0] Operator `Kernel` run in 0.00 s\n",
      "[stderr:1] Operator `Kernel` run in 0.00 s\n",
      "[stderr:2] Operator `Kernel` run in 0.00 s\n",
      "[stderr:3] Operator `Kernel` run in 0.00 s\n"
     ]
    }
   ],
   "source": [
    "%%px\n",
    "op = Operator(Eq(u.forward, u + 1))\n",
    "summary = op.apply(time_M=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can now check again the (distributed) content of our `u.data`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:9]: \u001b[0m\n",
       "Data([[[1., 1.],\n",
       "       [1., 2.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.513500",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1.],\n       [1., 2.]]], dtype=float32)"
       },
       "execution_count": 9,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "96e7e18b-417de328e3fb9739aeae79e0",
      "outputs": [],
      "received": "2019-06-19T06:09:48.516315",
      "started": "2019-06-19T06:09:48.508297",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.503750"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:9]: \u001b[0m\n",
       "Data([[[1., 1.],\n",
       "       [2., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.515591",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1.],\n       [2., 1.]]], dtype=float32)"
       },
       "execution_count": 9,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "1838471b-6feef8b58efe704463d0223f",
      "outputs": [],
      "received": "2019-06-19T06:09:48.520978",
      "started": "2019-06-19T06:09:48.509121",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.504078"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:9]: \u001b[0m\n",
       "Data([[[1., 2.],\n",
       "       [1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.515830",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 2.],\n       [1., 1.]]], dtype=float32)"
       },
       "execution_count": 9,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "c1c283b1-645fda318aad35f6df59810d",
      "outputs": [],
      "received": "2019-06-19T06:09:48.519653",
      "started": "2019-06-19T06:09:48.509395",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.504247"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:9]: \u001b[0m\n",
       "Data([[[2., 1.],\n",
       "       [1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.515073",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nu.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[2., 1.],\n       [1., 1.]]], dtype=float32)"
       },
       "execution_count": 9,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "32ee6f70-a70cf121a459512f8032eccc",
      "outputs": [],
      "received": "2019-06-19T06:09:48.518332",
      "started": "2019-06-19T06:09:48.509386",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.505241"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "u.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Everything as expected. We could also peek at the generated code, because we may be curious to see what sort of MPI calls Devito has generated..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#define _POSIX_C_SOURCE 200809L\n",
      "#include \"stdlib.h\"\n",
      "#include \"math.h\"\n",
      "#include \"sys/time.h\"\n",
      "#include \"xmmintrin.h\"\n",
      "#include \"pmmintrin.h\"\n",
      "#include \"mpi.h\"\n",
      "\n",
      "struct dataobj\n",
      "{\n",
      "  void *restrict data;\n",
      "  int * size;\n",
      "  int * npsize;\n",
      "  int * dsize;\n",
      "  int * hsize;\n",
      "  int * hofs;\n",
      "  int * oofs;\n",
      "} ;\n",
      "\n",
      "struct profiler\n",
      "{\n",
      "  double section0;\n",
      "} ;\n",
      "\n",
      "\n",
      "int Kernel(struct dataobj *restrict u_vec, const int time_M, const int time_m, struct profiler * timers, const int x_M, const int x_m, const int y_M, const int y_m)\n",
      "{\n",
      "  float (*restrict u)[u_vec->size[1]][u_vec->size[2]] __attribute__ ((aligned (64))) = (float (*)[u_vec->size[1]][u_vec->size[2]]) u_vec->data;\n",
      "  /* Flush denormal numbers to zero in hardware */\n",
      "  _MM_SET_DENORMALS_ZERO_MODE(_MM_DENORMALS_ZERO_ON);\n",
      "  _MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON);\n",
      "  for (int time = time_m, t0 = (time)%(1), t1 = (time)%(1); time <= time_M; time += 1, t0 = (time)%(1), t1 = (time)%(1))\n",
      "  {\n",
      "    struct timeval start_section0, end_section0;\n",
      "    gettimeofday(&start_section0, NULL);\n",
      "    /* Begin section0 */\n",
      "    for (int x = x_m; x <= x_M; x += 1)\n",
      "    {\n",
      "      #pragma omp simd aligned(u:64)\n",
      "      for (int y = y_m; y <= y_M; y += 1)\n",
      "      {\n",
      "        u[t1][x + 2][y + 2] = u[t0][x + 2][y + 2] + 1;\n",
      "      }\n",
      "    }\n",
      "    /* End section0 */\n",
      "    gettimeofday(&end_section0, NULL);\n",
      "    timers->section0 += (double)(end_section0.tv_sec-start_section0.tv_sec)+(double)(end_section0.tv_usec-start_section0.tv_usec)/1000000;\n",
      "  }\n",
      "  return 0;\n",
      "}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%px --targets 0\n",
    "print(op)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hang on. There's nothing MPI-specific here! At least apart from the header file `#include \"mpi.h\"`. What's going on? Well, it's simple. Devito was smart enough to realize that this trivial `Operator` doesn't even need any sort of halo exchange -- the `Eq` implements a pure \"map computation\" (i.e., fully parallel), so it can just let each MPI process do its job without ever synchronizing with halo exchanges. We might want try again with a proper stencil `Eq`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#define _POSIX_C_SOURCE 200809L\n",
      "#include \"stdlib.h\"\n",
      "#include \"math.h\"\n",
      "#include \"sys/time.h\"\n",
      "#include \"xmmintrin.h\"\n",
      "#include \"pmmintrin.h\"\n",
      "#include \"mpi.h\"\n",
      "\n",
      "struct dataobj\n",
      "{\n",
      "  void *restrict data;\n",
      "  int * size;\n",
      "  int * npsize;\n",
      "  int * dsize;\n",
      "  int * hsize;\n",
      "  int * hofs;\n",
      "  int * oofs;\n",
      "} ;\n",
      "\n",
      "struct neighborhood\n",
      "{\n",
      "  int ll, lc, lr;\n",
      "  int cl, cc, cr;\n",
      "  int rl, rc, rr;\n",
      "} ;\n",
      "\n",
      "struct profiler\n",
      "{\n",
      "  double section0;\n",
      "} ;\n",
      "\n",
      "void haloupdate0(struct dataobj *restrict a_vec, MPI_Comm comm, struct neighborhood * nb, int otime);\n",
      "void sendrecv0(struct dataobj *restrict a_vec, const int buf_x_size, const int buf_y_size, int ogtime, int ogx, int ogy, int ostime, int osx, int osy, int fromrank, int torank, MPI_Comm comm);\n",
      "void gather0(float *restrict buf_vec, const int buf_x_size, const int buf_y_size, struct dataobj *restrict a_vec, int otime, int ox, int oy);\n",
      "void scatter0(float *restrict buf_vec, const int buf_x_size, const int buf_y_size, struct dataobj *restrict a_vec, int otime, int ox, int oy);\n",
      "\n",
      "int Kernel(const float h_x, struct dataobj *restrict u_vec, MPI_Comm comm, struct neighborhood * nb, const int time_M, const int time_m, struct profiler * timers, const int x_M, const int x_m, const int y_M, const int y_m)\n",
      "{\n",
      "  float (*restrict u)[u_vec->size[1]][u_vec->size[2]] __attribute__ ((aligned (64))) = (float (*)[u_vec->size[1]][u_vec->size[2]]) u_vec->data;\n",
      "  /* Flush denormal numbers to zero in hardware */\n",
      "  _MM_SET_DENORMALS_ZERO_MODE(_MM_DENORMALS_ZERO_ON);\n",
      "  _MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON);\n",
      "  for (int time = time_m, t0 = (time)%(1), t1 = (time)%(1); time <= time_M; time += 1, t0 = (time)%(1), t1 = (time)%(1))\n",
      "  {\n",
      "    struct timeval start_section0, end_section0;\n",
      "    gettimeofday(&start_section0, NULL);\n",
      "    /* Begin section0 */\n",
      "    haloupdate0(u_vec,comm,nb,t0);\n",
      "    for (int x = x_m; x <= x_M; x += 1)\n",
      "    {\n",
      "      #pragma omp simd aligned(u:64)\n",
      "      for (int y = y_m; y <= y_M; y += 1)\n",
      "      {\n",
      "        float r0 = 1.0/h_x;\n",
      "        u[t1][x + 2][y + 2] = 5.0e-1F*(-r0*u[t0][x + 1][y + 2] + r0*u[t0][x + 3][y + 2]) + 1;\n",
      "      }\n",
      "    }\n",
      "    /* End section0 */\n",
      "    gettimeofday(&end_section0, NULL);\n",
      "    timers->section0 += (double)(end_section0.tv_sec-start_section0.tv_sec)+(double)(end_section0.tv_usec-start_section0.tv_usec)/1000000;\n",
      "  }\n",
      "  return 0;\n",
      "}\n",
      "\n",
      "void haloupdate0(struct dataobj *restrict a_vec, MPI_Comm comm, struct neighborhood * nb, int otime)\n",
      "{\n",
      "  sendrecv0(a_vec,a_vec->hsize[3],a_vec->npsize[2],otime,a_vec->oofs[2],a_vec->hofs[4],otime,a_vec->hofs[3],a_vec->hofs[4],nb->rc,nb->lc,comm);\n",
      "  sendrecv0(a_vec,a_vec->hsize[2],a_vec->npsize[2],otime,a_vec->oofs[3],a_vec->hofs[4],otime,a_vec->hofs[2],a_vec->hofs[4],nb->lc,nb->rc,comm);\n",
      "}\n",
      "\n",
      "void sendrecv0(struct dataobj *restrict a_vec, const int buf_x_size, const int buf_y_size, int ogtime, int ogx, int ogy, int ostime, int osx, int osy, int fromrank, int torank, MPI_Comm comm)\n",
      "{\n",
      "  float (*bufs)[buf_y_size];\n",
      "  float (*bufg)[buf_y_size];\n",
      "  posix_memalign((void**)&bufs, 64, sizeof(float[buf_x_size][buf_y_size]));\n",
      "  posix_memalign((void**)&bufg, 64, sizeof(float[buf_x_size][buf_y_size]));\n",
      "  MPI_Request rrecv;\n",
      "  MPI_Request rsend;\n",
      "  MPI_Irecv((float *)bufs,buf_x_size*buf_y_size,MPI_FLOAT,fromrank,13,comm,&rrecv);\n",
      "  if (torank != MPI_PROC_NULL)\n",
      "  {\n",
      "    gather0((float *)bufg,buf_x_size,buf_y_size,a_vec,ogtime,ogx,ogy);\n",
      "  }\n",
      "  MPI_Isend((float *)bufg,buf_x_size*buf_y_size,MPI_FLOAT,torank,13,comm,&rsend);\n",
      "  MPI_Wait(&rsend,MPI_STATUS_IGNORE);\n",
      "  MPI_Wait(&rrecv,MPI_STATUS_IGNORE);\n",
      "  if (fromrank != MPI_PROC_NULL)\n",
      "  {\n",
      "    scatter0((float *)bufs,buf_x_size,buf_y_size,a_vec,ostime,osx,osy);\n",
      "  }\n",
      "  free(bufs);\n",
      "  free(bufg);\n",
      "}\n",
      "\n",
      "void gather0(float *restrict buf_vec, const int buf_x_size, const int buf_y_size, struct dataobj *restrict a_vec, int otime, int ox, int oy)\n",
      "{\n",
      "  float (*restrict buf)[buf_y_size] __attribute__ ((aligned (64))) = (float (*)[buf_y_size]) buf_vec;\n",
      "  float (*restrict a)[a_vec->size[1]][a_vec->size[2]] __attribute__ ((aligned (64))) = (float (*)[a_vec->size[1]][a_vec->size[2]]) a_vec->data;\n",
      "  for (int x = 0; x <= buf_x_size - 1; x += 1)\n",
      "  {\n",
      "    for (int y = 0; y <= buf_y_size - 1; y += 1)\n",
      "    {\n",
      "      buf[x][y] = a[otime][x + ox][y + oy];\n",
      "    }\n",
      "  }\n",
      "}\n",
      "\n",
      "void scatter0(float *restrict buf_vec, const int buf_x_size, const int buf_y_size, struct dataobj *restrict a_vec, int otime, int ox, int oy)\n",
      "{\n",
      "  float (*restrict buf)[buf_y_size] __attribute__ ((aligned (64))) = (float (*)[buf_y_size]) buf_vec;\n",
      "  float (*restrict a)[a_vec->size[1]][a_vec->size[2]] __attribute__ ((aligned (64))) = (float (*)[a_vec->size[1]][a_vec->size[2]]) a_vec->data;\n",
      "  for (int x = 0; x <= buf_x_size - 1; x += 1)\n",
      "  {\n",
      "    for (int y = 0; y <= buf_y_size - 1; y += 1)\n",
      "    {\n",
      "      a[otime][x + ox][y + oy] = buf[x][y];\n",
      "    }\n",
      "  }\n",
      "}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%px --targets 0\n",
    "op = Operator(Eq(u.forward, u.dx + 1))\n",
    "print(op)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uh-oh -- now the generated code looks more complicated than before, though it still is pretty much human-readable. We can spot the following routines:\n",
    "\n",
    "* `haloupdate0` performs a blocking halo exchange, relying on three additional functions, `gather0`, `sendrecv0`, and `scatter0`;\n",
    "* `gather0` copies the (generally non-contiguous) boundary data into a contiguous buffer;\n",
    "* `sendrecv0` takes the buffered data and sends it to one or more neighboring processes; then it waits until all data from the neighboring processes is received;\n",
    "* `scatter0` copies the received data into the proper array locations.\n",
    "\n",
    "This is the simplest halo exchange scheme available in Devito. There are a few, and some of them apply aggressive optimizations, [as shown later on](#Performance-optimizations)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before looking at other scenarios and performance optimizations, there is one last thing it is worth discussing -- the `data_with_halo` view."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:12]: \u001b[0m\n",
       "Data([[[0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0.],\n",
       "       [0., 0., 1., 1.],\n",
       "       [0., 0., 1., 2.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.806219",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0., 0., 0.],\n       [0., 0., 0., 0.],\n       [0., 0., 1., 1.],\n       [0., 0., 1., 2.]]], dtype=float32)"
       },
       "execution_count": 12,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "7632bf46-74ac91664c9d983a63417f16",
      "outputs": [],
      "received": "2019-06-19T06:09:48.811047",
      "started": "2019-06-19T06:09:48.798263",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.794615"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:10]: \u001b[0m\n",
       "Data([[[0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0.],\n",
       "       [1., 1., 0., 0.],\n",
       "       [2., 1., 0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.807590",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0., 0., 0.],\n       [0., 0., 0., 0.],\n       [1., 1., 0., 0.],\n       [2., 1., 0., 0.]]], dtype=float32)"
       },
       "execution_count": 10,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "dd73c4f8-9037b569a0cfc423e8966f03",
      "outputs": [],
      "received": "2019-06-19T06:09:48.813221",
      "started": "2019-06-19T06:09:48.799818",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.795512"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:10]: \u001b[0m\n",
       "Data([[[0., 0., 1., 2.],\n",
       "       [0., 0., 1., 1.],\n",
       "       [0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.808214",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[0., 0., 1., 2.],\n       [0., 0., 1., 1.],\n       [0., 0., 0., 0.],\n       [0., 0., 0., 0.]]], dtype=float32)"
       },
       "execution_count": 10,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "b91ac447-b137912d731bc2d17cb179cf",
      "outputs": [],
      "received": "2019-06-19T06:09:48.815411",
      "started": "2019-06-19T06:09:48.800548",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.795829"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:10]: \u001b[0m\n",
       "Data([[[2., 1., 0., 0.],\n",
       "       [1., 1., 0., 0.],\n",
       "       [0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.807982",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[2., 1., 0., 0.],\n       [1., 1., 0., 0.],\n       [0., 0., 0., 0.],\n       [0., 0., 0., 0.]]], dtype=float32)"
       },
       "execution_count": 10,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "52b8ef48-6cc40655695d8312d5b1b548",
      "outputs": [],
      "received": "2019-06-19T06:09:48.817554",
      "started": "2019-06-19T06:09:48.800718",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.796209"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "u.data_with_halo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is again a global data view. The shown *with_halo* is the \"true\" halo surrounding the physical domain, **not** the halo used for the MPI halo exchanges (often referred to as \"ghost region\"). So it gets trivial for a user to initialize the \"true\" halo region (which is typically read by a stencil `Eq` when an `Operator` iterates in proximity of the domain bounday)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "u.data_with_halo[:] = 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:14]: \u001b[0m\n",
       "Data([[[1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.885500",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.]]], dtype=float32)"
       },
       "execution_count": 14,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "90c8e48b-942dff09215ec7dd506092f1",
      "outputs": [],
      "received": "2019-06-19T06:09:48.894076",
      "started": "2019-06-19T06:09:48.875533",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.871842"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:12]: \u001b[0m\n",
       "Data([[[1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.885576",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.]]], dtype=float32)"
       },
       "execution_count": 12,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "5e6cbe3a-f1f42c453bb973a657a9775f",
      "outputs": [],
      "received": "2019-06-19T06:09:48.892065",
      "started": "2019-06-19T06:09:48.877493",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.872789"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:12]: \u001b[0m\n",
       "Data([[[1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.885450",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.]]], dtype=float32)"
       },
       "execution_count": 12,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "71ad0c12-d60bdb87427835fbe694bb6b",
      "outputs": [],
      "received": "2019-06-19T06:09:48.890091",
      "started": "2019-06-19T06:09:48.878010",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.873275"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:12]: \u001b[0m\n",
       "Data([[[1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.],\n",
       "       [1., 1., 1., 1.]]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:48.886196",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nu.data_with_halo\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[[1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.],\n       [1., 1., 1., 1.]]], dtype=float32)"
       },
       "execution_count": 12,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "1122a8c3-5d47420c0ecc68eeeafe31da",
      "outputs": [],
      "received": "2019-06-19T06:09:48.896042",
      "started": "2019-06-19T06:09:48.878409",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:48.873804"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "u.data_with_halo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MPI and SparseFunction\n",
    "\n",
    "A `SparseFunction` represents a sparse set of points which are generically unaligned with the `Grid`. A sparse point could be anywhere within a grid, and is therefore attached some coordinates. Given a sparse point, Devito looks at its coordinates and, based on the domain decomposition, **logically** assigns it to a given MPI process; this is purely logical ownership, as in Python-land, before running an Operator, the sparse point physically lives on the MPI rank which created it. Within `op.apply`, right before jumping to C-land, the sparse points are scattered to their logical owners; upon returning to Python-land, the sparse points are gathered back to their original location.\n",
    "\n",
    "In the following example, we attempt injection of four sparse points into the neighboring grid points via linear interpolation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "from devito import Function, SparseFunction\n",
    "grid = Grid(shape=(4, 4), extent=(3.0, 3.0))\n",
    "x, y = grid.dimensions\n",
    "f = Function(name='f', grid=grid)\n",
    "coords = [(0.5, 0.5), (1.5, 2.5), (1.5, 1.5), (2.5, 1.5)]\n",
    "sf = SparseFunction(name='sf', grid=grid, npoint=len(coords), coordinates=coords)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let:\n",
    "* O be a grid point\n",
    "* x be a halo point\n",
    "* A, B, C, D be the sparse points\n",
    "\n",
    "We show the global view, that is what the user \"sees\".\n",
    "\n",
    "```\n",
    "O --- O --- O --- O\n",
    "|  A  |     |     |\n",
    "O --- O --- O --- O\n",
    "|     |  C  |  B  |\n",
    "O --- O --- O --- O\n",
    "|     |  D  |     |\n",
    "O --- O --- O --- O\n",
    "```\n",
    "\n",
    "And now the local view, that is what the MPI ranks own when jumping to C-land.        \n",
    "\n",
    "```\n",
    "Rank 0          Rank 1\n",
    "O --- O --- x   x --- O --- O\n",
    "|  A  |     |   |     |     |\n",
    "O --- O --- x   x --- O --- O\n",
    "|     |  C  |   |  C  |  B  |\n",
    "x --- x --- x   x --- x --- x\n",
    "\n",
    "Rank 2           Rank 3\n",
    "x --- x --- x   x --- x --- x\n",
    "|     |  C  |   |  C  |  B  |\n",
    "O --- O --- x   x --- O --- O\n",
    "|     |  D  |   |  D  |     |\n",
    "O --- O --- x   x --- O --- O\n",
    "```\n",
    "\n",
    "We observe that the sparse points along the boundary of two or more MPI ranks are _duplicated_ and thus redundantly computed over multiple processes. However, the contributions from these points to the neighboring halo points are naturally ditched, so the final result of the interpolation is as expected. Let's convince ourselves that this is the case. We assign a value of $5$ to each sparse point. Since we are using linear interpolation and all points are placed at the exact center of a grid quadrant, we expect that the contribution of each sparse point to a neighboring grid point will be $5 * 0.25 = 1.25$. Based on the global view above, we eventually expect `f` to look like as follows:\n",
    "\n",
    "```\n",
    "1.25 --- 1.25 --- 0.00 --- 0.00\n",
    "|         |        |        |\n",
    "1.25 --- 2.50 --- 2.50 --- 1.25\n",
    "|         |        |        |\n",
    "0.00 --- 2.50 --- 3.75 --- 1.25\n",
    "|         |        |        |\n",
    "0.00 --- 1.25 --- 1.25 --- 0.00\n",
    "```\n",
    "\n",
    "Let's check this out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[stderr:0] Operator `Kernel` run in 0.00 s\n",
      "[stderr:1] Operator `Kernel` run in 0.00 s\n",
      "[stderr:2] Operator `Kernel` run in 0.00 s\n",
      "[stderr:3] Operator `Kernel` run in 0.00 s\n"
     ]
    }
   ],
   "source": [
    "%%px\n",
    "sf.data[:] = 5.\n",
    "op = Operator(sf.inject(field=f, expr=sf))\n",
    "summary = op.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[output:0]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[0:17]: \u001b[0m\n",
       "Data([[1.25, 1.25],\n",
       "      [1.25, 2.5 ]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:50.060788",
      "data": {},
      "engine_id": 0,
      "engine_uuid": "5830fa05-027fcdd1634c963e8e943989",
      "error": null,
      "execute_input": "\nf.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[1.25, 1.25],\n      [1.25, 2.5 ]], dtype=float32)"
       },
       "execution_count": 17,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "d3248729-28b3554ff4fbd3179ec8efde",
      "outputs": [],
      "received": "2019-06-19T06:09:50.064178",
      "started": "2019-06-19T06:09:50.056735",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:50.052406"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[1:15]: \u001b[0m\n",
       "Data([[0.  , 0.  ],\n",
       "      [2.5 , 1.25]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:50.063624",
      "data": {},
      "engine_id": 1,
      "engine_uuid": "51b618d8-7a67fb0a68df9ed26d3165f4",
      "error": null,
      "execute_input": "\nf.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[0.  , 0.  ],\n      [2.5 , 1.25]], dtype=float32)"
       },
       "execution_count": 15,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "5da49279-20d252d3068de25c0dc99a38",
      "outputs": [],
      "received": "2019-06-19T06:09:50.068441",
      "started": "2019-06-19T06:09:50.057983",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:50.053103"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:2]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[2:15]: \u001b[0m\n",
       "Data([[0.  , 2.5 ],\n",
       "      [0.  , 1.25]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:50.062489",
      "data": {},
      "engine_id": 2,
      "engine_uuid": "5895d162-e3a580384e4f0cd3931f6f1a",
      "error": null,
      "execute_input": "\nf.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[0.  , 2.5 ],\n      [0.  , 1.25]], dtype=float32)"
       },
       "execution_count": 15,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "bdb4c715-ac16cc48a99308e67b56b5d8",
      "outputs": [],
      "received": "2019-06-19T06:09:50.066038",
      "started": "2019-06-19T06:09:50.057486",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:50.053502"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[output:3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mOut[3:15]: \u001b[0m\n",
       "Data([[3.75, 1.25],\n",
       "      [1.25, 0.  ]], dtype=float32)"
      ]
     },
     "metadata": {
      "after": [],
      "completed": "2019-06-19T06:09:50.062194",
      "data": {},
      "engine_id": 3,
      "engine_uuid": "9baeeb8e-fd0982b076000ccebeb6f851",
      "error": null,
      "execute_input": "\nf.data\n",
      "execute_result": {
       "data": {
        "text/plain": "Data([[3.75, 1.25],\n      [1.25, 0.  ]], dtype=float32)"
       },
       "execution_count": 15,
       "metadata": {}
      },
      "follow": [],
      "msg_id": "f40efe56-8987aaa6fba855f93766c552",
      "outputs": [],
      "received": "2019-06-19T06:09:50.067261",
      "started": "2019-06-19T06:09:50.057555",
      "status": "ok",
      "stderr": "",
      "stdout": "",
      "submitted": "2019-06-19T06:09:50.053915"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%px --group-outputs=engine\n",
    "f.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Performance optimizations\n",
    "\n",
    "The Devito compiler applies several optimizations before generating code.\n",
    "\n",
    "* Redundant halo exchanges are identified and removed. A halo exchange is redundant if a prior halo exchange carries out the same `Function` update and the data is not “dirty” yet.\n",
    "* Computation/communication overlap, with explicit prodding of the asynchronous progress engine to make sure that non-blocking communications execute in background during the compute part.\n",
    "* Halo exchanges could also be reshuffled to maximize the extension of the computation/communication overlap region.\n",
    "\n",
    "To run with all these optimizations enabled, instead of `DEVITO_MPI=1`, users should set `DEVITO_MPI=full`, or, equivalently"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%px\n",
    "configuration['mpi'] = 'full'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could now peek at the generated code to see that things now look differently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%%px\n",
    "op = Operator(Eq(u.forward, u.dx + 1))\n",
    "# Uncomment below to show code (it's quite verbose)\n",
    "# print(op)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The body of the time-stepping loop has changed, as it now implements a classic computation/communication overlap scheme:\n",
    "\n",
    "* `haloupdate0` triggers non-blocking communications;\n",
    "* `compute0` executes the core domain region, that is the sub-region which doesn't require reading from halo data to be computed;\n",
    "* `halowait0` wait and terminates the non-blocking communications;\n",
    "* `remainder0`, which internally calls `compute0`, computes the boundary region requiring the now up-to-date halo data."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}