[Q] programming on smp

[Yasushi Shinjo]

新城＠筑波大学情報です。こんにちは。

In article <86d6bm...@xh6.cc.hokudai.ac.jp>
Hiroki Kashiwazaki <r...@cc.hokudai.ac.jp> writes:
> 柏崎＠北海道です。
> で、CPUを2つ同時に利用するプログラムを書いて計算時間を短縮しようと、
> ようやく重い腰を上げたのですが、どのようにそれを実現するのかを全く知
> りません。

問題の性質によるのですが、性質がよくて単にデータを分割しても
いいという話なら、１番お奨めは、今までの逐次のプログラムを２
個同時に走らせることです。たとえば、全部で 100 個のデータに
ついて計算するなら、前半 50 個と後半 50 個にわけて、２つ走ら
せるわけです。問題の性質がよくて依存関係がないものなら、これ
でＯＫ。

> 「SMP プログラミング」といったキーワードでぐぐると、MPI の
> プログラミングに関するページがヒットしますが、MPI プログラミングと同
> 様の手法でコーディングしてコンパイルすると 2CPU を使うバイナリが生成
> されるのでしょうか。

MPI よりは、POSIX Threads (Pthreads) を使う方がいです。ルー
プ間で依存関係があるなら、バリア同期を使うかタスクバッグがい
いでしょう。２ＣＰＵでも、バランスが完全に取れるとは限らない
ので、問題を１０個くらいに分割するのがいいかと思います。

ニュースグループは、Followup-To: fj.comp.parallel でしょうか。

＼＼　新城　靖　（しんじょう　やすし）　＼＼
＼＼　筑波大学　電子・情報　　　　　　　＼＼

[Yasushi Shinjo]

新城＠筑波大学情報です。

fj.comp.misc から引っ越しということで元記事の転載です。

＼＼　新城　靖　（しんじょう　やすし）　＼＼
＼＼　筑波大学　電子・情報　　　　　　　＼＼

----------------------------------------------------------------------
From r...@cc.hokudai.ac.jp Sun Nov 23 01:37:51 2003
From: Hiroki Kashiwazaki <r...@cc.hokudai.ac.jp>
Newsgroups: fj.comp.misc
Subject: [Q] programming on smp
Date: Fri, 21 Nov 2003 09:00:53 +0900
Message-ID: <86d6bm...@xh6.cc.hokudai.ac.jp>

柏崎＠北海道です。

# 情報系としては非常に阿呆な質問をする事をお許し下さい。

今まで 1CPU マシンでプログラムを書いていましたが、今年の春に 2CPU の
SPARC マシンが届いて、当初は「CPUを2つ使うプログラムを書くの（を勉強
すること）も面倒だし、計算プロセスを 2つ同時に実行して、１計算あたり
の計算効率はにばーいにばーい」と喜んでいました。さすがにそれは阿呆だ
ろうと当初から分かっていましたのですが、問題を先伸ばしにしていました。

で、CPUを2つ同時に利用するプログラムを書いて計算時間を短縮しようと、
ようやく重い腰を上げたのですが、どのようにそれを実現するのかを全く知
りません。「SMP プログラミング」といったキーワードでぐぐると、MPI の

プログラミングに関するページがヒットしますが、MPI プログラミングと同
様の手法でコーディングしてコンパイルすると 2CPU を使うバイナリが生成
されるのでしょうか。

実際に試してみるのが一番という気もする…。

--
柏崎 礼生 (Hiroki Kashiwazaki)@HUIIC
Ph.D candidate in the Division of Electronics & Information
Engineering, Hokkaido University
mailto:r...@cc.hokudai.ac.jp
Tel:+81-11-706-2998

[Hiroki Kashiwazaki]

柏崎＠北海道です。

At 22 Nov 2003 16:37:15 GMT,
Yasushi Shinjo wrote:

> MPI よりは、POSIX Threads (Pthreads) を使う方がいです。ルー
> プ間で依存関係があるなら、バリア同期を使うかタスクバッグがい
> いでしょう。２ＣＰＵでも、バランスが完全に取れるとは限らない
> ので、問題を１０個くらいに分割するのがいいかと思います。

