[ewg] Optimized and deadlock-free routing algorithm for InfiniBand

[Jens Domke]

Dear OpenSM community,

We would like to point you towards an optimized and
deadlock-free routing algorithm for InfiniBand. We finished
an implementation within OpenSM as part of an academic project. 

The new routing resulted in up to 40% improved network performance
in some special architectures and it nearly halved the runtime
for all-to-all MPI communications in our test case, etc.
Scientific paper describing the algorithm, implementation and
deadlock handling have been published at Hot Interconnects 2009 [2]
and IPDPS 2011 [1] repectively. You can find copies of all papers
at the bottom of [3].

We also provide a patch for the OpenSM integration at [1]. The patch,
based on a checkout from Oct. 2009, includes two algorithms. The first
one is the SSSP routing, which is not deadlock-free but could used as an
replacement for MinHop because it can also handle arbitrary topologies.
The second algorithm is DFSSSP, a deadlock-free version of the SSSP
routing, using virtual channels like the LASH algorithm to avoid
deadlocks.

As a purely academic project, we cannot offer to maintain the patch but
we can answer your questions regarding the algorithms. However, we
believe that it is mostly bug-free and should be easy to maintain by the
community. We would appreciate if our work would find its way into
OpenSM (the license is BSD or GPLv2, like the other parts of the subnet
manager).

Thank you very much,
  Jens Domke and Torsten Hoefler


[1]: Domke, Hoefler, Nagel: Deadlock-Free Oblivious Routing for
Arbitrary Topologies
(http://www.unixer.de/publications/index.php?pub=124)
[2]: Hoefler, Schneider, Lumsdaine: Optimized Routing for Large-Scale
InfiniBand Networks (http://www.unixer.de/publications/index.php?pub=93)
[3]: http://www.unixer.de/research/dfsssp/index.php 


-- 
--------------------------------
Dipl.-Math. Jens Domke
Research Assistant

Technische Universitaet Dresden
Center for Information Services and High Performance Computing (ZIH)
Interdisciplinary Application Development and Coordination
01062 Dresden
Tel.: +49 (351) 463-39114
Fax: +49 (351) 463-37773
E-Mail: jens.domke at tu-dresden.de
--------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 4296 bytes
Desc: not available
URL: <http://lists.openfabrics.org/pipermail/ewg/attachments/20110614/e02154d7/attachment.bin>