Using page registers for efficient communication

[0002] In an interconnected computer network, the devices communicate through transactions. A transaction comprises one or more packets and conveys some meaningful information. For example, a CPU in a multiprocessor network may respond to a snoop request with a “snoop response” transaction. Generally, a packet consists of a fixed number of transfers or cycles in the interconnect structure. Different transactions may require different number of packets. A transaction may comprise one or more packets forming the header, followed by zero or more packets forming the accompanying data. The header packet(s) may comprise information such as the source node identifier, the destination node identifier, the address bits, the transaction identifier, length of the transaction, flow-control information. Note that different terms are sometimes used but have the same meaning, for example, it is common to use the terms address cycle and data cycle for the header packet and the data packet, respectively.

[0003] The raw bandwidth of an interconnect structure is determined by the number of wires and the frequency at which data is transferred. For example, the raw bandwidth available in a 39-bit wide bus, operating at 100 MHz, is 3900 Mbits/sec. The usable bandwidth would be less due to ECC and header packet overheads. The usable bandwidth will depend on the efficiency of the underlying protocol.

[0004] The prior art approach to improving the bandwidth relies on expanding the interconnect width and/or increasing the frequency of operation. This approach yields better bandwidth via wider interconnect andp/or faster data transfer. Thus, the improvement in usable bandwidth is solely due to the improvement in the raw bandwidth. The ratio of the usable bandwidth to the raw bandwidth remains unchanged. However, increasing the raw bandwidth is expensive in terms of manufacturing costs. Moreover, the increase in raw bandwidth may lead to electrical problems in the system interconnect interface. Note that technological limitations will restrict the amount with which the raw bandwidth can be increased.

[0005] Encoding schemes such as Hoffman encoding may be able to achieve more bandwidth by encoding the most frequently occurring patterns with less number of bits. However, Hoffman encoding require that these bit patterns be known before their actual use, so that the most used bit patterns are assigned the smallest number of bits. For example, assume that a system uses 4 bits in a pattern, and 1111 is the most common pattern. Using Hoffman coding, this pattern will be assigned 0. The next most common pattern will be assigned 10, the next will be assigned 110, then 1110, etc. Thus, Hoffman coding uses variable lengths of bit patterns to indicate the same width of data transfer. Note that some bit patterns are represented by a single bit and others, particularly, the least used patterns will be represented by more than 4 bits.

[0006] In typical systems, it is not possible to identify patterns that are more likely to occur than others, because computer systems exhibit a locality of reference that changes over time with regards to addresses and data patterns. Thus, in a computer system one may not be able to predict which addresses are more likely to be accessed than others, since this depends on the application, and space the address patterns change as the program executes. In other words, if a particular page or address is accessed, then most likely a nearby address will be accessed next. Hoffman codes are static and cannot change over time. Moreover, Hoffman encoding requires more bits for the patterns that are “less likely”, as a result one may end up in degraded performance.

[0007] Therefore, there is a need in the art for a mechanism which will improve the ratio of usable bandwidth to the raw bandwidth and thereby increase the bandwidth without having to increase the frequency or the number of wires.

[0008] These and other objects, features and technical advantages are achieved by a system and method which increases the usable data bandwidth by improving the efficiency of the protocol through the use of page registers as pointers. The inventive mechanism tracks bit patterns that could potentially repeat in page registers. If a bit pattern exists in a page register, then the page register number is sent to the receiver instead of the bit pattern. This conveys the same amount of information with less number of bits and hence improves the usable bandwidth.

[0009] In particular, the higher order address bits tend to repeat in sequential transactions, since computer programs exhibit locality of reference. Thus, by storing the higher order address bits in page registers, a pointer is sent to the destination node, which instructs it to look up the higher order bits in its page register, rather than send all the address bits. The inventive mechanism enhances the performance by providing the flexibility of choosing ‘on-the-fly’ which bit patterns are likely to repeat and overwriting older patterns as time progresses. Note that the inventive mechanism does not degrade the performance for bit patterns that do not repeat. Further note that the inventive mechanism is not limited only to address bits, but can be used for any other fields that repeat. The invention is useful in systems where there is a notion of a start and end of a transfer.

[0010] It is a technical advantage of the invention to increase the useable bandwidth of a computer network system without having to increase with raw bandwidth.

[0011] It is another technical advantage of the invention to store the repeated bit patterns in page registers, which allows a smaller sized reference to the register to be sent to the destination node instead of the larger sized bit pattern.

[0012] It is a further technical advantage of the invention to store repeated address bit patterns in the page registers.

[0013] It is a further technical advantage of the invention to change the stored patterns over time.

[0014] The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.

[0015] For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

[0016] FIG. 1 depicts a network system having two nodes interconnected by a bus;

[0017] FIGS. 2A and 2B depict a flow diagram of the inventive mechanism resident in a sending node; and

[0018] FIG. 3 depicts a flow diagram of the inventive mechanism resident in a receiving node.

