Performance analysis of mesh interconnection networks with deterministic routing
IEEE Transactions on Parallel and Distributed SystemsPublished 1 March 1994
Vikram Adve, M.K. Vernon
Citations137
SJR quartileQ1
SJR score2.10
SNIP2.28
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Detailed analytical performance models for k-ary n-cube networks with single-hit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz (1987) are developed.
Abstract
This paper develops detailed analytical performance models for k-ary n-cube networks with single-hit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz (1987). In contrast to previous performance studies of such networks, the system is modeled as a closed queueing network that: includes the effects of blocking and pipelining of messages in the network; allows for arbitrary source-destination probability distributions; and explicitly models the virtual channels used in the deadlock-free routing algorithm. The models are used to examine several performance issues for 2-D networks with shared-memory traffic. These results should prove useful for engineering high-performance systems based on low-dimensional k-ary n-cube networks.>
Keywords
Computer ScienceMaterials Science
IEEE Transactions on ComputersDeadlock-Free Message Routing in Multiprocessor Interconnection Networks
2,037 Citations1987Dally, Seitz
A deadlock-free routing algorithm can be generated for arbitrary interconnection networks using the concept of virtual channels, which is used to develop deadlocked routing algorithms for k-ary n-cubes, for cube-connected cycles, and for shuffle-exchange networks.
ComputerThe Stanford Dash multiprocessor
972 Citations1992Daniel Lenoski, James Laudon +6 more
The overall goals and major features of the directory architecture for shared memory (Dash), a distributed directory-based protocol that provides cache coherence without compromising scalability, are presented.
Computer Networks (1976)Virtual cut-through: A new computer communication switching technique
884 Citations1979Parviz Kermani, Leonard Kleinrock
The analysis shows that cut-through switching is superior (and at worst identical) to message switching with respect to the above three performance measures.
IEEE Transactions on ComputersPerformance analysis of k-ary n-cube interconnection networks
881 Citations1990William J. Dally
Expressions for the latency, average case throughput, and hot-spot throughput of k-ary n-cube networks with constant bisection that agree closely with experimental measurements are derived and it is shown that low-dimensional networks (e.g. tori) have lower latency and higher hot- spot throughput than high-dimensional Networks with the same bisection width.
IEEE Transactions on Computers“Hot spot” contention and combining in multistage interconnection networks
632 Citations1985Gregory F. Pfister, Vic Norton
The technique of message combining was found to be an effective means of eliminating this problem if it arises due to lock or synchronization contention, severely degrading all memory access, not just access to shared lock locations, due to an effect the authors call tree saturation.
IEEE Transactions on Parallel and Distributed SystemsLimits on interconnection network performance
445 Citations1991Anant Agarwal
A simple closed-form expression for contention in buffered, direct networks is derived and found to agree closely with simulations, and it is shown that a much larger fraction of the resulting performance improvement arises from the reduction in bandwidth requirements than from the decrease in latency.
iWarp: an integrated solution to high-speed parallel computing
316 Citations1988Shekhar Borkar, Robert Cohn +13 more
IEEE Transactions on ComputersDistributing Hot-Spot Addressing in Large-Scale Multiprocessors
271 Citations1987Pen-Chung Yew, Nian-Feng Tzeng +1 more
It is shown in [6] that even if only a small percentage of all requests are to a hot-spot, these requests can cause very serious performances problems, and networks that do the necessary combining of requests are suggested to keep the interconnection network and memory contention from becoming a bottleneck.
The J-machine multicomputer
235 Citations1993M.D. Noakes, Deborah A. Wallach +1 more
The design of the J-Machine is discussed and the effectiveness of the mechanisms incorporated into the MDP are evaluated to measure the performance of the communication and synchronization mechanisms directly and investigate the behavior of four complete applications.
Communications of the ACMLinearizer
209 Citations1982K. Mani Chandy, Doug Neuse
A new algorithm is presented for the approximate analysis of closed, product-form queueing networks with single-server and delay (infinite-server) queues that has the accuracy, speed, small memory requirements, and simplicity necessary for inclusion in a general network analysis package.
iWarp: an integrated solution to high-speed parallel computing
196 Citations2003Shekhar Borkar, Robert Cohn +13 more
Because of their strong computation and communication capabilities, the iWarp components provide a versatile building block for high-performance parallel systems ranging from special-purpose systolic arrays to general-purpose distributed memory computers.
Microprocessors and MicrosystemsA VLSI architecture for concurrent data structures
182 Citations1988William J. Dally
CERN Document Server (European Organization for Nuclear Research)High-performance computer architecture
180 Citations1987Harold S. Stone
Stone develops a proper understanding of the design process by treating the various trade-offs that exist in designing choices, and shows how good designs make efficient use of technology.
Limits on interconnection network performance
156 Citations1994Anant Agarwal
Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: preliminary results
150 Citations1989W.-D. Weber, Aman Gupta
The extent to which multiple hardware contexts per processor can help to mitigate the negative effects of high latency is explored and it is shown that two or four contexts can achieve substantial performance gains over a single context.
Kluwer international series in engineering and computer scienceA VLSI Architecture for Concurrent Data Structures
121 Citations1987William J. Dally
APRIL: a processor architecture for multiprocessing
116 Citations2002Anant Agarwal, Beng-Hong Lim +2 more
The J-machine Multicomputer: An Architectural Evaluation
96 Citations2005M.D. Noakes, Deborah A. Wallach +1 more
ACM SIGARCH Computer Architecture NewsAn accurate and efficient performance analysis technique for multiprocessor snooping cache-consistency protocols
71 Citations1988M.K. Vernon, Edward D. Lazowska +1 more
Performance analysis of finite-buffered multistage interconnection networks with a general traffic pattern
49 Citations1991Tiras Y. Lin, Leonard Kleinrock
An analytical model for evaluating the performance of finite-buffered packet switching multistage interconnection networks using blocking switches under any general traffic pattern is presented and compared with simulation indicates that the analytical model is very accurate.
IEEE Transactions on ComputersThe case for chaotic adaptive routing
46 Citations1997Kevin Bolding, Melanie L. Fulgham +1 more
A detailed head-to-head comparison between oblivious, minimal adaptive, and chaotic routing is presented, exploring the performance of comparable VLSI implementations through analysis and simulation and indicating that chaotic routers provide very effective and efficient high-performance message routing.
Exploring The Benefits Of Multiple Hardware Contexts In A Multiprocessor Architecture: Preliminary Results
39 Citations2005W.-D. Weber, Aman Gupta
An analytic model of multistage interconnection networks
39 Citations1990Darryl L. Willick, Derek L. Eager
This paper is concerned with evaluating the performance of multistage interconnection networks consisting of k × s switching elements, and considers clocked, packet switched networks with buffers at switch output ports.
IEEE Transactions on ComputersA unifying framework for the approximate solution of closed multiclass queuing networks
36 Citations2002Paolo Cremonesi, Paul J. Schweitzer +1 more
An interpolation-matching framework is proposed that allows a unified view of approximate solution techniques for closed product-form queuing networks and a new approximation technique is obtained, based on a third-order polynomial, that is shown to be more accurate than other known methods.
An accurate and efficient performance analysis technique for multiprocessor snooping cache-consistency protocols
36 Citations1988M.K. Vernon, Edward D. Lazowska +1 more
A family of dynamic cache-consistency-protocols for shared-bus multiprocessor systems is considered, and a modeling approach, based on the specification and the iterative solution of sets of equations that express the mean values of interesting performance measures in terms of themean values of certain model inputs, is presented.
IEEE Computer Society Press eBooksThe effectiveness of combining in shared memory parallel computers in the presence of “hot spots”
36 Citations1994Gyungho Lee, Clyde P. Kruskal +1 more
Performance analysis of the connection machine
5 Citations1990Erol Gelenbe
A queueing model of the network architecture, including the NEWS and ROUTER networks, is used to compute the slow-down induced by message exchange between processors.