Agile Cat — in the cloud

Facebook が Timeline をデザインしていく発想は、いったい何処から湧き上がってくるのか?

Posted in .Selected, Big Data, Facebook by Agile Cat on January 18, 2012

How Facebook built its Timeline feature
http://wp.me/pwo1E-3P0
By
Stacey Higginbotham Jan. 5, 2012, 1:06pm
http://gigaom.com/cloud/how-facebook-built-its-timeline-feature/

_ Gigaom

Facebook’s Timeline feature is beautiful, although some revile it. But love it or hate it, Timeline is the engineering equivalent of building a racing bike customized for a specific track, only without testing either until race day. At least that’s how Ryan Mack, an infrastructure engineer with Facebook, makes it seem on a blog posted Thursday detailing how Facebook engineered its Timeline feature.

Facebook の Timeline は素晴らしいが、悪口を言う人もいる。 好き嫌いもあるが、Timeline のエンジニアリングは、特定のサーキットにカスタマイズされたレーシング・バイクの開発に等しい。ただし、テストは行われず、ぶっつけ本番でレースに臨んでいる。少なくとも、Facebook のインフラ・エンジニア Ryan Mack にとって、それが彼のやり方のようだ。木曜日(1/5)にポストされたブログが、どのように Facebook Timeline 機能がデザインしたのを、詳述しているように思える。  

Making a legacy MySQL database faster.

クリックで拡大 ⇒

The blog post also offers a ton of data on how Facebook dealt with petabytes of user data stored in legacy MySQL systems on slow disks that could make Timeline less responsive. The company implemented a new architecture that separates out older data to slower disk storage and keeps more recent and more accessed data stored in flash drives and cached using memcached. From the blog:

そして、このブログ・ポストでは、Timeline の反応を遅くしてしまう、低速ディスク上のレガシー MySQL システムにストアされていたペタバイト・ユーザー・データを、Facebook が取り扱った方式についても、膨大なデータが提供されている。 Facebook は、その遅いディスク・ストレージと、従来からのデータを切り離す、新しいアーキテクチャを実装した。それは、直近にアクセスされたデータや、頻繁にアクセスされるデータを、フラッシュ・メモリ・ドライブにストアし、また、memcached にキャッシュするという方式である。以下は、そのブログからの参照である:

Before we began Timeline, our existing data was highly normalized, which required many round trips to the databases. Because of this, we relied on caching to keep everything fast. When data wasn’t found in cache, it was unlikely to be clustered together on disk, which led to lots of potentially slow, random disk IO. …A massive denormalization process was required to ensure all the data necessary for ranking was available in a small number of IO-efficient database requests.

Timeline が開始される前には、既存のデータが高度に正規化されており、対象となるデータベースとの間で、数多くのラウンド・トリップが必要とされていた。 そのような理由から、すべてをキャッシングして、高速化を図るというという手法に依存することにした。 そして、データがキャッシュ上で発見されなかったとき、きわめて低速なランダム I/O が、大量に発生する可能性のあるディスク上のデータを、探さないで済むようにした。つまり、ランキングに必要な全データが、効果的な I/O データベース・リクエストを介して、しかも、少ない呼び出し回数で得られるようにするための、大量の非正規プロセスが必要とされた。

Here’s a visual of the system
クリックで拡大 ⇒

Mack spent a lot of time detailing the challenges of denormalizing the data, which entailed getting an intern to define a custom language that would tell a compiler how to convert old data into the new format and the use of three “data archeologists” to write the conversion rules. It also required Facebook to move older activity data to slower network storage while maintaining acceptable performance. To do this Facebook, “hacked a read-only build of MySQL and deployed hundreds of servers to exert maximum IO pressure and copy this data out in weeks instead of months.”

Mack は、それらのデータの非正規化というチャレンジについて、大量の時間を費やしながら詳述してきた。そこでは、カスタム言語をインターンに定義させることまで必要になり、そこから、古いデータを新しいフォーマットにコンバートする方法を、コンパイラに伝えることになった。 さらに、そのコンバージョン規則を記述するために、3人の「データ考古学者」を採用することにもなった。 そして、受容できるパフォーマンスを維持しながら、さらに古いアクティビティ・データを、低速のネットワーク・ストレージに移動させることも必要となった。 それを実現するために Facebook は、「 MySQL のリード・オンリー・ビルドをハックし、最大の I/O プレッシャーを行使する、数百台のサーバーにディプロイした。 続いて、それらのデータのコピーを、数カ月から数週間に頻度を切り替えて、処理するようにした」。

To speed IO even further, engineers consolidated join tables into a tier of flash-only databases. Since PHP can perform database queries on only one server at a time, Mack said Facebook wrote a parallelizing query proxy that allowed it to query the entire join tier in parallel. Finally Facebook attempted to future-proof its data model, but we’ll see how far that takes it.

さらに I/O を高速化するために、エンジニアたちは複数のテーブルを、フラッシュ・メモリのみで構成されるデータベースの、1つのティアにコンソリデートしていった。 PHP によるデータベース・クエリーは、一度に 1つのサーバーのみという制限がかかるため、 Facebook では、ジョインされているティア全体をパラレルでクエリーしていく、並列化されたクエリー・プロキシーを記述したと、Mack は発言している。 Facebook は最終的に、そのデータ・モデルを future-proof にしようと試みているが、それを私たちが確認するのは、はるか未来になるだろう。

In response to a question I sent Mack, said through a spokesman, that it took Facebook two weeks to dump everyone’s old profile data from the existing system into an archive using “some off-the-shelf network attached storage.” That data was then stored on “the new servers that now power Timeline, which, at the time, were fresh and didn’t have anything hitting them from production. We did incremental updates weekly until later, when we had writes going to both systems in real time.” That’s a lot of fresh servers, although Facebook remained mum about the exact data transferred.

