Probabilistic and oscillatory Ising machines for combinatorial optimization: from software to hardware-acceleration with spintronics

The modern computer is arguably the most influential invention of the 20th century. The size of the transistor, one of its fundamental components, has always been strongly tied with the processing speed of a unit, as smaller transistors meant that it was easier to fit a lot of them in the same space. What started out as a 1 cm device in 1947, became over three million times smaller as of 2022, with the 3 nm transistors manufactured by Samsung. The reduction in size of the device over time, a natural result of technological advancement, follows a trend known as ``Moore's law'', which takes the name from the person who, in 1965, predicted that the number of transistors on integrated circuits would double every two years. This exponential forecast has been remarkably accurate up until the current years. The reason for this unstoppable growth is twofold: on one hand, the drive to miniaturize the device is pushed by the need of industry and the market to always improve computing performance; on the other hand, there were still improvement margins only limited by the technological advancements at the time. However, a critical point has been reached: while the first catalyst for growth is stronger than ever, the size of the transistors is approaching intrinsic physical limitations. While some continue searching for alternative ways to circumvent these limits, many are looking in other directions to satisfy the demands for faster computation. In this context, the latest years have seen several unconventional computing paradigms being devised by physicists, engineers, and computer scientists that are not based on the von Neumann computer. The main design difference between these unconventional computing paradigms and conventional computers is their goal, which is no longer to have a general-purpose universal Turing machine, but rather a super-optimized, domain-specific device. The reason for this change is that the need for better performance comes from the need to solve combinatorial optimization problems. This category of computational problems is now fundamental in modern society for their many applications in industry and companies. Route optimization, logistics, job scheduling, design optimization, and many others are all problem that can be written as a combinatorial optimization problem. These, however, are generally very challenging, even for highly performing computers, which ultimately struggle to have desirable performance as the size of the instances of those problems increase. One of the most heated research topics in unconventional computing is the Ising machine. All combinatorial optimization problems can be rewritten as Ising models in which the ground state is the solution of the problem. This class of solvers employs a variety of annealing strategies and hardware architectures to minimize the energy of these Ising models. When choosing a hardware technology to implement an Ising machine on, the guiding principles are four: scalability, energy efficiency, design flexibility, and CMOS compatibility. The reason for the first is obvious, as it is why these alternative solutions are being researched at all. The second one comes from the fact that current technology also consumes too much energy. As such, new paradigms all strive for efficiency. The third one is needed because of the still embryonic stage of research for hardware Ising machines, which still requires a lot of experimentation. The fourth is a requirement because these new devices do not aim to supplant conventional computers, but rather work alongside them. One technology that satisfies all these guiding principles is spintronics. In particular, its flagship device, the magnetic tunnel junction. This piece of hardware can be manufactured on silicon, it is known to be extremely energy efficient, it is on the tens of nanometers scale, and its magnetization dynamics can be tuned and controlled with a variety of both design parameters and dynamical ones (electric currents, magnetic fields). This thesis deals with the study of two Ising machine paradigms and their possible hardware implementations. One of the two, probabilistic computing with p-bits, is the central focus and will be evaluated from a software perspective, then envisioning an MTJ hardware implementation, and finally considering a hardware accelerated implementation using field programmable gate arrays. The other paradigm, oscillatory Ising machines, will be considered first from a software standpoint, and then as a second paradigm compatible with magnetic tunnel junctions. The thesis is organized as follows. Chapter 1 will act as an introduction on the Ising model, providing a strong foundation for all the following discussions. Several encodings of combinatorial optimization problems will be presented, along with novel strategies like invertible logic. Many of the latter encodings are original results. Chapter 2 will introduce probabilistic computing with p-bits and probabilistic Ising machines. The most important theoretical concepts, useful also for the comprehension of the other chapters, will be presented here. The chapter will also contain results obtained exclusively using software implementations. Chapter 3 will first lay down the foundations of micromagnetism simulations. These will be then connected with probabilistic Ising machines in the last part of the chapter with some results. The simulation of magnetic tunnel junction-based probabilistic Ising machines is a promising first step in the direction of a hardware implementation. Chapter 4 will describe the implementation of the probabilistic Ising machine using field programmable gate arrays and provide an extensive discussion of the results. The impressive performance achieved using hardware acceleration proves the potential of this paradigm for the solution of combinatorial optimization problems. Chapter 5 will introduce the concept of oscillatory Ising machine. The main models used to simulate this paradigm will be introduced. Some software results will be presented, together with perspectives on the implementation of this paradigm using magnetic tunnel junctions.