{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# PyOpenCL Parallel Patterns: Scan/Prefix Sum\n",
        "\n",
        "## Setup Code"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import pyopencl as cl\n",
        "import pyopencl.array\n",
        "import pyopencl.clrandom\n",
        "import numpy as np\n",
        "import numpy.linalg as la"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "ctx = cl.create_some_context()\n",
        "queue = cl.CommandQueue(ctx)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "n = 10**7\n",
        "x = cl.clrandom.rand(queue, n, np.float64)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Setting up the kernel: Compute the prefix sum of squares\n",
        "\n",
        "Want to compute the prefix sum of the squares of all entries in `x`.\n",
        "\n",
        "First, using `numpy`, as `result1`:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "result1 = np.cumsum(x.get()**2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Then, using PyOpenCL:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from pyopencl.scan import GenericScanKernel"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Syntax:\n",
        "    \n",
        "GSK(context, dtype, arguments, input_expr, scan_expr using `a` and `b`, neutral, output_statement with `item`)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "sknl = GenericScanKernel(ctx, np.float64,\n",
        "    arguments=\"double *y, double *x\",\n",
        "    input_expr=\"x[i]*x[i]\",\n",
        "    scan_expr=\"a+b\", neutral=\"0\",\n",
        "    output_statement=\"y[i] = item\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<pyopencl.cffi_cl.Event at 0x7f07c6d8f630>"
            ]
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "result2 = cl.array.empty_like(x)\n",
        "sknl(result2, x)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Testing the outcome"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.00019364830171\n"
          ]
        }
      ],
      "source": [
        "print(la.norm(result2.get() - result1))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "More features:\n",
        "\n",
        "* Segmented Scan\n",
        "* Output stencils\n",
        "* Works on structured types"
      ]
    }
  ],
  "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.5.0+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}