2009年11月25日水曜日

巨大データのソーティング

超巨大なデータのソーティング研究. 特に Sort Benchmark では、Hadoop が頑張っている

SPsort: How to Sort a Terabyte Quickly, Jim Wyllie,
http://sortbenchmark.org/SPsort.pdf

Sort Benchmark Home Page(originally known as Terabyte Sort Benchmark)
http://sortbenchmark.org/

2009年11月18日水曜日

SVD の C実装と実行時間の内訳

StreamGPU の SVD (特異値分解)に関して。

とりあえず、森田君の SVD の CUDA 版移植に向けて、newmat (C++ベース) ではなく、C ベースの SVD を Numerical Recipes を参考に書いて実行してみました。上のグラフは、正方行列の 128 から 1024 までの実行時間の遷移です(newmat と比べてみたいですね)

また、実行時間の内訳を知るべく、1024 x 1024 の行列サイズの時の各ステージにおける割合を円グラフにしてみました。単位は秒で、Tesla で測定した結果です。思った以上に、各ステージがそれなりにかかっているので、一部分を CUDA に移植するだけではなかなか高速化できなさそうですね。


2009年11月16日月曜日

オンライン障害検知手法

Web 系システムからの特徴抽出とオンライン障害検知手法
井手剛
http://www.research.ibm.com/trl/people/ide/2004_IBIS_Ide.pdf

I-SVD の実装

http://www-is.amp.i.kyoto-u.ac.jp/lab/isvd/download/
にて I-SVD の実装を配布しているが、バイナリのみ。ソースコードが配布されていないのが残念
マルチコア環境において、OpenMP および pThread を用いて並列化している。

CUDA Profiler

CUDA Profiler の使い方に関しては、
http://gpu.fixstars.com/index.php/CUDA_Profiler%E3%82%92%E4%BD%BF%E3%81%86
に書いてありますね。森田君、チェックしてください。

------- 特にカーネル実行時のイベントは4つまでしか取れないことに注意

カーネル起動に関する情報は以下のものがあります。
  • timestamp : カーネル起動時のタイムスタンプ
  • gridsize : 起動したブロックの数
  • threadblocksize : 起動したスレッドの数
  • dynsmemperblock : 動的に割り当てられたsharedメモリのサイズ
  • stasmemperblock : 静的に割り当てられたsharedメモリのサイズ
  • regperthread : スレッドごとのレジスタ数
  • memtransferdir : cudaMemcpyのコピー方向(0: host->device, 1:device->host)
  • memtransfersize : cudaMemcpyのサイズ
  • streamid : カーネルを起動したstreamのid


カーネル実行時のイベントは以下のものがあります。これらは同時に4つまでしか設定できません。

  • gld_incoherent : コアレスされなかったメモリロードの回数
  • gld_coherent : コアレスされたメモリロードの回数
  • gld_32b : 32-byte ロードした回数
  • gld_64b : 64-byte ロードした回数
  • gld_128b : 128-byte ロードした回数
  • gld_request : グローバルメモリからロードした回数
  • gst_incoherent : コアレスされなかったメモリストアの回数
  • gst_coherent : コアレスされたメモリストアの回数
  • gst_32b : 32-byte ストアした回数
  • gst_64b : 64-byte ストアした回数
  • gst_128b : 128-byte ストアした回数
  • gst_request : グローバルメモリにストアした回数
  • local_load : ローカルメモリからロードした回数
  • local_store : ローカルメモリにストアした回数
  • branch : 分岐した回数
  • divergent_branch : 分岐によってワープを分割した回数
  • instructions : 実行した命令数
  • warp_serialize : バンクコンフリクトによってシリアライズされた回数
  • cta_launched : 起動したスレッドブロックの数

2009年11月14日土曜日

東京医科歯科大学とのミーティング

小長谷先生と東京医科歯科大学の先生方、そしてオミックス医療学養成プログラムを受講されている方々と I2B2 (ハーバードが実装した Web ベースのデータベース)サーバー設置に関するミーティング。
VMWare ベースでイメージがあり、基本的にはそれを置くだけ。マシンのスペックが、メモリが 1GB しかないのが心配ですね。

Cutting the Electric Bill for Internet-Scale Systems

Cutting the Electric Bill for Internet-Scale Systems
http://ccr.sigcomm.org/online/files/p123.pdf

SIGCOMM2009の論文。まだちゃんと読んでいないが、非常に面白そうだ。

