Pre-arbitration request limiter for an integrated multi-master bus system

1. Technical Field

The present invention relates to a method and structure for dynamically blocking access of a request signal to a shared bus such that the request originates from a non real-time master and requests access to an address range of an address space.

2. Related Art

With a proliferation of highly integrated system-on-a-chip designs, the shared bus architecture that allows major functional units to communicate is commonly utilized. There are many different shared bus designs which fit into a few distinct topographies. A known approach in shared bus topography is for multiple masters to present requests to an arbiter of the shared bus for accessing an address range of an address space, such as an address space of a given slave device. The arbiter awards bus control to the highest priority request based on a request prioritization algorithm. As an example, a shared bus may include a Processor Local Bus (PLB), wherein the PLB is part a CoreConnect bus architecture of the International Business Machines Corporation (IBM).

The use of an arbiter presents a key problem for a bus architecture in which the arbiter has visibility only to requests when the requests are made and has no knowledge of requests to be made subsequently. With a PLB, for example, the arbitration is done on a request-by-request basis, and requests are honored on the basis of immediate priority according to the prioritization algorithm.

The aforementioned limited visibility of the arbiter presents a critical problem for real-time processing such as the real-time processing of video and audio decoders. Such real-time processing involves sequentially stacked multiple requests by real-time masters (e.g., video and audio decoders) for access to an address range of an address space, in competition with requests to the same address range by non real-time masters such as central processing units (CPUs). The multiple requests are stacked in internal queues of the real-time masters but the status of such internal queues are invisible to the arbiter of the shared bus to which the queued requests will subsequently be presented. Thus a relatively low-priority request originating from a non real-time master (e.g., a CPU) and visible to the arbiter may be granted by the arbiter while a much higher priority request from a real-time master (e.g., a video decoder) may be sitting in the real-time master's internal queue. If such high priority requests from the video decoder are not processed within specified time limits, then an artifact instead of a real image will appear on a video screen. Accordingly, video and audio decoders need to process data on a real-time basis.

Thus, there is a need to limit access of requests from non-real time masters in deference to internally queued requests of real-time masters.

The present invention provides a digital system, comprising:

a request limiter having a blocking mechanism for blocking access of a request signal to a shared bus, wherein the request signal originates from a blockable master, wherein the request signal requests access by the blockable master to an address range A of an address space, and wherein the shared bus manages requests for access to the address space;

a real-time clock, wherein an instantaneous clock cycle of the real time clock is denoted by a clock cycle index K such that K is a non-negative integer; and

an algorithm capable of dynamically enabling and disabling the blocking mechanism, wherein the algorithm is coupled to the clock, wherein the algorithm includes a dependence on K, wherein the algorithm includes a dependence on a variable Q whose value is a function of Q 1 , Q 2 , . . . , and Q I , wherein Q i (i=1, 2, . . . , I) denotes an internal queuing state of an i th controlling master M i , and wherein I is a positive integer that denotes a total number of the controlling masters.

The present invention provides a method for dynamically blocking an access of a request signal R to a shared bus such that R originates from a blockable master and requests access to an address range A of an address space, comprising the steps of:

providing the blockable master;

providing the shared bus for managing requests for access to the address space;

providing a real-time clock whose instantaneous clock cycle is denoted by a clock cycle index K such that K is a non-negative integer;

providing I controlling masters denoted as M 1 , M 2 , . . . , and M I , wherein I is a positive integer that denotes a total number of the controlling masters, and wherein each M i (i=1, 2, . . . , I) is interfaced with the shared bus such that M i may transmit a request signal R i to the shared bus for access to an address range A i within the address space; and

interfacing a request limiter between the blockable master and the shared bus, wherein the request limiter includes a blocking mechanism capable of blocking said access of the request signal R to the shared bus, wherein the blocking mechanism functions in accordance with an algorithm, wherein the algorithm is coupled to the clock, wherein the algorithm includes a dependence on K, wherein the algorithm includes a dependence on a variable Q whose value is a function F of Q 1 , Q 2 , . . . , and Q I , and wherein Q i denotes an internal queuing state of M i (i=1, 2, . . . , I).

The present invention has the advantage of limiting access of requests from non-real time masters in deference to internally queued requests of real-time masters.

FIG. 1 depicts a digital system, in accordance with preferred embodiments of the present invention.

FIG. 1 illustrates digital system 10 , in accordance with preferred embodiments of the present invention. The digital system 10 includes a blockable master 20 , a controlling master 30 , a request limiter 40 , a shared bus 50 , and an address space 60 .

The address space 60 is subdivided into portions 61 , 62 , 63 , 64 , 65 , 66 , and 67 , wherein the aforementioned portions includes address ranges. For example, the portion 64 includes the address range A. A particular address range (i.e., an address range within one of the portions 61 , 62 , 63 , 64 , 65 , 66 , and 67 ), may constitute an addressable portion of a slave device such as a random access memory ( 14 ) device. Access to any address range within the address space 60 may be requested by any master device within the system 10 , such as the blockable master 20 or the controlling master 30 . Although the system 10 in FIG. 1 includes exactly 7 portions ( 61 , 62 , 63 , 64 , 65 , 66 , and 67 ) with corresponding address ranges, the system 10 may generally include L portions, wherein L is any positive integer.

The controlling master 30 represents a master device M i (i=1, 2, . . . , I) of I controlling master devices. The controlling master 30 is not distinct from M i but is rather a symbolic representation of the I controlling masters M i (i=1, 2, . . . , I). The signal 32 originating from the master device M i includes a request signal R i for access to an address range A i associated with a portion 63 of the address space 60 . Note that the signal 32 in not limited to a single request signal R i that is associated with only one value of i, but may include any number of R i 's (i.e., any combination of R 1 , R 2 , . . . , R I ). M i is a master device that is able to control a blocking of access (in conjunction with a request limiter 40 , and a sideband signal 34 from M i to an algorithm, as will be described infra) of the blockable master 20 to an address range B i (i=1, 2, . . . , I) of the address space 60 , wherein the address range B i may be specified or determined by M i . B i may correspond to any of the portions 61 - 67 of the address space 60 . Such control of blocking of access of the blockable master 20 includes a control of transient blocking, rather than a control of permanent blocking, as will be explained infra. M i may advantageously control the blocking of access of the blockable master 20 to the same address range A i to which M i is itself seeking access through M i 's request signal R i (i.e., B i =A i for i=1, 2, . . . , I). For example, if the address range A i relates to an SDRAM (synchronous dynamic random access memory) such that M i seeks access to the SDRAM, then M i may advantageously control a blocking of access of the blockable master 20 to a SDRAM controller for the address range A i . The aforementioned ability of M i to control a blocking of access of the blockable master 20 (or of any other blockable master) is particularly important if M i is, inter alia, a real-time master device such as a video decoder or an audio decoder. As a real-time master device, M i requires real-time access to A i with little or no interruption. For example, if the video decoder is unable to satisfy its memory access requirements on a real-time basis, then an artifact instead of a real video image may appear on a video screen that receives signals from the video decoder.

The blockable master 20 is a master device whose signal 22 includes a request signal R for memory access to an address range A within a portion 64 of the address space 60 . The ability of the controlling master 30 to control a blocking of access of the blockable master 20 to an address range, such as may be specified by M i (i=1, 2, . . . , I), may nevertheless be combined with useful features that reduce or minimize restrictions on access by the blockable master 20 to the address range A. For example, a useful feature may be to disable blocking whenever A is unequal to each and every address range A i (i=1, 2, . . . , I) that M i is seeking access to, as discussed infra. The blockable master 20 may include, inter alia, a non real-time device (e.g., a central processing unit), which may operate less efficiently if its memory access requests are transiently blocked, but will nonetheless not lose functionality from a delayed access that results from blocking such memory access requests.

The shared bus 50 processes memory access requests, such as memory access requests of the controlling master 30 and the blockable master 20 . Thus, the controlling master 30 (i.e., the controlling masters M i , i=1, 2, . . . , I) and the blockable master 20 all use the shared bus 50 to process their respective requests for memory access. In particular, the signal 22 from the blockable master 20 , and the signal 32 from the controlling master 30 , must present their respective requests to the shared bus 50 . In accordance with a prioritization algorithm, the shared bus 50 resolves conflicting requests for memory, such as simultaneous or time-overlapping requests for the same memory address ranges. The shared bus 50 also functions as a conduit for accommodating a flow of data that is associated with a memory access request. As an example, a shared bus may include a Processor Local Bus (PLB), wherein the PLB is part of a CoreConnect bus architecture of the International Business Machines Corporation (IBM).

The request limiter 40 is a device which has a blocking mechanism 42 that is able to block access of the blockable master 20 under control by the any or all of the controlling masters M i (i=1, 2, . . . , I), wherein the M i are collectively represented by the controlling master 30 . The blocking mechanism 42 may block access of the signal 22 that includes the request signal R for access of the blockable master 20 to the address range A within the portion 64 of the address space 60 . Generally, the blocking mechanism 42 is any mechanism known to one of ordinary skill that can block (e.g., prevent or degate) a digital signal from propagating to the digital signal's destination. For example, the blocking mechanism 42 may be physically implemented by an AND gate which functions as a switch that opens or closes a circuit through which the request signal R must propagate in order to reach its destination. When the request signal R is being blocked, R may be held in any possible location. For example, the blocking mechanism 42 , when blocking the request signal R, may constrain R to remain in an internal queue of the blockable master 20 . As another example, the blocking mechanism 42 , when blocking the request signal R, may constrain R to be stored in an internal queue of the request limiter 40 .

The request limiter 40 is coupled to the shared bus 50 . If the request limiter 40 is electrically coupled to the shared bus 50 , then the request limiter 40 is capable of transmitting the signal 22 , in the form of an electric current, to the shared bus 50 . If the request limiter 40 is optically coupled to the shared bus 50 , then the request limiter 40 is capable of transmitting the signal 22 , in the form of electromagnetic radiation, to the shared bus 50 .

The blocking mechanism 42 of the request limiter 40 functions in accordance with an algorithm 46 . The algorithm 46 may be built into a hardware, such as an electronics hardware, of the request limiter 40 , but may alternatively be executable from software code, wherein the software code may reside either within the request limiter 40 or be located external to the request limiter 40 . If located external to the request limiter 40 , the software code may be recorded on a recordable medium such as on, inter alia, a disk drive, a disk, a magnetic tape, a compact disk, or a memory device (e.g., a RAM device). The algorithm 46 is coupled to the blocking mechanism 42 , as illustrated in FIG. 1, and may transiently enable or disable the blocking mechanism 42 based on variables that the algorithm 46 processes. The algorithm 46 is said to enable the blocking mechanism 42 if the algorithm 46 takes explicit action to enable the blocking mechanism 42 or takes no action to disable the blocking mechanism 42 when the blocking mechanism 42 is already enabled. The algorithm 46 is said to disable the blocking mechanism 42 if the algorithm 46 takes explicit action to disable the blocking mechanism 42 or takes no action to enable the blocking mechanism 42 when the blocking mechanism 42 is already disabled.