ここでふと疑問に思ったのですが、例えば SGI Onyx のように、1ノード
4CPUで、16程度のノードで構成されている計算機がありますよね。

こういった複数ノードで構成された計算機群により一つのシステムが構成
されている計算機において、複数ノードをまたいで処理を行なわせるのが
MPI であると理解しているのですが、このような計算機システムで一つの
ノードの全ての CPUを効率良く使い、かつ全てのノードも効率良く使おう
とするならば、pthreads と MPI の双方を同時に用いる、という事になる
のでしょうか。

[NAKAU Koji]

中右＠札幌です。

In article <86n0ak...@xh6.cc.hokudai.ac.jp>
r...@cc.hokudai.ac.jp writes:

| ここでふと疑問に思ったのですが、例えば SGI Onyx のように、1ノード
| 4CPUで、16程度のノードで構成されている計算機がありますよね。

| MPI であると理解しているのですが、このような計算機システムで一つの

| ノードの全ての CPUを効率良く使い、かつ全てのノードも効率良く使おう
| とするならば、pthreads と MPI の双方を同時に用いる、という事になる
| のでしょうか。

昔、LAMで1CPUに1ノードを割り当てていました。なので、Dual機には
2ノードを当てはめました。この時はモンテカルロシミュレーション
だったので、全てのCPUをほぼ100%使い切ってました。

問題によってはthreadsを使った方が早い等々あると思いますが、
手間を考えると、どうなんでしょうね。
---------------------------------------------
　中右 浩二 (なかう こうじ) 札幌市 豊平区
ko...@nakau.net http://nakau.net/~koji/
---------------------------------------------

[Yasushi Shinjo]

新城＠筑波大学情報です。こんにちは。
やはり、SMP ならスレッドでしょう。

In article <86n0ak...@xh6.cc.hokudai.ac.jp>

Hiroki Kashiwazaki <r...@cc.hokudai.ac.jp> writes:
> ここでふと疑問に思ったのですが、例えば SGI Onyx のように、1ノード
> 4CPUで、16程度のノードで構成されている計算機がありますよね。
>

> こういった複数ノードで構成された計算機群により一つのシステムが構成
> されている計算機において、複数ノードをまたいで処理を行なわせるのが

> MPI であると理解しているのですが、このような計算機システムで一つの
> ノードの全ての CPUを効率良く使い、かつ全てのノードも効率良く使おう
> とするならば、pthreads と MPI の双方を同時に用いる、という事になる
> のでしょうか。

Pthreads と MPI を混ぜるのは、どうかなあ。

MPI は、どのくらい頑張って実装しているかで性能が変る(MPI で
はインタフェースしか規定していない)という性質があります。下
手な実装で、下手な使い方をすると、CPU を増やせば増やす程遅く
なるプログラムは、比較的簡単に書けるんじゃないかなあ。

その点、最近のまともな SMP (まともでないものはのぞく)は、ス
レッドでプログラムを書くと、けっこう CPU の数で性能が上がる
プログラムは書きやすいです。SMP だけしか相手にしないなら、ス
レッドの方が簡単です。

In article <0311252228...@cond.cond.nenp.hokudai.ac.jp>
"NAKAU Koji" <koji...@nakau.net> writes:
> 問題によってはthreadsを使った方が早い等々あると思いますが、
> 手間を考えると、どうなんでしょうね。

混ぜる手間ですよね。混ぜるのは、私もどうかと思いますが、スレッ
ドのプログラムと MPI のプログラムでは、スレッドの方が手間が
少ないと思うんだけど、これは背景によるのかなあ。一応、SMP の
ウリは、プログラミングが簡単ということには、なっていたんだけ
ど。その昔は。

[NAKAMURA Kazushi]

中村和志＠神戸です。

In article <YAS.03No...@kirk.is.tsukuba.ac.jp>
y...@is.tsukuba.ac.jp writes:
># 情報系としては非常に阿呆な質問をする事をお許し下さい。