Energy expenses are becoming an increasingly important
fraction of data center operating costs. At the same time,
the energy expense per unit of computation can vary significantly
between two different locations. In this paper,
we characterize the variation due to fluctuating electricity
prices and argue that existing distributed systems should be
able to exploit this variation for significant economic gains.
Electricity prices exhibit both temporal and geographic variation,
due to regional demand differences, transmission inefficiencies,
and generation diversity. Starting with historical
electricity prices, for twenty nine locations in the US, and
network traffic data collected on Akamai’s CDN, we use simulation
to quantify the possible economic gains for a realistic
workload. Our results imply that existing systems may be
able to save millions of dollars a year in electricity costs, by
being cognizant of locational computation cost differences.

2009年11月13日金曜日

NS2: ネットワークエミュレータ

ネットワークエミュレーターNS2 :帯域幅やレイテンシをコントロールする
http://www.isi.edu/nsnam/ns/

プロセスの CPU 使用率をコントロールするプログラム

CPU の使用率をコントロールする Linux プログラム

http://cpulimit.sourceforge.net/

例えば、bigloop という実行プログラムを 40% の CPU 使用率に抑えたい場合には、
% cpulimit --exe bigloop --limit 40
とする。

また、プロセス ID として 2960 のプログラムを 55% の CPU 使用率にするには、
% cpulimit --pid 2960 --limit 55

ROCKS

松浦君の努力のおかげで、やっと、NPACI の ROCKS のインストール画面が起動しはじめました。





2009年11月12日木曜日

Fermi

Fermi に関する詳しい記事
http://www.realworldtech.com/page.cfm?ArticleID=RWT093009110932&p=2

大学院講義演習

徳田研の方2名、秋山研の方1名、村田研の方1名、合計4名が参加してくれました。
松浦くん、老木くん、お疲れ様でした。





2009年11月10日火曜日

EDBT2010: 13th International Conference on Extending Database Technology

http://lbd.epfl.ch/EDBTICDT/edbt-cfp.html

EDBT2010: 13th International Conference on Extending Database Technology

大体9月ぐらい
  • Research paper abstract submission: September 8, 2009, 11:59 pm PST (Pacific standard time)
  • Research Paper submission: September 15, 2009, 11:59 pm PST

2009年11月6日金曜日

Eucalyptus を活用したクラウド環境構築

クラウド研究会で「Eucalyptus を活用したクラウド環境構築」という講演を聞いてきました。


以下、トークのメモ。全く整理されていませんが。。。
-----------------------
- Iaas を実現する Amazon EC2 と互換性を持つオープンソースソフトウェア
- プライベートクラウド構築用
- Amazon EC2 互換とのインタフェースを持つメリット
- API 互換なため、ハイブリッドクラウドの実現が容易に
- RightScale は Amazon EC2 と Eucalyptus 双方に対応
- ライセンスは GPL v3
- 2009/11/05 現在のバージョンは V1.6.1. 09/1/1 の Amazon EC2 の仕様を満たす
- v1.5.2 のバグなどは fix. CLC と CC を同じノードに同居しなければいけなかったが、
   v1.6.1 では解消された
- v1.6.1 は 1.x では最終。これからは 2.x
- Ubuntu 9.10 に Eucalyptus が含まれている
- Eucalyptus の構成
- 3レイヤからなる。
- CLC, (Cloud Controller), CC (Cluster Controller), NC (Node Controller)
- CLC (クラウドコントローラ) :
- 下位のコントローラを制御するスーパースケジューラーみたいな位置づけ
- 簡易的な GUI を提供。ElasticFox から操作可能. ユーザーが VM を作る。IP アドレスが返ってくる
- インタフェースは SOAP, REST をサポート
- CC (Cluster Contoller)
- NC の状態監視 (NC の CPU コア数、メモリ使用量、ディスク使用量)
- スケジューリング .
状態監視につき、インスタンスをどの NC で実行するかを選択
以下のノード。GREEDY(順に割り当てる), ROUNDROBIN, POWERSAVE (VM が立ち上がっていないノードは落とす)
- 1秒単位で NC のリソースステータスを確認している。NC のスケーラビリティ
(Q) NC の数はスケールするか?
- SC というのがある: Storage Contoller: Walrus からイメージ、データを配る

  - NC (Node Contorller):
- insutans (VM)を管理する
- Hypervisor は KVM や Xen をサポート
- 6台、96VMぐらいまでは行ける?と、海外のベンダーは言っていた