The algorithm 46 is coupled to a real-time clock 44 and receives input that originates from the clock 44 . The algorithm 46 may also receive input from a sideband signal 34 (denoted as S) that originates from the controlling master 30 (i.e., from any combination of M i (i=1, 2, . . . , I). The ability of the controlling master 30 to transmit S to the algorithm 46 couples the controlling master 30 to the request limiter 40 inasmuch as the algorithm 46 is coupled to the blocking mechanism 42 of the request limiter 40 as shown in FIG. 1 and as described supra. The clock 44 may be built into the hardware of the request limiter 40 , but may alternatively be located external to the request limiter 40 . The clock 44 moves forward in time in discrete units, namely clock cycles. Each clock cycle encompasses a finite time interval and is denoted by a clock cycle index K, wherein K is a non-negative integer. The clock 44 may be a positive clock such that K increases as time moves forward, or a negative clock such that K decreases as time moves forward. The algorithm 46 receives K as input from the clock 44 , and the algorithm 46 includes a dependence on K.

The sideband signal 34 originates from the controlling master 30 and provides input to the algorithm 46 . The input to the algorithm 46 that exists within the sideband signal 34 may include, inter alia: information concerning an internal queuing state Q i (i=1, 2, . . . , I) of each controlling master M i , address ranges B i (i=1, 2, . . . , I) to which access by the blockable master 20 is to be blocked, and an integer N which determines the clock cycles during which address access blocking may occur. The internal queuing state Q i includes a status of data to be subsequently transferred between Q i and a slave device such as random access memory (RAM). Specific ways in which the preceding components of the sideband signal 34 may be utilized by the algorithm 46 will be discussed infra. The sideband signal 34 may be transmitted from the controlling master 30 to the algorithm 46 by any transfer path. For example, the sideband signal 34 may be transmitted directly from the controlling master 30 to the algorithm 46 . As another example, the sideband signal 34 may be transmitted from the controlling master 30 to within the request limiter 40 and then to the algorithm 46 .

As stated supra, the sideband signal 34 may include information concerning the internal queuing state Q i (i=1, 2, . . . , I) of each controlling master M i as represented by the controlling master 30 . In particular, Q i may denote, inter alia, an existence of data queued for subsequent transfer from M i to a slave device (e.g., a memory device such as an SDRAM), or from the slave device to M i . Q i may additionally include information concerning a number of bits or bytes of data queued for subsequent transfer to or from the slave device. The algorithm 46 may include a dependence on a variable Q which represents any combination or function F of Q 1 , Q 2 , . . . , and Q I . The algorithm 46 may receive Q as a component of the sideband signal 34 . Alternatively, the algorithm 46 may receive the individual Q i (i=1, 2, . . . , I) from the sideband signal 34 , followed by computation by the algorithm 46 of the function F of Q 1 , Q 2 , . . . , and Q I . Note that Q 1 , Q 2 , . . . , Q I , Q, and F are application dependent and may be defined in any useful manner for a given application. In a particular embodiment, Q i (i=1, 2, . . . , I) may be a binary variable having permissible values of 0 and 1 which respectively denote an empty and non-empty internal queue of M i , wherein Q is a binary variable that is equal to the logical function of Q 1 OR Q 2 OR . . . OR Q I , and wherein the algorithm disables the blocking mechanism 42 whenever Q=0. It is thus pertinent that the shared bus 50 , such as a processor local bus (PLB) of a CoreConnect bus architecture of IBM, may have no way of knowing anything about the internal queuing state Q i of the controlling masters M i . By blocking access of the blockable master 20 whenever any controlling master M i has data in its queue or has data access requests in it queue, the algorithm 46 compensates for the shared bus 50 's lack of knowledge of Q i .

The sideband signal 34 may include the address range B i (i=1, 2, . . . , I) whose access by the blockable master 20 is to be subsequently blocked by the blocking mechanism 42 of the request limiter 40 in conjunction with the algorithm 46 . As stated supra, the B i (i=1, 2, . . . , I) may be included within S, which permits the controlling masters M i to control the blocking access to the address ranges B i (i=1, 2, . . . , I), because S originates from M i , i=1, 2, . . . , I. It may be particularly useful for the controlling master M i to control the blocking of access to an address range B i during a time frame in which the controlling master M i itself requires access to B i . The preceding particularly useful control of blocking of access may be implemented by having B i =A i , wherein A i is the address range to which M i is seeking access. As an alternative (or a supplement) to having the B i included within S, the B i may be built into the algorithm 46 . If built into the algorithm 46 , the B i (i=1, 2, . . . , I) could reflect other considerations for denoting the B i as address ranges to be blocked from access by the controllable master 20 , wherein said other considerations are unrelated to dynamic control by M i of said access to B i .

The algorithm 46 may disable the blocking mechanism 42 whenever A is unequal to each and every of such address range B i (i=1, 2, . . . , I) of the address space 60 , wherein A denotes an address range of the address space 60 that the blockable master 20 seeks access to, and wherein the B i (i=1,2, . . . ,I) are the address ranges to be blocked. For the special case of B i =A i (i=1, 2, . . . , I) as discussed supra, the preceding disablement criterion would have the algorithm 46 disable the blocking mechanism 42 whenever A is unequal to each and every of such address range A i (i=1,2, . . . ,I) of the address space 60 . The preceding special case of B i =A i , together with inclusion of A i within S, would allow the controlling masters M i to substantially avoid having their data access requests delayed while nevertheless reducing or minimizing restrictions on access by the blockable master 20 to the address range A. This would circumvent a problem that could exist if a given address range cannot simultaneously accommodate a plurality of data transfer requests.

The algorithm 46 may use a windowing scheme that permits access of R to the shared bus 50 every N th clock cycle, wherein the value of the integer N may be supplied to the request limiter by the sideband signal 34 . Thus, the sideband signal 34 may include the integer N which determines the clock cycles during which there may be a blocking of access requests of the blockable master 20 . In particular, the algorithm 46 may disable the blocking mechanism every Nth clock cycle of the real-time clock 44 ; i.e., whenever there is an instantaneous clock cycle K such that K-J is an integer multiple of N on or after a clock cycle J of the clock 44 , wherein J denotes a clock cycle during which N becomes known to the algorithm 46 . Since the sideband signal 34 can be repeatedly transferred to the algorithm 46 and the contents of the sideband signal 34 can differ for each such transfer, the variables N and J may change as the clock 44 moves forward in time. Note that the preceding integer multiples of N may be negative to accommodate a mode in which the clock 44 counts downward (i.e., the instantaneous clock cycle index K decreases as the clock 44 moves forward in time). Alternatively, the preceding integer multiples of N may be positive to accommodate a mode in which the clock 44 counts upward (i.e., the instantaneous clock cycle index K increases as the clock 44 moves forward in time). As an alternative to having N and J supplied to the algorithm by at least one of the M i (i=1, 2, . . . , I), N and J may be built into the algorithm 46 .

Letting Q i (i=1, 2, . . . , I) be a binary variable having permissible values of 0 and 1 which respectively denote an empty and non-empty internal queue of M i , the preceding three inputs (Q i , A i , and N) to the algorithm 46 that may exist within the sideband signal 34 could be taken into account by the algorithm 46 as follows: the algorithm 46 enables the blocking mechanism 42 whenever Q=1 wherein Q is a binary variable defined as Q 1 OR Q 2 OR . . . OR Q I , the instantaneous clock cycle K is such that K-J is not an integral multiple of N on or after the clock cycle J, and wherein A (recalling that A denotes an address range that the blockable master 20 seeks access to) is equal to each address range A i (i=1, 2, . . . , I) of the address space 60 such that a request originating from M i requests access to A i . Although not explicitly depicted in FIG. 1, the case of A=A i is a special case in which the portions 63 and 64 of the address space 60 comprise overlapping address ranges.

While preferred and particular embodiments of the present invention have been described herein for purposes of illustration, many modifications and changes will become apparent to those skilled in the art. Accordingly, the appended claims are intended to encompass all such modifications and changes as fall within the true spirit and scope of this invention.