A unified approach to off-line permutation routing on parallel networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A unified approach to off-line permutation routing on parallel networks

Full text

Pdf (804 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents

Island of Crete, Greece

Pages: 398 - 406

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

F. Annexstein	COINS Department, University of Massachusetts, Amherst, Ma
M. Baumslag	COINS Department, University of Massachusetts, Amherst, Ma

Sponsors

IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/97444.97707 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AK	S. B. Akers , B. Krishnamurthy, A Group-Theoretic Model for Symmetric Interconnection Networks, IEEE Transactions on Computers, v.38 n.4, p.555-566, April 1989 [doi>10.1109/12.21148]
	AP	B. Alspach, T.D. Parsons (1982): A construction for vertex-transitive graphs. Ca~ad. J. Ma~h., Vol. 34~ no. 2~ 307-318.
	ABR	Fred Annexstein , Marc Baumslag , Arnold L. Rosenberg, Group action graphs and parallel architectures, SIAM Journal on Computing, v.19 n.3, p.544-569, June 1990 [doi>10.1137/0219037]
	Be	V.E. Bene~ (196~): M~th~r.~ti~~l theory of connecting networks. Academic Press. Mafl~ema~ics in Science arid Engineering, Volume 17.
	BD	J.-C. Bermond , C. Delorme , J.-J. Quisquater, Strategies for interconnection networks: some methods from graph theory, Journal of Parallel and Distributed Computing, v.3 n.4, p.433-449, December 1, 1986 [doi>10.1016/0743-7315(86)90008-0]
	CCFFLMMS	Lowell Campbell , Gunnar E. Carlsson , Michael J. Dinneen , Vance Faber , Michael R. Fellows , Michael A. Langston , James W. Moore , Andrew P. Mullhaupt , Harlan B. Sexton, Dense Symmetric Networks From Linear Groups, University of Tennessee, Knoxville, TN, 1989
	CCSW	G. E. Carlsson , J. E. Cruthirds , H. B. Sexton , C. G. Wright, Interconnection networks based on a generalization of cube-connected cycles, IEEE Transactions on Computers, v.34 n.8, p.769-772, Aug. 1985 [doi>10.1109/TC.1985.1676627]
	Cl	C. Clos (1959): A study of non-blocking switching networks, Bell Systera Techuical Journal 32, 406-424.
	FL	Michael R. Fellows , Michael A. Langston, Processor Utilization in a Linearly Connected Parallel Processing System, IEEE Transactions on Computers, v.37 n.5, p.594-603, May 1988 [doi>10.1109/12.4610]
	Go	D. Gorenstein (1968): Finite groups. Harper & Row.
	Gr	D. Greenberg (1990): Private communication.
	GP	W.H. Gates, C.H. Papadimitriou (1979): Bounds for sorting by prefix reversal. Disc. Math., No. 27, 47-57.
	Lu	A. Lubotzky, R.Phi}ips, P. Sarnak (1988): Ramanujan graphs. Combinatorica, 8, 261- 277.
	MVV	Ketan Mulmuley , Umesh V. Vazirani , Vijay V. Vazirani, Matching is as easy as matrix inversion, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.345-354, January 1987, New York, New York, United States [doi>10.1145/28395.383347]
	NS	D. Nassimi and S. Sahni (1982): Parallel algorithms to set up the Bene~ permutation network. IEEE Trans. on Comp. C-31 uo. 2. 148-154.
	PS	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	Ro	A.L. Ro~nbe~g (1988): The p~oa.~t-~hum~ network: toward reconcihng shuffles and butterflies. COINS Tech. Rp~. 8 8-10L
	Sl	D. Slepian (1952): Two theorems on a particulax crossbar switching network, unpublished manuscript.
	SS	Youcef Saad , Martin H. Schultz, Data communication in hypercubes, Journal of Parallel and Distributed Computing, v.6 n.1, p.115-135, February 1989 [doi>10.1006/jpdc.2000.1667]
	Tz	D. Tzvieli (1988): Minimal diameter doublering networks I: Some very large infinite optimal families. Typescript, Louisiana State Univ.
	Ul	3. D. Vllman (1983): Computational aspects of VLSI. Computer Science press.

CITED BY 13

	Christos Kaklamanis , Danny Krizanc , Satish Rao, Simple path selection for optimal routing on processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.23-30, June 29-July 01, 1992, San Diego, California, United States
	Bojana Obrenic, An approach to emulating separable graphs (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.159-167, July 21-24, 1991, Hilton Head, South Carolina, United States
	Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Direct routing on trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.342-349, January 25-27, 1998, San Francisco, California, United States
	Berthold Vöcking, Almost optimal permutation routing on hypercubes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.530-539, July 2001, Hersonissos, Greece
	Hisao Tamaki, Robust bounded-degree networks with small diameters, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.247-256, June 29-July 01, 1992, San Diego, California, United States
	Sebastian Egner , Markus Püschel , Thomas Beth, Decomposing a permutation into a conjugated tensor product, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.101-108, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	K. Coolsaet , V. Fack , H. De Meyer, A tabular method for verification of data exchange algorithms on networks of parallel processors, Nordic Journal of Computing, v.1 n.2, p.202-213, Summer 1994
	M. Herbordt , C. Weems , J. Corbett, Message-passing algorithms for a SIMD torus with coteries, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 02-06, 1990, Island of Crete, Greece
	Manfred Kunde, Balanced routing: towards the distance bound on grids, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.260-271, July 21-24, 1991, Hilton Head, South Carolina, United States
	Nader Bagherzadeh , Martin Dowd , Shahram Latifi, A Well-Behaved Enumeration of Star Graphs, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.531-535, May 1995
	Martin C. Herbordt , Charles C. Weems , James C. Corbett, Message-passing algorithms for a SIMD torus with coteries, ACM SIGARCH Computer Architecture News, v.19 n.1, p.69-78, March 1991
	Yasuto Suzuki , Keiichi Kaneko, The Container Problem in Bubble-Sort Graphs, IEICE - Transactions on Information and Systems, v.E91-D n.4, p.1003-1009, April 2008
	Kevin Chiew , Yingjiu Li, Multistage off-line permutation packet routing on a mesh: an approach with elementary mathematics, Journal of Computer Science and Technology, v.24 n.1, p.175-180, January 2009