Adaptive Arbitration Mechanism for a Shared Multi-Master Bus

The present claimed invention relates to the field of computer busses. More specifically, the present claimed invention relates to the arbitration of peripheral component interconnect (PCI) bus access among multiple peripheral components.

PCI bus systems constitute an industry standardized, widely known, and widely used approach for transporting data within a computer system. As shown in Prior Art FIG. 1, a typical PCI bus arbitration system 100 is comprised of the PCI bus 102, multiple peripheral components 104, 106, and 108, and a PCI bus arbiter 110. PCI bus 102 is coupled to each of peripheral components 104, 106, and 108 by links 112, 114, and 116 respectively. Additionally, each of peripheral components 104, 106, and 108 is coupled to PCI bus arbiter 110 via request and grant lines 118 and 120, 122 and 124, and 126 and 128, respectively.

Referring still to Prior Art FIG. 1, PCI bus arbiter 110 typically receives requests from peripheral components 104, 106, and 108 for access to PCI bus 102. PCI arbiter 110 then determines which of the requesting peripheral components will be provided with access to PCI bus 102. PCI arbiter 110 then asserts the chosen peripheral component's grant line, and the chosen peripheral component is able to access PCI bus 102.

In a PCI bus environment, because the PCI bus lines are not terminated, one peripheral component must always be granted access to the PCI bus. If one device is not granted to the PCI bus, the PCI bus will "float" at an intermediate state and will be susceptible to oscillation. Thus, it is said that in a PCI bus environment, some device must always "drive" the PCI bus. Hence, when none of the peripheral components 104, 106, and 108 are accessing PCI bus 102, PCI bus arbiter 110 must still assert the respective grant line of one of peripheral components 104, 106, and 108. Thus, even if a peripheral component is not requesting access to PCI bus 102, the peripheral component may still be given access to PCI bus 102. Asserting a grant line to a non-requesting peripheral component is referred to as "parking" the PCI bus. In conventional PCI bus environments, the PCI bus is "parked" on the last requesting peripheral component. Therefore, if grant line 120 of peripheral component 104 is asserted, when peripheral component 104 no longer requests access to PCI bus 102, and no other peripheral component is currently requesting access to PCI bus 102, grant line 120 of peripheral component 104 will remain asserted. That is, PCI bus arbiter 110 will park PCI bus 102 on peripheral component 104 even though peripheral component 104 is no longer requesting access to PCI bus 102. Although such a parking technique is functional, the technique does not predict which peripheral component will be most likely to request access to the PCI bus in the future.

PCI bus systems which employ conventional PCI bus parking methods often suffer from substantial PCI bus latency periods. For example, if PCI bus 102 is parked on peripheral component 104, and peripheral component 106 later requests access to PCI bus 102, several steps must occur before peripheral component 102 is granted access to PCI bus 102. First, PCI bus arbiter 110 must receive the request from peripheral component 106 for access to PCI bus 102. Next, PCI bus arbiter 110 must deassert grant line 120 of peripheral component 104. Finally, PCI bus arbiter 110 will be able to assert grant line 124 of peripheral component 106. Thus, a substantial number of clock cycles may pass before peripheral component 106 is allowed access to PCI bus 102. The period of time that passes from when peripheral component 106 requests access to PCI bus 102 until peripheral component 106 is granted access to PCI bus 102 is referred to as a latency period. Therefore, over a period of time, the total latency period can adversely affect operation and speed of a computer system.

Thus, a need exists for a system and method for determining the appropriate peripheral component on which to park the PCI bus. A further need exists for a system method which does not merely grant access to the PCI bus to the last peripheral component to have accessed the PCI bus. Still another need exists for a PCI arbitration system and method which decreases PCI bus access latency periods.

The present invention provides a system and method for determining the appropriate peripheral component on which to park the PCI bus wherein the system method which does not merely grant access to the PCI bus to the last peripheral component to have accessed the PCI bus. The present invention also provides a system and method which decreases PCI bus access latency periods. The present invention meets the above needs with an adaptive arbitration system and method for determining which of plurality of peripheral components will have access to a peripheral component interconnect (PCI) bus when none of the plurality of peripheral components is currently requesting access to the PCI bus.

