A three-dimensional (3-D) wavefront array with minimal computation time (latency) of 2n - 2 cyclesfor an n*n matrix and minimal block pipelining period of one is introduced and compared to existingtwo-dimensional (2-D) systolic array architectures for L-U factorization. An optimal processor-timeproduct of (1/3)n{sup}3 with cycles defined computationally by two operations is obtained whensuccessive problem instances are considered. The 3-D architecture is extensible and scalable, is cycleinvariant (all respects), has minimal node complexity of two arithmetic operations per cycle, hasunidirectional data forwarding in three dimensions, has 100 utilization of processing elements forsuccessive inputs, and has a cycle-invariant one-to-one correspondence between input/output portsand input/output matrix elements.
展开▼