Search

A 2021 Nature paper by Google researchers claimed a breakthrough in using reinforcement learning (RL) for chip design but lacked transparency, sparking skepticism. Cross-analyses reveal that the RL approach lagged behind conventional methods and commercial software, raising doubts about the validity of the paper’s conclusions. Methodological omissions and data inconsistencies hindered reproducibility, and Google’s attempts to address criticisms remain incomplete. This case underscores the importance of transparency in high-impact research and calls for policy adjustments to enforce reproducibility standards and address research misconduct effectively.

VLSI placement optimizes locations of circuit components so as to reduce interconnect. Formulated in terms of (hyper)graphs, it is NP-hard, and yet must be solved for challenging million-node instances within several hours. We propose an algorithm for large-scale placement that outperforms prior art both in run time and solution quality on standard benchmarks. The algorithm is more straightforward than existing placers and easier to integrate into timing-closure flows. Our C++ implementation is compact, self-contained and exploits instruction-level and thread-level parallelism.Due to its simplicity and superior performance, the algorithm has been adopted in the industry and was extended by several university groups to multi-objective optimization. [ABSTRACT FROM AUTHOR]

A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modularexponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-commondivisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors. [ABSTRACT FROM AUTHOR]

Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.

Abstract Many algorithms for Boolean satisfiability (SAT) work within the framework of resolution as a proof system, and thus on unsatisfiable instances they can be viewed as attempting to find proofs by resolution. However it has been known since the 1980s that every resolution proof of the pigeonhole principle (PHPnm), suitably encoded as a CNF instance, includes exponentially many steps [18]. Therefore SAT solvers based upon the DLL procedure [12] or the DP procedure [13] must take exponential time. Polynomial-sized proofs of the pigeonhole principle exist for different proof systems, but general-purpose SAT solvers often remain confined to resolution. This result is in correlation with empirical evidence. Previously, we introduced the Compressed-BFS algorithm to solve the SAT decision problem. In an earlier work [27], an implementation of a Compressed-BFS algorithm empirically solved instances in T(n4) time. Here, we add to this claim, and show analytically that these instances are solvable in polynomial time by Compressed-BFS. Thus the class of tautologies efficiently provable by Compressed-BFS is different than that of any resolution-based procedure. We hope that the details of our complexity analysis shed some light on the proof system implied by Compressed-BFS. Our proof focuses on structural invariants within the compressed data structure that stores collections of sets of open clauses during the Compressed-BFS algorithm. We bound the size of this data structure, as well as the overall memory, by a polynomial. We then use this to show that the overall runtime is bounded by a polynomial.