- Walrus : Amazon のストレージサービス。S3 と互換性を持つ
- インスタンス(VMのイメージ)をマシンイメージの保管場所

- EBS (Elastic Block Store): アプリケーションやデータを保管する

- CLC, CC の負荷が高い。CLC からイメージ(数GB) がNCに配られ, かつ NC から CC, CLC へネットワーク
 が流れるので、非常に負荷が高い

- プライベートクラウド検証環境の検証
- Xen CentOS 5.3 を仕様
- Eucalyptus のモード. SYSTEM, STATIC, MANAGED, MANAGED-NOVLAN. =-> MANAGED モードを使用
- 1.5.1 スイッチポートでタグVLAN をサポートする必要があった

- v1.5.1 で発生した問題点
- MAC アドレス重複による不具合。
- CPU コア数がインスタンス数の上限? Xeon 4 core, だと4インスタンスだったが、
 Eucalyptus の設定ファイルで、その上限値を変更可能
  - EBS の不具合
- CC がいなくなると、NC の情報がすべてなくなる。冗長化できない。
- 課金の機能などもない。
- v.1.6.1 で一部は解決

- CSK システムズ社で、Eucalyptus をらっぷんぐした自動化基盤 (PaaS)を開発
- Web ブラウザ上から、仮想マシンの追加、削除、起動、停止、仮想マシンの一覧表示を行う
- Web 3層構造 Load Balancer,Web サーバー, DB サーバーを作る
- それぞれのVMインスタンスを用意し、それを追加し、各仮想サーバーを起動
- 外部 Disk (EBS) をアタッチする
- AppScale (Google App Engine のクローン?)が存在

- 最新バージョン v1.6.1
- 複数クラスタ環境をサポート
- Dynamic DNS をサポート。
- オープンソースの監視ツールでステータス確認が可能に。Ganglia と Nagios

- Eucalyptus での開発環境での活用を促進させる

- クラスタ単位は、VLAN という単位。管理の単位

- EMI (Eucalyptus の仮想イメージ)と AMI (Amazon 用) との互換性はない、変換ツールはない

- SLA は保障されるのか? Eucalyptus だけでは無理
- Eucalyptus のみでは商用化は難しい。何か加えないと駄目
- Monitoring の機能とかは商用レベルではない

ベンチマーク

ストリーム用ではないですが、以下のベンチマークに関する論文があります。DSMS 用のベンチマークは以前も書いたと思いますが、Linear Road Benchmark の論文以外はなく、Twitter を含めた様々なデータ特性、性能特性を持つアプリケーションを何種類か用意すれば、論文が一つ書けるでしょう。

A Benchmark Suite for Unstructured Data Processing
Clinton Wills Smullen, University of Virginia
http://www.cs.virginia.edu/~gurumurthi/papers/snapi07.pdf

Rodinia: A Benchmark Suite for Heterogeneous Computing,
IISWC 2009 (IEEE International Symposium on Workload Characterization)
http://www.cs.virginia.edu/~skadron/Papers/rodinia_iiswc09.pdf

次の実験

森田君が、タスク並列を実現できたようです。素晴らしい。
次は左のような実験を Cまたは UDOP でやってみましょう。






Cell Processor 上の 特異値分解高速化

森田君、必見。

Cell 上で SVD を高速化した論文(というか授業の課題?)があるようです。
論文: http://www.mc2.umbc.edu/docs/georgalas-araim.pdf
コード: http://code.google.com/p/cellsvd

ICDCS 2010(The 30th International Conference on Distributed Computing Systems )

ICDCS 2010(The 30th International Conference on Distributed Computing Systems )
http://icdcs2010.cnit.it/

Genoa (Italy) 2010年6月開催。我々と関係するとしたら、以下の2つのトピックでしょうか。

Topics of particular interest include, but are not limited to:

  • Algorithms and Theory
  • Data Management and Data Centers
  • Distributed Cyber-Physical Systems
  • Distributed Operating Systems and Middleware
  • Fault Tolerance and Dependability
  • Network/Internet Protocols and Applications
  • Privacy and Security
  • Sensor Networks and Ubiquitous Computing
  • Wireless and Mobile Computing
Paper Submission
Extended to November 25, 2009 - 12:00 pm, Hawaii time (GMT -10)
Author NotificationFebruary 8, 2010
Final Manuscript Due
March 15, 2010

PACT 2010 (Parallel Architectures and Compilation Techniques)

Parallel Architectures and Compilation Techniques (PACT)
Vienna, Austria, September 11-15, 2010

http://www.pactconf.org/

