.. title: PAR Class 21, Thu 2020-04-09
.. slug: class21
.. date: 2020-04-06
.. tags: class
.. category: 
.. link: 
.. description: 
.. type: text
.. has_math: true

.. raw:: html

   <style> .red {color:red} </style>
   <style> .blue {color:blue} </style>

.. role:: red
.. role:: blue

.. sectnum::
.. contents:: Table of contents
..


Final project presentations
---------------------------
Remember to sign up.


Thrust
------
#. The Thrust `examples <https://github.com/thrust/thrust/tree/master/>`_ teach several non-intuitive paradigms.  As I figure them out, I'll describe a few.  My descriptions are modified and expanded versions of the comments in the programs.  This is not a list of all the useful programs, but only of some where I am adding to their comments.

   a. **arbitrary_transformation.cu** and **dot_products_with_zip.cu**. show
      the very useful zip_iterator.  Using it is a 2-step process.

      i. Combine the separate iterators into a tuple.

      #. Construct a zip iterator from the tuple.

      Note that operator() is now a template.

   #. **boundingbox.cu** finds the bounding box around a set of 2D points.

      The main idea is to do a reduce.  However, the combining operation, instead of addition, is to combine two bounding boxes to find the box around them.

      The combining op can be any associative op.

   #. **bucket_sort2d.cu** overlays a grid on a set of 2D points and finds
      the points in each grid cell (bucket).

      i. The tuple is an efficient class for a short vector of fixed length.

      #. Note how random numbers are generated.  You combine an engine that produces random output with a distribution.

         However you might need more complicated coding to make the numbers good when executing in parallel.  See **monte_carlo_disjoint_sequences.cu**.

      #. The problem is that the number of points in each cell is unpredictable.

      #. The cell containing each point is computed and that and the points are sorted to bring together the points in each cell.

      #. Then **lower_bound** and **upper_bound** are used to find each bucket in that sorted vector of points.

      #. See this `lower_bound description <http://thrust.github.io/doc/group__vectorized__binary__search.html>`_.

   #. **mode.cu** shows:

      a. Counting the number of unique keys in a vector.

	 i. Sort the vector.

	 #. Do an **inner_product**.  However, instead of the operators being **times** and **plus**, they are **not equal to the next element** and **plus**.

      #. Counting their multiplicity.

	 i. Construct vectors, sized at the number of unique keys, to hold the unique keys and counts.

	 #. Do a **reduce_by_keys** on a constant_iterator using the sorted vector as the keys.  For each range of identical keys, it sums the constant_iterator.  That is, it counts the number of identical keys.

	 #. Write a vector of unique keys and a vector of the counts.

      #. Finding the most used key (the mode).

	 i. Do **max_element** on the counts vector.

   #. **repeated_range.cu** repeats each element of an N-vector K times:
      repeated_range([0, 1, 2, 3], 2) -> [0, 0, 1, 1, 2, 2, 3, 3].  It's a lite
      version of **expand.cu**, but uses a different technique.

      a. Here, N=4 and K=2.

      #. The idea is to construct a new iterator, **repeated_range**, that, when read and
	 incremented, will return the proper output elements.

      #. The construction stores the relevant info in structure components of the variable.

      #. Treating its value like a subscript in the range [0,N*K), it divides
	 that value by K and returns that element of its input.

      See also **strided_range.cu** and **tiled_range.cu**.


    
Backends
========

#. The Thrust device can be CUDA, OpenMP, TBB, etc.

#. You can spec it in 2 ways:

   a. by adding an extra arg at the start of a function's arg list.

   b. with an envar

      https://github.com/thrust/thrust/wiki/Host-Backends

      https://github.com/thrust/thrust/wiki/Device-Backends




Quantum computing
-----------------

`My summary <../posts/quantum.html>`_.

Extra material
==============

#. Watch `A Beginner’s Guide to Quantum Computing <https://www.youtube.com/watch?v=S52rxZG-zi0>`_, 18 min, by Dr. Talia Gershon, IBM Research.

#. Wikipedia qubit - don't read.

#. Readable  https://en.wikipedia.org/wiki/Quantum_computing

#. https://qiskit.org/

#. https://github.com/Qiskit/qiskit-presentations.git