**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**:- Systolic algorithms for multiplication (see T. Jebelean: Systolic multiprecision arithmetic - Chapt. 10, page 161).

**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: Systolic multiprecision arithmetic (PhD thesis), RISC report 94-37.
- L. Ruff: Generation and Verification of Systolic Algorithms (PhD Thesis).
- T. Jebelean, L. Szakacs: Functional-Based Synthesis of Systolic Online Multipliers.
- B. Matasaru, T. Jebelean: FPGA Implementation of an Extended Binary GCD Algorithm for Systolic Reduction of Rational Numbers Technical report no. 99-48.
- T. Jebelean: Using the Parallel Karatsuba Algorithm for Long Integer Multiplication and Division. Technical report no. 97-08
- T. Jebelean: Auto-Configurable Array for GCD Computation. Technical report no. 97-12
- T. Jebelean: Practical Integer Division with Karatsuba Complexity. Technical report no. 96-29
- T. Jebelean: Exact Division with Karatsuba Complexity. Technical report no. 96-31
- T. Jebelean: Integer and Rational Arithmetic on MasPar. Technical report no. 96-38
- T. Jebelean: Design of a Systolic Coprocessor for Rational Addition. Technical report no. 96-37

T. Jebelean