{'fraction_non_alphanumeric': 0.022235986373490245, 'fraction_numerical': 0.006379684112728399, 'mean_word_length': 4.85299981874207, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The design of nectar: a network backplane for heterogeneous multicomputers

Nectar is a “network backplane” for use in heterogeneous multicomputers. The initial system consists of a star-shaped fiber-optic network with an aggregate bandwidth of 1.6 gigabits/second and a switching latency of 700 nanoseconds. The system can be scaled up by connecting hundreds of these networks together.
The Nectar architecture provides a flexible way to handle heterogeneity and task-level parallelism. A wide variety of machines can be connected as Nectar nodes and the Nectar system software allows applications to communicate at a high level. Protocol processing is off-loaded to powerful communication processors so that nodes do not have to support a suite of network protocols.
We have designed and built a prototype Nectar system that has been operational since November 1988. This paper presents the motivation and goals for Nectar and describes its hardware and software. The presentation emphasizes how the goals influenced the design decisions and led to the novel aspects of Nectar.


Introduction
The structure of these parallel applications requires communication among different tasks, both "horizontally" (among tasks operating at the same level of representation) and "vertically" (between levels). The lower levels in particular require a high data rate (megabyte images at video rates, for example).

Moreover, applications often have response-time requirements that can only be satisfied by low-latency communication; two examples are continuous speech recognition and the control of autonomous vehicles.
In general, by providing low-latency, high-bandwidth communication the system can rapidly distribute computations to multiple processors. This allows the efficient parallel implementation of many applications.
Lowering latency is much more challenging than increasing bandwidth, since the latter can always be achieved by using pipelined architectures with wide data paths and high-bandwidth communication media such as fiber-optic lines. Latency can be particularly difficult to minimize in a large system where multihop communication is necessary. Nectar has the following performance goals for communication latency: excluding the transmission delays of the optical fibers, the latency for a message sent between processes on two CABs should be under 30 microseconds; the corresponding latency for processes residing in nodes should be under 100 microseconds; and the latency to establish a connection through a single HUB should be under 1 microsecond.  To build larger systems, multiple HUBs are needed. In such systems, some of the I/O ports on each HUB are used for inter-HUB fiber connections, as shown in Figure 3. The HUB clusters may be connected in any topology appropriate to the application environment. Since the I/O ports used for HUB-HUB and for CAB-HUB connections are identical, there is no a priori restriction on how many links can be used for inter-HUB connections. Figure 4 depicts a multi-HUB system using a 2-dimensional mesh to connect its clusters.
The Nectar-net offers at least an order of magnitude improvement in bandwidth and latency over current LANs. Moreover, the use of crossbar switches substantially reduces network contention. Moderate-size, high-speed crossbars (with setup latency under one microsecond) arc now practical; 8-bit wide 32 x 32 crossbars can be built with off-the-shelf parts, and 128 x 128 crossbars are possible with custom VLSI.
Re-engineering the software in the critical path of communication is as important for achieving low latency as building fast network hardware. Typical profiles of networking implementations on UNIX 2 show that the time spent in the software dominates the time spent on the wire [3,5,11].
There are three main sources of inefficiency in current networking implementations. First, existing application interfaces incur excessive costs due to context switching and data copying between the user process and the node operating system. Second, the node must incur the overhead of higher-level protocols that ensure reliable communications for applications. Third, the network interface burdens the node with interrupt handling and header processing for each packet.
The Nectar software architecture alleviates these problems by restructuring the way applications communicate. User processes have direct access to a high-level network interface mapped into their address spaces. Communication overhead on the node is substantially reduced for three reasons. First, no system calls arc required during communication. Second, protocol processing is off-loaded to the CAB. Third, interrupts are required only for high-level events in which the application is interested, such as delivery of complete messages, rather than low-level events such as the arrival of control packets or timer expiration. 2

Prototype Implementation
We have built a prototype Nectar system to carry out extensive systems and applications experiments. The system includes three board types: CAB, HUB I/O board, and HUB backplane. As of early 1989 the prototype consists of 2 HUBs and 4 CABs. The system will be expanded to about 30 CABs in Spring 1989.
In the prototype, a node can be any system running UNIX or Mach [12] with a VME interface. The initial Nectar system at Carnegie Mellon will have Sun-3s, Sun-4s and Warp systems as nodes.
To speed up hardware construction, the prototype uses only off-the-shelf parts and 16 x 16 crossbars. The serial to parallel conversion is performed by a pair of TAXI chips manufactured by Advanced Micro Devices. The effective bandwidth per fiber line is 100 megabits/second, a limit imposed by the TAXI chips.
When the prototype has demonstrated that the Nectar architecture and software works well for applications, we plan to re-implement the system in custom or semi-custom VLSI. This will lead to larger systems with higher performance and lower cost. 4 The HUB The Nectar HUB establishes connections and passes messages between its input and output fiber lines. There are four design goals for the HUB: 1. Low latency. The HUB provides custom hardware to minimize latency. In the prototype system, the latency to set up a connection and transfer the first byte of a packet through a single HUB is ten cycles (700 nanoseconds). Once a connection has been established, the latency to transfer a byte is five cycles (350 nanoseconds), but the transfer of multiple bytes is pipelined to match the 100 megabits/second peak bandwidth of the fibers.

2.
High switching rate. In the prototype Nectar system, the HUB central controller can set up a new connection through the crossbar switch every 70 nanosecond cycle.

Efficient support for multi-HUB systems. Because of the low switching and transfer latency of a single HUB, the latency of process to process communication in a multi-HUB system is not significantly higher. Flow control for inter-HUB communication is implemented in hardware (see Section 4.2.3).
4. Flexibility and high efficiency. The HUB hardware implements a set of simple commands for the most frequently used operations such as opening and closing connections. These commands can be executed in one cycle by the central HUB controller. By sending different combinations of these simple commands to the HUB, CABs can implement more complicated datalink protocols such as multicast and multi-HUB connections. The HUB hardware is flexible enough to implement point-to-point and multicast connections using either circuit or packet switching. In addition, HUB commands can be used to implement various network management functions such as testing, reconfiguration, and recovery from hardware failures.

HUB Overview
The HUB has a number of I/O ports, each capable of connecting to a CAB or a HUB via a pair of fiber lines. The I/O port contains circuitry for optical to electrical and electrical to optical conversion. From the functional viewpoint, a port consists of an input queue and an output register as depicted in Figure 5.

Figure 5: HUB overview
The HUB has a crossbar switch, which can connect the input queue of a port to the output register of any other port (see Figure 7). An input queue can be connected to multiple output registers (for multicast), but only one input queue can be connected to an output register at a time. A status table is used to keep track of existing connections and to ensure that no new connections are made to output registers that are already in use. The status table is maintained by a central controller and can be interrogated by the CABs.
The I/O port extracts commands from the incoming byte stream, and inserts replies to the commands in the outgoing byte stream. Commands that require serialization, such as establishing a connection, are forwarded to the central controller, while "localized" commands, such as breaking a connection, are executed inside the I/O port.

HUB Commands and Usage
The HUB hardware supports 38 user commands and 14 supervisor commands for various datalink protocols. Supervisor commands are for system testing and reconfiguration purposes, whereas user commands are for operations concerning connections, locks, status, and flow control.
For the Nectar prototype each command is a sequence of three bytes:

command HUB ID param
The first byte specifies a HUB command, the second byte specifies the HUB to which the command is directed, and the third byte is a parameter for the command, typically the ID of one of the ports on that HUB.
In the following we mention some of the user commands and describe how they can be used to implement several datalink protocols. The four-HUB system depicted in Figure 7 will be used in all the examples.

Circuit Switching
Using circuit switching, the entire route is set up first using a command packet, before a data packet is transmitted. (A data packet is framed by start of packet and end of packet.) To send data from CAB3 to CAB1, CAB3 first establishes the route by sending out the following command packet: with retry and reply command is forwarded to HUB1 over the connection. After the connection from P3 to P8 in HUB1 is established, HUB1 sends a reply over the route established in the opposite direction, using another set of fiber lines, input queues, and output registers. By stealing cycles from these resources whenever necessary, the reply is never blocked and can reach CAB3 within a bounded amount of time. After receiving the reply, CAB3 knows that all the requested connections have been established. Then CAB3 sends data, followed by a close all command that travels over the established route.
The close all command is recognized at the output register of each HUB in the route. After detecting the close all, the HUB closes the connection leading to the output register. Therefore all the connections will be closed after the data has flowed through them. Alternatively, close all can be replaced with a set of individual close commands, closing the connections in reverse order.
If CAB3 does not receive a reply soon enough, it can try to get the connection status of the HUBs involved to find out what connections have been made, and can send another command packet requesting a different route (possibly starting from some existing connections). CAB3 can also decide to take down all the existing connections by using close all, and attempt to re-establish an entire route.

Circuit Switching for Multicasting
To illustrate how multicasting is implemented, consider the case in which CAB2 wants to send a data packet to both CAB4 and CAB5, as depicted in Figure 7. To establish the required connections, CAB2 can use the following command packet: After receiving replies to both of the open with retry and reply commands, CAB2 sends the data packet.

Packet Switching
The HUB has two facilities to support packet switching: 1. An input queue for each port. For the prototype Nectar system the length of the input queue, and thus the maximum packet size, is 1 kilobyte. (Circuit switching must be used for larger packets but, since the overhead of circuit setup is small compared to the packet transmission time, this does not add significantly to latency.)

Support for flow control A ready bit is associated with each port of a HUB. The ready bit indicates
whether the input queue of the next HUB connected to it is ready to store a new packet. Consider for example port P8 of HUB2 in Figure 7. This port is connected to port P3 of HUB 1. If the ready bit associated with P8 of HUB2 is 1, then the input queue of P3 of HUB 1 is guaranteed to be ready to store a new packet.
The ready bit associated with each port is set to 1 initially. When start of packet is detected at the output register of the port, the ready bit is set to 0. Upon receipt of a signal from the next HUB indicating that the start of packet has emerged from the input queue connected to the port, the bit is set to 1.
Suppose that CAB3 wants to send a data packet to CAB1 using the route shown in Figure 7. Using packet switching, CAB3 can send out the following packet: The test open with retry command is used to enforce flow control. For example, the first test open with retry command ensures that HUB2 will not succeed in making the connection from P4 to P8 until port P3 of HUB1 is ready to store the entire data packet Otherwise HUB2 will keep trying to make the connection. Thus the packet is forwarded to the next HUB as soon as the input queue in that HUB becomes available.

The CAB
The CAB is the interface between a node and the Nectar-net It handles the transmission and reception of data over the fibers connected to the network. Communication protocol processing is off-loaded from the node to the CAB thus freeing the node from the burden of handling packet interrupts, processing packet headers, retransmitting lost packets, fragmenting lar^e messages, and calculating checksums.

CAB Design Issues
The design of the CAB is driven by three requirements: 1. The CAB must be able to keep up with the transmission rate of the optical fibers (100 megabits/second in each direction).
2. The CAB should ensure that messages can be transmitted over the Nectar-net with low latency. The HUB can set up a connection and begin transferring a data packet in less than one microsecond. Thus any latency added by the CAB can contribute significantly to the overall latency of message transmission.
3. The CAB should provide a flexible environment for the efficient implementation of protocols and selected applications. Specifically, it should be possible to implement a simple operating system on the CAB that allows multiple lightweight processes to share CAB resources.
Together these design goals require that the CAB be able to handle incoming and outgoing data at the same time as meeting local processing needs. This is accomplished by including a hardware DMA controller on the CAB. The DMA controller is able to manage simultaneous data transfers between the incoming and outgoing fibers and CAB memory, as well as between VME and CAB memory, leaving the CAB CPU free for protocol and application processing.
To meet the protocol and application processing requirements, we designed the CAB around a high performance RISC CPU and fast local memory. The choice of a high-speed CPU, rather than a custom microengine or lower performance CPU, distinguishes the CAB from many I/O controllers. The latest RISC chips are competitive with microsequencers in speed, but offer additional flexibility and a familiar development environment. Older general-purpose microprocessors would be unable to keep up with the protocol processing requirements at fiber speeds, let alone provide cycles for user tasks.
Allowing application software to run on the CAB is important to many applications but has dangers. In particular, incorrect application software may corrupt CAB operating system data structures. To prevent such problems, the CAB provides memory protection on a per-page basis and hardware support for multiple protection domains.
The CAB design also includes various devices to support high-speed communication: hardware checksum computation removes this burden from protocol software; hardware timers allow time-outs to be set by the software with low overhead. Figure 8.

CAB Implementation The prototype CAB implementation uses as its RISC GPU a SPARC processor running at 16 megahertz. A block diagram of the CAB is shown in
A VME interface to the node was the natural choice in our environment, allowing Sun workstations and Warp systems to be used in the Nectar prototype. The initial CAB implementation supports a VME bandwidth of 10 megabytes/second, which is close to the speed of the current fiber interface.
Two fibers (one for each direction) connect each CAB to the HUB. The fiber interface uses the same circuit as the HUB I/O port (see Section 4.1). Data can be read or written to the fiber input or output queue by the GPU, but for data transfers of more than small numbers of words the DMA controller should be used to achieve higher transmission rates. The DMA controller also handles flow control during a transfer the DMA controller waits for data to arrive if the input queue is empty, or for data to drain if the output queue is full.
The on-board CAB memory is split into two regions: one intended for use as program memory, the other as data memory. DMA transfers are supported for data memory only; transfers to and from program memory must be performed by the CPU. The memory architecture is thus optimized for the expected usage pattern, although still allowing code to be executed from data memory or packets to be sent from program memory.
In the prototype, the total bandwidth of the data memory is 66 megabytes/second, sufficient to support the following concurrent accesses: CPU reads or writes, DMA to the outgoing fiber, DMA from the incoming fiber, and DMA to or from VME memory. The program memory has the same bandwidth as data memory and is thus able to sustain the peak CPU execution rate.
The program memory region contains 128 kilobytes of PROM and 512 kilobytes of RAM. The data memory region contains 1 megabyte of RAM. Both memories are implemented using fast (35 nanosecond) static RAM. Using static RAM in the prototype rather than less expensive dynamic RAM plus caching was worth the additional cost-it allowed us to focus on the more innovative aspects of the design instead of expending effort on a cache.
The CAB's memory protection facility allows each 1 kilobyte page to be protected separately. Each page of the CAB address space (including the CAB registers and devices) can be assigned any subset of read, write, and execute permissions. All accesses from the CAB CPU or from over the VME bus are checked in parallel with the operation so that no latency is added to memory accesses. The flexibility, safety, and debugging support that memory protection affords the CAB software is worth the non-trivial cost in design time and board area.
The memory protection includes hardware support for multiple protection domains, with a separate page protection table for each domain. Currently the CAB supports 32 protection domains. The assignment of protection domains is under the control of the CAB operating system kernel. The kernel can therefore ensure that the CAB system software is protected from user tasks and that user tasks are protected from one another. In addition, accesses from over the VME bus are assigned to a VME-specific protection domain.
The CAB occupies a 24-bit region of the node's VME address space. Every device accessible to the CAB CPU is also visible to the node, allowing complete control of the CAB from the node. In normal operation, however, the node and CAB communicate through shared buffers, DMA, and VME interrupts.
The CAB prototype is a 15 x 17 inch board, with a typical power consumption of 100 watts. Of the nearly 360 components on the densely packed board about 25% are for the data memory and DMA ports, 15% for the VME interface, 15% for the CPU and program memory, and 13% for the I/O ports. The remaining 120 or so chips are divided among the DMA controller, CAB registers, hardware checksum computation, memory protection, and clocks and timers.

Software
The design of the Nectar software has two goals: [3,5,11], the software organization plays a critical role in reducing the latency. To achieve low latency, data copying and context switching must be minimized.

2.
Provide a flexible software environment on the CAB. This will convert a bare "protocol engine" into a customizable network interface. When appropriate, the CAB can also be used to off-load application tasks from the node.
The software currently running on the prototype system consists of the CAB kernel, communication protocols, and Nectarine, a library for programming applications.

The CAB Kernel
Candidate run-time systems for the CAB range from a minimal single-task system to a complete UNIX implementation. To provide the required efficiency and flexibility, we built the CAB kernel around lightweight processes similar to Mach threads [8]. Threads support multitasking so the CAB can execute multiple activities concurrently in a time-shared fashion, but, since threads have little state associated with them, the cost of context switching is low. Thread switching takes between 10 and 15 microseconds; almost all of this time is spent saving and restoring the SPARC register windows.
Threads execute as a set of coroutines, using a simple, non-preemptive scheduler. This organization matches the intended use of the CAB: a thread will be awakened by an event (such as the arrival of a packet), will take some action (such as processing transport protocol headers), and will voluntarily go back to waiting for another event.
The CAB kernel provides support for simple, time-critical operations such as memory management and timers, but it relies on the node operating system for more complicated operations such as file I/O. The CAB invokes these services by interrupting the node over the VME bus.
Another CAB function is to provide temporary buffer space for messages in an efficient way. This is achieved using mailboxes in CAB memory. In the common single-reader, single-writer case, allocating and reclaiming space is simple because mailboxes behave like FIFOs. Mailboxes also support multiple readers, multiple writers, and out-of-order reads. These access patterns occur, for example, when multiple servers operate on different messages in the same mailbox.

Communication
The communication software has three main parts: the datalink protocol on the CAB, transport protocols on the CAB, and node software dealing with the CAB-node interface. The main guideline in the design of the communication software was to avoid data copying and context switching on both the CAB and the node.

Datalink Protocol
The datalink protocol transfers data packets between CABs using HUB commands, manages HUB connections, and recovers from framing errors and lost HUB commands. The most frequently used simple operations, such as sending a packet to a node in the same HUB cluster, are implemented in hardware as a single HUB command, while more complicated and less frequent operations, such as multicasting and error recovery, are implemented in software.
The interface between the datalink and transport layers passes packets by reference, thus avoiding the copying of data. During a send, the datalink gathers the packet when it transfers the data to the fiber output queue using DMA. During a receive, the datalink interrupt handler, invoked by the start of packet signal, executes an upcall [6] to a transport layer routine. This routine uses the transport header to determine the destination mailbox for the packet. The datalink layer then sets up the DMA to transfer the incoming data to the destination mailbox. The transport layer upcalls must determine the destination mailbox and return to the datalink layer before incoming data overflows the CAB input queue.
The datalink code is executed entirely by interrupt handlers and by procedures that are called from transport or application threads, so there is no context switching overhead at the datalink-transport interface. The SPARC architecture helps reduce the overhead for critical interrupts by reserving a register window for trap handling.

Transport Protocols
The transport layer is responsible for message transfer between mailboxes on different CABs. This involves breaking messages into packets, reassembling messages, flow control, and retransmission of lost and damaged packets. Three protocols have been implemented: • The datagram protocol has low overhead but does not guarantee packet delivery; it is a direct interface to the datalink layer and should only be used by applications that can tolerate or recover finom lost packets.
• The byte-stream protocol provides reliable communication using acknowledgments, retransmissions, and a sliding window for flow control.
• The request-response protocol supports client-server interactions such as remote procedure calls.

13
The current transport protocols are simple and Nectar-specific.

We plan to experiment with the corresponding Internet protocols (IP, TCP, and VMTP [4]) over Nectar in the coming year.
Each transport protocol can be invoked through a procedure call or by placing a command in a special mailbox. In both cases, the message to be sent is specified as a list of areas located in CAB memory or in CAB-accessible VME memory. When sending large messages between nodes, it is important to overlap packet transfers over the Nectar-net and over the VME bus at each end, in order to reduce latency and increase throughput The CABs at the sender and receiver sides are well suited for setting up this "packet pipeline": they can select an optimal packet size, synchronize the various DMAs, and manage the buffers.

623
CAB-Node interface Three CAB-node interfaces arc provided, with different tradeoffs between efficiency and transparency: • The most efficient CAB-node interface is based on shared memory: the CAB memory is mapped into the address space of the node process, and the node process builds or consumes messages in place in CAB memory. Node processes invoke services by placing a command in a special mailbox on the CAB. This interface is efficient since it eliminates copying the message between the node and the CAB and does not involve the operating system on the node. Messages are received by polling CAB memory.
• A second approach is to provide a Berkeley UNIX socket interface to Nectar. This interface is less efficient since it involves system call overhead and data copying on the node. But the transport protocol overhead is off-loaded onto the CAB. This approach allows existing source code to be used on Nectar with minimal modification.
• The third interface is a Berkeley UNIX network driver for Nectar. In this case, Nectar is used as a "dumb" network and all transport protocol processing is performed on the node. The advantage of this approach is binary compatibility for current applications such as network file systems and window systems.

Programming Nectar: Nectarine
Nectarine is a programming interface that gives the programmer access to the Nectar hardware and lowlevel software. It is similar to the communication interface available on other distributed-memory machines such as hypercubes [2]. An important difference is that Nectarine must accommodate heterogeneous nodes, operating systems, memories, attached processors, and other devices. Nectarine presents the programmer with a simple communication abstraction: applications consist of tasks that communicate by transferring messages between user-specified buffers. Tasks are processes on any CAB or node. Messages can be located in any memory. Using Nectarine, the programmer can create tasks, manage buffers, and send and receive messages. Nectarine minimizes the number of copy operations and uses DMA whenever possible.
The fact that Nectarine hides much of the heterogeneity does not free the programmer from knowing the characteristics of nodes and memories, because the allocation of tasks and data to processors and memories has a serious impact on performance. For example, whether a message is allocated in CAB or node memory influences how efficiently the message can be built and how fast it can be sent Work has started on higher-level programming tools for Nectar. We are developing a high-level, language that will be mapped onto a specific Nectar configuration by a compiler. Automating the mapping process will not only simplify the programming task, but will also make programs portable across multiple Nectar configurations or other distributed systems. ^

7 Applications
The prototype Nectar system will be used for a wide spectrum of applications ranging from parallel programs, in which Nectar is used as a multicomputer, to research in distributed operating systems, in which Nectar is viewed as a fast LAN. One of the first Nectar applications is in the area of vision. The application uses a Warp machine [1] for low-level vision analysis and Sun workstations for manipulating image features that are stored in a distributed spatial database. It requires both high bandwidth for image transfer and low latency for communication between nodes in the database. This application has a static computational model: the assignment of tasks to nodes is done when the application is started.
We are implementing a parallel production system as an example of an application that requires runtime load balancing. Matching is performed in parallel using a distributed RETE network, and tokens that propagate through the network are stored in a distributed task queue [14]. The low latency communication of Nectar provides good support for the fine-grained parallelism required by this application.
The flexibility of Nectar allows it to run applications originally written for other parallel systems. For example, to run hypercube applications on Nectar, we have implemented the Intel iPSC communication library [10] on top of Nectarine. Since Nectarine is functionally a superset of the iPSC primitives, this implementation is relatively simple. Several large applications are being ported to Nectar using this approach, including simulated annealing and a solid modeling system based on the octree data structure.
Large-scale scientific applications that execute well on loosely-coupled arrays of processors [7] are also easily ported to Nectar. Powerful, general-purpose Nectar nodes can provide sufficient processing power and memory to meet the computational demands of these applications and the Nectar-net has the bandwidth to meet their communication needs.
The high bandwidth and low latency provided by Nectar also make it an attractive architecture for communication-intensive distributed applications. Examples of such applications include distributed transaction systems, such as Camelot [13], and the simulation of shared virtual memory over a distributed system using Mach [9]. In these applications, the CAB will play a critical role as an operating system co-processor.

Conclusions
Architectures to exploit the high-level, irregular parallelism found in large applications should support heterogeneity, low-latency communication, and scalability. The Nectar architecture meets these goals: it is based on a "network backplane" that consists of a high-speed fiber-optic network, large crossbar switches, and powerful network interface processors.
The hardware design takes advantage of the availability of fast crossbar chips, fiber-optic technology, and RISC processors that can keep up with fiber speeds. The software architecture has benefited from experience with network communication, operating systems, and parallel applications.
The prototype shows that the proposed architecture can be implemented. Developing real applications on the prototype is the next step; we will use these applications to evaluate the basic ideas of Nectar, to judge how well the design meets its goals, and to guide us in evolving the prototype into a large-scale system with hundreds of nodes in production use.