|
In this thesis, we present a novel to mapping algorithms onto
linear arrays. First, we use directed acyclic graphs(DAGs) to
represent the computation dependence of algorithms. The
vertices in a DAG denote statements of an algorithm and an arc
between a pair of vertices denotes the data flow. We partition
the vertices of the DAG into a group of sets by topological
sorting, and the vertices in each set are assigned to different
processing elements(PEs). Two dependence vertices should be
assigned to PEs whose distance is as near as possible. Design
examples are also described in this thesis including
multiplication of band-matrix and vector, convolution problem,
sorting, matrix multiplication, and dynamic programming
problem. Our linear arrays for sorting, band-matrix and vector
multiplication, and convolution problem require only half the
number of PEs used by Ramakrishnan's designs, while the
computation time is the same. If each PE in the linear array
has local memory of size n or has n-1 shift registers in a
channel, the linear array designed for matrix multiplication
are better than previous results. The time delay of the
channels does not depend on the problem size in the linear
array designed for the optimal parenthesization problem using
dynamic programming approach. As a result, we can solve the
dynamic programming problem using fixed size linear array
independent of the problem size by partitioning the problem.
|