私からの質問に対して、Mack がスポークスマンを介して回答してきたのは、「ストレージにアタッチされた、いくつかの既製品ネットワーク」を用いて、既存システム上の古いプロファイル・データをアーカイブにダンプするのに、2週間を要したというものだった。 続いて、それらのデータは、「いまや Timeline にパワーを供給する新しいサーバーにストアされた。 なお、その時点における、それらのサーバーは、フレッシュなものであり、また、プロダクション・システムからのアクセスが皆無なものであった。私たちは、毎晩遅くまで、Weekly のインクリメタル更新を行なっていった。そして、その時には、2つのシステムに、リアル・タイムで書き込んでいった」とも伝えてきた。 たしかに、大量のフレッシュ・サーバーを用いたのだろうが、転送された正確なデータについては、Facebook は口を閉ざしたままである。

Facebook also built the Timeline aggregator to run locally on each database to avoid information traveling over the network unless that information will be displayed on the page. That’s another timesaver. It also used it’s Hip Hop code for speeding up PHP in that aggregator.

さらに Facebook は、ネットワーク上を情報が移動することを回避するために、個々のデータベース上でローカルに実行される Timeline Aggregator を構築した。 ただし、その情報がページ上に表示される場合には、この情報の移動は制約されない。 つまり、ここでも時間の短縮が図られている。 そして更に、Aggregator の PHP を高速化するために、Hip Hop コードが用いられた。

Building in parallel.

The other element of the blog that I found amazing was how Facebook apparently denormalized its data, had a product team visualizing the Timeline UI, and built a scalable back end system for everything to run on all at the same time. I’m going to call that crazy, but Mack notes that’s what kept the development time frame to a mere six months.

見たところ、Facebook がデータの非正規化を行なっているらしいという、驚くべき発見があったブログには、Timeline UI のビジュアライズと、スケーラブルなバックエンド・システムを、プロダクト・チームが常に同時に構築していたとも書かれている。 私はクレージーだと叫びたいが、Mack の方はというと、6ヶ月間の開発タイム・フレームで保持したものに過ぎないと言っている。

I asked Facebook about what it learned during that process, because I imagine a lot of other sites would love to be able to develop their front and back end systems in parallel and save the cost of replicating their entire production environment’s data to test it. The response a spokesman emailed me from Mack was as follows:

私は、このプロセスで Facebook が学習したことについて尋ねた。 なぜなら、Timeline に限らず、彼らの多くのサイトが、フロント・エンドとバック・エンドを、平行して開発できるようになっていると、想像したからである。また、全体的なプロダクション環境のデータを、テストのためにリプリケートするコストも、排除されていると想像した。 スポークスマンが Mack からのメールを転送してきたが、その答えは以下のとおりである:

Layering is a good way of describing the process of building Timeline. To make sure we could work in parallel, we always made sure that there was at least a temporary technology that each part of the team could build on top of. Some of these were pre-existing, but many of them were quick prototypes built in a couple of days as needed. We also had frequent scrums to identify places where people were blocked on each other, and everyone on the team did an excellent job of knowing what others needed or would soon need.

Timeline の構築プロセスを表現する上で、階層化は良い方式である。 私たちの作業を並列で機能させるために、少なくとも、テンポラリなテクノロジーの上に、チームが構築しているものが在ることを、常に確認していった。 いくつかのテクノロジーは、以前から存在するものであったが、その他の大半は、必要に応じて2~3日で構築されるプロトタイプであった。 それぞれの個人が、相互に守るべき境界線を定めるために、私たちは頻繁に議論してきた。そして、このチームの全員が、他者が必要としていること、また、必要になると思われることを理解するという、素晴らしいジョブを実施していった。

When the production solutions were ready, there was always some friction in migrating from the temporary solution, but usually it was just a few days of work. It was a definite win compared with the weeks or months of delay we’d have faced if we had waited for the production solution up front. Given that we wanted to build the entire system in six months, it was critical that we avoided wasting any time.

そして、プロダクション・ソリューションの準備が整ったとき、テンポラリ・ソリューションからの移行において、いくつかの軋轢が常にあったが、だいたいは数日間の作業でフィックスできた。 このプロダクション・ソリューションを、以前から待っていたとするなら、私たちが直面することになった、数週間あるいは数ヶ月の遅れと比較して、たしかな勝利を収めたと言えるだろう。 全システムを 6ヶ月で構築することが望みだったと考えると、あらゆる時間の浪費を避けたことが、とても重要であった。

From nothing to Timeline in six months is pretty impressive, considering we’re talking about creating something to support more than 800 million users. Now you know a bit more how this Timeline sausage was made.

無から始めて、6ヶ月で Timeline を達成するとは、とても素晴らしい結果である。 そして、8億人以上のユーザーをサポートするための、何らかのものについて、ここで話しているという事実を再認識したい。 そして、いまでは、この Timeline ソーセージが作られた方式について、あなたも少し詳しくなっただろう。

Related research and analysis from GigaOM Pro:

ーーーーー

TAG indexいやぁ~~~ 翻訳していて、これほどゾクゾクしてくるのは、ほんとうに久しぶりの経験でした。 昨年の 11月のことですが、「 Big Data の実装へと走る前に、Better Data について考えるべきだ 」という Formatek のブログポストを訳しました。 そのときには、Better Data のイメージが掴めませんでしたが、ここに書かれている非正規化と、Non ストレージ・アクセス(ゼロではありません)も、きっと、その 1つなのだろうと思えてきます。 こうした柔軟な発想には、ほんとうに脱帽です。 ーーー  __AC Stamp 2

ーーーーー

<関連>

