We describe a set of representations for polnomials and sparse matrices suited for use with fine-grain parallelism on a distributed memory multiprocessor system.Our aim is to support use of supercomputers with this style of architecture to perform computations that would exceed the main memory capacity of more traditional computers:although such systems have very high performance communication networks it is still essential to avoid letting any one part of the network become a bottleneck.We use randomised data placement both to avoid hot-spots in the communication patterns and to balance (in a probabilistic sense) the memeory load placed upon each processing element.the expected application areas for such a system will be those where intermediate expression swell means that the huge primary memory available on MPP systems will be needed if the smaller final result is to be successfully computed.
展开▼
