Communication in partitioned computer systems

A processor or other resource in a computer system may be capable of addressing memory and other resources directly using an address of a definite size. The maximum length of address that a resource can handle determines the extent of the address space that resource can address. A resource can access locations outside its own address space, but this typically requires indirect addressing procedures that require both time and resources. In a multi-processor system, several cells may be arranged to share a “coherency domain” of common, directly addressable address space. However, because each cell must generally be able to address the entire coherency domain directly, the total size of the coherency domain, and thus the sum of the sizes of the cells, is then limited to the address space of any one processor.

For purposes of illustrating the invention, the drawings show one or more forms in which the invention can be embodied. The invention is not, however, limited to the precise forms shown. In the drawings:

FIG. 1 is a block diagram of one embodiment of a computer system according to an embodiment of the invention.

FIG. 2 is a block diagram of a second embodiment of a computer system according to an embodiment of the invention.

FIG. 3 is a block diagram of a third embodiment of a computer system according to an embodiment of the invention.

Referring to the accompanying drawings, and initially to FIG. 1 , one embodiment of a computer system according to the invention, indicated generally by the reference numeral 90 , has a plurality of cells 00 . . . 77 , each including, among other things, at least one processor 92 and memory 94 controlled by a memory controller 96 . In this embodiment, each cell may be identical, and the processor 92 and memory controller 96 in each cell are capable of addressing an address space that is large enough to cover eight cells. In this embodiment, the cell is identified in addresses by the most significant bits of the address, corresponding to the right hand digit of the cell number in FIG. 1 . Memory accesses within the address space of the originating cell can be fast, because the originating cell or processor can specify directly the address of the memory to be accessed, eliminating the latency that would be caused by interpreting an indirect address.

Each cell may belong to a partition P 0 . . . P 7 , identified by the left-hand digit of the cell number in FIG. 1 . In this embodiment, the cells within a partition can freely read data from and write data to any memory within the same partition. Restrictions may be imposed on reading data from, and stricter restrictions may be imposed on writing data to, memory within another partition.

The processor 92 in each cell 00 . . . 77 also has a “processor coherency domain,” which is a range of cells that may be larger than a partition, but is not larger than the address space of the processor, within which that processor can communicate directly with the memory controllers 96 . The processor 92 may be allowed to read data from and write data to memory that is outside its own partition but within the coherency domain of the processor that originates the read or write. Where such reads and writes are permitted, however, they are directly addressed and take place with the corresponding low latency. The memory controller 96 in each cell 00 . . . 77 also has a “memory controller coherency domain,” which is a range of cells that may be larger than a partition, but is not larger than the address space of the memory controller, within which that memory controller can communicate directly with the processors 92 . As will be explained below, the processor coherency domain for the processor in a cell is not necessarily the same as the memory controller coherency domain for the memory controller in the same cell. Where they are the same, or where it is not necessary to distinguish between them, the term “coherency domain” may be used to denote concisely either or both of the processor coherency domain and the memory controller coherency domain.

