This paper considers the problem of creating message-passing protocols for parallel computers. It is assumed that the processors are connected by a network that provides guaranteed delivery of every message, provided that each message delivered by the network is removed by the receiving processor unconditionally and in finite time. Two models of message passing are considered, namely, a selective model in which the receiver specifies the source of the message and a nonselective model in which the receiver accepts messages from all sources. We consider only space-efficient protocols in which each processor has storage for a constant number of messages and message headers. We present three main results. First, we give a protocol for the selective model that performs a constant amount of communication per send or receive posted by the application. Second, we prove that no such efficient protocol exists for the nonselective model. Third, we present a protocol for the nonselective model that performs a logarithmic amount of communication per send or receive posted by the application.

In this paper we present the Segment router, a novel router design for the interconnection networks of massively parallel computers. The design decisions of the Segment router are motivated by the need to improve the network performance when the traffic consists of messages with widely different lengths.

The Chaos router, a randomizing, nonminimal adaptive packet router is introduced. Adaptive routers allow messages to dynamically select paths, depending on network traffic, and bypass congested nodes. This flexibility contrasts with oblivious packet routers where the path of a packet is statically determined at the source node. A key advancement of the Chaos router over previous nonminimal routers is the use of randomization to eliminate the need for livelock protection. This simplifies adaptive routing to be of approximately the same complexity along the critical decision path as an oblivious router. The primary cost is that the Chaos router is probabilistically livelock free rather than being deterministically livelock free, but evidence is presented implying that these are equivalent in practice. The principal advantage is excellent performance for nonuniform traffic patterns. The Chaos router is described, it is shown to be deadlock free and probabilistically livelock free, and performance results are presented for a variety of work loads.>

This paper studies the behavior of scientific applications running on distributed memory parallel computers. Our goal is to quantify the floating point, memory, I/O and communication requirements of highly parallel scientific applications that perform explicit communication. In addition to quantifying these requirements for fixed problem sizes and numbers of processors, we develop analytical models for the effects of changing the problem size and the degree of parallelism for several of the applications. We use the results to evaluate the trade-offs in the design of multicomputer architectures.

Article Free Access Share on Bounds on the efficiency of message-passing protocols for parallel computers Authors: Robert Cypher IBM Almaden Research Center, San Jose, CA IBM Almaden Research Center, San Jose, CAView Profile , Smaragda Konstantinidou IBM Almaden Research Center, San Jose, CA IBM Almaden Research Center, San Jose, CAView Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 173–181https://doi.org/10.1145/165231.165253Published:01 August 1993Publication History 3citation202DownloadsMetricsTotal Citations3Total Downloads202Last 12 Months4Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Multistage interconnection networks (MINs) have been used extensively as communication networks in parallel machines due to their high bandwidth, low diameter and constant degree switches. The fault-tolerance of multistage networks can be improved by simply adding extra stages to the network. A novel method of attaching the extra stages in MINs so that they are used in the absence of faults but not necessarily by all messages is suggested. Messages can adaptively select the shortest path to their destination or use one of the longer paths going through the extra stages. Performance results for the method (obtained through simulation), using various traffic loads both in the presence and absence of faults, are presented.>

A novel method of attaching the extra stages in multistage interconnection networks (MINs) that allows for the bypassing of the extra stages is presented. Using a novel routing scheme, messages adaptively select to take the shortest path toward their destination or use one of the longer paths going through the extra stages. This results in significant performance improvement under many traffic patterns, including hot spots, as shown by simulation results.>

The Chaos router is an adaptive, randomized message router for multlicomputers.Aclaptive routers are superior to oblivious routers, the state-of-the-art, because they can by-pass congestion and faults.unlike other adaptive routers, however, the Chaos router has reduced the complexity along the critical path of the routing decision by using randomization to eliminate livelock protection, The foundational theory for Chaotic routing, proving that, this approach is sound, has been previously de~-eloped [1 1].In this paper we present, the complete design of the router together with (simulated) performance figures.The results show that, the Chaos t-outer is competitive with the simple and fast obli~ious routers for random loads and greatly superior for loads with hot spots. 1 Non-nliuimal, adaptive routers, as shown by our simulat ions, have the potential of outperforming minimal, adaptive routers, especially under non-uniform traffic.Their disad~ant,age though is their difficulty in guarant wing freedom from ltrc lock.L,6.guarantee that, no message will fail to be deli~"ered because it is repeatedly derout ed.The well known solution to this problem is priorit ~-routing, where messages are assigned a timestamp upon injection into the network.JYhen multiple messages require the same channel the oldest one is selected.Priority routing is known to be expensive, not only because it increases the message length in order to incorporate the timestamp, but, even more so because

We present the chaos router, an asynchronous adaptive router, which under certain circumstances can send messages farther from their destinations.The chaos router greatly simplifies the routing logic by removing the livelock protection of previous schemes.Through an effective use of randomness, whose sources include that due to the adaptively processed load, the natural timing differences of selftimed circuitry and explicitly injected randomization, the chaos router avoids long message routes with high probability.In this paper the router is described, it is argued that the chaos router is deadlock free and probabilistically livelock and starvation free, and simulation results are presented showing that the chaos router performs well.