Parallel and Distributed Algorithms

Parallel and distributed algorithms, motivations. Parallel and distributed architectures vs. von Neumann architecture. Computational resources within different paradigms.
Parallel and distributed architectures:
- Problems in parallel algorithms design: synthesis, analysis, universality
- Shared and distributed memory parallel architectures: communication in both realms
- Shared memory architectures. The PRAM (Parallel RAM) model
- PRAM as a SIMD vs. MIMD architecture
- PRAM models: EREW, CREW, CRCW (common, priority, ... )
- Computational resources: hardware and time complexity
- Comparisons with sequential algorithms: speed-up and efficiency
- Efficient paralle solution on PRAM of some fundamental problems
- Computing iterated binary associative operations. iterated sum: structure and analysis of a parallel solution
- Efficient parallel algorithms for: linear algebra, graph theory, optimization, ...
- Computing prefix iterated binary associative operations. prefix sum
- Structure and analysis of Kogge-Stone's algorithm (pointer doubling)
- Efficient parallel polynomial evaluation. Parallel search algorithms
- Sorting problems (ranking), efficient sequential solutions
- Efficient parallel sorting problems. Batcher's Bitonic sort, structure and analysis
- Eulerian circuit technique in parallel algorithm design
- Distributed memory parallel architectures, interconnection network and performance parameters: degree, diameter and bisection size
- Sorting networks and the 0-1 principle (Knuth)
- Linear arrays of processors, structure, functions and net parameters
- Solving on linear arrays of processors: sorting, max and shuffle
- Odd-even and merge-split sorting, structure and analysis
- Meshes of processors, structures, functions and net parameters
- Computing max on a mesh
- LS3 sorting algorithms, structure and analysis
Distributed architectures and algorithms:
- Distributed architecture modeling
- Entities and communication channels
- Computational resources, time and message complexity
- Structure and analysis of distributed algorithms for fundamental problems
- Broadcasting, lower bounds for distributed solutions
- The flooding algorithm
- Wake-up, the wflooding algorithm
- Traversing, the depth-first algorithm
- Spanning tree, the shout and depth-first algorithm
- Election, computability limitations and elextion by minimum
- Routing, gossiping algorithms