Graph Partitioning for Reconfigurable Topology

DC FieldValueLanguage
dc.contributor.authorAjwani, Deepak-
dc.contributor.authorAli, Shoukat-
dc.contributor.authorMorrison, John P.- IEEEen_US
dc.descriptionThe 2012 IEEE International Parallel and Distributed Symposium (IPDPS), 21-25 May 2012, Shanghai, Chinaen_US
dc.description.abstractOptical circuit switches have recently been proposed as a low-cost, low-power and high-bandwidth alternative to electronic switches for the design of high-performance compute clusters. An added advantage of these switches is that they allow for a reconfiguration of the network topology to suit the requirements of the application. To realize the full potential of a high-performance computing system with a reconfigurable interconnect, there is a need to design algorithms for computing a topology that will allow for a high-throughput load distribution, while simultaneously partitioning the computational task graph of the application for the computed topology. In this paper, we propose a new framework that exploits such reconfigurable interconnects to achieve these interdependent goals, i.e., to iteratively co-optimize the network topology configuration, application partitioning and network flow routing to maximize throughput for a given application. We also present a novel way of computing a high-throughput initial topology based on the structural properties of the application to seed our co-optimizing framework. We show the value of our approach on synthetic graphs that emulate the key characteristics of a class of stream computing applications that require high throughput. Our experiments show that the proposed technique is fast and computes high-quality partitions of such graphs for a broad range of hardware parameters that varies the bottleneck from computation to communication.en_US
dc.description.sponsorshipIrish Research Council for Science, Engineering and Technologyen_US
dc.relation.ispartofProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium: 21-25 May 2012 / Shanghai, Chinaen_US
dc.rights© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.en_US
dc.subjectGraph-partitioning algorithmsen_US
dc.subjectReconfigurable topologyen_US
dc.subjectOptical circuit switchen_US
dc.titleGraph Partitioning for Reconfigurable Topologyen_US
dc.typeConference Publicationen_US
dc.statusPeer revieweden_US
dc.neeo.contributorMorrison|John P.|aut|-
item.fulltextWith Fulltext-
Appears in Collections:Computer Science Research Collection
Files in This Item:
File Description SizeFormat 
ajwani_ipdps12.pdf196.06 kBAdobe PDFDownload
Show simple item record

Citations 50

Last Week
Last month
checked on Jun 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.