Accession Number : ADA139306

Title :   On Mapping Cube Graphs on VLSI Array and Tree Architectures.

Descriptive Note : Technical rept.,

Corporate Author : MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s) : Ramakrishnan,I V ; Varman,P J

PDF Url : ADA139306

Report Date : Dec 1983

Pagination or Media Count : 34

Abstract : 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)

Descriptors :   *Trees, *Processing equipment, *Graphs, *Arrays, *Integrated circuits, *Computer architecture, Algorithms, Mapping, Circuit interconnections, Computations, Faults, Requirements, Models, Architecture

Subject Categories : Electrical and Electronic Equipment
      Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE