A Network Configuration Algorithm Based on Optimization of Kirchhoff Index
|Title:||A Network Configuration Algorithm Based on Optimization of Kirchhoff Index||Authors:||Hackett, Adam
|Permanent link:||http://hdl.handle.net/10197/9895||Date:||30-Jul-2013||Online since:||2019-04-10T11:52:53Z||Abstract:||Traditionally, a parallel application is partitioned, mapped and then routed on a network of compute nodes where the topology of the interconnection network is fixed and known beforehand. Such a topology often comes with redundant links to accommodate the communication patterns of a wide range of applications. With recent advances in technology for optical circuit switches, it is now possible to construct a network with much fewer links, and to make the link endpoints configurable to suit the communication pattern of a given application. While this is economical (saving both links and the power to run them), it raises the difficult problem of how to configure the network and how to reconfigure it quickly when the application's communication pattern changes. In this paper, we propose the Kirchhoff index (KI) of a certain weighted graph related to the interconnection network as a proxy for its communication throughput. Our usage of this metric is based on a theoretical analogy between resistances in an electrical network and communication loads in the interconnection network. We show how mathematical techniques for reducing KI can be used to configure a network in a dramatically shorter time as compared to the current state-of-the-art scheme.||Type of material:||Conference Publication||Publisher:||IEEE||Start page:||407||End page:||417||Copyright (published version):||2013 IEEE||Keywords:||Graph partitioning algorithm; Reconfigurable topology; Optical circuit switch; Kirchhoff index||DOI:||10.1109/IPDPS.2013.116||Language:||en||Status of Item:||Peer reviewed||Is part of:||2013 IEEE International Parallel & Distributed Processing Symposium (IPDPS): 20-2 May 2013: Boston (MA) USA||Conference Details:||2013 27th International Symposium on Parallel and Distributed Processing, Boston, United States of America, 20-24 May 2013||ISBN:||978-0-7685-4971-2|
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.