Hardware Acceleration of EDA Algorithms- P4: Single-threaded software applications have ceased to see significant gains in performance on a general-purpose CPU, even with further scaling in very large scale integration (VLSI) technology. This is a significant problem for electronic design automation (EDA) applications, since the design complexity of VLSI integrated circuits (ICs) is continuously growing. In this research monograph, we evaluate custom ICs, field-programmable gate arrays (FPGAs), and graphics processors as platforms for accelerating EDA algorithms, instead of the general-purpose singlethreaded CPU | Hardware Architecture 39 Hardware Details Decision Engine Figure shows the state machine of the decision engine. To begin with the CNF instance is loaded onto the hardware. Our hardware uses dynamic circuits so all signals are initialized into their precharged or predischarged states in the refresh state . The decision engine assigns the variables in the order of their identification tag which is a numerical ID for each variable statically assigned such that most commonly occurring variables are assigned a lower tag. The decision engine assigns a variable in assign_next_variable state and this assignment is forwarded to the banks via the base cells. The decision engine then waits for the banks to compute all the implications during wait_for_implications state. If no conflict is generated due to the assignment the decision engine assigns the next variable. If there is a conflict all the variables participating in the conflict clause are communicated by the banks to the decision engine via the base cell. Based on this information during the analyze_conflict state the base cell generates the conflict-induced clause and then stores it in the clause bank. Also it non-chronologically backtracks according to the GRASP 28 algorithm. Each variable in a bank retains the decision level of the current assignment implication. When the backtrack level is lower than this stored decision level then the stored decision level is cleared before further action by 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 decision is applied to the banks. If all the variables have either been assigned or implied with no conflicts this is detected from the assignment on the last level the CNF instance is reported to be satisfiable in the satisfied state of the decision engine finite state Fig. State diagram of the decision engine 40 4 Accelerating Boolean .
