System having configurable interfaces for flexible system configurations Number:7,394,823 from the United States Patent and Trademark Office (PTO) owispatent An apparatus includes a plurality of memories, a plurality of systems, and a switch interface circuit. Each of the plurality of systems includes a memory controller coupled to a respective one of the plurality of memories. Additionally, each of the plurality of systems is coupled to at least one other one of the plurality of systems. Each of the plurality of systems further includes one or more coherent agents configured to access the plurality of memories, and wherein the plurality of systems enforce coherency across the plurality of systems for at least some accesses. At least one of the plurality of systems is coupled to the switch interface circuit separate from the interconnection of the plurality of systems. The switch interface circuit is configured to interface the apparatus to a switch fabric.<H configurations, configurable, System, having, c, 7394823.html, Patent, pto, 7394823

Title: System having configurable interfaces for flexible system configurations

Abstract: An apparatus includes a plurality of memories, a plurality of systems, and a switch interface circuit. Each of the plurality of systems includes a memory controller coupled to a respective one of the plurality of memories. Additionally, each of the plurality of systems is coupled to at least one other one of the plurality of systems. Each of the plurality of systems further includes one or more coherent agents configured to access the plurality of memories, and wherein the plurality of systems enforce coherency across the plurality of systems for at least some accesses. At least one of the plurality of systems is coupled to the switch interface circuit separate from the interconnection of the plurality of systems. The switch interface circuit is configured to interface the apparatus to a switch fabric.

Patent Number: 7,394,823 Issued on 07/01/2008 to Sano

Inventors: Sano; Barton J. (Fremont, CA)
Assignee: Broadcom Corporation (Irvine, CA)

Appl. No.: 10/270,014

Filed: October 11, 2002

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
60380740	May., 2002
60348777	Jan., 2002
60348717	Jan., 2002
60344713	Dec., 2001
60331789	Nov., 2001

Current U.S. Class: 370/419 ; 370/235; 711/141

Current International Class: H04L 12/56 (20060101)

Field of Search: 370/235,419 711/141

References Cited [Referenced By]

U.S. Patent Documents


4788679	November 1988	Kataoka et al.
5623628	April 1997	Brayton et al.
5644753	July 1997	Ebrahim et al.
5689500	November 1997	Chiussi et al.
5710907	January 1998	Hagersten et al.
5805590	September 1998	Gillard et al.
5878268	March 1999	Hagersten
5887138	March 1999	Hagersten et al.
5920226	July 1999	Mimura
5925097	July 1999	Gopinath et al.
5961623	October 1999	James et al.
5963745	October 1999	Collins et al.
6009426	December 1999	Jouenne et al.
6070215	May 2000	Deschepper et al.
6094715	July 2000	Wilkinson et al.
6101420	August 2000	Van Doren et al.
6105119	August 2000	Kerr et al.
6108739	August 2000	James et al.
6108752	August 2000	Van Doren et al.
6128728	October 2000	Dowling
6138217	October 2000	Hamaguchi
6182201	January 2001	Arimilli et al.
6185520	February 2001	Brown et al.
6195739	February 2001	Wright et al.
6202132	March 2001	Islam et al.
6209065	March 2001	Van Doren et al.
6219755	April 2001	Klein
6249846	June 2001	Van Doren et al.
6266731	July 2001	Riley et al.
6298370	October 2001	Tang et al.
6338122	January 2002	Baumgartner et al.
6901052	May 2005	Buskirk et al.
2001/0039604	November 2001	Takahashi
2002/0038407	March 2002	Mounes-Toussi et al.
2004/0062261	April 2004	Zecharia et al.

Foreign Patent Documents


199 07 200	Feb., 1999	DE
265 636	Oct., 1986	EP
893 766	Jan., 1999	EP
920 157	Jun., 1999	EP
936 555	Aug., 1999	EP
945 805	Sep., 1999	EP
777 179	May., 2002	EP
98/15155	Apr., 1998	WO
WO 00/38069	Jun., 2000	WO

Other References

Giorgi et al.; PSCR: A Coherence Protocol for Eliminating Passive Sharing in Shared-Bus Shared-Memory Multiprocessors; IEEE Transactions on Parallel and Distributed Systems; vol. 10, No. 7, Jul. 1999. cited by other .
"They Design and Analysis of Dash: A Scalable Directory-Based Multiprocessor," Daniel Lenoski, Dec. 1991, A Dissertation submitted to the Dept. of Elect. Engin. And the committee on graduate studies of Stanford Univ., 176 pages. cited by other .
"An Argument for Simple COMA," Saulsbury, et al., Aug. 1, 1994, SISC Research Report No. R94:15, 20 pages. cited by other .
Tom R. Halfhill, "SiByte Reveals 64-Bit Core For NPUs; Independent MIPS64 Design Combines Low Power, High Performance," Microdesign Resources, Jun. 2000, Microprocessor Report, 4 pages. cited by other .
SiByte, "Target Applications," http://sibyte.com/mercurian/applications.htm, Jan. 15, 2001, 2 pages. cited by other .
SiByte, "SiByte Technology," http://sibyte.com/mercurian/technology.htm, Jan. 15, 2001, 3 pages. cited by other .
SiByte, "The Mercurian Processor," http://sibyte.com/mercurian, Jan. 15, 2001, 2 pages. cited by other .
SiByte, "Fact Sheet," SB-1 CPU, Oct. 2000, rev. 0.1, 1 page. cited by other .
SiByte, "Fact Sheet," SB-1250, Oct. 2000, rev. 0.2, 10 pages. cited by other .
Stepanian, SiByte, SiByte SB-1 MIPS64 CPU Core, Enbedded Processor Forum 2000, Jun. 13, 2000, 15 pages. cited by other .
Jim Keller, "The Mercurian Processor: A High Performance, Power-Efficient CMP for Networking," Oct. 10, 2000, 22 pages. cited by other .
Intel, "21143 PCI/CardBus 10/100Mb/s Ethernet LAN Controller," Hardware Reference Manual, Revision 1.0, Oct. 1998, 219 pages. cited by other .
European Search Report for EP26011, mailed Mar. 6, 2003, 5 pages. cited by other .
EP Search Report for EP app 02025691.3, May 9, 2003, Broadcom Corp. cited by other.