In this embodiment, partition P 0 contains cells 00 , 01 , 02 , 03 . The processors in the cells in partition P 0 have a processor coherency domain C 0 , which contains memory in those four cells plus memory in cell 14 , which belongs to partition P 1 . Partition P 1 contains cells 14 , 15 , 16 , 17 . The processors 92 in partition P 1 have a processor coherency domain C 1 , which contains memory in those cells plus memory in cell 03 , which belongs to partition P 0 , and cell 20 , which belongs to partition P 2 . Partition P 2 contains cells 20 , 21 , 22 , 23 . The processors in partition P 2 have a processor coherency domain C 2 , which contains memory in those cells plus cell 17 , which belongs to partition P 1 , and cell 34 , which belongs to partition P 3 . Partition P 3 contains cells 34 , 35 , 36 , 37 . The cells in partition P 3 have a processor coherency domain C 3 , which contains memory in those cells plus cell 23 , which belongs to partition P 2 , and cell 40 , which belongs to partition P 4 . Partition P 4 contains cells 40 , 41 , 42 , 43 . The cells in partition P 4 have a processor coherency domain C 4 , which contains memory in those cells plus cell 37 , which belongs to partition P 3 , and cell 54 , which belongs to partition P 5 . Partition P 5 contains cells 54 , 55 , 56 , 57 . The processors in partition P 5 have a processor coherency domain C 5 , which contains memory in those cells plus cell 43 , which belongs to partition P 4 , and cell 60 , which belongs to partition P 6 . Partition P 6 contains cells 60 , 61 , 62 , 63 . The processors in partition P 6 have a processor coherency domain C 6 , which contains memory in those cells plus cell 57 , which belongs to partition P 5 , and cell 74 , which belongs to partition P 7 . Partition P 7 contains cells 74 , 75 , 76 , 77 . The cells in partition P 7 have a processor coherency domain C 7 , which contains memory in those cells plus cell 63 , which belongs to partition P 6 .

As may be seen from FIG. 1 , any cell 00 . . . 77 can identify other cells in the same partition P 0 . . . P 7 unambiguously by the right-hand digit of the cell number. Because this digit represents the most significant bits of an address, a device in a cell can address unambiguously other parts of the partition to which that cell belongs, and can thus target a resource that has an address in the same partition. In addition, a processor 92 in a partition can target directly the memory controllers 96 in the two cells that are outside that partition but in the processor coherency domain of the processor in question. For example, the processors 92 in cells 34 , 35 , 36 , 37 in partition P 3 can target directly the memory controllers in all of cells 23 , 34 , 35 , 36 , 37 , 40 . Similarly, the processors 92 in cells 40 , 41 , 42 , 43 in partition P 4 can target directly the memory controllers in all of cells 37 , 40 , 41 , 42 , 43 , 54 .

The converse does not apply in this embodiment. For example, the memory controller 96 in cell 37 can be targeted by the processors 92 in cells 34 , 35 , 36 , 37 , 40 , 41 , 42 , 43 . Therefore, that memory controller cannot communicate directly with the processor 92 in cell 23 , because an address with the most significant bits “ 3 ” would be ambiguous between cell 23 and cell 43 . Thus, it is possible to define memory controller coherency domains, but they are different from the processor coherency domains. Each pair of cells such as cells 37 , 40 at the overlap of two processor coherency domains will have, for example, an eight-cell memory controller coherency domain, in this example cells 34 , 35 , 36 , 37 , 40 , 41 , 42 , 43 . The alternating pairs of cells in the middle of a partition will have a four-cell memory controller coherency domain consisting of the four cells in that partition. In the interests of clarity, the memory controller coherency domains are not marked in FIG. 1 . Because in this embodiment the memory controller coherency domains are different from the processor coherency domains, logical addresses must be translated into physical routings through the inter-cell fabric of the computer system separately for messages originating from processors and for messages originating from memory controllers.

If data is to be transferred, for example, from cell 00 to cell 77 , then the processor 92 of the source cell 00 can copy that data to memory in cell 03 or, subject to any restrictions on writing to another partition, to memory in cell 14 . From the memory in cell 03 or 14 , the processor of any cell in partition P 1 can copy the data to cell 17 or 20 . From cell 17 or 20 , any cell in partition P 2 can copy the data to cell 23 or cell 34 . From cell 23 or 34 , any cell in partition P 3 can copy the data to cell 37 or 40 , and so on. Eventually the data reaches cell 63 or 74 , from which the data is directly accessible to the destination cell 77 .

