**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**:- Systolic multiplication.

**No lecture on Nov. 19.**:- Individual work on preparing the projects.

**Nov. 26: Lecture 6**:- Systolic exact division.

**Dec. 3: Lecture 7**:- Systolic GCD.

**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: 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