"S"MPなら、新城さんの言うようにスレッドで処理すりゃ良いでしょ、で
済んで阿呆な質問なのですが、これが、

In article <86n0ak...@xh6.cc.hokudai.ac.jp>

r...@cc.hokudai.ac.jp writes:
>ここでふと疑問に思ったのですが、例えば SGI Onyx のように、1ノード
>4CPUで、16程度のノードで構成されている計算機がありますよね。

このような"S"MPでないMPマシンとなると、途端に話が難しくなります。
実在したトポロジだけでも、nCUBE,Hyper-Tree,トーラス…。
トランスピュータなんかは大抵、２次元格子ですよね。

In article <YAS.03No...@kirk.is.tsukuba.ac.jp>

y...@is.tsukuba.ac.jp writes:
>Pthreads と MPI を混ぜるのは、どうかなあ。

fj.comp.databasesにタイムリに挙がっているトランザクションの話題
とも共通しますが、ロックなり同期なりを、マルチプロセッサ、それも
非対称構成で、効率的、かつ安全に実装するのは頭痛のネタです。

>その点、最近のまともな SMP (まともでないものはのぞく)は、ス
>レッドでプログラムを書くと、けっこう CPU の数で性能が上がる
>プログラムは書きやすいです。SMP だけしか相手にしないなら、ス
>レッドの方が簡単です。

同感。ただし、SMPはリニアに性能向上が期待できる規模の並列マシン
しか作られていないのでは？たいていメモリ帯域やキャッシュの
コヒーレンシで頭打ちになるので、256PE以上の規模の"S"MP
マシンって実用になっていないような。LinuxのSMP回りも16PE
以下の規模しか基本的に想定していないですよね。

>少ないと思うんだけど、これは背景によるのかなあ。一応、SMP の
>ウリは、プログラミングが簡単ということには、なっていたんだけ
>ど。その昔は。

今もそうだと思います。GNU(hurd)も、普通に作った／既に作られている
ソースでも、スレッドライブラリをリンクするだけで、ライブラリ
レベルで実行可能な範囲で、並列動作してくれる、みたいなことを
狙っているようですし。MPIとかになると、プログラマがマシンや
ネットワーク構成を意識する必要が出て来るケースが多いと思います。

＃挙げ句の果てに、問題の方をマシン構成に向いたものを探して来る
＃ようになる本末転倒。＜かつての俺だ。

ところで、"p"threadって使いにくくないですか？セマンティックスが
素直な発想で構築されていると思うのだが、いざ使ってみると何だか
使いにくいことが多い。結局、Solarisにせよ、Linuxにせよ、POSIX
threadに何らかの拡張を施していますよね。
--
中村和志＠神戸 <mailto:k...@kobe1995.net>
NAKAMURA Kazushi@KOBE <http://kobe1995.net/>
- Break the hate chain. No more kill!
administrator@127.1

[Yasushi Shinjo]

新城＠筑波大学情報です。こんにちは。

In article <0311290312...@ns.kobe1995.net>

k...@kobe1995.net (NAKAMURA Kazushi) writes:
> ところで、"p"threadって使いにくくないですか？セマンティックスが
> 素直な発想で構築されていると思うのだが、いざ使ってみると何だか
> 使いにくいことが多い。結局、Solarisにせよ、Linuxにせよ、POSIX
> threadに何らかの拡張を施していますよね。

具体的に Pthread のどの辺りが使いにくいと思いますか？

私は、Pthread より前に自分のスレッド・ライブラリを使っていた
ので、自分のものが使いやすいとは思っています。どの辺りが使い
やすいかというと、メタレベルのプログラムが書きやすい、という
所です。Pthread は、メタレベルのプログラムが書きにくい。メタ
レベルの変数がないので。

> >少ないと思うんだけど、これは背景によるのかなあ。一応、SMP の
> >ウリは、プログラミングが簡単ということには、なっていたんだけ
> >ど。その昔は。
>
> 今もそうだと思います。GNU(hurd)も、普通に作った／既に作られている
> ソースでも、スレッドライブラリをリンクするだけで、ライブラリ
> レベルで実行可能な範囲で、並列動作してくれる、みたいなことを
> 狙っているようですし。

