**Parallel Algorithms in Symobolic Computation**

Winter Semester 2013

Friday 10:15 - 11:45 KG 712

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. 11: 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 18 and Oct 25, individual work:**- Refresh the basic notions about the basic models of computation.
- Inspect the literature (see below) and think about a possible min-project.

**Nov 8: Lecture 2**:- The computing power of cellular automata: comparison with sequential machines using the problem of language recognition.

**Nov. 15: Lecture 3**:- Basic parallel computer architectures with examples.
- Systolic arrays: definition, comparison with other architectures.

**Nov. 22: Lecture 4**:- Systolic algorithms for multiplication (see T. Jebelean: Systolic multiprecision arithmetic - Chapt. 10, page 161).

**Nov. 29 and further**:- Subject to be announced.

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