{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# CUDA Transpose: Coalescing and Bank Padding\n",
        "\n",
        "Rectangular indexing and a simple bank-address model separate two optimizations: contiguous global access and padded shared-memory layout.\n",
        "\n",
        "CPU rectangular indexing and simplified shared-memory bank-address model; no GPU execution.\n",
        "\n",
        "The code uses Python 3 and the standard library. Saved output is from the checked CPU run.\n"
      ],
      "id": "cuda-transpose-coalescing-bank-0"
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "source": [
        "rows, cols, tile = 5, 7, 3\n",
        "source = [10 * r + c for r in range(rows) for c in range(cols)]\n",
        "actual = [None] * (rows * cols)\n",
        "writes = [0] * len(actual)\n",
        "\n",
        "for r0 in range(0, rows, tile):\n",
        "    for c0 in range(0, cols, tile):\n",
        "        for r in range(r0, min(r0 + tile, rows)):\n",
        "            for c in range(c0, min(c0 + tile, cols)):\n",
        "                destination = c * rows + r\n",
        "                actual[destination] = source[r * cols + c]\n",
        "                writes[destination] += 1\n",
        "\n",
        "expected = [source[r * cols + c]\n",
        "            for c in range(cols) for r in range(rows)]\n",
        "assert actual == expected\n",
        "assert writes == [1] * len(actual)\n",
        "print(f'transpose {rows}x{cols} -> {cols}x{rows}: correct')\n",
        "print('last output row:', actual[-rows:])\n",
        "\n",
        "for stride in [32, 33]:\n",
        "    banks = [(lane * stride) % 32 for lane in range(32)]\n",
        "    distinct = len(set(banks))\n",
        "    print(f'shared row stride={stride}: unique banks={distinct}')\n",
        "print('Bank-address model only; no hardware counters or timing.')\n"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "transpose 5x7 -> 7x5: correct\n",
            "last output row: [6, 16, 26, 36, 46]\n",
            "shared row stride=32: unique banks=1\n",
            "shared row stride=33: unique banks=32\n",
            "Bank-address model only; no hardware counters or timing.\n"
          ]
        }
      ],
      "id": "cuda-transpose-coalescing-bank-1"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Sources\n",
        "\n",
        "- NVIDIA efficient transpose tutorial: https://developer.nvidia.com/blog/efficient-matrix-transpose-cuda-cc/\n- Lei Mao CuTe transpose walkthrough: https://leimao.github.io/article/CuTe-Matrix-Transpose/\n"
      ],
      "id": "cuda-transpose-coalescing-bank-2"
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.12.14"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}