Intellectual property metering(3)

Abstract. We have developed the first hardware and software (intellectual property) metering scheme that enables reliable low overhead proofs for the number of manufactured parts and copied programs. The key idea is to make each design slightly different d

that all operations take one control step. The critical path is six control steps long. We schedule the filter, in the minimum amount of hardware resources using only 1 adder and 1 multiplier. The graph in Figure 2 shows the same filter after being restructured following the schedule. The same graph also has information about the used variables which are denoted by (v1, v2,..., v11).

A variable is alive during its lifetime, i.e. between the time it is generated (written)and the last use (read) of it. The variables whose lifetime do not overlap can be stored in the same register. Figure 3 shows the interval graph that contains information about life-times of all variables for the filter. The standard way of variable assignment to registers is to model it using the graph coloring problem [6, 36]. The interval graph is constructed in such a way that for each variable, there is a corresponding node in the graph. Two nodes are connected if the lifetime of the corresponding variables overlap. Now, register assign-ment can be performed by coloring the interval graph, which is an NP-complete task for cyclic interval graphs [16,21].

The instance of the graph-coloring problem that corresponds to register assignment of the filter is shown in Figure 6 (considering only the solid lines). Assigning two variables to the same registers corresponds to coloring two nodes with the same color. One potential assignment is also shown in Figure 6. Finally, Figures 4 and 5 show the corresponding datapath and a path of control unit (FSM) that contains read/write operations to the regis-ter. Figure 5 shows read control of the register files that is used to store variables. The key point is that although we can obtain many different solutions (which we discuss in the next paragraphs) by coloring the graph in different ways, our datapath remains the same for

+

D2

+

D1

+

++

c1

c2

c3c4

c6

c5

IN

OUT

Figure 1. 2nd order continued fraction IIR [CFIIR] filter

1 2345

6

OUT D1D2

Figure 2. Scheduled CFIIR filter