Specifically, in one embodiment, a history buffer records all requests by a plurality of peripheral components for access to the PCI bus. The present invention then determines which of the plurality of peripheral components requests access to the PCI bus most often. Next, the present invention grants the peripheral component which requests access to the PCI bus most often access to the PCI bus when no other peripheral component is requesting access to the PCI bus. In so doing, the present invention "parks" the PCI bus on the peripheral component which has, in the past, requested access to the PCI bus most often.

In another embodiment, a history buffer records all requests by a plurality of peripheral components for access to the PCI bus. The present embodiment also includes a weight buffer. The weight buffer weights each of the recorded requests such that each of the recorded requests has a priority value associated therewith. The present embodiment the adds the priority values for each of the recorded requests such that each of the peripheral components has a total priority value associated therewith. Next, in this embodiment, the present invention compares the summed priority values to determine which of the peripheral components has the greatest priority value. The present embodiment then grants the peripheral component having the greatest priority value access to the PCI bus when no other of the plurality of peripheral components requests access to the PCI bus. In so doing, the present invention "parks" the PCI bus on the peripheral component which has the greatest priority value based on past usage of the PCI bus.

These and other advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.

The accompanying drawings, which are incorporated in and form a part of this specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention:

Prior Art FIG. 1 is a schematic diagram of a conventional PCI bus arbitration system.

FIG. 2 is a schematic diagram illustrating components of an adaptive arbiter in accordance with one embodiment of the present claimed invention.

FIG. 3 is a schematic diagram illustrating components of an adaptive arbiter having a weight buffer in accordance with one embodiment of the present claimed invention.

FIG. 4 is a timing diagram illustrating operation of the adaptive arbiter of the embodiment of FIG. 3 in accordance with the present claimed invention.

Reference will now be made in detail to the preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. While the invention will be described in conjunction with the preferred embodiments, it will be understood that they are not intended to limit the invention to these embodiments. On the contrary, the invention is intended to cover alternatives, modifications and equivalents, which may be included within the spirit and scope of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be obvious to one of ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.

With reference now to FIG. 2, a schematic diagram illustrating components of an adaptive PCI bus arbiter 200 in accordance with one embodiment of the present invention is shown. In the present embodiment, adaptive PCI bus arbiter 200 (hereinafter adaptive arbiter 200) is comprised of a history buffer 202, a summation accumulator 204, and a priority encoder 206. Adaptive arbiter 200 uses history buffer 202, summation accumulator 204, and priority encoder 206 to intelligently predict the proper peripheral component on which to park the PCI bus. A detailed description of the manner in which adaptive arbiter achieves such an accomplishment is set forth below.

Adaptive arbiter 200 of FIG. 2 includes an incoming request channel 208 for receiving PCI bus requests, and outgoing grant channel 210 represents respective grant lines of peripheral components, not shown, coupled to adaptive arbiter 200. In the present invention, requests for access to a PCI bus are received at adaptive arbiter 200 via new request channel 208. Thus, incoming request channel 208 represents the plurality of request lines which are coupled to PCI bus arbiter 200. Each time a request for access to the PCI bus is received at adaptive arbiter 200, the request is recorded as an entry in history buffer 202. In the present embodiment, history buffer 202 is an eight entry first-in-first-out (FIFO) buffer having entries R.sub.1 through R.sub.8. Therefore, when history buffer 202 is filled with eight entries, a new request causes the oldest entry, R.sub.8, to be removed from history buffer 202. Each remaining entry is shifted to the left such that R.sub.2 through R.sub.8 are occupied and R.sub.1 is vacated. The new request then becomes the newest entry, R.sub.1, in history buffer 202. Thus, only the eight most recent requests remain in history buffer 202. Although such a buffer is used in the present embodiment, the present invention is also well suited to using various other types and sizes of buffers as history buffer 202.

