How to make PC Cluster Systems

PCクラスタを作ろう！！
廣安知之
同志社大学工学部知識工学科
[email protected]
Cluster
clus·ter n.
Ⅰ 〔ブドウ・サクランボ・フジの花などの〕房（ふさ）
〔of〕a cluster of grapes 一房のブドウ.
Ⅱ 〔同種類のもの・人の〕群れ, 集団
〔of〕a cluster of spectators 一団の観客.
a cluster of butterflies チョウの群れ.
a cluster of stars 星団.
in a cluster （一つに）かたまって, 群れをなして.
in clusters いくつもの群れをなして, かたまりになって.
New College English-Japanese Dictionary, 6th edition (C) Kenkyusha
Ltd. 1967,1994,1998
PCクラスタ
並列計算機
このチュートリアル講座では．．．
PCクラスタという並列計算機
計算機の作り方
ハードウエア
ソフトウエア
並列計算の仕方
一般的なプログラムの作成
進化的計算（GAなど）の並列モデル
でも本当は教えたくない！？
導入が極めて簡単（大規模･高度
なシステムは難しい）
並列処理の研究には明日はないか
もしれないが，経済問題，バイオイン
フォマティクスとならんで，並列アプリ
ケーションには夢がある．（閉塞を打破しよ
う．．．情報処理学会誌 2001.7,8)
並列アプリケーションには明日があ
る！？
高速に処理が可能
創発アルゴリズム（特に進化的計算ア
ルゴリズム）は確実に高速化が可能
計算パラダイムが変わる？（P2Pなど）
創発アルゴリズム（特に進化的計算ア
ルゴリズム）には秘策がある
はずかしい並列
（embarrassing parallel)
P
P
P
P
P
P
P
P
パラメトリックサーチ
創発アルゴリズム（特に進化的計算
アルゴリズム）の秘策
ある探索アルゴリズムで25％の確率で解が発見できる場合
P
P
P
P
初期解のbroadcast
解の収集･ベスト解の選択
並列アルゴリズムによって100%の確率で解が発見可能！！
何故，並列処理を行わなけれ
ばならないか？
何故並列処理を行わなければならないのか？
高速に処理をおこなわなければならない
計算コストが高い
繰り返しを多く必要とする
大規模な問題
進化的計算手法
Features
生物の遺伝と進化
様々な問題に比較的簡単に適用可能
計算負荷が高い
個体数が多い
１つの仕事はサブタスクに分割可能
High Performance Computing
(HA)
何故並列処理を行わなければならないのか？
特に進化的計算の場合は威力を発揮（後で詳しく
説明）
何故並列処理を行わなければならないのか？
ex. SETI@home
計算パラダイムの変化
Project rc5
Intel
計算資源は余っている．
Philanthoropic
研究室のパソコン
P2P Program
実習室･演習室のパソコン
景気刺激対策で導入された大型計算機
その他
グローバルコンピューティング
インターネット接続による大規模システム
P2P
NapsterやGnutellaを代表とする分散システム
並列処理の必要性はわかったが
何故PCクラスタなのか？
Top５００
http://www.top500.org
Name
# Proc
1
ASCI White
8192
2
SP Power3
2528
2526
3
ASCI Red
9632
2379
ASCI Blue-Pacific
5808
2144
SR8000/MPP
1152
1709
Ranking
4
5
Parallel Computers
Rmax
(Gflops)
7226
Commodity Hardware
CPU
Networking
Pentium
Internet
Alpha
Power
etc.
Lan
Wan
Gigabit
cable less
etc.
PCs + Networking
PC Clusters
なぜPCクラスターなのか?
hardware
Commodity
Off-the-shelf
Software
Open source
Free ware
Peopleware
大学の学生，助手，講師
研究所のおたく
高い性能
低コスト
簡単なセットアップ
簡単な利用
占有可能
Top５００
http://www.top500.org
Name
# Proc
36
SCore III
1024
42
CPlant Cluster
1000
512.4
102
LosLobos
512
237
156
CLIC PIII
528
143.3
389
ABACUS Cluster
520
80.8
439
Presto III
104
77.4
Ranking
Rmax
(Gflops)
547.9
並列計算機の分類
簡単なPCクラスタを作ろう！！
PCクラスタ
8nodes + gateway(file server)
Fast Ethernet
Switching Hub
150万
何を準備すれば良いのか?
Hardware
CPU
memory
motherboard
hard disc
case
network card
cable
hub
Normal PCs
何を準備すれば良いのか?
Software
OS
tools
Editor
Compiler
Parallel Library
メッセージパッシング
ソケット
意味：「接続の端点」
コンピュータとTCP/IPを
つなぐ出入り口
ソケット
TCP/IP
ソケット通信
ソケットを使って通信を行うには
２つのプログラムが必要
クライアントプログラム
ソケットを用意して
サーバに接続要求を行う
サーバプログラム
ソケットを用意して接続要求を待つ
ソケット通信とは
接続待ちのサーバを
クライアントが探す
接続待ち
サーバを探す
サーバ側
クライアント側
ソケット通信とは
サーバが見つかったら
接続して通信
接続を受信
サーバを見つけて接続
サーバ側
クライアント側
メッセージパッシングライブラリ
PVM (Parallel Virtual Machine)
http://www.epm.ornl.gov/pvm/pvm_home.html
PVM was developed at Oak Ridge National
Laboratory and the University of Tennessee.
MPI (Message Passing Interface)
http://www-unix.mcs.anl.gov/mpi/index.html
MPI is an API of message passing.
1992: MPI forum
1994 MPI 1
1887 MPI 2
MPIの実装
Free Implementation
MPICH ：
LAM：
WMPI ： Windows 95，NT
CHIMP/MPI
MPI Light
Bender Implementation
Implementations of parallel computers
MPI/PRO ：
クラスタの構築の手順
複数台のPCを用意する
PCをつなげる
OSとtoolをインストールする
開発toolと並列ライブラリをインストール
OS/tools
Linux
GNU Compiler, GDB
rsh
MPICH/LAMのインストール
# rpm –ivh lam-6.3.3b28-1.i386.rpm
# rpm –ivh mpich-1.2.0-5.i386.rpm
#
#
#
#
dpkg –i lam2_6.3.2-3.deb
dpkg –i mpich_1.1.2-11.deb
apt-get install lam2
apt-get install mpich
ソケット通信の流れ 1
ソケット生成
(socket)
ソケット生成
(socket)
クライアント
サーバ
ソケット通信の流れ 2
サーバを探す
(gethostbyname)
クライアント
接続の準備
(bind/listen)
サーバ
ソケット通信の流れ 3
接続要求
(connect)
クライアント
接続受理
(accept)
OK!
サーバ
ソケット通信の流れ 4
通信
(send/recv)
通信
(send/recv)
こんにちわ
クライアント
こんにちわ
サーバ
ソケット通信の全体の流れ
クライアント
サーバ
ソケット生成(socket)
ソケット生成(socket)
サーバを探す
(gethostbyname)
接続の準備(bind)
接続待機(listen)
接続要求(connect)
識別情報
接続受信(accept)
データ送受信(send/recv)
データ送受信(send/recv)
ソケットを閉じる(close)
ソケットを閉じる(close)
クライアントプログラム（C）
//client.c
#include<stdio.h>
#include<sys/types.h>
#include<sys/socket.h>
#include<netinet/in.h>
#include<netdb.h>
#include<string.h>
#define PORT (u_short)10000
#define BUF_LEN 100
char hostname[]="localhost";
char buf[BUF_LEN];
main()
{
struct hostent *servhost;
struct sockaddr_in server;
int s;
servhost = gethostbyname(hostname);
bzero((char *)&server,sizeof(server));
server.sin_family = AF_INET;
server.sin_port = PORT;
bcopy(servhost->h_addr,
(char *)&server.sin_addr,servhost->h_length);
s = socket(AF_INET,SOCK_STREAM,0);
connect(s,(void *)&server,sizeof(server));
read(s,buf,BUF_LEN);
printf(buf);
close(s);
}
サーバプログラム（C）
//server.c
me.sin_family = AF_INET;
me.sin_port = PORT;
#include<stdio.h>
#include<sys/types.h>
#include<sys/socket.h>
#include<netinet/in.h>
#include<netdb.h>
#include<string.h>
#define PORT (u_short)10000
char hostname[] = "localhost";
bcopy(myhost->h_addr,
(char *)&me.sin_addr,myhost->h_length);
s_waiting = socket(AF_INET,SOCK_STREAM,0);
bind(s_waiting,(void *)&me,sizeof(me));
main()
listen(s_waiting, 1);
{
s = accept(s_waiting, NULL, NULL);
struct hostent *myhost;
close(s_waiting);
struct sockaddr_in me;
int s_waiting, s;
write(s, msg, strlen(msg));
char msg[] = "Hello World!!\n";
close(s);
myhost = gethostbyname(hostname);
bzero((char *)&me, sizeof(me));
}
クライアントプログラム（Java）
import java.io.*;
import java.net.*;
import java.lang.*;
//サーバ側から送信された文字列を受信
byte[] buff = new byte[1024];
int a = is.read(buff);
System.out.write(buff, 0, a);
public class Client{
public static void main( String[] args ){
//ストリーム，ソケットをクローズ
is.close();
socket.close();
try{
//ソケットを作成
String host="localhost";
Socket socket = new Socket( host, 10000 );
//入力ストリームを作成
DataInputStream is = new DataInputStream (
new BufferedInputStream(
socket.getInputStream()));
}catch(Exception e){
System.out.println(e.getMessage());
e.printStackTrace();
}
}
}
サーバプログラム（Java）
//Server.java
import java.net.*;
import java.lang.*;
import java.io.*;
//ストリーム，ソケットをクローズ
os.close();
cliSocket.close();
svSocket.close();
}catch( Exception e ){
System.out.println(e.getMessage());
e.printStackTrace();
}
public class Server{
public static void main( String[] args ){
try{
//ソケットを作成
ServerSocket svSocket = new ServerSocket(10000);
//クライアントからのコネクション要求受付
Socket cliSocket = svSocket.accept();
//出力ストリームを作成
DataOutputStream os = new DataOutputStream(
new BufferedOutputStream(
cliSocket.getOutputStream()));
//文字列を送信
String s = new String("Hello World!!\n");
byte[] b = s.getBytes();
os.write(b, 0, s.length());
}
}
並列計算の枠組み (MPI)
Massive parallel computer
gateway
user
Jobs
Tasks
PC-Cluster
並列計算の分類
MPIの枠組み
# include “mpi.h”
int main( int argc, char **argv )
{
MPI_Init(&argc, &argv ) ;
MPI_Comm_size( …… )；
MPI_Comm_rank( …… ) ;
Initialization
Communicator
Acquiring number of process
Acquiring rank
/* parallel procedure */
MPI_Finalize( ) ;
return 0 ;
}
Termination
通信方法
１対１通信
Process A
Receive/send data
グループ通信
Receive/send data
Process B
１対１通信
[Sending]
MPI_Send( void *buf, int count,
MPI_Datatype datatype, int dest, int tag,
MPI_Comm comm)
void *buf：Sending buffer starting address (IN)
int count：Number of Data (IN)
MPI_ Datatype datatype：data type (IN)
int dest：receiving point (IN)
int tag：message tag (IN)
MPI_Comm comm：communicator(IN)
１対１通信
[Receiving]
MPI_Recv( void *buf, int count,
MPI_Datatype datatype, int source, int tag,
MPI_Comm comm, MPI_Status status)
void *buf：Receiving buffer starting address (OUT)
int source：sending point (IN)
int tag：Message tag (IN)
MPI_Status *status：Status (OUT)
~Hello.c~
#include <stdio.h>
#include "mpi.h"
void main(int argc,char *argv[])
{
int myid,procs,src,dest,tag=1000,count;
char inmsg[10],outmsg[]="hello";
MPI_Status stat;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
count=sizeof(outmsg)/sizeof(char);
if(myid == 0){
src = 1; dest = 1;
MPI_Send(&outmsg,count,MPI_CHAR,dest,tag,MPI_COMM_WORLD);
MPI_Recv(&inmsg,count,MPI_CHAR,src,tag,MPI_COMM_WORLD,&stat);
printf("%s from rank %d\n",&inmsg,src);
}else{
src = 0; dest = 0;
MPI_Recv(&inmsg,count,MPI_CHAR,src,tag,MPI_COMM_WORLD,&stat);
MPI_Send(&outmsg,count,MPI_CHAR,dest,tag,MPI_COMM_WORLD);
printf("%s from rank %d\n",&inmsg,src);
}
MPI_Finalize();
}
１対１通信
MPI_Recv(&inmsg,count,MPI_CHAR,src,
tag,MPI_COMM_WORLD,&stat);
MPI_Send(&outmsg,count,MPI_CHAR,dest,
tag,MPI_COMM_WORLD);
MPI_Sendrecv(&outmsg,count,MPI_CHAR,dest,
tag,&inmsg,count,MPI_CHAR,src,
tag,MPI_COMM_WORLD,&stat);
π計算
-Parallel conversion-
4
 
dx
2
0 1 x
1
4
3.5
3
部分に分割
y
2.5
2
分割部分を各プロ
セッサに割り当て
1.5
1
0.5
結果を収集
0
0.1
0.2
0.3
0.4
0.5
0.6
x
0.7
0.8
0.9
1
グループ通信
Broadcast
MPI_Bcast( void *buf, int count, MPI_Datatype
datatype, int root, MPI_Comm comm )
Rank of sending point
Data
グループ通信
• Communication and operation (reduce)
MPI_Reduce( void *sendbuf, void *recvbuf, int
count, MPI_Datatype datatype, MPI_Op op,
int root, MPI_Comm comm ) Operation handle
Rank of receiving point
Operation
MPI_SUM, MPI_MAX,
MPI_MIN, MPI_PROD
π計算の流れ
PCクラスタの高性能化
CPU
Hardware
Intel Pentium III, IV http://www.intel.com/
http://www.amd.com/
AMD Athlon
Transmeta Crusoe http://www.transmeta.com/
Network
Ethernet
Gigabit
Ethernet
Myrinet
QsNet
Giganet
SCI
Gigabit
Wake On LAN
ネットワークの２重化
Hardware
Atoll
VIA
Infinband
Myrinet
• Myricom社が開発
• PCクラスタコンピューティングの
デファクト・スタンダードとして期待
– EthernetやATMなどより優れた
性能，コストパフォーマンスを発揮
各ネットワークの性能比較（１）
各ネットワークの性能比較
（２）
従来の通信
送信側
ユーザ
アドレス空間
受信側
ユーザ
アドレス空間
データ
データ
コ
ピー
コ
ピー
データ
データ
カーネル
アドレス空間
カーネル
アドレス空間
データ
データ
NIC
NIC
ゼロコピー通信
送信側
ユーザ
アドレス空間
受信側
ユーザ
アドレス空間
データ
データ
カーネル
アドレス空間
カーネル
アドレス空間
データ
データ
NIC
NIC
ハードディスク
Hardware
SCSI
IDE
Raid
Diskless Cluster
http://www.linuxdoc.org/HOWTO/Diskless-HOWTO.html
ジャーナリングファイルシステム
ケース
Box
inexpensive
Rack
compact
maintenance
Hardware
ソフトウエア
Software
OS
Linux Kernels
Open source
Free ware
Features
network
The /proc file system
Loadable kernel
modules
Virtual consoles
Package management
OS
Linux Kernels
http://www.kernel.org/
Linux Distributions
Red Hat
Debian GNU/Linux
S.u.S.E.
Slackware
www.redhat.com
www.debian.org
www.suse.com
www.slackware.org
管理ツール
NFS（Network File System)
NIS (Network Information
System)
NTP (Network Time Protocol)
server
client
client
client
リソースマネージメントとスケジューリングツール
プロセスの分配
ロードバランス
複数タスクのジョブ管理
CONDOR
http://www.cs.wisc.edu/condor/
DQS
http://www.scri.fsu.edu/~pasko/dqs.html
LSF
http://www.platform.com/index.html
The Sun Grid Engine
http://www.sun.com/software/gridware/
プログラミング開発ツール
Editor
Language
Compiler
Emacs
C, C++, Fortran, Java
GNU http://www.gnu.org/
NAG http://www.nag.co.uk
PGI http://www.pgroup.com/
VAST http://www.psrv.com/
Absoft http://www.absoft.com/
Fujitsu http://www.fqs.co.jp/fort-c/
Intel
http://developer.intel.com/software/
products/compilers/index.htm
プログラミング開発ツール
Make
CVS
Debugger
Gdb
Total View
http://www.etnus.com
MPIの実装
mpich
http://www-unix.mcs.anl.gov/mpi/index.html
Easy to use
High portability
for UNIX, NT/Win, Globus
Lam
http://www.lam-mpi.org/
High availability
MPICH VS LAM （SMP)
# node
Processor type
Memory
OS
Network
DGA
Gcc(2.95.3), mpicc
-O2 –funroll - loops
60
40
30
40
30
20
20
10
10
0
0
0
1X
5X
10X
50X
100X
500X
50
Speedup
50
Speedup
60
1X
5X
10X
50X
100X
500X
20
40
60
32 ,2
Pentium III 700MHz
128 Mbytes
Linux 2.2.16
Fast Ethernet，TCP/IP
Switching HUB
0
20
40
Number of Process
Number of Process
LAM (6.3.2)
MPICH (1.2.1)
60
MPICH VS LAM (# process)
# node
processor
memory
OS
Network
8
8
6
6
4
Speedup
Speedup
DGA
Gcc(2.95.3), mpicc
-O2 –funroll - loops
1X
5X
10X
50X
100X
500X
2
8
PentiumⅢ 850MHz
256 Mbytes
Linux 2.2.17
Fast Ethernet，TCP/IP
Switching HUB
4
2
0
0
0
10
20
30
0
10
20
Number of Process
Number of Process
LAM (6.4-a3)
MPICH (1.2.0)
30
プロファイラー
MPE (MPICH)
Paradyn
http://www.cs.wisc.edu/par
adyn/
Vampier
http://www.pallas.de/pages/
vampir.htm
Win用のメッセージパッシングライブラリ
PVM
MPI
PVM3.4
WPVM
mpich
WMPI(Critical Software)
MPICH/NT
(Mississippi State Univ.)
MPI Pro
(MPI Software Technology)
クラスタのディストリビューション
FAI http://www.informatik.uni-koeln.de/fai/
Alinka http://www.alinka.com/
Mosix http://www.mosix.cs.huji.ac.il/
Bproc
http://www.beowulf.org/software/bproc.html
Scyld http://www.scyld.com/
Score
http://pdswww.rwcp.or.jp/dist/score/html/index.html
Kondara HPC
http://www.digitalfactory.co.jp/
Math Library
PhiPac from Berkeley
FFTW from MIT
www.fftw.org
Atlas
Automatic Tuned Linear Algebra software
www.netlib.org/atlas/
ATLAS is an adaptive software architecture and
faster than all other portable BLAS
implementations and it is comparable with
machine specific libraries provided by the vender.
Math Library
PETSc
PETSc is a large stuite of data structures
and routines for both uni and parallel processor
scientific computing.
http://www-fp.mcs.anl.gov/petsc/
遺伝的アルゴリズム
GAsの並列モデル
Master Slave (Micro grained )
Cellular (Fine grained)
Distributed GAs
(Island, Coarse grained)
Amdahl’s low
Speed up =
1
(1 – r) + r / Number of processors
r: ratio of parallelization
20
0.90
15
0.80
0.50
10
2000
5000
10000
200
500
1000
50
100
0
2
5
10
20
5
1
Speed up
0.95
Number of Processors
Master Slave model
Master node
crossover
mutation
evaluation
evaluate
evaluate
client client client
client client client
a) delivers each
individual to slave
b) returns the value
as soon as finishes
calculation
selection
evaluate
client client client
c) sends nonevaluated
individual from
master
Cellular GAs
Distributed Genetic Algorithms
(Island GAs)
subpopulation
migration
Migration interval
Generation
Distributed Genetic Algorithms
island 0
island 1
island n
GA
GA
GA
migration
GA
GA
GA
migration
= migration rate
Cambria
Visual Technology
# node 256
# CPUs: 256
CPU: Pentium III 0.8GHz
Memory:32GB(128MB × 256)
Hard Disc:
Network: FastEithernet
Hub:
DGAの並列化効率
DGAsの探索性能
教科書，Web sites，その他
教科書
“Building Linux
Clusters”
“How to Build
Beowulf”
“High Performance
Cluster Computing”
教科書
MPI並列プログラミング
虎の巻きシリーズ
Web sites
IEEE Computer Society Task Force on
Cluster Computing
http://www.ieeetfcc.org/
White Paper
http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/
Cluster top 500
http://clusters.top500.org/
Beowulf Project
http://www.beowulf.org/
Beowulf Under Ground
http://www.beowulf-underground.org/
学会その他
IEEE TFCC
超並列計算研究会
SOFTEK HPC メイリングリスト
Debian Beowulf
このチュートリアルでは….
クラスタのコンセプト
クラスタの作り方
並列GA

Download Report