File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Oblivious routing for LC permutations on hypercubes

TitleOblivious routing for LC permutations on hypercubes
Authors
Issue Date1999
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/parco
Citation
Parallel Computing, 1999, v. 25 n. 4, p. 445-460 How to Cite?
AbstractWe propose an oblivious algorithm to route linear-complement (LC) permutations on hypercubes in circuit switched and wormhole routing. The algorithm guarantees that N independent paths can be set up simultaneously for any LC permutation with only a comparison of two bits in one routing step for any path. An LC permutation is determined by a transformation matrix T and a constant modifier C. For all the LC permutations with the same transformation matrix T (we call them a type of permutations), an algorithm is executed to find an ordered sequence of dimensions without knowing a particular permutation. When the sequence of dimensions is used in the routing process for all the packets of a permutation of this type, a comparison of two bits is carried out in each routing step in the packet transmission process. It is guaranteed that no contention will occur between any two paths on the use of the dimensional links, thus N independent paths can be set up simultaneously for the N packets of an LC permutation. Time complexity of the algorithm for finding an ordered sequence for the use of the n dimensions is O(n3) for any type of LC permutations (rather than one particular LC permutation), and it can be carried out off-line. The routing process itself is distributed, and oblivious.
Persistent Identifierhttp://hdl.handle.net/10722/88952
ISSN
2015 Impact Factor: 1.0
2015 SCImago Journal Rankings: 0.726
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLiu, Zen_HK
dc.contributor.authorCheung, DWen_HK
dc.date.accessioned2010-09-06T09:50:32Z-
dc.date.available2010-09-06T09:50:32Z-
dc.date.issued1999en_HK
dc.identifier.citationParallel Computing, 1999, v. 25 n. 4, p. 445-460en_HK
dc.identifier.issn0167-8191en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88952-
dc.description.abstractWe propose an oblivious algorithm to route linear-complement (LC) permutations on hypercubes in circuit switched and wormhole routing. The algorithm guarantees that N independent paths can be set up simultaneously for any LC permutation with only a comparison of two bits in one routing step for any path. An LC permutation is determined by a transformation matrix T and a constant modifier C. For all the LC permutations with the same transformation matrix T (we call them a type of permutations), an algorithm is executed to find an ordered sequence of dimensions without knowing a particular permutation. When the sequence of dimensions is used in the routing process for all the packets of a permutation of this type, a comparison of two bits is carried out in each routing step in the packet transmission process. It is guaranteed that no contention will occur between any two paths on the use of the dimensional links, thus N independent paths can be set up simultaneously for the N packets of an LC permutation. Time complexity of the algorithm for finding an ordered sequence for the use of the n dimensions is O(n3) for any type of LC permutations (rather than one particular LC permutation), and it can be carried out off-line. The routing process itself is distributed, and oblivious.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/parcoen_HK
dc.relation.ispartofParallel Computingen_HK
dc.rightsParallel Computing. Copyright © Elsevier BV.en_HK
dc.titleOblivious routing for LC permutations on hypercubesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0167-8191&volume=25&spage=445&epage=460&date=1999&atitle=Oblivious+routing+for+LC+permutations+on+hypercubesen_HK
dc.identifier.emailCheung, DW:dcheung@cs.hku.hken_HK
dc.identifier.authorityCheung, DW=rp00101en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/S0167-8191(99)00008-3en_HK
dc.identifier.scopuseid_2-s2.0-0032634611en_HK
dc.identifier.hkuros41338en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0032634611&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume25en_HK
dc.identifier.issue4en_HK
dc.identifier.spage445en_HK
dc.identifier.epage460en_HK
dc.identifier.isiWOS:000080240600006-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLiu, Z=7406671827en_HK
dc.identifier.scopusauthoridCheung, DW=34567902600en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats