最短路問題の目標

最短路 Online Solver から、一番大きな全米データ(#nodes: 23,947,347 | #arcs: 58,333,344)を選んでも、バケット法で 3～4秒、ヒープでも 5 秒程度で実行が終了する。図を見てもらえればわかるのだが、そもそも全米データ(2000万点以上)での前処理なしのダイクストラ法の実行に数十秒を要していたので、前処理＋ダイクストラ法という発想になった。それが今では、数秒程度に短縮されている（データ読み込み等の時間も入っているので、query 自体は 1 ～ 2秒か？）。これは、やはり以下のマシンのパワーに依存するところも大きい（ただし、1 query は 1 スレッドでの実行）。

PowerEdge 2900
CPU : Intel X5460 (3.16GHz) × 2
メモリ : 48GB (4GB × 12)
HDD : 1TB × 6 (RAID5)

また図の中で前処理 + query で数ミリ秒という目標になっているが、これは最短距離だけ求めれば良い場合なので、最短路まで求めているこの Online Solver の方がより手間がかかっている。ちなみに Online Solver でも、NY(#nodes: 264,346 | #arcs: 733,846)だと、前処理なしでもミリ秒単位で最短路を求めることができる。前処理なしということは動的にグラフのトポロジーや枝長が変化しても構わないということである。

GeForce 200 番台登場 その２

GeForce GTX 280 や Radeon HD 4800 などの最新のビデオカードは単精度演算で 1TFlops 級の性能を持っている。IEEE754 にほぼ準拠した倍精度演算がサポートされることになったのだが、倍精度演算ユニットの数が単精度演算ユニットの数よりも少なくなっていて、当然ながら演算性能も大差が付いている。そのためこのチップは、通常は単精度演算で行い、どうしても精度が必要な時にだけ倍精度演算を使うことが想定されている。普段実行しているアプリケーションでは倍精度演算でも精度が足りないのだが、やはりこのチップの性能を生かすためには単精度演算をメインにすべきということだろう。いろいろな最適化問題で必要とされる小数点の精度を考えてみると、

１ 半正定値計画問題：最初の反復の方は単精度演算でも対応できるかもしれない。ただし、実行可能解が見付からないようであれば、倍精度演算以上が必要。相補性が減少していった後の反復ではやはり倍精度演算以上が必要。ただし、このように単精度と倍精度をミックスした場合には、反復回数が増える可能性がある。

２ 整数計画問題や組合せ最適化問題：おそらく単精度演算でも十分。ただし、問題とアルゴリズムの性質上、このような GPGPU 上での高速化には不向き。

今後の研究設備

今後の研究用の設備（クラスタ計算、サーバなど）を図にしてみた。あと１か月ほどで、この図のような計算機環境が完成するだろう。

GeForce 200 番台登場

ついに GeForce GTX 200 シリーズが登場した。業者の方に紹介されたのだが、様々な改良点の中で倍精度演算に対応している点が注目である。よって、今度は CUDA を用いて単精度演算だけでなく、倍精度演算も行うことができる。しかし、今までの研究を見ていると PCI-Express の高バンド幅を要求するような問題では、あまり成果が上がっていない。
また、CPU は Intel のAtom で GPS搭載モバイルPC が発表されている。もちろん GPS で場所の測定ができるだけではなく、カーナビ用のソフトも付いている。これも HDD を分割して Linux を入れてしまおうかと思っている。

最短路 Online Solver 高速化

最短路 Online Solver だが、現在はユーザが始点、終点を指定して最短路を求める度に、ダイクストラ法のプログラム(ヒープ)を呼び出して、DIMACS データ（グラフや座標）を読み込んでから、最短路を求めるという手順にしている。そのため大規模な地図（全米 USA) などでは、実行に１分ぐらいの時間を要する。この時間の中では、ダイクストラ法そのものの実行時間よりも、巨大なデータを読み込んで、専用のデータ構造に変換する時間が多くを占めている。実は query 自体の時間は少ないので、様々な工夫によって高速化できる余地がたくさんある。いろいろと試して段階的に高速化されていくことになろう。

自作クラスタ計算機

以前は業者から PC パーツを買い求めて、自分達で数十台ほど組み立てて、自作のクラスタ計算機を造って運営していた。メーカーで完成品を購入する場合と比較して、２倍ぐらいのノード数にできるのが魅力だった。ただし普通の PC では、１年３６５日２４時間通電したまま稼働させて、計算負荷をかけるという任務には向いていないので、実際に使用するとトラブル続きだった。規模が数十台なので、Linpack 測定も 1 時間以内で終わるのだが、これが規模が大きくなって Linpack 測定に 1 日ぐらいかかるようになると全台で完走させるのは結構難しい。その後でグリッド計算用の資源として用いたので、８、９割稼働していれば十分ということになった。
このような経緯から、現在ではクラスタを構築するにしても重厚なサーバ仕様のマシンを購入することにした。台数は少なくても性能は出るし、管理の手間よりもソフトウェア開発の方に労力を使いたいので。

ゲームで覚える日本語

子供のおもちゃとして、久しぶりに LR44 の電池を入れてゲームウォッチを復活させてみた。1981年に購入したにも関わらず、どこも壊れていないで正常に動作する。オクトパスが欲しかったはずなのに、なんでミッキーマウスを買ったのか理由を覚えていない。当時友達が目をつぶっていても音でわかると言っていたが、やってみると音だけでは卵の落ちてくる順番はわからないような気がする。エポック社のパクパクマンも音のパターンでわかると言っていた。
先日、当専攻の大学院生のところにアメリカからホームステイで現地（ニューオリンズのそば）で高校の先生をしている人が来ていた。最短路とかクラスタ計算の話をしても、専門ではないのでほとんどわからないようだ。でも、日本のゲームには大変詳しくて、PS系はもちろん、PCエンジン、メガドライブ、サターン、ドリームキャストなど何でも知っている（研究室に全部現物があるのはすごい）。彼は日本語が全く話せないのだが、日本語教えたことがないので、一から教えるときにどのように教えたら良いのか全くわからない。ゲームで覚えたらということで、PS 版のドラクエをあげようとしたが、さすがに日本語全くわからない人にはプレイするのは無理だろう。日本のゲームが普及しても、日本語が普及しないのはやはり残念。

最短路 Online Solver の使い方

最短路 Online Solverの使い方の説明。

1:http://opt.indsys.chuo-u.ac.jp/portal/にアクセスする

2: 解像度とグラフファイルを選ぶ。その後で Change を押す

3: 始点と終点の座標を指定する。あるいは画像上でマウスをクリックする（２回、始点と終点）。

4: Submit ボタンを押す

画像は png 形式になっていて、マウスの右ボタンを押すなどして保存することもできる。

ドコモの携帯を海外で使う

すでに 906i の新型が登場しているが、昨年の暮れに新型の 905i(P905i) に変更した理由の一つは World Wing (3G/GSM両対応) で海外のほとんどの国でそのまま通話等に使えるからである。先日、アメリカに出張に行ってシカゴのオヘア空港について、電源を入れたところ突然メイルが二通ほどやって来た。メイル内容は、
1: お客様の携帯は日本と通信可能ですというもの
2: 紛失、盗難時の連絡先
というもの。そのまま i モードにしたら普通に使うことができるので、フルブラウザに切り替えてみたところ、やはり普通に使うことができた。ただ通信料が高そうなので、使用には注意が必要。

EXPO 70

公式長編記録映画日本万国博という DVD を購入した。谷口千吉総監督によるEXPO 70 の公式長編記録映画で 71年に劇場公開されている。EXPO 70 開催中に生まれたので入場したことはないのだが、小さいころには周辺に EXPO 70 の解説本や特集号などが置いてあったので、今 DVD を見ると懐かしいというか、行ったことがあるような錯覚を受けてしまう。
実際に行った人の間ではアメリカ館の月の石などが大人気だったようだが、個人的にはサンヨー館の人間洗濯機（ウルトラソニックバス）や日立館のフライトシミュレータなどが強い印象に残っている。すでに遠い過去の話のように感じていたのだが、自分が大人になってから、DVD や様々なホームページ等でさらに詳しい情報を得られるとは思わなかった。

最短路 Online Solver

最短路 Online Solver の開発が進んでいる。当面の機能としては、画像のように始点と終点をマウスでクリックあるいは座標を指定すると、最短路をピンクで表示するようになっている。Google 系のツールと連動できると良いと思っている。このバージョンの特徴としては、
１：本当の最短路を出力する（近似ではなく、厳密な最短路）
２：前処理を必要としない（枝長やグラフのトポロジーなどが動的に変化しても良い）
３：高速に解を出す（ここはまだまだ改善の余地あり）
となっている。ただし前処理を付けても良いし、付けることもできる。

公開までに必要な機能等は、以下のようなものである。
１：トップページと説明
２：複数ユーザが同時にアクセスしたときの対処
３：最短路ソルバーはメモリ上にグラフデータ等を保持したまま待機する

やりたいことは沢山あるので、まだ始まったばかりというところ。
http://opt.indsys.chuo-u.ac.jp/portal/

SDPA と SDPA-GMP 更新しました

頻繁に更新されている方が、ソフトウェアとしての信頼性（継続性という意味で）も上がるという傾向がある。確かに数年間ぐらい更新が行われていないと、今後も継続してサポートされるのか不安になるので、使用をためらう人も多いだろう。有期（数年ぐらい）で予算を取ってソフトウェア開発などを行っている場合には、予算の切れ目が縁の切れ目で、その後はサポート無しで放置されることも多い（何回かそんなソフトウェアを使って痛い目に遭った）。
昨日（６月１８日）、SDPA と SDPA-GMP を更新して Ver 7.1.1 として統一した。バグ取りと仕様変更が更新の理由になっている。

http://sdpa.indsys.chuo-u.ac.jp/sdpa/index.html

4022ガル

今回の岩手・宮城内陸地震で観測された加速度の最大値は 4022 ガルに達していたことが報道されている。加速度はあくまでも加速度なので、実際に何秒間続いたのかが重要なのだが、建築基準法では 200 ガルを想定している。阪神淡路大震災（兵庫県南部地震）では、神戸海洋気象台において南北方向に 818 ガルが測定されて話題になった（建築基準法の４倍）。その後で、2004年10月の新潟県中越地震で 2515.4 ガル（これはおそらく３次元合成）が観測されて、今回はさらに大きな 4022 ガルが測定された。最近の地震が大きくなっているということではなく、地震観測網が広がり、機器の精度が上がってきたことが原因と考えられる。今後 M8 クラスの超巨大地震が来たときには、さらに大きな加速度が観測される可能性もあるだろう。

地震の加速度、国内観測史上最大を記録…中越地震超す

以下は加速度に関する豆知識である

○なぜ加速度を用いるのか？
明治時代には変位型の地震計。しかし、変位型の装置では、揺れの振幅が１ミリの何十分の一といった微弱な振動は測定できない。
現在では、強震加速度計が主流
○地震の揺れの加速度を「ガル」、速度を「カイン」、変位を「センチ」で示す。
1 ガル = 1cm/秒2、1 カイン = 1cm/秒、重力加速度　1G = 980ガル
○建築基準法の耐震設計
(1981年以前)地震時に建物にかかる水平の揺れの最大加速度を 200 ガル、つまり重力を W とすると、0.2Wの力が建物に加わっても壊れないように設計する
(1981年以後)地面の揺れそのものを0.2Gに想定する（より厳しくなる）

Parallel Shortest Path Algorithm

最短路問題に対する並列アルゴリズムというのを考えたことがあったが、ダイクストラ法というのはポテンシャル最少のノードを見付けて（ここでヒープやバケットが使えるが）、枝の緩和処理を行う。そのため複数ノードに分けて同時に処理するわけにはいかない。枝の緩和処理は枝ごとに並列に処理することが出来るが、実際の道路ネットワークでは、あまりノードの次数が高くないので、これも上手くいかない。各枝の緩和処理を SIMD で行おうと考えたが、やはり次数が高くないので、これも効果は期待薄である。
一方、Bellman-Ford 法やこれに近い方法を並列化した論文なども見かける。通常は枝の費用が全て非負の場合にはダイクストラ法が使えるだが、並列化するのならば Bellman-Ford 法の方がやりやすい。

Parallel Shortest Path Algorithms for Solving Large-Scale Instances

個人的には、並列化しなくてもダイクストラ法をベースにしていろいろと工夫して高速化した方が速いと思っているのだが、この論文で使っている Cray MTA-2 とはどんな計算機だろうか？　噂は聞くのだが、商業的には成功しなかったので、幻の計算機のような感じになっている。

緊急地震速報

今回の岩手、宮城内陸地震でも緊急地震速報が間に合わない（速報よりも先に揺れが到達してしまう）という事態が発生しているが、もともと以下の特性を持ったシステムである。

１：緊急地震速報はP波とS波の到達時間の差を利用したものなので、震源が近い直下型地震では間に合わない可能性が高い
２：地上デジタル方法では２，３秒のタイムラグがあるので、さらに速報が間に合わなくなる可能性が高くなる

というわけで、近いうちに発生する東海、東南海、南海地震などの海洋型地震では P 波と S 波の到達時間差が大きいので十分役に立つのではないだろうか。
地震のときには無線通信の方が耐性が強いので、やはりテレビ、ラジオ、携帯電話等が使えそうなのだが、フルセグは基本的に携帯型に向かないので、アナログ方法終了後は通常の電池が使えるワンセグチューナー付き携帯機器を揃えたい。最近の携帯電話が一番便利だが、電池が切れると充電が難しいので。