Edit/Green Lotus
Combinatorial optimization is a type of problem of finding the optimal object in a finite set of objects, which is a very complex set of problems, so that it is often not feasible to use exhaustive search to find the best solution. These problems arise in a variety of applications in supply chain management, airline scheduling, industrial resource allocation, artificial intelligence, applied mathematics, and theoretical computer science.
A well-known example is the traveling salesman problem, where the salesman must go from city A to city B to city C to city D, but he must find the best route, visit each city once in the shortest possible time, and then return home.
Someone has to solve these problems, but from a computational point of view, the amount of resources required to run these algorithms is enormous.
Researchers from Pennsylvania State university have come up with a solution that combines a simulated annealing algorithm (SA) with a technique called in-memory computing. The researchers recommend using a simulated annealing algorithm to look for the ground state of the Ising spin glass system. Searches using SA's 4×4 ferromagnetic, antiferromagnetic, and spin glass systems are > 800 times faster than exhaustive searches using brute force tests.
The study was published in Advanced Materials under the title "An Annealing Accelerator for Ising Spin Systems Based on In-Memory Complementary 2D FETs."
SA is an excellent optimization technique in discrete problems with multiple local minimums. SA provides a simple framework that can be implemented on systems with any energy landscape, and it statistically guarantees the best solution.
Taking inspiration from physical annealing, SA heats the material above its recrystallization temperature to allow atoms to rearrange, which is then slowly cooled to increase its crystallinity and reach a low-energy state. SA uses random searches that allow high-energy transitions ("climbs") to evade local optimality with temperature-dependent probabilities.
Ising spin glass systems have properties such as spin disorder and "frustration" and provide a careful combination of a large number of metastable and ground-state degeneracies. Rotating glass is the ideal system for achieving SA.
SA and Ising rotary glass systems.
In this work, the researchers explored SA, known as p-type WSe2 and n-type MoS2FETs, using memory-complementary field-effect transistors (FETs) based on ultra-thin body two-dimensional semiconductors.
First, unlike quantum computers running at low temperatures, whose demonstrations are based on room temperature, and second, the researchers used simulated sub-threshold conduction and simulated programmability to design unique computational primitives and annealing schedules that achieve better energy and area efficiencies than large memristic crossover arrays.
In addition, this work has further advanced the development of an in-memory computing platform based on 2D FETs. To our knowledge, this is the first demonstration of SA hardware acceleration of an Ising Spin Glass system using emerging materials and equipment.
The hardware implementation of THE SA requires: (1) a random number generator for random spin flips; (2) a computational unit; (3) a computational unit to determine the cost of "climbing"; and (4) a hardware mechanism equivalent to annealing/cooling plan in metallurgy.
Simulates memory-complementary two-dimensional field-effect transistors (FETs).
"To achieve simulated annealing, we perform certain computational operations in hardware," said Amritanand Sebastian, a co-author of the study, a phD student in engineering science and mechanics. "The hardware is implemented using transistors based on 2D materials. In addition to performing calculations, these transistors can also store information. We use this in-memory computing power to perform simulated annealing in an efficient manner."
This method has several advantages:
First, the use of transistors based on 2D materials allows for ultra-low-power operation, saving energy;
Then, the multiplier circuit used in this work is very unique, allowing us to efficiently calculate the energy of the spin system;
Finally, unlike many implementations of simulated annealing, the hardware required to achieve this work does not need to scale with the size of the problem.
Experimental demonstration of SA.
The "frustration" of the rotating glass system can be observed. It is worth noting that SA speeds up the search compared to exhaustive searches using BFT, requiring orders of magnitude of low spin flip events. The maximum acceleration of ferromagnetic, antiferromagnetic and spin glass systems is ≈1365×, ≈ 1260 × and ≈ 1310 ×, respectively, while the average acceleration of systems converging to their ground state is ≈850 ×, ≈ 900 ×, and ≈ 810 ×, respectively.
It makes sense to use 2D materials to achieve this, as 2D materials often have the potential of future electronics and may be an alternative to silicon technology.
"We all know that silicon technology is aging, even though it's still a very rough technology that's very hard to compete with," Das said. "But we also know that in 20 years, we may have to enhance silicon technology, if not replace it completely." The unique capabilities of two-dimensional materials are ideal for the purposes of our research, making it one of the main candidates to replace silicon at some point."
Thesis link: https://doi.org/10.1002/adma.202107076
Reference: https://techxplore.com/news/2022-01-big-problems-algorithms-2d-materials.html
Artificial Intelligence × [ Biological Neuroscience Mathematics Physics Materials ]
"ScienceAI" focuses on the intersection and integration of artificial intelligence with other cutting-edge technologies and basic sciences.
Welcome to follow the stars and click Likes and Likes and Are Watching in the bottom right corner.