Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Digital Circuit Design: Problem

Circuit Design > Design problem | Next

  • Circuit topology

  • Design variables

  • Design objective

Circuit Topology

The combinational circuit consists of n connected gates, with primary inputs and outputs. We assume that there are no loops in the corresponding graph. For each gate, we can define the fan-in, or set of predecessors of the gate in the circuit graph, and the fan-out, which is its set of successors.

alt text 

Circuit topology: A digital circuit that consists of several ‘‘gates’’ (logical blocks with a few inputs and one output) connecting primary inputs, labeled 8,9,10, to primary outputs, labeled 11,12. Each gate is represented by a symbol that specifies its type; for example, the gates labelled 1,3 and 6 are inverters. For this circuit, the fan-in and fan-out of gate 2 is

mbox{FI}(2) = {8,9,10}, ;; mbox{FO}(2) = {4,5}.

By definition, the primary inputs have empty fan-in, and the primary outputs have empty fan-out.

Design Variables

The design variables in our models are the scale factors, which we denote by x_i, i=1,ldots,n, which roughly determine the size of each gate. These scale factors satisfy x_ige 1, i=1,ldots,n, where x_i = 1 corresponds to a minimum-sized gate, while a scale factor x_i = 16 corresponds to the case when all the devices in the gate have 16 times the widths of those in the minimum-sized gate.

The scale factors determine the size, and various electrical characteristics, such as resistance and conductance, of the gates. These relationship can be well approximated as follows:

  • The area of gate i is proportional to the scale factor x_i: A_i(x) = a_i x_i, with a_i >0. (So, you can simply think of the scale factors as the areas.)

  • The intrinsic capacitance of gate i is of the form

C_i^{rm intr}(x) = C^{rm intr}_i x_i,

with c_i>0 positive coefficients.

  • The load capacitance of gate i is a linear function of the scale factors of the gates in the fan-out of gate i:

C_i(x) = sum_{j in mbox{small FO}(i)} C_j^{rm in} x_j,

where C_j^{rm in}>0 are positive coefficients.

  • Each gate has a resistance that is inversely proportional to the scale factor (the larger the gate, the more current can pass through it):

R_i(x) = r_i / x_i ,

with r_i >0 positive coefficients.

  • The gate delay is a measure of how fast the gate implements the logical operation it is supposed to perform; this delay can be approximated as

D_i(x) approx 0.7R_i(x) (C_i^{rm intr} + C_i(x)) .

We observe that all the above parameters are actually posynomials in the (positive) design vector x.

Design Objective

A possible design objective is to minimize the total delay D for the circuit. We can express the total delay as

D = max_{1 le i le n} : T_i,

where T_i represents the latest time at which the output of gate i can transition, assuming that the primary inputs signals transition at t=0. (That is, T_i is the maximum delay over all paths that start at primary input and end at gate i.) We can express T_i via the recursion

T_i = max_{j in mbox{small FI(i)}} : (T_j + D_i).

The operations involved in the computation of D involve only addition and point-wise maximum. Since each D_i is a posynomial in x, we can express the total delay as a generalized posynomial in x.

alt text 

Recursion for the total delay: For the circuit on the left, the total delay D can be expressed as

begin{array}{rcl} T_i&=&D_i, ;; i=1,2,3, T_4&=& max(T_1,T_2) + D_4, T_5&=&max(T_2,T3)+D_5 T_6&=&T_4+D_6, T_7&=&max(T_3,T_4,T_5) + D_7, D&=&max(T_6,T_7). end{array}