It is known that temperature gradients and thermal hotspots affect the reliability of microprocessors. Temperature is also an important constraint when maximizing the performance of processors. Although DVFS and DFS can be used to extract higher performance from temperature and power constrained single core processors, the full potential of multi-core performance cannot be exploited without the use of thread migration or task-to-core allocation schemes. In this paper, we formulate the problem of throughput-optimal task allocation on thermally constrained multi-core processors, and present a novel solution that includes optimal speed throttling. We show that the algorithms are implementable in real time and can be implemented in operating system's dynamic scheduling policy. The method presented here can result in a significant improvement in throughput over existing methods (5X over a naive scheme).

This paper describes a fast and accurate technique to predict the steady-state throughput and the corresponding power consumption of a homogeneous multicore processor for a given benchmark workload while accounting for speed reduction due to thermal constraints. The expressions contain several parameters of interest to a system designer, like the static and dynamic-power consumptions (for hottest block and for full chip), the vertical thermal resistance of the hottest block, the leakage sensitivity to temperature, the chip threshold temperature, the ambient temperature, etc. Their computational complexity is independent of the number of cores. These are incorporated in a system-level multicore power/thermal simulator that uses the PTScalar power model and the Hotspot thermal model. The analytical throughput and power predictions were within 1.7% of that predicted by the system-level simulator. However, the analytical technique takes less than 0.2 s for a given set of design parameters, making it well suited for early design-space exploration. In contrast, the numerical technique takes anywhere from a minute (for 4 cores) up to a few hours (for 25 cores).

We address the problem of efficient online computation of the speeds of different cores of a multi-core processor to maximize the throughput (which is expressed as a weighted sum of the speeds), subject to an upper bound on the core temperatures. We first compute the solution for steady-state thermal conditions by solving a linear program. We then present two approaches to computing the transient speed curves for each core: (i) a local solution, which involves solving a linear program every time step (of about 10 ms), and (ii) a global solution, which computes the optimal speed curve over a large time window (of about 100 s) by solving a non-linear program. We showed that the local solution is insensitive to the weights assigned in the performance objective (hence the need for the global solution). This is because a reduction in the speed of a core can only reduce the temperature of the other cores over much larger time periods (of the order of several seconds). The local solution is then completely determined by the temperature constraint equations. We show that the constraint matrix exhibits a special property - it can be expressed as the sum of a diagonal matrix and a matrix with identical rows. This allows us to solve the multi-core thermal constraint equations analytically to determine the (temporally) local optimum speeds. Further, we showed that due to this property, the steady-state speed solution selects a set of threads to operate at maximum temperature, and turns off all unused cores. Hence, to ensure that all available threads are scheduled, we impose a ldquofairnessrdquo constraint. Finally, we show how the open-loop speed control methods proposed above could be used together with a feedback controller to achieve robustness to model uncertainty.

Migrating threads away from the hot cores in a multicore processor allows them to operate at up to higher speeds. While this technique has already attracted a lot of research effort, the majority of thread migration studies are simulation-based. Although they are valuable for micro-architectural level optimization, they require prohibitively long simulation times, and hence have limited value for early design space exploration. We derive closed form expressions for the steady-state throughput of a multicore processor that employs thread migration and throttling for thermal management. These expressions can be evaluated under a millisecond (vs days for cycle-accurate simulation), and allow designers greater flexibility in evaluating the trade-offs involved in implementing thread migration on-chip. We also developed a system-level power/thermal simulator that we used to validate the analytical results.

We derive analytically, the performance optimal throttling curve for a processor under thermal constraints for a given task sequence. We found that keeping the chip temperature constant requires an exponential speed curve. Earlier works that propose constant throttling only keep the package/case temperature constant, and are hence suboptimal. We develop high-level thermal and power models that are simple enough for analysis, yet account for important effects like the power-density variation across a chip (hotspots), leakage dependence on temperature (LDT), and differing thermal characteristics of the silicon die and the thermal solution. We use a piecewise-linear approximation for the exponential leakage dependence on temperature, and devise a method to remove the circular dependency between leakage power and temperature. To solve the multi-task speed control problem, we first solve analytically, the single task problem with a constraint on the final package temperature using optimal control theory. We then find the optimum final package temperature of each task by dynamic programming. We compared the total execution time of several randomly generated task sequences using the optimal control policy against a constant speed throttling policy, and found significantly smaller total execution times. We compared the thermal profiles predicted by the proposed high-level thermal model to that of the Hotspot thermal model, and found them to be in good agreement.

