Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-04-24
2001-07-31
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C710S116000, C710S063000, C710S112000, C710S113000
Reexamination Certificate
active
06269360
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data transfers within data processing systems and in particular to ordered data stores on a pipelined bus within a data processing system. Still more particularly, the present invention relates to optimization of ordered stores on a pipelined bus within a data processing system to improve system performance.
2. Description of the Related Art
Integrated circuits which transfer data within data processing systems, particularly processors, are required to adhere to certain requirements for such data transfers. One possible requirement is ordering, where data transfer transactions must be completed on a system bus in the order that an execution unit generated the transactions. An ordering requirement between multiple data transfer transactions may occur, for example, in the context of multiple stores to the same address.
Other reasons exist for ordering requirements besides matching addresses for multiple stores. Typical processor architectures associate attributes with certain address ranges, such as the WIMG bits associated with page table entries within the PowerPC™ architecture. These attributes may specify the ordering of transactions to addresses within the associated address range. Moreover, depending on the type of memory model implemented, a processor architecture may support instructions which dictate specific transaction ordering, such as the EIEIO, SYNC, and TLBSYNC instructions within the PowerPC™ family of processors. These and other processor features may impose ordering requirements on data transfer transactions within a data processing systems.
Contemporary high performance processors typically utilize a high frequency, pipelined bus interface. The pipelined nature allows multiple transactions to be active on the bus simultaneously. In general, a bus transaction may be broken down into the following segments:
arbitration for the bus;
presentation of the address and transaction type on the bus (to be decoded for slave selection and snooped for memory coherency);
response by slaves and snooping masters to the transaction address, which may be an acknowledge (Ack) that the transfer may proceed as requested or a retry (Retry) which aborts the transaction and causes it to be initiated again later starting with arbitration; and
transfer of data, which may occur before or after the address response, or not at all for address-only transactions.
A data transfer transaction is complete after the later of the last datum being presented and accepted or receiving a satisfactory address response.
To enforce strict ordering between data transfers, current processors completely serialize the transactions. Any pending transfer subject to an ordering requirement with a previous transfer is delayed from the beginning (bus arbitration) if the previous transfer is not complete or at least guaranteed to complete in the present bus tenure (i.e., the transfer has past the point where the bus protocol permits retry of the transfer).
FIGS. 4A and 4B
are bus timing diagrams showing the general serialization of two ordered transfers.
FIG. 4A
is a timing diagram for non-retried transfers, while
FIG. 4B
is a timing diagram for the same operation when the first transfer receives an address response indicating a retry. In both figures, the address response is valid three clock cycles after the address is valid on the bus. In both cases, the bus request for data transfer B is not initiated until an acknowledge response is received for data transfer A. This requires a latency of at least six clock cycles for the best case or twelve clock cycles if a retry is asserted before data transfer B may be initiated. As shown in the figures, the total latency—from start of the first transaction to completion of the second—is twelve clock cycles with no retry response and eighteen clock cycles if a retry response of the first transaction is asserted.
In the example depicted, an address response three clock cycles after the address is valid is the only mechanism for retrying a data transfer. Some bus protocols may support multiple windows for responses—one for slave responses and one for snoop responses—with a much higher latency between the address and the final response. The higher the latency, the longer the delay before starting a succeeding, ordered transfer and the lower the overall performance for serialized data transfers.
It would be desirable, therefore, to provide a mechanism for reducing the latency of ordered transactions on a pipelined bus within a data processing system. It would further be advantageous for the mechanism to take full advantage of the pipelined nature of the bus while preserving the ordering requirement.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved method and apparatus for data transfers within data processing systems.
It is another object of the present invention to provide an improved method and apparatus for ordered data stores on a pipelined bus within a data processing system.
It is yet another object of the present invention to provide a method and apparatus for optimization of ordered stores on a pipelined bus within a data processing system to improve system performance.
The foregoing objects are achieved as is now described. Where a plurality of ordered transactions are received for data transfers on a pipelined bus, each transaction in the series is initiated before all prospective retry responses to the preceding ordered transactions may be asserted. The address responses to all preceding ordered transfers are then monitored in connection with performance of the newly initiated transfer. If a retry response to any preceding ordered transaction is asserted, a self-initiated retry response for all subsequent transactions, including the newly initiated transfer, is also asserted. The system-retried transactions and all succeeding, ordered transactions are immediately reattempted. The overlapping performance of the ordered transfers reduces the latency of non-retried transfers, achieving performance comparable to non-ordered transactions. Even where a retry response is asserted, the total latency required for completion of both transactions in the ordered pair is reduced by at least a portion of the address-to-response latency, so that the impact of ordering requirements on system performance is minimized. Strict ordering is thus enforced while taking full advantage of the pipelined nature of the bus to maximize utilization of the bus bandwidth.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 3688274 (1972-08-01), Cormier et al.
patent: 4044337 (1977-08-01), Hicks et al.
patent: 5185871 (1993-02-01), Frey et al.
patent: 5293621 (1994-03-01), White et al.
patent: 5319766 (1994-06-01), Thaller et al.
patent: 5388224 (1995-02-01), Maskas
patent: 5535345 (1996-07-01), Fisch et al.
patent: 5555382 (1996-09-01), Thaller et al.
patent: 5592631 (1997-01-01), Kelly et al.
patent: 5623628 (1997-04-01), Brayton et al.
patent: 5629950 (1997-05-01), Godiwala et al.
patent: 5796977 (1998-08-01), Saranghar et al.
patent: 5797026 (1998-08-01), Rhodehamel et al.
patent: 5987549 (1999-11-01), Hagersten et al.
Hardage, Jr. James Nolan
Petersen Thomas Albert
Black Thomas
Bracewell & Patterson L.L.P.
England Anthony V. S.
International Business Machines - Corporation
Mizrahi Diane D.
LandOfFree
Optimization of ordered stores on a pipelined bus via... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of ordered stores on a pipelined bus via..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of ordered stores on a pipelined bus via... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2535809