# Patent

## Title
Multiprocessor node controller circuit and method

## Abstract

A multiprocessor computer system includes a first and second node controller, a number of processors being connected to each node controller, a memory connected to each node controller, a first input/output system connected to the first node controller, and a communications network connected between the node controllers. The first node controller includes: a crossbar unit to which are connected a memory port, an input/output port, a network port, and a plurality of independent processor ports. A first and a second processor port is connected between the crossbar unit and a first subset and a second subset, respectively, of the processors. The memory port includes a memory data port including a memory data bus and a memory address bus coupled to the first subset of memory chips, and a directory data port including a directory data bus and a directory address bus coupled to the second subset of memory chips.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
This application is a continuation application of U.S. application Ser. No. 10/868,181 filed Jun. 15, 2004 and now U.S. Pat. No. 7,406,086, which is a continuation application of U.S. application Ser. No. 09/407,428 filed Sep. 29, 1999 and now U.S. Pat. No. 6,751,698, which is related to U.S. application Ser. No. 09/408,874 filed Sep. 29, 1999 and entitled “MODULAR COMPUTING ARCHITECTURE HAVING COMMON COMMUNICATION INTERFACE” and now U.S. Pat. No. 6,829,666, U.S. application Ser. No. 09/408,084 filed Sep. 29, 1999 and entitled “TRANSLATION OF PCI LEVEL INTERRUPTS INTO PACKET BASED MESSAGES FOR EDGE EVENT DRIVE MICROPROCESSORS” and now U.S. Pat. No. 6,604,161, U.S. application Ser. No. 09/522,695 filed Mar. 10, 2000 and entitled “SYSTEM AND METHOD FOR A HIERARCHICAL SYSTEM MANAGEMENT ARCHITECTURE OF A HIGHLY SCALABLE COMPUTING SYSTEM” and now U.S. Pat. No. 6,845,410, which is a continuation of U.S. application Ser. No. 09/407,429 filed Sep. 29, 1999 and entitled “HIERARCHICAL SYSTEM MANAGEMENT ARCHITECTURE FOR A HIGHLY SCALABLE COMPUTING SYSTEM” and now abandoned, U.S. Pat. No. 6,516,372 issued Feb. 4, 2003 and entitled “PARTITIONING A DISTRIBUTED SHARED MEMORY MULTIPROCESSOR COMPUTER TO FACILITATE SELECTIVE HARDWARE MAINTENANCE”, U.S. application Ser. No. 09/408,972 filed Sep. 29, 1999 and entitled “NETWORK TOPOLOGY FOR A SCALABLE MULTIPROCESSOR SYSTEM” and now U.S. Pat. No. 6,973,559, U.S. application Ser. No. 09/407,421 filed Sep. 29, 1999 and entitled “TRANSFER ATTRIBUTE ENCODING WITHIN AN ADDRESS ON A BUS” and now U.S. Pat. No. 6,711,636, U.S. application Ser. No. 09/408,778 filed Sep. 29, 1999 and entitled “AGE-BASED NETWORK ARBITRATION SYSTEM AND METHOD” and now U.S. Pat. No. 6,674,720, U.S. Pat. No. 6,085,303 issued Jul. 4, 2000 and entitled “SERIALIZED, RACE-FREE VIRTUAL BARRIER NETWORK”, U.S. Pat. No. 6,230,252 issued May 8, 2001 and entitled “HYBRID HYPERCUBE/TORUS ARCHITECTURE”, U.S. Pat. No. 5,970,232 issued Oct. 19, 1999 and entitled “ROUTER TABLE LOOKUP MECHANISM”, U.S. application Ser. No. 08/971,184 filed Nov. 17, 1997 and entitled “MULTI-DIMENSIONAL CACHE COHERENCE DIRECTORY STRUCTURE” and now U.S. Pat. No. 6,633,958, and U.S. Pat. No. 6,101,181 issued Aug. 8, 2000 and entitled “VIRTUAL CHANNEL ASSIGNMENT IN LARGE TORUS SYSTEMS”, all of the above of which are hereby incorporated by reference.


TECHNICAL FIELD OF THE INVENTION
The present invention relates to methods and apparatus for parallel multiprocessor computer systems and more specifically to a multiprocessor node-controller circuit and method.
BACKGROUND OF THE INVENTION
Multiprocessor (MP) systems are computing systems comprised of a few or up to hundreds or thousands of processing elements (PEs). While the power of a multiple-instruction multiple-data (MIMD) MP computer system lies in its ability to execute independent threads of code simultaneously, the inherently asynchronous states of the PEs (with respect to each other) makes it difficult in such a system to enforce a deterministic order of events when necessary. Program sequences involving interaction between multiple PEs such as coordinated communication, sequential access to shared resources, controlled transitions between parallel regions, etc., may require synchronization (such as barrier and/or eureka synchronization) of the PEs in order to assure proper execution. One such invention having routers, networks, and synchronization apparatus and methods is described further in copending U.S. Pat. No. 6,085,303, issued Jul. 4, 2000, entitled “SERIALIZED, RACE-FREE VIRTUAL BARRIER NETWORK”.
Some MP systems having symmetric distributed multiprocessors use a coherent model of cache. One such system is described in application Ser. No. 08/971,184 filed Nov. 17, 1997 entitled “MULTI-DIMENSIONAL CACHE COHERENCE DIRECTORY STRUCTURE”.
There is a need in the art for an improved node controller apparatus and method to improve communications between various portions of an MP system. Further, there is a need for a node controller that will “scale well” providing excellent performance-cost benefits for both small and large systems. Further, there is a need for a node controller that has very high flexibility, performance and speed.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus that facilitates highly parallel processing. The present invention includes a node controller usable in both small and large multiprocessor systems, and that provides superior performance-cost benefits across a large range of system prices and capabilities. In some embodiments, this node controller is implemented on a single chip that provides two or more processor ports, each supporting single-processor and/or multiprocessor subsystems (each optionally including local cache memories), as well as one or more of the following port types: input/output (I/O), memory, directory, and network interface.
Traditionally, distributed multiprocessors are built using a separate directory controller along with a memory controller, connected to the network controller, the input/output interface, and processors. In various embodiments of the present invention, the memory controller (that optionally includes a directory controller that provides cache coherence functions) and the I/O controller and the network controller and put them all on one chip that includes a plurality of processor ports. This provides a couple of advantages. First, transmissions between any of the nodes are direct, on chip, and are implemented using a single protocol, so that transmissions do not have to traverse as many chip boundaries. Second, by imbedding all of this onto a single chip, a full crossbar design is utilized inside the chip. This provides non-blocking communication whereby a remote node can talk directly to the local node's memory while the local node is talking to its I/O system with no queuing between those communications. In contrast, on a bus-type system, one of the communications would have to wait for the other to complete. These can go on simultaneously in embodiments of the present invention that use a crossbar. Further, by building all of the stuff into a single chip, it is more cost effective to build a smaller system out of this same architecture because there is not the overhead of having a lot of extra chips to support a large system configuration when one is not building a large system.
A first aspect of the present invention provides a multiprocessor computer system (for example, a small multiprocessor system having only two node controllers connected to one another, or a multiprocessor system having up to hundreds or thousands of node controllers connected together through a router network). One such embodiment of the system includes a first node controller, a second node controller, a first plurality of processors operatively coupled to the first node controller, a second plurality of processors operatively coupled to the second node controller, a first memory operatively coupled to the first node controller, a first input/output system operatively coupled to the first node controller, and an interprocessor communications network operatively coupled between the first node controller and the second node controller. In this embodiment, the first node controller includes: a crossbar unit, a memory port operatively coupled between the crossbar unit and the first memory, an input/output port operatively coupled between the crossbar unit and the first input/output system, a network port operatively coupled between the crossbar unit and the interprocessor communications network, and a plurality of independent processor ports, including a first processor port operatively coupled between the crossbar unit and a first subset of the first plurality of processors, and a second processor port operatively coupled between the crossbar unit and a second subset of the first plurality of processors. In some embodiments of the system, the first node controller is fabricated onto a single integrated-circuit chip.
In some embodiments of the system, the memory is packaged on a plurality of pluggable memory/directory cards wherein each card includes a plurality of memory chips including a first subset of memory chips dedicated to holding memory data and a second subset of memory chips dedicated to holding directory data. Further, the memory port includes a memory data port including a memory data bus and a memory address bus coupled to the first subset of memory chips, and a directory data port including a directory data bus and a directory address bus coupled to the second subset of memory chips. In some such embodiments, the ratio of (data space in the first subset of memory chips) to (data space in the second subset of memory chips) on each of the memory/directory cards is set to a value based on a size of the multiprocessor computer system.
In some embodiments of the system, the crossbar unit selectively combines two serially received doublewords of data into a single quadword micropacket for transmission through the crossbar unit, and wherein each doubleword contains at least 64 bits of data and the single quadword contains at least 128 bits of data.
Another aspect of the present invention provides a method usable with one or more of the above described systems. The method includes transmitting data between the memory port and the first processor port, between the memory port and the second processor port, between the memory port and the input/output port, and between the memory port and the network port.
Some embodiments of the method further include transmitting data directly between the first node controller and the second node controller that are directly connected to one another by the interprocessor communications network.
Some embodiments of the method further include transmitting data indirectly between the first node controller and the second node controller through a router chip that is also connected to one or more other node controllers.



BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings, wherein like reference numerals represent like parts, in which:
FIG. 1 shows one embodiment of multiprocessor system 100 of the present invention.
FIG. 2 shows one embodiment of a node cluster 170 having a router 76 with six router connections 72 and eight processors 74, wherein four processors 74 are connected to each of two node controllers 75.
FIG. 3 shows an embodiment of a multiprocessor system 300 having a single router 76.
FIG. 4 shows an embodiment of a multiprocessor system 400 having no router chips, but having two node controllers connected to one another.
FIG. 5 shows one embodiment of a multiprocessor system 500 of the present invention.
FIG. 6A shows DIMM module 600.
FIG. 6B shows DIMM guide 673 having four DIMM modules 600.
FIG. 7A shows node controller 75 of one embodiment of the present invention.
FIG. 7B shows one embodiment node controller 75 further including indications of the flow of data into and within node controller 75. FIG. 7B also shows node controller 75 implemented within a single chip 475.
FIG. 7C shows a diagram of node controller 75 within a node 370 and describing the various interface widths and clock speeds for one embodiment of the present invention.
FIG. 7D shows header and data formats for messages of one embodiment of node controller 75.
FIG. 7E shows the field format for source and supplemental fields.
FIG. 7F shows a table of control signal usages for control field 741 or control field 747.
FIG. 7G shows a device ID encoding for field 743.
FIG. 7H shows terminology used for describing content of the source field in the header of messages for XB 279.
FIGS. 7I, 7J, 7K, 7L, 7M, and 7N show a multi-part table (Table 3) describing internal Bedrock message source and supplemental fields.
FIG. 7O is a table (Table 4) of the Xsel select-encodings for XB 279.
FIG. 8 is a block diagram of one embodiment of XB 279.
FIG. 8A shows a table of POQ/PI interface signals.
FIG. 8B shows a table of PIQ/PI interface signals.
FIG. 9 shows a timing diagram 900 for PIQ.
FIG. 9A shows a table of MOQ/MD interface signals.
FIG. 10 shows a timing diagram 1000 of MD/MOQ interface signals.
FIG. 10A shows a table of XB/MD interface signals.
FIG. 11 shows a timing diagram 1100 for the NOQ interface.
FIG. 11A shows a table of NOQ/NI interface signals.
FIG. 11B shows a table of XB/NI interface signals.
FIG. 12 shows the protocol for access errors (AE).
FIG. 12A shows a table of LOQ/LB interface signals.
FIG. 12B shows a table of LIQ/LB interface signals.
FIG. 12C shows a table of IOQ/II interface signals.
FIG. 12D shows a table of IIQ/II interface signals.
FIG. 13 shows a table of sample bypass arbiter interface signals.
FIG. 14 shows a diagram of XB arbiter filter 1400 for XB 279, with MOQ filter shown as an example.
FIG. 15 shows a diagram of a wavefront arbiter structure 1500 (this diagram shows only one of six fixed-priority arbiters).
FIG. 15A shows a table of sample wavefront arbiter interface signals.
FIG. 16 shows a timing diagram of flow control in XB 279.
FIG. 16A shows a table of channels for requesting input queues.
FIG. 17 shows a block diagram of MOQ data buffers.
FIG. 17A shows a table of signals for requesting input queues.
FIG. 18 shows a block diagram of NOQ buffers.
FIG. 19 shows a block diagram of IOQ buffers.
FIG. 20 shows a block diagram of MIQ buffers.
FIG. 21 shows a block diagram of LIQ buffers.
FIG. 22 shows a block diagram of XB RLMs.
FIG. 23 shows a block diagram of PI 270.
FIG. 23A shows speeds for SYSAD interfaces for some T-Rex speeds and clock divisors.
FIG. 24 shows a block diagram for the address and datapath for PI 270.
FIG. 25 shows a data structure diagram of a RRB element.
FIG. 25A shows various RRB status bits.
FIG. 26 shows a block diagram of an RRB.
FIG. 27 shows a data structure diagram of a WRB element.
FIG. 27A is a table (Table 35) of WRB status bits.
FIG. 28 shows a data structure of one embodiment of an IRB element.
FIG. 29 shows a diagram of functions provided by a PI 270 of one embodiment of the present invention.
FIG. 29A is a table (Table 36) of T-Rex generated requests.
FIG. 29B is a table (Table 37) of RRB requests for WRB conflicts.
FIG. 29C is a table (Table 38) showing the data format for outbound requests.
FIG. 29D is a table (Table 39) showing the data format for incoming reply actions.
FIG. 30 is a timing diagram for SYSAD arbitration for a T-Rex external block data response.
FIG. 31 is a block diagram of one embodiment of MD 275.
FIG. 32 is a block diagram of one embodiment of a memory DIMM 600.
FIG. 32A is a table (Table 58) of DIMM configurations.
FIG. 33 is a block diagram of one embodiment of a pair of “standard” memory DIMMs 680.
FIG. 34 is a block diagram of one embodiment of a pair of “premium” memory DIMMs 690 (wherein one half of the pair is shown).
FIG. 34A is a table (Table 59) of address translation used.
FIG. 34B is a table (Table 60) of incoming messages for MD 275.
FIG. 34C is a table (Table 61) of outgoing messages for MD 275.
FIG. 35 is a block diagram of one embodiment of the queues of MD 275.
FIG. 36 is a block diagram of one embodiment of the interface between MD 279 and external EPROM, UART, LED, and Synergy bridge chip.
FIG. 37 shows one embodiment of a Memory Block datapath.
FIG. 38 is a block diagram of Fetch and OP Cache datapath.
FIG. 39 is a block diagram of the main address and data paths of the NI 274.
FIG. 40 shows message sideband encoding.
FIG. 41 shows a block diagram of the connections between node controller 75 and router 76 of one embodiment.
FIG. 42 shows a high level diagram of the IO unit and its position relative to the rest of node controller 75 and input/output port 79.