Referring still to FIG. 2, in the present invention, the identity of the peripheral component making the request is stored in history buffer 202. Hence, in the present embodiment, history buffer 202 provides a log of the eight most recent requests for access to the PCI bus and history buffer 202 indicates which of the peripheral components made the request for access to the PCI bus. In the present embodiment, a three bit identifier is used to identify which peripheral component requested access to the PCI bus. As a result, when full, history buffer 202 contains 8 three bit identifier entries indicating which peripheral components have made the most recent eight requests for access to the PCI bus. Although a three bit identifier is used to identify the peripheral component which makes a request for access to the PCI bus in the present embodiment, the present invention is well suited to storing various other type of identifiers in history buffer 202.

With reference still to FIG. 2, when no peripheral device is requesting access to the PCI bus, it is necessary to "park" the PCI bus on one of the peripheral components. In the present embodiment, when a need to park the PCI bus arises, summation accumulator 204 examines the contents of history buffer 202 to determine which of the plurality of peripheral components requests access to the PCI bus most often. That is, summation accumulator 204 examines each of entries R.sub.1 through R.sub.8 of history buffer 202. After summation accumulator 204 makes its determination, it instructs priority encoder 206 as to which of the peripheral components requests access to the PCI bus most often. Priority encoder 206 then asserts the grant line of the peripheral component which requests access to the PCI bus most often. As mentioned above, outgoing grant channel 210 represents respective grant lines of peripheral components coupled to adaptive arbiter 200. Thus, adaptive arbiter 200 grants access to the PCI bus to the most frequently requesting peripheral component, when no other peripheral component is requesting access to the PCI bus. In so doing, the present invention always "parks" the PCI bus on the peripheral component which has, in the past, requested access to the PCI bus most often.

Referring yet again to FIG. 2, in one embodiment, priority encoder 206 is adapted to receive additional weighting criteria. In such an embodiment, additional weighting criteria such as, for example, user inputted criteria is used to adjust the determination as to which of the peripheral components will have the PCI bus parked thereon. Such additional weighting criteria include, but are not limited to, the importance of the requesting peripheral component, the length of time the peripheral component requires access to the PCI bus, and the like. As an example, assume that a particular peripheral component, "component X", is known to typically request access to the PCI bus seven consecutive times and then not request access again for an extended period of time. Hence, after all seven consecutive requests have been made by component X, it would not be prudent to park the PCI bus on component X. By importing such additional weighting criteria in priority encoder 206, the PCI bus would not be parked on component X even when seven of the eight entries in history buffer 202 are requests for PCI access by component X. The present invention intelligently determines which peripheral component will have the PCI bus parked thereon.

Thus, unlike the prior art, the present invention does not merely park the PCI bus on the last requesting peripheral component. Instead, the present invention intelligently predicts which of the peripheral components is most likely to next request access to the PCI bus. As a result, the present invention increases the chance that the next requesting peripheral component will be the component on which the PCI bus is parked. In such an instance, the present invention significantly decreases PCI bus latency periods. More specifically, when the PCI bus is parked on a peripheral component which later requests access to the PCI bus, that component's grant line is already asserted. Hence, the present invention eliminates the need for a separate peripheral component to request from access to the PCI, the present invention eliminates the need to deassert a granted line to another peripheral component, and the present invention eliminates the need to assert the grant line to the newly requesting peripheral component. Thus, the present adaptive arbiter 200 improves PCI bus access time by a substantial number of clock cycles. In so doing, the present invention improves overall operation and speed of a computer system.

Referring next to FIG. 3, a schematic diagram of the components of another embodiment of an adaptive PCI bus arbiter is shown. As in the previous embodiment, adaptive PCI bus arbiter 300 (hereinafter adaptive arbiter 300) is comprised of a history buffer 202, a summation accumulator 204, a priority encoder 206, incoming request channel 208, and outgoing grant channel 210. In contrast to the embodiment of FIG. 2, the present embodiment also includes a weight buffer 302, and multiplication stages 304.sub.1 through 304.sub.8. Although eight multiplication stages are present in the embodiment of FIG. 3, only two of the multiplication stages 304.sub.1 and 304.sub.8 are shown for purposes clarity.