Primary Examiner: Pham; Chi
Assistant Examiner: Chou; Albert T.
Attorney, Agent or Firm: Garlick Harrison & Markison

Parent Case Text

This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 60/380,740, filed May 15, 2002. This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 60/331,789, filed Nov. 20, 2001. This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 60/344,713, filed Dec. 24, 2001. This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 60/348,777, filed Jan. 14, 2002. This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 60/348,717, filed Jan. 14, 2002.

Claims

What is claimed is:

1. An apparatus comprising: a plurality of memories; a plurality of systems, each of the plurality of systems including at least one processor, a cache, interface circuits for receiving and sending data, a bridge and a memory controller, in which the memory controller is coupled to a respective one of the plurality of memories and each of the plurality of systems is coupled to at least one other one of the plurality of systems for bi-directional data transfer between the plurality of systems, wherein each of the plurality of systems further comprises one or more coherent agents configured to access the plurality of memories, and wherein the plurality of systems enforce coherency across the plurality of systems for at least some accesses, the plurality of systems including at least one system to bi-directionally receive and transmit packets to and from a network; and a switch interface circuit, wherein at least one system is coupled to the switch interface circuit separate from the interconnection of the plurality of systems, wherein the switch interface circuit is configured to interface the apparatus to a switch fabric, and wherein the switch interface circuit is coupled to bi-directionally receive and transmit packets between the at least one system coupled to the switch interface circuit and the switch fabric.

2. The apparatus as recited in claim 1 further comprising a port aggregator circuit coupled to the network through a plurality of ports to receive and transmit packets.

3. The apparatus as recited in claim 2 wherein the port aggregator circuit is configured to aggregate packets from the network ports.

4. The apparatus as recited in claim 1 further comprising a coprocessor coupled to one of the plurality of systems.

5. The apparatus as recited in claim 4 wherein the coprocessor is configured to assist in processing packets.

6. The apparatus as recited in claim 4 wherein the coprocessor is configured to perform a lookup function.

7. The apparatus as recited in claim 4 wherein the coprocessor is configured to perform security processing on a packet.

8. The apparatus as recited in claim 1 wherein each of the plurality of systems is integrated onto a separate integrated circuit.

9. The apparatus as recited in claim 1 wherein at least one system is coupled to an input/output (I/O) interface.

10. The apparatus as recited in claim 9 wherein the at least one system that is coupled to the I/O interface is to receive and transmit packets for data transfer with the I/O interface through the bridge.

11. The apparatus as recited in claim 9 wherein the at least one system that is coupled to the I/O interface is to receive and transmit packets for data transfer with the I/O interface through the bridge and the interface circuits.

12. The apparatus as recited in claim 1 wherein the at least one system to receive and transmit packets to and from the network is disposed on a first circuit card, and wherein at least one other one of the plurality of systems is attached to a second circuit card coupled to the first circuit card.

13. A network device comprising; a switch fabric; and one or more line cards coupled to the switch fabric, wherein each of the line cards is coupled to receive and transmit packets to a respective network, and wherein each of the line cards comprises: a plurality of memories; a plurality of systems, each of the plurality of systems including at least one processor, a cache, interface circuits for receiving and sending data, a bridge, and a memory controller, in which the memory controller is coupled to a respective one of the plurality of memories and each of the plurality of systems is coupled to at least one other one of the plurality of systems for bi-directional data transfer between the plurality of systems, wherein each of the plurality of systems further comprises one or more coherent agents configured to access the plurality of memories, and wherein the plurality of systems enforce coherency across the plurality of systems for at least some accesses, and wherein the plurality of systems are further configured to route packets between at least some of the plurality of systems, the plurality of systems including at least one system to bi-directionally receive and transmit packets to and from the respective network; and a switch interface circuit, wherein at least one system is coupled to the switch interface circuit separate from the interconnection of the plurality of systems, wherein the switch interface circuit is configured to interface the apparatus to the switch fabric, and wherein the switch interface circuit is coupled to bi-directionally receive and transmit packets between the at least one system coupled to the switch interface circuit and the switch fabric.

14. The network device as recited in claim 13 wherein each of the plurality of line cards further comprises a port aggregator circuit coupled to the respective network through a plurality of ports to receive and transmit packets.

15. The network device as recited in claim 13 wherein each of the plurality of line cards further comprises a coprocessor coupled to one of the plurality of systems.

16. The network device as recited in claim 15 wherein one of the coprocessors is configured to assist in processing packets.

17. The network device as recited in claim 15 wherein one of the coprocessors is configured to perform a lookup function.

18. The network device as recited in claim 15 wherein one of the coprocessors is configured to perform security processing on a packet.

