Transcript 集中講義 計算量理論と並列分散 アルゴリズムについて

Part 4 Current trend of parallel processing
(1) Cluster computing
(2) Grid computing)
1
Traditional parallel processing
• Vector type or shared memory type or distributed memory
type
• Special technology/architecture
• Very expensive (millions 〜100 millions dollars), long
developing period
• One computer used by a number of users
• Special ＯＳ and programming languages
• Limited users
2
New trend of parallel processing
Cluster computing
Grid computing
Features
• Cheap to construct processing environments.
• Easy to popularize because of the use of ordinary computers.
3
Cluster processing
What is cluster processing
• Use a number of work stations or PCs to construct a virtual parallel
computer.
• Comparing with parallel computers, cluster processing is
cheap.
• Performance is worse than parallel computers, but it can be
largely improved by using high performance network（100BASE-TX,
ATM, etc.).
4
Outline of global computing
What is global (GRID) computing
• Use all the resources on internet to construct a super distributed
parallel virtual computer
Super parallel
computers
Intranet
+
Internet
User
High performance
PC
PC cluster
5
Implement of cluster processing (1)
Well known software for cluster processing
• PVM (Parallel Virtual Machine)
• MPI (Message Passing Interface)
History of PVM
1989
1991
1993
1994
2001
PVM1.0 released by Oak Rige National Laboratory.
PVM2.0 released by University of Tennessee.
PVM3.0 released.
Published with free manual
PVM 3.4.3 released with C and Fortran.
6
Implement of cluster processing (2)
History of MPI
1993-1994 Specification (MP-I) was decided by the
experts from 40 companies.
1995 Specification of MPI-2 was decided.
2001 MPI-1.1 based implementation was released.
• It is used as default environment in many distributed parallel
processing systems.
7
Common points of PVM and MPI
• Communication is based on 1 to 1 message passing.
Processor ID: ３
send(5, message）
Processor ID: ５
receive(3)
• They are designed for not only work stations and PCs but
also parallel computers.
• Corresponding to many OS and Languages.
（OS: UNIX, Windows95/NT, Languages: C, Fortran, JAVA)
• Free
• Standard software in distributed and parallel computing.
8
Construction of PVM
Software of PVM
• Daemon pvmd used for the communication between
processors.
• Console pvm used for constructing virtual parallel computer
（xpvm is the console combined with GUI)
• Library of functions such as pvm_send and pvm_receive
for message sending and receiving.
A virtual parallel computer
pvmd
pvmd
(opty1)
(optima)
On any computer, one can use pvm
or xpvm to construct a virtual parallel
computer, and then make and
execute programs.
pvmd
pvmd
(opty2)
(opty3)
（Constructed by connected 4 computers ）
9
Start of PVM (1)
(1) On any computer, use command pvm or xpvm to start pvmd.
On optima, use pvm or xpvm
to start pvmd .
10
Start of PVM (2)
(2) On console pvm add computers to construct a virtual parallel
computer. (At the this time, pvmd is started in these computers.)
On optima
add opty1, opty2, opty3 to virtual
parallel computer by pvmd.
11
Execution of PVM (1)
Program execution on PVM
(1) When the program which contains communication functions of
pvm is executed, the specified programs will be executed by pvmd
When program prog1 is executed on optima
which contains communication functions,
the process (in this case prog 1) will be
started in all processors by pvmd.
12
Execution of PVM (2)
(2) Once the execution of a program started, communication and
processing inside the program will be done automatically until the end.
Processing is held with
the communication between processors.
13
Using PVM (1)
Using command pvm
chen[11]% pvm
pvm> add opty1 opty2 opty3（add opty1, opty2, opty3 to the virtual
computer）
3 successful
HOST
DTID
opty1
80000
opty2
c0000
opty3
100000
pvm> conf (Show the configuration of the virtual parallel computer)
4 hosts, 1 data format
HOST
DTID
ARCH
SPEED
DSIG
optima
40000 X86SOL2
1000
0x00408841
opty1
80000 X86SOL2
1000
0x00408841
opty2
c0000 X86SOL2
1000
0x00408841
opty3
100000 X86SOL2
1000
0x00408841
pvm> spawn edm4 （Execute program edm4 on the virtual computer)
1 successful
t80001
pvm> halt
（Halt of the virtual computer）
Terminated
chen[12]%
14
Using PVM (2)
• Using xpvm (X application)
15
PVM programming (1)
Example (hello.c, hello_other.c)
(hello.c)
(hello_other.c)
#include "pvm3.h"
#include "pvm3.h"
main() {
int tid, answer;
main() {
int mytid, ptid;
pvm_spawn("hello_other",
(char**)0,0,"",1, &tid);
printf("Hello, Dr.t%x\n",tid);
mytid = pvm_mytid();
ptid = pvm_parent();
printf("Good morning,
Prof. t%x.\n",ptid);
pvm_recv(tid,1);
pvm_upkint(&answer,1,1);
printf("Fine, thank you,
Dr. t%x", answer);
printf("How are you?\n");
pvm_initsend(PvmDataDefault);
pvm_pkint(&mytid,1,1);
pvm_send(ptid, 1);
pvm_exit();
}
pvm_exit();
}
16
PVM Programming (2)
Start the process hello
Hello, Dr. t80004
(Process hello_other is
started on other computers pvm_spawn
by pvm_spawn.
Started process has its task ID.)
（Process hello_other is started）
Hello, Prof. t4000a.
How are you?
pvm_send
（Send message by pvm_send）
pvm_recv
（Finish the process by pvm_exit）
（Receive the message by pvm_recv）
Fine, thank you, Dr. t80004
（Finish the process by pvm_exit）
17
Grid computing (1)
• Distributed and parallel processing techniques
- TCP/IP protocol such as telnet, rlogin
- Cluster processing such as PVM, MPI
- WWW related technique such as HTTP/HTML/CGI
- Agent related technique such as Plangent, Aglets
- ...
They can not be used to Grid computing without changing.
（Some of them can be used.）
18
Grid computing (2)
Abilities necessary for grid computing
•
•
•
•
•
Generalization: easy to add computers
Security: unknown users，mobile users
Tolerance of fault
Heterogeneity: Language，OS，hardware, security level
High performance: super high performance, super high
speed network
• Scalability：Very large scale
LAN
Internet
東京
LAN
大阪
Internet
LAN
福岡
19
Grid computing (3)
History of Grid computing
•
•
•
•
•
•
•
•
•
1980’s：Distributed computing
1990’s：Gigabit network
I-way, 1995: Application
Alliance (NCSA) Virtual Machine Room
PACIs (NCSA/SDSC NSF National Technology Grid), 1998〜
NASA Information Power Grid, 1999〜
eGrid (European Grid), 2000〜
ApGrid (Asia-Pacific Grid) 2000〜
...
20
Implement of grid computing
Software for grid computing
•
•
•
•
Toolkit: Globus, Legion, AppLes
Message passing: MPICH-G2
GridRPC: Ninf, Netsolve, Nimrod
Business software:United Devices, Entropia, Parabon,...
Ninf is developed in Japan
21
Achievement of Ninf
• Solving 大規模非凸２次計画問題 by SCRM (kojima-Tuncel-Takeda)
method:
The world record is achieved by using large scale cluster
(128 processors)
• Solving Cyclic Polynomial Equation by Homotopy method:
The world record is achieved by using large scale cluster
(128 processors)
22
Summary (1)
Changing in parallel processing
• From parallel computers to cluster processing ＆grid computing
• Combined with high performance network
• Using popular technologies
Using internet which has huge processing ability
• Parallel processing becomes possible for ordinary users
• Advanced technologies are necessary.
23
Summary (2)
Cluster processing
• wide used technologies are used for parallel processing.
• Parallel processing becomes possible for ordinary users.
Grid computing
• 最先端の広帯域ネットワークを用いたインフラ技術
• Combination of network technology and computing technology
• Great progress in computer related fields.
Necessity of the comprehensive research
• Parallel processing，Language，OS
• Network
• Application
24