Reference no: EM131299858

You are given a number of logic blocks B₁, B₂, ..., B_n where each block has three choices for Vdd, each will give different power and delay.  For example, the three choices for B₁ are: high Vdd  ( and delay = 5ns), medium Vdd ( and delay = 7ns), or low Vdd (power = 8mW and delay = 10ns). When we combine two or more blocks, the delay is the maximum of the block delays, and the power is the sum of the block powers.

Write a program using any script language to read an input of CSV file of the following format:

Block,Power,Delay

B1,12,5

B1,10,7

B1,8,10

B2,8,9

Then compute the possible choices for combine all blocks, excluding redundant choices (a choice is redundant if there is another choice with less power and less delay).  Try to make the algorithm run reasonably fast.

• And if we further require at most 10% of the blocks can use high Vdd. Is the problem NP-Complete?  Write an algorithm (don't have to implement) to solve the problem or approximate the problem.