[發明專利]優化裝置、優化方法和記錄介質

在審

• 申請號: 202110056655.0
• 申請日: 2021-01-15
• 公開（公告）號: CN113283046A
• 公開（公告）日: 2021-08-20
• 發明（設計）人: 渡部康弘
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06N7/00;G06F111/06
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 王萍;楊林森

公開了優化裝置、優化方法和記錄介質。一種優化裝置包括：多個伊辛機，每個伊辛機搜索通過劃分由伊辛模型表示的問題而獲得的多個子問題之中的子問題的解，多個伊辛機中的每一個包括：存儲單元，其存儲針對多個組的與要計算的子問題對應的狀態變量集的值；搜索單元，其通過改變每個單位時段要處理的組、基于由其他伊辛機計算的子問題的第一解候選，對多個組中的每一個執行計算第二解候選的處理，使得在相同單位時段內針對與由其他伊辛機處理的組不同的組的狀態變量集計算第二解候選；以及通信單元，其每當單位時段結束時，將第二解候選發送到其他伊辛機。

技術領域

本文中討論的實施方式涉及優化裝置、優化方法和記錄介質。

背景技術

作為用于計算諾伊曼型計算機不易處理的大型離散優化問題的裝置，存在使用伊辛型能量函數(也被稱為成本函數或目標函數)的伊辛機(也被稱為玻爾茲曼機)。

在通過伊辛機的計算中，要計算的問題被伊辛模型代替，伊辛模型是表示磁性體的自旋行為的模型。基于馬爾科夫鏈蒙特卡洛方法諸如模擬退火方法或副本交換方法(也被稱為交換蒙特卡洛方法)，搜索使伊辛模型型能量函數的值(對應于伊辛模型的能量)最小化的狀態。

在通過伊辛機的計算中，使用表示各個狀態變量之間的相互作用的大小的權重系數。當狀態變量的數量由于問題規模的增加而增加時，權重系數的數量也增加。在完全耦合伊辛機——其用伊辛模型代替該問題時靈活性優異并可以考慮所有狀態變量之間的相互作用中，要存儲的權重系數與狀態變量數量的平方成比例。因此，在伊辛機由單個裝置(例如，一個芯片)實現的情況下，存在所有權重系數不能存儲在內部存儲器中的可能性。存在如下方法，其中權重系數存儲在大容量存儲裝置中，將通過劃分問題獲得的子問題轉移到伊辛計算單元，并且通過適當地調換要轉移的子問題來執行計算，但是需要花費時間來調換用于計算每個子問題的權重系數。

在相關技術中，為了加速通過馬爾科夫鏈蒙特卡洛方法進行的處理，存在一種方法，其中將相同的伊辛模型分配給多個伊辛芯片中的每一個，并且并行地執行處理。還有一種方法，其中問題被劃分成多個子問題，并且將多個子問題分配給多個伊辛芯片，并且并行地執行針對各個子問題的計算。

例如在日本特開專利公布第2018-206127號和日本特開專利公布第2016-51350號中公開了相關技術。

通過馬爾科夫鏈蒙特卡洛方法對伊辛模型進行能量最小化的原理是順序地更新狀態變量的值(1位的值被反轉)。

在應用將問題劃分成子問題并由多個伊辛機執行解搜索的方法的情況下，為了滿足該原理，在多個伊辛機中的任一個更新狀態變量的值時，其他伊辛機不執行更新而是處于暫停狀態。因此，每個伊辛機中的運算單元可能無法被有效使用，并且計算效率降低。

在一個方面中，實施方式的目的是提供一種可以提高優化裝置的計算效率的優化方法。

發明內容

根據實施方式的一個方面，一種優化裝置包括：多個伊辛機，每個伊辛機搜索通過劃分由伊辛模型表示的問題而獲得的多個子問題之中的子問題的解，多個伊辛機中的每一個包括：存儲單元，其存儲針對多個組的與要計算的子問題對應的狀態變量集的值；搜索單元，其通過改變每個單位時段要處理的組、基于由其他伊辛機計算的子問題的第一解候選，對多個組中的每一個執行計算第二解候選的處理，使得在相同單位時段內針對與由其他伊辛機處理的組不同的組的狀態變量集計算第二解候選；以及通信單元，每當單位時段結束時，其將第二解候選發送到其他伊辛機。

在一個方面中，該實施方式可以提高優化裝置中的計算效率。

附圖說明

圖1是示出根據第一實施方式的優化裝置的示例的圖；

圖2是示出控制裝置對優化裝置的控制的示例的流程的流程圖；

圖3是示出優化裝置的操作的示例的流程的流程圖；