Facebook のスケール感覚に驚愕! _1
Facebook のスケール感覚に驚愕! _2
Facebook 探検隊:どのようなソフトウェアでスケールを達成しているのか _1
Facebook 探検隊:どのようなソフトウェアでスケールを達成しているのか _2
Facebook 探検隊:どのようなソフトウェアでスケールを達成しているのか _3

プロジェクト Piccolo は、スピードで Hadoop を凌駕する

Posted in Big Data, Hadoop, Parallel by Agile Cat on February 18, 2011

Piccolo Project Tries to Speed Past Hadoop
By
Derrick Harris Feb. 3, 2011, 11:30am PST
http://gigaom.com/cloud/piccolo-project-tries-to-do-parallel-processing-faster/

_ Gigaom

Few would argue that Hadoop doesn’t have a bright future as a foundational element of big data stacks, but Piccolo, a new project out of New York University, is moving data storage into machines’ memory in an attempt to improve parallel-processing performance beyond what Hadoop and/or MapReduce can do. Todd Hoff at High Scalability profiles the project, and I’d suggest going there for the details. At a high level, the difference between Hadoop and Piccolo might be explained as the difference between digging for one vegetable at a time and spreading the cleaning and peeling duties to a team of workers, versus having those workers each grab and process their own vegetables simultaneously, from a prearranged pile above the ground.

ビッグ・データ・スタックの基本的な要素として、Hadoop の明るい未来を否定する人は、ほとんどいないだろう。しかし、New York University で生まれた新規のプロジェクトである Piccolo は、マシン・メモリ内へのデータ・ストレージの移行により、並列処理パフォーマンスの改善を試み、Hadoop や MapReduce の能力をしのぐ領域を目指す。 このプロジェクトの概要については、High Scalability の Todd Hoff が記しているため、詳細については、その参照をお勧めする。 高い抽象レベルにおいて、 Hadoop と Piccolo の相違を以下のように例えることができる。 つまり、一度に1つの野菜を掘り出し、洗って、皮を剥く、農夫の仕事が Hadoop に相当するなら、あらかじめ定められた区画から複数の農夫が、それぞれが担当する野菜を同時に収穫し、その後の処理も行うのが Piccole である。

A more technical explanation is that Piccolo uses an in-memory, key-value store and a “global table interface” — as opposed to Hadoop, which utilizes a distributed file system contained within the disk drives of the machines in the cluster — that lets the CPUs access all the data simultaneously, and at high speeds only possible by pulling data straight from RAM. In this fairly long, but genuinely interesting presentation at the OSDI 10 conference, lead developer Russell Power explains how Piccolo works, how it differs from Hadoop and how it has tested far faster than Hadoop on certain workloads. Power compares Piccolo to the Chevy El Camino, which was both efficient and easy to use while also delivering high performance. Here’s a screenshot of Power illustrating Piccolo’s scalability on an Amazon EC2 cluster:

よりテクニカルに説明すると、Piccolo はイン・メモリーと Key-Value ストアだけではなく、Hadoop の対極にある 『 グローバル・テーブル・インターフェイス 』を用いることが、大きな相違点として挙げられる。そこでは、クラスタを構成するマシンに配備されたディスク・ドライブ内に含まれる、分散型のファイル・システムを活用する。 つまり、RAM から直接データを引き出すことで可能となる、きわめて高速のデータ・アクセスを、CPU に提供することになる。OSDI 10 カンファレンスにおける、長時間におよぶが、きわめて興味深いプレゼンテーションで、中心となるデベロッパーである Russell Power が、どのように Piccolo が動くのか説明した。また、特定のワークロードにおいて、Hadoop との差異が状況と、Hadoop を上回るテスト結果について説明した。 Power は、Piccolo と Chevy El Camino と比較し、どちらが使いやすく、また、効率的で、高性能をもたらすかという点を指摘した。Amazon EC2 クラスタ上で、Piccolo のスケーラビリティを証明する、Power のスクリーンショットは以下のとおりである:

クリックで拡大 ⇒

I’m not suggesting Piccolo is going to replace Hadoop, or MapReduce, generally, anytime soon or ever — Hadoop vendor Cloudera today received a strategic investment from U.S. intelligence sector consultant In-Q-Tel, which should hammer home the fact that Hadoop is for real — but Piccolo is worth watching. It certainly wouldn’t be the first academic project in recent memory to make it big; the Marten-Mickos-led cloud-software provider Eucalyptus Systems was a research project from the University of California Santa Barbara when it caught on, and then struck it big with VCs and early adopters.

一般論として、近々あるいは特定の時期に、Hadoop や MapReduce に対して、Piccolo が取って代わると示唆しているわけではない。今日(2/3)のことだが、Hadoop ベンダーである Cloudera は、US 政府情報部門のコンサルタントである In-Q-Tel から戦略的投資を受けた。それは、Hadoop が本物であるという現実を裏付けるものだ。 しかし、Piccolo は注視し続けるだけの価値を持つ。アカデミック・プロジェクトに関する最近の記憶では、この件が最初の成功例というわけでもない。Marten Mickos が率いるクラウド・ソフトウェア・プロバイダーである Eucalyptus Systems は、University of California Santa Barbara の研究プロジェクトとして始まった。そして、広まるにつれてアーリー・アダプタを得て、VC からの資金も調達するようになった

To learn even more about the future of big data processing and analysis, make sure to attend out Structure Big Data conference March 23 in New York City. You won’t likely hear about the seedling Piccolo project, but you’ll hear plenty about cutting-edge use cases and tactics for the current generation of big data tools.

3月23日に NYC で開催される、私たちの Big Data conference に参加して欲しい。 Piccolo については聞くことができないが、最先端のデータベースを含めて、ビッグ・データを取り扱う際の要因について、また、それを解決するための最適化された戦略を学べる。

Related Content From GigaOM Pro (subscription required)

ーーーーー

