File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/S0167-8191(99)00008-3
- Scopus: eid_2-s2.0-0032634611
- WOS: WOS:000080240600006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Oblivious routing for LC permutations on hypercubes
Title | Oblivious routing for LC permutations on hypercubes |
---|---|
Authors | |
Issue Date | 1999 |
Publisher | Elsevier 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/88952 |
ISSN | 2015 Impact Factor: 1.0 2015 SCImago Journal Rankings: 0.726 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Liu, Z | en_HK |
dc.contributor.author | Cheung, DW | en_HK |
dc.date.accessioned | 2010-09-06T09:50:32Z | - |
dc.date.available | 2010-09-06T09:50:32Z | - |
dc.date.issued | 1999 | en_HK |
dc.identifier.citation | Parallel Computing, 1999, v. 25 n. 4, p. 445-460 | en_HK |
dc.identifier.issn | 0167-8191 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88952 | - |
dc.description.abstract | We 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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/parco | en_HK |
dc.relation.ispartof | Parallel Computing | en_HK |
dc.rights | Parallel Computing. Copyright © Elsevier BV. | en_HK |
dc.title | Oblivious routing for LC permutations on hypercubes | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+hypercubes | en_HK |
dc.identifier.email | Cheung, DW:dcheung@cs.hku.hk | en_HK |
dc.identifier.authority | Cheung, DW=rp00101 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/S0167-8191(99)00008-3 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0032634611 | en_HK |
dc.identifier.hkuros | 41338 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0032634611&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 25 | en_HK |
dc.identifier.issue | 4 | en_HK |
dc.identifier.spage | 445 | en_HK |
dc.identifier.epage | 460 | en_HK |
dc.identifier.isi | WOS:000080240600006 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Liu, Z=7406671827 | en_HK |
dc.identifier.scopusauthorid | Cheung, DW=34567902600 | en_HK |