Method and apparatus for generating timeouts to a system based counting intervals supplied by a shared counting device

[0002] The present invention relates generally to computer systems. More particularly, the invention relates to a mechanism for reducing timeout uncertainty associated with pending transactions.

[0003] It is common for devices coupled in a computer system to communicate by exchanging transactions or requests. For example, an I/O device can initiate a transaction requesting data from a host I/O bridge. The host I/O bridge, in turn, can initiate a DMA transaction requesting the data from main memory. While the host I/O bridge is waiting for the requested data, the host I/O bridge can perform other tasks including initiating other DMA transactions. In order to prevent the host I/O bridge from waiting indefinitely for the requested data, a timeout mechanism is often used to indicate that an error has occurred when a response is not received within the timeout period. The host I/O bridge then handles the error according to the type of timeout.

[0004] One such timeout mechanism is a timeout counter. A timeout counter tracks the number of timeout periods that have lapsed since the transaction was initiated. The timeout counter consists of a number of bits, n, and can track 2ⁿtimeout periods. When the timeout counter reaches a predetermined threshold, an interrupt is set indicating that a timeout has occurred.

[0005] The number and length of the timeout periods is usually set based on the maximum expected response time for the transaction. In some applications, it is necessary for the timeout counter to indicate with reasonably accuracy the time at which the timeout occurs. However, this requirement is not always feasible.

[0006] In some applications, a single timeout counter is used to accommodate multiple transactions. Although this technique utilizes less circuitry, it does not accurately track the time at which the timeout occurs. The transactions are queued and the timeout starts once the transaction gets to the head of the queue. The time that the transaction waits in the queue is not tracked which affects the accuracy of the timeout.

[0007] In yet other applications, there is a timeout counter for each transaction. Although this produces a more accurate result, it has the drawback of requiring a considerable amount of circuitry. For example, for an application having 128 possible outstanding transactions where each timeout counter has 20 bits, there would have to be 2560 bits of counters. At times, this amount of circuitry is not feasible. Accordingly, there is a need to overcome these shortcomings.

[0008] In summary, the technology of the present invention pertains to a timeout mechanism that attempts to accurately track the time a timeout occurs while preserving the amount of circuitry and processing required to maintain this accuracy. In an embodiment of the present invention, the timeout mechanism is used to track requests for cache lines that are requested from an I/O bridge in a multiprocessor system.

[0009] The timeout mechanism includes a timeout control unit having a fetch state machine for each cache line entry. Each fetch state machine ensures that the outstanding fetch transaction for the associated cache line times out after a prescribed number of timeout periods have lapsed. Preferably, there are six timeout periods. The timeout periods are set at a relatively small interval so that when the timeout occurs, the timeout will have occurred within a smaller time frame which produces a more accurate result. If the fetch transaction times out, an error control unit is notified which handles the timeout appropriately.

[0010] Such accuracy is important in a system, such as the computer system described herein, which has a hierarchy of timeouts. The lowest priority timeouts have a shorter timeout period with the higher priority timeouts having a longer timeout period. Each succeeding level in the hierarchy has a longer timeout period than a preceeding priority level. The priority level scheme is set so that the lower priority devices shut down before the higher priority devices in the event of a system failure. If a lower priority component's timeouts are longer than expected, it can affect the shutdown order.

[0011] For a better understanding of the nature and objects of the invention, reference should be made to the following detailed description taken in conjunction with the accompanying drawings, in which:

[0012] FIG. 1 is a schematic view of an exemplary computer system in accordance with an embodiment of the present invention;

[0013] FIG. 2 is a block diagram illustrating the second level I/O bridge shown in FIG. 1;

[0014] FIG. 3 is a block diagram illustrating the timeout control unit shown in FIG. 2; and

[0015] FIG. 4 is a block diagram illustrating the steps used by the fetch state machines in accordance with an embodiment of the present invention.

[0016] Like reference numerals refer to corresponding parts throughout the several views of the drawings.