[0019] FIG. 1 depicts a simple network system 10, having two nodes, node A11 and node B12 connected by bus 13. For purposes of discussion assume that the bus C13 is 39 bits wide, with a frequency of approximately 100 MHz. Thus, the overall bandwidth of system 10 is 3900 Mbits/sec. Also assuming that ECC is used, such that out of the 39 bits, 32 bits are information, and 7 bits are ECC check bits that form a (39, 32) single error correcting, double error detecting (SEC-DED) ECC code. The address bits are assumed to be 32 bits wide, broken into 16 upper address bits and 16 lower address bits. The system 10 uses a packet type of communications, however other communication types may be used.

[0020] Table 1 shows an example of the contents of the header packets for a transaction, which is being sent from node A11 to node B12 via bus C13. The transaction requires 2 cycles, or 2 packets, to send all of the necessary header information. The data will follow in zero or more data packets. Other types of transactions may require different number of cycles. The header packet as well as its contents are shown by way of example only.

[0021] The first packet of Table 1, comprises 3 bits to identify the source node of the packet, 3 bits to identify the destination node of the packet, 4 bits to identify the particular transaction, and 16 upper address bits. The 6 remaining bits of the 32 available bits are insufficient to carry the lower 16 address bit. Thus, the 16 lower address bits are sent in the second packet. Therefore, the transaction will require two packets or two cycles to send the header information. If this requirement were to be cut to one packet or one cycle, then the effective bandwidth will be increased as more cycles will be available to carry data packets.

[0022] Note that a subsequent header packet is likely to have a similar address, particularly a similar upper address, since nodes tend to exhibit locality of reference as far as their accesses are concerned. Thus, the inventive mechanism uses page registers that store the bit patterns that are likely to repeat. To accomplish this, the definition of the header packet includes the format information as well as the page register information. The sender node and the receiver node have a fixed number of page registers to store the bits in the fixed bit positions that have the potential of repetition. A sender would review its page registers to determine if the bit pattern which it is about to send is already present. If it exists, than it sends the page register number (where it found the matching bit pattern) along with the proper format without sending the bit pattern. The resultant reduction in header length increases the usable bandwidth. If the entry does not exist in the page registers, and the bit pattern is likely to repeat in the fixed bit positions, the sender may store the bits in a particular page register and send the header with all the bits, but with a format that tells the receiver to store the repeated bits in a page register of the same number where the sender stored the bits. Subsequent transactions with the same bit patterns will benefit from the page register usage.

[0023] Table 2 depicts the header packets for the same transaction as shown in Table 1, but includes format and page register number bits in place of the spare bits. The format bits inform the destination or receiving node as to the type of packet, i.e. whether there are two header packets as shown in Table 2, or whether there is only one header packet as shown in Table 3. The two format bits allow for a total of four formats. For example, 00 indicates that the header is 2 packets long or full length, and instructs the destination node not to store the upper address bits in any page register, as it is not anticipated to be repeated. A format of 01 implies that the current packet is part of two packet header, but the higher address bits need to be stored in the page register indicated by the page register number bits, as it is anticipated to be repeated. Thus, subsequent transactions may send a lesser number of header packets if the higher address bits match. Format 11 indicates that the sender is only one header packet, as shown in Table 3, which does not include the upper address bits. Thus, the receiving node will retrieve the upper 16 address bits by looking up the page register indicated by the sending node in the packet. The actual format bits are by way of example only, as a different format arrangement could be used, for example 11 may indicate that the header is 2 packets long or full length, and the destination node should not store the upper address in any page register. More bits are required if more than four formats are to be used. Note that the sending node commands the receiving node. The sending node determines what steps the receiving node should take, e.g. whether to store the upper address bits, and instructs the receiving node with the format bits.

[0024] The page register number bits identify the particular register which is to be accessed by the receiving node. The four bits allow for a total of 16 page registers to be involved with the sender node and the receiving node. Thus, node A11 (as well as node B12) would have 16 page registers in its sending interface for node B12. To reciprocate, node B12 should have 16 page registers in the receiving interface for node A11. It should be noted that a node may have more than one set of page registers in its sending interface either for one or multiple destination nodes. Since there are 16 upper address bits, each register would be 16 bits wide. Note that if the address is a different size, then the register would also be of the same width. Additional sets of registers would be required for connection with different nodes. For example, an additional set of 16 registers may be required in the sending interface of node A11 for an additional connection between node A11 and node Q (not shown).

