Unconstrained Binary Quadratic Programming (UBQP) is widely studied. It is a powerful modeling tool and its associate problem is NP-hard. In this work a new approach is introduced, which can be used to build an exact algorithm. Also, the fundamental idea behind it can be used in an even wider family of problems. This exact algorithm derived from the new method is highly parallelizable, which is a desired feature nowadays, when the cloud computing is a reality. For reasonably large instances of UBQP, the new method can parallelize to hundreds, or even thousands, of cores easily, with a near-linear speedup.