DETAILED DESCRIPTION OF THE INVENTION
In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.
Some embodiments of the present invention include routers, networks, and synchronization apparatus and methods as described further in copending U.S. patent application Ser. No. 08/972,010 filed Nov. 17, 1997, which is hereby incorporated by reference.
Some embodiments implement multiprocessor systems, that generally do not use a coherent cache model. Other embodiments include cache coherence mechanisms and methods such as described in application Ser. No. 08/971,184 filed Nov. 17, 1997 entitled “MULTI-DIMENSIONAL CACHE COHERENCE DIRECTORY STRUCTURE”, which is hereby incorporated by reference. In particular, the present invention provides a node controller that is economic and provides excellent performance when scaled sown as well as when scaled up (i.e., to a large number of processors).
FIG. 1 shows one embodiment of multiprocessor computer system 100 of the present invention having one or more node clusters 170, each node cluster 170 having zero to N processors 74, zero to M memories 77, and zero to I input/output (I/O) subsystems 79. Depending on the needs of a user, interconnection network 175 can be set up as a three-dimensional torus, an N-dimensional hypercube, or any other suitable interconnection network between routers 76. In one embodiment, each router 76 includes eight ports 211, wherein each port 211 can be used to either connect to other routers 76, or to one to N node controllers 75 each having zero or more processor elements (PEs) 74. Thus, in some embodiments, a router 76 can be used as just an interconnection node in the network 175 (i.e., a circuit within block 175 rather than within node cluster 170), having no PEs 74 or memory 77 or I/O subsystems 79, and all of its ports are used to connect to other routers 76.
In other embodiments, such as shown in FIG. 1, some of the ports 211 are used to connect to other routers 76 through network 175, and other ports 211 are used to connect, via node controller 75, to a plurality 141 of PEs 74, to memories 77, and to I/O subsystems 79.
FIG. 2 shows details of one such embodiment of a node cluster 170 having a router 76 with six router connections 72 (i.e., connections to other routers 76), and two node-controller connections 73 (also called channel 73) (i.e., connections to the two node controllers 75 that together connect in turn to eight processor elements 74). One to four PEs 74 connect to each node controller 75, and share a single memory 77 having one or more banks of memory. In some embodiments, each bank includes two or more memory cards accessed in parallel. In some embodiments, each memory card includes separate subsets of memory chips, one subset dedicated to memory data, and another dedicated to directory data (such cards are sometimes called memory/directory cards). Each node controller 75 optionally connects to an I/O subsystem 79 that provides connections to conventional high-speed I/O ports and devices such as workstations, disk systems, and tape systems, etc.
In one embodiment, each node controller 75 includes up to five interface ports, i.e., PI 271, PI 272, II 273, NI 274, and MI 275. Processor port interface 0 (PI0) 271 connects to a first subset 241 of processors 74, processor port interface 1 (PI1) 272 connects to a second subset 242 of processors 74, input/output port interface (II) 273 connects to an input/output system 79, network port interface (NI) 274 connects to either a router 76 as shown in FIG. 2, or to another node controller 75 as shown in FIG. 4 below. Memory interface (MI) 275 connects to memory 77.
FIG. 3 shows another embodiment, showing a multiprocessor system 300 having a single node cluster 170 having a single router 76 with no router connections 72, eight node-controller connections (channels) 73 (i.e., connections to the eight node controllers 75 that together connect in turn to thirty-two processors 74). This is the maximum number of PEs 74 for this embodiment of router 76 (which has eight ports 211) and node controller 75 (which can connect to up to four PEs 74). Each port 211 connects to up to one processor cluster 370, and each processor cluster 370 has up to four PEs 74, a shared memory 77 for the PEs 74, and a shared I/O subsystem 79, all connected through one node controller 75. In this embodiment, router 76 is not connected to any other router 76. Of course in other configurations, not all ports 211 need be used, and not all processor clusters 370 need be fully populated with four PEs 74.
FIG. 4 shows an embodiment of a multiprocessor system 400 having no router chips, but having two node controllers 75 connected to one another using a single interprocessor communications channel 73. This embodiment accommodates up to eight processors 74. This is the maximum number of PEs 74 for this embodiment of node controller 75 (each of which can connect to up to four PEs 74). Each node controller 75 connects to up to one other processor cluster 370, and each processor cluster 370 has up to four PEs 74, a shared memory 77 for the PEs 74, and a shared I/O subsystem 79, all connected through one node controller 75. Of course in other configurations, not all processor clusters 370 need be fully populated with four PEs 74, and in still other embodiments, more than eight processors are supported.
System Architecture
The system architecture of the present invention (sometimes denoted “SN1”), shown in FIG. 5, includes of one or more processor/memory nodes 370 connected with a general interconnect network (also called an interprocessor communications fabric) 575 whose bandwidth scales with the number of processors. In various embodiments, interprocessor communications fabric 575 can be as simple as a single interprocessor communications channel 73 that directly couples two node controllers 75 as shown in FIG. 4, or can include an extensive network connecting many node controllers 75. One such extensive network includes a network of interconnected routers 76 such as shown in FIG. 1, but other embodiments include other interconnection networks such as are well known in the art.
High-Level Organization of the SN1 System
The global shared-memory 577 in SN1 is partitioned with a section of memory 77 distributed (i.e., locally connected) to each group of four processors 74. This partitioning provides very low latency for memory allocated close to the processor 74, while the general interconnect provides for global access to all of memory 577 from any processor 74. A directory-based protocol is used to maintain cache coherence over all of global memory 577. Input/output (I/O) 579 within the SN1 system is also partitioned with an I/O interface connection point (II port) 273 on each CPU/Memory node 370. As with the distributed memory 577, every I/O port 273 is addressable from every processor 74.
In one embodiment, each CPU/Memory node 370 is packaged in a “brick” module. Large CPU configurations can be constructed using multiple Node modules. These nodes 370 are connected with links through routers 76, each of which is also packaged in brick. In various embodiments, each node 370 contains up to four T-Rex-type or Merced-type processors, memory-directory bank(s) 77 each having some amount of main memory and an associated amount of directory memory, an attachment port 274 for multinode interconnection through the interconnection network (sometimes called CrayLink2), and an II attachment port 273 to the I/O subsystem 79. The interconnection network attachment port is full duplex, 1600 MB/sec in each direction. The I/O attachment port (sometimes called “XTOWN2”) is full duplex at 1200 MB/sec but can be slowed down to 800 MB/sec to interface with older I/O devices or graphics components from older SN0 systems.
The attachment port to the CrayLink2 connects to the routing network 175. The routing network 175 is built up from 8-ported router chips 76 that connect to nodes and to each other using cables. The interconnection topology used in the SN1 family is described in the next section.
DIMM Module 600
The DIMM module 600 (see FIG. 6A) is a 294-pin-position vertically-plugged PCB (printed circuit board), containing parts for main memory and directory memory.
DIMM Guide Base 671 and Levers 672
FIG. 6B shows DIMM guide 673 having four DIMM modules 600. Because the DIMM module 600 is extra tall, an external guide/support part 673 is required. The guide 673 supports four modules 600, allows airflow, and provides features for an insertion/extraction mechanism. In one embodiment, one guide design is used at both ends of the DIMM's, as shown in FIG. 6B.
Levers 672 reside on the top of the guide 671. These levers 672 will provide a mechanical advantage in the insertion, ejection, and retention of the DIMM modules 600.
Near-end DIMM latches shown closed in FIG. 6B. Far end latches shown in open state.
In some embodiments, node controller 75 is implemented on a single integrated circuit chip 475 (see FIG. 7B), and in one particular embodiment, on a single chip called “Bedrock.” References to Bedrock shall mean this particular embodiment of node controller 75, but other embodiments of the invention are contemplated. In particular, some embodiments contemplated omit certain features described below, and other embodiments replicate features described, or add and delete certain combinations of features.
Overview of the System
In one embodiment, the present invention specifies a distributed, shared-memory multiprocessor employing 1 to 4096 processors (although the Bedrock SN1 node implementation of one embodiment supports a maximum of 1024 processors). SN1 fully supports a single address space and provides cache coherence across the entire machine. SN1 is organized into a number of nodes; each node connects the local memory to the processors, provides a port to the Router Network, and a port to the IO subsystem. Bedrock is the first implementation of an SN1 node. Each Bedrock supports up to four T-Rex+ processors, a portion of the global memory, a directory to maintain cache coherence, an interface to the Crosstalk IO subsystem, and an interface to SN1 (SN1Net) Router Network, as shown in FIG. 7A.
Node Controller 275 (Bedrock) Overview
The Bedrock chip provides connectivity between four types of external interfaces and an interface to local chip resources. Each of the interfaces is managed by a subdivision of the Bedrock known as a unit. The units' names derive from the interfaces they manage: the IO interface unit (II), the network interface unit (NI), the memory/directory interface unit (MD), the two processor interface units (PI_0 and PI_1), and the local block (LB). The units are connected by a central crossbar (XB), as shown in FIG. 7B. Bedrock supports shared memory systems of up to 256 SN1Net nodes (1024 processors).
The different internal Bedrock interfaces communicate by sending messages through the XB unit. As explained in the SN1 Cache Coherence Protocol Specification, to avoid system deadlock, messages are separated into two groups: requests and replies. When a message arrives through the I/O port (Crosstalk protocol) or Network port (SN1Net protocol), the message is converted to the Bedrock's internal format. The reverse occurs when a message exits one of these ports.
FIG. 7A shows node controller 75 of one embodiment of the present invention. FIG. 7B shows one embodiment node controller 75 further including indications of the flow of data into and within node controller 75. FIG. 7B also shows node controller 75 implemented within a single chip 475. FIG. 7C shows a diagram of node controller 75 within a node 370 and describing the various interface widths and clock speeds for one embodiment of the present invention. FIG. 7D shows header and data formats for messages of one embodiment of node controller 75.
Bedrock Internal Message Format
The internal message of Bedrock (one embodiment of node controller 75) (see FIG. 7D) includes a header frame (a frame is a group of bits that is conceptually or logically a single unit. The term does not infer the number of clock cycles required to process the information, nor the unit-size of the bits that are placed simultaneously “on the wire” (either through the Bedrock's XB or over the Router Network or Crosstalk interfaces)), followed (optionally) by one or more data frames carrying a total of 64 to 1024 bits of data for the message. The format for each of the Bedrock frames (the header, the doubleword data, and the quadword data) is shown in FIG. 7D. A header frame can be followed by 0, 1, 2, or 16 doubleword data frames, or, on the MD interface, by 0, 1, or 8 quadword data frames (any particular Bedrock MD interface uses only one of these data formats). Most interfaces on the Bedrock's Crossbar unit accept/transmit one 160-bit micropacket flit (carrying either a header, a doubleword of data, or a quadword of data) in a single clock cycle. Bedrock's Crossbar unit processes each micropacket (from input port to output port) in two clock cycles. Whenever possible, the Crossbar unit combines 2 received doublewords into a single quadword micropacket.
As each frame crosses into or out of the Bedrock's XB unit, the control signals (defined in FIG. 7D and described in detail in Table 1) indicate all or some of the following information:

    
    
        to which local Bedrock unit (that is, XB port) the frame is destined (Xsel)
        whether the frame is a request or a reply (that is, the Class which defines the virtual channel used)
        whether this frame concludes the current message (Tail). Note that the Xsel field is only valid for headers, and that data frames always follow the header to the destination unit.
    
    


FIG. 7E shows the field format for source and supplemental fields. FIG. 7F shows a table of control signal usages for control field 741 or control field 747. FIG. 7G shows a device ID encoding for field 743. FIG. 7H shows terminology used for describing content of the source field in the header of messages for XB 279. FIGS. 7I, 7J, 7K, 7L, 7M, and 7N show a multi-part table (Table 3) describing internal Bedrock message source and supplemental fields. FIG. 7O is a table (Table 4) of the Xsel select-encodings for XB 279.
The header frame contains the source and supplemental fields, the message type (command) field, and 37 bits (39:3) of valid address. Subsequent data frames contain 64 or 128 bits of data, plus a bit to indicate an uncorrectable data error (UCE). The UCE bit is set if an uncorrectable error was encountered for that data word, such as a double bit error in memory. Note that the quadword data format is explicitly divided into DataEven and DataOdd doublewords. Whenever quadwords must be broken up into doublewords for transmission along a narrower interface, DataEven is transmitted first. If a doubleword of valid data is sent across the quadword interface, it is assumed to reside in DataEven.
FIG. 7G (Table 2) specifies the values that are contained in the Source and Supplemental fields of the header frame. The general format of the identifiers used in the these fields is shown in FIG. 7E. The Node ID corresponds to the Router Network Address [39:32] (when the system is operating in its default M-mode). The node address space (total memory addressable in a node) is therefore Address[31:0], allowing up to 8 Gigabytes of addressable memory per node. FIG. 7H specifies Terminology for Describing Content of Source Field in Header. The Source field (illustrated in FIG. 7E) identifies one of the following:

    
    
        For directory revision messages (such as XFER or SHWB) headed out the network interface, it identifies a coherency request initiator (that is, a source).
        For other messages going to the network interface, the Source field on the forwarded request identifies the destination address of the third party (illustrated in FIG. 7H) in the coherency transaction.
        For all other messages, it identifies a coherency request initiator (that is, a source). There are two types of invalidates inside the Bedrock:
        an invalidate plus bit vector, which is only sent to the LB, is referred to as a local invalidate (LINVAL),
        the normal invalidate, which is sent to a PI (local or remote), is referred to as an invalidate (INVAL).
    
    


The table shown in FIGS. 7I-7N details Source and Supplemental field contents for all Bedrock transactions. Some of the abbreviations used in this table are described as follows:

    
    
        Init—initiator of the original transaction. 3 bit field points to a DeviceID encoding, as detailed in Table 2.
        Send—sender, 8 bit node ID of the node sending the current message. 1 Owner—the owner of the cache line referred to by the address in this header. Used to generate revision messages. Owner will be either the initiator or the sender.
        Priority—priority level of the coherence request.
        AckCnt—acknowledge count expected as the result of invalidates sent. This number is the total number of invalidates sent minus 1. 1 WRB—write request buffer resource tag number of current write transaction.
        Target—identifier of the intervention target.
        T-Rex/BCast—two bit field which specifies which TRex to send an invalidate to. Can also specify a broadcast to both TRexs.

Overview of XB 279

    
    


FIG. 8 is a block diagram of one embodiment of XB 279.
The crossbar unit (XB) 279 of node controller 75 provides connectivity between the two PI 270s, the MD 275, II 273, LB, and NI 274 units in a fair and efficient manner. The XB 279 supports the flow of messages in Bedrock internal format along two virtual channels, multiplexed across the physical channel(s) connecting each unit to the XB 279. The XB 279 is designed for minimal latency under light loads by means of buffer/queue bypass paths and arbitration hints, and maximum throughput under heavy loads by means of per virtual channel arbitration requests and a wavefront arbiter. Message ordering between each pair of units is maintained within each virtual channel. Messages targeting different destination units from a single source virtual channel may be transmitted in any order. Messages along different virtual channels may be interleaved across an interface or along a physical channel at the flit level. (A flit is the smallest atomic, flow-controlled transfer unit supported by an interface to the crossbar).
This section uses the following unit-centric (not XB-centric) acronyms:

    
    
        xIQ=x unit's input queue that receives messages from the XB 279 (for example, PIQ=a processor interface's input queue)
        xOQ=x unit's output queue that holds messages awaiting transmission to the XB 279 (for example, NOQ=network interface's output queue)
    
    