We analyze the effect of thermal constraints on the performance and power of multi-core processors. We propose system-level power and thermal models, and derive expressions for (a) the maximum number of cores that can be activated, with and without throttling, (b) the speedup (multi-core over single core), and the total power consumption, both as functions of the number of active cores. These expressions involve parameters like power per core, thermal resistance of hottest die block and package, and leakage dependence on temperature. We also computed the above metrics (a) and (b) numerically by solving the detailed Hotspot circuit of an multicore processor driven by a block-level exponential temperaturedependent leakage model. When compared to these numerical results, we found that the above expressions for (a) were at most 8% underpredicted, while those for (b) were accurately predicted. The proposed analytical approach is the first of its kind to relate metrics of interest in multi-core processors to high-level design parameters. Compared to numerical approaches, it provides much faster computation time, and valuable insight for processor designers.

We propose a modular approach for minimizing the total energy consumed by a pair of generic communicating devices (producer--consumer scenario) by jointly controlling their speed profiles. Each device (like a CPU, or disk drive) is assumed to have a controllable variable called its speed (e.g., a CPU's clock frequency, a disk drive's spindle motor speed) that affects its power consumption and performance (e.g., throughput, data transfer rate). The device and task models we analyzed were inspired by applications like CD recording (hard drive to CD drive data transfer) and data processing (disk drive to CPU data transfer). The proposed solution can be used for any pair of devices with convex (for continuous speed sets) or W-convex (a discrete version of a convex function for discrete speed sets) power--speed relationships. For discrete speed sets, the method operates directly on the power--speed values and does not require an analytical relationship between power and speed. The key to solving the two-device optimization problem was the observation that it could be split into two single device parametric optimization problems, where the parameters correspond to the common task that both the devices must execute. The following divide-and-conquer approach is proposed: [divide] the optimal speed policy and energy consumption of each device is derived as an analytical function of its task parameters; [conquer] the optimal values of these parameters are found by minimizing the sum of the parameterized energy functions and plugged back into the parameterized speed profiles. The main advantage of this approach is that each device can be characterized independently and this allows system designers to mix and match manufacturer-supplied device energy curves to evaluate and optimize different application scenarios. We demonstrate our approach using three device characterization examples (for a CD drive, hard drive, and a CPU) and two application scenarios (CD recording, MD5 checksum computation).

As semiconductor manufacturing technology scales to smaller device sizes, the power consumption of clocked digital ICs begins to increase. Dynamic voltage and frequency scaling (DVFS) is a well-known technique for conserving energy. Recently, it has also been used to control the CPU temperature as part of Dynamic Thermal Management (DTM) techniques. Most works in these areas assume that the optimum speed profile (for either minimizing energy or maximizing performance) is a constant profile. However, in the presence of thermal constraints, we show that the optimal profile is in general, a time-varying function. We formulate the problem of maximizing the average throughput of a processor over a given time period, subject to thermal and speed constraints, as a problem in the calculus of variations. The variational approach provides a powerful framework for precisely specifying and solving the speed control problem, and allows us to obtain an exact analytical solution. The solution methodology is very general, and works for any convex power model, and simple lumped RC thermal models. The resulting speed profiles were found to consist of up to three segments, of which one of them is a decreasing function of time, and the others are constant. We analyze the effect of different parameters like the initial temperature, thermal capacitance and the maximum rated speed on the nature and the cost of the optimum solution. We also propose a two-speed solution that approximates the optimal speed curve. This solution was found to achieve a performance close to that of the optimum, and is also easier to implement in real processors.