Abstract Submission March 20
March 27 Paper Submission, Workshop and Tutorial Proposal
Sept. 11-1Workshops and Tutorials
Sept. 13-15 Conference

トピックは以下。
  • Parallel architectures and computational models
  • Multicore, multithreaded, superscalar, VLIW and GPU architectures
  • Scalability and system architecture for parallel systems
  • Compilers and tools for parallel computer systems
  • Compiler exploitation of data- and thread-level parallelism
  • Generating parallel code for domain-specific languages
  • Support for concurrency correctness in hardware and software
  • Compiler/hardware support for managing memory hierarchies
  • Hardware and software support for power/heat-aware parallel computing
  • Parallel accelerators and reconfigurable computing
  • Dynamic translation and optimization for parallel systems
  • I/O issues in parallel computing and their relation to applications
  • Parallel programming languages, algorithms and applications
  • Middleware and run-time system support for parallel computing
  • Reliability and fault tolerance for parallel systems
  • Modeling and simulation of parallel systems and applications
  • Parallel applications and experimental systems studies
  • Case studies of parallel systems and applications
  • Non-traditional parallel computing systems topics

2009年11月4日水曜日

複数カーネル実行 on GPU

タスク並列を現在の CUDA でどのように効率的に行うかを論じた論文です。森田君の研究テーマに非常に関連しています。

PACT 2009 で行われたワークショップで発表された論文
First Workshop on Programming Models for Emerging Architectures (PMEA)

Marisabel Guevara, Enabling Task Parallelism in the CUDA Scheduler
http://www.cs.virginia.edu/~skadron/Papers/guevera_pmea09.pdf

以下、概要。
General purpose computing on graphics processing units (GPUs) introduces the challenge of scheduling task parallel workloads on devices designed for data parallel applications. This paper analyzes the problem, and presents a method for merging workloads such that they can be run concurrently on an NVIDIA GPU. Some kernels do not fully utilize the processing power of the GPU, and thus overall throughput will increase when running two kernels alongside one another. Our approach scans a queue of independent CUDA kernels (i.e., code segments that will run on the GPU), across processes or from within the same process, and evaluates whether merging the kernels would increase both throughput on the device and overall efficiency of the computing platform. Using kernels from microbenchmarks and a Nearest Neighbor application we show that throughput is increased in all cases where the GPU would have been underused by a single kernel. An exception is the case of memory-bound kernels, seen in a Nearest Neighbor application, for which the execution time still outperforms the same kernels executed serially by 12-20%. It can also be benefitial to choose a merged kernel that over-extends the GPU resources, as we show the worst case to be bounded by executing the kernels serially. This paper also provides an analysis of the latency penalty that can occur when two kernels with varying completion times are merged


また、NVida の Forum には、複数カーネル実行の議論が書かれています。
http://forums.nvidia.com/index.php?showtopic=84740

2009年11月2日月曜日

SIGMOD 2010

http://www.sigmod2010.org/index.shtml

SIMGOD2010 のスケジュールは以下のようでした。 来年6月にインディアナポリスで開催されるそうです。 論文投稿のスケジュールが WWW と完全に重なっていますね。

October 29, 2009: Abstract submission (research papers only) 11:30PM PST
November 5, 2009: Manuscript submission (research papers, industrial papers, demonstration proposals) 11:30PM PST
December 3, 2009: Tutorial and Panel proposals submission
February 15, 2010: Notification of acceptance
March 15, 2010: Final camera-ready papers due, 9AM EST

ICDE 2011

論文投稿は毎年6月頃. ICDE 2010 は 3月に Los の Long Beach.

昨年は以下のようなスケジュールだったようです。
Abstract submission deadline: June 10, 2009; 11:00 pm PST (research papers only)
Full paper submission deadline: June 17, 2009; 11:00 pm PST
Author feedback time window: August 4-10, 2009 (research papers only)
Notification of authors date: September 9, 2009
Camera-ready versions due: October 19, 2009

CBI 学会@韓国

CBI 学会 (Chem-Bio Infomatics Society: 情報計算化学生物学会) が明日から開催され、松浦君がポスター発表をします。彼にとって初の英語による学会発表ですので、大変だとは思いますが、頑張ってくださいね。発表ネタは、StreamDNA です。

WWW 2010 に論文提出完了

WWW 2010 (http://suzumura-lab.blogspot.com/2009/10/www-2010-cfp.html) になんとか金曜日から4日連続で書き続け、submit まではこぎつけました。