In one embodiment, the XB 279 resides physically in the approximate center of the node controller 75, as it must communicate directly with each of the functional units (MD 275, II 273, LB 278, NI 274, and two PIs 271 and 272). The XB 279 is divided into a set of modules that each interface directly with a functional unit, and a set providing central connectivity and arbitration.
FIG. 8 is a block diagram of the XB architecture. In the notation shown in the figure, a dual-FIFO refers to two virtual channel FIFOs within a single buffer memory structure, a quad-FIFO referring to four virtual channels in an analogous structure. Dual bank refers to the width of the FIFO write port. The memory output queue (MOQ) requires dual banked FIFOs to sustain 3.2 GB/sec. of bandwidth.
Datapath Crossbar
This centrally located module contains an 8-input by 6-output crossbar. The crossbar datapath is 67 bits wide for all inputs and outputs, providing 1.6 GB/s of data bandwidth per port at a 5 ns clock. A single cycle is spent traversing the crossbar datapath: data is registered before being presented to the crossbar datapath, and flows into a register after the output multiplexer.
Data transfers are orchestrated by the unit output queues and the arbiter working in tandem. Data, valid and flit tag information are provided by the source output queue. Crossbar select lines are controlled by the arbiter and registered as one-hot busses to minimize fall-through latency.
Unit Output Queues
The unit output queues (the “OQs”) provide buffering for outgoing unit messages (destined for the XB 279) while they arbitrate for datapath resources. (Note: XB nomenclature is unit-centric, not XB-centric.) In certain cases they are also used to provide rate matching between disparate XB and unit bandwidths (MOQ, NOQ—only when SN0Net is being used, IOQ, as well as a point of synchronization for units asynchronous to the core (POQ, IOQ).
The OQs have two major interfaces: a unit interface and an arbiter/datapath interface. The unit interfaces are customized to the unique requirements of each unit, and detailed in the sections that follow. The arbiter/datapath interface is uniform across the OQs.
Across all OQ interfaces, message destinations are specified using the Xsel associated with the destination unit. This encoding, described in Table 4 (shown in FIG. 7O), is consistent with the router network header format (in one embodiment, the present invention uses a router network such as described in U.S. Pat. No. 6,085,303 issued Jul. 4, 2000 and entitled “SERIALIZED, RACE-FREE VIRTUAL BARRIER NETWORK”, U.S. Pat. No. 6,230,252 issued May 8, 2001 and entitled “HYBRID HYPERCUBE/TORUS ARCHITECTURE”, U.S. Pat. No. 5,970,232 issued Oct. 19, 1999 and entitled “ROUTER TABLE LOOKUP MECHANISM”, application Ser. No. 08/971,184 filed Nov. 17, 1997 and entitled “MULTI-DIMENSIONAL CACHE COHERENCE DIRECTORY STRUCTURE”, and U.S. Pat. No. 6,101,181 issued Aug. 8, 2000 and entitled “VIRTUAL CHANNEL ASSIGNMENT IN LARGE TORUS SYSTEMS” all of which are incorporated by reference), minimizing the amount of format translation required at the network interface. Note that the XB 279 supports a superset of the router network encodings to address Bedrock-internal only message destinations.
Note that the Valid (from the unit to the output queue) corresponds to a single cycle flit, except for NI 274 where it corresponds to either 1 header or two consecutive data flits. The Tail comes with last flit of the message, except for NI 274 where it comes with the Valid. See FIG. 7O showing Table 4. Note that setting Xsel[2] to 0 results in four SN0-compatible encodings (with the Local Block replacing the NI 274 as the destination for vectors and NI register PIOs). Xsel[2] can also be thought of as a “sub-node” select bit.
To reduce latency through an empty OQ, the message buffers may be bypassed entirely, or the data may be written and read from the buffers in the same cycle. The details of the crossbar arbitration are hidden from the unit, which need only be concerned with proper data transfer and flow control on the OQ interface.
Unit Input Queues
The unit input queues (the “IQs”) provide buffering for data that has traversed the XB 279, but has not yet been processed by its destination unit. Their primary role is to provide rate matching and synchronization between the XB 279 and the receiving unit. If sized properly, they isolate XB message flow from the effects of lower bandwidth units, and allow higher bandwidth units to accumulate incoming packets until a transfer at the higher rate is possible.
Since the NI 274 is synchronous and bandwidth-matched to the XB 279, the NI 274 does not have an IQ. Fill level information from the IQs is used by the arbiter to flow control messages from the OQs. In the case of the NI 274, SN1Net flow control information is used to provide back pressure across the XB 279.
The MD 275 requires input buffers to provide rate matching between the XB 279 and the higher bandwidth memory interface. To allow a tighter coupling between the MD 275 and the input buffers, the buffers are placed in the MD unit 279 rather than in an XB IQ. The MD 275 also provides flow control signals to the arbiter.
Note that the Valid (from XB 279 to the IQ or unit) is consistent throughout all the queues in that it corresponds to a single-cycle flit. The Tail correspond to the last flit of the message, except for NI 274 where it is asserted in the first cycle of the two cycle transfer.
Arbiter
The arbiter provides low latency arbitration for uncontested ports via bypass arbitration, and efficient, high utilization via wavefront arbitration as resources become saturated. The arbiter must also ensure fairness for all units and correctness by disallowing message fragmentation within a virtual channel.
The basic unit of data transfer supported by the arbiter is a two clock entity, composed of either a single clock header followed by an unused cycle, a single clock of data followed by an unused cycle, or two data clocks. Note that single clock data transfers are only used for the last transfer of an odd-length data payload. The arbiter receives requests for two cycles of XB bandwidth from the units every other cycle, and grants bandwidth to a particular destination in the same cycle.
Error Handling
The XB 279 will, in some embodiments, encounter errors with some of the following root causes:

    
    
        1. design flaws in the Bedrock (in the units or in the XB 279 itself).
        2. external component failures whose effects are not filtered by the units before reaching the XB 279.
        3. system configuration errors.
    
    


While these errors may manifest themselves in many ways, the crossbar will only detect errors of the following types:
4. Invalid Xsel destination encodings from unit to OQ (BAD_XSEL).
5. Queue overflow, from unit to OQ or OQ to IQ.
6. Queue underflow, due to OQ grant or IQ read of empty queue.
7. Lack of forward progress from an IQ to unit (DEADLOCK_TIMEOUT).
8. Missing tail from a unit to an OQ (TAIL_TIMEOUT).
Spew Mode
The crossbar provides a debug mode in which all data leaving a particular OQ or all data entering a particular IQ can be echoed (“spewed”) to the NI 274. Once reaching the NI 274, the data will be converted to network format and sent out the SN1Net port (as normal) for capture via a suitable test chip (one that allows examination of the signals on the link) that is embedded in the link. Note that this mode is only useful for single node system debugging, as the NI 274 port cannot be shared by spew traffic and normal traffic.
POQ
In one embodiment, there are two instantiations, POQ0812 and POQ1816, of the processor interface's output queue, one for each PI 270. In other embodiments, even more instantiations of the PI port, or a plurality of instantiations of one or more of the other ports, are used.
Each POQ accepts request and reply messages for a PI 271 or 272 at the PI clock frequency. Internally, the POQ has a synchronizer to bring the PI data into the core clock domain. In the core clock domain, the POQ presents PI requests and replies to the XB arbiter and datapath. There is a Synchronous mode (pin) which can be set when the PI 270 and the core runs synchronously. This causes the POQ to bypass the synchronizer and save 1.5 cycles.
The PI 271 or 272 is flow-controlled by the POQ 812 or 816, respectively. The POQ indicates the number of free entries available for new data in the request and reply queues. When the number of free entries reaches 0, the PI 270 is no longer permitted to send data to the POQ.
The PI 270 needs to know the number of entries so it can properly flow control the T-Rex+processor (a simple Full flag is not sufficient for this).
Since there are two processors connected to each PI 270, the naming convention used is, for example, PI_POQ_RqValid_PO, PI_POQ_RqValid_P1.
The core-side clock domain of the POQ has special logic for creating revision messages in the reply channel. Some intervention responses from T-Rex+require revision messages, with or without data, to be sent to the home node's memory, depending on the command type and the supplemental fields. The following equation details revision message types:
With Revision Bit (bit 55) set, RevisionMessage command is one of

    
    
        (‘BR_CMD_UACK|‘BR_CMD_SACK.|‘BR_CMD_EACK|‘BR_CMD_RACK|‘BR_CMD_URESP|‘BR_CMD_SRESP|‘BR_CMD_ERESP)
    
    


Revision is LongLong type if (RevCmd==‘BR_CMD_SXWB) |(RevCmd=‘BR_CMD_SHWB);
Revision id is LongShort type if (MsgCmd==‘BR_CMD_ERESP) (RevCmd==‘BR_CMD_XFER).
RpFree is asserted whenever an entry is freed from the Reply buffer, but RqWrFree is only asserted when the packets are longer than two flits are freed.
No RqWrFree is asserted for Read since Read Request is not longer than two flits, while 15 RqWrFree pulses are asserted for block write (flits 3-17), since PI 270 needs to reserve the two entries to be able to do a partial write in case of any error. For graphics Request (with no error expected), RqWrFree is asserted whenever an entry is freed.
PIQ
The processor interface input queue (PIQ) is a FIFO pair with separate request and reply channels. The XB side of the PIQ runs at the core clock speed, while the PI side of the PIQ runs at the PI clock speed. Thus, the PIQ implements an asynchronous boundary. When valid data appears at the PI side of the PIQ, valid lines are asserted until the PI 270 reads data from the PIQ.
MOQ
To sustain full memory bandwidth, the memory unit's output queue (MOQ) block provides three replicated queuing structures (MP0, MP1, MMQ), attached to three separate XB 279 ports. The MD 275 sends messages into each queue based on their destination. There is a single queue dedicated to each PI 270 (MP0 and MP1), and a third queue within which LB, NI, and II messages are held (MMQ).
Each MOQ structure is made up of separate header (MOQH) and data (MOQD) FIFOs. MOQH and MOQD have separate interfaces to streamline connecting to the MD 275 datapath. The MOQH is divided unequally into request and reply channels (mostly reply), since most outgoing traffic is on the reply channel. The MOQH and MOQD also have bypass paths. The limited set of data bearing requests from the MD 275 travel entirely through MOQH, eliminating the need for a request channel on MOQD. To accept the 3.2 GB/s data rate from the MD 275, the MOQD has dual buffers which are written simultaneously by the MD 275, and read alternately by the XB 279.
When transferring a doubleword of data, the MD 275 may present the data on either side of the quadword interface. The DwOffset signal indicates whether DataEven or DataOdd is used.
To reduce remote read latency, the MD 275 will at times present a header to the MOQ before all checking is complete. There are two scenarios under which this takes place:

    
    
        1. Hdr {Rq,Rp} dst is asserted and on the following cycle, during which the header itself is transferred, the MD 275 encounters an ECC error and must cancel the message. The MD 275 asserts the Abort signal in this second cycle, indicating that the header should be dropped and all state associated with this message cleared. In the same (second) cycle, another Hdr {Rq,Rp} Valid (on the same channel) may be asserted, and that message must also be cancelled.
        2. For messages heading towards the NI 274 (on their way to a remote node), an access error may be detected in the cycle after the header has been transferred to the MOQ. In these cases, the MD 275 asserts the AE signal on the third cycle of the transfer, and the MOQ and NI 274 cooperate to ensure that the header is dropped. There may be residual message-in-progress state left in the XB 279 as a result of this cancelled transfer. The MD 275 guarantees that it will resend a message to the NI 274 along the same channel, clearing up any outstanding XB state. Note that the original Hdr {Rq,Rp} Valid may have not been aborted on the second cycle, and encountered an access error on the third. Also note that any header immediately following (on the same channel) a header that ultimately encounters an Access Error must be aborted. A single cycle of delay after the AE header is sufficient to again allow a valid transfer. If AE is asserted in the third cycle, MD 275 guarantees that there is no Hdr {Rq,Rp} Valid on the second and third cycles.
    
    


Flow control between the MD 275 and each of the MOQs is credit based. On reset, the MD 275 assumes that the following space is available in each MOQ:

    
    
        1. 4 request headers/DW data entries in MOQH
        2. 12 reply/DW data entries in MOQH
        3 24 QW data reply entries in MOQD
    
    


The MD 275 must maintain a count of available buffer space for each MOQ. On transferring a header or data cycle to a particular MOQ, the MD 275 must decrement the corresponding credit count. The HdrRq/RpFree outputs from each MOQ indicate that a single cycle header/doubleword data entry has become available in MOQH. DataFree indicates that a quadword or quadword-aligned doubleword entry has become available in MOQD.
FIG. 10 and Table 20 (shown in FIG. 9A) provide a detailed list of the MD/MOQ interface signals.
MIQ
There is no MIQ in XB 279. The XB 279 attaches directly to the MD 275 input datapath, allowing the MD 275 to better manage queued messages. The XB's 1.6 GB/s port can only provide half of the memory's peak bandwidth.
The MD 275 provides separate flow control for several XB sources, allowing requests from certain sources to make progress while others are stalled until their buffers are freed.
To improve the latency of remote reads, the NI 274 forwards remote read requests to the MIQ as soon as they are received, bypassing the XB 279 entirely. Reads that are received from the NI fast path are speculative in nature, and are only forwarded across the MD 275 interface when the MIQ cannot make use of the interface otherwise. The speculative headers are presented for a single cycle only, and are identified by the HdrSpec signal associated with HdrAvail.
Note that speculative hints sent from the NI 274 to the MD 275 do not affect the operation of the NI.fwdarw.NOQ interface in any way. Table 21 (shown in FIG. 10A) lists in detail the interface signals between the XB 279 and MD 275.
NOQ
The network unit's output queue (NOQ) includes four channels that correspond directly to the router network (175)'s four virtual channels. Each individual channel is treated as a FIFO, and each presents requests to the arbiter. By controlling the grants returned to the NOQ, the arbiter ensures that the four virtual channels are properly merged into the two virtual channels supported by the rest of the Bedrock.
Data is transferred across the NI-NOQ interface in 2-cycle flits, in a manner analogous to that used between OQs and IQs within the XB 279. Valid cannot be asserted to the NOQ on consecutive cycles. Each assertion of Valid represents either a single-cycle Bedrock header followed by an unused cycle, a single cycle or data followed by an unused cycle, or two cycles of data. Even-length payloads are sent as a series of two-cycle data flits, with the last transfer of an odd-length payload being a valid single-cycle of data followed by a dead cycle.
There is no explicit differentiation between a single-cycle and a dual-cycle data flit on the NI-NOQ interface. The NOQ uses the Size field provided with the header's Valid pulse to distinguish the two. The NOQ decodes the header command size bits and samples only the first doubleword of data in the last flit of the message. Also note that although the UCE bit is defined for each doubleword of data in crossbar format, it is only valid on the first cycle of a data flit from the NI 274 to the NOQ.
The NI 274 forwards flits to the NOQ before link-level checking is complete. In cases where a flit must be dropped due to a link-level error, the NI 274 will assert Squash a cycle after asserting Valid.
NOQ-NI interface flow control requires the NI 274 to know the NOQ buffer depth. The NI 274 must keep track of all buffers consumed (by means of Valid transfers), and all buffers freed (as indicated by Free pulsed from the NOQ). The buffer depth is measured as the number of 2-cycle flits that can be stored, and a Free pulse indicates the release of a 2-cycle flit buffer. A Valid followed by Squash is dropped by the NOQ and thus will not result in a Free pulse.
See FIG. 11 for an NOQ timing diagram. Note that the figure includes SN1Net LLP and internal crossbar signals. These help illustrate the expected fall-through latency from SN1Net onto the crossbar, but do not directly affect the NI-NOQ interface. The interface signals are listed in Table 22 (shown in FIG. 11A).
NIQ Functionality
The NI 274 does not have an input queue for incoming XB traffic. The direct connection of the NI 274 and the XB 279 dictates that messages be transmitted across the interface in the 2-cycle flit format supported by the XB 279. Each assertion of DataValid signals the first cycle of a flit being transmitted. The unused cycle after each header allows the NI 274 to expand Bedrock headers into 2-cycle Router Network headers at full rate. To allow the NI 274 to format outgoing messages with minimal latency, the DataTail tag is provided on the first cycle of the 2-cycle flit. There is no distinction between single and dual data cycle flits on the interface.
The two channels of traffic supported by the XB (request/reply) are demultiplexed onto the four router network channels by the NI 274, in a manner which is invisible to the crossbar. The NI 274 combines flow-control information from the four network virtual channels to apply back-pressure to the two channels seen by the crossbar.
The XB.->NI protocol is complicated by a latency-reducing optimization from the memory system. To support minimum latency responses to remote memory requests, the MD 275 sends response headers to the XB (headed for the NI 274) before access rights checking is complete. When access checking results in an error, the MD 275 asserts the Access Error (AE) signal to the MOQ and the NI 274 (see FIG. 12). If the response header passes through the MOQ and the crossbar with minimum latency, the header DataValid will arrive simultaneously with the AE signal. The AEValid signal from the MOQ to the NI 274 is asserted whenever this minimal latency path is taken. At the NI 274, the Access Error (AE) bit from the MD 275 is combined with the AEValid bit from the MOQ to gate XB DataValid, as illustrated in FIG. 11B. See Table 23 (shown in FIG. 11B) for a description of the full set of XB/NI interface signals.
LOQ
The local block's output queue (LOQ) is a FIFO pair. It need only be sized large enough to ensure that outgoing invalidates can be sent at full network bandwidth. The LOQ has no bypass path.
The LOQ interface signals are detailed in Table 24 (shown in FIG. 12A). A header or single cycle of data is considered transferred if:

    
    
        (RqAvail && RqReady)∥(RpAvail && RpReady)

Rq and RpReady may be asserted together. Rq, RpAvail are mutually exclusive.

LIQ

    
    


The local block's input queue (LIQ) presents independent request and reply interfaces to the Local Block. The request FIFO will buffer invalidate requests (as well as other requests to the local block), and should be large enough to hold all of the coarse invalidates that can be issued from the four processors on the local node (4 invalidates per processor=16 invalidates per node).
When the LIQ has request flits to deliver to the LB, it asserts the RqAvail signal. The LB independently asserts RqReady when it can accept a request flit. When both RqAvail and RqReady are asserted in the same cycle, a data transfer is defined to have occurred. The LB may consume multiple flits in the same cycle by asserting multiple Ready signals in the presence of multiple Avail signals.
The only reply messages flowing through the LIQ are vector replies. The LB guarantees that vector responses can always be consumed at full rate. The LB also guarantees that any reply messages erroneously arriving at the LB will be consumed at full rate. As a result, a Valid signal from the LIQ is used to indicate a reply transfer rather than a Ready/Avail protocol, and no reply storage is allocated in the LIQ.
The LIQ/LB interface signals are detailed in Table 25 (shown in FIG. 12B).
IOQ
The IO interface's output queue (IOQ) is a FIFO pair with separate request and reply channels. Data from the II 273 is written into the IOQ at the speed of the II 273, which is asynchronous with respect to the Bedrock core clock. Data is read by the XB 279 at the Bedrock core speed.
To simply implementation, the IOQ and POQ are instantiated from the same source logic. That is, they are identical logically. In various embodiments, special features are enabled or disabled depending on whether the logic is serving the II 273 or PI 270.
The exception is Arbitration Trigger in IOQ. Arbitration Trigger in IOQ enables the IOQ to wait a programmable number of cycles after seeing a Header, before it starts to arbitrate. This gives the IOQ a chance to have enough entries such that it can use the arbiter and the bus optimally without any unused cycle. The Arbitration Trigger register can be set to: II frequency/Core frequency*number of cycles to transfer a cache line.
The IOQ/II interface signals are detailed in Table 26 (shown in FIG. 12C).
IIQ
The IO interface's input queue (IIQ) is a FIFO pair with separate request and reply channels. Data from the XB 279 is written into the IOQ at the speed of the Bedrock core, which is asynchronous with respect to the II clock. It is presented to the II 273 through separate request and reply registers.
To simply implementation, the IIQ and PIQ are instantiated from the same source logic. That is, they are identical logically, with the exception of Arbitration Trigger in IOQ. Arbitration Trigger in IOQ enables the IOQ to wait a programmable number of cycles after seeing a Header, before it starts to arbitrate. This gives the IOQ a chance to have enough entries such that it can use the XB bandwidth (arbiter and the bus) optimally without any unused cycle. The Arbitration Trigger register can be set to: II frequency/Core frequency*number of cycles to transfer a cache line. If the Tail of a message is seen, it can immediately arbitrate without waiting for the programmed number of cycles.
The IIQ/II interface signals are detailed in Table 27 (shown in FIG. 12D).
Arbiter and Datapath Interface
The arbiter combines per virtual channel requests and message framing information from the OQs with flow control information from the destination IQs/units to grant crossbar bandwidth fairly and efficiently. To provide low latency under light loads and high-utilization under heavy loads, the arbiter supports two bandwidth request interfaces: the bypass arbiter interface and the wavefront arbiter interface, named respectively for the arbiter implementation that handles each.
The switch carries the data along with virtual channel tag, tail bit from the OQ source to the IQ or unit destination.
Bypass Arbitration
The arbiter supports bypass arbitration as a means of low latency, fixed priority arbitration. When a OQ is empty and idle, it can use bypass arbitration for new requests to minimize latency. To initiate bypass arbitration, the OQ asserts its appropriate request line at the beginning of a clock cycle (for a summary of all request lines, see the XB interface section, below.) If the requested IQ is free, and if there are no conflicting virtual messages in progress (“MIPs”), the bypass arbiter will grant the IQ to the requesting OQ. On the next clock, the OQ must provide data on the XB datapath, starting at the beginning of the cycle. Since this process does not give the OQ sufficient time to complete an FIFO read, the OQ must bypass the FIFO read stage and have the data staged for immediate transmission to the XB 279.
To simply the implementation, there are restrictions on when an OQ can request bandwidth from the bypass arbiter. Bypass requests can be made from an empty queue as long as no MIPs are outstanding on other channels.
To be able to request n cycles early, the units may need to speculate that they will need the XB bandwidth, but ultimately be unable to use it. To solve this problem, the arbiter supports speculative bypass requests. Once a bypass grant is received, data is presented to the XB datapath with the virtual channel and Xsel of the data. If these match the registered granted values, the data is considered valid at the destination IQ, otherwise the request is considered speculative and the request is ignored.
The bypass arbiter can be disabled via a XB_BYPASS_EN register. When disabled, bypGnt will never be asserted, and all message transfers will be controlled by the wavefront arbiter 1500.
Sample bypass arbiter interface signals are detailed in Table 28 (shown in FIG. 13).
Wavefront Arbitration
The arbiter also supports wavefront arbitration, which uses the XB bandwidth more effectively by maximizing the number of grants per arbitration, and provides fairness to OQ requesters through the age mechanism. An OQ may always request wavefront arbitration, and should assert wavefront arbitration requests to all destinations for which it has a valid packet at the head of a FIFO. The wavefront arbiter can assign grants more efficiently if it is presented with more requests.
The OQ must assert its wavefront arbitration request(s) at the beginning of a cycle. Towards the end of that same cycle, the arbiter will provide the OQ with a grant. The OQ then has one full cycle to complete its FIFO read, then it must provide data for the XB 279 on the next cycle.
FIG. 14 is a block diagram of one embodiment of an XB arbiter filter 1400 (the MOQ filter is shown). Before arbitration requests reach the wavefront arbiter, they are sent through the filter block 1400. The filter block prevents the mixing of two message streams on one virtual channel. If there are no other virtual channel MIPs targeting the same destination as an OQ request, that request is sent on from the filter block to the wavefront arbiter 1500 (see FIG. 15).
The wavefront arbiter is set up in a matrix form, although it is tilted to the side to minimize worst case timing paths. Rows in the wavefront matrix represent OQ sources, while columns represent IQ destinations. Each tile in the wavefront arbiter is the terminus of a filtered arbitration request line, and represents a particular OQ requesting a particular IQ. OQs may request several IQs in one arbitration round. OQs will be granted a maximum of 1 IQ per round. Note that the wavefront arbiter treats the MOQ as 3 OQs, as the MOQ can provide 3 data streams simultaneously. Thus, the MOQ can receive up to 3 grants in an arbitration round.
Wavefront arbitration tiles closest to the upper left corner in FIG. 15 are evaluated first, and therefore have the highest priority. If a request is granted at a particular tile, that information is propagated down and to the right as the granting tile de-asserts its Row Free (RFree) and Column Free (CFree) lines. Within an individual tile, a request can only be granted if the RFree and CFree lines are both asserted.
There are a total of 6 wavefront arbiters in the XB 279, each with a different priority set. Notice that the wavefront arbiter structure shown in FIG. 15 has a fixed priority, with POQ0 having top priority for PIQ0, POQ1 having top priority for LIQ, etc. Each of the 6 wavefront arbiters in the XB 279 represents a different priority ordering, and depending on which OQ has the oldest age packet bound for a particular IQ, the arbiter selects one of the wavefront arbiters to use.
The arb/gnt Interface Between the Arbiter and the OQs
XB requests and grants are pipelined two clocks ahead of the data to allow a full cycle for the OQ buffer memory to be read before the data is presented to the datapath. FIG. 15A shows a table (Table 29) of wavefront arbiter signals as an example.
Crossbar Arbitration Fairness
To ensure fairness and forward progress, the arbiter attempts to grant the “oldest” arb on the chip whenever possible. Oldest is defined by an aging protocol implemented at the OQs and forwarded to the arbiter. A new header arriving at the head of a virtual channel queue receives an age of 0. Until the message is complete, the age will be incremented at a rate determined by the arbiter. The aging rate enforced by the arbiter is programmable via the XB_AGE_WRAP register. Note that bypass arbitration is not fair, but any message that does not receive a bypass grant will immediately go into wavefront arbitration, which is fair. Wavefront requests have higher priority than bypass requests.
The arbiter priority module is constantly comparing the ages from each OQ. The oldest age is always selected and given priority according to its preferred ageXsel field. In the case of a tie, the priority block will select the winner according to a round-robin pointer. The pointer advances every grant cycle, regardless of the grant results. To prevent virtual messages from being cut off before ages have advanced to high levels, the robin pointer will not advance until at least one of the OQs has an and age of eight or more (half of its maximum value.)
The priority module requires a full clock cycle to complete the age comparison between all the OQs. Because of this delay, priority information always lags grant decisions by 1 cycle. Because of this delay, priority information always lags grant decisions by 1 cycle. To prevent new messages from inheriting the age of the previous message due to this lag, if the tail flit of a message receives a grant, the next requester from that OQ is treated as if it has a 0 age for one request cycle.
In the case of age ties, the arbiter uses a pseudo-random resolution function to choose a winner. This is important when ages saturate at the maximum value of 0xf, or when the arbiter age function is disabled. When a tie occurs, a winner is chosen at random from the pool or arbitrating OQs. The pseudo-random number is generated using a 15 bit Linear Feedback Shift Register (LFSR). The LFSR is driven by the polynomial X15+X+1, which provides an equal balance of 0's in 1's in a non-repeating fashion every 215 clocks.
Crossbar Flow Control
Several flow control signals are provided by each IQ (or the unit where no IQ is present) to handle the pipeline depth of the arbiter. The Full and FullIn1 signals must be asserted based on the queue fill-level. The queue fill-level must be updated on the cycle following a valid transfer from the crossbar.
FullIn1 must be asserted whenever there is space available for one or fewer crossbar flits composed of a header or up to two data cycles. Full must be asserted whenever there is not enough space available to handle a single crossbar flit. In queues where headers and data are stored separately, the lack of space for either must cause Full/FullIn1 to be asserted.
See FIG. 16 for a timing diagram illustrating the relationship between crossbar DataV(alid) and the Full, FullIn1 signals.
Arbiter Connectivity
Signals within the arbiter are named with two capital letters specifying the source unit (P0, P1, M0, M1, NO, IO, or LO) followed by an action (arb, gnt, mip), followed by two capital letters specifying the destination input unit (PI, MI, NI, II, LI). Table 30 (see FIG. 16A) summarizes the virtual channels that each queue can use to request input queues. Table 31 (see FIG. 17A) summarizes the virtual channels that each queue can use to request input queues.
Datapath Crossbar Interface
Data transfers along the crossbar datapath are qualified with a data valid (DataV) control signal, and tagged with virtual channel (DataVch) and message tail (DataT) information. A single cycle is spent traversing it: data is registered before being presented to the crossbar datapath, and flows into a register after the output multiplexer. Crossbar select lines are controlled by the arbiter and registered as one-hot busses to minimize fall-through latency.
XB Structures
The following sections describe each XB queue structure separately.
POQ Structure
The POQ structure is similar to IOQ structure described below.
MOQ Structure
The MOQ is split into separate header (MOQH) and data (MOQD) queues. The MOQH contains two independent FIFOs (first-in-first-out registers), one for each virtual channel. The data MOQD is a reply-only data FIFO. A FIFO design was chosen over a DAMQ (dynamically allocated multi-queue memory) design for the MOQ because performance sensitive traffic from the MD 275 is of a predictable nature which would not significantly benefit from a DAMQ control structure. The FIFO reduces control logic overhead, and separate independent FIFOs allow request and reply traffic to interleave arbitrarily.
MOQ Data Buffers
FIG. 17 shows a block diagram of MOQ data buffers 1700.
Request message data travels entirely through MOQH. Short data responses may travel through either queue, based on which section of the MD 275 (header/directory vs. data/memory) generated them. Long (cacheline) data responses always travel through MOQD.
The MOQ request and reply FIFOs are built with suitable FIFO memories. The MOQD uses double-banked FIFOs to accept full bandwidth traffic from the MD 275, while the banks are read alternately to match the bandwidth of the XB 279. The MOQH FIFO is shared among request and reply FIFOs to reduce multiplex levels in the datapath and save on FIFO overhead.
The dual-banked MOQD is managed as a set of quarter cacheline (QCL) response buffers (one QCL=two clocks in each bank). Cacheline responses from the MD 275 consist of four QCL writes, and all partial responses (including F&OP) take up a full QCL. The MOQH contains single clock headers as well as header+single data packets. MOQH reply headers are decoded as they leave the MOQ to determine how many MOQD entries are associated with the header.
Since the MD 275 must reserve MOQ space before issuing a request to the memory, the MD 275 keeps a shadow copy of the fill levels of MOQD and MOQH. Flow control is achieved by a signal per queue that indicates that an entry (single header or QCL of data) has been drained.
NOQ Structure
The NOQ contains the SN1Net network virtual channel receive buffers. Each of the four virtual channel buffers is 16 entries deep, where each entry corresponds to a router network flit-a header or 128 bits of data. Each channel may contain any mix of headers and data. The NOQ buffers are structured as four independent FIFOs.
NOQ Buffers
FIG. 18 shows a block diagram of NOQ buffers.
FIFOs were chosen over DAMQs for the NOQ to reduce control structure overhead. Performance critical messages tend to be read requests to the MD 275 and read responses to the PI 270, and since these message types will travel on separate virtual channels they will not interfere with each other. Writeback messages to the MD 275 will share the request channel with read messages to the MD 275, but this effect will be countered somewhat MD 275 request processing favoring reads and by virtual channel adaption in the network encouraging reads to take the emptier channels. Since each of the four virtual channels has an independent FIFO cable of XB arbitration, the effects of network virtual channel adaption are carried forward to the Bedrock XB 279.
The four logical FIFOs in the NOQ are implemented across a dual banked FIFO structure. This structure allows each FIFO to be 65 bits wide, and requires that headers be written and read out across both banks.
IOQ Structure
FIG. 19 shows a block diagram of IOQ buffers.
The IOQ must synchronize traffic coming from the II 273 to the hub core clock domain. This is done with a standard double synchronizer applied to a gray code counter. When the POQ receives a message on the hub core side, it will arbitrate for the XB 279 once the entire message is received. This is done for block length messages to prevent the higher bandwidth XB 279 from underrunning the IOQ FIFO. The IOQ is divided into independent request and reply FIFOs, although they do share the same buffer memory FIFO.
PIQ Structure
The PIQ receives data from the XB 279 and writes it into an FIFO to be read by the PI 270. There are 64 entries for each of the Request and Reply channels. In Synchronous mode, the data can be bypassed from the XB 279 to PI 270.
MIQ Structure
FIG. 20 shows a block diagram of MIQ buffers.
The MIQ is divided into four logical FIFOs, implemented in 3 FIFOs. Headers are buffered in a single bank, request/reply MIQH, and a dual banked request/reply MIQD holds associated data. The MIQD buffers are divided into 3 block request entries and 1 block reply entry, as request data to the MD 275 is more common than reply data.
MIQ always presents a single header to the MD 275. If only one virtual channel contains a valid header, the MIQ will present the valid header and indicate request or reply. If the MIQ has a valid header in both channels, it will always present the reply channel to the MD 275, as long as the MD 275 is not asserting its reply channel full signal. When the MD 275 is ready to consume a header, it asserts the HeaderRead signal, which frees that entry off the queue.
IIQ Structure
The IIQ receives data from the XB 279 at the core data rate of 1.6 GB/s and writes it into the GRA in either the request or reply FIFO. After the write pointer is synchronized to the IO clock domain, it can be read by the II 273 at 0.8 GB/s. There is no bypass datapath in the II queues.
LIQ Structure
FIG. 21 shows a block diagram of LIQ buffers.
The LIQ provides a dedicated queue for PI0 request from NI 274. PI0 request is rare, but higher priority, to avoid the Request-Request PI0 deadlock. While servicing LINVAL, LB needs to be able to service an incoming remote PI0 request from NI 274. The only request NI 274 can make to LB is PI0 request. Requests can bypass the FIFO, and Replies are written to the output register, and never enter the FIFO. The Reply register is free running since LB can process Reply every cycle with no delay.
Queue Sizes & Types
In one embodiment, the XB queue structures are implemented with IBM CMOS 6s Low Power Register Arrays (FIFOs) (available from IBM Corp of Burlington Vt.), or with standard registers where the queue size does not justify the FIFO's gate overhead. Table 32 (shown in FIG. 22) summarizes the size and type of each queue in the XB 279.
RLMs
FIG. 22 details the breakdown of the XB functional units into RLMs for physical design.
Memory/Directory Interface
The Bedrock (one embodiment of node controller 75) Memory/Directory Interface (MD) 275 controls access to all the memory in a Bedrock system. In addition to performing the standard memory controller operations, such as reading and writing memory, the Bedrock MD 275 keeps track of exactly which processors and which IO interfaces are currently using every cache line in the system. On every access, the Bedrock MD 275 checks this table (called the Directory) and generates the necessary messages in order to maintain cache coherence.
The Bedrock MD 275 provides enough bandwidth to fully satisfy any single class of requesters. In other words, all four processors or both directions of the SN1 net or both directions of the IO interface can access memory at full bandwidth. The Bedrock MD 275 also provides the arbitration structures necessary to fairly and efficiently allocate bandwidth when multiple requesters are accessing memory. The “Architecture” section contains an architectural level overview of the MD 275, covering the following topics:

    
    
        Memory Addressing
        Page Handling
        Interfaces
        Message Types
        Protection Model
        Page Counters
        Fetch-And-Op
        Backdoor ECC
        Backdoor Directory
        Junk Bus
        SDRAM Initialization
        DDR-SDRAM Initialization
        Refresh
        Built-In-Self-Test
        SN0 Compatibility

Subsequently, the major architectural blocks are described, of which there are three (illustrated in FIG. 31):

    
    


Issue Block (IB) 3110: Takes in all new messages and issues them in an efficient and fair order to the rest of the memory system. Issues address and control signals to the DRAM.

    
    
        Memory Block (MB) 3118: Transfers data from the DRAM to the XBAR or from the XBAR to the DRAM.
        Directory Block (DB) 3116: Reads the directory data, creates any necessary message headers, computes the new directory data, and writes it back.
    
    


Then implementation information that crosses multiple architectural blocks is discussed:

    
    
        DDR Synchronization
        Timing Diagrams

Architecture

    
    


This section first gives a detailed description of the overall memory system design. The following sub-sections then explain the higher level architectural features built on top of the memory system.
Memory System
The Bedrock memory system includes a Bedrock chip, some clock buffers, a flash prom, a UART, four banks of LEDs, and two, four, six, or eight DIMMs (Dual Inline Memory Modules).
Each Bedrock DIMM consists of one or two 72-bit sub-banks of memory DRAM and one or two 16-bit sub-banks of directory DRAM. FIG. 32 shows a diagram of the front of a Bedrock DIMM. In a two bank DIMM, the back of the DIMM would be the same as the front.
DIMMs can be populated (or not populated) in groups of two, resulting in a 128-bit wide memory system (plus 16 bits of ECC and 32-bits of directory). In order to accommodate different system uses, the Bedrock MD 275 supports many different sizes of DIMMs. Each set of two DIMMs must be of the same size.
The Bedrock MD 275 supports the following DIMM sizes: 32 MB, 64 MB, 128 MB, 256 MB, 512 MB, and 1 GB. Table 58 (see FIG. 32A) shows information on each potential DIMM configuration (shaded rows are the most likely DIMMs the SN1 system will actually use).
The Bedrock MD 275 supports two different types of DIMMs: DDR-SDRAM-std, and DDR-SDRAM-prm. DDR-SDRAM are special versions of SDRAM that output data at twice the rate that they receive addresses. All production Bedrock systems will use DDR-SDRAM.
Standard (std) DIMMs contain one bank of directory DRAM for every two banks of memory DRAM. Premium (prm) DIMMs contain a bank of directory DRAM for every bank of memory DRAM. Systems containing up to 128 processors can use Standard DIMMs. Premium DIMMs will work in any system (up to the max of 1024 processors).
The address bus from the Bedrock chip to the DIMMs always runs at 100 MHz. The data bus between the Bedrock chip and the DIMMs runs at 200 MHz. The maximum bandwidths is therefore 3.2 GB/s.
Directory Organization
The Bedrock MD 275 maintains system cache coherence by checking a directory memory on every coherent access of the memory system. Since each access changes the state, the Bedrock MD 275 must perform a read-modify-write of the directory memory in parallel with every read or write of the data memory.
In a system populated with DDR-SDRAM-std DIMMs, there is one bank of directory DRAM for every two banks of memory DRAM. As DIMMs are populated in groups of two, the Bedrock MD 275 can share the two banks of directory DRAM (one on each DIMM) between the two banks of memory DRAM (spread across the two DIMMs). This results in an effectively 16-bit wide datapath that could enter the Bedrock MD 275 on either side of the 32-bit directory datapath. As the standard directory entry is 32-bits, it is read and written over two cycles. FIG. 33 shows a schematic illustration of a standard directory system (with two banks of memory DRAM and one bank of directory.
In a system populated with DDR-SDRAM-prm DIMMs, there is one bank of directory DRAM for every bank of memory DRAM. In this case, the directory banks are spread across the two DIMMs in the same manner as the data, allowing the full 32-bit directory datapath to be utilized. As the premium directory entry is 64-bits, it is also read and written over two cycles. FIG. 34 shows a schematic illustration of a single premium DIMM in a premium directory system (with two banks of memory DRAM and two banks of directory DRAM).
Memory Addressing
A maximum memory configuration in M-Mode of eight 1 GB DIMMs results in an address space of 8 GB. A maximum configuration in N-mode of four 1 GB DIMMs results in an address space of 4 GB. The Bedrock MD 275 allocates two blocks of 1 GB for each set of two DIMMs. The DIMMs with two physical banks use both blocks, while one bank DIMMs just use a single block. If a set of DIMMs does not completely fill the 2 GB space, the OS is expected to allocate around the resulting gaps in memory. The minimum memory configuration would be two 32 MB DIMMS or 64 MB.
All of the DDR-SDRAM supported by the Bedrock MD 275 contain four internal (logical) banks. The Bedrock MD 275 interleaves across these four logical banks using the lowest possible address bits (right above the cache line size of 128 bytes). Table 59 (see FIG. 34A) shows how each address bit is used. The Bedrock MD 275 drives all the pins shown even if the smaller DIMMs might not receive or interpret every bit. Memory.
Directory Addressing
On every coherent transaction, the Bedrock MD 275 performs a read-modify-write of the directory entry. In addition, it might perform a read of the protection entry and/or a read-modify-write of the page counter entry. The directory entry, protection entry, and page counter entry are all stored in the directory. The DIMM, Physical, Logical, and RAS addresses shown in Table 59 are the same for both memory and directory addresses. However, the directory CAS addresses are different for each type of entry. In the CASDir, CASProt, and CASCount fields, the constants are defined as follows: D=0, P=1, C=0, x=0, and Rgn refers to bits 4:0 of the protection region.
Page Handling
The SDRAM and DDR-SDRAM used in Bedrock, like all DRAM, are accessed using a row address and a column address. Multiple column addresses can be read sequentially without any extra delay. In order to change rows (also called pages), the DRAM must close the old row and only then open the new row. For this reason, an access to a new row is much more costly than an access to a new column.
In spite of this fact, the Bedrock MD 275 always closes the row (page) immediately after a transaction has finished (regardless of the address of subsequent transactions). This decision was made for a couple of reasons:

    
    
        By doing 4-way interleaving on the cache-line address and supporting full pipelining of four requests, the Bedrock MD 275 can still achieve full bandwidth.
        When multiple interfaces (and therefore multiple streams) are accessing memory (the only time when the memory interface can reach full bandwidth), keeping pages open loses much of its effectiveness.
        When a single stream is accessing memory, the excess bandwidth and the reordering capability of the arbitration logic can mitigate most, if not all, of the performance difference relative to keeping the page open.

Transaction Grouping

    
    


A full cache line read can move across the 128-bit wide memory interface in eight 5 ns cycles. Unfortunately, it takes 12 5 ns cycles to perform the directory read-modify-write necessary to maintain cache coherence. For this reason, the Bedrock MD 275 groups all transactions (whenever possible) into pairs. In this way, two reads, two modifies, and two writes can take place underneath two data reads or writes without losing any bandwidth. The Bedrock MD 275 can group any two coherent or full cache-line transactions. All partial transactions must execute by themselves.
Interfaces
The Bedrock MD 275 connects to the rest of the Bedrock system through the Bedrock crossbar. A single 1.6 GB/s link handles data and headers entering the MD 275 from the crossbar. Three 1.6 GB/s links handle data and headers entering the crossbar from the MD 275.
In order to better utilize the memory system, the Bedrock MD 275 treats requests from PI0, requests from PI1, requests from the NI or II, and replies as four separate virtual channels. By doing this, the MD 275 prevents bottlenecks where one stream would have to wait for a competing stream to drain before continuing. When messages arrive in the MD 275 (into the IB block), they are written into separate input queues based on their virtual channel. When messages leave the MD 275 (into the MOQ 3113; see FIG. 31), they are written into separate output queues based on their virtual channel (replies to PI0, replies to PI1, replies to NI or II, and requests). The arbitration engine in the IB block assures that the MD 275 fairly allocates bandwidth between the channels.
Message Types
At a high level, all the Bedrock MD 275 does is receive messages from the crossbar and generate responses back into the crossbar. For reference, Table 60 (see FIG. 34B) and Table 61 (see FIG. 34C) show all the messages received and generated by the Bedrock MD 275. The directory table (described in the SN1 Cache Coherence Protocol Specification) determines exactly which set of outgoing messages are generated in response to a particular incoming message.
Protection Model
A Bedrock system can scale up to 1024 processors. It would be almost impossible to run a single shared-memory operating system on a system that large. In order to make such systems usable, the Bedrock system must include support for multiple operating systems running on the same shared-memory base. In general, each operating system controls its own environment and can reset or reboot independently from the rest of the system. In order to prevent a single such operating system from taking down the entire system, the Bedrock MD 275 prevents certain processors or IO widgets from accessing certain memory regions. The information used to prevent access is stored in a special protection area of the directory memory and read, along with the directory, on every access.
In order to limit the amount of information needed, the Bedrock system stores protection information based on the region of the requesting processor or IO widget. There are never more than 64 regions in a system. For smaller systems (less than or equal to 64 Bedrock chips), one Bedrock chip equals a region. For systems between 65 and 128 Bedrock chips, two Bedrock chips equals a region. For large systems (up to 256 Bedrock chips or 1024 processors), four Bedrock chips equals a region.
For the most part, all processors and IO widgets inside the same operating system (also called cell) will have the same protection. For this reason, the Bedrock MD 275 uses a 64-bit local register called CurrentCell to specify which regions are inside the same operating system as the Bedrock chip. For requests from these “local” regions, the Bedrock MD 275 checks a single bit inside the directory entry. For all other requests, the Bedrock MD 275 reads a separate part of the directory memory that contains four bits for each region in the system (one for Processor Reads, Upgrades, and Write Invalidates, one for Processor WriteBacks and Replies, one for IO Reads and Write Invalidates, and one for IO Writebacks and Replies). Processor and IO protection are separated in order to allow cross-cell DMA without lowering the firewalls. Reads, Upgrades, and Write Invalids are separated from Writebacks and Replies in order to allow a two stage cell removal process (first disallow reads, then pull the cache lines to the home node, and then finally disallow writes and replies). For details on how to access the protection entries, please refer to the SN1 Programming Manual.
If a READ, RDSH, RDEX, REXU, or UPGRD request hits a line for which it does not have access, the Bedrock MD 275 returns an AERR (Access Error) instead of a normal response. If a WINV request hits a line for which it does not have access, it does not write the memory, and returns a WERR (Write Error). If a WB request or a SHWB, SXWB, or PGWB reply hits a line for which it does not have access, the Bedrock MD 275 acts differently if the requester is inside or outside the CurrentCell. For requests or replies from inside the cell, the data is written to memory regardless of the protection value. If the firewall has been breached, the MD 275 returns a WERR message (in the case of a WB), stores error information in the MISC_ERROR register, and sends an interrupt to both local PIs. For requests and replies from outside the cell, the Bedrock MD 275 treats the WB, SHWB, SXWB, or PGWB the same as a WINV and does not write the memory unless the protection is valid.
Non-coherent read requests (RSHU and PRDU), do not check protection and can therefore be used to create safe communication between cells. PWRU requests check protection and are treated the same as a WINV PRDM and PWRM requests both check protection when they miss in the fetch-and-op cache. They both use a separate 64-bit protection field that is cached along with the fetch-and-op variable for cache hits. PRDH requests do not check protection. PWRH requests use the CurrentCell register as their protection register (preventing any processor outside the cell from writing to HSPEC space). The UAlias portion of HSPEC space (a non-coherent read section that is placed in HSPEC for internal R10000 reasons) is treated here as part of USPEC spec. For more information on USPEC, MSPEC, and HSPEC space, please refer to the SN1 Programming Manual.
Page Counters
In a NUMA (non-uniform memory architecture) machine such as Bedrock, program performance will change based on the placement of important data structures. In general, data wants to be close to the processors that access it. However, ensuring that the data is always placed correctly is a non-trivial problem and can not always be guaranteed. The Bedrock chip supports page migration in order to improve the situation when the operating system and application do not place data correctly.
Every operating system page (16 kB) contains four sets of two counters. Each set of counters refers to an interleave of the memory. Therefore, set 0 refers to cache lines 0, 4, 8, 12, etc, set 1 refers to cache lines 1, 5, 9, 13, etc, set two refers to cache lines 2, 6, 10, 14, etc, and set 3 refers to cache lines 3, 7, 11, 15, etc. While this is not an intuitive mapping of counters to addresses, it is necessitated by the decision to interleave on cache line boundaries.
The two counters that make up each set are a local counter and a remote counter. Local and remote are determined by a local register inside the Bedrock MD 275. This register (called the MigNodeMask) contains a 9-bit chipid mask (supporting up to 512 Bedrock chips). For any given access, if the source chipid ANDed with the mask is the same as the MD 275 chipid ANDed with the mask, then the access is considered to be local. Otherwise, the access is considered to be remote.
The counters themselves are stored in the directory memory along with the directory entries and the protection information (for a complete map of the directory memory, refer to the SN1 Programming Manual). In order to prevent the directory access from impacting memory bandwidth, the Bedrock MD 275 only increments and checks these page counters on every nth access. The value of n can be set in the MigIntervalCount local register.
On an access that results in a counter check, both counters are read into the Bedrock MD 275. If the access was local (as determined by the mask), then the local counter is incremented. If the access was remote, then the remote counter is incremented. After the increment, the incremented counter is compared against a threshold (set in the MigValueThresh register) and the difference between the two counters is compared against a threshold (set in the MigDiffThresh register). Two control bits (ValueInterrupt and DiffInterrupt) are read from the directory along with the counter. If the ValueInterrupt bit is set, then the MD 275 will send out an interrupt if the MigValueThresh was exceeded. If the DiffInterrupt bit is set, then the MD 275 will send out an interrupt if the MigDiffThresh register is set. See the SN1 Programming Manual for a full description of MD interrupts. Even if the corresponding interrupt bit is not set, exceeding either counter will cause the address and source of the access to be stored in the MigCandidate register. If either counter saturates on the increment, both counters will be shifted right by one.
Fetch-and-Op
In a shared memory system, both the operating system and user programs spend a large amount of time acquiring and releasing locks. Unfortunately, most simple synchronization algorithms do not scale well past a couple of processors. In order to get around this problem, the Bedrock MD 275 offers a special non-coherent synchronization mechanism that scales very well to large numbers of processors.
The Bedrock MD 275 maintains a cache (two 64-bit entries or four 32-bit entries) of recently accessed synchronization variables. Any uncached read or write to MSPEC space (PRDM or PWRM) first checks to see if it hits in the cache. If it does, the operation (discussed below) is immediately performed and the data or an acknowledgment is returned. If the read or write does not hit in the cache, then the oldest cache entry is written back, the new data is read in, the operation is performed, and the data or an acknowledgment is returned.
Operations are performed on the cache by setting bits five to three of the address to specific values. Since these address bits are no longer used to address memory, there can be at most two 64-bit (or four 32-bit) fetch-and-op variables per cache line. On a PRDM, the following operations can be performed: a straight fetch of the cache value, a fetch followed by an increment, a fetch followed by a decrement, a fetch followed by a clear, and a cache flush. On a PWRM, the following operations can be performed: a straight write of the cache value, a simple increment (ignoring the value sent with the PWRM), a simple decrement (ignoring the value sent with the PWRM), an AND of the cache value with the PWRM value, an OR of the cache value with the PWRM value, and a cache flush. For the exact encoding, please see the SN1 Programming Manual.
As mentioned above, the cache can be used by two 64-bit entries or four 32-bit entries (or by one 64-bit entry and two 32-bit entries). However, each pair of 32-bit entries must be in the same 64-bit doubleword. A 64-bit protection word is also cached along with each 64-bit entry (or each pair of 32-bit entries).
Backdoor FCC
The Bedrock MD 275 supports a backdoor path to read and write the ECC memory. Two address spaces inside the HSPEC space support backdoor ECC access. For write access (PWRH), both spaces perform a read-modify-write of the data in order to write the ECC memory. For read access (PRDH), the BDECC-NORMAL space simply returns the ECC value, while the BDECC-SCRUB space reads the data and ECC, returns the ECC value, corrects the data and ECC, and re-writes the corrected data and ECC. For a full description of the interface, please refer to the SN1 Programming Manual.
Backdoor Directory
While the directory memory is read and written on every coherent transaction, the data is only used inside the Bedrock MD 275. In order for the operating system to access the information stored in the directory (and to initialize the directory during boot-up), a separate backdoor path provides transparent access to the directory memory. Two address spaces inside the HSPEC space are used for backdoor directory operation. A read (PRDH) to either space returns the entire 32-bit (standard) or 64-bit (premium) directory word. A write (PWRH) to the BDDIR-ACCESS space causes the single protection bit inside the directory entry to be written. A write (PWRH) to the BDDIR-FULL space causes the entire directory word to be written.
The 32-bit or 64-bit directory word contains a 6-bit or 7-bit ECC field. Without special assistance, the operating system would need to pre-compute the ECC value whenever it needed to do a backdoor ECC write. In order to avoid this extra complexity, the Bedrock MD 275, by default, fills in the ECC fields with the correct value (regardless of the value sent with the write command). If the IgnoreECC bit is set in the DirectoryConfig register, then the Bedrock MD 275 will pass on the ECC bits without modification.
For complete information on the BDDIR address space and on the address mappings necessary to access a specific directory, protection, or page counter entry, please refer to the SN1 Programming Manual.
Flash PROM
The Bedrock MD 275 supports a 16 MB flash prom (two 8 MB parts) for boot code and system configuration/error information. The prom is accessed through the LBOOT and RBOOT spaces within the HSPEC spec. Since the processors must access the prom before the Bedrock chip has a chip-id, the processor interface catches accesses to LBOOT space on node 0 and directs them to the local MD 275. RBOOT space can be used by any processor to access the prom of any node once the chip-ids have been initialized.
For prom reads, there is a one-to-one mapping of HSPEC address to prom address (within the given space). The Bedrock MD 275 supports all read sizes (doubleword, word, half-word, and byte). For prom writes, there is an eight-to-one mapping of HSPEC address to prom address (within the given space). In other words, HSPEC address 0 corresponds to prom address 0 while HSPEC address 8 corresponds to prom address 1. The Bedrock MD 275 only supports byte writes of the flash prom.
Junk Bus
The Bedrock MD 275 supports a separate interface to components that have no relation to the core MD 275 functionality. The flash prom, four bands of LEDs, a UART, and two Synergies (this interface is used to read remote Synergy registers). Access to the Junk Bus is through the LREG and RREG address spaces within HSPEC space. The Bedrock MD 275 only supports 16-bit reads and writes of all Junk Bus devices except for the flash prom and Synergies, which support 64-bit reads 16-bit writes.
SDRAM and DDR-SDRAM Initialization
All SDRAM and DDR-SDRAM contain mode registers that need to be initialized during system boot. These mode registers are accessed through the same LREG and RREG address spaces that are used to access the Junk Bus.
Refresh
The SDRAM and DDR-SDRAM supported by the Bedrock MD 275 require a refresh command approximately once every 16 microseconds. In order to reduce the refresh power surge, the Bedrock MD 275 refreshes one bank of the SDRAM or DDR-SDRAM on each DIMM approximately every eight microseconds. The Bedrock MD 275 uses the auto-refresh feature of the SDRAM and DDR-SDRAM in order to refresh all four internal banks simultaneously. The refresh will occur during the first idle cycle inside the four microsecond window. If there are no idle cycles, the refresh will timeout and force its way through. The exact refresh interval is configurable by the RefreshControl register. If all DIMMs in the system only have one or two banks, the MD 275 will only perform refresh every eight or 16 microseconds.
Memory Testing
The Bedrock MD 275 supports a Build-In-Self-Test (BIST) feature that can test all of memory (data, ECC, and directory) much faster than it could otherwise be accessed. The goal of this feature is to keep as much control as possible in the hands of software, while keeping the speed advantages of hardware testing. First, the software must do the mode register write to initialize the memory configuration, turn on refresh and determine the size of each DIMM (i.e., by four or by eight parts—this is read from the system controller). This memory sizing operation is equivalent to an address decode test of memory. For this reason, the BIST function contains no support for address testing.
After the memory sizing has taken place and the software has configured the MemoryConfig register with the correct DIMM sizes, the actual BIST operation can begin. The software first sets up a couple of configuration registers. The 4-bit data pattern goes into the BISTDataPattern register. This pattern will replicated across all 144-bits of data memory and all 32-bits of directory data. Pattern sequencing information (always same pattern or invert alternate cycles) also goes into the BISTDataPattern register. The bank under test goes into the BISTControl register. Finally, a writing of the start bit in the BISTControl register starts off the BIST operation.
During the BIST, the Bedrock MD 275 initializes all banks under test to the desired pattern and then tests all banks under test. On the first error, the data pattern is stored in the BISTDataError registers (one for directory data, one for memory data, and one for the address) and the BIST operation is halted. Status reports can be read from the BISTStatus register. Once the BIST operation has completed, the Bedrock MD 275 will update a bit in the BISTStatus register. If BIST is restarted after an error, it will continue where it left off.
The flash prom and Junk bus cannot be accessed during BIST operation. Since the local registers are not accessed through the MD 275 (they are read through a special datapath from the LB block), they can proceed normally during BIST operation.
Soft-Reset
In order to maintain the state of the node's memory through soft-reset, the MD 275 gates the internal reset of some of its functionality based on whether it is going through a soft or hard reset. During a soft-reset, the unit is initialized like a power-on reset except for the following exceptions:

    
    
        The contents of the MEMORY_CONFIG and DIR_CONFIG registers are maintained. This ensures that settings that pertain to the size and width of the SDRAMs, synchronizer settings and directory flavor are preserved.
        Soon after the reset signal goes away, the MD 275 issues a precharge to all banks of the SDRAMs in order to bring them to a known state (in case the reset signal came in the middle of an SDRAM access).
        The contents of the REFRESH_CONTROL register are maintained. The refresh counter restarts its count at zero after the soft-reset and if refresh was enabled before the soft-reset, the MD 275 will resume issuing refreshes according to the threshold that was programmed.

Issue Block

    
    


All messages from the XBAR enter the MD 275 through the IB (Issue Block). The IB decodes the messages, reorders them for fairness and efficiency, issues the necessary addresses and commands to the DRAM, and synchronizes the DB and MB blocks with the incoming or outgoing data.
This section is broken up into three subsections: architecture, arbitration, and design. The overall structure of the Issue Block is discussed in the architecture section, while the arbitration algorithm (for all message types) is discussed in the arbitration section.
Architecture
FIG. 35 shows an example of queues for MD 275.
When a message arrives in the MD 275 from the XB, the header is written into the 12-entry Header Queue (located in the IB block) and the corresponding data, if any, is written into the eight cache-line Data Queue (located in the MB block). In parallel with the Header and Data Queue writes, the incoming message is decoded and stored in the Pending Queue and Write Table. The Pending Queue maintains one entry for each entry in the Header Queue and the Write Table maintains one entry for each of the cache lines in the Data Queue (the Data Queue actually contains a ninth cache line for used internally by the MB that does not have an entry in the Write Table).
The XBAR divides incoming messages into one of four virtual channel based on source and type. Requests from PIO arrive on one channel, while requests from PI1, requests from the NI or II, and replies arrive on the other three channels. Each of the four input queues (Header, Data, Pending, and Write) allocates a quarter of its space to each virtual channel. The XB and IB both treat the four virtual channels as completely independent and support arbitrary interleaving.
In parallel with the Header Queue write, the IB compares the incoming message against all open banks (up to 4) and decodes the command (Read/Write, Full/Partial). The output of these operations are stored in the Pending Queue and used during arbitration. For incoming messages with data, the IB writes the Write Table once the tail bit has been received.
Once the decoded information for a message is in the Pending Queue and the Write Table, the arbitration logic can select it and issue it to the rest of the MD 275. A message is issued by reading its header out of the Header Queue and writing the relevant information into the three queues at the head of each datapath (address, directory, and memory). Once the message is in these three queues, it then can be issued to the DRAM and completed.
Arbitration
The arbitration section of the Issue Block takes the 12 entries in the Pending Queue and selects the “best” one to issue. Here, “best” is defined in such a way that there is a fair distribution between the three input request queues, writes and replies get enough bandwidth, all messages issue in a reasonable amount of time, and all DRAM constraints are observed.
In order to simplify things, the arbitration process is broken up into two stages: a local arbitration stage based on the individual message and a global arbitration stage based on the queue. Very few dependencies exist between the two stages, allowing them to run in parallel in the same cycle.
Local Request Arbitration
Each of the four virtual channels (requests from PI0, requests from PI1, requests from NI or II, all replies) performs its own independent local arbitration. In parallel, the global arbitration is selecting which of the four channels will actually win the full arbitration.
For the three request queues, the arbitration logic must first figure out which of the (up to three) requests in the queue are ready to execute. For a cached read, partial read, or partial write to be considered ready, it must meet the following requirements:

    
    
        If the message is the oldest cached read, partial read, or partial write in the channel and a write timeout (described below) is not pending, then there must be space for at least three headers in the correct output header queue and space for a cache line of data in the correct output data queue. If the message is a cached read, partial read, or partial write or a write timeout is pending, then there must be space for at least six headers in the correct output header queue and specs for two cache lines of data in the correct output data queue. If the message is a cache line write, then there must be space for at least six headers in the correct output header queue.
        The message must not conflict with any of the open banks.
        For partial reads and partial writes, the address logic must be able to accept partials. For cached reads and cached writes, the address logic must be able to accept non-partials.
        For cached writes and partial writes, the entire data packet must be present in the data queue.
        For cached writes, there must be no ERESPs waiting to issue. (ERESPs are messages that are issued as writes and then need to be reissued as reads. Between the issue and the reissue, no new writes are allowed to win arbitration.)
        For partial reads and partial writes, the message must be oldest partial in the channel (partials must issue in order).
        For cached writes, the message must be the oldest cached write in the channel (cached writes issue in order).
    
    


Once the ready information is available for each of the (up to) three messages, the arbitration logic selects the message with the highest priority. Priorities are determined as follows:

    
    
        1. Any cached write (if write timeout is asserted).
        2. Oldest cached read, partial read, or partial write.
        3. Any cached read, partial read, or partial write.
        4. Any cached write.

Local Reply Arbitration

    
    


The reply channel is handled slightly differently than the three request channels. A reply is considered ready if the following criteria are satisfied:

    
    
        The message must not conflict with any of the open banks.
        The address logic must be able to accept non-partials.
        The message is the oldest reply in the queue (replies issue in order).
        For write replies, the entire data packet must be present in the data queue.
    
    


There are no priorities for the reply channel as the oldest message is always selected (if it is ready).
Global Arbitration
In order to allocate bandwidth fairly between the three request queues, the global arbitration logic maintains three LRU tables. The first LRU (Oldest) keeps track of the order in which the queues last issued a message marked as the oldest pending cached read, partial read, or partial write. The second LRU (Any) keeps track of the order in which the queues last issues any cached read, partial read, or partial write message. The third LRU (Write) keeps track of the order in which the queues last issued a cached write message.
The global arbitration selects the queues using the following priority scheme:

    
    
        1. Ready reply with Reply Timeout
        2. Ready cached write with Write Timeout. Selected using the Write LRU.
        3. Ready cached read, partial read, or partial write marked as oldest. Selected using the Oldest LRU.
        4. Ready cached read, partial read, or partial write. Selected using the Any LRU.
        5. Ready cached write. Selected using the Write LRU.
        6. Ready reply.
    
    


The Write LRU is updated whenever a cached write message issues. The Oldest LRU is updated whenever a message marked as the oldest cached read, partial read, or partial write issues. The Any LRU is updated whenever a cached read, partial read, or partial write issues.
Write Timeout
The write timeout logic makes sure that writes will not sit in the data queue forever. In addition, once the data queue for a channel is full, the write timeout logic forces the writes to issue, freeing up space for the next write message.
A write timeout is started after one of two conditions is met:

    
    
        There are two cache lines of data in the data queue of any channel.
        A user-settable number of read messages have issued since the last write message issued.
    
    


If one of the above conditions is true and there is not a reply timeout in progress, a write timeout will be asserted only on the virtual channel, containing a write message, that has the highest priority in the Write LRU. Once a write issues out of that channel, with the timeout asserted, then the timeout is broadcast to all three request channels. The timeout continues until something besides a cached write issues or four cached writes issue, whichever comes first. After the timeout has completed, at least four messages, of any type, must issue before the timeout can be reasserted.
Reply Timeout
The reply timeout logic makes sure that replies eventually issue. A reply timeout is asserted if more than a user-settable number of requests have issued since the last reply was issued, and there is no write timeout in action.
Junk Bus and PROM
The Bedrock MD 275 talks to non-DRAM external devices using a separate proprietary bus. The MD 275 recognizes four different types of devices on this bus: an EPROM, a UART, LEDs, and one or more “Junk” buses. Each type of device has its own address space within the LREG or RREG portion of HSPEC space (see Table 42).
The bus connects to the Bedrock MD 275 using 16 address/data pins, four control pins, and an Interrupt line. FIG. 36 shows a diagram of the interface.
Memory Block
FIG. 37 shows a block diagram of the Memory Block datapath. This datapath transfers data from the pins to the output data queue (MOQD 3114), and from the input data queue (MIQD) to the pins. Inside the datapath are a couple of special subblocks that allow read-modify-write operations of cache lines, and that implement Fetch&Op operations.
The Merge Cache supports read-modify write operations on cache lines. The Bedrock MD allows uncached write operations on a byte boundary. However, in order to save SDRAM cost, protection information (ECC) is only stored on 64-bit quantities. Therefore, in order to perform an uncached write, the MD must perform a read-modify-write operation. First, the Memory Block reads an entire cacheline, storing the needed 128-bits in the Merge Cache. The Memory Block then reads the store information out of the MIQD and overwrites the selected bytes with new data. Now that the correct data is available, it is sent through ECC generation and written back to memory.
The Fetch- and Op-block implements a two entry cache in order to improve synchronization operations.
Basic Operation
Normal Read
A normal read proceeds by taking in data from the pins, detecting and correcting ECC errors (if we are not ignoring ECC errors) and then passing this data on to the MOQ. ValidData and DataTail signals are sent to the MOQ 3113 to indicate that valid data is present.
Normal Write
The Odd and Even MIQD queues each contain seventy-two 65-bit entries, each entry being a 64-bit word, and a UCE bit associated with that word. The seventy-two entries are enough for two complete cache lines of data from each of the input queues (P0, P1, and Misc), and one extra cache line that is used only by the MB to do read-modify-writes of individual cache lines. The MIQD is written one 64-bit word at a time by the XB. When told to do a normal write, the MB reads MIQD Odd and MIQD Even in parallel, latches this data, and on the next cycle generates the ECC bits, and sends the data to the pins. Note that during a normal write ECC bits are generated regardless of whether the IgnoreECC bit is set or not.
FIG. 37 shows one embodiment of a Memory Block Datapath.
Partial Read
A partial read proceeds by reading an entire cache line from memory, but only sending the 128-bits that contain the requested data to the MOQ. DataValid and DataTail are set when the appropriate 128-bit quantity is available.
Partial Write
Partial write is a 2-phase operation. In the first phase the appropriate cache line is read into the MIQD, and the 128-bit quantity that requires modification is read into the Merge Cache. During the second phase of the partial write, the cache line is written back to memory. The partial write data is taken from the read into the Memory Cache. During the second phase of the partial write, the cache line is written back to memory. The partial write data is taken from the MIQD and merged with the data in the Merge Cache based on ByteEnable signals. All the other 128-bit pieces of the cache line are written back to memory unchanged from the MIQD. Normally ECC is regenerated on the writeback. However, in the case that we are ignoring ECC, the old ECC that the line had previously will be written back instead.
Fetch-and-Op Write Miss
A Flush operation is performed to write out the data currently in the cache, followed by a Fill operation, followed by a Write operation.
Fetch-and-Op Protection
Fetch-and-Op protection has two parts. The first part is the normal directory protection check that occurs over in the Directory Block, and occurs during a Fill operation. If the DB detects an access error, then the protection word in the Fetch-and-Op cache is cleared, and no Fetch-and-Op operations will be allowed. The DB also notifies the IB that an access error occurred on a Fetch-and-Op fill.
The second part of the protection check occurs during a Read Hit or Write Hit operation. The IB has sent the Protection Region bits that address one of the 64 bits in the Fetch-and-Op protection register. If this is set then the operation is allowed to proceed, otherwise the Fetch-and-Op cache remains unchanged.
Fetch-and-Op Operation
The Bedrock MD implements the same Fetch-and-Op commands as the SN0 MD. A small fetch-and-op cache (2 entries) allows a low occupancy (.about.20 ns) transaction which significantly speeds up program synchronization.
FIG. 38 shows a block diagram of the Fetch-and-Op Cache datapath. There are two entries in the cache. Each entry consists of a 64-bit protection word, and 64-bit data word, which can be considered as a single 64-bit word, or as 2 32-bit words, shown as F&Op-Hi, and F&Op-Lo in the diagram. The four key operations performed by the Fetch-and-Op Cache are: fill, read, write, and flush. A short summary of each operation is described below:

    
    
        Fill—On a fill operation, data is loaded from memory directly into the Fetch-and-Op Cache. No arithmetic or logical operations are performed.
        Read—On a read operation, data is taken from the Cache, sent to the MOQD, and the cache entry is cleared, incremented, decremented, or left unmodified. No logical operations are performed.
        Write—On a store operation, data is taken from the MIQD, optionally ANDed or ORed with the value in the Cache, and then stored in the Cache. It can also ignore the incoming data from the MIQD, and simply increment or decrement the value in the Cache.
        On a flush operation, data is taken from the Cache and returned to memory. This is a two phase operation similar to a partial write operation: the entire cache line is read from memory and stored in the MIQD, then the cache line is written back, with the first two words taken from the Fetch-and-Op Cache rather than the MIQD.
    
    


We can do a read or write to the Fetch-and-Op Cache, and for each case there are three possibilities: a hit in the cache (Hit case), a miss in the cache and the cache entry is unused (Load case), and a miss in the cache with the cache entry currently in use (Miss case). Each of these cases is handled by some combination of Fill, Read, Write, and Flush operations.
Fetch-and-Op Read Hit: A Read operation is performed.
Fetch-and-Op Write Hit: A Write operation is performed.
Fetch-and-Op Read Load: A Fill operation is performed to load the correct data into the cache, followed by a Read operation.
Fetch-and-Op Write Load: A Fill operation is performed to load the correct data into the cache, followed by a Write operation.
Fetch-and-Op Read Miss: A Flush operation is performed to write out the data currently in the cache, followed by a Fill operation, followed by a Read operation.
Backdoor Data FCC Operation
Backdoor FCC Read
A backdoor ECC read proceeds by collecting the ECC bits from either the top 8 double words in a cache line, or the bottom 8 double words in a cache line. The IB always brings in the critical part of the cache line first, so the MB collects the ECC bits from the first 4 cycles, 16 ECC bits per cycle. These ECC bits are then sent as a single 64-bit word of the MOQ.
If IgnoreECC is not set, then ECC errors in the cache line will be detected and corrected (single bit error case) during backdoor ECC reads.
Backdoor FCC Write
A backdoor ECC write proceeds in a fashion similar to a partial write. A backdoor ECC write writes the ECC bits of 2 aligned 64-bit words at one time. We first read in a complete cache line from memory, and write it into the MIQD. Note that the IB does critical half cache line re-ordering in this case, so the words for which we want to write the ECC will always be in the first 4 cycles. The MB looks at the byte enables to determine which 2 words will have their ECC bits written (only two of the byte enable bits should be set). The merge cache is written with the 128 bits for which we wish to do a backdoor ECC write. The cache line is then written back to memory, and on the appropriate cycle the backdoor ECC bits are read from the MIQD at the same time as the Merge Cache data, and the full 144-bits are written to memory. Note that the ECC bits are the 16 bottom bits of the word read from the MIQD.
Backdoor ECC writes are primarily intended for use with IgnoreECC set. If IgnoreECC is not set, then ECC errors will be detected and corrected on the read of the cache line. Also, ECC bits will be regenerated for all words that we are not writing directly with backdoor ECC write.
ECC Scrub Operation
The ECC scrub operation is used to correct single bit ECC errors in memory. It is a 2-phase operation which involves reading in a cache line and writing the corrected cache line into the MIQD. Then writing back the data to memory while regenerating the correct ECC. Note that since the purpose of the Scrub operation is to correct known errors, single bit ECC errors on the read do not generate an interrupt, and do not affect the error registers, even if IgnoreECC is not set. However, double bit errors will still be detected when IgnoreECC is not set.
Directory Block
The directory block (DB) is responsible for implementing the SN1 cache coherence protocol. While the inbound-message block (IB) decides which incoming transactions to handle and issues all the addresses to the SDRAMs, and the memory block (MB) handles the data to and from memory, the DB maintains coherence information in the directory and generates all headers for outgoing messages.
The primary functions of the DB are:

    
    
        9. Store up to 6 pending requests for the DB pipeline.
        10. Determine output message headers and sometimes output message data, based on the incoming message, the protection permission for the source of the incoming message, and the current directory state.
        11. Maintain directory state. ECC is generated and checked. Two different directory entry sizes are supported (32/64 bits).
        12. Update page migration counters. Generate interrupts if the count (or difference between the counts) exceeds a user defined threshold.
        13. Log errors (directory state memory errors and incoming message protocol errors).
        14. Allow direct reads/writes of the directory memory. These are supported through uncached HSPEC space as well as a special mode in which cached reads return a doubleword of data.
        15. Allow the local registers to be read and written (The IB handles the interface to the local block).

Network Interface Unit 274

    
    


The network interface unit (NI) 274 acts as a bridge between the Bedrock crossbar 279 and the Bedrock's SN1Net port 73. The NI 274 handles all aspects of the SN1Net connection, and can be attached to an SN1 router 76, or directly to a peer node controller 75's NI 274.
Since the SN1Net message format differs from the Bedrock crossbar's message format, the NI translates all messages flowing between the two interfaces. The NI performs these translations at full bandwidth, with a single cycle of latency in each direction. All Bedrock side message buffering takes place within the crossbar, with the NI mediating the flow control information between the crossbar and the remote SN1Net agent.
Throughout this document, the terms “send” and “outgoing” refer to messages being sent from the Bedrock to SN1Net, while “receive” and “incoming” refer to messages being received at the Bedrock from SN1Net.
FIG. 39 is a block diagram of the main address and data paths of the NI 274.
SN1Net Interface
FIG. 41 shows a block diagram of the connections between node controller 75 and router 76 of one embodiment.
At the physical layer, the NI connects to SN1Net via two unidirectional, source synchronous 20-bit data ports operating with STI signal technology (refer to FIG. 41). All the signals are differential, resulting in 44 signal pins per port. The physical layer circuitry consists of a source synchronous driver (SSD) and source synchronous receiver (SSR) that implement the conversion between 800 MHz serial data on the pins and 200 MHz parallel data used by the chip core.
The Link Level Protocol (LLP version 3.0) resides above the physical layer to provide reliable, in-order delivery of 128-bit data atoms known as micropackets. See the Link Level Protocol specification for details on the operation of this protocol layer. The SSD, SSR, and LLP send and receive modules implement the same protocol as those used on the SN1 router 76. Most aspects of the SSD/SSR interface are handled within the LLP. An exception is control of the SSR's data sampling window which is done via the d_avail_select port. The sample setting is set in NI_PORT_PARMS register with the D_AVAIL_SEL bits.
SN1Net virtual channel tagging, message framing, and credit-based flow control are layered above the LLP, allowing SN1 coherence protocol messages to be composed from micropacket sequences. This information is passed on from the LLP as sideband data (Refer to FIG. 40, which shows message sideband encoding).
Crossbar Interface
Both directions of the NI's crossbar interface are simplified by the exact bandwidth match between internal Bedrock and SN1Net transfers. All single-cycle Bedrock headers are followed by a dead-cycle on the crossbar, thus consuming equal bandwidth to the two-cycle SN1Net headers. All quadword data micropackets consume two data cycles on the crossbar, and doubleword data micropackets are followed by a dead-cycle on the crossbar, again matching the SN1Net bandwidth.
All messages received from SN1Net are translated at full bandwidth and forwarded to the crossbar's NOQ section where they may be buffered or sent directly to the crossbar switch. The NOQ fill level is communicated via the NI to the remote SN1Net peer using the sideband virtual channel flow control protocol.
SN1Net to Bedrock Internal Message Conversion
This section describes how SN1Net messages arriving at the NI port are converted to Bedrock internal message format.
NOTE: When receiving router network micropackets, Bedrock considers any micropacket that follows a micropacket-with-its-Tail-bit-set to be a router network header. After reset, the first micropacket received is assumed to be a Header.
Bedrock to SN1Net header conversion is message-type independent. In brief,

    
    
        16. Bedrock Source[10:0]=SN1Net Source
        17. Bedrock Supplemental[10:0]=SN1Net Supplemental
        18. Bedrock Command[6:0]=SN1Net Command[30:24]
        19. SN1Net Addr[2:0]=0, as all addresses are byte aligned
        20. SN1Net Addr[34:33]=0, reserved for future node memory expansion
        21. SN1NetAddr[42:35] is the node number, from BedrockAddress[40:33]

Bedrock Internal to SN1Net Message Conversion

    
    


This section describes how Bedrock internal messages exiting the NI port are converted to SN1 Net message format.
Note: The content of the Destination Field of the SN1Net Header corresponds to the contents of the Bedrock Internal Header's Address field, Source field or Supplemental field, depending on the command (as summarized in Table 120 below).







TABLE 120







Processor Physical Address to SN1Net Address











T-Rex + Physical





Address
SN1Net Address
Description







47:46
Zero (Future





Expansion to 8K





Nodes)



40:33
42:35
Node Number (256





Nodes)




34:33
Zero (Future





Expansion to 32





Gbytes)



32:3 
32:3 
Node Memory





Address (8 Gbytes)



2:0
2:0
Always Zero; all





addresses must be





byte aligned
















TABLE 121







Converting Bedrock Internal Header











Command
SAMPLE





Type
COMMAND
SN1Net Source
SN1Net Dest
SN1Net PreXsel





Request 1
DNET_RDSH
Source [10.0]
Address[40:33]
MD, PI0,






PI11


Request 2
DNET_IRSHU
Source [10.0]
Supp1[10:3]
PI0, PI1






or II2


Request 3
DNET_INVAL
Source [10.0]
Supp1[10:3]
PI0 or






PI13


Request 4
DNET_PRDI
Source [10.0]
Address[40:33]
II


Request 5
DNET_PWRI
Source [10.0]
Address[40:33]
PIx, LB






or II4


Request 6
DNET_VRD
Source [10.0]
8′h0
LB


Reply 1
DNET_SACK
{NODE_ID, Source
Source[10:3]
PIx or




[2:0]}

II5


Reply 2
DNET_SXFER
Source [10.0]
Address[40:33]
MD


Reply3
DNET_VRPLY
{NODE_ID, Source
Source[10:3]
LB




[2:0]}





1For Request 1 barrier commands (PRDB, PWRB & BAR) select P0/1. This is based on Source field subnode bits [2:0] = . All other commands select MD


2For Request 2, the Pre-Xsel field is based on the Supplemental[2:0]. A master of IO or GBR uses II, and, a master of PROC uses FI0/1 based on the Supplemental field subnode bit.


3For Request 3, select PI0/1 based on the Supplemental field subnode bit.


4Request 5 is PIO to Bedrock widget. The PreXsel field depends on address bits [23:21]. An address in the IO range uses II ([23:21] = 0. times. 6), an address in the PI range uses PI0/1 (PI0 = 0. times. 4 & PI1 = 0. times. 5 for [23:21]), and all other addresses use LB. Access to PIx/LB/II registers require address[31:24] = 0. times. 01 (BW0/SW1).


5For Reply 1 the PreXsel field depends on Source field bits [2:0]. A master of IO or FBR uses II, and a master of PROC uses PI0/1 based on the subnode bit, Source[2].













TABLE 122







DeviceID Encoding








Source [2:0] or SuppI[2:0]
Unit





000
Processor Interface 0,



Processor 0


001
Processor Interface 0,



Processor 1


010
Real/TimeGBR IO


011
Normal I/O


100
Processor Interface 1,



Processor 0


101
Processor Interface 1,



Processor 1


110-111
Reserved









Register Access

Access to registers in the NI space is mediated by the Local Block (LB). Register read and write requests are received by the LB, which uses a dedicated register data and address bus to transfer register data to/from the NI. Access protection is also controlled by the LB. However, the NI will detect read access errors to registers address space that does not exist. This error is passed on to the LB.
The IO Interface unit (II) of the Bedrock chip implements the interface to the Crosstalk interface, which connects to I/O devices such as disk controllers and network boards (e.g., Ethernet).
FIG. 42 shows a high level diagram of the IO unit and its position relative to the rest of node controller 75 and input/output port 79. The interface between Bedrock's Crossbar (XB) unit and II is composed of four XB queues. The names of the four queues are prefixed by “RQ” or “RP”, indicating that they carry request messages or response messages, respectively. The remainder of the name indicates whether the II section is the receiver of the message (the input queue, “IIQ”) or the sender of the message (the output queue, “IOQ”). FIG. 42 lists the types of messages that can be produced or consumed by each interface.
The II section performs two basic functions: (1) it provides a method by which IO devices can read and write host memory (“DMA” operations), and it provides a method by which the processors in the system can control IO devices (“PIO” operations). Thus, the term “DMA” refers to the case where an IO device is the initiator of a request and the term “PIO” refers to the case where a processor somewhere in the system is the source of the request. In order to control II itself, a third basic function is also implemented, called “Local PIO”. This term reflects the fact that a processor is the initiator of the request, and the object of the request is a register which is internal (local) to II.
For DMA operations, an IO device initiates a request by sending a Crosstalk request message into the Crosstalk receive interface. The request is recorded within II in a state vector called a Credit Response Buffer (CRB). The request is reformatted to the Bedrock-internal message format, then sent to the XB unit by way of the Request IOQ for dispatch to the home node of the memory which is the target of the request. The II section participates in the SN1 Coherence Protocol, and may need to take several actions (described later) to gain access to the target memory. As these actions are taken, the state of the request is updated in the CRB. Once a response is received from the XB by way of the Response IIQ, it is forwarded to the Crosstalk Transmit Interface and the CRB is retired.
For PIO operations, a processor initiates a request by sending a router network request message into the Request IIQ. If the request is a read request, the node number and processor number of the request is recorded in a structure called a PIO Response Buffer (PRB). If the request is a write request, the requester is given a write response immediately by sending it out the Response-IOQ. The request is then reformatted to Crosstalk format and sent to the target IO device by way of the Crosstalk Transmit Interface. The II section does not have any work to do with regard to cache coherence for PIOs, because accesses to IO space are defined as having left the coherence domain. When a read response is received on the Crosstalk Receive Interface, the information stored in the PRB is used to reformat the response into a Bedrock-internal message, and it is sent out across the Response-IOQ. When a write response is received on the Crosstalk Receive Interface, it is discarded after checking for errors and other status information.
PIO operations to II-local registers operate very much like PIO operations to IO devices. The only difference is the obvious difference that the target of the request is internal to II, so the request doesn't involve the Crosstalk interface.
Message Flow
In order to prevent buffer overflows and deadlock conditions, hardware flow control mechanisms must be used. These flow control mechanisms form a hierarchy, with low level signal handshaking at the bottom of the hierarchy and message-synchronized flow control at the top of the hierarchy. This section is an overview of the flow control aspects of II.
In order to prevent deadlock within a node or between nodes, II assures that it will pop requests and responses off of the IIQ in a finite amount of time. This assurance remains even in the face of certain errors, especially those that involve the Crosstalk Interface. The II further attempts to minimize the time a message spends on the IIQ.
Because II implements the Crosstalk interface, it implements the Crosstalk Credit mechanism. This credit mechanism keeps message input buffers from overflowing (both IO devices and II).
The mechanisms described in the preceding two paragraphs are not independent. In fact, the Crosstalk Credit mechanism could undermine the assurance of IIQ forward progress when there is a slow IO device. (II cannot accept any further PIO requests when it has no Crosstalk Credits, thus possibly stalling the IIQ.) To mitigate this problem, a mechanism called “PIO conveyor Belt” is implemented by II. This mechanism manages a second set of credits, called “PIO Credits.” These PIO Credits manage access to particular IO devices (as opposed to Crosstalk Credits, which control access to all IO devices), and when a particular IO device cannot accept another request, any new request for that IO device is popped from the IIQ and given a negative acknowledge. This action causes the requester to requeue the request and send it again, thus implying a “conveyer belt”, which gives the mechanism its name.
The CRB as a Partial Merge Buffer
The SN1 Network Protocol and Cache Coherence Protocol operate on memory data one cacheline at a time. But IO devices need to be able to operate on byte-sized chunks of memory data, so II must provide the mechanisms for doing this. For reads, this simply means that whenever an IO device requests memory read data, an entire cacheline is sent to II, which then forwards the interesting bytes to the device. For writes, it is more complicated.
When an IO device writes main memory in chunks smaller than cachelines, II will (1) request the cacheline from the system (2) receive the cacheline in a buffer when the system returns it, (3) merge the byte data into the cacheline, and (4) write the entire cacheline back to main memory. Just as all other requests from Crosstalk, a CRB is assigned to maintain the coherence information for the cacheline, and the cacheline buffer associated with the CRB is used to perform the merge.
The merging of partial cacheline writes (also called “partial writes”) represents the only case where II requests an exclusive copy of a cacheline. Upon completion of the merge, the line is immediately written back, so it is not held in the dirty exclusive state.
Credit Response Buffers (CRB)
The Coherent Resource Buffers (or CRBs) are internal II state describing cachelines which are being manipulated by II. Since the II must participate in the SN1 Cache Coherence Protocol, it must maintain certain state information relative to each cacheline for which it has requests in flight.
In general, every request that is received from Crosstalk uses one CRB for each cacheline it touches. As the request is forwarded to the router network 575, some information is left behind in a CRB so that when a response is received from the router network 575, II knows what to do with it. Given the complexity of the SN1 Cache Coherence Protocol, II may participate in several exchanges with the directory or the owner of the cacheline before a response is received that can finally be forwarded to the requester on Crosstalk. Thus, each CRB represents the “current state” in the state machine that manages II's participation in the Cache Coherence Protocol.
The rest of the state machine that manages II's participation in the Cache Coherence Protocol is the so-called “CRB Table”. The CRB Table is simply a big chunk of combinational logic that looks at the incoming message, the CRB implied by the incoming message (determined by a CAM lookup of the address in the message), and other II-internal factors. Given all these inputs, the CRB Table produces the next CRB state, which is used to update the CRB, and the responses to the messages: requests or responses to the router network 575 or Crosstalk 82. Sometimes an incoming message only updates the CRB, and doesn't produce an outgoing message.
There is only one CRB Table, and it is shared in a pipelined fashion with all fifteen CRBs.
PTO Response Buffers (PRB)
CRBs keep information about outstanding DMA requests (requests which are initiated by Crosstalk). In a similar manner, information about outstanding PIO requests (requests which are initiated on the router network 575) is kept in PIO Response Buffers (PRBs). When a processor in the SN1 system makes a request to an I/O device on Crosstalk, certain state must be maintained so that when the response comes back from that device, II knows where to send it. For reasons which will be described later, this information is only kept for PIO Read requests.
The information about outstanding reads is kept in registers called PIO Read Table Entries (PRTEs). There are eight PRTEs, one for each possible outstanding read. There is a PRB table which functions in a manner similar to the CRB table, taking the state of the outstanding request (described by the PRB and the PRTE associated with that request) and the incoming message, and deriving the next state and response messages. Because this is on the I/O side of the coherence boundary (PIO requests, by definition, leave the coherence domain), the current state embodied by the PRBs and PRTEs is much simpler than in the CRB, as is the PRB table.
II-Internal Registers
The II is configured and controlled by many internal (local) registers. They are mentioned here because they represent the rest of the II-internal state required to make sense of the II interfaces as described in the subsequent sections of this document.
IIQ Interface
Requests
The only requests from the router network 575 received by II are interventions (messages regarding cachelines that II owns), and PIO reads and writes (to either Crosstalk or II local registers). The table of FIG. 42 summarizes the requests received by II.
Local Block
The Local Block (LB) of the Bedrock chip contains the PIO Access Machine, some registers, the Invalidate Engine, the Vector PIO Machine and a real-time clock generator.
The input signals which enter the LB and the output signals which are driven by the LB can be aggregated into several different groups. Each such group constitutes a particular interface. Together, these interfaces comprise the entire interface of the LB unit. Each of the following subsections describes a particular group.
Clock, Reset and JTAG












Signal Name
Direction
Description







CLOCK
input
system clock


RESET_LB
input
hard system reset




(active high)


RESET_LB_SOFT
input
soft node reset




(active high)


JTAG_ID[31:0]
output
JTAG info (rev.




part num, mfctr)


LB_II_JTAG_ID_31_28[31:28]
output
JTAG info




(REVISION)


LB-II-JTAG-ID 11-
output
JTAG info


0[11:0]

(MANUFACTURER)









Assertion of the RESET_LB input causes the LB to reset all its state machines and initialize its registers to their specified reset values. The LB will abort any operation that is in progress (e.g., a PIO read or write request, or an LINVAL request). Assertion of the RESET_LB_SOFT input causes the LB to reset all its state machines and abort any operation that is in progress, but registers retain their current contents (i.e., they are not re-initialized). The RESET_LB_SOFT input is intended for diagnostic purposes while the Bedrock chip is subjected to testing in the lab after prototype chips are available. If a node becomes “stuck” such that no further progress is possible, the RESET_LB_SOFT input can be used to restore the chip to a state in which software can examine the contents of registers so as to determine the cause of the failure.










Rq Flits From LIQ toLB











Signal name
Direction
Description






LIQ_LB_RqAvail
input
flit is available





on RqData Signal



LIQ_LB_RqTail
input
flit is last one





in packet



LIQ_LB_RqData[60:0]
input
contents of flit



LIQ_LB_RqReady
output
LB is able to





receive rq flit



LIQ_LB_RqRpValid
input
a valid flit is





on RpData signal



LIQ_LB_RpTail
input
flit is last one





in packet



LIQ_LB_RpData[66:0]
input
contents of flit



















Rq and Rp Flits From LB to LOQ











Signal name
Direction
Description






LB——LOQ_Data[66:0]
output
contents of flit





(may be rq or rp)



LB——LOQ_RqAvail
output
rq flit is





available on Data





signal



LB——LOQ_RqAvail
output
rq flit is





available on Data





signal



LB——LOQ_Xsel[2:0]
output
encoded





destination



LB——LOQ_Tail
output
flit is last one





in packet



LB——LOQ_RqReady
input
LOQ is able to





receive rq flit



LB——LOQ_RqReady
input
LOQ is able to





receive rq flit









System Configurations and Topologies

SN1 apparatus of the present invention are modular computer systems which span the range of two to 512 CPUs. They are made up of separate rack-mounted modules which include node having two or four CPUs (C-Bricks), 8-port routers (R-Bricks), various IO bricks (I-Bricks, P-Bricks, and/or X-Bricks), Power Bays, and/or disk drive bays (D-Bricks). All of these modules (or “bricks”) are mounted in a rack or racks and interconnected with cables. In one embodiment, a systems and method is used such as described further in application Ser. No. 09/408,874, filed on Sep. 29, 1999, entitled “MODULAR COMPUTING ARCHITECTURE HAVING COMMON COMMUNICATION INTERFACE”.
These systems are extremely flexible in configuration, since the amount of CPU, memory, IO and disk resource can all be independently selected. High-availability systems, where all functionality is fully redundant, may be easily configured.
All SN1 systems (with the exception of systems containing eight or fewer CPUs, which are a special case that are implemented without using a router R-Brick) include groupings of a Power Bay, a router (R-Brick), and 4-processor nodes (C-Bricks), plus one or more I/O bricks. The other nodes are cabled to the router, and in large systems, the routers are cabled to each other. This configuration gives an excellent value, yielding a combination of low cost, high bandwidth, and low latency, and it easily supports the configuration of high-availability systems. Up to 24 CPUs with a fairly substantial I/O system may be configured in a single rack. Up to 32 CPUs may be constructed in a single rack, with a separate rack for IO. Larger systems are implemented using multiple racks.
Systems involving over one hundred twenty-eight (128) CPUs are configured with additional routers 76 installed in some of the racks, known as metarouters, which allow interconnection of larger numbers of nodes. Modules within the racks are organized and installed identically for all configurations, and no re-cabling is ever required within a rack to expand the configuration.
In systems of 16 or fewer CPUs, space is available within the rack for installation of I/O and disk bricks. For larger systems, I/O and disk modules are mounted in separate racks which contain no nodes 370 or routers 76.
Node: Processor/Memory
A SN1 system includes one or more nodes 370. Each node 370 includes two or four processors 74 and their associated caches, main memory 77, and I/O port 273 and a port 274 into the router network. A central ASIC (application-specific integrated circuit), node controller 75, connects these four subsystems.
CPU Types
In some embodiments of the present invention, two families of CPUs are supported in SN1 systems: MIPS “T-Rex” processors (e.g., the R12000S processor and its follow-on processors available from SGI, assignee of the present invention) and Intel “Merced” processors (a type of processor anticipated to be available from Intel Corporation). Each type of CPU is implemented on a different board design used to implement the various embodiments of each node 370. Upgrades may be achieved by replacing the (node 370) C-Brick. In one embodiment, MIPS and Merced nodes are not to be mixed within a single system, although systems using both processor types may be connected as a cluster using interconnects other than CrayLink2.
MIPS CPUs
In one embodiment, SN1 supports MIPS T-Rex CPUs, starting with the T-Rex Shrink (R12000S) CPU, which is packaged in a flip-chip package and supports a 200 MHz SYSAD speed (SYSAD is the processor interface 71). In various embodiments, additional MIPS processors are planned to be developed for SN1 enhancements.
In one embodiment, cache sizes for MIPS SN1 nodes are four and eight MB. In one embodiment, the cache is built from nine 256 k×18 or 512 k×18 SSRAMs (synchronous static random access memory chips). The secondary cache for the T-Rex Shrink processor operates at 1⁄2 of the CPU core clock.
Merced CPUs
In one embodiment, SN1 supports Merced-type CPUs. In one embodiment, Merced CPUs are supported by introducing an additional processor interface ASIC, which adapts two Merced CPUs to communicate on one of the SYSAD busses (a processor interface bus 71 of node controller 75). Two processor interface ASIC s are provided per node to implement support for four Merced CPUs. The processor interface ASIC also supports a level-3 cache, which is implemented using DDR SDRAM chips (double-data rate synchronous dynamic random access memory, such as are available from Hitachi and NEC of Japan, and are being sampled by IBM Corp.). This cache improves the effective memory access time for the CPUs, and is also used to perform the protocol translations needed to allow the Merced CPUs to operate in the SN1 system, which is based on the protocols employed in MIPS CPUs.
Main Memory Configuration
In one embodiment, SN1 systems employ custom DIMMs (dual in-line memory modules) containing DDR SDPAM for main memory. The DIMMs that are used in larger SN1 systems (those systems which are capable of scaling beyond 128 processors) are physically similar but contain one additional memory chip to provide enough directory memory to allow building configurations of up to 512 CPUs. These DIMMS are called “premium DIMMs” in this document, and those without the extra directory memory are called “standard DIMMs.” Other than the difference in the directory memory, premium and standard DIMMs are identical and share a common PCB (printed circuit board) design. In systems of less than 128 CPUs, it is acceptable to use the two types interchangeably, and to mix them within a node. In these embodiments, the ratio of (memory data space) to (directory data space) on each of the plurality of memory/directory cards is set to a value that is based on a size of the multiprocessor computer system. In some embodiments, the size is measured as the number of CPUs in the system, and in particular, whether there are (128) or more processors. When (128) or more processors are included, the premium DIMMs having an extra memory chip (i.e., a lower ratio of (memory data space) to (directory data space)) are used.
In one embodiment, the board of each node 370 includes eight DIMM sockets, arranged as four banks of two DIMMs each. Note that this is half the number of DIMM slots implemented in prior systems. This decision was made because of the greater memory densities available in the SN1 time frame. Main memory is implemented using DDR SDRAM parts running at 100 MHz address/200 MHz data and supplying a peak of 3200 Mbyte/sec of bandwidth. The DIMMS employ 128 and 256 Mbit DRAM technology to offer a variety of DIMM sizes to meet various customer needs. With 256 Mbit technology, each SN1 node can support up to eight Gbytes (gigabytes) of memory.
All SN1 DIMMs are built from two base printed circuit types, one supporting ×4 memory (four-bit wide data path) chips for data/ECC and the other supporting ×8 memory (eight-bit wide data path) chips. The following table enumerates the various types that are implemented in various embodiments. All types may be implemented in either standard or premium; the planned implementation is to make the smallest chosen size available in standard only and all other sizes in premium only. The types which are used for one embodiment are shown in bold. Those marked with a * are premium DIMMs.










DIMM Table


















Min.








Increment


DIMM
Fab
DRAM
Data
Dir
(2
Max Node


Size
Type
Tech
DRAM
DRAM
DIMMS)
Capacity





128 MB
x8
128 Mbit
9 -
1 -
256 MB
1 GB





16Mx8
8Mx16


256 MB
x8

18 -
1 -
512 MB
2 GB





16Mx8
8Mx16


 512 MB*
x4

36 -
4 -
 1 GB
4 GB





32Mx4
16Mx8


512 MB
x8
256 Mbit
18 -
2 -
 1 GB
4 GB





32Mx8
16Mx16


1024 MB*
x4

36 -
4 -
 2 GB
8 GB





64MX4
32Mx8









The above table identifies the data memory increment DIMM kits. An increment requires two memory/directory data DIMMs.
In one embodiment, all DIMMs contain an serial PROM which is readable by the system controller. The PROM contains part number, date code, memory chip manufacturer, and other information as specified in the JEDEC standard for SPID PROMs. The DIMM includes a write-enable pin to allow programming of the PROM in the factory. This pin is not be connected on the node board, thereby making it impossible to write the PROM in the system 100.
The C-Brick
The C-Brick for one embodiment houses a single node of up to four CPU's, together with eight DIMM slots, the node controller 75, and L1 system controller. The design of the C-box, in one embodiment, accommodates either a MIPS T-Rex CPU implementation or an Intel Merced CPU implementation. The C-Brick design is based around a removable logic carrier that slides in and out of the front side of the C-Brick for service. This logic carrier unit holds the node electronics, front panel, hot plug fans, L1 display, and cosmetic plastics.
Visible from the front of the C-Brick are the L1 display and 3 front mounted fans. The fans are removable from the front, redundant and hot swappable.
The rear of the C-Brick contains connectors for 48 VDC input power, D-NET, XTalk2 I/O, and USB. The USB port is used for connection to an optional L2 system controller in small systems without a R-Brick. The same USB port could also connect to a L3 system controller if desired.
Fan replacement is the only type of service which is able to be performed while the C-Brick is operating. All other maintenance activities (such as DIMM replacement) will require the brick to be powered down, and the logic carrier unit to be removed from the brick.
“C” Node Brick MIPS T-Rex CPU Implementation
The T-Rex node board set includes a main board and up to two processors boards (PIMM's). The main board of one embodiment is a half-panel (11×17 inches) 16 layer board that holds the node controller 75, eight DIMM sockets for memory 77, three 48 VDC-to-low-voltage DC-DC converters, L1 system controller, and connections to the PIMM (processor in-line module) boards.
Each processor board holds two MIPS CPUs 74 that are soldered directly to the board, along with their L2 cache memory. Each PIMM will provide its own 48 VDC-to-low-voltage conversion through the use of two DC-DC converters on each PIMM. Electrical connection between the main board and each PIMM is provided by two 240-position area-array connector.
CONCLUSION
A first aspect of the present invention provides a multiprocessor computer system (for example, a small multiprocessor system 400 having only two node controllers 75 connected to one another using an interprocessor channel 73, or a multiprocessor system 100 or 500 having up to hundreds or thousands of node controllers 75 connected together through a router network 575 or other interprocessor communications fabric 575). One such embodiment of the system includes a first node controller 75, a second node controller 75, a first plurality of processors 141 operatively coupled to the first node controller 75, a second plurality of processors 141 operatively coupled to the second node controller 75, a first memory 77 operatively coupled to the first node controller 75, a first input/output system 79 operatively coupled to the first node controller 75, and an interprocessor communications network 575 operatively coupled between the first node controller 75 and the second node controller 75. In this embodiment, the first node controller 75 includes: a crossbar unit 279, a memory port 275 operatively coupled between the crossbar unit 279 and the first memory 77, an input/output port 273 operatively coupled between the crossbar unit 279 and the first input/output system 79, a network port 274 operatively coupled between the crossbar unit 279 and the interprocessor communications network 575, and a plurality of independent processor ports 270, including a first processor port 271 operatively coupled between the crossbar unit 279 and a first subset 241 of the first plurality of processors 74, and a second processor port 272 operatively coupled between the crossbar unit 279 and a second subset 242 of the first plurality of processors 74.
In some embodiments of the system, the first node controller 75 is fabricated onto a single integrated-circuit chip 475.
In some embodiments of the system, the first memory 77 is packaged on a plurality of pluggable memory/directory cards 600 wherein each card 600 includes a plurality of memory chips 610 including a first subset of memory chips 620 dedicated to holding memory data and a second subset of memory chips dedicated to holding directory data. Further, the memory port 275 includes a memory data port 613 including a memory data bus 611 and a memory address bus 612 coupled to the first subset of memory chips 610, and a directory data port 623 including a directory data bus 621 and a directory address bus 622 coupled to the second subset of memory chips 620. In some such embodiments, the ratio of (data space in the first subset of memory chips 610) to (data space in the second subset of memory chips 620) on each of the memory/directory cards is set to a value based on a size of the multiprocessor computer system.
In some embodiments of the system, the crossbar unit 279 selectively combines two serially received doublewords of data into a single quadword micropacket for transmission through the crossbar unit 279, and wherein each doubleword contains at least 64 bits of data and the single quadword contains at least 128 bits of data.
In some embodiments of the system 400, the first node controller 75 and the second node controller 75 are directly connected to one another by the interprocessor communications network 73. In other embodiments of the system 100, 300, the first node controller 75 and the second node controller 75 are indirectly connected to one another through a router chip 76 that is also connected to one or more other node controllers 75.
Another aspect of the present invention provides a first node controller 75 for use in a multiprocessor computer system 100, 300, 500 having one or more other node controllers 75. This first node controller 75 includes a crossbar unit 279, a memory port 275 operatively coupled to the crossbar unit 279 for communicating to a memory 77, an input/output port 273 operatively coupled to the crossbar unit 279 for communicating to a first input/output system 79, a network port 274 operatively coupled to the crossbar unit 279 for communicating to a second node controller 75 across an interprocessor-communications network 575, and a plurality of independent processor ports 270. These processor ports 270 include a first processor port 271 operatively coupled to the crossbar unit 279 for communicating to a first subset 241 of a first plurality of processors 74, and a second processor port 272 operatively coupled to the crossbar unit 279 or communicating to a second subset 242 of the first plurality of processors 74.
In various embodiments of the node controller, various details are optionally included, as described above for embodiments of the first system aspect of the invention.
Another aspect of the present invention provides a multiprocessor system 100, 300, or 500 (the “second system”) that includes one or more node controllers 75 including a first node controller 75, a first plurality of processors 74 operatively coupled to the first node controller 75, a first memory 77 operatively coupled to the first node controller 75. This first node controller 75 is packaged as a single integrated circuit chip 475 that includes a crossbar unit 279, a memory port 275 operatively coupled between the crossbar unit 279 and the first memory 77, and a plurality of independent processor ports, including a first processor port operatively coupled between the crossbar unit 279 and a first subset 241 of the first plurality of processors 74, and a second processor port 272 operatively coupled between the crossbar unit 279 and a second subset 242 of the first plurality of processors 74, wherein the first subset 241 includes a plurality of processors 74 and the second subset 242 includes a plurality of processors 74.
In some embodiments of the second system, the system further includes a first input/output system 79 operatively coupled to the first node controller 75, and the first node controller 75 further includes an input/output port 273 operatively coupled between the crossbar unit 279 and the first input/output system 79.
In some embodiments of the second system, the system further includes an interprocessor communications channel 73 operatively coupled between the first node controller 75 and a second node controller 75; and the first node controller 75 further comprises a network port 274 operatively coupled between the crossbar unit 279 and the interprocessor communications channel 73.
In some embodiments of the second system, the system further includes a first input/output system 79 operatively coupled to the first node controller 75, and an interprocessor communications network 575 operatively coupled between the first node controller 75 and a second node controller 75. The first node controller 75 of these embodiments further includes an input/output port 273 operatively coupled between the crossbar unit 279 and the first input/output system 79, and a network port 274 operatively coupled between the crossbar unit 279 and the interprocessor communications network 575.
In some embodiments of the second system, the first memory 77 is packaged on a plurality of pluggable memory/directory cards 600, each card including a plurality of memory chips including a first subset of memory chips 610 dedicated to holding memory data and a second subset of memory chips 620 dedicated to holding directory data, wherein the memory port 275 further includes a memory data port 613 including a memory data bus 611 and a memory address bus 612 coupled to the first subset of memory chips 610, and a directory data port 623 including a directory data bus 621 and a directory address bus 622 coupled to the second subset of memory chips 620. In some such embodiments, the ratio of (data space in the first subset of memory chips 610) to (data space in the second subset of memory chips 620) on each of the plurality of memory/directory cards 600 is set to a value that is based on a size of the multiprocessor computer system.
Another aspect of the present invention provides a method usable with one or more of the above described systems. The method includes transmitting data between the memory port 275 and the first processor port 271, between the memory port 75 and the second processor port 272, between the memory port 275 and the input/output port 273, and between the memory port 275 and the network port 274.
Some embodiments of the method further include transmitting data directly between the first node controller 75 and the second node controller 75 that are directly connected to one another by the interprocessor communications channel 73.
Some embodiments of the method further include transmitting data indirectly between the first node controller 75 and the second node controller 75 through an interprocessor fabric 575 that is also connected to one or more other node controllers 75.
Some embodiments of the method further include transmitting data between any two of the memory port, the first processor port, the second processor port, the input/output port and the network port.
In some embodiments of the method, the transmitting of data between any two of the memory port, the first processor port, the second processor port, the input/output port and the network port is performed in a non-blocking manner such that a plurality of such transmissions occur simultaneously.
Another aspect of the present invention provides a system that varies the relative size of the directory based on a size of the system, such as the number of processors, the amount of memory, and/or the number of nodes. Some such embodiments provide a multiprocessor system 100, 300 or 500 that includes a plurality of node controllers 75 including a first node controller 75, wherein each one of the plurality of node controllers 75 includes a memory port 275 and a separate network port 274 and a separate first processor port 277 and optionally a second processor port 272, an interprocessor communications network operatively coupled to the network port 274 of each respective one of the plurality of node controllers 75, a plurality of processors 74 operatively coupled to the first processor port of each respective one of the plurality of node controllers 75, including a first plurality of processors 74 operatively coupled to first processor port 271 of the first node controller 75, and a plurality of separate memories 77, wherein one or more of the plurality of separate memories 77 is operatively coupled locally to the memory port 275 of each respective one of the plurality of node controllers 75, including a first memory 77 operatively coupled locally to the memory port 275 of the first node controller 75, wherein the first memory is packaged on a plurality of pluggable memory/directory cards 600. Each of these cards 600 include a plurality of memory chips 610 including a first subset of memory chips 610 dedicated to holding memory data and a second subset of memory chips 620 dedicated to holding directory data. The memory port 275 of the first node controller 75 further includes a memory data port 613 including a memory data bus 611 and a memory address bus 612 coupled to the first subset of memory chips 610 on each of a plurality of memory/directory cards 600 such that memory data is accessed simultaneously from the plurality of memory cards 600, and a directory data port 613 including a directory data bus 621 and a directory address bus 622 coupled to the second subset of memory chips 620 on each of the plurality of memory/directory cards 600 such that directory data is accessed simultaneously from a plurality of memory cards 600 independent of memory data accesses. In some of these embodiments, the ratio of (data space in the first subset of memory chips 610) to (data space in the second subset of memory chips 620) on each of the plurality of memory/directory cards 600 is set to a value that is based on a size of the multiprocessor computer system. In various embodiments, the size that determines the ratio is based on a number of processors 74, an amount of memory 77, a number of routers 76, and/or a number of node controllers 75.
It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of the invention should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.

## Claims

1. A node controller in a computer system, comprising:
a datapath crossbar operable to pass message frames in a dedicated format;
a plurality of output queues, each output queue associated with a local source, a particular output queue operable to buffer outgoing message frames from the local source for transfer to the datapath crossbar, the particular output queue operable to rate match between a bandwidth of the datapath crossbar and a bandwidth of the local source, the particular output queue operable to provide synchronization between the datapath crossbar and the local source, the particular output queue having a unit interface customized to a unique requirement of the associated local source, the particular output queue having a datapath interface that is uniform with the datapath crossbar for all output queues;
a memory/directory interface unit operable to convert data to and from a format of a memory device coupled thereto and the dedicated format of the datapath crossbar;
an input/output interface unit operable to convert data to and from a format of a device coupled thereto and the dedicated format of the datapath crossbar;
a network interface unit operable to convert data to and from a network format and the dedicated format of the datapath crossbar;
a processing device interface unit operable to convert data to and from a format of a processing device coupled thereto and the dedicated format of the datapath crossbar;
wherein the output queues associated with the memory/directory interface unit include separate header and data buffers.

2. The node controller of claim 1, wherein the unit interface operates at a clock speed of the local source and the datapath operates at a clock speed of the datapath crossbar.

3. The node controller of claim 1, wherein the particular output queue is operable to bypass synchronization when the associated local source is synchronized with the datapath crossbar.

4. The node controller of claim 1, wherein the dedicated format of a particular message frame indicates which port of the datapath crossbar the particular message frame is destined, whether the particular message is a request or a reply, and whether the particular message frame is a last frame of a message.

5. The node controller of claim 1, wherein the datapath crossbar is operable to interleave message frames associated with different virtual channels.

6. The node controller of claim 1, further comprising:
an arbiter operable to control message frame transfer within the datapath crossbar.

7. The node controller of claim 6, wherein the arbiter prevents mixing of message frames for different messages on one virtual channel.

8. The node controller of claim 6, wherein the arbiter is operable to provide wavefront arbitration for the output queues, wavefront arbitration allowing a particular output queue to read data upon grant from a buffer location in a first clock cycle and provide the data to the datapath crossbar in a second clock cycle.

9. The node controller of claim 6, wherein the arbiter is operable to provide bypass arbitration, bypass arbitration allowing a particular output queue to provide data upon grant to the datapath crossbar in a single clock cycle upon receipt without storing the data in a buffer.

10. The node controller of claim 1, wherein the header buffer handles all message frames associated with a request from the memory/directory interface unit.

11. The node controller of claim 1, wherein the data buffer includes dual buffers written into simultaneously by the memory/directory interface unit and read alternatingly by the datapath crossbar.

12. The node controller of claim 1, wherein the output queues associated with the memory directory unit include a dedicated output queue for the processing device interface unit and a dedicated output queue associated with the other units of the node controller.

13. The node controller of claim 1, wherein the network interface unit is operable to provide message frames associated with read requests directly to the memory/directory interface unit and bypass the datapath crossbar.

14. The node controller of claim 1, wherein the network interface unit and the memory/directory interface unit are aware of a buffer depth for its associated output queues.

15. The node controller of claim 14, wherein the network interface unit and the memory directory interface unit are each operable to receive an indication that a buffer location in its associated output queues has become available for use.

16. The node controller of claim 1, wherein the datapath crossbar is operable to pass copies of message frames entering and leaving the datapath crossbar unit to the network interface unit regardless of a destination for the message frames.

17. The node controller of claim 1, further comprising:
a plurality of input queues associated with local destinations that are asynchronous with the datapath crossbar.

18. The node controller of claim 17, wherein a fill level of the input queues is used to control a flow of message frames from the output queues.