nishio-dens's diary

Railsとかプログラミング関連の備忘録

Windows-Ubuntu間でスピーカーを共有する方法

Ubuntu

やりたいこと

  • 2台（以上）のPCで一つのスピーカーを共有したい

動機

私は以下のような環境で作業を行っています。

Macbook Airでtwitterを表示しつつ、Windowsで作業しつつ、Ubuntuでニコ動などを再生するというような、パソコンを3台起動した状態での作業を良く行ってます。
もちろん、キーボードとマウスはmacbook airについているものをsynergyなどで共有しているため、パソコン毎にいちいちキーボードを変えるなんていう面倒なことはしてません。

しかし上記の環境に一部不満を持っていました。普段はWindowsが走っているPCにスピーカーを接続しているのですが、Ubuntuでニコ動を再生しながら作業する場合は、わざわざUbuntuが走っているコンピュータにスピーカーを接続しなおさなければなりませんでした。これはとても面倒です。
そこで、リモートPCで再生された音をローカルPCに出力する（つまりローカルPCのスピーカーを共有する）こととしました。今回は以下の環境化において、スピーカーを共有する方法の紹介を致します。

  • Ubuntu(リモート）で再生した音をUbuntu(ローカル）のスピーカーで流す
  • Ubuntu(リモート）で再生した音をWindows(ローカル）のスピーカーで流す
  • Windows(リモート）で再生した音をUbuntu(ローカル）のスピーカーで流す

Ubuntu(リモート）で再生した音をUbuntu(ローカル）のスピーカーで流す方法

Ubuntu-Ubuntu間でのスピーカー共有はとても簡単です。なぜなら、Ubuntuで標準搭載されているオーディオ再生機構のPulseAudioは、標準でPCの音を別PCに飛ばす機能が付いているからです。

Ubuntuローカル側(スピーカーに接続しているPC, IP:192.168.1.99)の設定

1.ターミナルから cp /etc/pulse/default.pa ~/.pulse/ を実行し、pulseaudioの設定ファイルをホームフォルダの.pulse下に置く
2.vimなどでコピーした default.pa ファイルを開き、以下の項目を追加する

load-module module-native-protocol-tcp auth-ip-acl=リモートPCのアドレス

3.以下のコマンドでPulseAudioの再起動を行う

pulseaudio -k
pulseaudio -D


図1: default.paの設定。写真では、リモートPCのアドレスは192.168.1.5となっている

Ubuntuリモート側(IP:192.168.1.5)の設定

1.cp /etc/pulse/client.conf ~/.pulse/ を実行する
2.コピーしたclient.confに以下のコマンドを追加する

default-server = ローカルPCのアドレス

3.pulseAudioの再起動を行う（上記のコマンド参照)


図2: client.paの設定。写真では、ローカルPCのアドレスは192.168.1.99となっている

以上で完了です。リモートPCで何か音楽でも再生してみて、ローカルPC側のスピーカーで再生されたら成功です。

Ubuntu(リモート）で再生した音をWindows(ローカル）のスピーカーで流す

Windowsローカル側(スピーカーを接続しているPC, IP:192.168.1.50)の設定

1. http://www.cendio.com/pulseaudio/ からPulseAudioのwindows版をダウンロードする
2. 適当な場所に展開し、そのフォルダ内に default.pa という名前のファイルを作る
3. default.paを次のように編集する

load-module module-waveout
load-module module-native-protocol-tcp auth-ip-acl=リモートUbuntuのIPアドレス

4. pulseaudio.exeというファイルを実行する

Ubuntuリモート側(IP:192.168.1.5)の設定

先ほどUbuntu-Ubuntu間で行った設定と同じです。
1. cp /etc/pulse/client.conf ~/.pulse/ を実行
2. client.conf に default-server = 192.168.1.50 を追加
3. Pulseaudioを再起動

以上で完了です。

Windows(リモート）で再生した音をUbuntu(ローカル）のスピーカーで流す方法

この方法はあまりお勧めしません。なぜなら、遅延が酷くて動画などは音ズレが凄く気になります。音楽再生程度なら問題ないかと思います。

Ubuntuローカル側(スピーカーが接続されているPC, IP:192.168.1.5)の設定

  • 特に設定は必要ありません

Windowsリモート側(IP:192.168.1.50)の設定

Windows側は前提条件があります。

  • Cygwinがインストールされており、かつsshが利用できること
  • ステレオミキサーが有効であること

Cygwinのインストール方法とかはここでは説明しません。分からない方はgoogle先生に聞いてください。gnupackとか使うのがお勧めです。

ステレオミキサーは、有効にしておかなければWindowsパソコン上で流れた音をUbuntu側に転送できません。
ステレオミキサーを有効にするには、コントロールパネル → サウンドで、録音タブを開き、ステレオミキサーを有効にしてください。もしステレオミキサーが表示されていない場合は、右クリックして無効なデバイスの表示、を押すと表示されるかもしれません。

次に手順を説明します。
1.LiveInCode( http://liveincode.romanrm.ru/ )をダウンロードする
2.cygwinで以下のコマンドを実行し、Liveincode(linco.exe)で取得した音をssh経由でUbuntuに送る

linco.exe -B 16 -C 2 -R 44100 | ssh ユーザ名@UbuntuローカルのIP "cat - | pacat --playback"

以上で完了です。ただ遅延が酷く、私の環境では使えませんでした。

IP電話サービスのためのSIPサーバの実装と解説 - SIPソフトフォン(X-Lite4)による通話テスト

Programming
通話テストに必要なもの
  • パソコン2台
  • SIPフォン(X-lite4などのソフトウェアで可)
  • Ruby
通話テスト手順

SIPサーバ(http://github.com/nishio-dens/sip-server-sample)を使って通話テストを行ってみます。今回は無料で利用できるX-lite4と呼ばれるSIPソフトフォンを使って通話を行ってみます。余談ですが、X-lite4はパソコン上で利用可能なIP電話機です。ひかり電話等のIP電話を既に使っている方は、このX-lite4を使うことでパソコンから電話をかけられて便利です。

まずはX-lite4の公式ページ(http://www.counterpath.com/x-lite.html)からソフトをダウンロードし、インストールを行ってください。
インストールが完了したら、SIPサーバを起動しておきましょう。サンプルのSIPサーバはrubyで書かれているため、以下のコマンドをターミナルから入力してください。

ruby sip_server.rb サーバのIPアドレス

今回の実験ではサーバのIPアドレスは192.168.1.50、クライアントは192.168.1.50, 192.168.1.101を使うことにします。この辺りはお使いのパソコンのIPアドレスに置き換えてサンプルを実行してください。
なお、サンプルのSIPサーバはNATを越えて接続することはできません。ローカルネットワーク内で実験を行ってください。また、SIPサーバはデフォルトで5060番のポート番号を利用します。

プログラム起動後、2台のパソコンでX-lite4を起動し、SIPサーバに電話の情報を登録(Register)してみましょう。

X-lite4を起動後、アカウントの設定を行ってください。Windows版X-lite4を用いている方は、メニューバーからSoftphone → Account Settingsからアカウントの登録ができます。
AccountタブのUser Details内のUser ID及びDomainという部分の編集を行います。User IDは登録する電話番号です。またDomainはSIPサーバのIPアドレスです。


実験に使うクライアント毎に、このアカウント設定を行ってください。なお、今回はクライアント1(192.168.1.50)の電話番号を1, クライアント2の電話番号を2(192.168.1.101)としました。

登録が完了できたら、SIPサーバのプログラムになんらかのログが出力されているはずです。Register New Address(Number: 何々) と出力されていれば登録が完了しています。
もしサーバに何の情報も出力されていない場合は、プログラムが正しく動いていないか、ファイアーウォールによって通信が正しくできていないなどの可能性が考えられます。

登録完了後、クライアント1(電話番号1)からクライアント2（電話番号2)に向かって電話をかけてみます。
クライアント1は、ダイアルパッドから2番を入力し、緑色のCallボタンを押してください。相手側に電話がかかるはずです。
相手が電話にでたあとにマイクで話しかけて、相手側に音声がきちんと届いているかを確認してください。

IP電話サービスのためのSIPサーバの実装と解説

Programming

近年IP電話が急速に普及していますが、このIP電話の通話管理にSIP(Session Initiation Protocol)と呼ばれる通信プロトコルが採用されることが増えています。
SIPは相手に電話をかける、相手が受話器を取った際に通話を開始する、通話を切るなどといった流れを制御するためのプロトコルです。通話中に音声情報を相手に送るプロトコルはSIPではなくRTP(Real-time Transport Protocol)等別物なので注意してください。
SIPはテキストベースであり、HTTP等と同様にシンプルなプロトコルです。とてもシンプルなのですが、SIPの仕様書(RFC3261, http://www.ietf.org/rfc/rfc3261.txt)は269ページにもわたる膨大なものなので、個人で実装するのは相当手間がかかるものと思われます。

今回はRegister(電話番号等の情報を登録する）サーバとProxyサーバ（クライアント間のリクエストを中継する）サーバの基本的な部分を実装しましたので、解説とともに公開します。

目次

JavaにおけるTimer, ScheduledExecutorServiceのシステム時刻変更時の挙動の問題

Programming

問題点

  • java.util.Timer, java.util.concurrent.ScheduledExecutorServiceで処理を実行中にシステム時刻の変更を行うと、処理が不安定になる

実験環境

  • 実験環境1 - Ubuntu11.10 (OpenJDK)
    • Java version: java version "1.6.0_23" OpenJDK Runtime Environment (IcedTea6 1.11pre) (6b23~pre11-0ubuntu1.11.10) OpenJDK Server VM (build 20.0-b11, mixed mode)
  • 実験環境2 - MacOSX 10.6 (SunJava)
    • Java version: java version "1.6.0_26" Java(TM) SE Runtime Environment (build 1.6.0_26-b03-384-10M3425) Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02-384, mixed mode)
  • 実験環境3 - Windows7 (SunJava)
    • Java version: java version "1.6.0_26" Java(TM) SE Runtime Environment (build 1.6.0_26-b03) Java HotSpot(TM) Client VM (build 20.1-b02, mixed mode, sharing)

周期的処理実行クラスのシステム時刻変更時の挙動の問題

デスクトップアプリケーション作成の際に、ScheduledExecutorServiceのバグに気がついたのでこのメモを残しておきます。

Javaで周期的に処理を実行したい場合、java.util.Timerやjava.util.concurrent.ScheduledExecutorServiceを利用します。しかしこのクラス、処理中にシステム時刻が変更されると、極めて不可解な動作を起こすので注意が必要です。

システム時刻が変更されるなんてこと、そうそうないだろうと思うかもしれませんが、実は結構頻繁に発生します。一番よくあるのが、コンピュータをスリープ状態にして復帰した場合です。

10分間PCをスリープしてから復帰した場合、システム時刻は10分進められます。また、最近のOSではNTPを用いた時刻同期が標準機能として搭載されています。これらの機能を用いた場合も、プログラム側から見た場合には時刻が進んだり、戻ったりしたように見えます。

時刻が修正された際に起こる不可解な挙動について検証してみます。今回は1秒周期でプログラム実行後の経過時間と現在時刻を表示するプログラムを用意します。

import java.util.Date;
import java.util.Timer;
import java.util.TimerTask;

public class TimerCheck {
    private class TestTask extends TimerTask{
        @Override
            public void run() {
            time++;
            System.out.println(time + " : " + (new Date()));
        }
        private long time = 0; //経過時間
    }
    public static void main(String[] args) {
        new TimerCheck().main2();
    }
    public void main2() {
        Timer timer = new Timer();
        timer.schedule(new TestTask(), 0, 1000);
    }
}

次に時刻が修正された場合の動作を検証します。今回はプログラム実行中に時刻を1分進め、その後1分戻すという手順を踏んでみます。結果は以下のようになりました。

実行結果
1 : Tue Nov 29 18:45:29 JST 2011
2 : Tue Nov 29 18:45:30 JST 2011
(略)
17 : Tue Nov 29 18:45:45 JST 2011
18 : Tue Nov 29 18:46:37 JST 2011 ← 1分時刻を進めた
19 : Tue Nov 29 18:46:38 JST 2011
20 : Tue Nov 29 18:46:39 JST 2011
(略)
28 : Tue Nov 29 18:46:47 JST 2011
29 : Tue Nov 29 18:46:48 JST 2011
                                  ← 1分時刻を戻したら、処理が止まった!

実験環境1,2,3ともに同様の結果となりました。1分時刻を進めた場合は問題なく動作していますが、1分時刻を戻した場合は動作が止まってしまいました。
私が望んでいる動作は、システム時刻にかかわらず1秒周期で処理を実行して欲しいのですが、予想外の結果です。

周期的にに処理を実行するクラスは、Timerの他にScheduledExecutorServiceが存在しています。

このクラスはJava5.0から導入された新しいクラスであり、現在ではTimerよりもこちらのクラスが推奨されています。上記と同様のプログラムをScheduledExecutorServiceを使って書きなおしてみます。

import java.util.Date;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class ScheduledExecutorTest {
	private class TestTask implements Runnable{
		@Override
		public void run() {
			time++;
			System.out.println(time + " : " + (new Date()));
		}
		private long time = 0; //経過時間
	}
	public static void main(String[] args) {
		new ScheduledExecutorTest().main2();
	}
	public void main2() {
		ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
		scheduler.scheduleAtFixedRate(new TestTask(), 0, 1000, TimeUnit.MILLISECONDS);
	}
}

Timerクラスを用いた場合と同様に、1分時刻を途中で進め、その後1分戻す動作を行ってみます。
結果が環境1,2,3それぞれ異なるので順番に書いていきます。

まず環境1(Ubuntu)での動作結果です。

1 : Tue Nov 29 18:27:18 JST 2011
2 : Tue Nov 29 18:27:19 JST 2011
(略)
21 : Tue Nov 29 18:27:38 JST 2011
22 : Tue Nov 29 18:27:39 JST 2011
23 : Tue Nov 29 18:28:29 JST 2011 ← 1分進めた
24 : Tue Nov 29 18:28:30 JST 2011
(略)
44 : Tue Nov 29 18:28:50 JST 2011
45 : Tue Nov 29 18:27:42 JST 2011 ← 1分戻した
46 : Tue Nov 29 18:27:43 JST 2011
47 : Tue Nov 29 18:27:44 JST 2011

期待通りの動作をしているようです。

次に実験環境2(MacOSX)で動作させてみます。

1 : Tue Nov 29 18:49:21 JST 2011
2 : Tue Nov 29 18:49:22 JST 2011
(略)
22 : Tue Nov 29 18:49:42 JST 2011
23 : Tue Nov 29 18:50:38 JST 2011　← 1分時間を進めた
24 : Tue Nov 29 18:50:38 JST 2011  ← 24から78までの処理において、同時刻に同じ処理を一度に行っている
25 : Tue Nov 29 18:50:38 JST 2011
(略)
76 : Tue Nov 29 18:50:38 JST 2011
77 : Tue Nov 29 18:50:38 JST 2011
78 : Tue Nov 29 18:50:38 JST 2011
79 : Tue Nov 29 18:50:39 JST 2011
80 : Tue Nov 29 18:50:40 JST 2011
81 : Tue Nov 29 18:50:41 JST 2011
82 : Tue Nov 29 18:50:42 JST 2011
83 : Tue Nov 29 18:50:43 JST 2011
84 : Tue Nov 29 18:50:44 JST 2011
85 : Tue Nov 29 18:50:45 JST 2011
86 : Tue Nov 29 18:50:46 JST 2011
                                   ←　1分戻したら、処理が止まった!


これはとんでもない結果となってしまいました。
まず、時間を1分進めた場合、今まで実行できなかった処理（1分分の処理）を一気に実行しようとします。また時刻を1分戻した場合は、処理が停止してしまいました。

この問題は私がNishio Tweet Manager(NTM)というTwitterクライアントを作成中に気がつきました。NTMでは、60秒に1回ツイッターに対してタイムライン取得要求を出しているのですが、システムがスリープから復帰後、突然ツイッターに向けて猛烈な勢いでアクセスし始め焦りました。

最後に実験環境3の場合ですが、実行結果は省略させていただきます。
結果としては、1分時間を進めた際は問題ありませんでしたが、1分時間を戻すと処理が停止してしまいました。

まとめ

java.util.Timer利用時、システム内部時刻を1分進めた場合
実験環境 動作
環境1: Ubuntu 正常に動作
環境2: MacOSX 正常に動作
環境3: Windows7 正常に動作
java.util.Timer利用時、システム内部時刻を1分戻した場合
実験環境 動作
環境1: Ubuntu 処理が止まってしまう
環境2: MacOSX 処理が止まってしまう
環境3: Windows7 処理が止まってしまう
java.util.concurrent.ScheduledExecutorService利用時、システム内部時刻を1分進めた場合
実験環境 動作
環境1: Ubuntu 正常に動作
環境2: MacOSX 1分間に行われるはずであった処理を一度に処理する
環境3: Windows7 正常に動作
java.util.concurrent.ScheduledExecutorService利用時、システム内部時刻を1分戻した場合
実験環境 動作
環境1: Ubuntu 正常に動作
環境2: MacOSX 処理が止まってしまう
環境3: Windows7 処理が止まってしまう

この問題に関する詳しい知識をお持ちの方がいらっしゃいましたら、ご教示いただけるとありがたいです。

ラストエグザイル１期のあらすじと解説

Animation

アニメ関連のブログ書くの初めてかもしれない。ラストエグザイルというアニメが結構好きなんだけど、いかんせんストーリーが分かりにくい。２期が始まったけど１期みてないと分かりづらそう。私も１期の内容結構ちゃんと理解してないので、２期みてもよくわからないかもしれない。
そこで某大型掲示板とWikipediaの情報を引用して(というかこの記事の99%は引用です)、１期のあらすじと解説をまとめてみました。なお１期のネタばれなので、これから１期を見ようと思っている方は読まない方がいいです。

ラストエグザイル１期あらすじ[1]

温暖化と寒冷期突入によって異常気象が続いていた地球。
１００年後には住めなくなるという結果に世界が団結し、人類の優秀な人々をあつめた集団(ギルド)の先導で、宇宙コロニー(プレステール)への移住と、ナノ技術による地球環境の浄化を進めていく。地球浄化に長い年月がかかるのに加え、移住先での人口増加に対応するためプレステールは複数建造されて、ある程度文化が近い人々がまとめられた。１６世紀から１８世紀にかけての文明設定も人口の急増を防ぐ意図があった。ただ、プレステールへの移民は欧州連合が中心であり、地球に残った人々もいたようだ。

１期主人公のクラウスたちのプレステールは、北に東欧・ロシア系移民の『デュシス』南に欧州・北欧系移民の『アナトレー』が、ギルド管理の元にそれぞれ国をかまえていた。プレステールは、ギルドが管理する『気象制御装置』のおかげで大気と水が安定して存在し地球と同じような環境で生活できていたが、移住から６００年たった頃ギルドの内乱と気象装置故障の放置によって、徐々に世界は均衡と秩序を崩していく。ギルド４大家系のエラクレア家当主、デルフィーネが他家を抹殺しギルドを独占支配した結果デュシスの地は凍り、アナトレーは砂漠化が進み、『水』に大変な希少価値がつくまでになる。もはや次の冬を越せぬと悟った北のデュシスは、アナトレーとの緩衝地帯であり強烈な暴風域の『グランドストリーム』を超えて南侵を開始、『第三次ミナギス会戦』が始まる。

その頃、かつて父親が果たせなかったグランドストリームを超えること夢見る少年、クラウスと幼馴染みの少女ラヴィは、アナトレー辺境でヴァンシップ乗りとして暮らしていた。二人の父親は同盟の書簡をデュシスに届ける途中、グランドストリームに散った過去があった。あるとき、ギルド・ハミルトン家の謎の少女『アルヴィス』を偶然保護したのをきっかけに世界一安全な船、アナトレー特殊任務艦『シルヴァーナ』と行動を共にする。そこには、クラウスに『空を飛ぶ理由』を問いかける艦長のアレックスや、『自由な空』を否定するパイロット『タチアナ』と、ナビの『アリスティア』らがいて、さらにはギルド・エラクレア家の次期当主候補『ディーオ』もお忍びでやってくる。世を統べる謎の力『エグザイル』の『生体キー』である少女アルと、ギルド４大家系にそれぞれ伝わる『４編の詩』を巡りクラウスたちの冒険は続き……。

シルヴァーナ元副艦長で、アナトレー王女のソフィアの元に団結したプレステールの人々は、ギルドの技術独占に端を発する混乱に終止符を打つべくデルフィーネに決戦を挑み、これに勝利。アルを乗せてグランドストリームを突破したクラウスは、エグザイルが眠るデュシスへ降り立つ。その後アルとクラウスが４つの詩を諳んじて起動したエグザイルは、かつて人類が地球からプレステールに移住するための『移民船』であり、それが起動した事と、地球環境が改善したことは同義であった。(正確にはアルの誕生と同義)先発隊としてエグザイルに搭乗したクラウスたちは無事地球へ帰還し……。ここで１期エンド。ちなみにプレステールの異常気象はエグザイル起動で回復した模様。

エグザイルとは[2]

太古の人類が荒廃したもとの世界（地球）からプレステールに移民する際に使用した移民船。離発着のためのエアロックはデュシスの湖の下にあるのだが、第一次移民作戦の後はアナトレーとデュシスの中間部に停泊し、もとの世界の受け入れの準備が整うのをかなりの期間に渡って待機していた。この際嵐を使った防壁を構築していたが、これがグランドストリームである。ギルドはこのことを隠し伝説化させ、過去の人々のテクノロジーを独占したことと併せ、プレステール支配の基盤とした。アルヴィスはエグザイル再起動のための生体キーであり、彼女が生誕したことは即ちもとの世界への帰還作戦発動のための環境が整ったことを意味している。またアルヴィスをキーとして動作させるためのパスワードをミュステリオンとしてギルド四家に伝承させていた。アルヴィス生誕を捕捉したデルフィーネはプレステールの支配権の根拠であるエグザイルが自分のもとを離れることを警戒し、アルヴィスをおよび全てのミュステリオンを自らのもとに確保することを企図した。これが『LAST EXILE』の物語の全ての発端であると言える。待機モードのエグザイルは船体を強固な装甲で覆っており、近付くものは全て触手で攻撃する。この触手の威力は甚大でウルバヌス級戦艦やギルド戦艦をも一撃で沈めることができる。

良くある質問[1]

  • Q　舞台は？
    • A　前作から２年後の地球です
  • Q　１期見ていないけど大丈夫？
    • A　見ていなくても分かるように作ってある（監督談）気になる人は>>1のバンダイチャンネルの無料配信を試聴してみよう
  • Q　ディーオ死んだんじゃないの？
    • A　コキネラとアピス（最後の方に出てきたギルド人の仲間）が回収した.グランドストリームは、内部で風が回遊し、重力の均衡地点なので落ちて即死する訳じゃない
  • Q　ディーオの性別は？
    • A　男の娘

2期にも登場する人物[2]

ディーオ・エラクレア

デルフィーネの弟ギルド四大家系の一つ、エラクレア家出身のプリンシパル。物事に縛られることを嫌い、目新しいものに興味を抱き、面白いものを好きになる。ミステリアスで少し変わっているが基本的には純粋無垢な少年である。姉を極端に恐れている。姉の下を離れてシルヴァーナを襲うギルド艦に乗っていた。星型と戦うクラウスの天才的な操縦技術を偶然見て彼を“インメルマン”と呼ぶ。そのクラウスと勝負をするためにホライゾンケイブの八耐レースに参加するが敗北。クラウスにさらに興味を持ったためそのままシルヴァーナに乗船することになる。シルヴァーナで暮らす中でクラウスたちと楽しそうに接するようになる。シルヴァーナの面々に誕生日を祝ってもらい、涙を流して喜んだ。デルフィーネに捕まった後は強制洗脳で記憶を奪われ、性格を破壊されてしまった。徐々に自分を取り戻していくものの、記憶の混乱を引きずったままグランドストリームを飛行中、自分のためにルシオラが墜落死したと錯覚して……。

タチアナ・ヴィスラ

シルヴァーナに属するヴァンシップ隊隊長。17歳。階級は中尉。機体の色は赤。没落した貴族の出で給金を実家に送っている。ソフィアとは士官学校時代からの知り合いでプライベートでは対等な口をきく。士官学校中退後ソフィアの紹介でシルヴァーナに乗ることになる。とても固い性格でプライドも高く融通も利かない。クラウスと戦闘に出た際に精神的に脆い部分が露呈し、それ以来クラウスに好意を寄せるようになる。

アリスティア・アグリュー

タチアナのナビ。17歳。階級は少尉。タチアナとは士官学校時代からの友人で、彼女の中退と同時に自らも退学し共にシルヴァーナに乗ることになる。大人しい見た目とは裏腹に芯は強く、タチアナに対して厳しく接することもある。男性への免疫はなく、クラウスのことを少し意識している。

引用先

[1] 2ch, ■ラストエグザイル‐銀翼のファム‐■8th move, http://kamome.2ch.net/test/read.cgi/anime/1318628140/
[2] Wikipedia, LAST EXILE, http://ja.wikipedia.org/wiki/LAST_EXILE

謝辞

丁寧かつ分かりやすいまとめをしてくださった2ch住人の方、wikipediaの編集者の方に感謝いたします。

Mars:A MapReduce Framework on Graphics Processors の概要(日本語訳)

研究

Mars:A MapReduce Framework on Graphics Processorsの論文についてまとめておきます．英語の訳は間違っている可能性があります．

出典: Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, Tuyong Wang: Mars: a MapReduce framework on graphics processors, In Proceedings of the 17th international conference on Parallel architectures and compilation techniques (2008), pp. 260-269.

概要

概要（原文）

We design and implement Mars, a MapReduce framework, on graphics processors (GPUs). MapReduce is a distributed programming framework originally proposed by Google for the ease of development of web search applications on a large number of commodity CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth, but are harder to program since their architectures are designed as a special-purpose co-processor and their programming interfaces are typically for graphics applications. As the first attempt to harness GPU’s power for MapReduce, we developed Mars on an NVIDIA G80 GPU, which contains over one hundred processors, and evaluated it in comparison with Phoenix, the state-of-the-art MapReduce framework on multi-core CPUs. Mars hides the programming complexity of the GPU behind the simple and familiar MapReduce interface. It is up to 16 times faster than its CPU-based counterpart for six common web applications on a quad-core machine.

概要(日本語訳)

私たちはグラフィックプロセッサ(GPU)上で，MapReduceフレームワークであるMarsをデザインし実装した．MapReduceとは分散型プログラミングのフレームワークであり，Googleが大量の汎用CPUを使ってウェブサーチアプリケーションを楽に開発するために提案したものである．CPUに比べ，GPUは膨大な計算能力とメモリ帯域幅を持っているが，GPUを使ったプログラムを作る事はとても大変である．それは，GPUのアーキテクチャが特定の用途向けにデザインされており，インターフェースは大抵グラフィックアプリケーション向けに作られているからである．

MapReduceのためにGPUの計算力を使う最初の試みとして，私たちは100個以上のプロセッサが搭載されたNVIDIA G80 GPU上にてMarsを開発した．そしてMarsとPhoenixとの計算能力を比較した．Phoenixとは，マルチコアCPU上にてMapReduceを実装した最新のフレームワークである．MarsはGPUでの複雑なプログラミングを行うことなく，シンプルで親しみやすいMapReduceのインターフェースを使ってプログラミングが可能である．6個のウェブアプリケーションを使ってPhoenixとMarsを比較した結果，Quad Core CPUを搭載したPhoenixよりもMarsの方が16倍高速となった．

導入

  • ウェブページのインデックス作成等，大量のデータを日々扱うことは頻繁にある．よって高いパフォーマンスを出すことは必要である．
  • MapReduceは大量のデータを処理するためフレームワークとして成功している．
  • MapReduceは以下の操作を提供している．
    • (1)MapはKey/Valueペアを入力とし，中間Key/Valueペアを生成する．
    • (2)Reduceはすべての中間Key/Valueペアの同じKey同士のValueをまとめる
  • MapReduceランタイムは，自動的に複数のマシンで[9]，またはマルチコアプロセッサ上で[27]分散処理を行う．
  • MapReduceフレームワークは，並列プログラミングの複雑さを軽減してくれるものである．
  • 著者らはGPU上でのMapReduceフレームワークの開発を行った．
  • GPUはCPUと比べて10倍の計算能力と10倍のメモリ帯域幅を持っている[1].
  • NVIDIA CUDA[24]はグラフィックスレンダリングパイプラインなどの知識なしで，GPU上でプログラムを書くことができる言語である．
  • GPUは特定用途向けにデザインされており，一般的な処理，例えばウェブデータの分析を行うためのプログラムを書くことは難しい．
  • 著者らはGPU上でのMapReduceフレームワークを作ることによって，GPUの強力な計算力を簡単に使えるようにした．
  • GPUはCPUと違い，100個を越えるSIMD(Single Instruction Multiple Data)プロセッサを持っている．
  • GPUはアトミックな処理やロック機能をサポートしていない．
  • GPU上でMapReduceを実装するにあたり，3つの技術的な挑戦を行う．
    • (1)データ同期の際のオーバーヘッドを少なくさせなければならない．100個以上のプロセッサを使っても性能がスケールできるようにする．
    • (2)大量のスレッドを使って，並列に処理が実行できるよう仕事を割り当てる．
    • (3)文字列処理やファイル操作と並列読み込み，書き込みを含む処理ができるようにする．かつ効率よく扱えるようにする．
  • MarsはCPU上で作られたMapReduceのAPIと同じようなAPIを提供する．
  • 並列にデータ書き込みを行っている間にデータが衝突してしまうのを避けるため，ロックフリーな仕組みを開発した．
  • ロックフリーは，小さなオーバーヘッドで並列実行の結果が正しいものだと保証できるような仕組みである．
  • 著者らは，Quad-Core CPU, NVIDIA GeForce 8800 GPU(G80)の性能を持ったPC上でMarsを実装した．
  • Marsを評価するため6個のタスクを用意した．タスクは以下のとおりである．
    • String Match(SM)
    • Inverted Index(II)
    • Similarity Score(SS)
    • Matrix Multiplication(MM)
    • Page View Count(PVC)
    • Page View Rank(PVR)
  • 上記のタスクをMarsとPhoenix[27]にて実装し（PhoenixとはマルチコアCPU上でのMapReduceの実装の事），性能を比較した．
  • MarsとPhoenixの性能比較の結果，Marsの方が1.5倍から16倍パフォーマンスが向上した．

予備知識と概要

グラフィックプロセッサ(GPU)
  • 著者らはGPUをたくさんのコアをもったプロセッサだと考えた（下図)[16,28].

  • GPUは複数のSIMDマルチプロセッサで構成されており，数千のスレッド実行をサポートしている．
  • GPUのスレッドはCPUでのスレッド生成，切り替えよりも素早くできる．
  • それぞれのマルチプロセッサ上のスレッドはスレッドグループを作り上げている．
  • スレッドグループはマルチプロセッサ上のレジスタ等を共有している．
  • それぞれのスレッドグループはマルチプロセッサ上の動的なスケジュールを割り当てられるスケジュールユニットに分割できる．
  • 著者らはGPUのリソース活用度をMetric occupancy[23]を使って測ることとした．
  • NVIDIA G80は86GB/secの帯域幅と200サイクルの遅延を持っている．
GPGPU
  • GPGPUは様々なアプリケーションで利用されている．例えば，FFT[17],行列演算[18,19],データベース[12,13,16],分散コンピューティングプロジェクトであるFolding@home[11]やSeti@home[29]などである．
  • 以前までは，GPGPUの開発者はOpenGL[25]やDirectX[4]を使って開発を行っていた．
  • 最近はAMD CTM[2]やNVIDIA CUDA[24]等のGPGPU言語が登場した．
  • これらの言語は，大量のマルチスレッドを利用したパラレルコンピューティングアーキテクチャを利用できるようにし，マルチスレッドに対応したCやC++言語のようなプログラミング環境を提供してくれた．
  • Accelerator[30]やBrook[5]のようなGPGPU向けの高レベルプログラミングフレームワークが存在している．
  • 著者らは，これらのフレームワークを利用して，MapReduceフレームワークを実装することもできた．
  • MapReduceを作るにあたっては，例えばBrookのストリーミングプログラミングモデルのような特別な知識はユーザは必要ではない．
  • よって，我々は効率化のためにCUDAを使ってMarsの実装を行った．
  • 我々は様々なアプリケーションをビルディングブロックを使えるGPGPU基礎関数を開発した．
  • GPGPUの最新の技術を使った情報についてはOwensら[26]が調査している．
  • Govindaraju[15]らは分割統治操作に関するMalti-pass schemeを提案している．
  • CUDPP[14]はデータの並列操作に関するCUDAライブラリを提供している．
  • これらのGPUベースなプログラミングモデルはとても複雑である．
  • 著者らのMapReduceを使えば，簡単にプログラミングを行える．
MapReduce
  • MapReduceフレームワーク[9]は，MapとReduce関数をベースとしている．
  • MapとReduceは以下のように定義される

Map:(k1,v1) → (k2,v2)*
Reduce:(K2,v2*) → (k2,v3)*

  • Map関数はKey/valueのペア(k1,v1)を入力とし，中間Key/Valueペア(k2,v2)を出力する．
  • Reduce関数は同じkey同士をまとめて，Key/Valueペアのリストを生成する．
  • MapReduceを使った単語数のカウントの擬似コード[9]を以下に示す．
 Map(void *doc) {
    for each word w in doc
      EmitIntermediate(w, 1);
 }
 Reduce(void* word, Iterator values) {
    int result = 0;
    for each v in values
      result += v;
    Emit(word, result); //output word and its count
 }
  • MapReduceはデータマイニング，機械学習やバイオインフォマティクス等に適応されている．
  • Hadoop[3]はGoogleのMapReduceに似たMapReduceのオープンソース実装である．
  • Phoenix[27]はマルチコアCPU上でのMapReduce実装である．
  • Chuら[8]はMapReduceをマルチコアプロセッサ上で10個の機械学習へと適応させた．
  • Yangら[7]はリレーショナルデータベースのためのマージ操作をMapReduceに追加した．
  • Phoenixと違い，著者らの作成したGPUベースのMapReduceはロックフリーである．
  • このロックフリーの仕組みは，GPUやCPU上の数百のプロセッサを使ってもスケールするものである．
  • 著者らの研究と同じく，Catanzaroら[6]がGPU上でのMapReduceフレームワークを提案した．
  • しかし，それは開発者がGPUプログラミングの詳細について，例えばスレッドの設定やGPUのメモリ階層についての深い知識が必要である．
  • Lindermanら[20]は異種のプロセッサ同士での動的なMapReduceのスケジューリングタスクのためのフレームワークを提案した．
  • これらのスケジューリング方法は，CPUとGPUベースなMapReduceフレームワークに使うことができる．

デザインと実装

  • 著者らのデザインのゴールは以下の二つである．
    1. 簡単にプログラミングができること．
    2. 高性能なこと．
API
  • Marsは以下のAPIを提供している
 //MAP_COUNT counts result size of the map function.
 void MAP_COUNT(void *key, void *val, int keySize, int valSize);
 
 //The map function.
 voidMAP(void *key, void* val, int keySize, int valSize);
 
 //REDUCE_COUNT counts result size of the reduce
 function.
 void REDUCE_COUNT(void* key, void* vals, int keySize, int valCount);
 
 //The reduce function.
 void REDUCE(void* key, void* vals, int keySize, int valCount);
  • Marsは上記のAPI以外に4つのシステムがAPIを提供している．
  • emit関数はユーザが実装したMapとReduce関数の出力に使う．
 //Emit the key size and the value size in MAP_COUNT.
 void EMIT_INTERMEDIATE_COUNT(int keySize, int valSize);
 
 //Emit an intermediate result in MAP.
 void EMIT_INTERMEDIATE(void* key, void* val, int keySize, int valSize);
 
 //Emit the key size and the value size in REDUCE_COUNT.
 void EMIT_COUNT(int keySize, int valSize);
 
 //Emit a final result in REDUCE.
 void EMIT(void *key, void* val, int keySize, int valSize);
  • これらのAPIは既存のMapReduceフレームワークであるHadoop[3]やPhoenix[27]と似ている．
  • しかし，既存のフレームワークとは決定的に違う点が2つある．
    • (1)結果のサイズを数える部分
    • (2)結果を出力する部分
  • GPUはアトミックな演算をサポートしていないため，Marsでは結果を出力するために2ステップ利用する．
  • Marsを使った単語数カウントの擬似コードを以下に示す．
 //key is a line in the document.
 //val is the line ID.
 MAP_COUNT(key, val, keySize, valSize){
   for each word w in key
     EMIT_INTERMIDIATE_COUNT(w.length, sizeof(int));
 }
 MAP (key, val, keySize, valSize) {
   for each word w in key
     EMIT_INTERMIDIATE (w, 1);
 }
  • 上記のコードのように，それぞれの単語についてEMIT_INTERMIDIATE_COUNTを行う必要がある．
システムワークフローと設定
  • 下図はMarsのワークフローである．

  • MarsはCPUベースのMapReduceフレームワークのように，MapとReduceという二つのステージを持っている．
  • Mapでは，入力されたKey/Valueペアを複数のチャンクに分割する．
  • このチャンクの数はスレッドの数と等しい．
  • GPUの一つのスレッドは一つのチャンクに大して責任をもつ．
  • このため，Map段階のスレッドは負荷分散される．
  • Mapが完了したら，中間Key/Valueのペアをソートする．
  • Reduceでは，ソート済みのKey/Valueペアを同じようなサイズのチャンクに分割する．
  • この分割するチャンクの数もスレッドの数と等しくさせる．
  • The thread with a larger thread ID is responsible for a chunk with larger keys.(TODO:どういうことか分からないので調べる)
  • 動的な負荷分散機能は適応できない．なぜなら，現在のGPUは動的スレッドスケジューリングをサポートしていないからである．
  • 最終的に，Reduceの出力を一つのバッファに保存する．
  • Marsの詳細なワークフローは以下の通りである．
  • (1)から(3)と(7)はスケジューラの仕事である．
    1. 入力するKey/Valueのペアをメインメモリ上の配列に配置する．
    2. run-time設定のパラメータの初期化を行う．このパラメータについては表1を参照のこと．
    3. メインメモリ上の入力データ配列をGPU上のデバイスメモリへとコピーする．
    4. GPU上にてMapを開始し，中間Key/Valueペアを配列へと保存する．
    5. もしnoSortがF(False)ならば，中間データをソートする．
    6. もしnoReduceがFならば，GPU上にてReduceを行い，結果を出力する．そうでなければ，中間データを最終的な結果として出力する．
    7. 結果をGPUのデバイスメモリからメインメモリへコピーする．
  • GPUの制約により，Marsは二つのことを行う．
    1. Marsはスレッドの設定を行う．それは，GPUが動的なスレッドスケジューリングをサポートしていないからである．
    2. 加工前の入力データの受け渡しをCPUに任せる．それは，GPUはディスクファイルに直接アクセスできないからである．

表1 : Configuration parameters of Mars.

パラメータ 解説
noSort ソートが必要かどうか(もし必要なら，noSort=Fとし，そうでなければnoSort=Tとする)
noReduce Reduceが必要かどうか
tgMap Map段階でのスレッドグループの数
tMap Map段階でのスレッドグループあたりのスレッド数
tgReduce Reduce段階でのスレッドグループの数
tReduce Reduce段階でのスレッドグループのスレッド数
  • 表1はマーズのパラメータ設定について表している．
  • 例えば，Reduceの操作が必要ないのなら，noReduceをtrueとする．
実装の詳細
  • GPUはコード実行中の動的メモリ確保をサポートしていないため，著者らはメインのデータ構造として配列を利用した．
  • 入力データや中間出力データ，最終的な結果のデータは，それぞれ3つの配列に保存される．
  • それらはすなわち，Key Array, Value array, 及びdirectory Indexである．
  • Directory Indexはのエントリーで構成されている．
  • 配列構造を利用しているため，利用者は入力データ及び出力データ用の配列をGPUプログラム実行前に用意しておく必要がある．
  • しかし，これらMapやReduceの出力サイズは分からない．
  • さらに，大量のスレッドが同時に書き込むため，共有の出力配列への書き込みが衝突してしまう可能せいがある．
  • これは，GPU自体がアトミックな操作やロック機構等をサポートしていないからである．
  • これらの問題を解決するため，ロックフリーな仕組みを著者らは過去に作成した[16]．

最適化のテクニック

メモリ最適化
  • メモリへ効率よくアクセスするために，次の2つの方法を使った
  • Coalesced Accesses（Coalesced:合体する，一体化する)
    • Map段階において，スレッドがT個あり，合計のKey/ValueペアがN個の場合を考える．
    • スレッドiは(i + T・k)番目のKey/Valueペアを処理する．(k = 0,1,,,N/T)

  • build-in vector型を用いたアクセス
    • デバイスメモリにある値へとアクセスするのはコストがかかる．
    • それは，データのサイズがそれぞれ違い，一緒にアクセスするのが難しくなるからである．
    • G80などのGPUにはchar4型やint4型といったbuild-in vector型が存在している．
    • Build-in Vectorは一回のメモリリクエストでベクター全体をとってくる事ができる．
    • Char型やint型とくらべて，メモリアクセス時の性能があがる．
Marsにおける他の最適化テクニック
  • Thread parallelism
    • スレッドグループの数やスレッドグループあたりのスレッド数を設定できる．
    • これらの値はさまざまな要因と関係してくる．
    • MapとReduceの処理は開発者が作るものなので，処理コストを見積もることはできない．
    • CUDAはoff-line calculator[23]というものを提供している．
    • このcalculatorはスレッドグループあたりのスレッド数や，スレッドあたりのレジスタ利用数を入力として，マルチプロセッサあたりのスレッドグループのアクティブスレッドの数を出力してくれる．
  • 可変長型の取扱い
    • 可変長型はdirectory indexをサポートしている．
    • もし，Key/valueペアを交換する場合は，Key/Valueのデータ自体を変えずに，このdirectory indexを変えるだけでよい．
    • 文字列は典型的な可変長型であり，ウェブデータの解析などによく使われる．
    • 著者らは，GPU上での文字列制御ライブラリを作成した．
    • 実装した関数はstrcmp,strcat,memset等である．
  • ハッシング
    • ハッシングはソートアルゴリズムの際に，同じキーの値をまとめる際に利用する．
    • データをソートする際は，まずハッシュ値を求めて，ハッシュ値の比較を行う．
    • もしハッシュ値が等しかった場合のみ，値の比較を行う．
  • ファイル制御
    • GPUはハードディスクのデータへ直接アクセスを行うことができない．
    • よって，ファイル制御をするためにはCPUを使って以下の3つの作業を行う必要がある．
      • (1)データをメインメモリ上にロードする
      • (2)ロードしたデータを処理してKey/Valueペアを取得する
      • (3)取得したKey/ValueペアをGPUのデバイスメモリにコピーする

実験

実験への準備
  • 実験にはGPU:G80, CPU:Intel Core2 Quad,OS:Fedora7.0 を利用する
  • メインメモリは2GB, GPUのデバイスメモリは768MB
  • MarsとPhoenix[27]との性能を比較する
  • 著者らはMarsをCPU上でも動かした
  • CUDAには __host__ __device__と関数につけると，CPU上でコードを動かすことができる
  • MarsではソートのアルゴリズムにGPU上で実装したバイトニックソートを用いた[16]
  • CUDAライブラリ[24]にあるprefix sum implementationを用いた．
  • アプリケーション
    • 著者らはMapReduceフレームワーク評価のため，6つのウェブデータ解析用のアプリケーションを実装した
    • 実装したアプリケーションの詳細は以下のとおりである．
    • データはS,M,Lの3つを用意した．
アプリケーション 解説 データセット
String Match ファイル中の文字列の場所を見つける S:32MB, M:64MB,L:128MB
Inverted Index HTMLファイルにおける逆インデックスを作成する S:16MB, M:32MB, L:64MB
Similarity Score ドキュメント集合中で似たようなペアを求める #doc: S:512, M:1024, L:2048. #feature dimension:128
Matrix Multiplication 2つの行列を掛ける #dimension: S:512, M:1024, L:2048
Page View Count ウェブログからページ参照回数をカウントする S:32MB, M:64MB, L:96MB
Page View Rank ウェブログから上位10位までのよく参照されているページを抜き出す S:32MB, M:64MB, L:96MB
文字列ライブラリの結果

  • 図4はC/C++とMarsにて実装した文字列ライブラリを，CPUとGPUにて実行した結果である．
  • non-optとoptの違いは，データ型をcharとchar4を使ったものとの違いである
  • GPU(opt)では，CPU実装より2倍から9倍高速化している．
Marsの結果

  • 図5は最適化したMarsとPhoenixとの比較結果である．
  • Marsのほうが1.5倍から16倍高速化している．

  • 図6は，MapやReduce等，それぞれの段階での実行時間を表したものである．
  • Map段階の結果は，入力データをデバイスメモリに読み込む時間も含まれている
  • Reduce段階の結果は，結果をメインメモリにコピーする時間も含まれている

  • 図7はCoalesced Accessを使った際のパフォーマンス向上率を表している

  • 図8はハッシングを使った際のパフォーマンス向上率を表している

  • 図9はbuild-in vector型を使った際のパフォーマンス向上率を表している
Multi-Core CPUの結果

  • 図10はMarsをCPU上で動かしたものと，Phoenixとを比較したものである．
  • MarsはCPU上で実行しただけでもPhoenixより早い

  • 図11はGPU上で実装したMarsとCPU上で実装したMarsとの性能比較である．
  • CPUベースのものよりも3.9倍早くなっている

まとめと今後の課題

  • GPUは用意に手に入る並列計算用デバイスである
  • GPUを使うためにはGPUのアーキテクチャに関する知識が必要である
  • ウェブデータ解析などをGPUで行うのは大変複雑である
  • MapReduceはウェブ解析等を簡単に作ることができる
  • MapReduceをGPU上で実装することを著者らは提案
  • GPUの仕組みを知らなくてもGPU上でのプログラム開発が可能
  • さらに，MapReduceを使うことでCPUベースのMapReduceよりも16倍高速化できた
  • 今後の課題は以下のとおりである
    • (1)扱うデータ量はGPUのデバイスメモリよりも少なくないといけない．今後はデバイスメモリよりも多いデータを扱えるようにする
    • (2)MapReduceをBrook+を使ってAMD GPUでも実装予定である．AMDとNVIDIA GPUとのデザインや実装の違いを調査することも興味深いことである．
    • (3)CPUとGPUを組み合わせたMapReduceを研究中である

Marsの問題点(nishioが追加)

  • GPUのデバイスメモリより大きなデータを扱うことはできない
  • Map段階,Reduce段階の出力するデータ量をあらかじめ予測できない場合には，Marsを使うことができない
参考文献

[1] A. Ailamaki, N. K. Govindaraju, S. Harizopoulos, and D. Manocha. Query co-processing on commodity processors.
In VLDB ’06: Proceedings of the 32nd international conference on Very large data bases, pages 1267–1267.
VLDB Endowment, 2006.
[2] AMD CTM. http://ati.amd.com/products/streamprocessor/, 2007.
[3] Apache Hadoop. http://lucene.apache.org/hadoop/, 2006.
[4] D. Blythe. The direct3d 10 system. ACM Trans. Graph.,25(3):724–734, 2006.
[5] I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian,M. Houston, and P. Hanrahan. Brook for gpus: stream
computing on graphics hardware. ACM Trans. Graph.,23(3):777–786, 2004.
[6] B. Catanzaro, N. Sundaram, and K. Keutzer. A map reduce framework for programming graphics processors.
In Workshop on Software Tools for MultiCore Systems, 2008.
[7] H. chih Yang, A. Dasdan, R.-L. Hsiao, and D. S. Parker.Map-reduce-merge: simplified relational data processing on
large clusters. In SIGMOD ’07: Proceedings of the 2007 ACM SIGMOD international conference on Management of
data, pages 1029–1040, New York, NY, USA, 2007. ACM.
[8] C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun. Map-reduce for machine learning on multicore.
In NIPS ’07: Proceedings of Twenty-First Annual Conference on Neural Information Processing Systems.
Neural Information Processing Systems Foundation, 2007.
[9] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1):107–113, 2008.
[10] J. Feng, S. Chakraborty, B. Schmidt, W. Liu, and U. D. Bordoloi. Fast schedulability analysis using commodity
graphics hardware. 13th IEEE International Conference on Embedded and Real-Time Computing Systems and
Applications, 2007.
[11] Folding@home. http://www.scei.co.jp/folding, 2007.
[12] N. Govindaraju, J. Gray, R. Kumar, and D. Manocha. GPUTeraSort: high performance graphics co-processor
sorting for large database management. In SIGMOD ’06: Proceedings of the 2006 ACM SIGMOD international
conference on Management of data, pages 325–336, New York, NY, USA, 2006. ACM.
[13] N. Govindaraju, B. Lloyd, W. Wang, M. Lin, and D. Manocha. Fast computation of database operations using
graphics processors. In SIGMOD ’04: Proceedings of the 2004 ACM SIGMOD international conference on
Management of data, pages 215–226, New York, NY, USA, 2004. ACM.
[14] M. Harris, J. Owens, S. Sengupta, Y. Zhang, and A. Davidson. Cudpp: Cuda data parallel primitives library.2007.
[15] B. He, N. K. Govindaraju, Q. Luo, and B. Smith. Efficient gather and scatter operations on graphics processors.
In SC’07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing, pages 1–12, New York, NY, USA, 2007. ACM.
[16] B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander. Relational joins on graphics processors. In
SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 511–524, New York, NY, USA, 2008. ACM.
[17] D. Horn. Lib GPU FFT, 2006.
[18] C. Jiang and M. Snir. Automatic tuning matrix multiplication performance on graphics hardware. In PACT ’05:
Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, pages 185–196,
Washington, DC, USA, 2005. IEEE Computer Society.
[19] E. S. Larsen and D. McAllister. Fast matrix multiplies using graphics hardware. In Supercomputing ’01: Proceedings of
the 2001 ACM/IEEE conference on Supercomputing (CDROM), pages 55–55, New York, NY, USA, 2001. ACM.
[20] M. D. Linderman, J. D. Collins, H. Wang, and T. H. Meng. Merge: a programming model for heterogeneous multi-core
systems. In ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for
programming languages and operating systems, pages 287–296, New York, NY, USA, 2008. ACM.
[21] W. Liu, B. Schmidt, G. Voss, and W. Wittig. Streaming algorithms for biological sequence alignment on gpus. IEEE Transactions on Parallel and Distributed Systems, 18:1270–1281, 2007.
[22] H. Nguyen. GPU gems 3. Addison-Wesley, 2008.
[23] NVIDIA Corp. . CUDA Occupancy Calculator, 2007.
[24] NVIDIA CUDA. http://developer.nvidia.com/object/cuda.html, 2007.
[25] OpenGL. http://www.opengl.org/, 2007.
[26] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26, 2007.
[27] C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis. Evaluating mapreduce for multi-core and multiprocessor systems. In HPCA ’07: Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, pages 13–24, Washington, DC, USA, 2007. IEEE Computer Society.

GPUへのMapReduceの適用に関する調査

研究

概要

近年、GPUの性能は飛躍的に向上しており、グラフィック専用の処理装置としてではなく、数値計算等の汎用向けの処理に利用する、GPGPUに関する研究が盛んに行われている。GPUは内部に多くのコアを備えており、NVIDIA社のGeForce GTX 580では、512個ものコアを保持している。これらのコアすべてを効率よく利用することで、GPUの持っている高いパフォーマンスを引き出すことが出来るが、GPUの高い並列性を利用するためにはGPU特有の処理を実装する必要があり、GPUプログラミングになじみの無い利用者にとっては処理の記述が困難である。

そこで、GPUを大量のコアを持ったプロセッサだと考え、これらに対してMapReduceを適用することを検討する。親しみやすいMapReduceインターフェースにあてはめて処理を記述するだけで、GPUの高い並列性を生かしたプログラムが実装可能となる。加えてGPUに関して深い知識が無くても、用意に性能を引き出すことができるようになる。

MapReduceについて

MapReduce[1]は、巨大なデータを複数の計算機を使って並列分散処理させるフレームワークであり、Googleが検索エンジンのインデックス作成等、巨大なデータを処理するために考案されたアルゴリズムである。MapReduceでは、map関数とreduce関数を定義するだけで、大規模データの並列処理が可能となるシンプルなアルゴリズムである。また、計算機の台数に応じて性能が直線的にスケールするといった特徴を備えている。

MapReduceが得意、不得意とする分野を以下に示す。

得意な分野

  • 大量データ（数百Mバイト以上）の処理
  • バッチ処理

不得意な事

  • 小さなデータの処理
  • インタラクティブな処理

MapReduceは、データ処理の信頼性をハードウェアではなくソフトウェアで補うアルゴリズムである。従来の大量のデータを処理する方法としては、ハードウェアの性能を高める方法（スケールアップ）や、MPI, CORBA等を利用する方法が考えられる。
ハードウェア性能を上げる方法は、コストがかかるという問題がある。また、スケールアップよりもスケールアウト（安価なコンピュータを大量に利用）するほうが性能が高く，コストも抑えられるという調査報告がある。MPIやCORBAを利用する場合は、データの分散化に関しては自分で考えて実装する必要があり、プログラマ側の負担が大きいという問題点がある。

MapReduceが適用可能な分野に関する研究はまだ始まったばかりであるため、どのような分野に適用できるかは分かっていない。Chu[2]らは、マルチコアプロセッサ上にMapReduceを実装し、機械学習を行った。16プロセッサを利用すると，おおよそどの学習も1コアを使った学習より8倍から16倍まで性能が上げることができた。Lin[3]らは、MapReduceをグラフアルゴリズムに適応させた。ダイクストラ法のようなグラフアルゴリズムにはMapReduceは適用しにくいことを指摘し、幅優先探索等が適応可能であることを示した。

GPUでのMapReduceの実装

A Map Reduce Framework for Programming Graphics Processors[4]

Catanzaroら[4]は、CUDAを利用してGPU上でのMapReduceの実装を行った。Catanzaroらは、SVM(Support Vector Machine)にGPUを用いたMapReduceを適用した所、CPUのみで実装した処理よりも32倍から150倍スピードアップを達成することができた。彼らは、MapReduceにあてはめるだけで簡単にGPUを用いた並列処理が可能であったとし、MapReduceのモデルはGPU上での並列計算にも適しているとしている。

Catanzaroらの実装には各map関数は単一のKey/Valueペアしか出力ができないという制約が存在している。加えて、GPUプログラミングの仕組みを隠すようなフレームワーク作成を目的としておらず、性能を引き出すためにはGPUのメモリ階層に関する知識が必要であるとしている。MapReduceをGPUへ適用するのは、GPUプログラミングの複雑さを隠すためであり、Catanzaroらの実装はMapReduceの良さを十分に生かし切れていないフレームワークとなっている。


Mars: A MapReduce Framework on Graphics　Processors[5]

Mars[5]は、CUDAを用いたGPUによるMapReduceの実装である。GPUでの複雑なプログラミングを行うことなく，親しみやすいMapReduceインターフェースを使ってプログラムが可能であるとしている。MarsではQuad Core CPU上でのMapReduce実装より最大16倍高速化できたとしている。

著者らの目指すシステムは以下の通りである。

  • 簡単にプログラミングができること
  • 高性能なこと

Marsでは，MAP_COUNT, MAP, REDUCE_COUNT,REDUCEの4つの関数をユーザが定義する。MAP_COUNT, REDUCE_COUNT関数では出力されるデータ量を定義する。これは、GPUではあらかじめ出力されるデータ量を指定しておかなければならない制約の為である。Marsでは、データのロックを行わなくても書き込みが衝突しないような仕組み[7]を採用している。

Marsでは、データ処理にCPU(Mars Scheduler)とGPUの両方を用いる（図1)。データ処理の流れは以下の通りである。
1. 入力するKey/Valueのペアをメインメモリ上の配列に配置する (CPU)
2. run-time設定のパラメータの初期化を行う (GPU)
3. メインメモリ上の入力データ配列をGPU上のデバイスメモリへとコピーする (CPU)
4. GPU上にてMapを開始し，中間Key/Valueペアを配列へと保存する (GPU)
5. もしnoSortがF(False)ならば，中間データをソートする (GPU)
6. もしnoReduceがFならば，GPU上にてReduceを行い，結果を出力する．そうでなければ，中間データを最終的な結果として出力する (GPU)
7. 結果をGPUのデバイスメモリからメインメモリへコピーする (CPU)


図1: Marsでの処理の流れ([5] Fig2より引用)

Marsでは、デバイスメモリより大きなデータを扱うことができないといった制約が存在する。またMap段階,Reduce段階の出力するデータ量をあらかじめ予測できない場合には、Marsを利用することができない。


DisMaRC: A Distributed Map Reduce framework on CUDA[6]

DisMaRCはCUDAとMPIを組み合わせたMapReduce実装(図2)である。


図2: Dismarkの処理の流れ([6] Fig2より引用)

Marsと同じく、MAP_COUNT, REDUCE_COUNT等が必要である。DisMaRCでは、Marsとの処理速度を比較しており、Marsよりも処理を高速化できたとしている。しかし、それほど速くなっているようには思えず、結果は微妙である。
Marsと同じく、Map段階、Reduce段階での出力するデータ量をあらかじめ予測できないような問題にはDisMaRCを利用することができない。加えてソートするデータを１つのマスターノードに集めるので、性能がスケールしない可能性が存在する。また、Fault Toreranceについては考えられていない。

まとめ

Catanzaroらの実装、Mars、及びDisMaRCの比較を下図に示す。

GPUへのMapReduceの適用について、親しみやすいMapReduceインターフェースにあてはめた処理を記述するだけで、高い処理性能を引き出すという点においては、まだまだ改良の余地があると考えられる。Marsに関しては、CUDAでの実装が著者らのWebサイト(http://www.cse.ust.hk/gpuqp/Mars.html)にて公開されているので、興味のある方はMarsの改良を試みてみるのも面白いかと思う。


参考文献

[1] Jeffrey Dean, Sanjay Ghemawat, ”MapReduce:Simplified Data Processing on Large Clusters”, OSDI 2004.
[2] Cheng-Tao Chu, Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary R. Bradski, Andrew Y. Ng, Kunle Olukotun. "Map-Reduce for Machine Learning on Multicore" In Proceedings of NIPS'2006. pp.281~288
[3] Jimmy Lin, Chris Dyer, "Data-Intensive Text Processing with MapReduce", http://www.umiacs.umd.edu/~jimmylin/book.html (2011-09-11 accessed)
[4] Bryan Catanzaro, Narayanan Sundaram and Kurt Keutzer "A Map Reduce Framework for Programming Graphics Processors", In Workshop on Software Tools for MultiCore Systems, 2008.
[5] Bingsheng He, Wenbin Fang, Qiong Luo, Naga K.Govindaraju, and Tuyong Wang "Mars: A MapReduce Framework on Graphics Processors", PACT 2008.
[6] Alok Mooley, Karthik Murthy, Harshdeep Singh, DisMaRC "A Distributed Map Reduce framework on CUDA", 2009.
[7] B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander: "Relational joins on graphics processors". In SIGMOD, 2008.