Fine Grained Parallel Computing
Winter Semester 2010
Friday 10:15 - 11:45 K 009 D
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. 8: Lecture 1:
- Overview of parallel computing paradigms: MIMD, SIMD.
- Examples of typical parallel architectures.
- Basic models of computation: finite state machines, push-down automata, linear bounded automata, Turing machines.
- No lecture on Oct 15, individual work:
- Refresh the basic notions about the basic models of computation.
- Inspect the literature (see below) and think about a possible project.
- Oct. 22: Lecture 2:
- 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.
- Oct. 29: Lecture 3:
- Cellular automata: definition and basic properties.
- Nov. 5: Lecture 4:
- Cellular automata: language recognition.
- Nov. 12: Lecture 5:
- No lecture on Nov. 19.:
- Individual work on preparing the projects.
- Nov. 26: Lecture 6:
- Dec. 3: Lecture 7:
- Dec. 10: Lecture 8:
- Hardware implementation: normalization of rational numbers.
- Multiplication and addition.
- Dec. 17: Lecture 9:
- Project presentations.
- GCD and exact division.
- Jan 14: Lecture 10:
- Second version of normalization of rational numbers.
- GCD with Feeder.
- Jan 21: Lecture 11:
- Project presentations.
- Third version of GCD array: self-configurable cells.
- Functional based synthesis of online systolic arrays.
- Jan 28: Lecture 12:
- Final project presentations.
- Functional based synthesis of online systolic arrays.
Useful reading:
T. Jebelean