The data transfer may require a copy operation carried out by a cell that is neither the origin nor the destination of the data. For example, a transfer from memory in cell 03 to memory in cell 20 may be carried out by cell 15 or cell 16 or, as described above for the transfer from cell 00 to cell 77 , a transfer may require copying by a cell in an intervening partition. The intermediate copying cell then needs to be aware that the data is to be copied, and where it is to be copied to. The data may then be presented in the form of a packet that has a message header indicating the destination partition for the packet. Any intermediate forwarding cell then merely needs to read the packet header and recognize that the packet is to be forwarded to the next processor coherency domain. The forwarding cell does not need to be actively notified of the routing of particular packets. In order to avoid the ambiguous addressing that would sometimes arise from direct processor-to-processor communication between cells in different partitions, some or all of the processors 92 may be programmed to regularly poll the memory areas in which packets for forwarding are placed, and to forward any new packet that arrives without external prompting.

As shown in FIG. 1 , the computer system 90 has 8 processor coherency domains, each with 5 or 6 cells, and 8 partitions, each with 4 cells. By repeating the pattern of overlap shown for partitions P 1 through P 6 and processor coherency domains C 1 through C 6 in FIG. 1 , the number of partitions in the computing system can be increased indefinitely.

If the address space format, as compared to the size of a cell, permits, the number of cells in a coherency domain may be greater than 8. However large the processor and memory controller coherency domains are, with the configuration shown in FIG. 1 the maximum number of cells in a partition is half the maximum number of cells in the address space.

As shown in FIG. 1 , at each overlap between two adjacent processor coherency domains, two cells, one in each partition, belong to both processor coherency domains. This configuration allows highly secure restrictions to be applied to the transfer of data between domains. However, if one partition is allowed to write freely into a cell in the neighboring partition, then an arrangement with only one cell shared between two adjacent processor coherency domains is possible. For example, if all exchanges between partition P 0 and partition P 1 are written in cell 14 , then cell 03 does not need to be in processor coherency domain C 1 . If the amount of traffic between partitions is large, each of the processor coherency domains C 0 . . . C 7 shown in FIG. 1 may be extended by one cell at each end so that, for example, processor coherency domain C 3 also contains cells 22 and 41 . This shares the burden of traffic over all of the memory controllers 96 . Memory in cells that are not in a processor coherency domain other than the one spanning their own partition may be less vulnerable to disruption originating outside the partition. Processors that are not active in inter-partition traffic handling may have more capacity for other operations.

As described above, the chain-like arrangement of the partitions may require repeated copying of data that is to be transferred between cells that are far apart in the chain. By including cell 00 in processor coherency domain C 7 and cell 77 in processor coherency domain C 0 , the chain of partitions shown in FIG. 1 can be changed into a ring. This reduces the maximum distance that data must travel to half the length of the chain, which may provide a useful reduction in latency when the chain is long.

Referring now to FIG. 2 , a second embodiment of a computer system according to the invention, indicated generally by the reference numeral 190 , has a plurality of cells 100 . . . 177 , which are internally similar to the cell 00 shown in FIG. 1 , each including, among other things, a processor 92 , memory 94 , and a memory controller 96 . In this embodiment, each cell may be identical, and the processors 92 in the cells are capable of addressing a processor coherency domain C 10 . . . C 17 of addresses. In this embodiment, the cell is identified in addresses by the most significant bits of the address, corresponding to the right-hand digit of the cell number. Memory accesses within a coherency domain can be fast, because the originating cell or processor can specify directly the address of the memory to be accessed, reducing the latency that would be caused by interpreting an indirect address.

The cells also belong to a partition P 10 . . . P 17 . In this embodiment, the cells within a partition can freely read data from and write data to any memory within the same partition. Restrictions may be imposed on reading data from, and stricter restrictions may be imposed on writing data to, memory within another partition, even if the memory is within the processor coherency domain of the cell that originates the read or write.

