Mapping Cube Graphs on VLSI Array and Tree Architectures

摘要

We formalize a model of array architectures suitable for VLSI implementation. A formal model of an arbitrarily structured tree machine is also presented. A mathematical framework is developed to transform cube graphs, which are data-flow descriptions of certain matrix computations, onto the array and tree models. All published algorithms for these computations can be obtained using the mathematical framework. In addition, novel linear-array algorithms for matrix multiplication are obtained. More importantly, the algorithms obtained for the tree model are of special significance. Besides their novelty, the independence of the tree algorithms from a specific inter-processor communication geometry make them robust to hardware faults as opposed to algorithms that are based on specific interconnection requirements. (Author)