いろいろと出てきて、ほんとうに面白いですね! それと、Chevy El Camino は、Todd Hoff さんサイトにあるように、いわゆるデカいアメ車のことなのでしょう。 なんで黄色いのかという、意味もあるのですね。 この人の茶目っ気が大好きです :) ーーー __AC Stamp 2

ーーーーー

<関連>
Real World NoSQL シリーズ – Openwave における Cassandra
Real World NoSQL シリーズ – 4PB を処理する Trend Micro の HBase
Yahoo!は、独自の Hadoop Distribution を止めて、Apache コミュニティに協力する
Hadoop に似た Dryad は、Microsoft の Big Data スターになれるのか

 

GPGPU を用いたソートについて考える – James Hamilton

Posted in Amazon, Big Data, James Hamilton, Parallel by Agile Cat on December 22, 2010

GPGPU Sorting
Perspectives
James Hamilton’s Blog
http://perspectives.mvdirona.com/2010/12/16/GPGPUSorting.aspx

Years ago I believed that incorrectly believed special purpose hardware was a bad idea. What was a bad idea is high-markup, special purpose devices sold at low volume, through expensive channels. Hardware implementations are often best value measured in work done per dollar and work done per joule. The newest breed of commodity networking parts from Broadcom, Fulcrum, Dune (now Broadcom), and others is a beautiful example of Application Specific Integrated Circuits being the right answer for extremely hot code kernels that change rarely.

何年か前のことだが、特殊な目的のハードウェアは好ましくないという、間違った考え方を持っていた。 何が良くないかといえば、コストのかかるチャネルを介して販売される、特別な用途のための、少量生産の高額なデバイスである。 効率のよいハードウェア実装とは、コストとロットをベースに測定するときに、最も大きな価値をもたらすのが一般である。 Broadcom/Fulcrum/Dune(現在は Broadcom)などから提供される、一般的なネットワーク・パーツといった系譜は、Application Specific Integrated Circuits(ASIC)の美しい事例であり、きわめてホットで変化しにくいコードをカーネルとする際の、正しい回答である。

I’ve long been interested in highly parallel systems and in heterogeneous processing. General Purpose Graphics Processors are firmly hitting the mainstream with 17 of the Top 500 now using GPGPUs (Top 500: Chinese Supercomputer Reigns). You can now rent GPGPU clusters from EC2 $2.10/server/hour where each server has dual NVIDIA Tesla M2050 GPUs delivering a TeraFLOP per node. For more on GPGPUs, see HPC in the Cloud with GPGPUs and GPU Clusters in 10 minutes.

私は長い期間にわたり、パラレル・システムとへトロジニアスな処理に、強い興味を持ち続けてきた。 いまや、スーパーコンピュータ Top 500 において、17 種類のGeneral Purpose Graphics Processors 採用され、主流となるコンセプトに対して着実に打撃を与えている(Top 500: Chinese Supercomputer Reigns)。 そしていま、ノードごとに 1 TeraFLOP を提供する、Dual NVIDIA Tesla M2050 GPUs と搭載した EC2 サーバー($2.10 server/hour)により、GPGPU クラスタを借りることができる。 GPGPU の詳細については、HPC in the Cloud with GPGPUs および GPU Clusters in 10 minutes を参照して欲しい。