The dynamic voltage and frequency scaling technique in CPUs is an example of adjusting a device's control variable to trade off power consumption and performance. This idea of energy optimization through speed control has been subsequently applied to other components of electronic systems such as disk drives and wireless transceivers. In this paper, the energy-optimal speed profile (a function of time) of a generic device that has to execute a given task in a given time is obtained analytically. The proposed approach is applicable to devices with either discrete or continuous-speed sets. The main novelty of the approach is that for discrete-speed sets, the nature of the underlying continuous power-speed relationship does not need to be known. The discrete power-speed data points only need to satisfy a W-convex relation: a discrete analog of a convex function. Based on the observation that most devices have W-convex power-speed relations, it is shown that the optimal speed profile uses at most one speed (for continuous speeds) or two speeds (for discrete-speed sets). Furthermore, each device has an intrinsic speed (independent of the task) ucat which it consumes the least energy per unit work done. It is shown that this speed can be calculated directly from measured values of power-speed data points (for discrete-speed sets) or by an experimental line search procedure where each step involves measuring a power-speed data point (for continuous-speed sets). In either case, no curve fit or knowledge of analytical power models is required. The optimum speed profile was shown to be either ucor the minimum feasible speed(s) for the given task, with the choice depending on the energy overheads and task parameters

It has been recently pointed out that cyclic circuits are not necessarily sequential, and cyclic topologies that are combinational generally have lower literal counts than their acyclic counterparts. However, the synthesis of cyclic combinational circuits is potentially expensive due to the need to explore a wide range of cyclic topologies and check each of them for combinationality. We first obtain the acyclic implementation of the given set of boolean functions. Then using a branch-and-bound heuristic, we generate cyclic circuits that are to be checked for combinationality. Unlike earlier complex methods for combinationality check, our approach is to check whether this cyclic circuit is functionally equivalent to the acyclic circuit obtained earlier. While synthesizing cyclic circuits with the proposed method, we observed up to 45%. improvements in the literal count (for Espresso and LGsynth93 benchmarks) over the acyclic circuit synthesized by the Berkeley sis package.

We obtain analytically, the energy optimal speed profile of a generic multi-speed device with a discrete set of speeds, to execute a given task within a given time. Current implementations of energy efficient speed control policies (including DVFS) almost exclusively use the minimum feasible speed pair, which has been shown before to be suboptimal. Unlike previous works, ours does not require an explicit functional relationship between the device's power and speed (e.g. the CMOS power model), but only assumes that the power-speed relationship is a W-convex (a discrete equivalent of a convex) function. This assumption allowed us to show that the optimal speed profile uses at most two speeds, and that all the essential characteristics of the power-speed relationship can be encapsulated within a single speed, /spl omega//sub u/. The latter speed is intrinsic to the device (i.e. task independent) and can be readily computed from its power-speed values (without any curve fit). Further, /spl omega//sub u/ is also the speed at which the device consumes the least energy per unit work done. The problem formulation reduces to a linear program in the number of supported speeds, which in general, is difficult to solve analytically. However, the optimum solution has a very simple form - it is either /spl omega//sub u/, or the minimum feasible speed pair for the given task. We verified that a number of commercial DVFS processors, and other devices like disk drives satisfied our model of the W-convex power-speed relationship.

Batteries are non-ideal energy sources - minimizing the energy consumption of a battery-powered system is not equivalent to maximizing its battery life. We propose an alternative interpretation of a previously proposed battery model, which indicates that the deviation from ideal behavior is due to the buildup of "unavailable charge" during the discharge process. Previously, battery-aware task scheduling algorithms and power management policies have been developed, which try to reduce the unavailable charge at the end of a given workload. However, they do not account for the occurrence of rest periods (user enforced, naturally occurring, or due to finite load horizon), which are present in a variety of workloads. We first obtain an analytical bound on the recovery time of a battery as a function of the extent of recovery. Then, we shown that the effect of the rest periods is to reduce the improvement of battery-charge optimizing techniques over traditional energy-optimizing techniques. Under certain conditions, the policy that only minimizes energy consumption can actually achieve a longer battery lifetime than a battery-aware policy. A formal criterion based on the recovery time is proposed to choose between a candidate battery-aware policy and a candidate energy-aware policy. We also model the battery discharge process as a linear time invariant system and obtain the frequency response of a battery. This is then used to study the effect of task granularity on the improvement achieved by battery-aware task scheduling. It was observed that the response time of typical batteries are of the order of seconds to several minutes. This, along with the charge recovery effect, was seen to cause battery-aware task scheduling methods to become ineffective for both very fine-grained (less than 10 ms) and very coarse-grained (greater than 30 mm) task granularities.