In this embodiment, partition P 10 and processor coherency domain C 10 contain cells 100 , 101 , 102 , 103 , 104 , 105 , 106 . Partition P 11 and processor coherency domain C 11 contain cells 110 , 111 , 112 , 113 , 114 , 115 , 116 . Partition P 12 and processor coherency domain C 12 contain cells 120 , 121 , 122 , 123 , 124 , 125 , 126 . Partition P 13 and processor coherency domain C 13 contain cells 130 , 131 , 132 , 133 , 134 , 135 , 136 . Partition P 14 and processor coherency domain C 14 contain cells 140 , 141 , 142 , 143 , 144 , 145 , 146 . Partition P 15 and processor coherency domain C 15 contain cells 150 , 151 , 152 , 153 , 154 , 155 , 156 . Partition P 16 and processor coherency domain C 16 contain cells 160 , 161 , 162 , 163 , 164 , 165 , 166 .

Partition P 17 contains a single cell 177 . Processor coherency domain C 17 contains the cells 100 , 111 , 122 , 133 , 144 , 155 , 166 mentioned above, plus cell 177 .

If data is to be transferred from one “spoke” partition P 10 . . . P 16 to another, for example, from cell 106 to cell 165 , then the processor 92 of the source cell 106 , or another cell in partition P 10 , can copy that data to the memory 94 of cell 100 . From cell 100 , the “hub” cell 177 can copy the data to cell 166 . From cell 166 , the data is directly accessible to the destination cell 165 , or can be copied to cell 165 by another cell in partition P 16 .

The forwarding of packets in the embodiment of FIG. 2 differs from that in the embodiment of FIG. 1 because in FIG. 2 the “hub” cell 177 reads the message header on a packet of data and decide which “spoke” partition P 10 -P 16 the packet is to be delivered to.

In the embodiment shown in FIG. 2 as just described, the hub cell 177 is in the memory controller coherency domain of the “border” cells 100 , 111 , 122 , 133 , 144 , 155 , 166 , but is not in the processor coherency domains of those cells. As a result, all traffic between spoke partitions is handled by the processor in the hub cell 177 reading packets from one border cell and writing them to another border cell. This arrangement minimizes the use of resources in the spoke partitions P 10 . . . P 16 for traffic handling. Alternatively, the border cells 100 . . . 166 may have processor coherency domains that include the hub cell 177 . In that case, the border cell 100 may copy the data directly from the source cell 106 to memory on the hub cell 177 , and border cell 166 may copy the data directly from cell 177 to the destination cell 165 .

Even if the copying of data is handled entirely by the hub cell 177 , the hub cell may be included in the processor coherency domains of the border cells 100 , 111 , . . . . This enables the processors 92 in the border cells to communicate directly with the processor in the hub cell 177 . For example it enables a processor 92 in a border cell to send an interrupt to alert the hub cell when the border cell has a new data packet to be copied to another border cell, rather than waiting for a processor 92 in the hub cell 177 to poll the memory controller 96 in the border cell. Furthermore, if the interrupt does not require a response to be sent from hub cell 177 to the cell transmitting the interrupt, then a cell in another partition may transmit an interrupt to hub cell 177 after placing data to be copied into the partition's border cell's memory. Defining the processor coherency domain and the memory controller coherency domain of a cell identically also simplifies communications routing, because messages do not have to be routed differently depending on which resource in a cell they originate from.

As shown in FIG. 2 , the computer system 190 has one hub coherency domain with 8 cells and 7 spoke coherency domains, each with 7 cells. As explained above, the border cells 100 . . . 166 have their own processor and memory controller coherency domains, which in the interests of simplicity are not marked in FIG. 2 . The system 190 has one hub partition P 17 with a single cell, and 7 spoke partitions each with 7 cells. It will be seen that the number of spoke partitions P 110 . . . P 16 may be more or less, and is limited to one less than the number of cells in hub coherency domain C 17 . If levels of inter-spoke traffic are large, there may be more than one hub cell 177 , although in that case the number of spokes will be correspondingly reduced. Each of the border cells 100 , . . . 166 must allow both reads by and writes from the hub cell 177 of data for and from other spoke partitions. Consequently, security in these cells may be limited. In this embodiment, there is at least one hub cell 177 that belongs to partition P 17 and does not belong to any coherency domain except C 17 . This cell can contain the core functionality of partition P 17 in an environment that is strongly protected from external disturbance. Hub cell 177 may be configured so that data being transferred from one border cell 100 . . . 166 to another is strictly segregated, in order to reduce the risk of the entire hub partition being disrupted by a rogue spoke partition.