[0017] FIG. 1 illustrates an exemplary computer system 100 embodying the technology of the present invention. There is shown a number of cells 102 connected through an interconnect 104. Each cell 102 can include a number of processors (e.g., P₀-P_n) 106 connected to a memory controller unit 108 by a first communication link 110, such as a bus. The memory controller unit 108 is also connected to a memory bank 112 and an I/O subsystem 114.

[0018] The processors 106 can be any type of processor or central processing unit (“CPU”), such as but not limited to, microprocessors and the like. Examples of such microprocessors include the Hewlett-Packard (“HP”) PA-RISC family of microprocessors, the Intel IA-32 and IA-64 microprocessors, and the like. Each processor 106 has several levels of internal caches (not shown) that store a portion of the system memory that can be accessible by other processors 106 in the cell 102 and by other cells 102.

[0019] The memory controller unit 108 controls access to the system memory. The memory banks 112 can be composed of any type of memory device or combination thereof, such as DRAM, SRAM, RAM, flash memory, and the like.

[0020] Each cell 102 includes a portion of the system memory image and the requisite components that maintain the system memory in a coherent manner. The system memory image of the multiprocessor computer system 100 is distributed throughout each cell 102 and can be partitioned to be accessible within each cell 102 and by other cells 102. For example, the system memory can include interleaved memory which is memory that is interleaved across cells 102 or non-interleaved memory which is memory that is accessible within a cell 102.

[0021] A directory-based coherency protocol is used to maintain the system memory in a coherent manner. In the directory-based coherency protocol, each memory line has an associated tag that includes state information identifying the owner or sharers of that memory line. The state information provides a means to coherently track the memory lines shared within the multiprocessor system 100.

[0022] The interconnect 104 can be any type of high-speed communication link, such as but not limited to, a network, point-to-point link, crossbar switch, or the like. Preferably, a crossbar switch is used.

[0023] The I/O subsystem 114 can include a second-level I/O bridge 116, a number of first-level I/O bridges 118, and several I/O devices 120. The I/O devices 120 are connected to a first-level I/O bridge 118 through a bus 122, such as the Peripheral Component Interface (“PCI”) bus. The I/O devices 120 include devices such as but not limited to host bus adapters, bus bridges, graphics adapter, printers, audio peripherals, motion video peripherals, and the like.

[0024] The first-level bridge 118 is connected through a second communications link 124 to the second-level I/O bridge 116. The second-level I/O bridge 116 is coupled to the memory controller unit 108 through a high-speed interconnect 126. The first-level 118 and second-level I/O bridges 116 serve to connect multiple PCI buses 120 operating at a slower clock rate with the high-speed interconnect 126 in a manner that reduces the pinout of the bridges 116, 118.

[0025] The foregoing description has described an exemplary computer system 100 embodying the technology of the present invention. Attention now turns to a more detailed discussion of the second-level I/O bridge 116.

[0026] FIG. 2 illustrates the components of the second-level I/O bridge 116. There is shown a link interface 130 and a number of control units 132 connected through a communications link 134. The link interface 130 enables the second-level I/O bridge 116 to communicate through the high-speed interconnect 126. Each control unit 132 processes transactions received from the I/O devices 120 connected to the respective first-level I/O bridges 118 supported by the control unit 132.

[0027] Each control unit 132 includes a cache having a cache data unit 136 and a cache tag unit 138. Each entry into the cache data unit 136 stores a cache line of data that is preferably 64-bytes wide. Preferably, there are 64 cache line entries. Each tag line entry in the cache tag unit 138 is associated with a particular cache line and stores tag data including state information. In addition, there is a cache controller unit 140 that manages the cache. The cache controller unit 140 handles DMA read and write requests, prefetches cache lines, processes software flush requests, and the like.

[0028] A fetch FIFO unit 142 is provided to fetch cache lines from the main memory which are then stored in the cache data unit 136 and to flush data from the cache data unit 136. The fetch FIFO unit 142 coordinates this activity with the cache controller unit 140 and the timeout control unit 144. The fetch FIFO unit 142 uses a cache entry address (“CEA”) 148 and a load signal 146 to fetch a cache line (see FIG. 3). When the cache line is returned, a response signal 150 and the CEA 148 is returned to the fetch FIFO unit 142 as well.