注記: 上記の 17の意味がよく分けりませんと、ここにコメントを書いていましたが、@kitayama_t さんと @kame355 さんが調べてくださり、Cell の 6種類 (7, 49, 120, 207, 208, 209) および、NVIDIA の 10種類 (1, 3, 4, 28, 72, 88, 102, 117, 145, 403)、そして ATI Radion の1種類 (22) の合計で、17種類の意味だと判明しました。 有難うございます! (参考 ⇒ http://bit.ly/gba93e

Some time ago Zach Hill sent me a paper writing up Radix sort using GPGPUs. The paper shows how to achieve a better than 3x on the NVIDIA GT200-hosted systems. For most of us, sort isn’t the most important software kernel we run, but I did find the detail behind the GPGPU-specific optimizations interesting. The paper is at http://www.mvdirona.com/jrh/TalksAndPapers/RadixSortTRv2.pdf and the abstract is below.

しばらく前のことだが、GPGPU を用いた Radix ソートに関するドキュメントを、Zach Hill から送ってもらった。 そのペーパーに記されているのは、Nvidia GT200 をホストするシステム上で、3倍の性能を達成する方式である。 大半のケースにおいて、ソートは最重要のソフトウェア・カーネルではないが、GPGPU 固有の最適化した際に、その背景に興味深い事柄が広がるのを見つけた。 そのペーパーの Abstruct を以下に記す。また、URL は http://www.mvdirona.com/jrh/TalksAndPapers/RadixSortTRv2.pdf である。

Abstract.

This paper presents efficient strategies for sorting large sequences of fixed-length keys (and values) using GPGPU stream processors. Compared to the state-of-the-art, our radix sorting methods exhibit speedup of at least 2x for all generations of NVIDIA GPGPUs, and up to 3.7x for current GT200-based models. Our implementations demonstrate sorting rates of 482 million key-value pairs per second, and 550 million keys per second (32-bit). For this domain of sorting problems, we believe our sorting primitive to be the fastest available for any fully-programmable microarchitecture. These results motivate a different breed of parallel primitives for GPGPU stream architectures that can better exploit the memory and computational resources while maintaining the flexibility of a reusable component. Our sorting performance is derived from a parallel scan stream primitive that has been generalized in two ways: (1) with local interfaces for producer/consumer operations (visiting logic), and (2) with interfaces for performing multiple related, concurrent prefix scans (multi-scan).

このペーパーが記すのは、GPGPU ストリーム・プロセッサを用いて、固定長の Key(および Value)で構成される、膨大なシーケンスを効率よくソートするためのストラテジである。 最先端とされる方式と比較して、私たちの Radix ソートは、すべての世代の NVIDIA GPGPU において、少なくとも 2倍の性能を発揮し、また、現行の GT200 ベース・モデル に対して3.7 倍のスピードアップを果たした。 私たちの実装では、4億 8200万の Key-Value セットおよび、5億 5000万のキー(32 Bit)を、毎秒ソートできることが証明れた。 ソートという問題ドメインに関して、私たちのソーティング・プリミティブは、プログラミングに対応する各種のマイクロ・アーキテクチャにおいて、最速を達成するものと信じている。 これらの結果から、GPGPU ストリーム・アーキテクチャのためのパラレル・プリミティブの、これまでとは異なる系譜が喚起される。そこでは、再利用が可能なコンポーネントの柔軟性を維持しながら、メモリとコンピューティグのリソースを、さらに効率よく利用できる 。 私たちのソートにおけるパフォーマンスは、2つの方式により生成されるパラレル・スキャン・ストリームのプリミティブからもたらされる。(1) producer/consumer オペレーション(visiting logic)のためのローカルなインターフェイスを用いる。(2)関連性を持つ多数のプリフィックス・スキャンを実行するインターフェイスを用いる。

As part of this work, we demonstrate a method for encoding multiple compaction problems into a single, composite parallel scan. This technique yields a 2.5x speedup over bitonic sorting networks for small problem instances, i.e., sequences that can be entirely sorted within the shared memory local to a single GPU core.

この処理の一部として、圧縮における多様な問題を、単一の複合パラレル・スキャンへと、エンコードする方式を実証する。 このテクニックは、小規模なインスタンスのための bitonic ソーティング・ネットワーク上で、2.5倍のスピードアップをもたらす。つまり、ワン GPU コアのローカルな共用メモリ内で、シーケンス全体がソートされる。

James Hamilton

e: jrh@mvdirona.com
w: http://www.mvdirona.com
b
: http://blog.mvdirona.com / http://perspectives.mvdirona.com

ーーーーー

何が何やらの GPGPU ですが、こうして、だんだんとイメージが掴めてくるのでしょうね。 調べなければならないことが、山のように残されていますが。 ーーー A.C.

ーーーーー

<関連>
スループット指向のアーキテクチャ- Amazon EC2 で GPU を正しく使うために
Big Data – だれが、どこで、使うのか?

スループット指向のアーキテクチャ- Amazon EC2 で GPU を正しく使うために

Posted in Amazon, Big Data, Parallel by Agile Cat on December 6, 2010

GPU Vs CPU Smackdown : The Rise Of Throughput-Oriented Architectures
FRIDAY, DECEMBER 3, 2010 AT 9:20AM
http://highscalability.com/blog/2010/12/3/gpu-vs-cpu-smackdown-the-rise-of-throughput-oriented-archite.html

_highscalability

In some ways the original Amazon cloud, the one most of us still live in, was like that really cool house that when you stepped inside and saw the old green shag carpet in the living room, you knew the house hadn’t been updated in a while. The network is a little slow, the processors are a bit dated, and virtualization made the house just feel smaller. It has been difficult to run high bandwidth or low latency workloads in the cloud. Bottlenecks everywhere. Not a big deal for most applications, but for many high performance applications (HPC) it was a killer.

ドアを開けてリビング・ルームに入り、緑色の古臭いシャギー・カーペットを眺め、その家が改築されていないと理解したとき、私たちの大半がいまだに住んでいる元々の Amazon クラウドは、いろいろな意味において寒々としている。 そのネットワークは少し遅くて、プロセッサも時代遅れであり、仮想化が家を狭く感じがさせた。 そのクラウドでは、広帯域および低レイテンシーのワークロードを動かすことが難しい。そこらじゅうに、ボトルネックがある。 大半のアプリケーションとっては重要な事柄ではないが、それは HPC(high performance applications )を殺してしまうものだった。

In a typical house you might just do a remodel. Upgrade a few rooms. Swap out builder quality appliances with gleaming stainless steel monsters. But Amazon has a big lot, instead of remodeling they simply keep adding on entire new wings, kind of like the Winchester Mystery House of computing.

そんなありふれた家は、リニューアルすべきかもしれない。 いくつかの部屋をアップグレードしよう。 輝きの薄れてきたステンレス・スチールの怪物を、ビルダー・クォリティのアプライアンスに入れ替えよう。 しかし、Amazon が抱えている資産は膨大であるため、大改造を行う代わりに、その全体を覆う新しいツバサが取り付けられた。それは、まるで、コンピューティングにおける Winchester Mystery House のようなものだ。

image

The first new wing added was a CPU based HPC system featuring blazingly fast Nehalem chips, virtualization replaced by a close to metal Hardware Virtual Machine (HVM) architecture, and the network is a monster 10 gigabits with the ability to specify placement groups to carve out a low-latency, high bandwidth cluster. Bottlenecks removed. Most people still probably don’t even know this part of the house exists.

最初に付け加えられたツバサは、きわめて高速な Nehalem チップを前面に押し出した、CPU ベースの HPC システムであり、金属性の Hardware Virtual Machine(HVM)アーキテクチャに取って代わる仮想化と、低レイテンシーと広帯域が保証されるクラスタ・グループを、指定する能力を持った 10ギガビット・モンスターのネットワークを実現する。 これで、ボトルネックが解消される。しかし、ほとんどの人々は、この家に、こんな部分が存在することを知る由もない。

The newest addition is a beauty, it’s a graphics processing unit (GPU) cluster as described by Werner Vogels in Expanding the Cloud – Adding the Incredible Power of the Amazon EC2 Cluster GPU Instances . It’s completely modern and contemporary. The shag carpet is out. In are Nvidia M2050 GPU based clusters which make short work of applications in the sciences, finance, oil & gas, movie studios and graphics.

そして、最新のツバサは美しい。 それは、Expanding the Cloud – Adding the Incredible Power of the Amazon EC2 Cluster GPU Instances において Werner Vogels が記述している GPU(graphics processing unit)クラスタである。 それは、きわめてモダンでコンテンポラリなものである。 もう、シャギーのカーペットはいらない。Nvidia M2050 GPU ベースのクラスタにより、科学/金融/石油/動画/グラフィックスなどの、アプリケーション処理の時間が大幅に短縮される。

To get a feeling of the speed involved read BillMcColl’s comment:

Cloudscale is now able to ANALYZE a SINGLE STREAM of entity events at a rate of TWO MILLION EVENTS PER SECOND (150MB/sec) on an 8-node 10-GigE Amazon cloud cluster. That’s well over ONE TRILLION EVENTS per week.

そのスピード感については、 BillMcColl のコメントを読むと良い:

いまや、クラウド・スケールは、Amazon クラウド・クラスタの 8-node 10-GigE を用いることで、全体的なイベントの SINGLE STREAM を、TWO MILLION EVENTS PER SECOND(150MB/sec)のレートで解析するに至った。それは、ONE TRILLION EVENTS / week を遥かに上回るものだ。

Having both CPU and GPU clusters seems a bit strange. Why have two? Mr. Vogels does a good job explaining the reasoning:

しかし、CPU と GPU の双方でクラスタを持つことは、少し奇妙に思える。 なぜ、2を持つのか? その理由を説明するために、Mr. Vogels は Good Job を提供している:

  • GPUs work best on problem sets that are ideally solved using massive fine-grained parallelism, using for example at least 5,000 – 10,000 threads. To be able build applications that exploit this level of parallelism one needs to enter a very specific mindset of kernels, kernel functions, threads-blocks, grids of threads-blocks, mapping to hierarchical memory, etc. Configuring kernel execution is not a trivial exercise and requires GPU device specific knowledge. There are a number of techniques that every programmer has grown up with, such as branching, that are not available, or should be avoided on GPUs if one wants to truly exploit its power.

  • GPU に適した問題のセットは、たとえば最低でも 5,000-10,000 のスレットを活用し、膨大でキメの細かなパラレルを用いて解決するものが理想的である。 このレベルのパラレルを用いたアプリケーションを構築するためには、カーネルと機能および、スレッド・ブロック、スレッド・ブロック・グリッド、階層メモリ・マップなどの、特定のマインドセットの入力が必要になる。カーネルを実行するためのコンフィグレーションは、些細な処理ではなく、また、GPU デバイス固有の知識を必要とする。たとえば、バランシングのような、すべてのプログラマが育ててきた数多くのテクニックが、そこでは利用できない。 また、GPU の真のパワーを活用するのであれば、それらは排除されてしまう。

  • Modern CPUs strongly favor lower latency of operations with clock cycles in the nanoseconds and we have built general purpose software architectures that can exploit these low latencies very well.  Now that our ability to generate higher and higher clock rates has stalled and CPU architectural improvements have shifted focus towards multiple cores, we see that it is becoming harder to efficiently use these computer systems. One trade-off area where our general purpose CPUs were not performing well was that of massive fine grain parallelism. Graphics processing is one such area with huge computational requirements, but where each of the tasks is relatively small and often a set of operations are performed on data in the form of a pipeline. The throughput of this pipeline is more important than the latency of the individual operations. Because of its focus on latency, the generic CPU yielded rather inefficient system for graphics processing. This lead to the birth of the Graphics Processing Unit (GPU) which was focused on providing a very fine grained parallel model, with processing organized in multiple stages, where the data would flow through.  The model of a GPU is that of task parallelism describing the different stages in the pipeline, as well as data parallelism within each stage, resulting in a highly efficient, high throughput computation architecture.

  • 近代的な CPU により、ナノ秒クロック・サイクルを用いた、低レイテンシー・オペレーションの恩恵が得られる。 そして、この低レイテンシーを活用した、汎用的ソフトウェア・アーキテクチャを構築できる。  しかし、これ以上のクロック・サイクルに関する追求は停滞しているため、CPU アーキテクチャの改善はマルチ・コアへとシフトし、それらのコンピュータ・システムを効率よく使用することが、難しくなり始めている。こうした汎用的 CPU が、効率を高められないトレードオフ領域の 1つは、膨大でキメの細かいパラレル処理であった。 グラフィクス処理は、そのような領域の1つであり、また、膨大なコンピュータ要件を伴う。 しかし、その個々のタスクは比較的に小さいものであり、また、大半のケースにおいて、パイプラインの形態で、オペレーション・セットがデータを処理していく。 このパイプラインのスループットは、個々のオペレーションにおけるレイテンシーより重要なものとなる。レイテンシーにフォーカスしたことで、一般的な CPU は、グラフィックス処理にとって非能率的なシステムとなる傾向にある。Graphics Processing Unit(GPU)の生い立ちをたどると、きわめて粒度の細かいパラレル・モデルへと行き着く。 そこでは、マルチ・ステージで構成された、データのフローを構成した行くための処理が用いられる。 この GPU のモデルは、パイプラインの個々のステージを記述するパラレル・タスクであるだけではなく、きわめて効率的で高スループットな、コンピューティング・アーキテクチャをもたらすものとなる。

The ACM has a timely article about using GPUs for high performance computing ACM:Understanding Throughput-Oriented Architecture by Michael Garland and David Kirk:

ハイパフォーマンス・コンピューティングのための GPU 使用法に関して、ACM Michael Garland と David Kirk が Understanding Throughput-Oriented Architecture というタイムリーな記事を提供している。

Scalability is the programmer’s central concern in designing efficient algorithms for throughput-oriented machines. Today’s architectural trends clearly favor increasing parallelism, and effective algorithmic techniques must scale with hardware parallelism. Some techniques suitable for four parallel threads may be entirely unsuitable for 4,000 parallel threads. Running thousands of threads at a time, GPUs are a powerful platform for exploring scalable algorithms and a leading indicator for algorithm design on future throughput-oriented architectures. GPUs are specifically designed to execute literally billions of small user-written programs per second.

スループット指向マシンのための、効率的なアルゴリズムを設計において、プログラマーたちの主たる関心事はスケーラビリティとなる。 今日におけるアーキテクチャ傾向は、パラレルの促進に対して明らかに有利にはたらき、また、有効なアルゴリズム技法は、並列ハードウェアを用いてスケールを達成するはずだ。 ただし、4 スレッドに適したテクニックは、4,000 のパラレル・スレッドに対して不適切かもしれない。 数千スレッドを同時に実行することで、 GPU はスケーラブルなアルゴリズムの探究において、パワフルなプラットフォームになる。 また、未来のスループット指向アーキテクチャにおける、アルゴリズム設計のための先行指標にもなるだろう。 とりわけ GPU は、ユーザー記述の何十億という小さなプログラムを、毎秒ごとに実行するようデザインされている。

What matters here are two things: tools and jobs.

そして、重要な事柄として、ツールとジョブがある。

First, there’s another exotic tool in the toolbox to solve difficult problems in ways very different than what we are used to. This along side the original recipe cloud, MapReduce, and the CPU Cloud, offers enormous flexibility when architecting systems.

第一に、私たちが慣れ親しんでいるもとは大きく異なる方式で、対象となる問題を解決するためのエキゾチックな別のツールが存在する。 その前方には、本来のクラウド・レシピ/MapReduce/CPU Cloud などがあり、システムを設計する際の、広大な柔軟性を提供していく。

Second, for a surprisingly large number of problems there is now a ready supply of GPU supercomputeryness. With supply there can be demand and not that many people know how to program GPUs. Programming GPUs is a specialized skill. It’s nothing like using your typical threading library, eventing infrastructure, and message passing library. Now that GPU processors are so readily available we’ll need GPU programmers to make use of all that power. Something to think about as a potential career direction.

第二に、驚くほど膨大な問題のための、GPU のスーパーコンピュータ的な用法が、まさにいま、準備できたことになる。 その供給に対する需要が生じるだろうが、多くの人々が GPU プログラミング知っていると言うわけではない。 GPU のプログラミングは、専門的なスキルである。 それは、一般的なスレッディング・ライブラリや、イベント・インフラストラクチャ、メッセージ・パス・ライブラリを使うようなものではない。現時点において、GPU プロセッサが容易に利用できるようになり、そのすべてのパワーを活用するために、私たちは GPU プログラマーを必要とするだろう。 経験に関する潜在的な方向性として、何を考えるべきか。

Related Articles

ーーーーー

High Scalability の Todd Hoff さんは、とても詩的な文章を書くので好きなのですが、写真の選び方もユーモアがあります。 おそらく、GPU 的な空中戦とでも、言いたいのだろうと思います。 原題の Smackdown って、プロレス技の名前なんでしょうかね?

コンテンツの訳は、もう、、、四苦八苦だったのですが、大まかなところは理解できたように思えます。 プログラミングの発想からツールまで、これから大変革が起こるのでしょう。 いやはや、たいへんな時代になってきたものです。

それにしても、この文章と写真のギャップがスゴイ :)ーーー A.C.

