Methods and apparatus for adaptive time keeping for multiple timers

A timer distribution module supports multiple timers and comprises: a command decoder arranged to determine expiration times of a plurality of timers; and a timer link list distribution adapter, LLDA, operably coupled to the command decoder. The LLDA is arranged to: receive a time reference from a master clock; receive timer data from the command decoder wherein the timer data comprises at least one timer expiration link list; construct a plurality of timer link lists based on at least one of: the timer expiration link list, at least one configurable timing barrier; dynamically split the link list timer data into a plurality of granularities based on the timer expiration link list; and output the dynamically split link list timer data.

FIELD OF THE INVENTION

The field of this invention relates to methods and apparatus for adaptive time keeping, and in particular to large scale adaptive time keeping for integrated circuits employing multiple timers.

BACKGROUND OF THE INVENTION

As processing power and the number of supported applications increases in computer/digital/software based devices, there is an ever growing need for an increased number of timers that are operable to oversee a multitude of tasks within integrated circuit (IC) devices. However, as the number of timers increase, software solutions have become more expensive and less accurate. Hardware solutions to manage millions of timers running in parallel, which requires providing services for millions of counters, are problematic and often prohibitive in terms of cost, die space and power consumption.

Timers, generally, are counters that are fed with an initial duration value and a counting granularity, in order to create a ‘timer’ value. For example, a timer may be allocated a hundred time units, with a one second granularity, creating a one hundred second timer. Upon expiration of the timer, a timer node notifies the relevant timer creator that the timer has expired, and the relevant timer creator can proceed/process whatever it is programmed to do after expiration of the timer.

Different mechanisms are generally utilised for different timing duration distributions.

In the networking domain, millions of simultaneously running timers are generally utilised to manage networking flows and quality of service related aspects. Typically, in the network domain, timers would run with high resolution granularities (microseconds up to milliseconds) for relatively short durations.

In the domain of general purpose processors (GPP), for example tasks requiring switching/watchdog timers, a large amount of timers are also utilised to manage various applications. For typical GPP usage, there could be around tens of thousands of timers being run in parallel, which would generally be for lower resolutions (milliseconds up to seconds) and running for relatively long durations.

Generally, managing tens of thousands to millions of timers tends to require a large number of counters. These counters tend to take up a lot of silicon area and, therefore, cannot be physically located within the IC. Therefore, an algorithmic approach is generally utilised to manage the vast amount of timers, without having to physically represent the counters, which generally takes the form of timing rings/wheels.

Referring toFIG. 1, an example of a known timing wheel, comprising a simplified timing wheel,100is illustrated. Simplified timing wheel100comprises N number of slots102, with six slots shown in this illustration, and a number of timers104,105,106associated with time slot107, and timers108,109associated with time slot110. Each of the number of slots102represents a time unit, wherein a cursor112within the timing wheel100moves onto the next location every time unit, in the same manner as a second hand on a clock. In this case, the cursor112is currently located at timeslot114, having previously been located at timeslot107at the previous time interval. When the cursor112moves onto timeslot110, the timers108and109associated with timeslot110will expire at that instant, or when the cursor112reaches the timeslot110in subsequent cycles. The cursor112continues to increment onto subsequent time slots and wraps back to timeslot107after the cursor112increments past the final array entry.

The number of slots102in the timing wheel100has a limit that is defined by the array size of the timing wheel100. For example, the maximum schedulable event that can be stored in the timing wheel could be 350 msec, but a 400 msec timing event needs to be stored. This leads to an overflow problem, wherein the 400 msec timing event cannot be stored.

As discussed above, different timing distributions require different timing mechanisms, resulting in potential problems if one mechanism is utilised for all timing distributions. In the networking domain, there is generally a need for millions of timers with short expiration times and a relatively small granularity, as they generally function in the ‘microsecond up to millisecond domain’. However, GPPs generally require a relatively larger granularity, as they tend to function up to the ‘second’ domain. Therefore, timing wheels for GPPs that have a large granularity will waste a lot of power during operation, for example when they are being monitored at a higher granularity level and may provide higher accuracy than needed. Further, utilising networking domain timing wheels for GPPs, would require a large number of timing wheels, due to the relatively smaller granularity, resulting in a large and expensive overhead, which affects the overall power/performance of devices.

