Newsgroups: comp.parallel From: patel@cis.ohio-state.edu (kant c patel) Subject: Responses to Wormhole Routing Question Organization: The Ohio State University Dept. of Computer and Info. Science Date: 5 Apr 1994 17:24:00 GMT Hi, I had posted a query regarding some questions on wormhole routed machines, which somehow never appeared on comp.parallel. Anyway, I have received some responses to a similar posting on other newsgroup, and so I have attached the query and the responses below for those who are interested. Cheers, Kant. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ QUERY: ===== I am currently studying the effects of various parameters on wormhole routing in multiprocessor networks. These include, buffer size, injection/ consumption channels, number of simulataneous sends/receives, etc. I am looking for the typical values of these parameters on contemporary machines, like, the Intel Paragon, the CM-5, the Cray T3D, etc., esp. the following: 1. Assuming truly non-blocking sends/receives, how many sends/receives can be done simulataneously from a processor ? 2. What is the buffer size typically used by the communication processor, and by the router ? 3. What is the number of injection/consumption channels used between the router and the processor ? If you have any information, or anyone to whom you could direct me for more information, I would be very grateful to hear about it. If there is sufficient interest, I will summarize here. Thanks a lot in advance, Kant (patel@cis.ohio-state.edu) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ RESPONSES: ========= From: Steve Atkins You may be interested in the data available on the C104 wormhole router (used with the T9000 transputer amongst other things). It's available for anon-ftp on inmos.co.uk in /inmos/info/comms. There are datasheets and a postscript version of the book `Networks, routers and Transputers'. ============================================================================== From: A.D.Ben-Dyke@computer-science.birmingham.ac.uk ... suggestion is that you dig around the University of Texas ftp site (cs.utexas.edu) -- they've published several (many?) papers dealing with wormhole routing (including performance measurement) and may have some data that is close. ============================================================================== Newsgroups: comp.parallel From: dmg2@tower.york.ac.uk (DM Goodeve) Subject: Re: Papers on mesh routing. Organization: University of York, Computing Service, UK Date: 20 Apr 94 14:34:09 GMT Joaquin Guerra Achem (jguerra@csd4.csd.uwm.edu) wrote: : Hi I am looking for papers (references/ftp sites) about routing on : mesh connected processors. : Thanks! : Joaquin Guerra-Achem Try: @techreport{Ni:Wormhole91, title="{A Survey of Routing Techniques in Wormhole Networks}", author="Lionel M. Ni and Philip J. McKinley", institution="Department of Computer Science, Michigan State University", number="MSU-CPS-ACS-46", year="October 17, 1991" } and @article{Ni:Wormhole93, author="Lionel M. Ni and Philip K. McKinley", title="{A Survey of Wormhole Routing Techniques in Direct Networks}", journal="IEEE Computer", volume="26", number="2", pages="62--76", year="February 1993" } Cheers Don ---------------------------------------------------- | Don Goodeve (don@ohm.york.ac.uk) | | Parallel and Signal Processing Applications | | Research Group (PASPA) ------------------------ | | Department of Electronics| tel: (+44) 904 432381 || | University of York | fax: (+44) 904 432335 || | Y01 5DD UK ------------------------ | ---------------------------------------------------- ``You could of course call them threads... ...but then I would have to kill you.'' (D. Ritchie) -------------------------------------------------------------------- From: stjahn@corinth.cs.uni-magdeburg.de (Steffen Jahn) Newsgroups: comp.parallel Subject: Re: Wormhole Routing Date: 28 Dec 1995 04:01:36 GMT Organization: Univ. of Magdeburg, CS Dept, Germany Hi! Ken Graham (kgraham@ix.netcom.com) wrote: : I am looking for information relevent to the topic of wormhole routing : in parallel systems. In particular, if there are any published papers : which are publically available in electronic form. : ... : If you know of any references I would be most appreciative. I have : tried several of the Web search engines and mostly come up with Deep : Space Nine (and other SF references), so please don't suggest them : unless you have a specific reference on a less general topic. DS9 -> *laugh* ;) Because I'm also interested, I searched with the "Web Crawler" & (surprise, surprise) I got some references: http://calypso.unl.edu/%7Esunil/ http://sparc1.cse.uiuc.edu/ICPP95/ http://cbs.umn.edu/%7Epemeagwa/History_Supercomputing.htm http://www.tns.lcs.mit.edu/vs/vunet.html http://weber.u.washington.edu/~caberle/ >From the three lower references I got no information!? By the way, wormhole routing is supported by inmos C104 chips, perhaps you got some informations from the inmos page!? http://www.pact.srf.ac.uk/inmos/ Oops, page moved!? - Or perhaps unconnectable? Merry Christmas & happy new Year! Steffen Otto-von-Guericke University Magdeburg Department of Computer Science ---------------------------------------------------------------------- Newsgroups: comp.parallel From: swt@stone.mti.sgi.com (Steve W. Turner) Reply-To: swt@sgihub.corp.sgi.com (Stephen W. Turner) Subject: Re: Wormhole Routing Organization: Silicon Graphics, Inc. Date: 4 Jan 1996 01:29:46 GMT Message-ID: Ken Graham (kgraham@ix.netcom.com) wrote: > I am looking for information relevent to the topic of wormhole routing > in parallel systems. In particular, if there are any published papers > which are publically available in electronic form. I've got mixed emotions about helping out someone who seems disinclined to do the work themeselves, but here's a couple of pointers... For online sources, try the CS Tech report search engine at Indiana U. That's at http://www.cs.indiana.edu/cstr/ A search for "wormhole" turned up 19 matches, when I checked. In case you want to make the effort to physically visit a library, here are a few bibliographic refs: @Article{DaSe87, author = "William J. Dally and Charles L. Seitz", title = "Deadlock-free message routing in multiprocessor interconnection networks", journal = "IEEE Transactions on Computers", year = 1987, volume = "C-36", number = 5, pages = "547--553", month = "May" } @Article{DaAo93, author = "William J. Dally and Hiromichi Aoki", title = "Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels", journal = TPDS, year = 1993, volume = 4, number = 4, pages = "466--475", month = "Apr" } @InProceedings{NgSe89, author = "John Y. Ngai and Charles L. Seitz", title = "A Framework for Adaptive Routing in Multicomputer Networks", pages = "1--9", booktitle = SPAA, year = 1989, annote = "father of virtual channels. demonstrates max potential gain for uniform traffic is factor of 2. proof of deadlock freedom for wormhole-routed nets" } @InProceedings{BaPa93, author = "Shobana Balakrishnan and Dhabaleswar K. Panda", title = "Impact of Multiple Consumption Channels on Wormhole Routed {\em k\/}-ary {\em n\/}-cube Networks", booktitle = "7th International Parallel Processing Symposium", year = 1993, editor = "IEEE", pages = "163--167" } @TechReport{BaPa93a, author = "Debashis Basak and Dhabaleswar K. Panda", title = "Designing Scalable Systems with two-level {\it k\/}-ary {\it n\/}-cube Wormhole-routed Interconnections", institution = "Department of Computer and Information Science, Ohio State University", year = 1993, number = "OSU-CISRC-8/93-TR29", address = "Columbus, OH 43210-1277", month = "Aug", annote = "Clusters, analysis (w/simulations)" } @InProceedings{FGPS91, author = "S.A. Felperin and L. Gravano and G.D. Pifarr\'{e} and J.L.C. Sanz", title = "Fully-Adaptive Routing: Packet Switching Performance and Wormhole Algorithms", booktitle = "Supercomputing", year = 1991, pages = "654--663" } @InProceedings{ChEn90b, author = "Suresh Chittor and Richard Enbody", title = "Performance Evaluation of Mesh-Connected Wormhole-Routed Networks for Interprocessor Communication in Multicomputers", pages = "647--656", booktitle = "Proceedings of Supercomputing '90", year = 1990 } @InProceedings{Chien93, author = "Andrew A. Chien", title = "A Cost and Speed Model for K-ary n-cube Wormhole Routers", booktitle = "Hot Interconnects '93", year = 1993 } @InProceedings{RaEa94, author = "Swaminathan Ramany and Derek Eager", title = "The Interaction between Virtual Channel Flow Control and Adaptive Routing in Wormhole Networks", booktitle = "International Conference on Supercomputing", year = 1994, pages = "136--145", month = "July", annote = "Shows that adaptivity can hurt if few virtual channels are used and traffic is high. Claims that adaptivity needs many virtual channels to work well, and virtual channels need adaptivity to work well" } @Article{LiHa91, author = "D. H. Linder and J. C. Harden", title = "An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes", journal = TOC, year = 1991, volume = "C-40", number = 1, pages = "2--12", month = "Jan", annote = "Proposed 'double-y' adaptive scheme for 2D meshes: route in x, then on y or y'" } @TechReport{NiMc91, author = "Lionel M. Ni and Philip K. McKinley", title = "A Survey of Routing Techniques in Wormhole Networks", institution = "Michigan State University", year = 1991, number = "MSU-CPS-ACS-46", address = "East Lansing, MI 48824-1027", month = "Oct", OPTannote = "Lays foundation for turn-model, defines terms." } @InProceedings{LMN93, author = "Xiaola Lin and Philip K. McKinley and Lionel M. Ni", title = "The Message Flow Model for Routing in Wormhole-Routed Networks", booktitle = ICPP, year = 1993, volume = "I", pages = "294--297", annote = "Framework for proving deadlock freedom, similar in tone, but different in approach from Ngai and Seitz. Use to extend 'double-y' routing in very similar fasion to the way the 'turn model' does", }