Adaptive Techniques for Dynamic Processor Optimization_Theory and Practice Episode 2 Part 4 pps

Chapter 9 Variability-Aware Frequency Scaling in Multi-Clock Processors 211

0.00

0.01

0.02

0.03

0.04

0.05

0.06

0.07

0.08

-3 -2 -1 0 1 2 3 4

fΔTWID(t)

ΔTWID, standard deviations

Ncp = 1

Ncp = 2

Ncp = 10

Figure 9.2 Delay distributions for Ncp = (1, 2, 10).

Unfortunately, determining the number of independent critical paths in a

given circuit in order to quantify this effect is not trivial. Correlations

between critical path delays occur due to inherent spatial correlations in

parameter variations and the overlap of critical paths that pass through one

or more of the same gates. To overcome this problem, Ncp is redefined to

be the effective number of independent critical paths that, when inserted

into Equation (9.2), will yield a worst-case delay distribution that matches

the statistics of the actual worst-case delay distribution of the circuit.

The proposed methodology estimates the effective number of

independent critical paths for the two kinds of circuits that occur most

frequently in processor microarchitectures: combinational logic and array

structures. This corresponds roughly to the categorization of functional

blocks as being either logic or SRAM dominated by Humenay et al. [9].

This methodology improves on the assumptions about the distribution of

critical paths that have been made in previous studies. For example,

Marculescu and Talpes assumed 100 total independent critical paths in a

microprocessor and distributed them among blocks proportionally to

device count [12], while Humenay et al. assumed that logic stages have

only a single critical path and that an array structure has a number of

critical paths equal to the product of the number of wordlines and number

of bitlines [9]. Liang and Brooks make a similar assumption for register

file SRAMs [11]. The proposed model also has the advantage of capturing

the effects of “almost-critical” paths which would not be critical under

nominal conditions, but are sufficiently close that they could become a

212 Sebastian Herbert, Diana Marculescu

block’s slowest path in the face of variations. The model results presented

here assume a 3σ of 20% for channel length [2] and wire segment

resistance/capacitance.

9.2.2 Combinational Logic Variability Modeling

Determining the effective number of critical paths for combinational logic

is fairly straightforward. Following the generic critical path model [2], the

SIS environment is used to map uncommitted logic to a technology library

of two-input NAND gates with a maximum fan-out of three. Gate delays

are assumed to be independent normal random variables with mean equal

to the nominal delay of the gate dnom and standard deviation L L nom σ μ ×d .

Monte Carlo sampling is used to obtain the worst-case delay distribution

for a given circuit, and then moment matching determines the value of Ncp

that will cause the mean of analytical distribution from Equation (9.2) to

equal that obtained via Monte Carlo.

This methodology was evaluated over a range of circuits in the

ISCAS'85 benchmark suite and the obtained effective critical path numbers

yielded distributions that were reasonably close to the actual worst-case

delay distributions, as seen in Table 9.1. Note that the difference in the

means of the two distributions will always be zero since they are explicitly

matched. The error in the standard deviation can be as high as 25%, which

is in line with the errors observed by Bowman et al. [3]. However, it is

much lower when considering the combined effect of WID and D2D

variations. Bowman et al. note that the variance in delay due to within-die

variations is unimportant since it decreases with increasing Ncp and is

dominated by the variance in delay due to die-to-die variations, which is

independent of Ncp [2]. The error in standard deviation in the face of both

WID and D2D variations is shown in the rightmost column of the table,

illustrating this effect. Moreover, analysis of these results and others shows

that most of the critical paths in a microprocessor lie in array structures

due to their large size and regularity [9]. Thus, the error in the standard

deviation for combinational logic circuits is inconsequential.

Such Ncp results can be used to assign critical path numbers to the

functional units. Pipelining typically causes the number of critical paths in

a circuit to be multiplied by the number of pipeline stages, as each critical

path in the original implementation will now be critical in each of the

stages. Thus, the impact of pipelining can be estimated by multiplying the

functional unit critical path counts by their respective pipeline depths.