ほう。具体的にどんなライブラリ関数が並列に動かして高速化でき
るのでしょうか。

[NAKAMURA Kazushi]

中村和志＠神戸です。こっちは月が沈んで、かに星雲(M1)の撮影中。

In article <YAS.03No...@kirk.is.tsukuba.ac.jp>

y...@is.tsukuba.ac.jp writes:
>> ところで、"p"threadって使いにくくないですか？セマンティックスが
>> 素直な発想で構築されていると思うのだが、いざ使ってみると何だか
>> 使いにくいことが多い。結局、Solarisにせよ、Linuxにせよ、POSIX
>> threadに何らかの拡張を施していますよね。
>
>具体的に Pthread のどの辺りが使いにくいと思いますか？

具体的にこれこれ、とは言い難いんだけど、

>私は、Pthread より前に自分のスレッド・ライブラリを使っていた
>ので、自分のものが使いやすいとは思っています。どの辺りが使い
>やすいかというと、メタレベルのプログラムが書きやすい、という
>所です。Pthread は、メタレベルのプログラムが書きにくい。メタ
>レベルの変数がないので。

この「メタレベル」のプログラムが書き難い、という表現がなんとなく
ピンと来ます。libXtを使ってGUIアプリを作るが如く、低レベルの
細かいことまでゴリゴリ組んでいかないといけなくて疲れる。その割に
痒い所に手が届かなくて、SolarisやLinuxの独自拡張や仕様変更に
頼らざるを得ない局面に遭遇しがちと。

新城さんのスレッドライブラリの文献のありか教えてもらえますか？
ポインタだけで構わないので。以前も見たような気がするのですが、
その時は余り注目してなくてよく見なかったけど、今これ見て、急に
とても見たくなりました。

>> >少ないと思うんだけど、これは背景によるのかなあ。一応、SMP の
>> >ウリは、プログラミングが簡単ということには、なっていたんだけ
>> >ど。その昔は。
>>
>> 今もそうだと思います。GNU(hurd)も、普通に作った／既に作られている
>> ソースでも、スレッドライブラリをリンクするだけで、ライブラリ
>> レベルで実行可能な範囲で、並列動作してくれる、みたいなことを
>> 狙っているようですし。
>
>ほう。具体的にどんなライブラリ関数が並列に動かして高速化でき
>るのでしょうか。

これもソースを見て判断したわけではないです。GNU-0.0を使った時に
ドキュメントに「並列動作するよ」もしくは「並列動作するように、
GNUに手を加える時は注意してね」みたいなことが書いてあった読めた
もので。

[Yasushi Shinjo]

新城＠筑波大学情報です。こんにちは。

In article <0312040218...@ns.kobe1995.net>
k...@kobe1995.net (NAKAMURA Kazushi) writes:
> 中村和志＠神戸です。こっちは月が沈んで、かに星雲(M1)の撮影中。

> この「メタレベル」のプログラムが書き難い、という表現がなんとなく
> ピンと来ます。libXtを使ってGUIアプリを作るが如く、低レベルの
> 細かいことまでゴリゴリ組んでいかないといけなくて疲れる。その割に
> 痒い所に手が届かなくて、SolarisやLinuxの独自拡張や仕様変更に
> 頼らざるを得ない局面に遭遇しがちと。

独自仕様か。独自拡張(_NP(non-portable)がついている)も人気が
出ると標準になります。recursive mutex とか。flockfile() は、
最初から recursive だったんだけど。

recursive mutex って、うまく作るとそんなに重くはないです。
self を使うといいです。

それで、どんな具体的な独自機能(Solaris,Linux)を使いましたか？

> 新城さんのスレッドライブラリの文献のありか教えてもらえますか？
> ポインタだけで構わないので。以前も見たような気がするのですが、
> その時は余り注目してなくてよく見なかったけど、今これ見て、急に
> とても見たくなりました。

