Browse Prior Art Database

Communication Scheme for Factoring Large Matrices on Distributed Memory Systems

IP.com Disclosure Number: IPCOM000104461D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 59K

Publishing Venue

IBM

Related People

Agarwal, RC: AUTHOR

Abstract

A scheme is disclosed which optimizes communication among a set of computing nodes communicating through a communication network. This scheme has direct applicability to the problem of factoring a large matrix in a distributed computing environment.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 54% of the total text.

Communication Scheme for Factoring Large Matrices on Distributed Memory Systems

      A scheme is disclosed which optimizes communication among a set
of computing nodes communicating through a communication network.
This scheme has direct applicability to the problem of factoring a
large matrix in a distributed computing environment.

      Consider a distributed computing environment with P computing
nodes connected through a fully connected (cross-bar type)
communication network.  At any time, a node can either receive or
send information to any one other node.  Thus, at any given time at
the most P/2 pairs of nodes can communicate.  All communications are
only in one direction.  This description implies that the network
lacks a broadcast facility.

      The problem requires communicating a message generated by one
of the nodes to all other nodes.  Each message requires time T for
communication between a pair of nodes.  Messages are generated
sequentially by each node.  Thus the k-th message is generated by
node k at time 2kT.  The (k+1)st message is generated by (k+1)st node
at time 2(k+1)T, and so on.  Using zero based indexing scheme, the
node numbers are evaluated modulo P.  Thus logical nodes j and j+P
refer to the same physical node.  Another constraint of the problem
is that the k-th message can not be generated unless the k-th node
has received all prior messages.  In the context of the matrix
factorization problem, the k-th block of colum...