Solving the ‘big problems’ via algorithms enhanced by 2D materials

Important optimization algorithms that are designed to solve large-scale problems such as airline schedules and supply chain logistics may soon get a boost from 2D materials that will enable the algorithms to better solve the problems and use less energy, according to Penn State researchers.

These large-scale issues are known as combinatorial optimization problems, the term for a set of problems that are so complex that finding the best solution using an exhaustive search is sometimes unfeasible. Therefore, algorithms are valuable tools in solving these problems by finding the best possible solution.

“These are problems that we face in our everyday life, such as scheduling of transportation or supply chain logistics, and you need to really optimize the best way of doing it correctly,” said Saptarshi Das, associate professor of engineering science and mechanics and primary investigator for the study that was recently published in Advanced Materials. “One famous example is the Traveling Salesman Problem, where a salesman has to go from city A to city B to city C to city D, but he has to find the optimal route where he can visit each city exactly once in the shortest time and return home.”

These problems are important ones to solve, as they affect how fast we receive goods and services, how expensive they are for customers and how efficient our society’s logistics are for anything from defense to transportation.

“Somebody has to solve these problems but the amount of resources needed from a computational perspective is enormous in order to run these algorithms,” Das said. “A future goal is if you can run this algorithm in a much, much smarter, more energy-efficient way, that will essentially help any organizational effort, from manufacturing to government or even private organizations.”

The key is overcoming a bottleneck that forms during the transfer of data between memory and the computational unit. This bottleneck happens when a computer tries to solve a combinatorial optimization problem, known as a von Neumann bottleneck.

“With all the scheduling and logistic problems, you are dealing with a lot of data, and then you have a lot of computation, and every time you have to essentially shuttle this huge amount of data to the computing, do the computation, bring it back and do it again,” Das said. “These processes consume a lot of energy, this shuttling of the data between your storage and your computation.”

The researchers propose a solution that combines an optimization algorithm known as simulated annealing with a technique known as in-memory computing. Simulated annealing is based on annealing in metallurgy, where a metal is heated, and the atoms reorganize themselves and then crystallize in the lowest energy state.

“That is something being adopted over here in the computational framework,” Das said. “The energy is provided for the atoms to momentarily maybe go to a higher energy state.”

The researchers propose using simulated annealing algorithm to find the ground state of an Ising spin glass system, which is a magnetic system characterized by the randomness in spin orientations. To do this, they need to do high-end computational operations, and to carry out these computations, they used 2D materials, which are materials that are only a few atoms thick.

“In order to implement simulated annealing, we perform certain computational operations in hardware,” said Amritanand Sebastian, doctoral student in engineering science and mechanics and co-author of the study. “The hardware is implemented using 2D material-based transistors. In addition to performing computations, these transistors can also store information. We make use of this in-memory computation capability in order to perform simulated annealing in an efficient manner.”

This method has several advantages.

“First, the use of 2D materials-based transistors allow for ultra-low power operation, saving energy,” said Sebastian. “Then, the multiplier circuit used in this work is very unique and allows us to efficiently compute the energy of the spin system. And finally, unlike many implementations of simulated annealing, the hardware required to implement our work does not need to scale with the size of the problem.”

Using 2D materials for this purpose makes sense, according to Das, as 2D materials in general hold potential for future electronics and possibly an alternative to silicon technology.

“We all know that silicon technology is aging, even if it is still a very roust technology that is very difficult to compete with,” Das said. “But we also know that 20 years down the line, we may have to augment the silicon technology, if not completely replace it. The unique functionalities of 2D materials that work so well for our purposes in this study make it one of the prime candidates for replacing silicon at some point.”

Along with Das and Sebastian, an additional author of the study is Sarbashis Das, doctoral candidate in electrical engineering. The Department of Defense and National Science Foundation supported this research.

Related