Tuesday, September 29, 2009

Dynamic Programming

Dynamic Programming Practice Problems

CODE
1. Maximum Value Contiguous Subsequence
NOTE: This algorithm skip the special case that all values are negative in the array.












2. Longest Increasing Subsequence
3. Integer Knapsack Problem (multiple copies)
4. Integer 0/1 Knapsack Problem
See ~/Algorithm/Dynamic_Programming/dp/dp.cpp

Wednesday, August 26, 2009

Interview - VLSI Verilog Part 1

1) Design a RAM using Verilog.

Interview - VLSI Perl Part 1

1) What is a 'Package' in Perl?
'Package' declares the compilation unit as being in the given namespace. It provides a mechanism for alternative namespaces to protect packages from stomping on each other's variables.

Monday, August 24, 2009

Interview - VLSI Design Part 2

1) Explain why & how a MOSFET works.
MOSFET: metal-oxide-semiconductor field-effect transistor. The MOSFET is a four-terminal device. The voltage applied to the gate terminal determines if and how much current flows between the source and the drain ports. Then explain the resistive region, saturation region and velocity saturation.

2) Draw Vds-Ids curve for a MOSFET. Show the curves with (a) increasing Vgs (b) increasing transistor width (c) Channel Length Modulation.
In the resistive region, the transistor behaves like a voltage-controlled resistor, while in the saturation region, it acts as a voltage-controlled current source (when the channel length modulation effect is ignored).

3) Explain the various MOSFET capacitances
The MOSFET capacitances include overlap capacitance (lateral diffusion), gate-to-channel capacitance (varies in three different regions) and junction capacitance (bottom-plate and side-wall junction).

4) Draw a CMOS Inverter. Explain its static and dynamic behavior.
static behavior:
  • Voltage Transfer Characteristic (VTC): narrow transient region, high gain during the switching transition.
  • switching threshold: defined as the point where Vin = Vout. We can balance the relative driving strengths of the PMOS and NMOS transistors to obtain symmetrical characteristics and maximize the noise margins. It's relatively insensitivetive to variations in the device ratio.
  • noise margin: channel length modulation can not be ignored. A high gain in the transition region is desirable for larger noise margin.
dynamic behavior: the propagation delay of the CMOS inverter is determined by the time it takes to charge and discharge the load capacitance through the PMOS and NMOS transistors, respectively.
  • load capacitances: gate-to-drain capacitance, diffusion capacitance, wiring capacitance, fanout capacitance.
  • propagation delay: sizing the inverter properly to obtain a symmetrical VTC and to equate the high-to-low and low-to-high propagation delays. To deduce the propagation delay: 1) Reduce load capacitances; 2) Increase the W/L ratio of the transistors, when the external load is dominant; 3) Increase VDD to trade off energy dissipation for performance; 4) The Smaller PMOS devices yield a faster design at the expense of symmetry and noise margin.
6) What is Noise Margin? Explain the procedure to determine Noise Margin.
Use a piece-wise linear approximation for the VTC. The transition region is approximated by a straight line, the gain of which equals the gain at the switching threshold.

7) Given the expression for CMOS switching power dissipation.

8) What is Body Effect?
The body effect describes the changes in the threshold voltage by the change in the substrate bias voltage between source and body.

9) Describe the various effects of scaling?

10) What is Latchup? Explain Latchup with cross section of a CMOS inverter. How do you avoid Latch Up?
Latchup is the inadvertent creation of a low-resistance path between VDD and GND, causing catastrophic meltdown. The cross-coupled transistors form a bistable silicon-controlled rectifier (SCR). Latchup will be triggered when transient currents flow through the substrate, which causes Vsub to rise.
Prevention:
  • A layer of insulating oxide (trench) surrounds both the NMOS and PMOS transistors, which breaks the parasitic SCR structure between these transistors.
  • Use a thin expitaxial layer of lightly doped silicon on top of a heavily doped substrate that offers a low substrate resistance (minimize Rsub and Rwell).
  • Place substrate and well traps close to each transistor. nMOS should be clustered together near GND and pMOS should be clustered together near VDD.
  • SOI devices are inherently latchup-resistant.

Interview - VLSI Design Part 1

Question: what is the difference between Mealy and Moore state machines?

The Moore state machine uses only only entry actions, i.e., output depends only on the previous state. It may has more states and synchronous outputs. The Mealy state machine uses only input actions, i.e., output depends on input and previous state. It may has fewer states and asynchronous outputs. The ouput timing behavior is different. The output of Moore machine has one cycle "delay", whereas the output of Mealy machine is immediately available.

Question: How to solve setup and hold violations in the design?

Setup Time is the amount of time the synchronous input must be stable before the active edge of the clock. Hold Time is the amount of time the synchronous input must be stable after the active edge of the clock.

During the initial iterations only setup violations are fixed whereas hold violations are fixed only after the actual physical place and route information is available. Setup and hold violations are mutually exclusive. Setup violations can be fixed by reducing the combo delay (minimizing the logic level). Hold violations are fixed by increasing the combo delay or by inserting buffers such that it does not cause the setup violations. Increasing or decreasing delays by upsizing or downsizing the cells ripples back into the design and the whole design is to be taken into consideration for carrying out the STA again.

Question: how can you reduce dynamic power?
  • Reduce switching activity by designing good RTL.
  • Clock gating [Reference] (De-activate the clocks for functions that are not required)
  • Architectural improvements
  • Reduce supply voltage
  • Use multi Vdd
Question: What is cross talk?

Switching of the signal in one net can interfere neighboring net due to cross coupling capacitance. Cross talk may lead setup or hold violation.

Question: what are High-Vt and Low-Vt cells?