VLSI CAD - Spring 2008

Programming Assignment #2: Static Timing Analysis

Problem Description

In this programming assignment, your task is to write a program that reads a directed weighted hypergraph as input, and finds the longest delay from input nodes to output nodes. The hypergraph represents a combinational circuit (gates represented as nodes, wires as hyperedges). An input node is one with no incoming edges (I use edge and hyperedge interchangably here). And output node is one with no outgoing edges. The delay at the output of a gate is defined as the time its latest input arrives, plus its delay. The delay of an input is the delay of the driving (source) gate, plus the delay of the wire.

A number of benchmarks are provided to test your program. You can post your answer for circuits a.in, cordic.in to the gmail group page to facilitate discussion and weed out possible bugs in your program. Below is a description of the hypergraph input file format.

Program Parameters and the Input Format

You should electronically submit the program in one zip file containing all source and header files. The name of the file should be yourFirstName_yourLastName.zip (or .rar, or .tgz or .gz.tar). The only command-line parameters of the program are the name of the input file that describes the graph. The input file extension is '.in' (an example of the input file name is "a.in") and the extension will always be used. The output file name should be your name, followed by the input file name, followed by '.out' (e.g., "Mahmoud_Ahmadinejad_cordic.out").

The input file format is the same as programming assignment #1.

The output file format (ASCII, not binary) should be as follows:

• Max delay among all nodes rounded to two fractional digits. Show exactly two fractional digits (e.g., 24.30)
• A line starting with an integer indicating the number of input pins, and then the index of input pins. Each input pin index is preceded with one space character.
• A line starting with an integer indicating the number of output pins, and the list of output pins.
• V lines (ending with "\n"), each containing:
  • NodeID (in ascending order).
  • Longest delay from any of the input nodes to NodeID rounded to two fractional digits. Show exactly two fractioinal digits. Use -1.00 if there are no paths from source to NodeID.
  • The slack of the node. The slack is defined as the difference between the arrival time and required time at the output of a node. The minimum slack is zero. Use exactly two fractional digits (e.g., 0.00) for all slack values.

Benchmarks

Test input #1: a.in.

Test input #2: cordic.in

(more input files can be downloaded here: cktInFmt.zip)

Submission Process

You will be submitting your program electronically.

1. Make sure you submit the latest version of your code.
2. Your program should compile either on a Unix platform (with gcc), or on Windows (Microsoft Visual C compiler).
3. You will be submitting only a single file called yourFirstName_yourLastName.zip. No executables or input / output data please.
4. Submit a table which lists all benchmark circuits, along with the maximum delay of the circuit (i.e., the delay of the node with the maximum delay from any input node).

Grading

• Submission: 10%
• Compilation: 15%
• Correct output for test data a.in: 15%
• Correct output for test data b.in: 15%
• Other test cases: 45%