Module binding interconnection

Page 1

Digital Systems Design Methodologies 1 Module Binding and Interconnection 1 Exercise 1 Given the following FSM: and assuming that the register binding has been already solved giving the following regis- ter assignment: tmp2: R1 tmp5: R2 Compute the solution of the module binding problem for the adders. Note that input parameters a,b use dedicated ports. 2 SOLUTION Let’s build the compatibility graph considering all the variables: Let’s add to the directed light blue edges representing chaining: In this case, the green path temp4 - temp1 - temp2 - temp3 - temp4 is a cycle. N.B. In case of multiple cycles, we have to consider firstly the smallest cycle, i.e. the one having the smallest number of undirected edges. We have to break the cycle, removing one of the 2 compatibilities described by the com- patibility graph. We have thus to remove an edge between temp4-temp1 and temp3-temp2. There are three metrics that have to be used in order to decide which edge to brake: 1. Absolute difference of levels: We have firstly to compute the level of each vertex. In order to assign a level, we have to consider only directed edges and, starting from the first node of the chain, we have to increase the level. 3 N.B. The level is NOT the number of incoming directed edges in a vertex. We have: Edge Levels Delta Levels temp1 - temp4 1 - 0 1 temp2 - temp3 1 - 0 1 Since the differences of levels are equal, we should use the metric based on the degree in order to choose which edge to brake. 2. Sum of degrees: In order to find the degree, we have to find the number of undirected edges for each vertex and summing those values for both the vertices of the compatibility edges. We have: Edge Degrees Degrees Sum temp1 - temp4 1 - 1 2 temp2 - temp3 3 - 2 5 3. Minimum weight: Since the two edges have…