どうもありがとうございます。メタレベルに正面から取り組んだの
は、これです。

[] Y.Shinjo and Y.Kiyoki: "A lightweight process facility
supporting meta-level programming", Parallel Computing,
Vol.22, No.11, pp.1429-1454 (1997).

スレッドにとってメタは、CPU。それで、CPU レベルの変数が使え
るといいというのが基本的な話です。あと、スケジューラなどのメ
タレベルのプログラムを全部、あるいは、部分的に取り替えられる
とか、スレッド間の同期プリミティブを簡単に書けるようにすると
か。別の視点では、次の論文にも出ています。

[] 新城, 清木: "並列プログラムを対象とした軽量プロセスの実現
方式",情報処理学会論文誌, Vol.33, No.1, pp.64-73 (1992).

[] 新城, 清木: "仮想プロセッサを提供するオペレーティング・シ
ステム・カーネルの構成法", 情報処理学会論文誌, Vol.34, No.3,
pp.478-488 (1993).

> これもソースを見て判断したわけではないです。GNU-0.0を使った時に
> ドキュメントに「並列動作するよ」もしくは「並列動作するように、
> GNUに手を加える時は注意してね」みたいなことが書いてあった読めた
> もので。

単にライブラリ関数が MT-Safe (Multithread-Safe) ということで
はなくて、１つのライブラリ関数の内部が並列に動作すると言うこ
とですか。ライブラリ関数自体が、CPUレベルの並列動作というの
は、なかなか思いつきません。CPUレベルではなくて、入出力とい
うのなら普通だと思いますけど。たとえば、fprintf(stdout,...)
と fprintf(stderr,...) が同時に動くとか。

Pthread の実装って、キャンセル(スレッドを殺す)が難しいんですよね。

[Hiroki Kashiwazaki]

柏崎＠北海道です。

# 興味深くスレッドを読ませて頂いています。
# なかなか理解できない話もあるので難儀していますが…。

At Fri, 28 Nov 2003 18:12:01 GMT,
NAKAMURA Kazushi wrote:

> >ここでふと疑問に思ったのですが、例えば SGI Onyx のように、1ノード
> >4CPUで、16程度のノードで構成されている計算機がありますよね。
>
> このような"S"MPでないMPマシンとなると、途端に話が難しくなります。
> 実在したトポロジだけでも、nCUBE,Hyper-Tree,トーラス…。
> トランスピュータなんかは大抵、２次元格子ですよね。

結局、数CPU/1ノード、数十ノードとかいうマシンの場合、その CPUを
複数使った計算を行なおうとするなら、

(1) 1CPUを使う計算を、MPIを利用して複数ノードにまたがらせて実行

(2) 1ノードだけ使ってthreadを利用して複数のCPU資源を利用。
マルチプロセスで計算できるようにモデルを切り分けて実行。

(3) 効率は上がらないかもしれないけど、threadを利用した計算を
MPIで複数ノードにまたがらせて実行。

みたいな認識で良いのでしょうか。それとも大間違い ?

[Shinji KONO]

河野真治 @ 琉球大学情報工学です。

In article <86u14e...@xh6.cc.hokudai.ac.jp>, Hiroki Kashiwazaki <r...@cc.hokudai.ac.jp> writes

> 結局、数CPU/1ノード、数十ノードとかいうマシンの場合、その CPUを
> 複数使った計算を行なおうとするなら、

結構、小規模なのね。

> (1) 1CPUを使う計算を、MPIを利用して複数ノードにまたがらせて実行
> (2) 1ノードだけ使ってthreadを利用して複数のCPU資源を利用。
> マルチプロセスで計算できるようにモデルを切り分けて実行。

これは、ま、そんなものでしょう。ちなみに、
Multi Thread と Multi Process
は別物です。Multi Processで最初から作って、socket で通信する
ってのも悪くないです。

> (3) 効率は上がらないかもしれないけど、threadを利用した計算を
> MPIで複数ノードにまたがらせて実行。