DETAILED DESCRIPTION

The illustrated embodiments should not be seen as limited to GPP and networking applications. These examples have merely been given to illustrate the functionality provided in the illustrated embodiments, and it is envisaged that the concepts herein described are applicable to any system that employs or supports multiple timer types and encompasses other timer types, such as security applications requiring expirations of secure processes for enhanced protection, or system management processes requiring tailor-made time keeping solutions for the proper maintenance of the system.

Further, the use and creation of new link lists in the illustrated embodiments is merely one example of supporting multiple timers and other list types and data structures are envisaged.

Referring toFIG. 2, an example of a timer distribution module200is illustrated, comprising a configuration module204operably coupled to a command decoder module206, a clock, which may be a master wall clock (MWC)212, operable to receive a control input210, operably coupled to a link list distribution adapter module (LLDA)214, which may, in some further examples be operably coupled to the command decoder module206. In this example, the MWC may be a free running wall clock, which is operable to generate an ‘n’ bits wide counter. The counter may take the form of, for example, ‘hours: minutes: seconds: milliseconds: microseconds’, wherein each part relates to a different granularity of the counters.

The configuration module204may be configured via an external system host202, and may be operable to configure timing barriers through a table of ‘M’ values, wherein each ‘M’ value may define a specific barrier. In some examples, the number of barriers to be configured may be dependent on the timing configuration. For example, for GPP domain applications, a single barrier may be implemented, which may allow for a linear distribution of timers. In some other examples, multiple barriers may be utilised for networking domain applications, which may allow for a narrow distribution of hardware timers link lists.

The command decoder module206may receive timer management commands from the configuration module204, for example create, delete, etc., and may be operable to align an expected expiration time according to a defined timing granularity. Subsequently, in some examples, the command decoder module206may be required to insert a timer into a chosen link list. Further, in some examples, it is envisaged that the command decoder module206may receive timer creation and/or timer deletion commands.

In some examples, the LLDA214may be operable to receive timer data, including a timer expiration value and the relevant chosen link list, from the configuration module204, as well as receive counter data from MWC212. Subsequently, the LLDA214may create timer context records and transmit218the records to memory (not shown), for example double data rate (DDR) synchronous dynamic random-access memory (SDRAM). The LLDA214may utilise counter data from the MWC212, which may comprise wall clock timing ticks, to facilitate accurate timing handling.

In some examples, if a timing event, which may hold a link list of timers, is about to expire, the LLDA214may be operable to output expiration notifications through a bus216, which may be a dedicated event expiration bus.

In some further examples, the LLDA214may perform link list construction and transmit218the constructed link list to memory, which may be an external memory. In other examples, the LLDA214may perform link list construction at external memory and, in some examples, create a timer context record in the (external) memory. The link list construction may be dynamically performed for each user configured granularity.

In some examples, a user may configure a number of barriers that he wishes to utilise, which may depend on the application, for example GPP, etc. Therefore, the number of granularities will be configured based on the user's determined number of barriers.

For each barrier that the user wishes to utilise, a place/index of the signal from the MWC212needs to be provided. For example, if a user decided to divide the processed reported signal from the MWC212into three fields, then the user would need to configure at least two barriers. The first barrier may be at, say, index (bit)23and the second barrier may be at, say, index (bit)43.

The above example results in a 64-bit [63:0] MWC212, which comprises three regions, namely a high granularity region [63:43], a medium granularity region [42:23], and a low granularity region [22:0].

In some examples, the LLDA214may receive and analyse one or more commands from the command decoder module206. In some examples, the one or more commands may comprise at least a future expiration date for a timer context record and, therefore, the LLDA214may be operable to utilise wall clock barriers/dividers from clock212to determine a suitable granularity link list to define where the context record should be positioned.

After the above operation has been completed, and a relevant link list has been ‘built’, a standard ‘add to link list tail flow’ may be utilised for subsequent operations.

In some examples, a user may be required to configure aspects of the clock212prior to the LLDA214‘building’ relevant link lists. For example, the user may be required or provided with the ability to determine how many barriers are going to be valid inside the clock212and thereafter determine or set indexes for each of the determined barriers.

