| Date | Topic | Read |
| 4/16 | Prefix sums |
Hillis and Steele, Data Parallel Algorithms
Wikepedia on prefix sums
Stackoverflow on prefix sum (work efficient algorithm
List packing example
|
| 4/11 | Pointer jumping
. . . |
|
| 4/9 | Matrix multiply: Cannon's algorithm
Cannon's algorithm
Minimum spanning tree -- Prim's algorithm: https://www.youtube.com/watch?v=Q-vYViWaY3E&t=0s&list=PLJse9iV6ReqgxpnbwIkCuqB5tP3shfZjR&index=9
Minimum spanning tree -- Kruskal's algorithm: https://www.youtube.com/watch?v=EEtWZoWGjyE&list=PLJse9iV6ReqgxpnbwIkCuqB5tP3shfZjR&index=10
Minimum spanning tree -- Boruvka's algorithm: https://www.youtube.com/watch?v=czcf73b0Ga0
| |
| 4/4 | Simulating heat equation |
https://en.wikipedia.org/wiki/Heat_equation
Horak & Gruber, "Parallel Numerical Solution
of 2-D Heat Equation", in Vajtesic, et al. Parallel Numerics, 2005, ISBN 961-6303-67-8. |
| 4/2 | Quad-tree, Oct-tree, Barnes-Hut algorithm |
Quadtree
Octree
Barnes-Hut simulation
|
| 3/28 | Finding area:
Integrate a curve using Riemann approximation
Monte Carlo method (finding pi, finding area) | |
| 3/26 | Pipelining |
http://www.cs.nthu.edu.tw/~ychung/slides/para_programming/slides5.pdf
Also, Hennessey and Patterson's MIPS architecture for RISC computer: http://www.cs.ucc.ie/~jvaughan/cs4617/slides/lecture10.pdf
|
| 3/21/2018 |
Petrie nets 101 (with two examples (H + H + O --> H2O, passengers boarding bus)
Intro to Petrie Net and examples
Introduction to and comparison of formalisms (see Petri net example)
Modelling with Petrie nets |
|
| 3/19 | Communication networks (started on 2/7):
completely connected, ring, shared bus,
shuffle-exchange,
butterfly,
omega |
|
| 3/14 | Parallel example: cellular automaton |
Cellular automata:
https://en.wikipedia.org/wiki/Category:Cellular_automaton_rules
Firing Squad Synchronization problem
Majority problem
https://en.wikipedia.org/wiki/Nagel%E2%80%93Schreckenberg_model
Bidirectional traffic |
| 3/12 | Image processing | Scarpino: Section 3.3
Gaster, et al, Heterogeneous Computing with OpenCL: Chpt 4 |
| 2/26 |
http://www.drdobbs.com/parallel/a-gentle-introduction-to-opencl/231002854?queryText=scarpino>/a> | |
| 2/12 | OpenCL Listing 1-1, matrix-vector multiply | Note! Appendix A gives what and how to download OpenCL libraries (if necessary) |
| 2/7 | Butterfly network -- relation to FFT
-- as a switching network
https://en.wikipedia.org/wiki/Butterfly_network |
| |
| 1/31 | Fourier transform Notes on FFT |
See youtube lectures: |
| 1/24 | Odd-even parallel sort p < n
Shear sort |
Ppt from Missouri S & T |
| 1/22 | (reprise of bitonic sort)
definitions: Amdahl's law, speedup, efficiency, cost |
Web pdf drawn from text: ____ https://www.cs.uky.edu/~jzhang/CS621/chapter7.pdf |
| 1/17 | parallelize merge sort, bitonic sort | |
| 1/10 | odd-even transposition sort, findMax (using tree, using hypercube), matrix-vector multiply | |
| 1/8 | Shared memory, local memory, interconnection network
Simple architectures | |