a sequence of n arrival times t0 t1 tn-1 a

Question

A sequence of n arrival times t₀, t₁, ..., t_n-1, . a library of mlogically equivalent gates {(d₀, c₀), (d₁, c₁), ..., (d_m-1,c_m-1)} where d is delay and c is cost. a maximum allowable arrival time at the output of the tree tmax

Objective: Construct a legal tree of gates which minimizes the total cost of the tree subject to the constraint that the arrival time at the output is no greater than tmax. Use dynamic programming to solve this

Problem:

Signal i arrives at its input pin at time t_i.  The arrival time at the output of a gate g with inputs x and y is determined by:

t_g = max (t_x, t_y) + d_g

where t_x and t_y are the arrival times of inputs x and y respectively and d_g is the delay through the gate.

The figures below give two trees for the given input.  The input pins are at the left of the diagrams and are labeled with their arrival times.  The two configurations

Allowable Trees

Because of the given ordering of the inputs, we will not allow just any tree structure; the trees must be "consistent" with the input pin ordering:

The leaves (inputs) of every subtree must be a consecutive subsequence of length two or more from the given pin ordering.

The tree in the diagram below violates this rule.

Don't worry, this is good news for you:  it makes the problem more tractable.

Given:  

? A sequence of n arrival times t₀, t₁, .........t_n-1,

? a library of m logically equivalent gates { (d₀,c₀), (d₁, c₁),..........(d_m-1, c_m-1)}

? a maximum allowable arrival time at the output of the tree t_max

Objective:  Construct a legal tree of gates which minimizes the total cost of the tree subject to the constraint that the arrival time at the output is no greater than t_max.

Formats

Pin Arrival Times and Ordering:  The first file format specifies the signal arrival times in sequence.  The inputs are implicitly labeled t₀, t₁, .........t_n-1.  The file is as simple as can be: 

? the first line specifies the number of input pins n;

? this is followed by n lines containing t₀.........t_n-1 as floating point numbers.

The problem instance used in the preceding diagrams would look like this:

6 6.0 3.0 4.0 7.0 2.0 3.0

 

Gate Library:  A gate library is specified in a file organized as follows:

? The first line is the integer m -- the number of gates in the library.

? This is followed by m lines, describing gates 0..m-1.  each line contains two positive floating point numbers (in this order).

? the delay -- a floating point number

? the cost -- an integer

? The ordering of the gates implicitly determines their IDs -- 0..m-1

? The gates are ordered in decreasing order of delay and increasing order of cost:  slowest/cheapest gate first.

For example, a library with three gates might look like this:

3 5.0 1 4.5 1 3.5 3

Topology Format:  postfix notation

A solution is a binary tree in which the leaves are labeled

b0, b1, ...

Each internal node represents a gate and is labeled:

gX

where X is the gate ID from the library (or simply 0 if there is only one such gate).

The structure of the tree itself is specified in postfix notation on a single line. Think of the gates as operators and as the inputs as operands.

The topology from the first figure would be specified as:

b0 b1 b2 g0 b3 b4 b5 g0 g0 g0 g0

Your program will use this format when reporting an optimal configuration.

Usage

Your program should run from the command line as follows:

% gtree {} {-t }

The pin file is required.

If no library file is specified, the default library is just a single gate with unit delay and unit cost.

If no maximum arrival time tmax is specified, the program should minimize the arrival time.

For example the following would run the program on a pin file test1 using gate library lib1 with timing constraint 10.0

% gtree test1 lib1 -t 10.0

Your program will then print a report to the terminal containing the following:

? Whether a feasible solution exists or not

? If a solution exists:

?     The arrival time of the solution

?     The cost

?     The topology in postfix notation

Assumptions:  For this assignment, you may assume the following:

? Input files are well-formatted

? The command line arguments are in exactly the order specified above.