一种解决众所周知的复杂数学问题的新型处理器

 
东京工业大学的科学家设计了一种新颖的处理器体系结构，它可以比现有解决方案更快地解决组合优化问题。组合优化是复杂的问题，在科学和工程的许多领域中都表现出来，并且常规计算机难以处理，这使得专用处理器体系结构非常重要。
通常，工程和其他科学应用中使用的数学问题涉及复杂的计算，这些计算在时间和资源上都超出了现代计算机的能力。组合优化问题就是这种情况。
组合优化包括在一个有限的可能对象集中找到一个最佳对象或解决方案。这些问题在财务中表现为投资组合优化，在物流中作为众所周知的“旅行推销员问题”，在机器学习中以及在药物发现中都有体现。但是，当前计算机在变量数量很大时无法解决这些问题。
东京工业大学的研究人员与北海道日立大学实验室以及东京大学合作，设计了一种新颖的处理器体系结构，专门解决了以伊辛模型形式表示的组合优化问题。 Ising模型最初用于描述磁性材料中原子(自旋)的磁性状态。但是，该模型可以用作解决组合优化问题的抽象方法，因为趋于达到所谓的最低能量状态的自旋演化反映了优化算法如何搜索最佳解决方案。实际上，处于最低能量状态的自旋状态可以直接映射到组合优化问题的解决方案。
拟议的处理器架构(称为STATICA)与计算伊辛模型(称为退火炉)的现有处理器从根本上不同。大多数报告的退火炉的局限性在于它们仅考虑相邻粒子之间的自旋相互作用。这样可以加快计算速度，但会限制其可能的应用。相反，STATICA已完全连接，并考虑了所有自旋相互作用。尽管STATICA的处理速度低于同类退火器，但其计算方案却更好，因为它使用了并行更新。
在大多数退火炉中，旋转(更新)的演化是迭代计算的。此过程本质上是串行的，这意味着旋转切换是一个接一个地计算的，因为一个旋转的切换会影响同一迭代中的所有其余旋转。在STATICA中，更新过程是使用所谓的随机细胞自动机并行进行的。 STATICA不会使用旋转本身来计算旋转状态，而是创建旋转的副本，并使用旋转间的相互作用，从而允许并行计算。由于减少了所需步骤，因此节省了大量时间。 “我们已经证明，传统方法和STATICA在某些条件下可以得出相同的解决方案，但是STATICA的步数要少N倍，其中N是模型中的自旋数，”负责该项目的Masato Motomura教授说。此外，研究团队实施了一种称为增量驱动旋转更新的方法。由于在计算下一个迭代时，仅在上一次迭代中改变的自旋很重要，因此使用了一个选择器电路，该电路仅包含在每次迭代中翻转的自旋。
STATICA比其他退火炉具有更低的功耗，更高的处理速度和更高的精度。本村教授说：“ STATICA旨在通过基于随机细胞自动机的数学模型解决最优化问题，从而使退火处理机发生革命性变化。我们的初步评估提供了有力的结果。”进一步的改进将使STATICA成为组合优化的诱人选择。