Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!harpo!eagle!mhuxt!mhuxi!cbosgd!ihnp4!we13!burl!duke!unc!koala
From: koala@unc.UUCP
Newsgroups: net.ai
Subject: Matrix Multiplication on the FFP Machine
Message-ID: <5687@unc.UUCP>
Date: Wed, 10-Aug-83 13:19:32 EDT
Article-I.D.: unc.5687
Posted: Wed Aug 10 13:19:32 1983
Date-Received: Thu, 11-Aug-83 05:08:03 EDT
Lines: 26


	Since  the  subject has been brought up, I felt I should
clear  up  some  of  the  statements about the FFP machine.  The
machine  consists  of  a linear vector of small processors which
communicate by being connected as the leaves of a binary tree.

	Roughly  speaking,  the  FFP  machine  performs  general
matrix multiplication in O(nxn) space and time.  Systolic arrays
can  multiply  matrices  in  O(n)  time,  but  do  not provide a
flexibility in the size of matrices that can be handled.

	Order  notation only presents half the picture - in real
life,  constant factors and other terms are also important.  The
machine's matrix multiply operation examines each element of the
two  matrices  once.   Multiplying  two  matrices,  mxn and nxp,
requires  accessing  (mxn + nxp) values, and this is the measure
of   the  time  for  the  computation.   Each  cell  performs  n
multiplications,  dominated  by  the  access.  Further, when you
multiply  two matrices, mxn and nxp, the result is of size mxp.
(Consider   multiplying   a   column  by  a  row).   Thus,  when
n  < (mxp)/(m+p), extra space must be allocated for the result.
This is also a quadratic time operation.

				David Middleton
				UNC Chapel Hill
				decvax!duke!unc!koala