File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient termination detection for loosely synchronous applications in multicomputers

TitleEfficient termination detection for loosely synchronous applications in multicomputers
Authors
KeywordsData parallelism
Distributed algorithms
Interconnection networks
Multicomputers
Parallel and distributed systems
Synchronous computations
Termination detection
Issue Date1996
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 1996, v. 7 n. 5, p. 537-544 How to Cite?
AbstractWe propose a simple algorithm which is based on edge-coloring of system graphs for termination detection of loosely synchronous computations. The proposed algorithm is fully symmetric in that all processors run syntactically identical code and can detect global termination at the same time. Under the 1-port communication model, the algorithm is optimal in terms of termination delay, the difference between the time when a global termination occurs and the time it is detected, in a number of structures - chain, ring of even number of nodes, k-ary n-cube and k-ary n-mesh of low degree, where k is even; and near-optimal for other cases. The optimality analysis is based on results from a related problem, periodic gossiping in edge-colored graphs. This algorithm has been applied to some practical cases in which the overhead due to its execution is found to be insignificant. © 1996 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/43630
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
References

 

DC FieldValueLanguage
dc.contributor.authorXu, Cen_HK
dc.contributor.authorLau, FCMen_HK
dc.date.accessioned2007-03-23T04:50:51Z-
dc.date.available2007-03-23T04:50:51Z-
dc.date.issued1996en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1996, v. 7 n. 5, p. 537-544en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43630-
dc.description.abstractWe propose a simple algorithm which is based on edge-coloring of system graphs for termination detection of loosely synchronous computations. The proposed algorithm is fully symmetric in that all processors run syntactically identical code and can detect global termination at the same time. Under the 1-port communication model, the algorithm is optimal in terms of termination delay, the difference between the time when a global termination occurs and the time it is detected, in a number of structures - chain, ring of even number of nodes, k-ary n-cube and k-ary n-mesh of low degree, where k is even; and near-optimal for other cases. The optimality analysis is based on results from a related problem, periodic gossiping in edge-colored graphs. This algorithm has been applied to some practical cases in which the overhead due to its execution is found to be insignificant. © 1996 IEEE.en_HK
dc.format.extent1043325 bytes-
dc.format.extent26112 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©1996 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.subjectData parallelismen_HK
dc.subjectDistributed algorithmsen_HK
dc.subjectInterconnection networksen_HK
dc.subjectMulticomputersen_HK
dc.subjectParallel and distributed systemsen_HK
dc.subjectSynchronous computationsen_HK
dc.subjectTermination detectionen_HK
dc.titleEfficient termination detection for loosely synchronous applications in multicomputersen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=7&issue=5&spage=537&epage=544&date=1996&atitle=Efficient+termination+detection+for+loosely+synchronous+applications+in+multicomputersen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.503778en_HK
dc.identifier.scopuseid_2-s2.0-0030145439en_HK
dc.identifier.hkuros11745-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0030145439&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume7en_HK
dc.identifier.issue5en_HK
dc.identifier.spage537en_HK
dc.identifier.epage544en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridXu, C=51562964900en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats