Methods for message routing in parallel machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Methods for message routing in parallel machines

Full text

Pdf (2.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 77 - 96

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Tom Leighton

Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 30, Citation Count: 24

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/129712.129721 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.

	1	F. Abolhassan, J. Keller, and W. Paul. On the cost-effectiveness and realization of the theoretical PRAM model. Technical Report 09/1991, FB Informatik, Universitgt des Saarlandes, 1991.
	2	A. Aggarwal , A. K. Chandra , M. Snir, On communication latency in PRAM computations, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.11-21, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72937]
	3	Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
	4	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	5	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	6	G. S. Almasi , A. Gottlieb, Highly parallel computing, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
	7	B. Alpern, L. Carter, E. Feig, and T. Selker. A uniform memory hierarchy model of computation. Technical report, IBM Watson, December 1990.
	8	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
	9	Y. Aumann and A. Schuster. Deterministic PRAM simulation with constant memory blow-up and no time-stamps. In Third Symposium on the Frontiers of Massively Parallel Computation, pages 22- 29, 1990.
	10	L.A. Bassalygo and M.S. Pinsker. Complexity of an optimum non-blocking switching network without reconnections. Problems of information Transmission, 9:64-66, 1974.
	11	V. Beneg. Permutation groups, complexes, and rearrangeable multistage connecting networks. Bell System Technical Journal, 43:1619-1640, July 1964.
	12	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	13	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	14	A. Chin. Practical issues in parallel complezity. PhD thesis, U. Oxford, England, November 1991.
	15	F. Chong, E. Egozy, and A. DeHon. Fault tolerance and performance of multipath multistage intereonneetion networks. In T.F. Knight, Jr. and j. Savage, editors, Advanced research in VLSI and Parallel Systems 1992. MIT Press, March 1992. To appear.
	16	Frederic T. Chong and Thomas Knight, Jr. Design and performance of multipath MIN architectures. Technical Report 64, MIT Artificial intelligence Laboratory, February 1992.
	17	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72954]
	18	R. Cole , O. Zajicek, The expected advantage of asynchrony, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.85-94, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97673]
	19	William Dally, Network and processor architecture for message-driven computers, VLSI and parallel computation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	20	William J. Dally, Express Cubes: Improving the Performance of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.40 n.9, p.1016-1023, September 1991 [doi>10.1109/12.83652]
	21	W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
	22	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	23	A. DeHon, T. Knight, Jr., and H. Minsky. Faulttolerant design for multistage routing networks. in Proceedings of the International Symposium on Shared Memory Multiprocessing. Information Processing Society of Japan, April 1991.
	24	Andr# DeHon. Mbta: Modular bootstrapping transit architecture. Technical Report 17, MIT Artificial Intelligence Laboratory, April 1990.
	25	F. Fich. The complexity of computing on a parallel random access machine. In John Reif, editor, Synthesis of Parallel Algorithms. Morgan Kaufman Publishers, San Mateo, CA, 1992. To Appear.
	26	F. Fich, R. Impagliazzo, B. Kapron, V. King, and M. Kutylowski. Limits on the power of PRAMs with weak forms of write conflict resolution. Unpublished manuscript, 1992.
	27	Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
	28	Phillip Baldwin Gibbons , Richard M. Karp, The asynchronous pram: a semisynchronous model for shared-memory mimd machines, 1989
	29	A. Gottlieb. An overview of the NYU ultracomputer project. In J. Dongarra, editor, Experimental Computing Architecture, pages 25-95. Elsevier, Amsterdam, 1987.
	30	Ronald I. Greenberg. E}ficient Interconnection Schemes for VLS1 and Parallel Computation. PhD thesis, MIT, September 1989.
	31	Ronald i. Greenberg and Charles E. Leiserson. Randomized routing on fat-trees. Advances in Computing Research, 5:345-374, 1989.
	32	Torben Hagerup , T. Radzik, Every robust CRCW PRAM can efficiently simulate a PRIORITY PRAM, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.117-124, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97677]
	33	J. Hastad , T. Leighton, Fast computation using faulty hypercubes, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.251-263, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73031]
	34	David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	35	A. Huang and S. Knauer. Starlite: a wideband digital switch. In Proc. GLOBECOMS#, pages 121- 125, December 1984.
	36	Nabil Kahale, Better expansion for Ramanujan graphs, Proceedings of the 32nd annual symposium on Foundations of computer science, p.398-404, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185397]
	37	C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
	38	A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching. Algorithmica, 3:79- 119, 1988.
	39	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
	40	R. Karp. Parallel combinatorial computing. In Jill P. Mesirov, editor, Very Large Scale Computation in the 21st Century, pages 221-238, Philadelphia, PA, 1991. SIAM Press.
	41	P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. In Proc. 31st FOCS, pages 726-737, 1990.
	42	R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In P9th Annual Symposium on Foundations of Computer Science, pages 221- 230. IEEE, October 1988.
	43	R. Koch. An Analysis of the Performance of Interconnection Networks for Mnltiprocessor Systems. PhD thesis, MIT, May 1989.
	44	S. Konstantinidou and E. Upfal. Experimental comparison of multistage networks. Technical report, IBM Almaden Research Center, 1991.
	45	C. Kruskal and M. Snir. The performance of multistage interconnection networks for multiprocessors. IEEE Transactions on Computers, C-32(12):1091- 1098, December 1983.
	46	C. P. Kruskal , M. Snir, A Unified theory of interconnection network structure, Theoretical Computer Science, v.48 n.1, p.75-94, Dec., 1986
	47	M. Kunde, Routing and sorting on mesh-connected arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	48	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	49	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	50	F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
	51	T. Leighton, C.L. Leiserson, and M. Klugerman. Theory of parallel and VLSI computation. Research Seminar Series Report MIT/LCS/RSS10, MIT Laboratory for Computer Science, May 1991.
	52	T. Leighton, D. Lisinski, and B. Maggs. Empirical evaluation of randomly-wired multistage networks. In Proceedings of the 1990 IEEE International Conference on Computer Design, pages 380- 385. IEEE, September 1990.
	53	T. Leighton and B. Maggs. Expanders might be practical" Fast algorithms for routing around faults in multibutterflies. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 384-389. IEEE, October 1989.
	54	F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992 [doi>10.1109/12.142684]
	55	T. Leighton and B. Maggs. Introduction to Parallel Algorithms and Architectures: Expanders, PRAMs and VLSI. Morgan Kaufman Publishers, San Mateo, CA, 1993. To appear.
	56	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	57	T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 256-271. IEEE, October 1988.
	58	T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29 th Annual Symposium on Foundations of Computer Science, pages 422-431. IEEE, October 1988.
	59	Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , W. Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong-Chan , Shaw-Wen Yang , Robert Zak, The network architecture of the connection machine CM-5, Journal of Parallel and Distributed Computing, v.33 n.2, p.145-158, March 15, 1996 [doi>10.1006/jpdc.1996.0033]
	60	Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
	61	Charles E. Leiserson. VLSI theory and parallel supercomputing, in Richard F. Rashid, editor, Carnegie Mellon University School of Computer Science 25th Anniversery Symposium, pages 29-44. Addison-Wesley, 1991.
	62	Charles E. Leiserson and Bruce M. Maggs. Communication-efficient parallel algorithms for distributed random-access machines. Algorithmica, 3:53-77, 1988.
	63	H. Li and Q. Stout. Reconfigurable SIMD massively parallel computers. In Proc. 1EEE, volume 79, pages 429-443, 1991.
	64	A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.
	65	Y.-D. Lyuu, Fast-fault-tolerant parallel communication and on-line maintenance using information dispersal, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.378-387, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97705]
	66	Yuh-Dauh Lyuu , Michael O. Rabin, An information dispersal approach to issues in parallel processing, 1990
	67	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129728]
	68	Henry Minsky, Andr# DeHon, and Thomas F. Knight, Jr. RNI" Low-latency, dilated, crossbar router. In Hot Chips Symposium 111, 1991.
	69	D. Nassimi and S. Sahni. A self-routing Bene# network and parallel permutation algorithms. IEEE Transactions on Computers, C-30(5):332- 340, May 1981.
	70	J. Y. Ngai , C. L. Setiz, A framework for adaptive routing in multicomputer networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.1-9, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72936]
	71	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97672]
	72	N. Pippenger. Telephone switching networks. In Proc. of AMS Symposia in Applied Mathematics, volume 26, pages 101-133, 1982.
	73	N. Pippenger. Parallel communication with limited buffers. In #5th Annual Symposium on Foundations of Computer Science, pages 127-136. IEEE, October 1984.
	74	Nicholas Pippenger, Communication networks, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	75	Dick Pountain, The transputer strikes back, BYTE, v.16 n.8, p.265-ff., Aug. 1991
	76	F. Preparata. Holographic dispersal and recovery of information. IEEE Trans. Information Theory, IT-35(5):1123-1124, September 1989.
	77	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	78	A. Ranade. How to emulate shared memory, in #8th Annual Symposium on Foundations of Computer Science, pages 185-194. IEEE, October 1987.
	79	Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
	80	Abhiram G. Ranade , Sandeep N. Bhatt , Lennart S. Johnsson, The fluent abstract machine, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.71-93, January 1988, Cambridge, Massachusetts, United States
	81	Randall D. Rettberg , William R. Crowther , Philip P. Carvey , Raymond S. Tomlinson, The Monarch Parallel Processor Hardware Design, Computer, v.23 n.4, p.18-28, 30, April 1990 [doi>10.1109/2.55467]
	82	B. Smith. A massively parallel shared memory machine. In 3rd ACM SPAA, 1991. Invited lecture.
	83	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	84	F. Tobagi. Fast packet switch architectures for broadband integrated services digital networks. In Proc. IEEE, volume 78, pages 133-167, January 1990.
	85	T. Tsantilas. A refined analysis of the Valiant- Brebner algorithm. Technical Report TR-22-89, Center for Research in Computing Technology, Harvard University, 1989.
	86	Eli Upfal, Efficient schemes for parallel communication, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.55-59, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806682]
	87	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
	88	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	89	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	90	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	91	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

