Report

Spring 2014 ECE 753 Hardware Implementation of Self-checking circuits on FPGA Project Team #1 Chandru Loganathan Sakshi Gupta Vignesh Chandrasekaran 1/28 8th May 2014 Structure of the Talk 1. Motivation and Introduction 2. Totally self-checking circuits and Reconfiguration logic 3. Less than or equal to checker 4. Non increasing sorting checker 5. Range checker 6. Residue checker 7. Future scope 2/28 Introduction • In a Totally Self-checking Circuit (TSC), if there is a fault in the inputs and/or within the TSC itself, the system no longer functions as desired. • If any of the input is faulty, then the TSC brings the complete system to halt. Having a reconfiguration logic can leverage that. • Reconfiguration logic allows the system to function properly in presence of at most two faults. • Motivation of this project is to make the most of the available hardware without having to compromise on the fault tolerance of the output. 3/28 Basic Definitions • A circuit is said to be fault secure if in the presence of a fault, the output is either always correct, or not a code word for valid input code words. • A circuit is said to be self-testing if only valid inputs can be used to test it for faults. • A circuit is said to be totally self-checking if it is both fault secure and self-testing. 4/28 Totally Self-checking Checker (TSC) A TSC has 4 inputs and 2 outputs Hence, 4 possible output combinations are possible (00, 11, 01, 10) Inputs 5/28 TSC 0 1 0 1 1 0 0 1 Valid Invalid Output code-words Totally Self-checking Checker (TSC) Two-rail checker 6/28 Totally Self-checking Checker (TSC) Multi-bit TSC x0[0] y0[0] x1[0] x0[1] y1[0] x1[1] y0[1] * y1[1] * x0[2] * * * * denotes a two-rail self-checker circuit 7/28 y0[2] f g x1[2] y1[2] Reconfiguration Logic When there is a fault in any one of the inputs or in the TSC itself, then the system halts. In order, to prolong system halt we introduce Reconfiguration Logic. If a non-code word (00 or 11) output is detected from the TSC, then the Reconfiguration Logic Enable (logic high) signal is triggered. Now, the reconfiguration logic identifies the faulty line and masks it. New x0, y0, x1, y1 values are computed and fed into a multiplexer. The multiplexer selects between the new values and old values of x0, y0, x1, y1 and outputs the final values of x0, y0, x1, y1. 8/28 Reconfiguration Logic Algorithm for Reconfiguration logic 9/28 10/28 denotes a 16-bit bus new_y1[15:0] new_x1[15:0] Reconfig_enable new_y0[15:0] new_x0[15:0] Multiplexer y1[15:0] x1[15:0] y0[15:0] x0[15:0] 16-bit TSC y1[15:0] x1[15:0] y0[15:0] x0[15:0] y1[15:0] x1[15:0] y0[15:0] x0[15:0] TSC with Reconfiguration Logic Block Diagram Reconfiguration Logic TSC with Reconfiguration Logic Analytical comparison Without reconfiguration logic With reconfiguration logic 11/28 Implementation Analysis 12/28 Checker Circuit Number of Sliced LUTs Number of LUT flip flop pairs used Worst case combinational delay (ns) TSC (1 bit) 2 2 4.494 TSC (16 bit) 49 49 12.555 Reconfiguration logic (16 bit) 32 32 4.678 TSC with reconfiguration logic (16 bit) 64 64 18.713 Non-increasing sorting checker • There are three types of errors encountered in sorting algorithm: – Functional error: Operands are incorrectly ordered – Data error: One or more bits of the operands are changed – Hybrid error: Where both functional and data errors occur simultaneously • LTOETC compares two consecutive non-negative numbers and checks if they are in correct order. 13/28 LTOETC • Suppose two non-negative numbers N1 and N2 are represented as x1,x2,…,xk and y1,y2,…,yk. • X1 = x2,…,xk and Y1 = y2,…,yk • Valid input code space: – x1y1 = 00 and X1 ≥ Y1 – x1y1 = 11 and X1 ≥ Y1 – x1y1 = 10 and X1 ≥ Y1 – x1y1 = 10 and X1 < Y1 Above code space denotes that N1 ≥ N2 and the output of LTOETC block must be a valid codeword. 14/28 LTOETC Block Diagram Reference: D.L. Tao, “A Self-Testing Non-increasing Order Checker”, IEEE Transactions on Computers, Vol. 46, No. 7, pp. 817-820, July 1997. 15/28 LTOETC Input code space x1 y1` (X1, Y1) 00 11 10 10 00 11 01 01 X1 ≥ Y1 X1 ≥ Y1 X1 ≥ Y1 X1 < Y1 X1 < Y1 X1 < Y1 X1 ≥ Y1 X1 < Y1 16/28 co1 co2 a11a12b11b12 c1c2c3c4 a21a22b21b22 a31a32b31b32 o1 o2 11 11 11 00 00 00 00 00 0110 0011 1100 1001 0011 0110 1001 1100 1000 0100 0001 0010 1010 0110 1100 1110 1100 1001 0011 0110 1110 1111 1101 1111 0110 1001 1100 0011 1101 0111 0111 1101 01 01 10 10 11 11 11 11 LTOETC Properties • LTOETC is code disjoint: – Different inputs follow different output routes. • LTOETC is self-testing: – Each functional block receives all necessary test vectors. Hence, it is fully tested during normal operation. – Fault in each functional block will be excited which therefore generates a noncode-word at o1o2 of LTOETC 17/28 Non-increasing sorting checker Block Diagram • Implemented a design which detects only functional errors in ordered set of inputs. • Considered 5 input numbers in order Reference: D.L. Tao, “A Self-Testing Non-increasing Order Checker”, IEEE Transactions on Computers, Vol. 46, No. 7, pp. 817-820, July 1997. 18/28 Non-increasing sorting checker Simulation • • 19/28 Inputs when in non-increasing order generate a valid code word Functional error in sorting order generates non-code word, i.e., o1o2 = 11 Range Checker Block Diagram • The checker circuit detects whether the input lies within a specified range. • Input out of bound generates a non-code word, i.e., o1o2 = 11 • Input within the range generates a valid code word 20/28 Range Checker Simulation • Input value for the first set of upper and lower range generates valid code word. • Input value when out of range for the second case generates non-code word. 21/28 Implementation Analysis 22/28 Checker Circuit Number of Sliced LUTs Number of LUT flip flop pairs used Worst case combinational delay (ns) Non-increasing sorting checker 70 70 8.636 Range checker 34 34 6.958 Residue Checker Based on the idea of computing the residue of a given function for a given modulo and comparing it against the residue obtained by computing the same function broken down by modulo arithmetic. Property 1: <X+Y>m = < <X>m + <Y>m >m Property 2: <X.Y>m = < <X>m * <Y>m >m Consider a multiple-accumulate (MAC) unit of a processor which computes the following function: Z = A*B+C 23/28 Residue Checker Block Diagram <Z >m = <A*B+C>m <Z’>m = <<<A>m*<B>m>m+<C>m>m Reference: S.Wei and K.Shimizu, “Error Detection of Arithmetic Circuits Using a Residue Checker with Signed-Digit Number System”, IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, pp. 72-77, Oct. 2001 24/28 Residue Checker Modulo Checker Modulo checkers can be implemented in several ways in hardware. 2n Modulo checker • Bit select the lower n bits of the applied input. • Hardware conservative. • Lesser combinational delay. General modulo checker • Residue for any value of modulo. • Demands more hardware compared to the earlier method. • Relatively slower clock rate. 25/28 Residue Checker Performance matrix • Hardware utilization for each of the implementation is different. • As the value of modulo increases, the hardware utilization increases. • Hardware utilization is the measure of the number of LUTs utilized on the FPGA. • Hardware complexity can be expressed as function of modulo. • Timing. 26/28 Residue Checker Hardware Complexity: 2n Modulo checker HC(m) = 4.2814ln(m) + 5.275 27/28 Residue Checker Hardware Complexity: General modulo checker HC(m) = 27.319ln(m) + 186.95 28/28 Residue Checker Mix of both designs • Multiplex both and choose according to Modulo. • This hybrid is ideally suited for various application. 29/28 Implementation details • Design was implemented on Xilinx Spartan 6 XUPV5LX110T FPGA • Synthesis was done with Xilinx ISE 14.7 • Simulation was done using ModelSim • Debugging was done using ChipScope Pro. 30/28 Future Scope Reconfiguration logic • Can be introduced in all hardware redundant circuits. • Can be scaled to every design. • Must be made fault secure 31/28 Questions? 32/28 Thank you 33/28