More Like this

1. RexBDDs: Reduction-on-Edge Complement-and-Swap Binary Decision Diagrams

   Ciardo, Gianfranco; Miner, Andrew S; Deng, Lichuan; Babar, Junaid (June 2024, DAC '24: Proceedings of the 61st ACM/IEEE Design Automation Conference)

   We introduce RexBDDs, binary decision diagrams (BDDs) that exploit reduction opportunities well beyond those of reduced ordered BDDs, zero-suppressed BDDs, and recent proposals integrating multiple reduction rules. RexBDDs also leverage (output) complement flags and (input) swap flags to potentially decrease the number of nodes by a factor of four. We define a reduced form of RexBDDs that ensures canonicity, and use a set of benchmarks to demonstrate their superior storage and runtime requirements compared to previous alternatives. 

   more » « less
2. Research Directions in Decision Diagram Technology

   https://doi.org/10.1109/JVA60410.2023.00018  

   Ciardo, Gianfranco; Miner, Andrew S. (July 2023, IEEE)

   Binary decision diagrams (BDDs) have been a huge success story in hardware and software verification and are increasingly applied to a wide range of combinatorial problems. While BDDs can encode boolean-valued functions of boolean-valued variables, many BDD variants have been proposed, not just to improve their efficiency, but to manage multivalued domains (a straightforward extension), multivalued ranges (using several competitive alternatives), and two-dimensional data (relations and matrices instead of sets or vectors). Orthogonally to these extensions, much effort has been spent on variable order heuristics, an essential aspect that can affect memory and time requirements by up to an exponential factor. We survey some of these exciting results and discuss some fruitful research directions for further work. Index Terms—Binary decision diagrams, canonicity, discrete function encoding, variable order heuristics, Markov chains 

   more » « less
3. Accelerating Graph Computations on 3D NoC-enabled PIM Architectures

   https://doi.org/10.1145/3564290  

   Choudhury, Dwaipayan; Xiang, Lizhi; Rajam, Aravind Sukumaran; Kalyanaraman, Ananth; Pande, Partha Pratim (October 2022, ACM Transactions on Design Automation of Electronic Systems)

   Graph application workloads are dominated by random memory accesses with poor locality. To tackle the irregular and sparse nature of computation, ReRAM-based Processing-in-Memory (PIM) architectures have been proposed recently. Most of these ReRAM architecture designs have focused on mapping graph computations into a set of multiply-and-accumulate (MAC) operations. ReRAMs also offer a key advantage in reducing memory latency between cores and memory by allowing for processing-in-memory (PIM). However, when implemented on a ReRAM-based manycore architecture, graph applications still pose two key challenges – significant storage requirements (particularly due to wasted zero cell storage), and significant amount of on-chip traffic. To tackle these two challenges, in this paper we propose the design of a 3D NoC-enabled ReRAM-based manycore architecture. Our proposed architecture incorporates a novel crossbar-aware node reordering to reduce ReRAM storage requirements. Secondly, its 3D NoC-enabled design reduces on-chip communication latency. Our architecture outperforms the state-of-the-art in ReRAM-based graph acceleration by up to 5x in performance while consuming up to 10.3x less energy for a range of graph inputs and workloads. 

   more » « less
4. FedVARP: Tackling the variance due to partial client participation in federated learning

   Jhunjhunwala, Divyansh; Sharma, Pranay; Nagarkatti, Aushim; Joshi, Gauri (July 2022, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence)

   Data-heterogeneous federated learning (FL) systems suffer from two significant sources of convergence error: 1) client drift error caused by performing multiple local optimization steps at clients, and 2) partial client participation error caused by the fact that only a small subset of the edge clients participate in every training round. We find that among these, only the former has received significant attention in the literature. To remedy this, we propose FedVARP, a novel variance reduction algorithm applied at the server that eliminates error due to partial client participation. To do so, the server simply maintains in memory the most recent update for each client and uses these as surrogate updates for the non-participating clients in every round. Further, to alleviate the memory requirement at the server, we propose a novel clustering-based variance reduction algorithm ClusterFedVARP. Unlike previously proposed methods, both FedVARP and ClusterFedVARP do not require additional computation at clients or communication of additional optimization parameters. Through extensive experiments, we show that FedVARP outperforms state-of-the-art methods, and ClusterFedVARP achieves performance comparable to FedVARP with much less memory requirements. 

   more » « less
5. Computing under-approximations of multivalued decision diagrams

   Hosseini, Seyedehzahra; Ciardo, Gianfranco (May 2023, Application and Theory of Petri Nets and Concurrency)

   Gomes, L.; Lorenz, R. (Ed.)

   Efficient manipulation of binary or multi-valueddecision diagrams (BDDs or MDDs) is critical in symbolic verification tools. Despite the applicability of MDDs to real-world tasks such as discovering the reachable states of a model, their large demands on hardware resources, especially memory, limit algorithmic scalability. In this paper, we focus on memory-constrained algorithms that employ a novel O(m log n)-time under-approximation technique for MDDs, where m and n are the number of MDD edges and nodes, respectively. The effectiveness of our approach is demonstrated experimentally by a reduction in peak memory usage for the symbolic reachability computation of a set of Petri nets. 

   more » « less