The user configured aspects of the clock212may be utilised by the LLDA214when ‘building’ relevant link lists. For example, the LLDA214may receive a ‘timer create’ command from the command decoder module206, and subsequently may normalise a time duration with respect to a granularity into a basic expiration date. Subsequently, this basic expiration date may be inspected by the LLDA214according to the user configured barriers and, in this manner, the LLDA214may be operable to place a context record in a suitable position.

Thus, granularities may be able to be customised for each timing event. As a result, the timer distribution module200may be able to support a wide range of timing events, which may have a significant variation in granularities and durations. For example, as discussed above, this is in contrast to current devices that are only set up for use with a particular domain timing event, for example GPP domain or networking domain timing events, which represent examples of two vastly different domain timing events.

In some examples, when utilising an LLDA214, timer expiration link lists may be able to be dynamically split into finer granularities at dynamically required positions, thereby allowing the timer distribution module200to handle various timing events. This may increase the flexibility and reduce the complexity of incorporating timer distribution modules200into device architecture.

For example, timer distribution module200may, initially, be configured to function within the GPP domain. Therefore, in such a scenario, the LLDA214may initially utilise a relatively coarse granularity, and operate using a timing wheel that may be similar to simplified timing wheel100ofFIG. 1.

However, during operation, the timer distribution module200may be subsequently required to operate in a different timer domain, for example a networking domain. As known, current timing wheels that are designed for a particular application, for example, GPP domain usage are not adequate for other types of timing domains, generally because the granularity is too coarse and this leads to poor accuracy.

However, utilising the LLDA214, the granularity and position of altering the granularity may be dynamically controlled. For example, initially, the LLDA214may have utilised timing wheel252for supporting GPP domain applications. In some examples, the timing wheel252may represent ‘seconds’ of a counter of clock212. Therefore, for GPP applications, the timing wheel252may be suitable. However, if the timer distribution module200is required to support a different time domain application, for example a networking domain application, the LLDA214may initiate further timing wheels, for example timing wheels254,256, in order to support one or more networking domain applications.

It is known that an overflow problem and/or an accuracy problem can occur in traditional systems when a tailor-made timer distribution module for GPP applications is utilised for finer granularity applications, such as networking applications. Therefore, in some examples, the LLDA214may be configured to initiate, say, timing wheel254, which may represent milliseconds, and/or timing wheel256, which may represent microseconds, depending on the current scenario. Therefore, in this manner, dynamically altering the granularity of the available timing wheels may enable the timing distribution module200, incorporating the LLDA214, to support various timing applications that require different granularities, whilst still maintaining accuracy and/or efficient memory usage.

In this example, during initial operation, timing wheel252may be utilised, which may comprise ‘N’ number of slots, with six slots shown in this illustration. Each time slot261may comprise a number of timers associated with a particular time slot261. Each of the number of slots represents a time unit, wherein a cursor262moves onto the next location every time unit, i.e. pointing to the next time slot. During a subsequent operation, timing wheels254,256, may be utilised, for example if the timer distribution module200is to be utilised for a different timing application. Therefore, the LLDA214may initiate these further timing wheels254,256in order to alter the available granularity of the timer distribution module200.

In this example, utilising timing wheels252,254,256, networking domain applications may be able to be supported as well as coarser granularity timing applications, without sacrificing accuracy or memory usage. For example, a cursor258may transition between time slots259, which may represent, microseconds, and wrap around to the beginning of the timing wheel256when the cursor258reaches the end of timing wheel256. Subsequently, a cursor260from timing wheel254may transition a time slot255every time the cursor258wraps around to the beginning of timing wheel256. Further, the cursor262may transition a time slot261when the cursor260wraps around to the beginning of timing wheel254. Therefore, utilising the LLDA214, granularities of timer distribution module200may be dynamically tailored to the specific requirements of timer applications.

In some examples, the number of time slots in each of the timing wheels252,254,256may vary and, therefore, cursors262.260,258may not necessarily transition based on a wrap around of a previous cursor.

Further, in some examples, the LLDA214may, as well as changing the granularity of the timer distribution module200, be further operable to dynamically determine the position of barriers, which may result in determining where link lists are split.

For example, the LLDA214may receive commands transmitted via the command decoder module206, and execute, and in some examples decode, the received commands. Additionally, a data base may be ‘built’ at external memory.

