Bicycle Tour

From Education

Jump to: navigation, search

Note: This document was pulled from EAPF's shared folder on June 2, 2010, and may not accurately reflect its current state.
Note: The conversion process from Docs -> Wiki may result in some unusual formatting.

Archetypal Bike Tour

  1. Introduction
    1. Parallelism- what it is, why, myths and misconceptions, Parellelism “gotcha’s”
    2. Architecture motivation (eg. shared memory parallelism, distributed memory parallelism)
    3. Heterogeneous architectures (eg. GPU’s)
    4. Concurrency Vs Parallelism
      1. Ben will explain.
    5. Design Considerations
      1. Policies/ Best Practices/Licensing
  2. Parallelism Patterns
    1. (Define the parallel abstractions that will be used for Programming Models)
    2. Task parallelism
      1. Pull examples from motifs/dwarves
    3. Data Parallelism
    4. Pipeline Parallelism
    5. Algorithmic patterns
      1. Parallel For
      2. Parallel Reduce
      3. Master/Worker
      4. Producer/Consumer
  3. Programming Languages and Libraries
    1. Scratch, Alice, BlueJay, Greenfoot (Investigate further)
    2. Python, Ruby, Matlab, Sho
    3. C#; Java; C/C++/Fortran with OpenMP, CUDA/OpenCL/DirectCompute, or MPI
    4. Frameworks - TBB, Ct, ConcRT, TPL, GCD
    5. Win32/POSIX threads
    6. Vector programming, Fortran
    7. Graphics API and languages - OpenGL and DirectX
    8. Functional - Haskell, Erlang, #F, OCAML
    9. PGAS -- Fortress, UPC, Chapel, X10
  4. Compound Applications of Parallelism
    1. nested/hybrid
    2. Real example
  5. Parallel Algorithms
    1. Divide and conquer
    2. Work pool
    3. Map and reduce
    4. Pipeline
  6. Data Structures
    1. critical sections
    2. lock free implementations
  7. Dwarves/Motifs/Patterns

The Bike Shop

We are the owners and employees of the shop, we decide on the inventory, layout, etc. Customers (educators) come to the shop to see which bikes we have available and what tours you can take on those bikes. Our job is to decide which bikes we should sell, how to match customers to bikes, and how to support the touring activities.


  • Need for a lexicon at a high level -- define scalability, parallelism, etc.
  • What about entry for those who have a performance problem? “I’m only able to use 2 of my 100 cores,...”
  • Tools & environments
  • Hardware considerations -
  • If you have little or no resources - hardware wise you can teach effectively
    • remote resources - pointers to places to go
    • Books -
    • tools for basic courses
      • CS1/2
      • ALG
      • Data Struct
  • If you have moderate resources


Sally’s Journeyman Bike Tour (Sally is a 4th year student, preparing for a capstone project)

  1. Introduction
    1. Parallelism- what it is, why, myths and misconceptions, Parallelism “gotcha’s”
    2. Architecture motivation (eg. shared memory parallelism, distributed memory parallelism)
    3. Scalability and Performance Portability
    4. Heterogeneous architectures (eg. GPU’s)
    5. Concurrency Vs Parallelism
      1. Concurrency and parallelism are not the same! Concurrency is a programming abstraction that
    6. Design Considerations
      1. Policies/ Best Practices/Licensing
  2. Parallelism Patterns
    1. (Define the parallel abstractions that will be used for Programming Models)
    2. Task parallelism
      1. Pull examples from motifs/dwarves
    3. Data Parallelism
    4. Pipeline Parallelism
  3. Programming Languages
    1. (Need explicit reference to what parallel models are common/well maintained for each of the languages)
    2. C, C++, Fortran - Programs written in these language can be parallelised through a number of Models - Depending on the needs of your program, you could consider . . . .
    3. Python
    4. C#, .Net -
    5. Java - Has threading and parallel APIs built into the platform . see Link

Parallel Programming Models/Libs/Interfaces

    1. OpenMP --
      1. Tutorial presentation -- http://www.nic.uoregon.edu/iwomp2005/iwomp2005_tutorial_openmp_rvdp.pdf
      2. Community site -- www.openmp.org
      3. Code example -- openmp.org -- MD example
      4. Cheat sheet -- Fortran & C/C++
      5. Book reference
    2. Open Compute Language (OpenCL) is a low-level host API and device programming model language for programming heterogeneous many-core architectures, supporting data and task parallelism. OpenCL is an open standard developed by the Khronos OpenCL working group with implementations available from wide selection of hardware and software vendors, including AMD, Apple, and NVIDIA.
      1. Introduction Tutorial --

http://developer.amd.com/GPU/ATISTREAMSDK/pages/TutorialOpenCL.aspx

      1. Community site - www.khronos.org/opencl
      2. Quick reference guide - http://www.khronos.org/files/opencl-quick-reference-card.pdf
    2. Cuda
      1. NVIDIA site - http://www.nvidia.com/object/cuda_home_new.html
    3. Frameworks -
      1. Intel Threading Building Blocks (TBB) - TBB is a threading library to introduce parallelism into C/C++. TBB is a relatively easy way to introduce parallelism, especially for programmers familiar with templated code. TBB is available both as an open source project and also as commercial product from theIntel Corporation.
        1. Tutorial
        2. Reference Manual
        3. Example Codes(http://www.threadingbuildingblocks.org/codesamples.php)
      2. Ct, ConcRT, TPL, GCD
    4. Win32 threads - Still the default method used to introduce paralleism into code, native threading can be difficult implement and maintain. Microsfot corporation has a rich body of materila http://msdn.com
      1. Hart, Windows System Programming, 3rd ed.
    5. Posix
      1. Butenhof, Programming with POSIX Threads
      2. Programmers might consider using models such as OpenMP, TBB etc.
    6. Graphics API and languages - OpenGL, DirectX, WebGL
    7. Map/Reduce
  2. Compound Applications of Parallelism
    1. nested/hybrid
    2. Real example
  3. Parallel Algorithms
    1. Sort
      1. O(NlnN) vs Parallel vs GPU
    2. Spanning Tree/ Shortest Path
      1. Branch&Bound/ Divide & Conquer
    3. Parallel For
      1. Master/Worker
    4. Sparse Matrix
    5. FFT
    6. Finite Difference/Stencil methods
  4. Data Structures
    1. critical sections
    2. lock free implementations
  5. Dwarves/Motifs/Patterns
Retrieved from "http://wiki.sc-education.net/index.php/Bicycle_Tour"
Personal tools
SC Education sites