Fine Grained Parallel Computing
Winter Semester 2011
Friday 10:15 - 11:45 HT 177 F
The course is a presentation of
several fined grained parallel computing models and their realization
as well as of some specific parallel algorithms for symbolic computation, especially for long integer arithmetic.
Lectures
- Oct. 14: Lecture 1:
- The Chomsky hierarchy of grammars and formal languages: regular, context-free, context dependent, unrestricted, and their relation to
- basic models of computation: finite state machines, push-down automata, linear bounded automata, Turing machines.
- No lecture on Oct 21, individual work:
- Refresh the basic notions about the basic models of computation.
- Inspect the literature (see below) and think about a possible project.
- Oct. 28: Lecture 2:
- The computing power of cellular automata: comparison with sequential
machines using the problem of language recognition.
- Nov. 4: Lecture 3:
- Basic parallel computer architectures with examples.
- Systolic arrays: definition, comparison with other architectures.
- Nov. 11: Lecture 4:
- Nov. 18: Lecture 5:
- Systolic algorithms for multiplication (continued).
- Nov. 25: Lecture 6:
- Parallelization of the Karatsuba multiplication and division.
- Exact division.
- Dec. 2: Lecture 7:
- Systolic algorithms for exact division.
- GCD algorithms: Euclidean, Lehmer, binary, generalized binary.
- Dec. 9: no lecture:
- Individual work on the mini-projects.
- Dec. 16: Lecture 8:
- Systolic GCD.
- Discussion about the schedule of mini-project presentations by the students.
Useful reading:
T. Jebelean