これは普通はないMPIの使い方です。

MPIではなく、Shared Virtual Memoryとか分散共有メモリとかいう
のがあるので、そういうのを使うみたい。えーと、なんか、彼らが
使っている変な略号があったんだけど、DSM とかNUMAとか、そんな
の。

ただ、分散共有メモリは普通に実装すると性能が上がらないので、
(当り前～) いろいろ意味不明な制限とか機能とかを付けるのが
普通なようです。例えば、

書いたものがすぐ読めるとは限らない (Weak consistency とかいう)
(そんなの考えながらプログラム書くわけ?)
とりあえずバリア同期の部分でなんとかする
(そこでネットワークが混むのは我慢する)
誰からでも同じように読めるわけではない (このメモリはどこにあるとか指定する)
(そんじゃ、PVMに逆戻り...)
ロックの機構を工夫する。(なんたらLock APIみたいなのを入れる)
(ロックネックになるのは見えてる...)

とかするようだね。

僕の意見としては、領域分割できるようなやさしい問題を並列化す
るなら、プロセスを分離してsocketで通信するのが簡単。難しい問
題をやるなら、結局は、通信部分から凝って書かないとダメ。Thread
と通信の組合せはシロートには手におえない。というところですね。

---
Shinji KONO @ Information Engineering, University of the Ryukyus,
河野真治 @ 琉球大学工学部情報工学科,

[Yasushi Shinjo]

新城＠筑波大学情報です。こんにちは。

In article <86u14e...@xh6.cc.hokudai.ac.jp>

Hiroki Kashiwazaki <r...@cc.hokudai.ac.jp> writes:
> 柏崎＠北海道です。
> # 興味深くスレッドを読ませて頂いています。
> # なかなか理解できない話もあるので難儀していますが…。

ネットワークニュースなので、それぞれ書きたいことを書いている
だけなので。自分の見たい記事を増やすには、自分の読みたい記事
を自分で書くというのが王道です。

> 結局、数CPU/1ノード、数十ノードとかいうマシンの場合、その CPUを
> 複数使った計算を行なおうとするなら、

どうせ MPI を使うなら、まず試しに MPI でやってみる(複数CPUに
はCPUの数だけノードを割り当てる)、というのでどうですかね。そ
れで性能が出れば、よし。出なければまた考える。

あと、OmniRPC というのも、一応宣伝しておかないといけないかな
あ。隣で作っているので。

http://www.omni.hpcc.jp/OmniRPC/

そうか。OmniRPC は基本的には、RPC 風の並列実行（ただし非同期
で、完了待ちは別にやる）なんだけど、Omni OpenMP という
OpenMP のコンパイラも呼べたのでした。OpenMP は、SMP 用のもの
です。SMP の部分は、OpenMP で、ネットワークの部分は、OmniRPC
でと組み合わせるといいかもしれません。

http://www.omni.hpcc.jp/OmniRPC/htdocs/parallel.html

In article <3989241...@insigna.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。

> これは、ま、そんなものでしょう。ちなみに、
> Multi Thread と Multi Process
> は別物です。Multi Processで最初から作って、socket で通信する
> ってのも悪くないです。

私でも、そうするかも。慣れの問題もあるし。

> ただ、分散共有メモリは普通に実装すると性能が上がらないので、
> (当り前～) いろいろ意味不明な制限とか機能とかを付けるのが
> 普通なようです。例えば、

分散共有メモリは、人手でプログラムを作るのはなかなか難しいん
じゃないかなあ。コンパイラがそういうコードを出してくれるなら
いいけれど。

> 書いたものがすぐ読めるとは限らない (Weak consistency とかいう)
> (そんなの考えながらプログラム書くわけ?)
> とりあえずバリア同期の部分でなんとかする
> (そこでネットワークが混むのは我慢する)

Java の SMP のマルチスレッドでも、一応、synchronized した時
だけメモリに書かれていることを保証するという話になっていたん
じゃないかなあ。規格としては。実際にはけっこうすぐ書かれるん
だとは思いますけど。