Earlier techniques for low power speed control in disk drives running audio/video applications attempted to either match the drive's speed to the data rate requirement of the host application (just-in-time speed), or run it at the maximum drive speed, neither of which are energy-optimal in general. Starting from the theory of DC motors, we obtain a high-level power model of a disk drive. We then analytically obtain the speed profile (function of time) that minimizes the energy required to transfer a given amount of data from/to the drive, in a given amount of time. Based on a power model obtained by measurement from a commercial optical drive, it is estimated that the proposed speed control technique consumes 79\%, 70\% and 50\% less energy for VCD, SVCD and DVD video playback, respectively, when compared to existing just-in-time CLV techniques. This work also provides an analytical framework to understand earlier observations that buffering multimedia data and employing CAV mode in disk drives is more energy-efficient.

Many applications running on today's portable devices use multiple power-consuming devices simultaneously, often in the form of a dataflow chain which involves transfer of data between devices through buffers. Some of these devices have the ability to scale their performance and power simultaneously by tuning one of their parameters (generically called the device speed). We address the problem of minimizing the energy consumed by a two-device data flow chain by choosing the speed profiles of the two devices and the "cycle time" of the intermediate buffer. Determining the speed profiles (functions of time) to minimize the energy functional, in general, requires variational techniques. However, based on certain observations about device power-speed relations and application performance constraints, we were able to solve the problem analytically in two steps - device characterization and cycle time optimization. The effectiveness of the technique was demonstrated for two practical applications of dataflow chains - CD recording and VCD playback with up to 45% and 64% energy improvements, respectively.

We present Synchroscalar, a tile-based architecture for embedded processing that is designed to provide the flexibility of DSPs while approaching the power efficiency of ASICs. We achieve this goal by providing high parallelism and voltage scaling while minimizing control and communication costs. Specifically, Synchroscalar uses columns of processor tiles organized into statically-assigned frequency-voltage domains to minimize power consumption. Furthermore, while columns use SIMD control to minimize overhead, data-dependent computations can be supported by extremely flexible statically-scheduled communication between columns. We provide a detailed evaluation of Synchroscalar including SPICE simulation, wire and device models, synthesis of key components, cycle-level simulation, and compiler- and hand-optimized signal processing applications. We find that the goal of meeting, not exceeding, performance targets with data-parallel applications leads to designs that depart significantly from our intuitions derived from general-purpose microprocessor design. In particular, synchronous design and substantial global interconnect are desirable in the low-frequency, low-power domain. This global interconnect supports parallelization and reduces processor idle time, which are critical to energy efficient implementations of high bandwidth signal processing. Overall, Synchroscalar provides programmability while achieving power efficiencies within 8-30/spl times/ of known ASIC implementations, which is 10-60/spl times/ better than conventional DSPs. In addition, frequency-voltage scaling in Synchroscalar provides between 3-32% power savings in our application suite.

We consider the problem of scheduling multiple identical batteries for discharge in portable electronic systems. Unlike previous work reporting some experimental data to suggest which scheduling schemes are better than others, we arrive at our general conclusions formally, based on the analysis of an accurate high-level model of battery behavior. Our analytical results show that: (1) the lifetime of a parallel discharge schedule is equal to that of an equivalent monolithic battery, (2) the lifetime of a parallel discharge schedule is no less than that of a sequential discharge schedule, and (3) the lifetime of a switched discharge schedule approaches that of an equivalent monolithic battery as the switching frequency increases. We also derive bounds on the lifetime of a single battery under a constant-rate load, and then extend them to multiple battery systems. Using a low-level battery simulator, we verify our analytical findings with numerical data. For the simulated cases, the parallel discharge schedule resulted in up to 72% higher lifetimes than the sequential discharge schedule but fell short of the lifetime upper bound by up to 29%.