** Parallel Algorithms in Symbolic Computation**

Winter Semester 2009

First lecture on Fri 9 Oct 10:15 - 11:45 HT 177F

The course is a presentation of several parallel algorithms for symbolic computation, especially for long integer arithmetic.

Lectures

**Oct. 9: Lecture 1**:- Basic models of computation: finite state machines, push-down automata, linear bounded automata, Turing machines.

**Oct. 16: Lecture 2**:- Basic models of parallel computation: cellular automata.

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

**Oct. 30: No lecture.****Nov. 6: Lecture 4**:- Systolic algorithms for multiplication (see T. Jebelean: Systolic multiprecision arithmetic - Chapt. 10 (page 161).

**Nov. 6: Lecture 5**:- Systolic algorithms for multiplication (continued).
- Parallelization of the Karatsuba multiplication.

- 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