The received commands transmitted via the command decoder module206may have initially been formed in conjunction with the configuration module204receiving and outputting configuration information, which may have been transmitted from external system host202, to the command decoder module206, and by the command decoder module206receiving timer commands, for example timer commands208.

Further, the LLDA214may receive a number of ticks, for example a time unit tick219, from clock212. For each time unit tick219, a timer expiration module215within the LLDA214may check218if a link list is available, which may be at external memory, for a particular time unit tick219. If the LLDA214determines that there is a link list available for the particular time unit tick219, the LLDA214may notify timers related to the available link list that they have expired. In some examples, the timer expiration module215may fetch216the entire link list that is available for the particular time unit tick219, in order to be able to notify relevant timers about the expirations. If the LLDA214determines that there are no relevant link lists for the particular time unit tick219, the LLDA214may wait for the next tick from clock212.

In some examples, the LLDA214may continue to fetch216relevant link lists until the link list ends.

Referring toFIG. 3, an example of a further timer distribution module300is illustrated, comprising two timer distribution modules200,200′ fromFIG. 2. In some other examples, the timer distribution module300may comprise more or less than two timer distribution modules200,200′, which may depend on external system constraints.

In this example, a first timer distribution module200may be operably coupled to a GPP entity302, and a second timer distribution module200′ may be operably coupled to a networking entity304.

It is known that a timer distribution module in known systems, which is tailor-made for operation with, for example, a GPP entity, is unable to accurately operate with entities requiring a different granularity, for example, a networking entity due, in part, to its use of a fixed granularity.

However, in some examples and by utilising LLDA module214, the first timer distribution module200and second timer distribution module200′ may be operable to dynamically alter the granularity output to GPP entity302and networking entity304, without any hardware modification between timer distribution modules200,200′. Therefore, by dynamically modifying output information from the LLDA module214, the first timer distribution module200may be operable to support GPP entity302, whereas second timer distribution module304may be operable to support networking entity304.

In this example, the MWC212may report the current time in a physical counter that is output306to the LLDA214, where the physical counter may be ‘n’-bits wide. In this manner, the LLDA214may dynamically determine whether to utilise the output306in full, facilitating a granularity suitable for GPP entity302, or divide the output306into a number of smaller values, thereby reflecting different granularities that may be suitable for networking entity304.

In some examples, the mechanisms to divide a received physical counter may be one or more timing barriers. Each time barrier may specifically describe a timer wheel that may handle relevant timers.

Thus, utilising the LLDA214in first timer distribution module200and the second timer distribution module200′, may allow for different granularities of timer applications to be supported. Therefore, utilising the LLDA214may allow for each of the first200and second200′ timer distribution modules to be utilised for the same or different timing applications.

In some examples, a single timer distribution module200,200′ may be utilised to support a GPP entity302and a networking entity304at different times. However, for concurrent operations, separate timer distribution modules200,200′, which may be configured dynamically for either supporting GPP entity302or networking entity304, may need to be utilised.

Further, in some other examples, timer distribution module200may be further configured to support networking entity304, and timer distribution module200′ may be further configured to support GPP entity302.

It should be noted, that embodiments are not limited to GPP and/or networking modes. These applications were chosen to illustrate aspects of the invention as they represent examples of different timer needs, with respect to accuracy, duration etc. As a result, some example aspects may be suitable for a variety of fields that may utilise characteristics somewhere between or above GPP and networking modes.

Referring toFIG. 4, an example timer wheel401is illustrated, with corresponding divided simplified timer wheels for a GPP application400and a networking application450.

Initially, example timer wheel401may comprise an N-bit (time slot) array, which in this example may be a sixteen-bit array for explanatory purposes. The size of timer wheel401may be incompatible/non-ideal for some applications and, therefore, an LLDA, for example LLDA214fromFIGS. 2 and 3, may be utilised to dynamically assign one or more barriers403to the timer wheel401. In some examples, the number of barriers may be implementation/application specific.

For example, if timer wheel401is to be utilised with a GPP application, it may be beneficial to implement a single barrier403at a particular point on the timer wheel401.