In the present invention, requests for access to a PCI bus are received at adaptive arbiter 300 via new request channel 208. Each time a request for access to the PCI bus is received at adaptive arbiter 200, the request is recorded as an entry in history buffer 202. As in embodiment of FIG. 2, history buffer 202 is an eight entry first-in-first-out (FIFO) buffer having entries R.sub.1 through R.sub.8. Although such a buffer is used in the present embodiment, the present invention is also well suited to using various other types and sizes of buffers as history buffer 202.

Referring still to FIG. 3, in the present invention, the identity of the peripheral component making the request is stored in history buffer 202. In the present embodiment, a three bit identifier is used to identify which peripheral component requested access to the PCI bus. Although a three bit identifier is used to identify the peripheral component which makes a request for access to the PCI bus in the present embodiment, the present invention is well suited to storing various other types of identifiers in history buffer 202.

With reference again to FIG. 3, weight buffer 302 is comprised of an eight entry buffer. In so doing, each of the entries in eight entry FIFO history buffer 202 has a respective entry in weight buffer 302. That is entry W.sub.1 of weight buffer 302 corresponds to entry R.sub.1 of history buffer 202, entry W.sub.2 of weight buffer 302 corresponds to entry R.sub.2 of history buffer 202, and so on. In the present embodiment, each of entries W.sub.1 through W.sub.8 of weight buffer 302 are comprised of order-based multiplication factors. More specifically, entry W.sub.1 corresponding to entry R.sub.1 of history buffer 202 has a greater value than entry W.sub.8 corresponding to entry R.sub.8 of history buffer 202. In the present embodiment, W.sub.1 has a value of 4, W.sub.2 has a value of 4, W.sub.3 has a value of 4, W.sub.4 has a value of 2, W.sub.5 has a value of 2, W.sub.6 has a value of 1, W.sub.7 has a value of 1, and W.sub.8 has a value of 1. Although such order-based multiplication factors are used in the present embodiment, the present invention is also well suited to using various other values ordering schemes.

Referring still to FIG. 3, because of the above described order-based multiplication factor entries of weight buffer 302, W.sub.1 *R.sub.1 has a greater value than W.sub.2 *R.sub.2, W.sub.2 *R.sub.2 has a greater value than W.sub.3 *R.sub.3, W.sub.3 *R.sub.3 has a greater value than W.sub.4 *R.sub.4, and so on. Additionally, the order-based multiplication factors are binary in the present embodiment to simplify the multiplication of each order-based multiplication factor and its corresponding entry in history buffer 202.

With reference still to FIG. 3, when no peripheral device is requesting access to the PCI bus, it is necessary to "park" the PCI bus on one of the peripheral components. In the present embodiment, when a need to park the PCI bus arises, each entry in weight buffer 302 is multiplied by its corresponding entry in history buffer 202. In so doing, a priority value is obtained for each of the peripheral components having its request for access to the PCI bus stored in history buffer 202. For example, if peripheral component A has made the six most recent requests for access to the PCI bus, peripheral component B has made the seventh most request for access to the PCI bus, and peripheral component C made the eighth most recent request for the PCI bus. In such an scenario, the contents of history buffer 202 are as follows: R.sub.1 =A, R.sub.2 =A, R.sub.3 =A, R.sub.4 =A, R.sub.5 =A, R.sub.6 =A, R.sub.7 =B, and R.sub.8 =C. Thus, the multiplication stages 304.sub.1 through 304.sub.8 will generate the following products: (W.sub.1 *R.sub.1), (W.sub.2 *R.sub.2), (W.sub.3 *R.sub.3), (W.sub.4 *R.sub.4), (W.sub.5 *R.sub.5), (W.sub.6 *R.sub.6), (W.sub.7 *R.sub.7), and (W.sub.8 *R.sub.8).