If the address space format, as compared to the size of a cell, permits, the number of cells in a coherency domain may be greater than the 8 cells shown in FIG. 2 . However large the coherency domain is, with the configuration shown in FIG. 2 the maximum number of cells in a spoke partition P 10 . . . P 16 is one less than the maximum number of cells in a coherency domain. The maximum number of spoke partitions P 10 . . . P 16 is one less than the number of cells in the hub coherency domain C 17 . Consequently, the maximum total system size is (N−1)(N−1)+1 cells, where N is the maximum number of cells in a coherency domain. That is 50 cells if N=8, or 226 cells if N=16, or 3970 cells if N=64.

However, within that maximum size, data can be transferred from any partition to any other partition with a maximum of three copy operations, or two if the border cells are permitted to copy to and from memory in the hub cell 177 . The maximum latency involved in fetching data from another partition is therefore both smaller and more predictable than in the embodiment shown in FIG. 1 .

Referring now to FIG. 3 , a third form of computer system according to an embodiment of the invention, indicated generally by the reference numeral 290 , has a plurality of cells 200 . . . 27 F, which are internally similar to the cell 00 shown in FIG. 1 , each including, among other things, a processor 92 , memory 94 , and a memory controller 96 . In this embodiment, each cell may be identical, and each cell is capable of addressing a coherency domain C 20 . . . C 27 of addresses. In this embodiment, the processor and memory controller coherency domains may be identical. In this embodiment, the cell is identified in addresses by the most significant bits of the address, corresponding to the right-hand digit of the cell number in FIG. 3 . Memory accesses within a coherency domain can be fast, because the originating cell or processor can specify directly the address of the memory to be accessed, eliminating the latency that would be caused by interpreting an indirect address.

Each cell also belongs to a partition P 20 . . . P 27 , identified by the second digit of the cell number in FIG. 3 . In this embodiment, the processors 92 within a partition can freely read data from and write data to any memory within the same partition. Restrictions may be imposed on reading data from, and stricter restrictions may be imposed on writing data to, memory within another partition, even if the memory is within the coherency domain of the processor that originates the read or write.

In this embodiment, partition P 20 contains cells 200 , 201 , 202 , 203 , 204 , 205 , 206 , 207 , 208 . The cells in partition P 20 belong to coherency domain C 20 . Partition P 21 contains cells 210 , 211 , 212 , 213 , 214 , 215 , 216 , 217 , 219 . The cells in partition P 1 belong to coherency domain C 1 . Partition P 22 contains cells 220 , 221 , 222 , 223 , 224 , 225 , 226 , 227 , 22 A. The cells in partition P 22 belong to coherency domain C 22 . Partition P 23 contains cells 230 , 231 , 232 , 233 , 234 , 235 , 236 , 237 , 23 B. The cells in partition P 23 belong to coherency domain C 23 . Partition P 24 contains cells 240 , 241 , 242 , 243 , 244 , 245 , 246 , 247 , 24 C. The cells in partition P 24 belong to coherency domain C 24 . Partition P 25 contains cells 250 , 251 , 252 , 253 , 254 , 255 , 256 , 257 , 25 D. The cells in partition P 25 belong to coherency domain C 25 . Partition P 26 contains cells 260 , 261 , 262 , 263 , 264 , 265 , 266 , 267 , 26 E. The cells in partition P 26 belong to coherency domain C 26 . Partition P 27 contains cells 270 , 271 , 272 , 273 , 274 , 275 , 276 , 277 , 27 F. The cells in partition P 27 belong to coherency domain C 27 . Within each partition, the last digit of the cell number corresponds to the cell address. It will be seen that these addresses are unique only within the partition.

