A parallel implementation of Strassen's matrix multiplication algorithm for wormhole-routed all-port 2D torus networks


Baransel C., İMRE K. M.

JOURNAL OF SUPERCOMPUTING, vol.62, no.1, pp.486-509, 2012 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 62 Issue: 1
  • Publication Date: 2012
  • Doi Number: 10.1007/s11227-011-0730-1
  • Title of Journal : JOURNAL OF SUPERCOMPUTING
  • Page Numbers: pp.486-509

Abstract

A new parallel implementation of Strassen's matrix multiplication algorithm is proposed for massively parallel supercomputers with 2D, all-port torus interconnection networks. The proposed algorithm employs a special conflict-free routing pattern for better scalability and is able to yield a performance rate very close to the theoretical bound for many practical network and matrix sizes. It effectively scales up to very large networks typically containing hundreds-of-thousands processors where petaflop or exaflop processing rates are sought.