<p>In combinatorial optimization, probabilistic Ising machines have gained significant attention for their acceleration of Monte-Carlo sampling with the potential to reduce time-to-solution in finding approximate ground states. However, to be viable in real applications, further advances in scalability and energy efficiency are necessary. Here, we experimentally demonstrate a scalable probabilistic Ising machine based on 250 spin-transfer-torque magnetic tunnel junctions. Our computing approach integrates spintronic tunable true random number generators with advanced annealing techniques. For sparsely connected graphs, the proposed massive parallel architecture enables a cluster parallel update method that overcomes the serial limitations of Gibbs sampling, leading to a 10 times acceleration without hardware changes. Furthermore, we prove experimentally that the simulated quantum annealing boosts solution quality 20 times over conventional simulated annealing while also increasing robustness to device variability. In addition, we propose a next generation chiplet-based architecture for future large-scale, high-performance, and energy-efficient unconventional computing hardware.</p>