[0025] For example, suppose an address is being sent from the sending node with the upper order address bits 0x01A1 (in hex) and lower order address bits 0x1BC1. Before the sending node A11 sends the packet to node B12, the sending node reviews its own page registers to determine if the upper order address bits have already been sent. Assuming these bits do not exist in the page registers, the sending node then decides whether the upper address bits are likely to repeat based on some internal hints. If it decides that this address is a likely pattern, it selects a page register to store the address bits, based on an internal page register replacement mechanism. Suppose register 7 is selected, then sending node sends the two packet header of Table 1 with the format set to 01 and page register number=7. The receiving node B12 on receipt of this packet, stores 0x01A1 in its own page register number 7, as indicated by the format 01 and the page register number 7 that it received in the first packet of the header. Suppose a subsequent transaction from node A11 to node B12 is to address 0x01A1_—11BC, then the upper order address bits will be found in page register 7 by the sending node. Thus, the sending node can send the header in the one packet format shown in Table 3 with format=11 and page register number=7. The receiving node B12 will then look up page register number 7 and obtain the upper address bits as 0x01A1. Thus, the bandwidth required to send the second packet is saved in this transaction.

[0026] The sending node decides which addresses to save based upon hints in the usage of the address. For example, assume the sending node is an I/O chip, and is moving an entire page out of memory, which will require multiple transactions. Thus, the I/O chip will know that a similar memory location will be sequentially accessed, particularly the upper address bits. The I/O chip will send a hint bit to the page register logic to save the current address, and instruct the receiving node to do likewise via the format bits. Alternatively, each address could be stored in a register, and older addresses would be bumped out by newer addresses. Other mechanisms for managing the page registers could be used.

[0027] FIGS. 2A and 2B depict the portion of the inventive mechanism resident in the sending node. The sending node first gathers all the information that needs to be sent 21. This information comprises the addresses, flow control information, transaction type, data, etc. Then the sending node determines whether the address pattern is a repeat pattern that is already stored in the page registers 22. The sending node compares the current upper address bits with those stored in the registers. If it finds a match, then the sending node sends a reduced header packet as shown in Table 3 with the appropriate page number and format number 23. Note that the savings in bit patterns need not be restricted to address bits only—one may choose some other field also. One may also choose multiple fields which will involve multiple format fields, multiple page register sets and multiple page number fields; one corresponding to each field that is being optimized. The packet will be sent to the receiving node, processed through ECC, and appropriately handled by node B.

[0028] If the sending node does not find a match between the current upper address bits and those stored within its page registers, then the sending node decides whether the bit pattern is likely to be repeated 24. If the pattern is not likely to be repeated, then the sending node will send a full 2 packet header as shown in Table 2 to the receiving node, that also instructs the receiving node not to save the address bits 25. If the pattern is likely to be repeated, then the sending node determines whether there is space in the page registers for the pattern 26. If space is available, then the sending node adds the pattern to its page registers 27, and sends a full 2 packet header as shown in Table 2 to the receiving node which instructs the receiving node to save the address bits 28 in the specified page register. If space is not available, then a replacement algorithm such as the least recently used scheme may be employed to make room in the page registers for the new address entry 29, before adding the pattern to the registers 27.

[0029] FIG. 3 depicts the portion of the inventive mechanism resident in the receiving node. The receiving node receives a new transaction packet from the sending node 31. The receiving node then determines the format of the packet from the format bits 32, i.e. a reduced packet or a long packet. If the packet is a reduced packet, then the receiving node retrieves the upper address portion from its own page registers, as indicated by the page number bits in the packet 33. The receiving node then constructs the complete address from the data in packet and the page register, and processes the transaction in the appropriate manner 34.

[0030] If the packet is a long packet, then the receiving node determines whether the upper address portion must be saved in its page registers, as indicated by the format bits in the packet. If it does not have to save the address, then the receiving node passes on the packet for appropriate processing 36. If the receiving node is instructed to save the address bits, then the receiving node updates the specified page register with the new address 37 before processing the packet 36.

[0031] Note that the page registers can be used to store other types of patterns other than upper address bits. They can store data patterns, patterns in a single packet fields, patterns in multiple fields, or full address patterns. Note that the bit positions in the packets do not have to be fixed bit positions, multiple sets of bit positions could be used independently and simultaneously by having multiple sets of page registers.

[0032] Further note that separate page registers must exist between every pair of sender and receiver nodes. However, every pair of nodes in the system do not have to use the inventive mechanism, and thus those nodes do not need registers. Note that the inventive mechanism will operate on systems that are not bus based. Any interconnect structure will work, so long as packets will arrive in the order in which they were sent or belong to classes of packets which will arrive in the order in which they were sent. Further, the selected bits need not be clubbed together, as shown in the tables. Different sets of selected bits can be stored independently in their own sets of page registers. In this case, each set of selected bits will need format and page register fields.

[0033] Note that instead of sending the lower address bits in the reduced packet, a bit sequence can be sent indicating a difference from the stored address value. Thus, a + or − value is sent which would be applied to the stored address to determine the new address. However, for this embodiment, the entire address must be stored, instead of just the upper address portion.

[0034] Therefore, the inventive mechanism improves the effective bandwidth between communicating nodes by sending fewer number of header address bits and using the page registers. The inventive mechanism improves the bandwidth without having to increase the frequency and/or the width of the interconnect media.

[0035] Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.