19. The network device as recited in claim 13 further including a network service card comprising: a plurality of service card memories; and a plurality of service card systems, each of the plurality of service card systems including a memory controller coupled to a respective one of the plurality of service card memories and each of the plurality of service card systems coupled to at least one other one of the plurality of service card systems, wherein each of the plurality of service card systems further includes one or more coherent agents configured to access the plurality of service card memories, and wherein the plurality of service card systems enforce coherency across the plurality of service card systems for at least some accesses.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention is related to the fields of packet processing and coherency.

2. Description of the Related Art

With the continued expansion of networks, networked systems (e.g. local area networks (LANs), wide area networks (WANs), the Internet, etc.), and emerging storage subsystem technologies such as network attached storage (NAS) and storage area network (SAN), packet processing is an increasingly important function for a variety of systems. The amount of packet processing to be performed may be increasing due to the increased amount of packet traffic, as well as the more sophisticated packet processing that is being attempted on each packet (e.g. processing at deeper layers of the packet).

In the past, packet processing circuitry was often implemented via fixed-function (non-programmable) devices. As packet interfaces, packet content, and packet standards evolved, the fixed-function devices would be redesigned to handle the changes. More recently, network processing units (NPUs) have been implemented to provide programmable packet processing solutions. However, NPUs have generally not provided robust scalability to multiple NPUs, and thus NPUs may have to be replaced when the processing power of the NPUs is no longer sufficient to handle the desired packet processing.

SUMMARY OF THE INVENTION

In one embodiment, an apparatus includes a plurality of memories, a plurality of systems, and a switch interface circuit. Each of the plurality of systems includes a memory controller coupled to a respective one of the plurality of memories. Additionally, each of the plurality of systems is coupled to at least one other one of the plurality of systems. Each of the plurality of systems further includes one or more coherent agents configured to access the plurality of memories, and wherein the plurality of systems enforce coherency across the plurality of systems for at least some accesses. At least one of the plurality of systems is coupled to the switch interface circuit separate from the interconnection of the plurality of systems. The switch interface circuit is configured to interface the apparatus to a switch fabric.

In another embodiment, a network device includes a switch fabric and one or more line cards coupled to the switch fabric. Each line card includes a plurality of memories and a plurality of systems as described above. In one implementation, the network device may further include one or more network cards comprising a plurality of memories and a plurality of systems as described above.

BRIEF DESCRIPTION OF THE DRAWINGS

The following detailed description makes reference to the accompanying drawings, which are now briefly described.

FIG. 1 is a block diagram of one embodiment of a system.

FIG. 2 is a block diagram of one embodiment of a network device.

FIG. 3 is a block diagram of a first embodiment of a line card shown in FIG. 2.

FIG. 3a is a block diagram of a second embodiment of a line card shown in FIG. 2.

FIG. 4 is a block diagram of a third embodiment of a line card shown in FIG. 2.

FIG. 5 is a block diagram of one embodiment of a network service card shown in FIG. 2.

FIG. 6 is a block diagram of one embodiment of a storage card.

FIG. 7 is a block diagram illustrating one embodiment of virtual channels in the integrated circuit of FIG. 1.

FIG. 8 is a block diagram of one embodiment of an Rx circuit shown in FIG. 1.

FIG. 9 is a block diagram of one embodiment of an H&R block shown in FIG. 8.

FIG. 10 is a state machine illustrating operation of one embodiment of the switch shown in FIG. 1.

FIG. 11 is a block diagram of one embodiment of a descriptor ring which may be used by one embodiment of a packet DMA circuit shown in FIG. 1.

FIG. 12 is a block diagram of one embodiment of a descriptor shown in FIG. 11.

FIG. 13 is a table of exemplary transaction and exemplary coherency commands.

FIG. 14 is a block diagram of one embodiment of an address space used by one embodiment of the system.

FIG. 15 is a decision tree illustrating operation of one embodiment of a node for a read transaction on the interconnect within the system.

FIG. 16 is a decision tree illustrating operation of one embodiment of a node for a write transaction on the interconnect within the system.

FIG. 17 is a diagram illustrating operation of one embodiment of the memory bridge shown in FIG. 1 for remote coherency commands received by the memory bridge.

FIG. 18 is a table illustrating exemplary updates of one embodiment of a remote line directory.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF EMBODIMENTS

System Overview

