A Network Configuration Algorithm Based on Optimization of Kirchhoff Index

Files in This Item:
File Description SizeFormat 
ajwani_ipdps13.pdf305.73 kBAdobe PDFDownload
Title: A Network Configuration Algorithm Based on Optimization of Kirchhoff Index
Authors: Hackett, Adam
Ajwani, Deepak
Ali, Shoukat
et al.
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 algorithmReconfigurable topologyOptical circuit switchKirchhoff 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

Citations 50

Last Week
Last month
checked on May 17, 2019

Google ScholarTM



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.