[0029] Referring to FIG. 3, the timeout control unit 144 is provided to ensure that transactions requesting a cache line do not wait indefinitely. In brief, the timeout control unit 144 has a fetch state machine 152 for each cache line entry. Each fetch state machine 152 ensures that the outstanding fetch transaction for the associated cache line times out after a prescribed number of timeout periods have lapsed. If the fetch transaction times out, an error control unit 154 is notified which handles the timeout appropriately. Attention now turns to a more detailed description of the timeout control unit 144.

[0030] As shown in FIG. 3, there is shown sixty-four fetch state machines (“SM”) 152, each of which is associated with a particular cache line entry. For example, fetch state machine 3 is associated with cache line entry 3. A first decoder 156 is coupled to each of the fetch state machines 152 and is used to indicate which cache line is being fetched. The first decoder 156 receives the load 146 and CEA 148 signals that are used by the fetch FIFO unit 142 when it fetches a particular cache line from main memory. The first decoder 156 sets one of the sixty-four output signals, set_fip[0 . . . 63], based on the load 146 and CEA 148 signals. The set_fip signal 158 that is set by the first decoder indicates the particular cache line that has a fetch in progress. The set_fip signal 158 that is set is transmitted to its respective fetch state machine 152 where it is used to initiate the timeout process.

[0031] A second decoder 158 is also coupled to each of the fetch state machines 152. The second decoder 158 receives the response 150 and CEA 148 signals that are received by the fetch FIFO unit 142 in response to a fetch request. If the fetched cache line was returned (i.e., response=‘1’b), the second decoder 158 sets the appropriate clr_fip [0 . . . 63] signal 170 thereby indicating that the associated cache line was retrieved.

[0032] A counter 160 is used to generate pulses at a predetermined time. The counter 160 generates a pulse, timeout_pulse, 162 within every n clock cycles. The timeout_pulse 162 is transmitted to each fetch state machine 152.

[0033] In addition, a reset signal 164 is transmitted to each of the fetch state machines 152 which can be set at system initialization, or the like, by one of the processors 106 or by another control unit. The reset signal 164 initializes the fetch state machine 152.

[0034] Each of the fetch state machines 152 has a time_out signal 166 that is transmitted to the error control unit 154. The time_out signal 166 indicates that a time out has occurred which will be explained in more detail below. The error control unit 154 handles the time out conditions appropriately. For instance, the error control unit 154 can generate an interrupt that is sent to one of the processors 106 or the operating system can poll the error control unit 154 for the time outs. When the error control unit 154 determines that another fetch for the timed-out cache line is possible, the error control unit 154 sets a clr_timeout signal 168 back to the affected fetch state machine 152 which resumes the fetch state machine's processing.

[0035] Attention now turns to the operation of the fetch state machine 152. In brief, the fetch state machine 152 attempts to accurately track the time a timeout occurs while preserving the amount of circuitry required to maintain this accuracy. In this instance, there are six timeout periods. When the sixth timeout period lapses, the fetch state machine 152 will have timed out. The aggregation of the six timeout periods is set based on the maximum expected response time that a memory fetch should take to complete. The timeout periods are set at a relatively small interval so that when the timeout occurs, it can be determined with reasonable accuracy that the timeout occurred within a smaller time frame. For instance, if the maximum expected response time for a memory fetch is 100 us and each timeout period is set to 20 us, and there are six timeout periods, then when the transaction times out, it can be determined that the timeout occurred between 100-120 us. By comparison, for the same maximum expected response time, if there are only two timeout periods, each of which are set to 100 us, then when the transaction times out, the timeout will be determined to have occurred some time between 100-200 us.

[0036] Such accuracy is important in a system, such as the computer system 100 described herein, which has a hierarchy of timeouts. The lowest priority timeouts have a shorter timeout period with the higher priority timeouts having a longer timeout period. Each succeeding level in the hierarchy has a longer timeout period than the preceeding priority level. If a lower priority component timeouts longer than expected, it can affect the priority scheme.