Microsoft の Modeling the World

Posted in Parallel by Agile Cat on June 5, 2010

Modeling the World – Microsoft Blog Admin
Posted by Bill Hilf

16 May 2010 11:01 PM
http://blogs.technet.com/b/microsoft_blog/archive/2010/05/17/modeling-the-world.aspx

こんなブログを見つけました。。。

As part of this initiative we’re also bringing together some of the brightest minds in the technical computing community at http://www.modelingtheworld.com ; to discuss the trends, challenges and opportunities we share. Personally, I think this site provides a great interactive experience with fresh, relevant content—I’m incredibly proud of it. Please tune in and join us—we welcome your ideas and feedback.

# Technical computing to the cloud:
# Simplify parallel development:
# Develop powerful new technical computing tools and applications:

そこからたどっていくと、以下のようなステキな Silverlight のページが。。。

modeling the world

http://www.modelingtheworld.com/

Bob Muglia さんをはじめ、おそらく MS Research 系の方々が、興味深いメッセージを発しています。 ひょっとして、Microsoft readying Hadoop for Windows Azure に関連する話も、、、と期待しましたが、さすがに Hadoop は出てきませんでした。 それと、みなさんが Jim Gray さんの名前を引用しているのが印象的でした。 もう、何年になるのだろう。 ーーー A.C.