Referring still to FIG. 3, after the multiplication stages are completed, summation accumulator 204 determines the priority value for each component. Component A will have a priority value of (W.sub.1 *R.sub.1)+(W.sub.2 *R.sub.2)+(W.sub.3 *R.sub.3)+(W.sub.4 *R.sub.4)+(W.sub.5 *R.sub.5)+(W.sub.6 *R.sub.6). That is, in the present embodiment, the priority value for component A=17. Component B will have a priority value of (W.sub.7 *R.sub.7), or B=1. Similarly, component C will have a priority value of (W.sub.8 *R.sub.8), or C=1. Hence, summation accumulator 204 determines that component A has the highest priority value. After summation accumulator 204 makes its determination, it instructs priority encoder 206 as to which of the peripheral components has the highest priority value. Priority encoder 206 then asserts the grant line of the peripheral component which has the highest priority value. As mentioned above, outgoing grant channel 210 represents respective grant lines of peripheral components coupled to adaptive arbiter 200. Thus, adaptive arbiter 300 grants access to the PCI bus to the peripheral component having the highest priority value, when no other peripheral component is requesting access to the PCI bus. In so doing, the present invention always "parks" the PCI bus on the peripheral component which, based on the last eight recorded requests, has the highest priority value.

With reference next to FIG. 4, a timing diagram 400 illustrating operation of the adaptive arbiter 300 of FIG. 3 is shown. FIG. 4 pertains to the above described example in which peripheral component A has made the six most recent requests for access to the PCI bus, peripheral component B has made the seventh most request for access to the PCI bus, and peripheral component C made the eighth most recent request for the PCI bus. Peripheral component A's requests are shown in region 402 as assertions of REQA#. After peripheral component A's first request, at t.sub.1, peripheral component A's grant line is asserted as shown by the assertion of GNTA# at t.sub.2. Note, even though no component is requesting access to the PCI bus at t.sub.3, GNTA# stays asserted in the present invention. At t.sub.4 peripheral component B requests access to the PCI bus. Thus, at t.sub.5 GNTA# is deasserted and GNTB# is asserted. At t.sub.6, no peripheral component requests the PCI bus, however, the present invention at t.sub.7 deasserts GNTB# and reasserts GNTA#. Thus, the present invention does not merely park the PCI bus on the last requesting peripheral component.

Referring still to FIG. 4, GNTA# stays asserted until t.sub.9, immediately following peripheral component C's request for access to the PCI bus at t.sub.8. At t.sub.9, GNTA# is deasserted and GNTC# is asserted. At t.sub.10, no peripheral components requests access to the PCI bus. Because peripheral component A has the highest priority value, as described above in detail, GNTC# is deasserted and GNTA# is asserted at t.sub.11. Because of the predictive nature the present adaptive arbiter invention, the PCI bus is already parked on peripheral component A when A requests access to the PCI bus at times t.sub.12 and .sub.13. As a result, at times t.sub.12 and t.sub.13, the present invention eliminates the need to deassert a granted line to peripheral component other than A, and the present invention eliminates the need to assert the grant line to newly requesting peripheral component A. Thus, the present invention improves PCI bus access time by a substantial number of clock cycles.

Referring yet again to FIG. 3, in one embodiment, priority encoder 206 is adapted to receive additional weighting criteria. In such an embodiment, additional weighting criteria such as, for example, user inputted criteria is used to adjust the determination as to which of the peripheral components will have the PCI bus parked thereon. Such additional weighting criteria include, but are not limited to, the importance of the requesting peripheral component, the length of time the peripheral component requires access to the PCI bus, and the like. A detailed description of how such additional weighting criteria is employed can be found above in conjunction with the embodiment of FIG. 2.

Thus, unlike the prior art, the present invention does not merely park the PCI bus on the last requesting peripheral component. Instead, the present invention intelligently determines a priority value for each requesting peripheral component and parks the PCI bus on the peripheral component with the highest priority value. In so doing, the present invention increases the chance that the next requesting peripheral component will be the component on which the PCI bus is parked. As mentioned above, the present invention significantly decreases PCI bus latency periods, and, in turn, improves overall operation and speed of a computer system.

Thus, the present invention provides a system and method for determining the appropriate peripheral component on which to park a PCI bus wherein the system method which does not merely grant access to the PCI bus to the last peripheral component to have accessed the PCI bus. The present invention also provides a system and method which decreases PCI bus access latency periods.

The foregoing descriptions of specific embodiments of the present invention have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, 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 Claims appended hereto and their equivalents.