Each of the cells 208 , 219 , 22 A, 23 B, 24 C, 25 D, 26 E, 27 F, forming abridge 292 between the partitions, has a globally unique address. A processor 92 in those bridge cells can address either another cell in the bridge 292 or a cell in its own partition unambiguously within the address scheme of its own coherency domain C 20 . . . C 27 . In this embodiment, the globally unique cells in the bridge 292 are in the address space of every coherency domain. However, cells that are not in the bridge 292 are not permitted to address cells in other partitions, even if those cells are in the bridge. This avoids the situation where, for example, cell 222 could use globally unique cell address 9 to address cell 219 , but cell 219 might then misidentify address 2 , which is only locally unique, as meaning its own cell 212 , rather than cell 222 . This restriction eliminates the need to resolve ambiguities in locally, but not globally, unique addresses. In effect, therefore, a bridge cell has a coherency domain that includes the bridge plus the coherency domain of the cell's own partition. The other cells in the partition have a coherency domain that is a subset of the bridge cell's coherency domain.

In this embodiment shown in FIG. 3 , data can be transferred between any two cells with only two transfer operations. For example, if data is to be transferred from cell 200 to cell 270 , the data could be copied from cell 200 to bridge cell 208 by a processor in partition P 20 . Because cell 208 is in the bridge, it can be addressed by a processor in cell 27 F, which can then copy the data directly to cell 270 .

Alternatively, the data could be copied from cell 200 to bridge cell 27 F by a processor in bridge cell 208 . From cell 27 F, the data can be accessed directly by a processor in the destination cell 270 . However, for security, cells may be permitted to read from, but not to write to, cells in other partitions. In particular, bridge cells 208 . . . 27 F are then permitted only to read from, and not to write to, each other. In that case, the transfer from cell 208 to cell 27 F must be a read by cell 27 F, not a write by cell 208 , so this alternative transfer procedure would not be allowed. Conversely, a transfer from source cell 270 to destination cell 200 would require the data to be copied from cell 270 to bridge cell 27 F by any processor in partition P 27 , and then copied to cell 200 by a processor in bridge cell 208 .

In this embodiment the maximum number of cells is p*b, where p is the number of cells in a partition, b is the number of partitions sharing the bridge 292 , and p+b−1≦N, where N is the maximum number of cells in an address space. The maximum is then usually (N/2+1)(N/2) cells. That is 20 cells if N=8, 72 cells if N=16, and 1056 cells if N=64. Having (N/2+1) cells in each of (N/2) partitions, rather than (N/2) cells in each of (N/2+1) partitions, will usually reduce the amount of traffic between partitions.

Although the invention has been described and illustrated with reference to exemplary embodiments thereof, it will be understood by those skilled in the art that various changes, omissions, and additions may be made thereto, without departing from the spirit and scope of the invention as recited in the attached claims. For example, the first two embodiments have been described with an address space containing 8 cells, and the third embodiment has been described with an address space containing 16 cells. The sizes of the address spaces may be larger or smaller, depending on the capabilities of the particular processors and fabrics used, and on the requirements of a particular system.

For simplicity, the embodiments have been described with a single chain, bridge, or hub to connect different coherency domains. However, the invention is not limited to such embodiments. For example, a cell in FIG. 2 or 3 that is shown as not forming part of the bridge or hub could form part of another bridge or hub linking to other partitions, or could be at the beginning of a chain. A suitably constructed network of bridges, hubs, and chains may allow a system of cells too large for the size limits in the bridge and hub systems, without the latency problem that a very long chain would cause.

Although in the interests of linguistic simplicity the embodiments shown in the drawings have been largely described as having one processor and one memory controller in each cell, there may be more than one processor 92 and/or more than one memory controller 96 in each cell. Although in the interests of linguistic simplicity in the embodiments shown in the drawings the cells are described as being the same, a single computer system may have cells that are not all the same. A single computer system may have processors and/or memory controllers that do not all have the same size of address space, and a single system may include coherency domains that are not all of the same size.