On partitioning the Faddeev algorithm

Partitioned schemes for computing the Faddeev algorithm are derived, using a graph-based methodology. Such implementations are obtained by performing transformations on the fully parallel dependence graph of the algorithm. Linear and two-dimensional structures are derived and evaluated in terms of throughput, I/O bandwidth, utilization of processing elements, and overhead due to partitioning. The partitioned implementation are compared with schemes previously proposed. It is shown that throughput of both the linear and two-dimensional arrays derived here tends to 3m/7n/sup 3/ for n*n matrices, where m is the number of cells and utilization tends to 1. A two-dimensional scheme that is more efficient and has less overhead than others previously proposed is derived. It is shown that for partitioned implementations with the same number of cells, a linear array performs better, its implementation is easier, and it is better suited for fault-tolerant capabilities than a two-dimensional one.<>