BITS - PILANI K.K. BIRLA GOA CAMPUS First Semester 2011-2012 CS G553-Reconfigurable Computing Component: Regular (Closed Book) Duration: 1 hour Test-I Max. Mark: 20 Qi. A simple datapath component shown in figure that could add/subtract two 8-bit binary numbers and produce 8-bit result (ignore carry/overflow in and out). The datapath uses DIP switches for inputs and LEDs for Output. A single DIP switch input that sets signal f (for function), When f=0, the datapath should add; when f=1, the datapath should subtract. Whenever an ‘output is required from the datapath, control input e is made high (this is supplied through a push button switch). Write the corresponding verilog modules of the components. Also write a verilog top module using this modules to implement this datapath in a FPGA (use the given verilog templates in your design and). 15] DIP switches Woop q oBUmuuuUL! jiu S-bit adder 2amux register with parallel load | Top Module module add( | module mux{ jodularagissl module dp_top( input [7:0] a, input [7:0] st, input [7:0] y, input [7:0] a, input [7:0] b, input [7:0] s2, Inpute, input (7:0] b, output{7:0]s1 | input f, input clk; input f, % output 70) y output regi7:0] leds inpute, input clk, H hi output [7:0] leds h endmodule &-bit subtractor ‘module subj input (7:0] a, input [7:0] b, output [7:0] s2 k endmodule endmodule end module endmoduleQ2. Show how to implement on two 3-input 2-output lookup tables the following function: F(a,b,c,d) =@bd+Bed . Assume the two lookup tables are connected in the manner shown in figure. You may not need to use every lookup table. Show the steps clearly without overwriting. 8x2 Mem. dl do Q3. The logic element shown in figure is used in an antifuse based FPGA. Should the LE be made of static gates or pass transistors? Justify your answer with proper circuit diagram. [6] ML a Q4. Discuss briefly about full and partial reconfiguration process, full and partial reconfiguration devices. [2] Q5. What are called "Sea of gates” FPGAs? Give an example. (11BITS - PILANI K.K. BIRLA GOA CAMPUS First Semester 2011-2012 CS G553-Reconfigurable Computing Component: Regular (Closed Book) Duration: 1 hour Test-IL Max. Marks: 20 Qi. The two level combinatorial part of a digital system as shown in Figure 1 is to be implemented on a FPGA. The library elements are look-up tables (LUT) with 5 inputs and one output. Each LUT delay is 3 ns. [6] (a) Compute the achievable clock rate of the resulting FPGA implementation when applying the chortle-crf LUT-technology mapping algorithm. [explain each step in detail] (b) Find an aiternative solution so to obtain a higher clock rate. at Figure 1: Combinational part of the digital circuit Q2. Build 2 BDD forf = abe + abc + abe + abe; - Use the variable ordering a < b < c, obtain 1, OBDD 2. ROBDD [show all the required steps] [6] Q3. Consider the sequence graph in Figure 2. Assume that there Is only one resource type which can compute all operations (+, -, <, x) and has an area of 1. One unit of this resource type is allocated. The cost of an implementation is given by the total required area. All the operations have the same execution time: D, = D. =D. =D.=1Figure 2 a) Set up a system of inequations which represent the constraints to valid schedules. b) Set up an optimization model for the optimization of the latency L. (Hint: give an objective function to the system of inequations). c) What is the minimal achievable latency for I. The resource constraints from task 1 Il, Unlimited resources Indicate valid starting times for the operations in both cases and check the validity of the schedules by means of the system of inequations determined previously. [6] Q4. What are the fundamental differences between spatial partitioning and temporal partitioning for RCS? [2]BITS ~ PILANI K.K. BIRLA GOA CAMPUS First Semester 2011-2012 CS G553-Reconfigurable Computing Component: Regular (Closed Book) Duration: 3 hours Comprehensive Examination Max. Marks: 70 Instructions: over written answers will not be evaluated. Make necessary assumption and justify the same wherever required. Qi. Write short answers for the following parts [10] Suppose you are trying to choose between the Actel ACT 1 family and the xilinx 4000 family. What types of designs would be best suited for each of these families of devices, and why? b, What is the use of Altera FLEX family’s “carry chain”? . What are multi context FPGAs? Discuss their operation, advantages and disadvantages. d. What do you mean by post synthesis simulation? Why it is required? €. The logic network shown in figure is simulated in an event driven simulator: a i] the lf o List the evaluations of logic elements in the order in which they happen, assuming that the inputs are changed in the following order @) aid (li) aje;d Q2. Consider the design of a 2-input FPGA lookup table (LUT). An abstracted view of the 2-LUT Is shown in figure, The ports, a, b, and y, are the data inputs and output, respectively. The input CIN stands for “configuration input", and CLK stands for “configuration clock", 2-LUT y ‘The configuration clock is used at FPGA initialization time to shift in : the LUT contents, one bit per clock cycle, over the CIN port. CIN CCLK @. Draw a circuit diagram for the internal implementation of the 2-LUT, including configuration loading. Use only the following circuit components: Inverter, 2-input AND, 2- input OR, Flip-Flops. Remember to label all inputs and outputs. b. Imagine now that the 2-LUT is programmed to implement the following function: a'b. Using your circuit diagram above, label the appropriate nodes in your circuit diagram with the correct configuration values. [05]Q3. Determine the mobility of each node in the sequencing graph below. Tabulate the mobility of each node. [05] Q4. Listed below are the headers from a set of Verilog modules followed by the structural description of a module called fib: module mux (INO, IN1, select, OUT) : // standard 32-bit wide multiplexor input [31:0] INO, IN1; input select; output [31:0] OUT; endmodule module register (D, clk, Q); // positive edge triggered register input [31:0] D; input clk; output [31:0] Q; endmodule “ module adder (A, B, R); // unsigned adder input [31:0] A, B; output [31:0] R:module fib (reset, clk, Y); //structural description input reset, cll output [31-0] Y: wire [31:0] A, B, C, D, E, F; assign E = 1; assign F = 0; mux m1 (Y, E, reset, A); mux m2 (B, F, reset, C); register r1 (A, clk, B); register r2 (C, clk, D); adder add (B, D, Y): endmodule a. Based on the structural description of fib draw its circuit diagram. Do not show the Internals of the submodules: b. Write a behavioral description for just the fib module. Your solution should have no instantiations of submodules. [10] module fib (reset, clk, Y); input reset, clk; output [31:0] Y; Q5. Consider the binding of a network implementing the conjunction of 10 variables. Assume that the available cells are only two-input AND gates with cost 2, three-input AND gates with cost 3 and four-input AND gates with cost 4. [15] a. Find an optimum cover of the tree decomposition of the network given below using 2- input AND gates as base functions: k=ab; m=ke; n= o=fg; q=mn; s=qr b. Is this the best implementation of the given network with the available cells? Is there decomposition into the same base function leading to a lower cost solution? ¢. Show all the partitions trees for the 4-input AND gate cell that need to be stored in the library assuming the use of 2-input AND gates as base functions. d. Show all the ROBDDs for the 4-input AND gate cell that need to be stored in the library for Boolean matching.ccume a device with an area of 75 units Is given. Let 2 multiplier require 25 area units and ‘N der/subtracter 10 area unit each. ~ Compute the connectivity of the data flow g _ partition the graph in a straightforward way, raph in Figure 46. then use List Scheduling to partition it. Compute the quality of the above partitioning. [07] SK WS Sk x) x) x (+ <7 f ‘ ; A 7 ies Figure q6: Data flow graph. ILP-based temporal partitioning: Formulate ILP constraints for the two partitions shown in Figure q7. b. Which of the two partitions fulfills the ILP constraints? [os] ) = S(2) = (8) = S(9) = $(10) = 10 Each edge has @ weight of 8. 3) = $(4) = 25 (Device) = 150 5) = S(6) = S(7) = 50 T(Device) = 30 11) = 75 12) = 80 2 * a i, C ' partitions 2 partitons 1 Figure q7: ILP partitioning example. jartitions shown in Figure q8.1 y8. For the placement of p rectangles (MER). Clearly draw a. Find all maximal empty and represent in your answer sheet b. Compute a partition of the free space Into a set of maximal but non-overlapping rectangles for the placement shown in Figure. Draw and show clearly Now, a new component M6 has to be placed on the device.G How many maximal empty rectangles will be generated if the component is placed as shown in Figure q8.2 using the approach of Bazargan? Is there any alternative to keeping overlapping free rectangles? - What are the advantages and disadvantages? What are the advantages and disadvantages of the Bazargan approach? [10] ot Figure q8.2: On-line placement of a new component