Turning now to FIG. 1, a block diagram of one embodiment of a system 10 is shown. In the embodiment of FIG. 1, the system 10 includes one or more processors 12A-12N, a memory controller 14, a switch 18, a set of interface circuits 20A-20C, a memory bridge 32, a packet DMA circuit 16, and an L2 cache 36. The memory bridge 32 includes a remote line directory 34. The system 10 includes an interconnect 22 to which the processors 12A-12N, the memory controller 14, the L2 cache 36, the memory bridge 32, the packet direct memory access (DMA) circuit 16, and the remote line directory 34 are coupled. The system 10 is coupled, through the memory controller 14, to a memory 24. The interface circuits 20A-20C each include a receive (Rx) circuit 26A-26C and a transmit (Tx) circuit 28A-28C. The system 10 is coupled to a set of interfaces 30A-30C through respective interface circuits 20A-20C. The interface circuits 20A-20C are coupled to the switch 18, which is further coupled to the memory bridge 32 and the packet DMA circuit 16. A configuration register 38 is also illustrated in FIG. 1, which stores a node number (Node #) for the system 10. The configuration register 38 is coupled to the L2 cache 36, the memory controller 14, the memory bridge 32, and the interface circuits 20A-20C in the embodiment of FIG. 1. The processors 12A-12N may also be coupled to receive the node number from the configuration register 38.

The system 10 may be configurable as a node in a multinode coherent system. In such a coherent system, internode coherency may be maintained via coherency commands transmitted to the system 10 and by the system 10 on one or more of the interfaces 30A-30C (via the interface circuits 20A-20C, respectively). Additionally, packets may be transmitted/received on one or more interfaces 30A-30C (via the interface circuits 20A-20C). Furthermore, noncoherent commands (e.g. communications with input/output (I/O) circuits) may be transmitted/received on one or more interfaces 30A-30C. Thus, a mix of packet, noncoherent, and coherent traffic may be received on the interfaces 30A-30C. Particularly, at least one of the interfaces 30A-30C may carry a mix of packet, noncoherent, and coherent traffic.

As used herein, a memory bridge includes circuitry designed to handle internode coherency functions within a node. Thus, the memory bridge 32 may be a source/destination of the coherency commands. In response to at least some received coherency commands, the memory bridge 32 may generate corresponding transactions on the interconnect 22. In response to at least some transactions on the interconnect 22 generated by other agents, the memory bridge 32 may generate coherency commands. The memory bridge 32 may also handle transmission and processing of noncoherent commands, in one embodiment.

As used herein, a packet DMA circuit comprises circuitry to communicate packets to and from a memory. The packet DMA circuit 16 may generate write transactions on the interconnect 22 to the memory controller 14 to write received packets to the memory 24, and may generate read transactions on the interconnect 22 to read packets from the memory 24 for transmission by one of the interface circuits 20A-20C.

The switch 18 may separate coherent traffic and packet traffic from the interface circuits 20A-20C, routing the coherent traffic to the memory bridge 32 and routing the packet traffic to the packet DMA circuit 16. In one embodiment, the switch 18 may generally select sources and destinations to be coupled for communication based on requests from the sources to transmit data and requests from the destinations for data. For example, the interface circuits 20A-20C (particularly the Rx circuits 26A-26C) may identify coherency commands and packets received on the interfaces 30A-30C, and may request transfer to the packet DMA circuit 16 (for packets) and the memory bridge 32 (for coherency commands). If the packet DMA circuit 16 or memory bridge 32 has indicated the ability to receive data of the corresponding type, the switch 18 may grant a transfer between a requesting Rx circuit 26A-26C and the packet DMA circuit 16 or the memory bridge 32. Similarly, the packet DMA circuit 16 or memory bridge 32 may request a transfer to an interface circuit 20A-20C (particularly, to a Tx circuit 28A-28C). If the Tx circuit 28A-28C has indicated the ability to receive data of the corresponding type, the switch 18 may grant a transfer between the requesting packet DMA circuit 16/memory bridge 32 and the Tx circuit 28A-28C.

In one embodiment, the interfaces 30A-30C may support a set of virtual channels in which coherency commands, noncoherent commands, and packets are transmitted. Each virtual channel is defined to flow independent of the other virtual channels, even though the virtual channels may share certain physical resources (e.g. the interface 30A-30C on which the commands are flowing). These virtual channels may be mapped to internal virtual channels (referred to as switch virtual channels herein). The switch 18 may be virtual-channel aware. That is, the switch 18 may grant a coupling between a source and a destination based not only on the ability of the source to transfer data and the destination to receive data, but also on the ability of the source to transfer data in a particular switch virtual channel and the destination to receive data on that switch virtual channel. Thus, requests from sources may indicate the destination and the virtual channel on which data is to be transferred, and requests from destinations may indicate the virtual channel on which data may be received. The switch virtual channels may identify a destination and a virtual channel at that destination, and they may be referred to as the destination and virtual channel, or collectively as the switch virtual channel, herein.

Additionally, in some embodiments, the switch 18 may merge inputs to a given destination virtual channel on a packet boundary. That is, if two sources are requesting to transfer packet data to the same destination and virtual channel, and one of the sources has been granted to that destination and virtual channel, the switch inhibits granting to the other source for that destination and virtual channel until the current source reaches a packet boundary. A similar boundary condition may be used for coherency commands, if more than one transfer through the switch 18 is used to transfer coherency commands.

Each of the interfaces 30A-30C used for coherent communications are defined to be capable of transmitting and receiving coherency commands. Particularly, in the embodiment of FIG. 1, those interfaces 30A-30C may be defined to receive/transmit coherency commands to and from the system 10 from other nodes. Additionally, other types of commands may be carried. In one embodiment, each interface 30A-30C that is used to carry coherency commands may be a HyperTransport.TM. (HT) interface, including an extension to the HT interface to include coherency commands (HTcc). Additionally, in some embodiments, an extension to the HyperTransport interface to carry packet data (Packet over HyperTransport, or PoHT) may be supported. As used herein, coherency commands include any communications between nodes that are used to maintain coherency between nodes. The commands may include read or write requests initiated by a node to fetch or update a cache block belonging to another node, probes to invalidate cached copies of cache blocks in remote nodes (and possibly to return a modified copy of the cache block to the home node), responses to probe commands, fills which transfer data, etc. A noncoherent command is a communication between devices that does not necessarily occur coherently. For example, standard HT commands may be noncoherent commands.

A given HT interface may thus carry a mix of coherent, noncoherent and packet traffic. Traffic on a given HT interface received by one of the interface circuits 20A-20C may be routed: (i) to the packet DMA circuit 16 (for a PoHT command); (ii) the memory bridge 32 (for a coherent command or non-coherent command to be processed in the system 10); or (iii) another interface circuit 20A-20C (for any type of command not targeted at the system 10). The virtual channels on the HT interfaces may include the standard HT virtual channels as well as some additional virtual channels defined for the HTcc and/or PoHT extensions. The HTcc virtual channels are shown in FIG. 13, and the PoHT extensions may include a number of packet virtual channels (e.g. 16 virtual channels, in one embodiment).

In some embodiments, one or more of the interface circuits 20A-20C may not be used for coherency management and may be defined as packet interfaces. The corresponding interfaces 30A-30C may be HT interfaces using the PoHT extension. Alternative, such interfaces 30A-30C may be system packet interfaces (SPI) according to any level of the SPI specification set forth by the Optical Internetworking Forum (e.g. level 3, level 4, or level 5). In one particular embodiment, the interfaces may be SPI-4 phase 2 interfaces. In the illustrated embodiment, each interface circuit 20A-20C may be configurable to communicate on either the SPI-4 interface or the HT interface. Each interface circuit 20A-20C may be individually programmable, permitting various combinations of the HT and SPI-4 interfaces as interfaces 30A-30C. The programming may be performed in any fashion (e.g. sampling certain signals during reset, shifting values into configuration registers (not shown) during reset, programming the interfaces with configuration space commands after reset, pins that are tied up or down externally to indicate the desired programming, etc.). Other embodiments may employ any interface capable of carrying packet data (e.g. the Media Independent Interface (MII) or the Gigabit MII (GMII) interfaces, X.25, Frame Relay, Asynchronous Transfer Mode (ATM), etc.). The packet interfaces may carry packet data directly (e.g. transmitting the packet data with various control information indicating the start of packet, end of packet, etc.) or indirectly (e.g. transmitting the packet data as a payload of a command, such as PoHT). The SPI-4 interface may define 16 hardware virtual channels, extendable to 256 virtual channels in software.

An overview of one embodiment of the internode coherency mechanism is next provided. Additional details regarding the internode coherency mechanism (for one embodiment) are provided further below (e.g. with regard to FIGS. 13-18).

The system 10 may support intranode coherency for transactions on the interconnect 22. Additionally, the system 10 may support internode coherency with other nodes (e.g. a CC-NUMA coherency, in one embodiment). For example, in one embodiment, if a transaction on the interconnect 22 (e.g. a transaction issued by the processors 12A-12N) accesses a cache block that is remote to the system 10 (i.e. the cache block is part of the memory coupled to a different node) and the system 10 does not have sufficient ownership to perform the transaction, the memory bridge 32 may issue one or more coherency commands to the other nodes to obtain the ownership (and a copy of the cache block, in some cases). Similarly, if the transaction accesses a local cache block but one or more other nodes have a copy of the cache block, the memory bridge 32 may issue coherency commands to the other nodes. Still further, the memory bridge 32 may receive coherency commands from other nodes, and may perform transactions on the interconnect 22 to effect the coherency commands.

In one embodiment, a node such as system 10 may have memory coupled thereto (e.g. memory 24). The node may be responsible for tracking the state, in other nodes, of each cache block from the memory in that node. A node is referred to as the "home node" for cache blocks from the memory assigned to that node. A node is referred to as a "remote node" for a cache block if the node is not the home node for that cache block. Similarly, a cache block is referred to as a local cache block in the home node for that cache block and as a remote cache block in other nodes.

Generally, a remote node may begin the coherency process by requesting a copy of a cache block from the home node of that cache block using a coherency command. The memory bridge 32 in the remote node, for example, may detect a transaction on the interconnect 22 that accesses the cache block and may detect that the remote node does not have sufficient ownership of the cache block to complete the transaction (e.g. it may not have a copy of the cache block at all, or may have a shared copy and may require exclusive ownership to complete the transaction). The memory bridge 32 in the remote node may generate and transmit the coherency command to the home node to obtain the copy or to obtain sufficient ownership. The memory bridge 32 in the home node may determine if any state changes in other nodes are to be performed to grant the requested ownership to the remote node, and may transmit coherency commands (e.g. probe commands) to effect the state changes. The memory bridge 32 in each node receiving the probe commands may effect the state changes and respond to the probe commands. Once the responses have been received, the memory bridge 32 in the home node may respond to the remote node (e.g. with a fill command including the cache block).

The remote line directory 34 may be used in the home node to track the state of the local cache blocks in the remote nodes. The remote line directory 34 is updated each time a cache block is transmitted to a remote node, the remote node returns the cache block to the home node, or the cache block is invalidated via probes. As used herein, the "state" of a cache block in a given node refers to an indication of the ownership that the given node has for the cache block according to the coherency protocol implemented by the nodes. Certain levels of ownership may permit no access, read-only access, or read-write access to the cache block. For example, in one embodiment, the modified, shared, and invalid states are supported in the internode coherency protocol. In the modified state, the node may read and write the cache block and the node is responsible for returning the block to the home node if evicted from the node. In the shared state, the node may read the cache block but not write the cache block without transmitting a coherency command to the home node to obtain modified state for the cache block. In the invalid state, the node may not read or write the cache block (i.e. the node does not have a valid copy of the cache block). Other embodiments may use other coherency protocols (e.g. the MESI protocol, which includes the modified, shared, and invalid states and an exclusive state in which the cache block has not yet been updated but the node is permitted to read and write the cache block, or the MOESI protocol which includes the modified, exclusive, shared, and invalid states and an owned state which indicates that there may be shared copies of the block but the copy in main memory is stale). In one embodiment, agents within the node may implement the MESI protocol for intranode coherency. Thus, the node may be viewed as having a state in the internode coherency and individual agents may have a state in the intranode coherency (consistent with the internode coherency state for the node containing the agent).

Generally speaking, a node may include one or more coherent agents (dotted enclosure 40 in FIG. 1). In the embodiment of FIG. 1, the processors 12A-12N, the L2 cache 36, and the memory controller 14 may be examples of coherent agents 40. Also, the memory bridge 32 may be a coherent agent (as a proxy for other nodes, based on the state in the remote line directory 34). However, other embodiments may include other coherent agents as well, such as a bridge to one or more I/O interface circuits, or the I/O interface circuits themselves. Generally, an agent includes any circuit which participates in transactions on an interconnect. A coherent agent is an agent that is capable of performing coherent transactions and/or operating in a coherent fashion with regard to transactions. A transaction is a communication on an interconnect. The transaction is sourced by one agent on the interconnect, and may have one or more agents as a target of the transaction. Read transactions specify a transfer of data from a target to the source, while write transactions specify a transfer of data from the source to the target. Other transactions may be used to communicate between agents without transfer of data, in some embodiments.

In one embodiment, the remote line directory 34 may be configured to track a subset of the local memory space that may be coherently shared with other nodes. That is, the remote line directory 34 may be configured to track up to a maximum number of cache blocks, where the maximum number is less than the total number of cache blocks that may be coherently shared. In another embodiment, the maximum number may be less than the total number of remote cache entries. The remote line directory may have any structure (e.g. cache-like structures such as direct-mapped, fully associative, set associative, etc.). In one embodiment, the remote line directory 34 may be 16 k entries arranged in an 8 way set associative structure. If a cache block is being accessed by a remote node, and the remote line directory 34 in the home node detects a miss for the cache block, an entry is allocated to track the cache block. If the allocated entry is currently allocated to track a second cache block, the memory bridge 32 in the home node may generate probes to evict the second cache block from the other nodes (and possibly write back modified data to the home node, if applicable).

In one implementation, the L2 cache 36 in a remote node is designated to retain the node state for modified remote cache blocks. If the L2 cache 36 evicts a modified remote cache block, the L2 cache 36 may cause the remote block to be evicted from the node as a whole (e.g. using a WrFlush command described below).

It is noted that, in some embodiments, a coherency command may be received by an interface circuit 20A-20C that is passing through the system 10 to another node, and does not require processing in the system 10. The interface circuits 20A-20C may be configured to detect such commands and retransmit them (through another interface circuit 20A-20C via the switch 18) without involving the memory bridge 32.

An overview of the packet processing mechanism of one embodiment of the system 10 is next provided. Additional details of one embodiment may be provided below with respect to FIGS. 7-12.

The system 10 may provide a flexible structure for processing packets and for routing packets without processing by the processors 12A-12N. In one embodiment, the Rx circuits 26A-26C may be programmable to select destinations for packets based on one or more packet attributes. For example, packets may be transmitted on the interfaces 30A-30C in a virtual channel on that interface. The virtual channel may be a packet attribute used for selecting a destination. Additionally, the Rx circuits 26A-26C may be programmable to select one or more packet fields to use in determining a destination. For packets generated by software, the software may select a destination for the packet (e.g. by selecting an output queue in the packet DMA circuit 16 mapped to a given Tx circuit 28A-28C and to a virtual channel on the corresponding interface).

Two or more instantiations of the system 10 may be coupled together to form packet processing systems in which packets are routed among the systems as well as packet circuits. If the Rx circuit 26A-26C receives a packet and determines that the destination for the packet is a Tx circuit 28A-28C (to be transmitted to another system 10 or elsewhere), the Rx circuit 26A-26C may transmit the packet through the switch 18 to the Tx circuit 28A-28C. The packet may not be transmitted to memory, nor acted upon by the processors 12A-12N. Thus, memory bandwidth, storage, and processor time may be used to process packets which are not automatically routed from a source to a destination. In packet processing systems including multiple systems 10, a packet may be routed from an Rx circuit 26A-26C to a Tx circuit 28A-28C that is coupled to an interface to the other system 10, and the Rx circuit 28A-28C in the other system 10 that is coupled to that interface may determine that the destination of the packet is the packet DMA circuit 16 in the other system 10. Alternatively, a packet may be routed through one or more Rx and Tx circuits 26A-26C and 28A-28C from a packet source device to a packet destination device, without any processing by processors 12A-12N in the systems 10.

The Rx circuits 26A-26C may determine that received packets are to be stored to the memory 24 (by the packet DMA circuit 16) for processing within the system 10. In one embodiment, the packet DMA circuit 16 may comprise a set of input queues (the virtual channels in the packet DMA circuit 16) to which a packet may be mapped by the Rx circuits 26A-26C. The switch 18 may route the packets to the packet DMA circuit 16 for storage in the identified input queue. Similarly, software may generate packets and store them in packet DMA circuit output queues. The output queues may be mapped to a Tx circuit 28A-28C (and an output virtual channel in the Tx circuit 28A-28C), and the switch 18 may route packets from the packet DMA circuit 16 to the Tx circuit 28A-28C.

In one embodiment, the input queues and the output queues of the packet DMA circuit 16 may be logical queues. That is, the queues may actually be implemented in memory 24. The packet DMA circuit 16 may include buffers to buffer the packet data being transmitted to and from the memory 24. The queues may be implemented in any fashion. In one particular embodiment, each queue is implemented as a descriptor ring (or chain) which identifies memory buffers to store packet data corresponding to a given input queue. In other embodiments, the queues may be implemented in any desired fashion (e.g. linked lists, contiguous memory locations for memory buffers, etc.). The packet DMA circuit 16 may be configured to read/write descriptors from/to memory 24 as well.

Packets stored to memory by the packet DMA circuit 16 may be processed by software executed by the processors 12A-12N (or software executed on a processor in a remote node, using internode coherency to coherently access the packets). The software may determine that a given packet is terminated in the system 10. Alternatively, the processors 12A-12N may determine that the packet is to be retransmitted on one of the interfaces 30A-30C, and may prepare the packet for transmission by the packet DMA circuit 16. The packet may have been modified by software, or may be unmodified. Additionally, the software may generate packets to be transmitted. In any of these cases, the software may inform the packet DMA circuit 16 of the packet and its location in the memory 24, so that the packet DMA circuit 16 may read the packet from the memory 24 for transmission to the interface circuit 20A-20C coupled to the interface 30A-30C on which the packet is to be transmitted. In one embodiment, the software may inform the packet DMA circuit 16 of the packet by storing the packet in one or more memory buffers indicated by descriptors in the descriptor ring forming an output queue, and updating the descriptor to indicate that the packet DMA circuit 16 owns the descriptor.

As used herein, a "packet" may include any communication between a source and a destination which includes one or more headers defining the source and destination of the packet at various levels within the source and destination and which may include a data payload. "Packet data" may include any data that is part of a packet, or may refer to multiple packets.

As used herein, an interface circuit includes any circuitry configured to communicate on an interface according to the protocol defined for the interface. The interface circuit may include receive circuitry configured to receive communications on the interface and transmit the received communications to other circuitry internal to the system that includes the interface circuit. The interface circuit may also include transmit circuitry configured to receive communications from the other circuitry internal to the system and configured to transmit the communications on the interface.

The processors 12A-12N may be designed to any instruction set architecture, and may execute programs written to that instruction set architecture. Exemplary instruction set architectures may include the MIPS instruction set architecture (including the MIPS-3D and MIPS MDMX application specific extensions), the IA-32 or IA-64 instruction set architectures developed by Intel Corp., the PowerPC instruction set architecture, the Alpha instruction set architecture, the ARM instruction set architecture, or any other instruction set architecture. The system 10 may include any number of processors (e.g. as few as one processor, two processors, four processors, etc.).

The L2 cache 36 may be any type and capacity of cache memory, employing any organization (e.g. set associative, direct mapped, fully associative, etc.). In one embodiment, the L2 cache 36 may be an 8 way, set associative, 1 MB cache. The L2 cache 36 is referred to as L2 herein because the processors 12A-12N may include internal (L1) caches. In other embodiments the L2 cache 36 may be an L1 cache, an L3 cache, or any other level as desired.

The memory controller 14 is configured to access the memory 24 in response to read and write transactions received on the interconnect 22. The memory controller 14 may receive a hit signal from the L2 cache, and if a hit is detected in the L2 cache for a given read/write transaction, the memory controller 14 may not respond to that transaction. The memory controller 14 may be designed to access any of a variety of types of memory. For example, the memory controller 14 may be designed for synchronous dynamic random access memory (SDRAM), and more particularly double data rate (DDR) SDRAM. Alternatively, the memory controller 16 may be designed for DRAM, DDR synchronous graphics RAM (SGRAM), DDR fast cycle RAM (FCRAM), DDR-II SDRAM, Rambus DRAM (RDRAM), SRAM, or any other suitable memory device or combinations of the above mentioned memory devices.

The interconnect 22 may be any form of communication medium between the devices coupled to the interconnect. For example, in various embodiments, the interconnect 22 may include shared buses, crossbar connections, point-to-point connections in a ring, star, or any other topology, meshes, cubes, etc. The interconnect 22 may also include storage, in some embodiments. In one particular embodiment, the interconnect 22 may comprise a bus. The bus may be a split transaction bus, in one embodiment (i.e. having separate address and data phases). The data phases of various transactions on the bus may proceed out of order with the address phases. The bus may also support coherency and thus may include a response phase to transmit coherency response information. The bus may employ a distributed arbitration scheme, in one embodiment. In one embodiment, the bus may be pipelined. The bus may employ any suitable signaling technique. For example, in one embodiment, differential signaling may be used for high speed signal transmission. Other embodiments may employ any other signaling technique (e.g. TTL, CMOS, GTL, HSTL, etc.). Other embodiments may employ non-split transaction buses arbitrated with a single arbitration for address and data and/or a split transaction bus in which the data bus is not explicitly arbitrated. Either a central arbitration scheme or a distributed arbitration scheme may be used, according to design choice. Furthermore, the bus may not be pipelined, if desired.

Various embodiments of the system 10 may include additional circuitry, not shown in FIG. 1. For example, the system 10 may include various I/O devices and/or interfaces. Exemplary I/O may include one or more PCI interfaces, one or more serial interfaces, Personal Computer Memory Card International Association (PCMCIA) interfaces, etc. Such interfaces may be directly coupled to the interconnect 22 or may be coupled through one or more I/O bridge circuits.

In one embodiment, the system 10 (and more particularly the processors 12A-12N, the memory controller 14, the L2 cache 36, the interface circuits 20A-20C, the memory bridge 32 including the remote line directory 34, the packet DMA circuit 16, the switch 18, the configuration register 38, and the interconnect 22) may be integrated onto a single integrated circuit as a system on a chip configuration. The additional circuitry mentioned above may also be integrated. Alternatively, other embodiments may implement one or more of the devices as separate integrated circuits. In another configuration, the memory 24 may be integrated as well. Alternatively, one or more of the components may be implemented as separate integrated circuits, or all components may be separate integrated circuits, as desired. Any level of integration may be used.

It is noted that, while three interface circuits 20A-20C are illustrated in FIG. 1, one or more interface circuits may be implemented in various embodiments. It is further noted that, while the cache block may be referred to as the granularity on which coherency is maintained, other embodiments may use different granularities greater than or less than a cache block in size. In such embodiments, a "coherency block" may be treated in the same fashion as a "cache block" or "block" when discussing coherency above. Generally, a "coherency block" may include a set of contiguous (in memory) bytes which are treated as a unit for coherency purposes. In various embodiments, a coherency block may comprise a portion of a cache block, a single cache block, or multiple cache blocks, as desired.

Use of the System in Network Devices and Storage Devices

One or more instantiations of system 10 may be used to form various network devices and/or storage devices. The processors 12A-12N included in the systems 10 may provide programmability for the network/storage devices, and thus the network devices/storage devices may be adapted to changes in the packet/storage protocols, standards, etc. as they are developed (e.g. by changing the software in the devices). In some implementations, the internode coherency features of the system 10 may be used to provide scalability to multiple systems 10. For example, coherency may be used to permit software access to any memory location (coupled to any system 10) in the same fashion that the local memory locations (coupled to the same system 10 as the initiator of the access). The coherency hardware may handle the transfer of the remote data to the initiator. In other implementations, the packet features of the system 10 (e.g. the routing of packets from an Rx circuit 26A-26C to a Tx circuit 28A-28C) may provide for scalability by passing a packet on to another system 10 without processing in the system 10 (thereby allowing packets to be distributed in the systems 10 without the intervention of the processors 12A-12N to cause the packet distribution). In still other implementations, a combination of the above mechanisms may be used to provide scalability.

Turning now to FIG. 2, a block diagram of one embodiment of a network device 300 is shown. In the embodiment of FIG. 2, the network device 300 includes a plurality of line cards 302A-302E, a network service card 304, and a switch fabric 306. Each of the line cards 302A-302E are coupled to a plurality of network ports and to the switch fabric 306. The network service card 304 is also coupled to the switch fabric 306.

Generally, the line cards 302A-302E are coupled to receive and transmit packets on the network ports. The line cards 302A-302E may process received packets to determine if the packets are, e.g., to be transmitted on another network port or responded to on the receiving network port. If a given packet is to be transmitted on a network port coupled to another line card, the line card 302A-302E may transmit the packet through the switch fabric 306 to that other line card. The line cards 302A-302E may be configured to perform a certain amount of packet processing to determine how to handle the packet. In some cases, deeper packet processing may be required to determine how to handle the packet. The network service card 304 may provide the deeper packet processing. If a line card 302A-302E determines that the network service card 304 is to be used to process a packet, the line card 302A-302E may transmit the packet to the network service card 304 through the switch fabric 306. The network service card 304 may process the packet and, if the packet is to be transmitted on a network port, the network service card 304 may transmit the packet through the switch fabric 306 to the line card 302A-302E that is coupled to that network port. Thus, the line cards 302A-302E may transmit packets on a network port that are received from another line card 302A-302E, from the network service card 304, or on another network port in the same line card 302A-302E.

One or more systems 10 may be implemented in any of the line cards 302A-302E or the network service card 304. As mentioned above, the systems 10 are programmable (via the processors 12A-12N) and thus software may be upgraded to track changes in various standards for packets, packet processing, etc. Additionally, combinations of the packet features and/or coherency features of the systems 10 may be used to scale the number of systems 10 in the card as desired, with minimal impacts to the software. Exemplary embodiments of the line cards 302A-302E and the network service card 304 are shown in FIGS. 3-5.

Generally, the switch fabric 306 may comprise any circuitry and interconnect that permits communication between the line cards 302A-302E and between the network service card 304 and the line cards 302A-302E. Any interface may be used (e.g. switch interfaces such as the universal test and operation physical interface for asynchronous transfer mode (UTOPIA), the common switch interface (CSIX), etc.; standard I/O interfaces such as peripheral component interconnect (PCI), universal serial bus (USB), etc.). For example, in one embodiment, one or more BCM 8832 chips (available from Broadcom Corporation of Irvine, Calif.) may be used.

It is noted that, while one network service card 304 is shown in FIG. 2, other embodiments may include multiple network service cards, if desired. Additionally, embodiments of the network device 300 are contemplated in which one or more storage cards are included for interfacing to storage devices. Such a network device 300 may be used in network attached storage (NAS) implementations or other types of storage devices accessible via a network. An embodiment of a storage card implementing one or more systems 10 is shown in FIG. 6.

Line cards, storage cards, and network service cards may be examples of circuit cards. Generally, a circuit