Intel 48 Cores + Hadoop

Posted in Hadoop, MS-MapReduce, Parallel, Virtualization by Agile Cat on December 4, 2009

Futuristic Intel Chip Could Reshape How Computers are Built, Consumers Interact with Their PCs and Personal Devices

Intel 48 cores

SANTA CLARA, Calif., Dec. 2, 2009 – Intel Labs 研究者がデモンストレーションしたのは、48-core Intel プロセッサであり、つまりは、シングルチッ・プクラウド・コンピュータであり、ラップトップや、PC、サーバーなどのデザインで用いられている、現在における数多くのアプローチを再考させるものである。 この未来のチップは、現時点で広く利用されているIntel Core ブランド・プロセッサと比較して、10~20倍の能力のある処理エンジンを内部に持つ。

この研究における長期的なゴールは、まったく新しいソフトウェア・アプリケーションと、コンピュータのマンマシン・インターフェイスをドライブするための、途方も無いスケールを加えていくことである。Intel が来年に計画しているのは、新しいソフトウェア・アプリケーションとプログラミング・モデルの具体的な研究のために、100 個以上の実験用チップを、産業界と教育機関で共有していくことだ。

Intel は、2010 年の前半には、Core ブランド・チップの新しいラインに主要な特徴を統合し、後半には 6-core と 8-core のプロセッサに、それらを導入する。その一方で、このプロトタイプを用いて、1つのシリコン・チップ上に、プログラムを処理できる48個の Intel プロセッシング・コアを取り込んでいく。さらに、 情報共有のための、高速のオン・チップ・ネットワークと、新たに開発されたパワー・マネジメント技術も取り込む。それにより、わずか25ワットから、最大性能時における 125ワットまでの間で、48コアにおける全てをエネルギーを、きわめて効率的に操作できる(今日の Intel プロセッサの消費電力は、標準的な家庭用電球2個分ほど)。

