🚀 go-pugleaf

Title of Talk:  A Mathematical Theory of High-Level Synthesis

Speaker:  Dr. Farhad Mavaddat
          Department of Computer Science
          University of Waterloo
          Waterloo, Ontario
          Canada, N2L 3G1
          fmavaddat@watmath.uwaterloo.ca

Date:   Friday, July 31, 1992
Time:   Talk begins at 10:30 a.m.
Place:  Room 432 Computer Science Building
        University of California, Irvine


Abstract:


High-Level synthesis is considered as the translation of
a high-level behavioural specification into an equivalent
structure of control-units and data-paths.

We define a data-path's behaviour as a collection of
{\em recurrence-systems\,} called a
{\em catenation-machine (CM)\,}, where
each recurrence-system represents an {\em DP-instruction\,}.
We define an algebraic system for manipulating
DP-instructions, establish a precise link between the theory of catenation
machines and the DT0L category of L systems,
and formalize {\em sequentialization\,}
as an operational trade-off between data-path
and control-unit complexities.

Given a high-level expected behaviour,
we show that when the target data-path is known,
control-unit synthesis can be formulated as a
{\em parsing\,} problem by the corresponding DT0L grammar;
when the target data-path is not known,
the data-path synthesis problem becomes one
of {\em grammar inference\,} and {\em learning\,}.

Considerable attention to the theories of
parsing, grammar inference, and learning
by the researchers in the past
has shown that both DT0L parsing and CM
inference are hard problems with no known
efficient algorithms.
Therefore, we introduce heuristic methods to
achieve both goals, often with good results.
A number of these results will be presented and discussed.