{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-1 fw=all -->\n",
    "\n",
    "# The Performance Model\n",
    "\n",
    "Run one matrix multiplication at two sizes on the same GPU and time it\n",
    "honestly, and you will find that the hardware delivers wildly different\n",
    "fractions of its advertised speed: a small multiplication achieves a\n",
    "percent or less of the chip's peak, a large one comes close to the\n",
    "specification sheet. Same silicon, same operation, same library — a\n",
    "difference of roughly two orders of magnitude in *achieved* arithmetic\n",
    "throughput. This section\n",
    "exists to explain that plot, and to turn the explanation into a working\n",
    "method.\n",
    "\n",
    "The method has four steps, and the rest of this chapter is the method,\n",
    "applied: **measure** what your program actually does; **classify** which of\n",
    "three resources binds it — arithmetic, memory bandwidth, or per-operation\n",
    "overhead; **fix** the binding constraint with the matching technique; then\n",
    "**re-measure**, because the fix moves the bottleneck somewhere else. Every\n",
    "later section of this chapter slots into this loop.\n",
    "that section explains where the machine's two headline numbers\n",
    "come from; that section targets the bandwidth and overhead\n",
    "regimes; that section buys back memory and trades\n",
    "precision for speed; that section and\n",
    "that section add devices;\n",
    "that section runs the whole loop on a real Transformer.\n",
    "\n",
    "Two ideas carry the section. The first is *arithmetic intensity*: how many\n",
    "floating-point operations a computation performs per byte it moves to and\n",
    "from memory. Intensity, compared against a single machine-dependent\n",
    "threshold, predicts which regime an operation lands in — before you run\n",
    "anything. The second is that *timing a GPU is easy to get wrong*: the\n",
    "frameworks dispatch work asynchronously, so a naive timer measures how fast\n",
    "Python can enqueue work, not how fast the GPU can do it. We build the\n",
    "measurement discipline first, package it into a small tool used throughout\n",
    "the chapter, and then use it to map our own GPU.\n",
    "\n",
    "*Prerequisites: tensors and GPU placement from* that section*; the\n",
    "training loop of* that section*. No new modeling ideas\n",
    "appear here — this section is about the machine.*"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-the-performance-model"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import jax as d2l\n",
    "import jax\n",
    "from jax import numpy as jnp\n",
    "import numpy as np\n",
    "import time"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-2 fw=all -->\n",
    "\n",
    "## Counting: FLOPs, Bytes, and Arithmetic Intensity\n",
    "\n",
    "Every tensor operation makes two demands on the hardware: it asks for\n",
    "*arithmetic* — some number of floating-point operations (FLOPs) — and it\n",
    "asks for *bytes* — its inputs must be fetched from memory and its outputs\n",
    "written back. A GPU has a separate budget for each. Our build machine's RTX\n",
    "4090 can execute about $165 \\times 10^{12}$ FLOP/s on bf16 tensor cores,\n",
    "and can move about $1.0 \\times 10^{12}$ bytes/s between its compute units\n",
    "and its memory. Which budget runs out first depends on the *ratio* the\n",
    "operation asks for:\n",
    "\n",
    "$$\n",
    "\\textrm{arithmetic intensity} \\;=\\;\n",
    "\\frac{\\textrm{FLOPs performed}}{\\textrm{bytes moved}}.\n",
    "$$\n",
    "\n",
    "Consider the workhorse: a matrix multiplication\n",
    "$\\mathbf{X}\\mathbf{W}$ with $\\mathbf{X} \\in \\mathbb{R}^{B \\times D}$ and\n",
    "$\\mathbf{W} \\in \\mathbb{R}^{D \\times F}$. It performs $2BDF$ FLOPs (one\n",
    "multiply and one add per term), while touching $BD + DF + BF$ numbers. With\n",
    "$b$ bytes per element, the intensity is\n",
    "\n",
    "$$\n",
    "\\frac{2BDF}{b\\,(BD + DF + BF)}\n",
    "\\;=\\; \\frac{2}{b}\\left(\\frac{1}{F} + \\frac{1}{B} + \\frac{1}{D}\\right)^{-1}\n",
    "\\;\\approx\\; \\frac{2B}{b} \\quad \\textrm{for } B \\ll D, F.\n",
    "$$\n",
    "\n",
    "The approximation is worth memorizing: for a skinny batch pushed through a\n",
    "wide layer, **intensity grows linearly with the batch size**, because each\n",
    "weight fetched from memory is reused across every row of the batch. A\n",
    "batch of one reuses nothing — each weight is fetched, used once, and\n",
    "discarded. This single observation will explain phenomena from \"why big\n",
    "batches are fast\" to why generating from a language model one token at a\n",
    "time is memory-bound (that section).\n",
    "\n",
    "An elementwise operation sits at the other extreme: $y_i = x_i + 1$\n",
    "performs one FLOP per element while moving $2b$ bytes (read $x_i$, write\n",
    "$y_i$), an intensity of $1/(2b)$ — a fraction of a FLOP per byte, no matter\n",
    "how large the tensor.\n",
    "\n",
    "The *roofline model* [@Williams.Waterman.Patterson.2009] turns\n",
    "intensity into a performance prediction with one line of arithmetic. An\n",
    "operation with intensity $I$ running on a machine with peak compute $P$\n",
    "(FLOP/s) and memory bandwidth $\\beta$ (bytes/s) can attain at most\n",
    "\n",
    "$$\n",
    "\\textrm{performance} \\;\\leq\\; \\min(P,\\; I \\cdot \\beta).\n",
    "$$\n",
    "\n",
    "Plotted on log–log axes (the figure), the bound is a sloped\n",
    "\"bandwidth wall\" that rises with intensity until it hits the flat \"compute\n",
    "roof\". The corner where they meet is the **ridge point** $I^* = P/\\beta$:\n",
    "operations with intensity below $I^*$ are *bandwidth-bound* — the memory\n",
    "system cannot feed the arithmetic units fast enough, and extra arithmetic\n",
    "hides under the memory time; operations above it are *compute-bound* — the\n",
    "arithmetic units are saturated, and moving fewer bytes would not help.\n",
    "\n",
    "![The roofline model, drawn with our build GPU's numbers. Attainable\n",
    "throughput is the minimum of the bandwidth wall (slope = memory bandwidth)\n",
    "and the compute roof. An elementwise operation lives far down the slope; a\n",
    "large matrix multiplication reaches the roof. The ridge point — about 165\n",
    "FLOP/byte here — separates the two regimes.](../img/mdl-perf-roofline.svg)\n",
    "\n",
    "Let's compute the ridge point for the card this book is built on. Peak\n",
    "tensor-core throughput is not exposed programmatically, so we take it from\n",
    "the specification sheet; the device query tells us what we are running on."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-counting-flops-bytes-and-arithmetic-intensity"
   },
   "source": [
    "device = jax.devices()[0]\n",
    "peak_tflops = 165.0   # RTX 4090 dense bf16 tensor-core spec\n",
    "bandwidth_tbs = 1.008  # GDDR6X spec\n",
    "print(f'{device.device_kind}')\n",
    "print(f'ridge point = {peak_tflops / bandwidth_tbs:.0f} FLOP/byte')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "NVIDIA GeForce RTX 4090\nridge point = 164 FLOP/byte\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-3 fw=all -->\n",
    "\n",
    "A ridge point of about 165 FLOP/byte means the machine wants about *165\n",
    "arithmetic operations for every byte it fetches*, just to break even —\n",
    "and our consumer card is on the low side; across modern accelerators the\n",
    "ridge sits anywhere from a hundred to several hundred FLOP/byte. Very little of\n",
    "what a neural network does naturally reaches that ratio — which is why\n",
    "the rest of this chapter is mostly about bytes, not FLOPs. For the square\n",
    "matmul above ($B = D = F = n$, bf16), intensity is $n/3$: *in principle*,\n",
    "sizes beyond $n \\approx 500$ stop being bandwidth-limited. The measured\n",
    "sweep below will show that this number is only half the story.\n",
    "that section explains where $P$ and $\\beta$ come from\n",
    "physically, and why their ratio has climbed, over the long run, from one\n",
    "hardware generation to the next.\n",
    "\n",
    "## Measuring Without Lying\n",
    "\n",
    "Before we can map our GPU against the roofline, we must be able to time it —\n",
    "and the obvious way is wrong. Deep learning frameworks dispatch GPU work\n",
    "*asynchronously*: when Python executes a tensor operation, the framework\n",
    "enqueues a kernel on the device and returns immediately, long before the\n",
    "arithmetic happens. Python then races ahead and enqueues more work while\n",
    "the GPU chews through the queue (the figure). This design\n",
    "is what lets a slow interpreter drive a fast accelerator — the CPU's job is\n",
    "to stay *ahead* of the GPU, and any point where Python must stop and wait\n",
    "for a value is a stall.\n",
    "\n",
    "![Asynchronous dispatch. Python enqueues kernels and moves on; the GPU\n",
    "executes behind it. A naive timer stops when the last kernel has been\n",
    "*enqueued*; only a synchronization point waits until the work is\n",
    "*done*.](../img/mdl-perf-async-timeline.svg)\n",
    "\n",
    "The consequence for measurement: a wall-clock timer wrapped around a GPU\n",
    "operation measures the *enqueue*, not the *execution*. Watch it lie:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-measuring-without-lying-1"
   },
   "source": [
    "key = jax.random.PRNGKey(0)\n",
    "a = jax.random.normal(key, (4096, 4096), dtype=jnp.bfloat16)\n",
    "jnp.dot(a, a).block_until_ready()  # Warmup: triggers compilation\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "for _ in range(10):\n",
    "    b = jnp.dot(a, a)\n",
    "naive = time.perf_counter() - t0\n",
    "\n",
    "b.block_until_ready()  # Drain the naive loop's in-flight work first\n",
    "t0 = time.perf_counter()\n",
    "for _ in range(10):\n",
    "    b = jnp.dot(a, a)\n",
    "b.block_until_ready()\n",
    "honest = time.perf_counter() - t0\n",
    "print(f'naive timer: {1000 * naive:.2f} ms   '\n",
    "      f'with block_until_ready: {1000 * honest:.2f} ms')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "naive timer: 0.74 ms   with block_until_ready: 8.84 ms\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-4 fw=all -->\n",
    "\n",
    "The naive timer reports close to nothing — it clocked ten kernel *launches*.\n",
    "The real number requires a barrier: in PyTorch,\n",
    "`torch.cuda.synchronize()` blocks Python until the device queue drains; in\n",
    "JAX, `block_until_ready()` blocks on one specific result (the tighter of\n",
    "the two — other work may proceed). Note the barrier *before* the second\n",
    "timer starts as well: without it, the naive loop's ten still-in-flight\n",
    "matmuls would be billed to the synchronized loop. A measurement must both\n",
    "start and stop at a known-quiet device. PyTorch also offers\n",
    "`torch.cuda.Event` timestamps recorded *on the device itself*, which avoid\n",
    "stopping the pipeline at all; for whole-operation timing,\n",
    "synchronize-and-wall-clock gives the same answer and is what we use.\n",
    "\n",
    "Synchronization also sneaks in where you did not ask for it. Any operation\n",
    "that needs a tensor's *value* on the host must wait for the device to\n",
    "produce it:\n",
    "\n",
    "* `float(x)` and `x.item()` — converting to a Python scalar;\n",
    "* `x.cpu()`, `x.numpy()`, `np.asarray(x)` — leaving device memory;\n",
    "* `print(x)` — printing needs the values;\n",
    "* boolean control flow like `if (loss < 0.1)` — deciding needs the value;\n",
    "* in PyTorch, shape-producing ops like `x.nonzero()` — the *size* of the\n",
    "  result depends on the data, so Python must wait to learn it.\n",
    "\n",
    "Each of these is a barrier exactly like `synchronize()`, but implicit. The\n",
    "classic self-inflicted wound is reading the loss on every step of a\n",
    "training loop: the read itself is cheap, but it parks Python at the barrier\n",
    "once per step, so the GPU queue drains and the enqueue-ahead pipeline of\n",
    "the figure never fills. Let's measure the damage on a\n",
    "long chain of small operations, where staying ahead matters most:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-measuring-without-lying-2"
   },
   "source": [
    "x = jnp.ones((256, 256))\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "s = 0.0\n",
    "for _ in range(1000):\n",
    "    y = (x * 1.01).sum()\n",
    "    s += float(y)          # Reads the value: a barrier on every step\n",
    "sync_every = time.perf_counter() - t0\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "s = jnp.zeros(())\n",
    "for _ in range(1000):\n",
    "    y = (x * 1.01).sum()\n",
    "    s = s + y              # Accumulate on the device: no barrier\n",
    "s = float(s)               # One read at the very end\n",
    "sync_once = time.perf_counter() - t0\n",
    "print(f'read every step: {sync_every:.3f} s   '\n",
    "      f'read once: {sync_once:.3f} s')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "read every step: 0.983 s   read once: 0.361 s\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-5 fw=all -->\n",
    "\n",
    "Both loops launch the same kernels and compute the same total; they differ\n",
    "only in *where the host reads*. Keeping the accumulator on the device and\n",
    "reading once at the end cuts the wall clock by roughly a third in PyTorch\n",
    "and by more — around two-thirds — in JAX, where every un-jitted operation\n",
    "already pays a hefty dispatch cost (a preview of that section)\n",
    "and the per-step read stalls that pipeline on top. The exact margin is\n",
    "framework- and workload-dependent; the rule is not: **synchronize once per\n",
    "minibatch at most, and only when the host actually needs the value** —\n",
    "accumulate metrics on the device and read them at logging boundaries. (The\n",
    "`d2l` training loops used throughout this book go a step further: they\n",
    "hand each logged value to the plotting board, which performs the\n",
    "device-to-host conversion on a background thread, off the training loop.)\n",
    "\n",
    "Since every timing in this chapter needs the same three-step discipline —\n",
    "warm up, synchronize, then time — we package it once. Warmup matters\n",
    "because first calls are unrepresentative: cuBLAS selects kernels, JAX\n",
    "compiles, caches fill. The class times a zero-argument callable and blocks\n",
    "on the device before starting and stopping the clock:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-measuring-without-lying-3"
   },
   "source": [
    "class Benchmark:\n",
    "    \"\"\"Time a callable: warmup, then device-synchronized average seconds.\"\"\"\n",
    "    def __init__(self, f, warmup=3, repeats=10, desc='time'):\n",
    "        self.desc = desc\n",
    "        for _ in range(warmup):\n",
    "            out = f()\n",
    "        jax.block_until_ready(out)\n",
    "        t0 = time.perf_counter()\n",
    "        for _ in range(repeats):\n",
    "            out = f()\n",
    "        jax.block_until_ready(out)\n",
    "        self.time = (time.perf_counter() - t0) / repeats\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f'{self.desc}: {1000 * self.time:.2f} ms/call'"
   ],
   "execution_count": 5,
   "outputs": []
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-measuring-without-lying-4"
   },
   "source": [
    "Benchmark(lambda: jnp.dot(a, a), desc='4096-matmul')"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "4096-matmul: 0.85 ms/call"
     },
     "metadata": {},
     "execution_count": 6
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-6 fw=all -->\n",
    "\n",
    "Note the JAX version blocks on the callable's *return value*, so the\n",
    "callable must return what it computes — pure functions returning their\n",
    "results is JAX's house style anyway, and that section will\n",
    "make that convention load-bearing.\n",
    "\n",
    "## The Sweep: Mapping Our GPU\n",
    "\n",
    "Armed with a synchronized timer, we can produce the plot this section\n",
    "opened with: achieved TFLOP/s as a function of matrix size, against the\n",
    "roofline's bound. A square bf16 matmul at size $n$ performs $2n^3$ FLOPs;\n",
    "its intensity $n/3$ crosses our card's ridge point near $n \\approx 500$,\n",
    "so the *ceiling* of the equation rises for small $n$ and flattens\n",
    "for large $n$. Where the measured curve sits below that ceiling is the\n",
    "interesting part."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-the-sweep-mapping-our-gpu"
   },
   "source": [
    "sizes = [256, 512, 1024, 2048, 4096, 8192]\n",
    "achieved = []\n",
    "for n in sizes:\n",
    "    a = jax.random.normal(key, (n, n), dtype=jnp.bfloat16)\n",
    "    compiled = jax.jit(jnp.dot).lower(a, a).compile()\n",
    "    flops = compiled.cost_analysis()['flops']  # Analytic count, no timing\n",
    "    t = Benchmark(lambda: compiled(a, a)).time\n",
    "    achieved.append(flops / t / 1e12)\n",
    "d2l.plot(sizes, [achieved], 'matrix size $n$', 'achieved TFLOP/s',\n",
    "         xscale='log', yscale='log')\n",
    "print([f'{n}: {tf:.1f}' for n, tf in zip(sizes, achieved)])"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['256: 0.4', '512: 4.7', '1024: 21.8', '2048: 119.9', '4096: 158.7', '8192: 173.1']\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"247.978125pt\" height=\"183.35625pt\" viewBox=\"0 0 247.978125 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-20T20:34:13.415438</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M -0 183.35625 \nL 247.978125 183.35625 \nL 247.978125 0 \nL -0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 45.478125 145.8 \nL 240.778125 145.8 \nL 240.778125 7.2 \nL 45.478125 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 124.158611 145.8 \nL 124.158611 7.2 \n\" clip-path=\"url(#pe583742ef3)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"me0a22e39ac\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#me0a22e39ac\" x=\"124.158611\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(115.358611 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <defs>\n       <path id=\"m7d860c4a2e\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"62.480541\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"77.218146\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"88.64952\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"97.989632\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"105.886585\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"112.727237\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"118.761119\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"159.667702\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"180.439188\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"195.176792\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_12\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"206.608166\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_13\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"215.948279\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_14\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"223.845232\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_15\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"230.685883\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_16\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m7d860c4a2e\" x=\"236.719766\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_2\">\n     <!-- matrix size $n$ -->\n     <g transform=\"translate(110.778125 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-78\" d=\"M 3513 3500 \nL 2247 1797 \nL 3578 0 \nL 2900 0 \nL 1881 1375 \nL 863 0 \nL 184 0 \nL 1544 1831 \nL 300 3500 \nL 978 3500 \nL 1906 2253 \nL 2834 3500 \nL 3513 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-7a\" d=\"M 353 3500 \nL 3084 3500 \nL 3084 2975 \nL 922 459 \nL 3084 459 \nL 3084 0 \nL 275 0 \nL 275 525 \nL 2438 3041 \nL 353 3041 \nL 353 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-Oblique-6e\" d=\"M 3566 2113 \nL 3156 0 \nL 2578 0 \nL 2988 2091 \nQ 3016 2238 3031 2350 \nQ 3047 2463 3047 2528 \nQ 3047 2791 2881 2937 \nQ 2716 3084 2419 3084 \nQ 1956 3084 1622 2776 \nQ 1288 2469 1184 1941 \nL 800 0 \nL 225 0 \nL 903 3500 \nL 1478 3500 \nL 1363 2950 \nQ 1603 3253 1940 3418 \nQ 2278 3584 2650 3584 \nQ 3113 3584 3367 3334 \nQ 3622 3084 3622 2631 \nQ 3622 2519 3608 2391 \nQ 3594 2263 3566 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(0 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(97.412109 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(158.691406 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(197.900391 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(239.013672 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-78\" transform=\"translate(266.796875 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(325.976562 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(357.763672 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(409.863281 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-7a\" transform=\"translate(437.646484 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(490.136719 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(551.660156 0.015625)\"/>\n      <use xlink:href=\"#DejaVuSans-Oblique-6e\" transform=\"translate(583.447266 0.015625)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_18\">\n      <path d=\"M 45.478125 118.578156 \nL 240.778125 118.578156 \n\" clip-path=\"url(#pe583742ef3)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_19\">\n      <defs>\n       <path id=\"ma64f20040e\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#ma64f20040e\" x=\"45.478125\" y=\"118.578156\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(20.878125 122.377374) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_20\">\n      <path d=\"M 45.478125 71.63151 \nL 240.778125 71.63151 \n\" clip-path=\"url(#pe583742ef3)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#ma64f20040e\" x=\"45.478125\" y=\"71.63151\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(20.878125 75.430729) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_22\">\n      <path d=\"M 45.478125 24.684865 \nL 240.778125 24.684865 \n\" clip-path=\"url(#pe583742ef3)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#ma64f20040e\" x=\"45.478125\" y=\"24.684865\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(20.878125 28.484084) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_24\">\n      <defs>\n       <path id=\"m56a469115f\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"143.125558\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_25\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"137.260104\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_26\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"132.710504\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_27\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"128.99321\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_28\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"125.850283\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_29\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"123.127755\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_30\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"120.726316\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_31\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"104.445807\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_32\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"96.178913\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_13\">\n     <g id=\"line2d_33\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"90.313459\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_14\">\n     <g id=\"line2d_34\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"85.763859\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_15\">\n     <g id=\"line2d_35\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"82.046565\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_16\">\n     <g id=\"line2d_36\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"78.903638\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_17\">\n     <g id=\"line2d_37\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"76.18111\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_18\">\n     <g id=\"line2d_38\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"73.779671\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_19\">\n     <g id=\"line2d_39\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"57.499162\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_20\">\n     <g id=\"line2d_40\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"49.232268\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_21\">\n     <g id=\"line2d_41\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"43.366814\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_22\">\n     <g id=\"line2d_42\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"38.817214\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_23\">\n     <g id=\"line2d_43\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"35.09992\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_24\">\n     <g id=\"line2d_44\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"31.956993\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_25\">\n     <g id=\"line2d_45\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"29.234465\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_26\">\n     <g id=\"line2d_46\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"26.833026\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_27\">\n     <g id=\"line2d_47\">\n      <g>\n       <use xlink:href=\"#m56a469115f\" x=\"45.478125\" y=\"10.552517\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- achieved TFLOP/s -->\n     <g transform=\"translate(14.798438 120.521094) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-54\" d=\"M -19 4666 \nL 3928 4666 \nL 3928 4134 \nL 2272 4134 \nL 2272 0 \nL 1638 0 \nL 1638 4134 \nL -19 4134 \nL -19 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-46\" d=\"M 628 4666 \nL 3309 4666 \nL 3309 4134 \nL 1259 4134 \nL 1259 2759 \nL 3109 2759 \nL 3109 2228 \nL 1259 2228 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-4c\" d=\"M 628 4666 \nL 1259 4666 \nL 1259 531 \nL 3531 531 \nL 3531 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-4f\" d=\"M 2522 4238 \nQ 1834 4238 1429 3725 \nQ 1025 3213 1025 2328 \nQ 1025 1447 1429 934 \nQ 1834 422 2522 422 \nQ 3209 422 3611 934 \nQ 4013 1447 4013 2328 \nQ 4013 3213 3611 3725 \nQ 3209 4238 2522 4238 \nz\nM 2522 4750 \nQ 3503 4750 4090 4092 \nQ 4678 3434 4678 2328 \nQ 4678 1225 4090 567 \nQ 3503 -91 2522 -91 \nQ 1538 -91 948 565 \nQ 359 1222 359 2328 \nQ 359 3434 948 4092 \nQ 1538 4750 2522 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-50\" d=\"M 1259 4147 \nL 1259 2394 \nL 2053 2394 \nQ 2494 2394 2734 2622 \nQ 2975 2850 2975 3272 \nQ 2975 3691 2734 3919 \nQ 2494 4147 2053 4147 \nL 1259 4147 \nz\nM 628 4666 \nL 2053 4666 \nQ 2838 4666 3239 4311 \nQ 3641 3956 3641 3272 \nQ 3641 2581 3239 2228 \nQ 2838 1875 2053 1875 \nL 1259 1875 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2f\" d=\"M 1625 4666 \nL 2156 4666 \nL 531 -594 \nL 0 -594 \nL 1625 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-61\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(61.279297 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(116.259766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(179.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(207.421875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(268.945312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(328.125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(389.648438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(453.125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-54\" transform=\"translate(484.912109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-46\" transform=\"translate(545.996094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-4c\" transform=\"translate(603.515625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-4f\" transform=\"translate(655.603516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-50\" transform=\"translate(734.314453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2f\" transform=\"translate(794.617188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(828.308594 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_48\">\n    <path d=\"M 54.355398 139.5 \nL 89.864489 87.029152 \nL 125.37358 55.756919 \nL 160.88267 20.980417 \nL 196.391761 15.269608 \nL 231.900852 13.5 \n\" clip-path=\"url(#pe583742ef3)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 45.478125 145.8 \nL 45.478125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 240.778125 145.8 \nL 240.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 45.478125 145.8 \nL 240.778125 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 45.478125 7.2 \nL 240.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pe583742ef3\">\n   <rect x=\"45.478125\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-7 fw=all -->\n",
    "\n",
    "The JAX tab shows off a genuinely elegant tool: instead of writing the\n",
    "$2n^3$ formula by hand, it asks the compiler. Ahead-of-time lowering\n",
    "(`jit(...).lower(...).compile()`) produces a compiled object whose\n",
    "`cost_analysis()` reports the exact analytic FLOP count of the program —\n",
    "no execution, no estimation. We will lean on this introspection again in\n",
    "that section and that section.\n",
    "\n",
    "Read the plot against the figure, remembering that the\n",
    "roofline is a *ceiling*, not a prediction of where you land. At $n = 256$\n",
    "the card delivers a percent or less of peak: the matrix is so small that\n",
    "per-kernel overhead (a few microseconds to launch work at all — see\n",
    "that section) rivals the arithmetic. More telling is $n = 512$.\n",
    "Its nominal intensity ($\\approx 171$) already sits *above* the ridge\n",
    "point, so the intensity model alone declares it compute-bound — yet the\n",
    "card delivers a tenth of peak or less. A $512^2$ output is simply too\n",
    "little work to fill 128 streaming multiprocessors, and the launch\n",
    "overhead has not yet been amortized away. Through the middle sizes\n",
    "throughput therefore climbs steeply — a single doubling of $n$ can buy\n",
    "several times the TFLOP/s — and the curve approaches the specification\n",
    "number only around $n \\approx 2048$–$4096$, where the tensor cores\n",
    "finally saturate and the operation is compute-bound in fact as well as on\n",
    "paper. The gap between the nominal crossover ($n \\approx 500$) and the\n",
    "measured knee ($n \\approx 2048$–$4096$, depending on the framework) is\n",
    "not a failure of the model; it *is*\n",
    "a lesson: intensity tells you when an operation stops being\n",
    "bandwidth-limited in principle, while utilization and overhead decide how\n",
    "much of the roof you collect — and separating those causes is exactly\n",
    "what the profiler below is for.\n",
    "\n",
    "## Three Regimes\n",
    "\n",
    "The sweep exposed all three ways a GPU program spends its time, and they\n",
    "are worth naming precisely, because the *fix depends on the diagnosis*\n",
    "[@He.2022]. A step of any workload divides its wall-clock time among\n",
    "arithmetic, memory traffic, and idle gaps where the device waits for\n",
    "Python; whichever dominates names the regime\n",
    "(the figure).\n",
    "\n",
    "![The three-regime diagnostic. Where a step's time goes determines which\n",
    "fix applies; misdiagnosing wastes effort — more FLOP/s cannot help a\n",
    "bandwidth-bound program.](../img/mdl-perf-regimes.svg)\n",
    "\n",
    "**Compute-bound** — the arithmetic units are the constraint. This is the\n",
    "regime you *want*: the silicon is earning its price. The remaining levers\n",
    "are to buy the arithmetic more cheaply — a lower-precision format doubles\n",
    "throughput per halving (that section,\n",
    "that section) — or to buy more silicon\n",
    "(that section).\n",
    "\n",
    "**Bandwidth-bound** — intensity below the ridge; the compute units starve\n",
    "while memory serves bytes. The fix is to *move fewer bytes*: fuse chains\n",
    "of operations so intermediate results never make the round trip to memory\n",
    "(that section), recompute rather than store\n",
    "(that section), or restructure the algorithm for reuse —\n",
    "the FlashAttention kernel of that section is this fix,\n",
    "executed by hand at world-class level.\n",
    "\n",
    "**Overhead-bound** — the device finishes each kernel before Python can\n",
    "supply the next one; the GPU is idle most of the time. Small models with\n",
    "many small layers live here. The fix is to get Python out of the loop:\n",
    "capture the whole graph once and replay it without the interpreter\n",
    "(that section).\n",
    "\n",
    "Here is a bandwidth-bound specimen, and a first taste of diagnosis. Take\n",
    "one large tensor and apply single elementwise kernels of wildly different\n",
    "arithmetic cost — an add, a multiply, and a transcendental:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-three-regimes-1"
   },
   "source": [
    "x = jax.random.normal(key, (4000, 4000))\n",
    "for desc, f in [('add', lambda: x + 1), ('mul', lambda: x * 1.5),\n",
    "                ('sin', lambda: jnp.sin(x)),\n",
    "                ('sigmoid', lambda: jax.nn.sigmoid(x))]:\n",
    "    print(Benchmark(f, desc=desc))"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "add: 0.29 ms/call\nmul: 0.30 ms/call\nsin: 0.17 ms/call\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "sigmoid: 0.16 ms/call\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-8 fw=all -->\n",
    "\n",
    "A sine costs far more arithmetic than an add, yet it runs no slower:\n",
    "each kernel's cost is set by the 128 MB it reads and writes, not by what\n",
    "it computes on the way through. (In the PyTorch tab the four times are\n",
    "all but identical; where they scatter, as in the JAX tab, the spread is\n",
    "per-dispatch overhead on these un-jitted calls — a preview of the third\n",
    "regime — not the arithmetic.) While bandwidth binds,\n",
    "extra arithmetic hides under the memory time — the definition of\n",
    "bandwidth-bound. Now chain a few of these operations, the way any\n",
    "activation function or normalization layer does:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-three-regimes-2"
   },
   "source": [
    "def gelu_ish(x):\n",
    "    # Several elementwise ops; without jit, one kernel per op,\n",
    "    # each a full round trip to memory\n",
    "    return 0.5 * x * (1 + jnp.tanh(0.8 * (x + 0.04 * x**3)))\n",
    "\n",
    "print(Benchmark(lambda: x + 1, desc='1 op'))\n",
    "print(Benchmark(lambda: gelu_ish(x), desc='chain'))"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1 op: 0.30 ms/call\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "chain: 1.70 ms/call\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-9 fw=all -->\n",
    "\n",
    "The chain performs a handful of cheap operations, but eager execution runs\n",
    "each as its own kernel, and each kernel pays the full memory round trip —\n",
    "so the chain costs roughly as many round trips as it has operations,\n",
    "despite computing one output from one input. The diagnosis is complete:\n",
    "bandwidth-bound, with a factor-of-several overpayment in bytes. We could\n",
    "cure it right now by hand-writing one fused kernel; instead we deliberately\n",
    "leave it bleeding. that section will cure it with one line,\n",
    "and explain what the compiler saw.\n",
    "\n",
    "## The Profiler\n",
    "\n",
    "Intensity arithmetic classifies a single operation; real training steps mix\n",
    "hundreds. The tool that classifies a *program* is the profiler, which\n",
    "records every kernel with its duration and stream — the measured version of\n",
    "the figure. First contact, on a small training step:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "performance-model-the-profiler"
   },
   "source": [
    "def loss_fn(params, X):\n",
    "    h = X\n",
    "    for W in params[:-1]:\n",
    "        h = jax.nn.relu(h @ W)\n",
    "    return (h @ params[-1]).sum()\n",
    "\n",
    "params = [jax.random.normal(k, s) * 0.03 for k, s in zip(\n",
    "    jax.random.split(key, 3), [(1024, 1024), (1024, 1024), (1024, 10)])]\n",
    "X = jax.random.normal(key, (64, 1024))\n",
    "grad_fn = jax.jit(jax.grad(loss_fn))\n",
    "jax.block_until_ready(grad_fn(params, X))  # Warmup / compile\n",
    "\n",
    "with jax.profiler.trace('/tmp/jax-trace'):\n",
    "    for _ in range(5):\n",
    "        grads = grad_fn(params, X)\n",
    "    jax.block_until_ready(grads)\n",
    "print('trace written to /tmp/jax-trace; '\n",
    "      'open it in Perfetto (ui.perfetto.dev) or TensorBoard')"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "trace written to /tmp/jax-trace; open it in Perfetto (ui.perfetto.dev) or TensorBoard\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=performance-model-md-10 fw=all -->\n",
    "\n",
    "The PyTorch table is the diagnostic in miniature. Two columns matter most:\n",
    "device (\"CUDA\") time tells you *which kernels* dominate — matmuls\n",
    "(compute), elementwise/copy kernels (bandwidth) — and the ratio of total\n",
    "CPU time to total CUDA time tells you *whether the GPU is fed*: when CPU\n",
    "time is far larger, the program is overhead-bound and the kernels\n",
    "themselves are almost irrelevant. Read that ratio coarsely, though: CPU\n",
    "and device totals overlap across threads and streams, so it is a regime\n",
    "heuristic, not a utilization figure — when a real decision hangs on it,\n",
    "look at the timeline instead. Both frameworks can also export a full\n",
    "timeline — `prof.export_chrome_trace(...)` in PyTorch; the JAX trace\n",
    "directory above opens in Perfetto or TensorBoard — where the\n",
    "the figure picture appears for your actual program, gaps\n",
    "and all. We will read one in earnest in that section.\n",
    "\n",
    "> **The method.** Measure with a synchronized timer or profiler. Classify\n",
    "> the regime: compute-bound (kernels dominated by matmuls, device busy),\n",
    "> bandwidth-bound (kernels dominated by memory traffic, device busy), or\n",
    "> overhead-bound (device idle between kernels). Fix what binds — formats\n",
    "> and parallelism for compute, fusion and recomputation for bandwidth,\n",
    "> capture-and-replay for overhead. Re-measure, because the bottleneck\n",
    "> moves. The rest of this chapter is this loop, applied.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* Arithmetic intensity — FLOPs per byte moved — caps performance\n",
    "  through the roofline bound\n",
    "  $\\min(\\textrm{peak}, \\textrm{intensity} \\times \\textrm{bandwidth})$. The\n",
    "  ridge point of a modern GPU sits at a hundred to several hundred\n",
    "  FLOP/byte (about 165 on our card), so most operations are\n",
    "  bandwidth-bound, and batch size is the main natural lever on a\n",
    "  matmul's intensity.\n",
    "* GPU dispatch is asynchronous: naive timers measure the enqueue, not the\n",
    "  work. Time with a synchronization barrier (`torch.cuda.synchronize`,\n",
    "  `block_until_ready`), warm up first, and beware implicit barriers —\n",
    "  `.item()`, `.numpy()`, `print`, value-dependent control flow — inside hot\n",
    "  loops.\n",
    "* One matmul kernel traverses three regimes as it grows: overhead-bound\n",
    "  when tiny, bandwidth-bound in the middle, compute-bound at scale — and\n",
    "  it reaches the roof well after the intensity model's nominal crossover,\n",
    "  because small shapes cannot fill the machine. The profiler's\n",
    "  CPU-versus-device-time comparison diagnoses which regime a whole\n",
    "  program is in.\n",
    "* The chapter's method: measure → classify → fix → re-measure.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Compute the ridge point of the GPU you are actually running on, from\n",
    "   its specification sheet, and compare it against your own sweep: at what\n",
    "   matrix size does the measured curve leave the bandwidth wall? How does\n",
    "   the answer change if you sweep fp32 matmuls instead of bf16?\n",
    "1. For the batched product $\\mathbf{X}\\mathbf{W}$ with\n",
    "   $\\mathbf{X} \\in \\mathbb{R}^{B \\times 4096}$ and\n",
    "   $\\mathbf{W} \\in \\mathbb{R}^{4096 \\times 4096}$ in bf16, the intensity\n",
    "   is approximately $B$ for small $B$. Predict the batch size at which the\n",
    "   operation crosses your card's ridge point, then measure achieved\n",
    "   TFLOP/s for $B \\in \\{1, 8, 64, 512, 4096\\}$ and check.\n",
    "1. Take the training loop of that section and add a\n",
    "   `print(loss)` on every iteration. Measure the slowdown per step as a\n",
    "   function of batch size. Why does the *relative* damage shrink as the\n",
    "   batch grows?\n",
    "1. Profile a training step whose `DataLoader` uses `num_workers=0` on a\n",
    "   small model, and classify the program using the CPU-versus-device-time\n",
    "   rule. Which of the three regimes is it in — and is that a GPU problem\n",
    "   at all?\n",
    "1. `x.nonzero()` forces a synchronization in PyTorch but `x + 1` does\n",
    "   not, even though both launch kernels. Explain the difference in one\n",
    "   sentence, and find one more operation with the same property."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
