http://dl.gi.de/handle/20.500.12116/6255 Beiträge im Fachbereich Informatik in den Lebenswissenschaften (ILW) 2026-07-21T14:10:39Z http://dl.gi.de/handle/20.500.12116/41706 Advanced tools and methods for treewidth-based problem solving Hecher, Markus Computer programs, so-called solvers, for solving the well-known Boolean satisfiability problem (Sat) have been improving for decades. Among the reasons, why these solvers are so fast, is the implicit usage of the formula’s structural properties during solving. One of such structural indicators is the so-called treewidth, which tries to measure how close a formula instance is to being easy (tree-like). This work focuses on logic-based problems and treewidth-based methods and tools for solving them. Many of these problems are also relevant for knowledge representation and reasoning (KR) as well as artificial intelligence (AI) in general. We present a new type of problem reduction, which is referred to by decomposition-guided (DG). This reduction type forms the basis to solve a problem for quantified Boolean formulas (QBFs) of bounded treewidth that has been open since 2004. The solution of this problem then gives rise to a new methodology for proving precise lower bounds for a range of further formalisms in logic, KR, and AI. Despite the established lower bounds, we implement an algorithm for solving extensions of Sat efficiently, by directly using treewidth. Our implementation is based on finding abstractions of instances, which are then incrementally refined in the process. Thereby, our observations confirm that treewidth is an important measure that should be considered in the design of modern solvers. 2023-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/41705 Optimizing multi-level ReRAM memory for low latency and low energy consumption Hosseinzadeh, Shima; Klemm, Marius; Fischer, Georg; Fey, Dietmar With decreasing die size and the ability to store multiple bits in a single cell, resistive random access memory (ReRAM) can be used to increase storage density, making it a promising technology for the next generation of memory. However, multi-level write operations suffer from impairments such as large latency, high energy consumption, and reliability issues. In this paper, we study different mechanisms affecting the “multi-level incremental step pulse with verify algorithm” (M-ISPVA) on a 1-transistor-1-resistor (1T1R) model in transient simulation at the component and the circuit level with focus on resistance control and energy consumption during the entire process of state transitions. By dividing the M-ISPVA into a triggering and a controlling period, we discovered the transistor to operate in the ohmic region during the triggering period as a voltage-controlled resistance and in the saturation region during the controlling period as a voltage-controlled current limiter. Controlling the gate voltage in the triggering period can move the triggering point to a desired write voltage and in the controlling period can increase or decrease resistance steps per pulse to attain a desired speed of resistance change. In addition, the major energy portion is consumed for reset operation during triggering and for set operation during the controlling period. To optimize write performance, extra precaution must be taken when defining resistance states with target read-out current and gate voltage with the focus on evenly balanced latencies between all transitions. A direct multi-level write operation shows 67.5 % latency and 62.5 % energy saving compared to indirect ones, but suffers from only unidirectional control, making it non-feasible. In case of a 4 k bit memory, the more reliable M-ISPVA faces almost 37 % higher latency and energy compared to the basic ISPVA. 2023-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/41702 Timing-accurate simulation framework for NVM-based compute-in-memory architecture exploration Rietz, Vincent; Münch, Christopher; Mayahinia, Mahta; Tahoori, Mehdi Data-intensive applications have a huge demand on processor-memory communication. To reduce the amount of data transfers and their associated latency and energy, Compute-in-Memory (CIM) architectures can be used to perform operations ranging from simple binary operations to more complex operations such as additions and matrix-vector multiplications directly within the memory. However, proper adjustments to the memory hierarchy are needed to enable the execution of CIM operations. To evaluate the trade-off between the usage of different emerging non-volatile memories for CIM and conventional computing architectures, this work extends the widely used gem5 simulation framework with an extensible timing-aware main memory CIM simulation capability. This framework is used to analyze the performance of CIM extended main memory with various emerging memory technologies, namely Spin-Transfer-Torque Magnetic Random Access Memory (STT-MRAM), Redox-based RAM (ReRAM) and Phase-Change Memory (PCM). We evaluate different workloads from the PolyBench/C benchmark suite and other selected examples. In comparison to a processor-centric system, the results show a significant reduction in execution time for the majority of applications. 2023-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/41701 Bit slicing approaches for variability aware ReRAM CIM macros Bengel, Christopher; Dixius, Leon; Waser, Rainer; Wouters, Dirk J.; Menzel, Stephan Computation-in-Memory accelerators based on resistive switching devices represent a promising approach to realize future information processing systems. These architectures promise orders of magnitudes lower energy consumption for certain tasks, while also achieving higher throughputs than other special purpose hardware such as GPUs, due to their analog computation nature. Due to device variability issues, however, a single resistive switching cell usually does not achieve the resolution required for the considered applications. To overcome this challenge, many of the proposed architectures use an approach called bit slicing, where generally multiple low-resolution components are combined to realize higher resolution blocks. In this paper, we will present an analog accelerator architecture on the circuit level, which can be used to perform Vector-Matrix-Multiplications or Matrix-Matrix-Multiplications. The architecture consists of the 1T1R crossbar array, the optimized select circuitry and an ADC. The components are designed to handle the variability of the resistive switching cells, which is verified through our verified and physical compact model. We then use this architecture to compare different bit slicing approaches and discuss their tradeoffs. 2023-01-01T00:00:00Z