The Experts below are selected from a list of 8847 Experts worldwide ranked by ideXlab platform
Philip K Mckinley - One of the best experts on this subject based on the ideXlab platform.
-
deadlock free multicast wormhole routing in 2 d mesh Multicomputers
IEEE Transactions on Parallel and Distributed Systems, 1994Co-Authors: Xiaola Lin, Philip K MckinleyAbstract:Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation Multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh Multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms. >
Xiaola Lin - One of the best experts on this subject based on the ideXlab platform.
-
deadlock free multicast wormhole routing in 2 d mesh Multicomputers
IEEE Transactions on Parallel and Distributed Systems, 1994Co-Authors: Xiaola Lin, Philip K MckinleyAbstract:Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation Multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh Multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms. >
-
ISCA - Deadlock-free multicast wormhole routing in multicomputer networks
Proceedings of the 18th annual international symposium on Computer architecture - ISCA '91, 1991Co-Authors: Xiaola LinAbstract:Efficient routing of messages is the key to the performance of Multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. Wormhole routing is the most promising switching technique used in new generation Multicomputers. In this paper, we present multicast wormhole routing methods for Multicomputers adopting 2D-mesh and hypercube topologies. The dual-path routing algorithm requires less system resource, while the multipath routing algorithm creates less traffic. More import antly, both routing algorithms are deadlock-free, which is essential to wormhole networks.
Matthias A Blumrich - One of the best experts on this subject based on the ideXlab platform.
-
Network interface for protected, user-level communication
1996Co-Authors: Matthias A BlumrichAbstract:Scalable parallel architectures are converging on the general framework of a distributed memory parallel processor (DMPP), consisting of a group of interconnected compute nodes, each typically consisting of a CPU, some memory, and a network interface. DMPP architectures range from tightly-coupled Multicomputers to loosely-coupled networks of personal computers (PCs), and support a number of parallel programming paradigms including shared-memory and message-passing. Networks of PCs are very attractive DMPPs because of the high performance and low cost of the PC nodes. Custom-built Multicomputers have one principal advantage over networks of PCs: they are faster. The major reason for this advantage is a gap in communication performance between multicomputer interconnects and local area networks. Recent networking trends have seen a migration of technology from Multicomputers to networks of PCs, shrinking this communication performance gap considerably. However, software overhead--largely attributable to local area network interfaces--continues to maintain the performance gap. This dissertation describes how network interfaces can bridge the gap by providing appropriate support for protected, user-level communication with extremely low software overhead. Such network interfaces can be used to build scalable, high-performance, really inexpensive multiprocessors out of low-cost, commodity components. This assertion is demonstrated via a working implementation of a prototype SHRIMP network of PCs. The prototype achieves data transfer latency competitive with custom Multicomputers, and efficient use of bandwidth down to small message sizes. In addition, SHRIMP supports general multiprogramming, extending its benefits from uniprocessors to multiprocessors. The key to SHRIMP performance is virtual memory-mapped communication, which strips away overhead from time-critical data transfer operations without sacrificing all the services that systems have come to depend on. Equipped with virtual memory-mapped communication, networks of PCs could very well become commodity scalable systems.
-
virtual memory mapped network interfaces
IEEE Micro, 1995Co-Authors: Matthias A Blumrich, Cezary Dubnicki, Kai Li, Edward W. Felten, Malena MesarinaAbstract:In today's Multicomputers, software overhead dominates the message-passing latency cost. We designed two multicomputer network interfaces that significantly reduce this overhead. Both support virtual-memory-mapped communication, allowing user processes to communicate without expensive buffer management and without making system calls across the protection boundary separating user processes from the operating system kernel. Here we compare the two interfaces and discuss the performance trade-offs between them. >
-
virtual memory mapped network interface for the shrimp multicomputer
International Symposium on Computer Architecture, 1994Co-Authors: Matthias A Blumrich, Richard D Alpert, Cezary Dubnicki, Kai Li, Edward W. Felten, Jonathan SandbergAbstract:The network interfaces of existing Multicomputers require a significant amount of software overhead to provide protection and to implement message passing protocols. This paper describes the design of a low-latency, high-bandwidth, virtual memory-mapped network interface for the SHRIMP multicomputer project at Princeton University. Without sacrificing protection, the network interface achieves low latency by using virtual memory mapping and write-latency hiding techniques, and obtains high bandwidth by providing a user-level block data transfer mechanism. We have implemented several message passing primitives in an experimental environment, demonstrating that our approach can reduce the message passing overhead to a few user-level instructions.
-
two virtual memory mapped network interface designs
High Performance Interconnects, 1994Co-Authors: Matthias A Blumrich, C Dubnickil, Kai Li, Edward W. Felten, Malena MesarinaAbstract:In existing Multicomputers, software overhead dom inates the message-passing latency cost. Our research on the SHRIMP project at Princeton indicates that appropriate network interface support can significantly reduce this software overhead. We have designed two network interfaces for the SHRIMP multicomputer. Both support virtual memory mapped communication allowing user processes to communicate without doing expensive buffer management, and without using sys tem calls to cross the protection boundary separating user processes from the operating system kernel. This paper describes and compares the two network in terfaces, and discusses performance tradeoffs between them.
Jonathan Sandberg - One of the best experts on this subject based on the ideXlab platform.
-
virtual memory mapped network interface for the shrimp multicomputer
International Symposium on Computer Architecture, 1994Co-Authors: Matthias A Blumrich, Richard D Alpert, Cezary Dubnicki, Kai Li, Edward W. Felten, Jonathan SandbergAbstract:The network interfaces of existing Multicomputers require a significant amount of software overhead to provide protection and to implement message passing protocols. This paper describes the design of a low-latency, high-bandwidth, virtual memory-mapped network interface for the SHRIMP multicomputer project at Princeton University. Without sacrificing protection, the network interface achieves low latency by using virtual memory mapping and write-latency hiding techniques, and obtains high bandwidth by providing a user-level block data transfer mechanism. We have implemented several message passing primitives in an experimental environment, demonstrating that our approach can reduce the message passing overhead to a few user-level instructions.
Shengjian Wang - One of the best experts on this subject based on the ideXlab platform.
-
IV - Efficient Multicast Algorithms for Mesh-connected Multicomputers
Tenth International Conference on Information Visualisation (IV'06), 1Co-Authors: H.a. Harutyunyan, Shengjian WangAbstract:Performance of Multicomputers largely depends on that of the underlying network communications such as multicast. Two major parameters used to evaluate multicast routing are the time it takes to deliver the message to all destinations and the traffic which refers to the total number of links involved. Mesh is a network topology widely used in Multicomputers. It has been proved that, in mesh network, it is NP-hard to find the multicast routing which is optimal on both time and traffic. In this paper, we proposed two efficient multicast algorithms designed for store-and-forward switched mesh-connected Multicomputers: DIAG and DDS. They are both tree-based shortest path multicast algorithms whose complexity is O(KN) or less. Performance evaluations of these algorithms resulted from simulations are given at the end.
