Multiplex communications – Communication techniques for information carried in plural... – Transmission bandwidth conservation
Reexamination Certificate
1998-03-19
2001-09-04
Cangialosi, Salvatore (Department: 2732)
Multiplex communications
Communication techniques for information carried in plural...
Transmission bandwidth conservation
Reexamination Certificate
active
06285686
ABSTRACT:
BACKGROUND OF THE INVENTION
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.
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.
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.
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.
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.
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.
SUMMARY OF THE INVENTION
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.
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.
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.
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.
It is a further technical advantage of the invention to store repeated address bit patterns in the page registers.
It is a further technical advantage of the invention to change the stored patterns over time.
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.
REFERENCES:
patent: 5020058 (1991-05-01), Holden et al.
patent: 5146456 (1992-09-01), Berkovich
patent: 5317604 (1994-05-01), Osterweil
patent: 5440562 (1995-08-01), Cutler, Jr.
patent: 5691986 (1997-11-01), Pearlstein
patent: 5831872 (1998-11-01), Pan et al.
patent: 5886995 (1999-05-01), Arsenault et al.
patent: 6038231 (2000-03-01), Dolby et al.
Cangialosi Salvatore
Hewlett--Packard Company
LandOfFree
Using page registers for efficient communication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using page registers for efficient communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using page registers for efficient communication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441628