Introduction to Parallel Algorithms Design and Techniques

This chapter gives an overview of how to approach a problem and design a problem in a parallel manner. The chapter starts with an insight into how a problem can be decomposed to solve it in parallel, touching upon aspects of data-dependencies and the measures of parallel algorithms.
The last section deals with specific parallel algorithms

Use Synchronization Routines Provided by the Threading API Rather than Hand-Coded Synchronization

Application programmers sometimes write hand-coded synchronization routines rather than using constructs provided by a threading API in order to reduce synchronization overhead or provide different functionality than existing constructs offer.
  • Serveur
  • OpenMP*
  • Hyper-Threading
  • synchronization
  • Pthreads
  • Win32 threads
  • spin-wait
  • Informatique parallèle
  • Parallélisation
  • Choosing Appropriate Synchronization Primitives to Minimize Overhead

    Currently, there are a number of synchronization mechanisms available, and it is left to the application developer to choose an appropriate one to minimize overall synchronization overhead.
  • Développeurs
  • Serveur
  • atomic operations
  • synchronization
  • Win32 threads
  • system overhead
  • mutual exclusion
  • Informatique parallèle
  • Parallélisation
  • Avoiding Heap Contention Among Threads

    Avoiding Heap Contention Among Threads (PDF 256KB)


    Allocating memory from the system heap can be an expensive operation due to a lock used by system runtime libraries to synchronize access to the heap. Contention on this lock can limit the performance benefits from multithreading. To solve this problem, apply an allocation strategy that avoids using shared locks, or use third party heap managers.

  • Développeurs
  • Microsoft Windows* 8.x
  • Serveur
  • Intermédiaire
  • Intel® VTune™ Amplifier
  • Intel® Parallel Studio XE Composer Edition
  • synchronization
  • heap contention
  • dynamic memory allocation
  • lock contention
  • stack allocation
  • Informatique parallèle
  • Parallélisation
  • Courseware - Parallel Algorithms

    • PRAM model
    • Exclusive versus concurrent reads and writes
    • Pointer jumping
    • Brent’s theorem and work efficiency

    Introduction to Parallel Algorithms Design and Techniques

    Material Type:

    Article / White paper

    ISN Logo

  • Professeurs
  • Étudiants
  • Algorithms and Complexity
  • Parallel Algorithms
  • Parallel algorithm
  • Decomposition
  • synchronization
  • load balancing
  • granularity
  • matrix multiplication
  • sorting
  • Thread Management
  • cache efficiency
  • processor affinity
  • Informatique parallèle
  • Parallélisation
  • Parallel Programming Talk #99 "Taming the Wild Order of Synchronizations" with YY Zhou

    It’s Tuesday, January 25, 2011 and this is Parallel Programming Talk

    The News:

      • Casual Connect (Casual Games industry)- Feb 10 – 12 Congress Center, Hamburg, Germany - for casual game developers… Learn more:

    Win32 Functions to Create, Suspend, and Terminate Threads

    Apply procedures provided by the Microsoft Win32 API to create, suspend, resume, and terminate threads. Context switching in a multithreaded application is cheaper than context switching of multiple processes, because switching processes carries a lot more overhead than switching threads.
  • Développeurs
  • Microsoft Windows* (XP, Vista, 7)
  • synchronization
  • Multi-thread apps for Multi-Core
  • How to thread?
  • Informatique parallèle
  • S’abonner à synchronization