<中略>

マルチ・コア・プロセッサのプログラミングは、シングル・シリコン・チップ上の Many Core へ向かう、コンピュータとソフトウェアのメーカーにとって、重要なチャレンジとして認識されている。 このプロトタイプが実現するのは、一般的で効果的な並列プログラミングのアプローチであり、クラウド・データセンターのソフトウェアで用いられ、このチップに適用されるものとなる。

Intel 48 cores Hadoop

こんな画面も、Youtube の動画でチラッ見られますよ~~~

Intel/HP/Yahoo の Open Cirrus コラボレーションからの研究者により、この 48 IA コアチップへのクラウド・アプリケーションのポートが始まっている。それは、Java framework を用いる Hadoop であり、Rattner が証明しているような、データ・セントリッな分散アプリケーションをサポートしている。 

詳しくは、↓ こちらで ど~ぞ。
http://www.intel.com/pressroom/archive/releases/2009/20091202comp_sm.htm

この実験に Hadoop が使われることが、とても自然に思えます。 Many Core の活躍の場を、Hadoop が作っていくと言っても過言ではないでしょう。 --- A.C. 

<関連>
Nehalem と仮想化

DryadLINQ とベンチマーク

Posted in MS-MapReduce by Agile Cat on June 10, 2009

DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language

From <http://research.microsoft.com/apps/pubs/default.aspx?id=70861>

1st December 2008

DryadLINQ とは、大規模な分散コンピューティングのための、新しいプログラミング・モデルを実現するシステムであり、また、拡張言語のセットである。 そして、以下の2つの方式による、 SQL および、MapReduce、Dryad などの実行環境を汎用化するものである。それは、ストロング・タイプの .NET オブジェクトのリッチなデータモデルを採用することにより、また、これまでの高レベル・プログラム言語のデータセットにおける汎用的な規範と、宣言型のオペレーションをサポートすることで達成される。

DryadLINQ のプログラムは、副作用から開放された方式でデータセットを任意に変換する、LINQ 表現で構成されたシーケンシャルなプログラムである。そして、標準的な .NET 開発ツールを用いた記述とデバッグに対応している。 DryadLINQ システムは自動的に、また、透過的に、プログラムのパラレル・データ 部分を分散形式に変換し、それを Dryad 実行プラットフォームに受け渡す。 Dryad は、何千というコンピュータで構成された実運用環境のクラスタ上で、この何年かにわたり継続して運用されており、この計画における効率的で信頼できる実行を保証する。

素晴らしいパフォーマンスが達成されたことを伝えたい。つまり、10^12バイトのデータについて、汎用的なソートを行った結果を示したい。240 台の コンピュータと、960 台のディスク・クラスタを用いて、このソートを 319秒で完了した。それだけではなく、いろいろとコンピュータの台数を変えて試してみたが、ほとんどリニアなスケールが得られることを、このアプリケーションは証明したのである。

Cosmos in msdn Forum

Posted in MS-MapReduce by Agile Cat on May 30, 2009

msdn Forum で Cosmos について

msdn Forum で Cosmos などについて尋ねてみましたら、Brad Calder さんが親切に答えてくれました。”Azure XStore I believe is a reference to Windows Azure Storage” なんだけど、詳細は話せないので、PDC のセッションを見てほしいとのことでした。

ーーーーーーーーーーーーーーーーーー

Agile Cat Thursday, May 28, 2009 11:10 PM

Hi Brad, thank you for your reply.
According to Mihai Budiu’s another PPT,,,

  • DryadLINQ and Scope compete with Sawzall, Pig and Hive.
  • Dryad competes with Map-Reduce and Hadoop.
  • Cosmos, Azure and SQL Server compete with GFS, BigTable, HDFS and S3.

Please find his those figures at below:
http://agilecat.wordpress.com/2009/05/28/dryadlinq/
In addition, there is Azure XStore.
If you have additional info, please let me know.

Thanks,
-A.C.

ーーーーーーーーーーーーーーーーーー

Brad CalderMSFT, ModeratorThursday, May 28, 2009 11:56 PM

Azure XStore I believe is a reference to Windows Azure Storage.
At this time, the only public information we have disclosed about Windows Azure Storage is in the following talk (there are a few slides at the end of the talk about durability, availability and scalability):

http://channel9.msdn.com/pdc2008/ES04/

The storage components have been built to provide a durable, scalable and highly available storage system for the Cloud, to provide Azure Tables, Blobs and Queues.    We make heavy use of replication, partitioning and load balancing of your data to make sure we can meet the traffic needs for your application’s data.
Thanks,
Brad

ーーーーーーーーーーーーーーーーーー

Brad さんが伝えたいのは、このあたりかなぁと、、、

Azure Storage in PDC_2

Azure Storage in PDC_3

ーーーーーーーーーーーーーーーーーー

よかったら、msdn の What’s Cosmos スレで、ご質問を ど~ぞ。

%d bloggers like this: