Abstract:
A system and method provide adaptive frequency scaling for predicting the load on a processing unit and dynamically changing its clock frequency while keeping the synchronization with other processing units. The amount of data in an input memory waiting to be processed is a good indicator of the current load and thus embodiments of the present invention utilize the same concept for predicting the load on the processing unit. The frequency of operation is thus changed on the basis of the percentage of memory being occupied by its input data. Algorithms according to embodiments of the present invention allow the processing unit to use the maximum possible clock frequency only when it is required and to run at some lower frequencies in low processing power requirements. Operating the circuit at low frequency helps in reducing power consumption.

Description:
PRIORITY CLAIM  
       [0001]     This application claims priority from Indian patent application No. 931/Del/2006, filed Mar. 31, 2006, which is incorporated herein by reference.  
       TECHNICAL FIELD  
       [0002]     The present invention relates to dynamic frequency scaling in electronic devices and more particularly to adaptive frequency scaling based on workload prediction for reducing power consumption in an electronic device.  
       BACKGROUND  
       [0003]     Current trends in the chip industry point to the development of heterogeneous systems that will be able to support several complementary standards on a single chip in order to satisfy the user&#39;s demands in diverse application scenarios. These systems will lead to the integration of existing technologies and standards and will be based on reconfigurable architecture consisting of hardware units shared between different technologies and standards.  
         [0004]     Supporting different types of task or service requests in a heterogeneous system based on reconfigurable architectures and side-by-side satisfying the need for low power consumption is a challenge.  
         [0005]     An interactive mobile terminal, for example can spend 90% of system energy and time waiting for a user response. Such idle periods provide opportunities for dynamic power management and voltage scaling techniques to reduce the system power usage. Dynamic voltage frequency scaling (DVFS) is a technique to reduce active power consumption by scaling processor frequency and voltage to meet the required performance. This technique enables a chip to operate at different voltages and clock frequencies. In a system based on dynamic frequency clocking, the current operating frequency of a processing unit is set on the basis of different factors. These factors may be application, environment, or circuit specific. The conventional systems based on dynamic frequency clocking try to reduce the power consumption by changing the frequency on the basis of technology or standard or interface being used at that time.  
         [0006]     The most effective way to reduce dynamic power consumption on an implementation level is scaling of the supply voltage due to the quadratic dependence. The limiting parameter is the propagation delay through a digital circuit that increases with low supply voltages.  
         [0007]     The propagation delay through a CMOS circuit increases drastically as the supply voltage approaches the threshold voltage of the circuit. On the other hand, there is only little impact on performance with high supply voltages. Therefore, any voltage reduction must be balanced against performance reduction. To compensate and maintain the same data throughput extra hardware may be added.  
         [0008]     The working principle of dynamic frequency clocking has been explained with the help of a block diagram shown in  FIG. 1 . A Clock Divider Block (also known as Frequency Divider Block) ( 101 ) is used to generate multiple clock frequencies based on a master clock frequency which is the maximum frequency at which the synthesized system can work. The multiple clocks have been shown as  102 A,  102 B,  102 C and  102 D. A frequency selector ( 103 ) selects one of these frequencies based on some control signals generated by a control block ( 104 ). The delay that is needed by the dynamic frequency scaling circuit to change the clock frequency and remaining stabilized is taken into account at the time of implementation.  
         [0009]     One system and method for dynamic clock generation includes a clock controller for an Application Specific Integrated Circuit (ASIC) for a portable electronic device that dynamically and automatically varies the frequency of on-chip clocks in response to bandwidth requirements of the driven logic. The ASIC includes one or more oscillators used by phase locked loops (PLLs) to generate one or more master clocks. These master clocks are received by a system clock controller which derives various clocks of different frequencies from the master clocks. These derived clocks are used to drive the various controllers and peripherals connected to the ASIC. For example, the system clock controller preferably generates a memory clock for clocking the memory controller and the external memory devices, a bus clock for clocking the system bus, a CPU clock for clocking the CPU, and one or more peripheral clocks for clocking the various peripheral controllers and peripherals coupled to the ASIC. The various devices in the ASIC that can be accessed by other devices in the ASIC are known as “resources”. The speed at which a resource is clocked affects the rate at which the resource can process data (i.e. the bandwidth of the resource). Every device in the ASIC that can access a resource, also known as a controller, has a request line coupled to the system clock controller to indicate when the controller is accessing a resource. In addition, the system clock controller has a programmable bandwidth register associated with each controller for holding a value representing the bandwidth utilized by the controller. The system clock controller also preferably includes an adder, a frequency table, and a multiplexer (MUX) for each clocked resource. When a controller accesses a resource, the controller signals the system clock controller via the request line. The system clock controller in turn, uses the adder to sum the values held in the bandwidth registers of all of the controllers that are currently accessing the resource. The resulting sum is then used as an index to an entry in the frequency table. The contents of the entry are applied to the selection lines of the MUX and dynamically select the appropriate clock frequency for the resource. Thus, the clock frequency for the resource is automatically determined by the total bandwidth utilization of the controllers requesting access to the resource. Accordingly, the clock frequency is preferably chosen so that the bandwidth of the resource closely matches the needed bandwidth. As a result, little power is wasted due to operating the resource at a higher clock frequency than is necessary.  
         [0010]     The above mentioned technique and other such techniques based on conventional dynamic frequency clocking reduce power consumption in an ASIC by changing the frequency of operation on the basis of the interface or standard being used at that time. These conventional techniques cannot work in the scenarios when there is only one technology or standard or interface controller is being used. In case of single standard, the processing requirement may change depending on the real time incoming data scenarios. For example, the real time data scenario may vary from time to time in terms of the number of packets arriving in a burst, size of each packet, inter-packet delay. Data sometimes can come as a burst of large number of packets whereas other times, the burst can just comprise only two or three packets. These variations have not been taken into account by any of the existing techniques of frequency scaling.  
         [0011]     Therefore, there arises a need for a system and method for dynamic frequency scaling which dynamically modifies the frequency of operation not on the basis of interface and standard being used but on the basis of load on the processing unit at a particular time, which is the right criterion for the processing requirement.  
       SUMMARY  
       [0012]     Embodiments of the present invention provide an improved technique of dynamic frequency scaling which modifies the frequency of operation not on the basis of an interface and standard being used but on the basis of the load on the processing unit at a particular instant of time.  
         [0013]     An improved algorithm predicts the load on the processing unit and dynamically changes its clock frequency while keeping the synchronization with other processing units. The amount of data in the input memory waiting to be processed is a good indicator of the current load. Embodiments of the present invention utilize the same concept for predicting the load on the processing unit. The frequency of operation is thus changed on the basis of the percentage of memory being occupied by its input data. Algorithms according to embodiments of the present invention allow the processing unit to use the maximum possible clock frequency only when it is required and run at some lower frequencies in low processing power requirements. Operating the circuit at low frequency helps in reducing power consumption. The present invention also provides a method of implementing the proposed algorithm in the form of a simple digital circuit.  
         [0014]     To overcome the drawbacks of the prior art and to achieve the aforementioned objectives, according to one embodiment of the present invention, a system for adaptive frequency scaling in an electronic device includes an input interface block for receiving real time data, at least one processing unit for processing real time data received by the input interface block, at least one memory unit for storing the real time data before the data is processed by the processing unit, a frequency divider block for generating multiple clock frequencies from received clock frequency; and a control unit for selecting the appropriate frequency of operation from the multiple clock frequencies wherein the selection is based on the level of utilization of the memory unit.  
         [0015]     According to one embodiment of the present invention a method for adaptive frequency scaling in an electronic device includes initializing the processing unit of said electronic device at a first frequency, keeping track of data present in memory for processing, signaling the change in occupancy level of memory; and changing the frequency of operation of said processing unit in response to change in occupancy level of memory 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]     Embodiments of the invention will now be described with reference to the accompanying drawings.  
         [0017]      FIG. 1  shows the basic principle of dynamic frequency clocking in the form of a block diagram.  
         [0018]      FIG. 2  shows a block diagram of the basic structure of a standard chip.  
         [0019]      FIG. 3  shows a block diagram of an asynchronous FIFO according to an embodiment of the present invention.  
         [0020]      FIG. 4  shows a block diagram of a system according to an embodiment of the present invention.  
         [0021]      FIG. 5  shows the logic used for the functioning of a Moore machine.  
         [0022]      FIG. 6  shows the implementation of a frequency divider according to an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0023]     The following discussion is presented to enable a person skilled in the art to make and use the invention. Various modifications to the embodiments will be readily apparent to those skilled in the art, and the generic principles herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0024]      FIG. 2  shows a block diagram of a standard chip. An Input Interface Block ( 201 ) receives real-time data which needs to be processed inside the chip by some Processing Units. The Input Interface Block ( 201 ) may either support different standards or a single standard depending on the implementation. The frequency of the Input Interface block is fixed depending on the standard it is supporting e.g. XGMII, GMII etc., while on the other hand, the Processing Units ( 202  A and  202  B) use dynamic frequency scaling scheme. The data is passed from one clock domain to another clock domain through FIFOs ( 203 A and  203 B). The data values are written to a FIFO buffer from one clock domain and the data values are read from the same FIFO buffer from another clock domain, where the two clock domains can be asynchronous to each other.  
         [0025]      FIG. 3  shows a block diagram of an asynchronous FIFO used in embodiments of the present invention. Two independent interfaces to the queue with all the signals needed for the implementation of the algorithm of embodiments of the present invention are also shown. Signals wr_clk &amp; rd_clk denote the clocks used to write to and read from the FIFO buffer respectively. Full &amp; Empty are the signals used to check whether the FIFO is full or empty respectively. The FIFO implementation uses separate pointers for write &amp; read, WR_PTR &amp; RD_PTR whose width depends on the depth of RAM used to implement the asynchronous FIFO. Before incrementing the FIFO pointers, “if not Full” or “if not Empty” tests are performed to ensure that overflow or underflow would not happen anytime. These tests are implemented by comparing the status of WR_PTR and RD_PTR.  
         [0026]     Apart from the above mentioned signals, a multi-bit signal named “almost_full” (herein after referred to as “status signal”) of width N is used to signal the different percentage occupancy levels of the FIFO buffer. The width of the signal, N, depends on the implementation &amp; different parameters like the maximum or average length of the packets that can come on the input interface and the depth of the buffer used to implement the FIFO. For example, if the average packet length of the incoming packet is 512 bytes, maximum packet length is 1024 bytes and the FIFO RAM depth is 8 Kbytes, then the width N can be taken as 3 such that “almost_full[2]=1” implies that the buffer is at least 75% filled i.e. buffer has at least 12 average size packets, “almost_full[1]=1” implies that the buffer is at least 50% filled but less than 75% i.e. buffer has between 8-12 average size packets, and “almost_full[0]=1” implies that the buffer is at least 25% filled but less than 50% i.e. buffer has between 4-8 average size packets. So in this case we have,  
         [0027]     almost_full[2]=1, if buffer occupancy is between 75% and 100%;  
         [0028]     almost_full[1]=1, if buffer occupancy is between 50% and 75%; and  
         [0029]     almost_full[0]=1, if buffer occupancy is between 25% and 50%.  
         [0030]     Where, “between a % and b %” means greater than or equal to a % but less than b %. Where a and b can take any value like 25, 50, 75, 100 as mentioned above.  
         [0031]     Different bits of “almost_full” are asserted by comparing the status of WR_PTR &amp; RD_PTR as is done to assert “Full” and “Empty” signals. The above definition clearly states that only one single bit of “Almost_Full” can be asserted at a time. So in the above example, whenever the memory occupancy level increases from 25% to 50%, the value of the signal almost_full[2:0] changes from “001” to “010”. This type of implementation is analogous with the Hot Code notation in which only one bit can be asserted at a time. Depending on the design implementation for multiple clock domains, it may be converted to Gray Code notation, which is the preferred notation for multiple clock domains. The value of this signal is updated in the “wr_clk” domain i.e. the clock of the block which is writing to this asynchronous FIFO, whereas it is captured and used in the “rd_clk” domain to change the frequency of the processing unit which has to read and process the data stored in this FIFO buffer. The “almost_full” signal from asynchronous FIFO,  203 A, is used to generate clock signal for processing unit  202 A as shown in  FIG. 4 . Similarly, the “almost_full” signal from asynchronous FIFO,  203 B, is used to generate a clock signal for processing unit  202 B. Hence every processing unit has its clock generation circuit, as shown in  FIG. 4 , to generate its clock using “almost_full” signal from its input asynchronous FIFO.  
         [0032]     The frequency of the processing unit in embodiments of the present invention is changed on the basis of the change in workload. The workload is estimated on the basis of the amount of data in the memory waiting to be processed by the processing unit. This is predicted by checking the status of “almost_full” signal. Whenever the value of the signal “almost_full” changes, the algorithm changes the frequency of the processing unit. This means that the performance of the algorithm is highly dependent on the definition and the structure of the signal “almost_full” since it represents different memory occupancy levels. Whenever any change is detected in “almost_full”, it triggers the algorithm to change the frequency of the processing unit. For the structure and definition of the “almost_full” signal described above, the frequency of the processing unit changes only when the memory occupancy level reaches 25%, 50% or 75%. The frequency would not get changed for any other changes in the memory occupancy level because the algorithm is dependent on the structure of “almost_full” signal and according to the above defined definition, the value of “almost_full” signal changes only when the memory occupancy reaches 25%, 50% or 75%. The value of the “almost_full” signal will remain the same for other changes in the memory occupancy. The total number of frequencies at which the processing block can run also depends on the implementation of “almost_full”. If the width of the signal “almost_full” is N, then the total number of frequencies available to the processing block is N+1.  
         [0033]     Again considering the above example in which the signal width is 3, the total number of available frequencies is 4. Now, referring to  FIG. 4  which shows a block diagram of a system according to an embodiment of the present invention. A signal “fmax” is the master clock frequency used to generate other scaled clock frequencies using a series of “divide-by-2” frequency dividers. The frequency dividers may be implemented using T flip-flop. The signals  102 A,  102 B,  102 C and  102 D are the four frequencies synthesized by the Frequency Divider Block ( 101 ). The frequency  102 A represents the master clock frequency, fmax, and other three frequencies  102 B,  102 C and  102 D are the frequencies that can be synthesized using the “divide-by-2” strategy based Frequency Divider Block ( 101 ) such that  102 A&gt; 102 B&gt; 102 C&gt; 102 D. The actual scaling factor for generating these frequencies depends on the implementation. For the above example, let us choose scaling factor of 2, 4 and 8 for the frequencies  102 B,  102 C and  102 D respectively such that  102 A=2* 102 B=4* 102 C=8* 102 D. A frequency selector ( 103 ) selects one of these frequencies based on some control signals generated by a control block ( 104 ). The selected frequency is shown as f in  FIG. 4 .  
         [0034]     In one embodiment, the clock frequency for the next task is changed to any of these four frequencies whenever any change in “almost_full” is detected. The processing unit starts working at the lowest frequency, which is  102 D in this example. If the value of almost_full[2:0] increases, say from 000 to 001, it means that 25% of memory is now filled with data that needs to be processed by the processing unit and processing unit should try to process the data faster, so increase its frequency to the next level frequency,  102 C. Again depending on how the “almost_full” is changed next time, the frequency is changed from  102 C to  102 B or from  102 C to  102 D depending on whether “almost_full” has decreased or increased respectively. A clock for triggering the control block ( 104 ) is generated by a trigger generator ( 405 ) as shown in  FIG. 4 . The trigger generator ( 405 ) receives the selected clock of frequency (f) and the signal “almost_full” as its input. Every cycle of the clock signal having frequency (f), the trigger generator ( 405 ) compares the current value of “almost_full” signal with the value available in the last clock cycle. In case the value has got changed, it asserts the signal, CLK, which is used as the clock of control block ( 104 ).  
         [0035]     In one embodiment of the present invention, a Moore machine acts as a Control Block ( 104 ). The Moore machine is implemented by means of a synchronous sequential circuit and its clock, CLK, is generated by the trigger generator ( 405 ).  FIG. 5  shows the state machine used for the implementation of the Moore machine. The Moore machine, on each rising edge of CLK, generates control signals, O 1  and O 2 , which are used by the frequency selector ( 103 ) and frequency divider block ( 101 ). The state numbers, shown in  FIG. 5 , represents the output associated with each state. It is shown that the output associated with each state is fed to the frequency selector which determines the next frequency of the processing unit. The starting state of Moore machine is 00. At this starting point, the value of Almost_Full [2:0] is 000 and the frequency is minimum i.e.  102 D. Now if from this point, the value of Almost_Full [2:0] gets changed to 001, then the next state would be 01. Depending on the further changes in the value of the “almost_full” signal, the state can change from 01 to 00 or 10 and so on.  
         [0036]     The implementation of the frequency divider block ( 101 ) is shown in  FIG. 6 .  601 A,  601 B, and  601 C are divide-by-two frequency dividers. They are implemented by means of T flip-flops.  602  A,  602 B and  602 C are pass logic blocks. These blocks allow or block a signal to pass through them depending on whether the blocks are enabled or disabled respectively. An Encoder ( 603 ) takes the outputs, O 1  and O 2 , of Control Block ( 104 ) as its inputs and sends signals c[2], c[1] and c[0] respectively to  601 A,  601 B, and  601 C. These signals enable Pass Logic blocks such that only the needed scaled frequency is generated as the output of frequency divider. Assuming that the “almost_full [2:0]” signal changes its value from 000 to 001, the output of Control Block [O 1 ,O 2 ], would be 01 and the frequency needed would be  102 C i.e. only two Pass Logic blocks need to be activated. So encoder ( 603 ) generates c [2:0] as 110. As a result, pass logic blocks  602 A and  602 B are enabled and the required frequency (which is  102 C in this case) is generated at the output of  601 B. Similarly, if the output of the Control Block is 10, frequency needed would be  102 B, so encoder ( 603 ) generates c[2:0] as 100. Also, for output values of 11 and 00, the value of c[2:0] would be 000 and 111 respectively. So depending on the values of output of Control Block, O 1  and O 2 , the encoder ( 603 ) generates c[2:0] so that only the required logic is enabled.  
         [0037]     It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description of embodiments thereof. It is also believed that it will be apparent that various changes may be made in the form, construction and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an exemplary embodiment thereof, it is the intention of the following claims to encompass and include such changes. Embodiments of the present invention can be utilized in a variety of different types of electronic devices, such as cellular telephones and personal digital assistants.  
         [0038]     From the foregoing it will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without deviating from the spirit and scope of the invention.