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