[0037] For instance, a peripheral device 120 can have a lower priority timeout associated with it while a processor 106 is associated with a higher priority timeout. This prioritization is done so that in the event of a catastrophic failure the peripheral device 120 will shut down and not the processor 106. When the peripheral device 120 shuts down, the interface will generate error responses on its behalf. These messages will be sent to the processor 106 even though the processor 106 was expecting a non-error type of message. However, the error message will allow the processor to continue to operate and not time out. Attention now turns to the operation of the fetch state machine 152.

[0038] Referring to FIG. 4, upon system initialization or boot up, a reset signal 164 is set (step 180) and transmitted to the fetch state machine 152 which places the fetch state machine 152 in the idle state (step 182). When the set_fip signal 158 is set (step 184), then a fetch is progress has been initiated by the fetch FIFO unit 142 for the cacheline entry associated with the fetch state machine 152 and the fetch state machine 152 enters into the first Fetch-In-Progress (“FIP”) state (step 186). If a timeout_pulse 162 is set and the clr_fip is not set when the fetch state machine 152 is in the first FIP state (step 186), then the fetch state machine 152 progresses to the second FIP state (step 190). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 192), then the fetch state machine 152 resorts back to the idle state (step 182).

[0039] When the fetch state machine 152 is in the second FIP state (step 190) and the timeout_pulse 162 is set and the clr_fip is not set (step 192), the fetch state machine 152 progresses to the third FIP state (step 194). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 194), then the fetch state machine 152 resorts back to the idle state (step 182).

[0040] When the fetch state machine 152 is in the third FIP state (step 194) and the timeout_pulse 162 is set and the clr_fip is not set (step 196), the fetch state machine 152 progresses to the fourth FIP state (step 198). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 200), then the fetch state machine 152 resorts back to the idle state (step 182).

[0041] When the fetch state machine 152 is in the fourth FIP state (step 198) and the timeout_pulse 162 is set and the clr_fip is not set (step 202), the fetch state machine 152 progresses to the fifth FIP state (step 204). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 201), then the fetch state machine 152 resorts back to the idle state (step 182).

[0042] When the fetch state machine 152 is in the fifth FIP state (step 204) and the timeout_pulse 162 is set and the clr_fip is not set (step 208), the fetch state machine 152 progresses to the sixth FIP state (step 210). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 206), then the fetch state machine 152 resorts back to the idle state (step 182).

[0043] When the fetch state machine 152 is in the sixth FIP state (step 210) and the timeout_pulse 162 is set and the clr_fip is not set (step 214), the fetch state machine 152 progresses to the time out state (step 216). In the time out state, the fetch state machine 152 sets the timed_out signal 166 that is transmitted to the error control unit 154 for further processing (step 218). If the clr_fip signal 170 is set or the clr_fip signal 170 and the timeout_pulse 162 are both set simultaneously (step 212), then the fetch state machine 152 resorts back to the idle state (step 182).

[0044] Once the timout condition is handled by the error control unit 154, the clr_timeout signal 168 is set (step 220) and the fetch state machine 152 resumes back to the idle state (step 182).

[0045] The foregoing description has described a timeout mechanism that can more accurately determine the timeout of a pending transaction while reducing the amount of circuitry and processing involved.

[0046] However, it should be noted that the number of FIP states used by the fetch state machines is not a limitation on the technology of the present invention. The fetch state machines can utilize more FIP states in order to achieve more accurate timeouts. Furthermore, the technology of the present invention is not limited to the use of state machines. One skilled in the art can use counters, combinatorial logic, or the like to implement the functionality of the fetch state machines.

[0047] The foregoing description, for purposes of explanation, used specific nomenclature to provide a thorough understanding of the invention. However, it will be apparent to one skilled in the art that the specific details are not required in order to practice the invention. In other instances, well known structures and devices are shown in block diagram form in order to avoid unnecessary distraction from the underlying invention. Thus, the foregoing descriptions of specific embodiments of the present invention are presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, obviously many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.