File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An optimal algorithm for global termination detection in shared-memory asynchronous multiprocessor systems

TitleAn optimal algorithm for global termination detection in shared-memory asynchronous multiprocessor systems
Authors
KeywordsOptimality
Shared-memory multiprocessor systems
Termination detect
Issue Date1997
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, 1997, v. 8 n. 5, p. 538-543 How to Cite?
AbstractIn the literature, the problem of global termination detection in parallel systems is usually solved by message passing. In shared-memory systems, this problem can also be solved by using exclusively accessible variables with locking mechanisms. In this paper, we present an algorithm that solves the problem of global termination detection in shared-memory asynchronous multiprocessor systems without using locking. We assume a reasonable computation model in which concurrent reading does not require locking and concurrent writing different values without locking results in an arbitrary one of the values being actually written. For a system of n processors, the algorithm allocates a working space of 2n + 1 bits. The worst case time complexity of the algorithm is n + 2√n + 1, which we prove is the lower bound under a reasonable model of computation. © 1997 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/43635
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
References

 

DC FieldValueLanguage
dc.contributor.authorLeung, HFen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2007-03-23T04:50:58Z-
dc.date.available2007-03-23T04:50:58Z-
dc.date.issued1997en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1997, v. 8 n. 5, p. 538-543en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43635-
dc.description.abstractIn the literature, the problem of global termination detection in parallel systems is usually solved by message passing. In shared-memory systems, this problem can also be solved by using exclusively accessible variables with locking mechanisms. In this paper, we present an algorithm that solves the problem of global termination detection in shared-memory asynchronous multiprocessor systems without using locking. We assume a reasonable computation model in which concurrent reading does not require locking and concurrent writing different values without locking results in an arbitrary one of the values being actually written. For a system of n processors, the algorithm allocates a working space of 2n + 1 bits. The worst case time complexity of the algorithm is n + 2√n + 1, which we prove is the lower bound under a reasonable model of computation. © 1997 IEEE.en_HK
dc.format.extent380769 bytes-
dc.format.extent25600 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©1997 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.subjectOptimalityen_HK
dc.subjectShared-memory multiprocessor systemsen_HK
dc.subjectTermination detecten_HK
dc.titleAn optimal algorithm for global termination detection in shared-memory asynchronous multiprocessor systemsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=8&issue=5&spage=538&epage=543&date=1997&atitle=An+optimal+algorithm+for+global+termination+detection+in+shared-memory+asynchronous+multiprocessor+systemsen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.598280en_HK
dc.identifier.scopuseid_2-s2.0-0031145222en_HK
dc.identifier.hkuros25407-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0031145222&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume8en_HK
dc.identifier.issue5en_HK
dc.identifier.spage538en_HK
dc.identifier.epage543en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridLeung, HF=7202811431en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats