SAGA: Synthesis Augmentation with Genetic Algorithms for In-Memory Sequence Optimization

• URL: http://arxiv.org/abs/2406.09677v1
• Date: Fri, 14 Jun 2024 03:00:42 GMT
• Title: SAGA: Synthesis Augmentation with Genetic Algorithms for In-Memory Sequence Optimization
• Authors: Andey Robins, Mike Borowczak,
• Abstract summary: MAGIC, or Memristor Aided Logic, is an approach which uses memory circuits which physically perform computation through write operations to memory. We detail the formation and implementation of these genetic algorithms and evaluate them over a number of open circuit implementations. Over the 10 benchmark circuits evaluated, these modifications lead to an overall improvement in the efficiency of in-memory circuit evaluation of 128% in the best case and 27.5% on average.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The von-Neumann architecture has a bottleneck which limits the speed at which data can be made available for computation. To combat this problem, novel paradigms for computing are being developed. One such paradigm, known as in-memory computing, interleaves computation with the storage of data within the same circuits. MAGIC, or Memristor Aided Logic, is an approach which uses memory circuits which physically perform computation through write operations to memory. Sequencing these operations is a computationally difficult problem which is directly correlated with the cost of solutions using MAGIC based in-memory computation. SAGA models the execution sequences as a topological sorting problem which makes the optimization well-suited for genetic algorithms. We then detail the formation and implementation of these genetic algorithms and evaluate them over a number of open circuit implementations. The memory-footprint needed for evaluating each of these circuits is decreased by up to 52% from existing, greedy-algorithm-based optimization solutions. Over the 10 benchmark circuits evaluated, these modifications lead to an overall improvement in the efficiency of in-memory circuit evaluation of 128% in the best case and 27.5% on average.

Related papers

• Resistive Memory-based Neural Differential Equation Solver for Score-based Diffusion Model [55.116403765330084]
  Current AIGC methods, such as score-based diffusion, are still deficient in terms of rapidity and efficiency. We propose a time-continuous and analog in-memory neural differential equation solver for score-based diffusion. We experimentally validate our solution with 180 nm resistive memory in-memory computing macros.
  arXiv  Detail & Related papers  (2024-04-08T16:34:35Z)
• GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
  We describe a parallel approximation algorithm for maximizing monotone submodular functions on distributed memory multiprocessors. Our work is motivated by the need to solve submodular optimization problems on massive data sets, for practical applications in areas such as data summarization, machine learning, and graph sparsification.
  arXiv  Detail & Related papers  (2024-03-15T14:19:09Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches [0.0]
  In evolutionary algorithms the computational cost of applying operators and storing populations is comparable to the cost of fitness evaluation. We show that storing the population as a minimum spanning tree, where vertices correspond to individuals but only contain meta-information about them, is a viable alternative to the straightforward implementation. Our experiments suggest that significant, even improvements -- including execution of crossover operators! -- can be achieved in terms of both memory usage and computational costs.
  arXiv  Detail & Related papers  (2023-06-29T05:12:14Z)
• QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation [0.8258451067861933]
  We introduce a domain-specific algorithm for numerical optimization operations used by quantum circuit instantiation, synthesis, and compilation methods. QFactor uses a tensor network formulation together with analytic methods and an iterative local optimization algorithm to reduce the number of problem parameters.
  arXiv  Detail & Related papers  (2023-06-13T21:51:20Z)
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits [0.0]
  reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. We propose a new algorithm for any linear reversible operator by using an optimized version of the Gaussian elimination algorithm and a tuned LU factorization. Overall, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes.
  arXiv  Detail & Related papers  (2022-01-17T16:31:42Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  Conditional gradient methods (CGM) are widely used in modern machine learning. Most efforts focus on reducing the number of iterations as a means to reduce the overall running time. We show the first algorithm, where the cost per iteration is sublinear in the number of parameters, for many fundamental optimization algorithms.
  arXiv  Detail & Related papers  (2021-11-30T05:40:14Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  We consider the problem of how to learn a step-size policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm. We propose a neural network architecture with local information of the current gradient as the input. The step-length policy is learned from data of similar optimization problems, avoids additional evaluations of the objective function, and guarantees that the output step remains inside a pre-defined interval.
  arXiv  Detail & Related papers  (2020-10-03T09:34:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.