CITED BY 24

	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
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States
	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Micah Adler , Sanjeev Khanna , Rajmohan Rajaraman , Adi Rosén, Time-constrained scheduling of weighted packets on trees and meshes, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 27-30, 1999, Saint Malo, France
	Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States
	Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States
	Suprakash Datta , Ramesh Sitaraman, The performance of simple routing algorithms that drop packets, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.159-169, June 23-25, 1997, Newport, Rhode Island, United States
	Richard J. Cole , Bruce M. Maggs , Ramesh K. Sitaraman, On the benefit of supporting virtual channels in wormhole routers, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.131-141, June 24-26, 1996, Padua, Italy
	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany
	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States
	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Ville Leppänen , Martti Penttonen, Work-optimal simulation of PRAM models on meshes, Nordic Journal of Computing, v.2 n.1, p.51-69, March 1995
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	N. Alon , F. R. K. Chung , R. L. Graham, Routing permutations on graphs via matchings, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.583-591, May 16-18, 1993, San Diego, California, United States
	Louxin Zhang, Optimal bounds for matching routing on trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.445-453, January 05-07, 1997, New Orleans, Louisiana, United States
	Alan Roberts , Antonios Symvonis, A General Method for Deflection Worm Routing on Meshes Based on Packet Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.781-789, August 1997
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	William Aiello , Rafail Ostrovsky , Eyal Kushilevitz , Adi Rosén, Dynamic routing on networks with fixed-size buffers, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Rachid Saad, An optimal schedule for Gaussian elimination on an MIMD architecture, Journal of Computational and Applied Mathematics, v.185 n.1, p.91-106, 1 January 2006
	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States