Hardware Acceleration of EDA Algorithms- P4

Hardware Acceleration of EDA Algorithms- P4: Single-threaded software applications have ceased to see significant gains in performanceon a general-purpose CPU, even with further scaling in very large scaleintegration (VLSI) technology. This is a significant problem for electronic designautomation (EDA) applications, since the design complexity of VLSI integratedcircuits (ICs) is continuously growing. In this research monograph, we evaluatecustom ICs, field-programmable gate arrays (FPGAs), and graphics processors asplatforms for accelerating EDA algorithms, instead of the general-purpose singlethreadedCPU....
Nội dung trích xuất từ tài liệu:
Hardware Acceleration of EDA Algorithms- P44.4 Hardware Architecture 394.4.3 Hardware Details4.4.3.1 Decision EngineFigure 4.3 shows the state machine of the decision engine. To begin with, the CNFinstance is loaded onto the hardware. Our hardware uses dynamic circuits so allsignals are initialized into their precharged or predischarged states (in the refreshstate). The decision engine assigns the variables in the order of their identificationtag, which is a numerical ID for each variable, statically assigned such that mostcommonly occurring variables are assigned a lower tag. The decision engine assignsa variable (in assign_next_variable state) and this assignment is forwarded to thebanks via the base cells. The decision engine then waits for the banks to computeall the implications during wait_for_implications state. If no conflict is generateddue to the assignment, the decision engine assigns the next variable. If there is aconflict, all the variables participating in the conflict clause are communicated bythe banks to the decision engine via the base cell. Based on this information, duringthe analyze_conflict state, the base cell generates the conflict-induced clause andthen stores it in the clause bank. Also it non-chronologically backtracks accordingto the GRASP [28] algorithm. Each variable in a bank retains the decision levelof the current assignment/implication. When the backtrack level is lower than thisstored decision level, then the stored decision level is cleared before further actionby the decision engine during the execute_conflict state. After a conflict is analyzed,the banks are again refreshed (in the precharge state) and the backtracked decisionis applied to the banks. If all the variables have either been assigned or implied withno conflicts (this is detected from the assignment on the last level), the CNF instanceis reported to be ‘satisfiable’ (in the satisfied state of the decision engine finite state idle satisfied refresh last level assign_next_variable var_implied no_conflict precharge wait_for_implications implication execute_conflict conflict analyze_conflict 0th level unsatisfiableFig. 4.3 State diagram of the decision engine40 4 Accelerating Boolean Satisfiability on a Custom ICmachine). On the other hand, if the decision engine has already backtracked on thevariable at the 0th level and a conflict still exists, the CNF instance is reported to be‘unsatisfiable’ (in the unsatisfiable state).4.4.3.2 Clause CellFigure 4.4 shows the signal interface of a clause cell. Figure 4.5 provides detailsof the clause cell structure. Each column (variable) in the bank has three signals –lit, lit_bar, and var_implied, which are used to communicate assignments, impli-cations, and conflicts on that variable. Each row (clause) in the bank has a signalclausesat_bar to indicate if the clause is satisfied. The 2-bit free_lit_cnt signalsserve as an indicator of the number of free literals in the clause. If the literal inthe clause cell is free (indicated by iamfree) then out_free_lit_cnt is one more thanin_free_lit_cnt. The imp_drv and cclause_drv signals facilitate generation of impli-cations and conflict clauses, respectively. Also, each row has a termination cell at itsend (which we assume is at the right side of the row) which drives the imp_drv andcclause_drv signals. We next describe the encoding of these signals and how theyare employed to perform BCP. clausesat_bar precharge cclause_drv wr imp_drv in_free_lit_cnt out_free_lit_cnt lit lit_bar var_impliedFig. 4.4 Signal interface of the clause cell Note that the signals lit, lit_bar, var_implied, and cclause_drv are predischargedand clausesat_bar is a precharged signal. Also, each clause cell has two single-bitregisters namely reg and reg_bar to store the literal of the clause. The data in theseregisters can be driven in or driven out on the lit and lit_bar signals. A variable is said to participate in a clause if it appears as a positive or nega-tive literal in the clause. The encoding of the reg and reg_bar bits is as shown inTable 4.1. The iamfree signal for a variable indicates that the variable has not beenassigned a value yet, nor has it been implied. The assignments and failure-driven assertions [28] are driven on lit, lit_bar, andvar_implied signals by the decision engine whereas implications are driven by theclause cells. Communication in both directions (i.e., from clause cell to the decisionengine and vice versa) is performed via the base cells using the above signals. Thereexists a base cell for each variable. Table 4.2 lists the encoding of the lit, lit_bar,and var_implied signals.4.4 Hardware Architecture 41 ...