パスワードを忘れた? アカウント作成
13893538 story
プログラミング

東芝、組み合わせ最適化問題の近似解を得る新アルゴリズムを開発。並列処理で大幅な高速化が可能 31

ストーリー by hylom
詳細は論文をどうぞ 部門より

東芝が、組み合わせ最適化問題の近似解を高速に得る新しいアルゴリズムを開発したと発表したScience Advances掲載論文毎日新聞NHK)。

今回考案されたアルゴリズムは「シミュレーテッド分岐アルゴリズム」と名付けられており、並列処理によって容易に高速化できるのが特徴。FPGAを使って演算を行った場合、2000変数・全結合(約200万結合)の問題の良解を0.5ミリ秒で得られるとしており、これはレーザーを用いた量子計算機よりも約10倍高速だという。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2019年04月23日 18時33分 (#3604243)

    論文を斜め読みすると富士通のやってるディジタルアニーラ( https://www.fujitsu.com/jp/digitalannealer/ [fujitsu.com] )よりも10倍以上速いと言っているように見える。論文中ではディジタルアニーラは SA と表記、参考文献29番。頑張れ富士通。

    • by Anonymous Coward on 2019年04月23日 18時54分 (#3604266)

      デジタルアニーラは「おおむね一秒以下」と言ってたから、0.5ミリ秒よりも全然遅い。赤射の半分(オイ

      一方東芝のは最適解とは言っておらず、良解と言ってるので局所最適解になっていて、収束しきっていない可能性もありそう。

      親コメント
      • by Anonymous Coward

        デジタルアニーラも最適解ではないはず。

    • by Anonymous Coward

      流行に乗って量子アニーリングの研究をぶち上げたものの、いつまでもハードウェアは出来そうもなく、シミュレーションテクニックの発表でお茶を濁してる感じ

      • by Anonymous Coward on 2019年04月24日 8時12分 (#3604614)

        量子アニーリングハードウェアに比べて枯れたFPGAで同等以上の性能が出る
        アルゴリズムが見つかったなら実用的にはより有用なのでは?

        親コメント
        • by Anonymous Coward

          量子アニーリングの時点で、
          従来の方法で厳密解を探す時間>>>>>>量子アニーリングで近似解を探す時間
          という話だったわけで。
          従来の方法とも比べないと実用性はわからん。

  • by Anonymous Coward on 2019年04月23日 19時31分 (#3604321)

    ロボにならずに済むかも・・・

    • by Anonymous Coward

      おねえさんは厳密解を求めてたので、多分、近似解法なこの手のとは話が違う。

      # そもそも、お姉さんは高速に厳密解を求められたとしても、その後に列挙しようとして死ぬほど時間がかかりそうだけど

  • by Anonymous Coward on 2019年04月23日 15時37分 (#3604160)

    仮定保留のままその先進めて最後に生き残りパスを求めるのだろうか
    最尤推定のような。
    でも、年内の実用化?
    何でそんなに時間が掛かるんだろう

    • by Anonymous Coward

      素人の想像だけど、現時点では問題に合わせたハードコーディングで想定した理屈通りに高速処理できることが確認できただけ、実用品として公開するには汎用的に扱えるライブラリのような形に整備して、特に問題や結果の受け渡しをするAPIの仕様を検討中とかかな?

      • by Anonymous Coward

        どんな問題を渡されても、「42」という答えを返すだけの簡単なお仕事

    • by Anonymous Coward

      今日でも年内やで

      #東芝がその気になれば商業化は2020年3月31日からということも可能だということ

    • by Anonymous Coward

      ついに東芝は非決定性機械を実現してしまったのか

  • by Anonymous Coward on 2019年04月23日 19時09分 (#3604287)

    アメリカや中国のライバルは10倍スパコンを用意するなりクラスターの規模を10倍に増やすなりすればいいだけだからな。金の力には勝てんわ

    • by Anonymous Coward

      ロシアの鉛筆か

    • by Anonymous Coward

      中国 「日本企業に秘密なんて存在しないんやで」

    • by Anonymous Coward

      SAベースのアーキテクチャではどれだけ大規模なクラスターを組んでもイジングモデルによる組み合わせ最適化問題を実用的な時間内に汎用的に解くのは無理。
      東芝が実現した(と言っている)ようなハミルトニアンの評価を並列化してネットワークによる遅延を隠蔽する仕組みを導入しないと。

    • by Anonymous Coward

      主要な部分はFPGA一個で実装したみたいよ。一個150万円位するインテルの石だけれど。

    • by Anonymous Coward

      どちらかと言うとこれは並列アルゴリズムの発見だから10倍のクラスタを作れば10倍?速くなることが革新性なんじゃ無い?
      日本に対して並列ではなく10倍速いマシンを用意するのは中国/アメリカといえど容易ではない。

  • by Anonymous Coward on 2019年04月23日 22時17分 (#3604453)

    レーザーを用いた量子計算機よりも約10倍高速だという。

    これはコヒーレントイジングマシンを指していて、コヒーレントイジングマシンは量子計算機(コンピュータ、アニーラ)ではありません [mainichi.jp]。話題の量子コンピュータより速い方法を開発したと誤解させる嘘プレスリリースを大企業東芝が流すあたり、日本の技術レベルの凋落をはっきり表しています。

    • by Anonymous Coward

      コヒーレントイジングマシンが量子コンピュータかどうかはともかく、東芝のリリース内容に嘘が無ければ真正の量子コンピュータであるD-Waveより高速だよ。
      速度の比較のために現存するイジングマシンとしてコヒーレントイジングマシンやデジタルアニーラを持ち出すのは別に間違っちゃいない。

      • by Anonymous Coward

        D-Wave=量子アニーリングマシンを真正の量子コンピュータと言っていいのかどうか。

        • by Anonymous Coward

          なんで?
          ちゃんと量子アニーリングの基礎理論に沿って実装されてるでしょ。

          量子ゲート方式以外は量子コンピュータと認めないっていうスタンス?

      • by Anonymous Coward

        速度の比較のために現存するイジングマシンとしてコヒーレントイジングマシンやデジタルアニーラを持ち出すのは別に間違っちゃいない。

        コヒーレントイジングマシンはGPUに20倍速度の差で負けている [arxiv.org]ので間違いです。

        Thus the question naturally arises: Can the optical portion of the coherent Ising machine be replaced with classical mean-field arithmetic? Here we answer this in the affirmative by showing that a straightforward noisy version of mean-field annealing closely matches

        • by Anonymous Coward

          その論文、問題サイズN=2000の時のNMFAアルゴリズムでの処理時間は載せてないね。
          ちゃんと数字載せてるのはN=200までなんだけど、なんで?
          なんかズルくない?

          アルゴリズム自体も式を見る限りあんまり並列性良くなさそうなんだけど、これで本当に「N=2000全結合でもCIMより20倍速い」って言えるの?

    • by Anonymous Coward

      量子効果使ってりゃ量子コンピュータでしょ
      わざわざ書き分けのためにレーザーとまで書いてくれてんのに何が不満かね

      • 量子効果使ってないコンピュータなんてあるんか?

        --
        the.ACount
        親コメント
        • by Anonymous Coward

          友「お前今何やってんの?」
          俺「量子演算」

          • by Anonymous Coward

            どこにぶら下げるか迷ったけど、どうせ誰も読まないから末端にこそっとコメント。

            半導体でスイッチング素子(トランジスタ)が作れるのは、半導体の中では電子のエネルギーがバンド構造を持つためです。このエネルギーバンドは量子力学を使わないと説明できないので、明らかにトランジスタは量子効果を用いたスイッチング素子です。なので我々が普段使っているコンピュータは全て量子効果を使っています。でもお分かりの通り普通の計算機で計算しても、それはいわゆる「量子演算」ではありません。

            以上、量子通信装置による書き込みでした。

            量子照明(LED照明)消してもう寝ます。

      • by Anonymous Coward

        > 量子効果使ってりゃ量子コンピュータでしょ

        間違ってますよ

typodupeerror

日本発のオープンソースソフトウェアは42件 -- ある官僚

読み込み中...