In this example, for illustrative purposes, barrier403has been positioned after the fourth bit in example timer wheel401. This may result in the example timer wheel401being split into timer wheel414comprising 4 bits, and timer wheel402comprising X-4 bits. Each element within timer wheel402may be associated (e.g. point) to a link list, for example link lists408,410, which may later be spread between bits of timer wheel414upon reaching a relevant point in time.

In this example, a cursor405may be initially positioned on the third bit406, indicating that any timers in linked list410may be due to expire.

In some examples, the LLDA214fromFIGS. 2 and 3may be operable to dynamically assign one or more barriers403, which in this illustrated example is one barrier after the fourth bit412. The barrier411in this example may separate linked lists408,410with a first granularity from subsequent linked lists with a future second granularity, pointed to by the bits situated after the barrier411.

Therefore, the LLDA214may be operable to dynamically determine the number of barriers to be inserted, and the position of those barriers, as, for example, is illustrated forFIGS. 2 and 3.

In some examples, the timer wheel401may be utilised with an application that requires more than one barrier, for example a networking application. Therefore, in this example, a number of barriers may be utilised.

For illustrative purposes, two further barriers407have been positioned within timer wheel401, amounting to a total of three barriers407,403. The position and number of barriers in this example are purely illustrative.

In some examples, the LLDA214may be operable to dynamically switch from a first timer type application to a second timer type application, e.g. from the GPP application400operation to the networking operation450.

The combination of the three barriers403,407in this example, results in a four-way split of resultant timer wheels,452,454,456,458.

In this example, the size of the resultant timer wheels452,454,456,458have been illustrated with an equal number of bits. This is purely for illustrative purposes, and the resultant timer wheels452,454,456,458may be any size that can be determined by the initial size of timer wheel401and position and number of barriers403,407.

In some examples, the resultant timer wheels452,454,456,458may form a hierarchical structure of hierarchical rings, wherein, for example, timer wheel452may represent ‘days’, timer wheel454may represent ‘hours’, timer wheel456may represent ‘minutes’ and timer wheel458may represent ‘seconds’.

Therefore, in some examples, the LLDA214may be operable to dynamically assign any number of barriers and dynamically determine the position of those barriers, thereby allowing the LLDA214to redefine the granularity of a timer distribution module incorporating the LLDA214.

Therefore, in this manner a timer distribution module utilising the LLDA214may allow for a re-configurable device, which may be operable to support different granularities of timing applications without the need to modify the hardware of the timer distribution module.

Such a timer distribution module utilising the LLDA214may be utilised for system on a chip (SoC) applications, for example. A SoC is an integrated circuit that integrates all components of a computer or other electronic system into a single chip. A SoC generally comprises both hardware and software for controlling, for example, a microcontroller, microprocessor or digital signal processing (DSP) cores, peripherals and interfaces. Therefore, by providing a timer distribution module, which may be able to dynamically assign any number of barriers and dynamically determine the position of those barriers, may provide a more flexible and efficient timing mechanism to be implemented.

Referring toFIG. 5, an example block diagram of a link list distribution adapter (LLDA)500, such as the LLDA214ofFIGS. 2 and 3, is illustrated. In some examples, the LLDA500may be similar to the LLDA214ofFIG. 2. In this case, the LLDA500may be an internal block instantiated under a TDM module200hierarchy. In this example, the LLDA500may provided with one or more inputs from the TDM module200, which for example may comprise one or more of user configuration commands for selection of barriers, generated signals from MWC212and other user commands. In this example, the LLDA500may have one or more modes of operation. A first mode of operation may comprise command execution functionality and a second mode of operation may comprise expiration notification functionality.

an expiration module501that is operable to determine if a link list is available, for example by reading and notifying expirations if a read link list is not empty,

a receiver module502that is operable to receive commands,

a decoder module504that is operable to decode commands received from the receiver module502; and

an execution module506that is operable to execute decoded commands from decoder module504.

Referring to the first mode of operation, the LLDA500may initially be in an ‘idle’ state, awaiting timer commands508to be received by receiver module502. If a timer command508is received by the receiver module502, the LLDA may transition out of an idle state and into an active state. In response to this transition, the receiver module502may sample the received timer command508and determine any additional information supplied with the timer command508.

After sampling the received timer command508, the LLDA500may be operable to transmit the received timer command508onto the decoder module504. The decoder module504may be operable to decode the timer command508, in order, for example, to determine what the command comprises. In some examples, the command may comprise, for example, a timer create/delete command etc.

Utilising the decoded timer command508, the decoder module504may subsequently apply previously received information, for example granularity and duration information, in order to determine a position that a timer record should be positioned in memory, for example in external memory (not shown).

In some examples, the previously received information may have been user defined. In other examples, the previously received information may have been dynamically determined by the LLDA500. The decoder module504may subsequently instruct the execution module506to position510the relevant timer record in memory.

Referring to a second mode of operation, the LLDA500may determine that for every time tick512received from a clock, for example clock212, it may instructs expiration module501to check whether a link list is available514for the current received time tick512. If the expiration module501determines that there is a link list available for the current time tick512, the LLDA500may be aware that some timers may need to be notified as ‘expired’.

Subsequently, the LLDA500may instruct the expiration module501to determine if the available link list is empty or comprises timer information. If the expiration module501determines that the available link list is not empty, it may fetch the entire available link list in order to notify timers about expirations.

Referring toFIG. 6, an example of a simplified flow chart of a timer distribution module operation600is illustrated. Initially, at602, the operation of the timer distribution module begins and one or more LLDAs within the TDM may be configured. At604, the TDM may receive a user configuration, which may comprise information on a number of barriers that the user wishes to be configured for a particular application. At606, the TDM may publish the configuration to all TDM sub blocks, for example a configuration module, clock, and command decoder.

At608, the TDM may receive one or more timer commands from, for example, an external system host.

The TDM may then, at610, forward information, which may comprise the determination of how to implement the one or more received timer commands to an LLDA module, for example LLDA module214fromFIG. 2, before returning to608.

Referring toFIG. 7, an example of a simplified flow chart of a link list distribution adapter (LLDA) operation700is illustrated. Initially, at702, the operation of the LLDA begins and at704, the LLDA receives configuration information from an associated TDM. After the LLDA has been configured, the LLDA may determine whether it has received any commands.

The received information may facilitate the LLDA to perform one or both of a command execution function and an expiration handling function.

If the LLDA is operable to perform a command execution function, the LLDA may, at706, determine whether it has received any timer commands from the TDM. If the LLDA determines at706that it has not received any timer commands, it may enter a loop until it receives timer commands. Otherwise, the LLDA may transition to708, and sample the received timer command(s) and determine any additional information/attributes associated with the received information.

At710, the LLDA may decode and determine how to implement the one or more received timer commands, which may be based on current and published time by an associated master wall clock, for example clock212. In some examples, the timer command may be a timer create/delete command, which may be utilised to determine where a relevant timer record should be positioned. In some further examples, the supplied information may be determined dynamically by the LLDA.

At712, the LLDA may build a database in memory, for example external memory, before transitioning back to706.

If the LLDA is operable to perform an expiration handling function, the LLDA may, at714, receive a time unit tick, and determine whether there is a link list available for the current received time unit tick. If the LLDA determines that there is a relevant link list available, which may mean that there are timers that should be notified as expired for the current time unit tick received at714, the LLDA may, at716, read the respective link list for the associated time unit tick.

At718, the LLDA determines whether the available link list is empty. If it is determined that the link list is empty, the LLDA may transition to back to714. Otherwise, the LLDA may transition to720and fetch the link list and notify timers in the link list as expired, before returning to714.

Any arrangement of components to achieve the same functionality is effectively ‘associated’ such that the desired functionality is achieved. Hence, any two components herein combined to achieve a particular functionality can be seen as ‘associated with’ each other such that the desired functionality is achieved, irrespective of architectures or intermediary components. Likewise, any two components so associated can also be viewed as being ‘operably connected’, or ‘operably coupled’, to each other to achieve the desired functionality.

Also for example, in one embodiment, the illustrated examples may be implemented as circuitry located on a single integrated circuit or within a same device. For example, the link list may be constructed and sent to internal memory of, say, the timer distribution module200. In other examples, the LLDA (e.g. LLDA214ofFIG. 2) may perform link list construction at internal memory to the timer distribution module200, rather than external memory. In some examples, a timer context record may be created in memory internal to the timer distribution module200rather than being external. Alternatively, the examples may be implemented as any number of separate integrated circuits or separate devices interconnected with each other in a suitable manner.