`
blovedot
  • 浏览: 13169 次
  • 性别: Icon_minigender_1
  • 来自: 南昌
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

分布式、并行计算语言Erlang 学习笔记(全)

阅读更多
分布式、并行计算语言Erlang 学习笔记(第一部分)
Erlang是由爱立信公司开发的一种平台式语言,可以说是一种自带了操作系统平台的编程语言,而且在这个平台上实现了并发机制、进程调度、内存管理、分布式计算、网络通讯等功能,这些功能都是完全独立于用户的操作系统的,它采用的是类似于Java一样的虚拟机的方式来实现对操作系统的独立性的。
介绍一下Erlang先:
1、并发性:Erlang的轻量级进程可以支持极高的并发性,而且在高并发的情况下内存使用相当的少。Erlang的并发性并不会受到宿主操作系统并发性的限制。
2、分布式:最开始Erlang的设计目标就是实现分布式环境,一个Erlang的虚拟机就是一个Erlang网络上的节点。一个Erlang节点可以在另一个Erlang节点上创建自己的并发进程,而子进程所在的节点可能是运行其他的操作系统的服务器。不同节点的之间的可以进行极为高效而又精确的通信,就像它们运行在同一个节点一样。
3、鲁棒形:Erlang内部建设有多种错误检测原语。我们可以通过这些原语来架设高容错性的系统。例如,一个进程可以监视其他进程的状态和活动,即使那些被监控的进程处于其他节点。在分布式状态下,我们可以把系统配置成具有Fail-over功能的分布式系统。当有其他节点出错的时候,系统会把他的运行场景自动快速的切换备份节点上。Erlang支持9个9的级别的故障率,一年只有几分钟的故障时间。
4、软实时:Erlang是一个“软”实时系统(Soft Real Time),它可以提供毫秒级别的响应。
一般的情况下,使用Erlang系统可以比其他系统的并发能力(例如Web会话负载)放大20~30倍。
下面我们就从Erlang的基础开始:
第一部分:Sequential Programming 顺序化编程
目录
--------------------------------------------------------------------------------
Numbers.
    ——Integers 整型
    ——Floats 浮点型
Atoms 字符串
Tuples 复表
Lists 链表
Variables 变量
Complex Data Structures 复杂数据结构
Pattern Matching 匹配赋值
Function Calls 函数调用
The Module Systems 模块系统
Starting the system 启动系统
Built in Functions (BIFs) 内建函数
Function syntax 函数语法
An example of function evaluation 一个例子
    ——Guarded function clauses 条件子句
Examples of Guards 使用条件判断的例子
Traversing Lists 操作链表
Lists and Accumulators 链表和聚集器
Shell commands Shell命令
Special Functions 特殊函数
Special Forms 特殊形式
--------------------------------------------------------------------------------
Numbers
Integers
10
-234
16#AB10F
2#110111010
$A
Floats
17.368
-56.654
12.34E-10.
B#Val is used to store numbers in base < B >.
B#Val:Val是用B进制表示的。
$Char is used for ascii values (example $A instead of 65).
$Char的值为Char代表的ASCII代码值,例如$A等于65。
--------------------------------------------------------------------------------
Atoms
abcef
start_with_a_lower_case_letter
'Blanks can be quoted'
'Anything inside quotes \n\012'
Indefinite length atoms are allowed.
系统允许无限长度的字符串。
Any character code is allowed within an atom.
在字符串中允许加入ASCII码代表的数字,只不过需要转义一下
--------------------------------------------------------------------------------
Tuples
{123, bcd}
{123, def, abc}
{person, 'Joe', 'Armstrong'}
{abc, {def, 123}, jkl}
{}
Used to store a fixed number of items.
可以用来存储定长的项。
Tuples of any size are allowed.
对一个复表来说。可以是任意长度的,只不过定下来长度后不能更改而已。
--------------------------------------------------------------------------------
Lists
[123, xyz]
[123, def, abc]
[{person, 'Joe', 'Armstrong'},
  {person, 'Robert', 'Virding'},
  {person, 'Mike', 'Williams'}
]
"abcdefghi"
        becomes - [97,98,99,100,101,102,103,104,105]
""
        becomes - []
Used to store a variable number of items.
用来存储不定长的项。
Lists are dynamically sized.
允许动态改变链表的长度。
"..." is short for the list of integers representing the ascii character codes of the enclosed within the quotes.
使用""包括起来的字符串将被转换为对应的ASCII码。
--------------------------------------------------------------------------------
Variables
Abc
A_long_variable_name
AnObjectOrientatedVariableName
Start with an Upper Case Letter.
以大写字母开始。
No "funny characters".
不允许一些奇怪的字符出现。
Variables are used to store values of data structures.
变量是用来存储数据结构内容的。
Variables can only be bound once! The value of a variable can never be changed once it has been set (bound).
变量只能被绑定一次,一旦绑定完成后,不允许修改原绑定关系。
--------------------------------------------------------------------------------
Complex Data Structures
[{{person,'Joe', 'Armstrong'},
       {telephoneNumber, [3,5,9,7]},
       {shoeSize, 42},
       {pets, [{cat, tubby},{cat, tiger}]},
       {children,[{thomas, 5},{claire,1}]}},
  {{person,'Mike','Williams'},
       {shoeSize,41},
       {likes,[boats, beer]},
...
Arbitrary complex structures can be created.
可以创建任意复杂的数据结构。
Data structures are created by writing them down (no explicit memory alloca- tion or deallocation is needed etc.).
数据结构的定义很简单,只需要写下来就可以了,不用关心显式的分配和删除内存区域。
Data structures may contain bound variables.
数据的结构中允许使用变量。
--------------------------------------------------------------------------------
Pattern Matching
A = 10
Succeeds - binds A to 10
操作成功,A被绑定为10
{B, C, D} = {10, foo, bar}
Succeeds - binds B to 10, C to foo and D to bar
操作成功,B被绑定为10,C为foo,D为bar
{A, A, B} = {abc, abc, foo}
Succeeds - binds A to abc, B to foo
操作成功,A为abc,B为foo

{A, A, B} = {abc, def, 123}
Fails
操作失败

[A,B,C] = [1,2,3]
Succeeds - binds A to 1, B to 2, C to 3
操作成功,A为1,B为2,C为3

[A,B,C,D] = [1,2,3]
Fails
操作失败
--------------------------------------------------------------------------------
Pattern Matching (Cont)
[A,B|C] = [1,2,3,4,5,6,7]
Succeeds - binds A = 1, B = 2,C = [3,4,5,6,7]
操作成功,A为1,B为2,C为[3,4,5,6,7]

[H|T] = [1,2,3,4]
Succeeds - binds H = 1, T = [2,3,4]
操作成功,H为1,T为[2,3,4]

[H|T] = [abc]
Succeeds - binds H = abc, T = []
操作成功,H为abc,T为[]

[H|T] = []
Fails
操作失败

{A,_, [B|_],{B}} = {abc,23,[22,x],{22}}
Succeeds - binds A = abc, B = 22
操作成功,A为abc,B为22
Note the use of "_", the anonymous (don't care) variable.
注意:"_"为匿名变量
--------------------------------------------------------------------------------
Function Calls
module:func(Arg1, Arg2, ... Argn)
func(Arg1, Arg2, .. Argn)
Arg1 .. Argn are any Erlang data structures.
Arg1到Argn可以是任意的Erlang的合法数据类型。
The function and module names (func and module in the above) must be atoms.
函数名和模块名必须是字符串。
A function can have zero arguments. (e.g. date() - returns the current date).
函数允许不带参数。例如date()返回当前的日期。
Functions are defined within Modules.
函数应在模块内被定义。
Functions must be exported before they can be called from outside the module where they are defined.
在定义该函数的模块外调用该函数之前,必须首先在外声明该函数(export)。
--------------------------------------------------------------------------------
Module System
-module(demo).
-export([double/1]).
double(X) ->
times(X, 2).
times(X, N) ->
X * N.
double can be called from outside the module, times is local to the module.
double函数可以在模块外进行调用,times函数位于该模块内。
double/1 means the function double with one argument (Note that double/1 and double/2 are two different functions).
double/1意味着该函数带有一个参数的形式,如果是double/2,则代表这带有两个参数的double函数原型。
--------------------------------------------------------------------------------
Starting the system
unix> erl
Eshell V2.0
1> c(demo).
double/1 times/2 module_info/0
compilation_succeeded
2> demo:double(25).
50
3> demo:times(4,3).
** undefined function:demo:times[4,3] **
** exited: {undef,{demo,times,[4,3]}} **
4> 10 + 25.
35
5>
c(File) compiles the file File.erl.
c(File)意味着编译文件File.erl
1> , 2> ... are the shell prompts.
1> , 2> ...是提示符而已~~
The shell sits in a read-eval-print loop.
Shell忠实的进行着读取命令->执行->输出结果的循环。
--------------------------------------------------------------------------------
Built In Functions (BIFs)
date()
time()
length([1,2,3,4,5])
size({a,b,c})
atom_to_list(an_atom)
list_to_tuple([1,2,3,4])
integer_to_list(2234)
tuple_to_list({})
Are in the module erlang.
内建函数是默认的Erlang模块中的。
Do what you cannot do (or is difficult to do) in Erlang.
它们负责做哪些我们很难或者不能够在Erlang中做到的事情。
Modify the behaviour of the system.
用于修改系统的行为模式。
Described in the BIFs manual.
可以参考内建函数的手册。
--------------------------------------------------------------------------------
Function Syntax
Is defined as a collection of clauses.
它们由一系列的字句所定义。
func(Pattern1, Pattern2, ...) ->
... ;
func(Pattern1, Pattern2, ...) ->
... ;
...
func(Pattern1, Pattern2, ...) ->
... .
Evaluation Rules
执行规则
Clauses are scanned sequentially until a match is found.
子句被顺序的扫描,直到找到匹配的为止。
When a match is found all variables occurring in the head become bound.
当一个匹配成功时,所有的形式变量就被绑定。
Variables are local to each clause, and are allocated and deallocated automatically.
变量存在于函数的生存周期内,它的内存的分配和销毁都是自动实现的。
The body is evaluated sequentially.
函数体的执行是顺序的。
--------------------------------------------------------------------------------
Functions (cont)
-module(mathStuff).
-export([factorial/1, area/1]).
factorial(0) -> 1;
factorial(N) -> N * factorial(N-1).

area({square, Side}) ->
       Side * Side;
area({circle, Radius}) ->
       % almost :-)
       3 * Radius * Radius;
area({triangle, A, B, C}) ->
       S = (A + B + C)/2,
       math:sqrt(S*(S-A)*(S-B)*(S-C));
area(Other) ->
       {invalid_object, Other}.
--------------------------------------------------------------------------------
Evaluation example
factorial(0) -> 1;
factorial(N) ->
N * factorial(N-1)
> factorial(3)
matches N = 3 in clause 2
== 3 * factorial(3 - 1)
== 3 * factorial(2)
matches N =2 in clause 2
== 3 * 2 * factorial(2 - 1)
== 3 * 2 * factorial(1)
matches N = 1 in clause 2
== 3 * 2 * 1 * factorial(1 - 1)
== 3 * 2 * 1 ? factorial(0)
== 3 * 2 * 1 ? 1 (clause 1)
== 6
Variables are local to each clause.
Variables are allocated and deallocated automatically.
变量存在于函数的生存周期内,它的内存的分配和销毁都是自动实现的。
--------------------------------------------------------------------------------
Guarded Function Clauses
factorial(0) -> 1;
factorial(N) when N > 0 ->
         N * factorial(N - 1).
The reserved word when introduces a guard.
关键字when引入了一个条件。
Fully guarded clauses can be re-ordered.
完善的条件判断可以把代码重排列而不出错。
factorial(N) when N > 0 ->
         N * factorial(N - 1);
factorial(0) -> 1.
This is NOT the same as:
不等同于一下的代码:
factorial(N) ->
      N * factorial(N - 1);
factorial(0) -> 1.
(incorrect!!)
这是不正确的!
--------------------------------------------------------------------------------
Examples of Guards
number(X) - X is a number X是一个实数
integer(X) - X is an integer X是一个整型
float(X) - X is a float X是一个浮点型
atom(X) - X is an atom X是一个字符串
tuple(X) - X is a tuple X是一个复表
list(X) - X is a list X是一个链表
length(X) == 3 - X is a list of length 3 X是一个长度为3的链表
size(X) == 2 - X is a tuple of size 2. X是一个大小为2的复表
X > Y + Z - X is > Y + Z X大于Y+Z
X == Y - X is equal to Y X等于Y
X =:= Y - X is exactly equal to Y X精确的等于Y
(i.e. 1 == 1.0 succeeds but
1 =:= 1.0 fails)
注意:1==1.0是正确的,但是1=:=1.0是不正确的,涉及精度问题。
All variables in a guard must be bound.
所有进行比较的变量必须经过绑定。
--------------------------------------------------------------------------------
Traversing Lists
average(X) -> sum(X) / len(X).
sum([H|T]) -> H + sum(T);
sum([]) -> 0.
len([_|T]) -> 1 + len(T);
len([]) -> 0.
Note the pattern of recursion is the same in both cases. This pattern is very common.
注意递归的写法,这是程序设计中很常见的。
Two other common patterns:
另外两种常见的样式为:
double([H|T]) -> [2*H|double(T)];
double([]) -> [].
member(H, [H|_]) -> true;
member(H, [_|T]) -> member(H, T);
member(_, []) -> false.
--------------------------------------------------------------------------------
Lists and Accumulators
average(X) -> average(X, 0, 0).
average([H|T], Length, Sum) ->
       average(T, Length + 1, Sum + H);
average([], Length, Sum) ->
       Sum / Length.
Only traverses the list ONCE
只需要操作该链表一次
Executes in constant space (tail recursive)
执行是原地进行的(尾部递归)
The variables Length and Sum play the role of accumulators
变量Length和Sum扮演着汇聚的角色
N.B. average([]) is not defined - (you cannot have the average of zero elements) -
evaluating average([]) would cause a run-time error - we discuss what happens when run time errors occur in the section on error handling .
注意:average([])是没有定义的(也就是说我们不能不带参数的调用该函数)——计算average([])将导致一个运行时错误,我们将在异常捕获中谈到。
--------------------------------------------------------------------------------
Shell Commands
h() - history . Print the last 20 commands.打印最后20条命令
b() - bindings. See all variable bindings.查看所有的变量绑定情况
f() - forget. Forget all variable bindings.清除所有的变量的绑定
f(Var) - forget. Forget the binding of variable 清除特定的变量的绑定
X. This can ONLY be used as a command to the shell - NOT in the body of a function!
只能在Shell环境下使用,不能在函数的函数体中使用!
e(n) - evaluate. Evaluate the n:th command in history.执行历史记录中的第n条命令
e(-1) - Evaluate the previous command. 执行上一条命令
Edit the command line as in Emacs
命令行的使用类似于Emacs的使用
--------------------------------------------------------------------------------
Special Functions
apply(Mod, Func, Args)
Apply the function Func in the module Mod to the arguments in the list Args.
将Func函数应用到Mod上,并带有参数Args。
Mod and Func must be atoms (or expressions which evaluate to atoms).
Mod和Func必须是字符串表示的(或者是表达式)
1> apply( lists1,min_max,[[4,1,7,3,9,10]]).
{1, 10}
Any Erlang expression can be used in the arguments to apply.
所有的Erlang表达式都可以用作Arg被使用。
--------------------------------------------------------------------------------
Special Forms
case lists:member(a, X) of
        true ->
                ... ;
        false ->
                ...
        end,
...
if
        integer(X) -> ... ;
        tuple(X) -> ...
end,
...
Not really needed - but useful.
虽然不是必须的,但是很有用就是了~~ 呵呵

分布式、并行计算语言Erlang 学习笔记(第二部分)
 
Concurrent Programming 并发编程
________________________________________
Definitions 定义
Creating a new process 创建新进程
Simple message passing 简单消息传递
An Echo Process 一个Echo进程
Selective Message Reception 选择性的消息接受
Selection of Any Message 任意消息的选择
A Telephony Example 电话的例子
Pids can be sent in messages 带有Pid的消息
Registered Processes 注册进程
The Client Server Model 客户端/服务器端模型
Timeouts 超时
________________________________________
Definitions 定义
Process - A concurrent activity. A complete virtual machine. The system may have many concurrent processes executing at the same time.
进程——一个并发活动。一个完整的虚拟机。这个系统可以同时拥有很多个并发进程。
Message - A method of communication between processes.
消息——一种进程间通讯的方式。
Timeout - Mechanism for waiting for a given time period.
超时——对一个有限长度的时间间隔的等待机制。
Registered Process - Process which has been registered under a name.
注册进程——有名字的进程。
Client/Server Model - Standard model used in building concurrent systems.
C/S模式——构建并发系统的标准模式。
________________________________________
Creating a New Process 创建一个新进程
Before之前

Code in Pid1 (Pid1中的代码)
Pid2 = spawn(Mod, Func, Args)

After之后
  
Pid2 is process identifier of the new process - this is known only to process Pid1.
Pid2被标识为新进程,只被进程Pid1所知晓。
________________________________________
Simple Message Passing 简单消息传递

self() - returns the Process Identity (Pid) of the process executing this function.
self()——返回当前正在执行的函数所在的进程的Pid标识符。
From and Msg become bound when the message is received. Messages can carry data.
From和Msg 构成消息传递的边界。消息可以携带数据。

Messages can carry data and be selectively unpacked.
消息可以携带数据,并可以被有选择性的解包(unpack)。
The variables A and D become bound when receiving the message.
变量A和D构成消息传递的边界(即被绑定在一起)。
If A is bound before receiving a message then only data from this process is accepted.
如果B在接收到消息之前是绑定到A,那么只有来自于A的消息(数据)才会被接受。
________________________________________
An Echo process 一个Echo进程
-module(echo).
-export([go/0, loop/0]).

go() ->
Pid2 = spawn(echo, loop, []),
Pid2 ! {self(), hello},
receive
{Pid2, Msg} ->
io:format("P1 ~w~n",[Msg])
end,
Pid2 ! stop.

loop() ->
receive
{From, Msg} ->
From ! {self(), Msg},
loop();
stop ->
true
end.
________________________________________
Selective Message Reception 有选择的消息接受

The message foo is received - then the message bar - irrespective of the order in which they were sent.
消息foo被接受——然后才是消息bar被接受,这和它们被发送的顺序无关。
________________________________________
Selection of any message 任意消息的选择

The first message to arrive at the process C will be processed - the variable Msg in the process C will be bound to one of the atoms foo or bar depending on which arrives first.
第一条消息抵达进程C被处理,进程C中的变量Msg将被绑定为字符串boo或者bar,这取决于虽首先到达。
________________________________________
A Telephony Example 电话的例子
 
ringing_a(A, B) ->
receive
{A, on_hook} ->
A ! {stop_tone, ring},
B ! terminate,
idle(A);
{B, answered} ->
A ! {stop_tone, ring},
switch ! {connect, A, B},
conversation_a(A, B)
end.
This is the code in the process `Call. A and B are local bound variables in the process Call.
上面的代码是进程Call的。A和B都是进程C的本地绑定变量。
________________________________________
Pids can be sent in messages 带有Pid的消息

A sends a message to B containing the Pid of A.
A发送消息给B,包含着A的Pid。
B sends a transfer message to C.
B将消息转交给C。
C replies directly to A.
C直接向A回应。
________________________________________
Registered Processes 注册进程
register(Alias, Pid) Registers the process Pid with the name Alias.
register(Alias, Pid)将给定的Pid附上名字Alias。
start() ->
Pid = spawn(num_anal, server, [])
register(analyser, Pid).

analyse(Seq) ->
analyser ! {self(),{analyse,Seq}},
receive
{analysis_result,R} ->
R
end.
Any process can send a message to a registered process.
任意的进程都可以发送消息给注册进程。
________________________________________
Client Server Model C/S模型
  
Protocol 协议

Server code 服务器代码
-module(myserver).

server(Data) ->
receive
{From,{request,X}} ->
{R, Data1} = fn(X, Data),
From ! {myserver,{reply, R}},
server(Data1)
end.
Interface Library 接口库
-export([request/1]).

request(Req) ->
myserver ! {self(),{request,Req}},
receive
{myserver,{reply,Rep}} ->
Rep
end.
________________________________________
Timeouts 超时

If the message foo is received from A within the time Time perform Actions1 otherwise perform Actions2.
如果从A出来的消息foo在Time时间内被接受,执行Actions1,否则执行Actions2。
Uses of Timeouts 使用超时
sleep(T)- process suspends for T ms.
sleep(T)-进程挂起T毫秒。
sleep(T) ->
receive
after
T ->
true
end.
suspend() - process suspends indefinitely.
suspend() -进程被挂起不确定的时间。
suspend() ->
receive
after
infinity ->
true
end.
alarm(T, What) - The message What is sent to the current process iin T miliseconds from now 。
alarm(T, What) -消息What从现在起经过T毫秒之后被发出。
set_alarm(T, What) ->
spawn(timer, set, [self(),T,What]).

set(Pid, T, Alarm) ->
receive
after
T ->
Pid ! Alarm
end.
receive
Msg ->
... ;
end
flush() - flushes the message buffer
flush() -清空消息缓冲区。
flush() ->
receive
Any ->
flush()
after
0 ->
true
end.
A value of 0 in the timeout means check the message buffer first and if it is empty execute the following code.
一个超时为0的代码意味着首先检查消息缓冲区,如果为空,则执行下面的代码。
分布式、并行计算语言Erlang 学习笔记(第三部分)
Error Handling 错误处理
--------------------------------------------------------------------------------
Definitions 定义
Exit signals are sent when processes crash 进程出错时的退出信号
Exit Signals propagate through Links 退出信号通过链接传播
Processes can trap exit signals 进程可以捕获退出信号
Complex Exit signal Propagation 复杂的退出信号传递
Robust Systems can be made by Layering 鲁棒系统的分层实现
Primitives For Exit Signal Handling 简单的退出信号处理
A Robust Server 一个鲁棒服务
Allocator with Error Recovery 带有错误恢复的分配器
Allocator Utilities 分配器工具
--------------------------------------------------------------------------------
Definitions 定义
Link A bi-directional propagation path for exit signals.
链接 退出信号的一个双向的传输路径。
Exit Signal - Transmit process termination information.
退出信号 发送的进程终止信息。
Error trapping - The ability of a process to process exit signals as if they were mssages. 错误捕获 进程间传递退出信号消息的一种能力。

--------------------------------------------------------------------------------
Exit Signals are Sent when Processes Crash
进程出错时的退出信号

When a process crashes (e.g. failure of a BIF or a pattern match) Exit Signals are sent to all processes to which the failing process is currently linked.
当一个进程挂掉了(例如BIF失败或者模式匹配失败),退出信号将发送给所有和该失效进程相关的其他进程。

--------------------------------------------------------------------------------
Exit Signals propagate through Links
退出信号通过链接传播

Suppose we have a number of processes which are linked together, as in the following diagram. Process A is linked to B, B is linked to C (The links are shown by the arrows).
Now suppose process A fails - exit signals start to propogate through the links:
假设我们有一组进程,它们之间是相互联系在一起的,如图所示。进程A链接到B,B链接到C(链接使用箭头表示)。现在假定进程A失效了,退出信号就开始以下面的方式传播:
These exit signals eventuall reach all the processes which are linked together.
退出信号可能到达所有互相链接在一起的进程。
The rule for propagating errors is: If the process which receives an exit signal, caused by an error, is not trapping exits then the process dies and sends exit signals to all its linked processes.
传播错误的规则是:如果一个进程接收到退出信号(可能是由于一个错误引起的),而没有加以捕获,这个进程失效并且发送退出信号给和它相链接的其他进程。

--------------------------------------------------------------------------------
Processes can trap exit signals
进程可以捕获退出信号

In the following diagram P1 is linked to P2 and P2 is linked to P3. An error occurs in P1 - the error propagates to P2. P2 traps the error and the error is not propagated to P3.
下图中,P1和P2链接,P2和P3链接。一个错误出现在P1,并且传递到P2。P2捕获该错误,该错误就不会传递到P3。

P2 has the following code:
P2的代码如下:
receive
{'EXIT', P1, Why} ->
... exit signals ...
{P3, Msg} ->
... normal messages ...
end
--------------------------------------------------------------------------------
Complex Exit signal Propagation
复杂的退出信号传递

Suppose we have the following set of processes and links:
假定我们有以下进程和链接关系:

The process marked with a double ring is an error trapping process.
使用双环标记的进程为错误捕获进程。

If an error occurs in any of A, B, or C then All of these process will die (through propagation of errors). Process D will be unaffected.
如果一个错误发生在A或者B或者C中,所有的进程都将失效(通过错误的传递)。进程D则不受影响。
--------------------------------------------------------------------------------
Exit Signal Propagation Semantics
退出信号传播语义

When a process terminates it sends an exit signal, either normal or non-normal, to the processes in its link set.
当一个进程终止的时候,它发出一个退出信号(不论是否正常退出)到和它链接在一起的所有进程。
A process which is not trapping exit signals (a normal process) dies if it receives a non-normal exit signal. When it dies it sends a non-normal exit signal to the processes in its link set.
一个没有捕获退出信号的进程(普通进程)在它接收到一个非正常退出信号的时候失效。它发出非正常退出信号给和它链接在一起的进程。
A process which is trapping exit signals converts all incoming exit signals to conventional messages which it can receive in a receive statement.
捕获了退出信号的进程将所有进入的退出信号转化为它可以接受的一般消息。
Errors in BIFs or pattern matching errors send automatic exit signals to the link set of the process where the error occured.
在BIF或者模式匹配中发生的错误将自动发送退出信号到该出错进程的链接进程集合。

--------------------------------------------------------------------------------
Robust Systems can be made by Layering
鲁棒系统的分层实现

By building a system in layers we can make a robust system. Level1 traps and corrects errors occuring in Level2. Level2 traps and corrects errors ocuring in the application level.
In a well designed system we can arrange that application programers will not have to write any error handling code since all error handling is isolated to deper levels in the system.
通过构造分层系统我们可以得到一个鲁棒系统。Level1捕获和纠正发生在Level2的错误。Level2捕获和纠正发生在应用层次上的错误。良好设计的系统我们可以安排程序不必写任何错误处理的代码,所有的错误处理都是由不同深度的层次独立负责的。

--------------------------------------------------------------------------------
Primitives For Exit Signal Handling
简单的退出信号处理

link(Pid) - Set a bi-directional link between the current process and the process Pid
link(Pid) 在当前的进程之间设置一个双向的链接。

process_flag(trap_exit, true) - Set the current process to convert exit signals to exit messages, these messages can then be received in a normal receive statement.
process_flag(trap_exit, true) 使用当前进程将退出信号转化为退出消息,这些消息可以通过一般的消息接受语句所接受。

exit(Reason) - Terminates the process and generates an exit signal where the process termination information is Reason.
exit(Reason) 终止进程,并且生成一个退出信号,包含的进程终止信息就是参数Reason。

What really happens is as follows: Each process has an associated mailbox - Pid?燤sg sends the message Msg to the mailbox associated with the process Pid.
The receive .. end construct attempts to remove messages from the mailbox of the current process. Exit signals which arrive at a process either cause the process to crash (if the process is not trapping exit signals) or are treated as normal messages and placed in the process mailbox (if the process is trapping exit signals). Exit signals are sent implicitly (as a result of evaluating a BIF with incorrect arguments) or explicitly (using exit(Pid, Reason), or exit(Reason) ).
到底真正发生了什么:每个进程都有一个关联着的邮箱(mailbox)-Pid,向邮箱内发消息就是与Pid所标识的进程进行通讯。receive...end结构尝试从当前进程的邮箱中删除消息。抵达进程的退出信号将导致进程失效(如果进程不捕获该退出信号的话)或者如同一般消息一样对待退出信号并且放入进程的邮箱中(如果进程捕获了退出信号)。退出信号被隐式的发送(执行带有错误参数的BIF导致的)或者显式的(使用exit(Pid,Reason)或者exit(Reason))。
If Reason is the atom normal - the receiving process ignores the signal (if it is not trapping exits). When a process terminates without an error it sends normal exit signals to all linked processes. Don't say you didn't ask!
如果Reason是一个字符串,一般情况下接受进程会忽略该信号。当一个没有发生错误的进程终止时发送正常退出信号到所有链接上的进程。
--------------------------------------------------------------------------------
A Robust Server
一个鲁棒服务

The following server assumes that a client process will send an alloc message to allocate a resource and then send a release message to deallocate the resource.
下面的server为一个client进程服务,通过发送请求分配的消息分配资源,发送释放消息来释放资源。
This is unreliable - What happens if the client crashes before it sends the release message?
这是不可靠的,如果client在发送释放消息之前就挂掉了呢?
top(Free, Allocated) ->
receive
{Pid, alloc} ->
top_alloc(Free, Allocated, Pid);
{Pid ,{release, Resource}} ->
Allocated1 = delete({Resource,Pid},燗llocated),
top([Resource|Free], Allocated1)
end.
top_alloc([], Allocated, Pid) ->
Pid ! no,
top([], Allocated);
top_alloc([Resource|Free], Allocated, Pid) ->
Pid ! {yes, Resource},
top(Free, [{Resource,Pid}|Allocated]).
This is the top loop of an allocator with no error recovery. Free is a list of unreserved resources. Allocated is a list of pairs {Resource, Pid} - showing which resource has been allocated to which process.
top没有带有错误恢复的进行循环的分配工作。Free是一个可以使用的资源的列表。分配的情况通过二元组来表示{Resource,Pid},表示哪个资源被哪个进程所使用了。
--------------------------------------------------------------------------------
Allocator with Error Recovery
带有错误恢复的分配器

The following is a reliable server. If a client craches after it has allocated a resource and before it has released the resource, then the server will automatically release the resource.
下面是一个可靠的服务,如果一个client在释放资源之前挂掉了,server将自动的释放该资源。
The server is linked to the client during the time interval when the resource is allocted. If an exit message comes from the client during this time the resource is released.
当进行资源分配的时候,该server链接到client。如果一个退出消息从client发出,资源也是被释放。
top_recover_alloc([], Allocated, Pid) ->
Pid ! no,
top_recover([], Allocated);
top_recover_alloc([Resource|Free], Allocated, Pid) ->
%% No need to unlink.
Pid ! {yes, Resource},
link(Pid),
top_recover(Free, [{Resource,Pid}|Allocated]).
top_recover(Free, Allocated) ->
receive
{Pid , alloc}?>
top_recover_alloc(Free, Allocated, Pid);
{Pid, {release, Resource}}?>
unlink(Pid),
Allocated1 = delete({Resource, Pid}, Allocated),
top_recover([Resource|Free], Allocated1);
{'EXIT', Pid, Reason}?>
%% No need to unlink.
Resource = lookup(Pid, Allocated),
Allocated1 = delete({Resource, Pid}, Allocated),
top_recover([Resource|Free], Allocated1)
end.
Not done -- multiple allocation to same process. i.e. before doing the unlink(Pid) we should check to see that the process has not allocated more than one device.
还没完~同一个进程的多次分配~在执行unlink(Pid)之前,我们应该检查改进成有没有分配多于1个的资源。
--------------------------------------------------------------------------------
Allocator Utilities
分配器工具

delete(H, [H|T]) ->
T;
delete(X, [H|T]) ->
[H|delete(X, T)].
lookup(Pid, [{Resource,Pid}|_]) ->
Resource;
lookup(Pid, [_|Allocated]) ->
lookup(Pid, Allocated).
13:11:22 | 添加评论 | 发送消息 | 固定链接 | 查看引用通告 (0) | 写入日志 | 分布式并行计算
2006/9/12
并行计算——寻找并发性(第二步)
数据分解模式
问题:
如何将一个问题的数据分解为多个能够相对独立的操作的单元?
背景:
并行算法设计者必须详细的了解所要求解的问题。另外,设计者应当识别出问题的哪些部分是计算最密集的部分,求解问题所需要的关键数据结构,以及随着问题求解的展开,如何使用数据。
了解了基本的问题之后,并行算法设计者应该考虑组成问题的任务,以及任务中隐含的数据分解。为了创建一种并行算法,必须进行任务分解和数据分解。问题不是进行哪一种分解,而是先从哪一种分解开始。如果下面的情况为真,最好首先进行基于数据的分解:
1、问题中计算最密集的部分是围绕着一个大型数据结构的管理而组织的。
2、相识的操作被应用于数据结构的不同部分,这样可以相对独立的操作不同的部分。
HINTS:线性代数~~
面临的问题:
在这里,面临的主要问题有灵活性、效率和简单性:
1、灵活性:设计中的灵活性将使得它能够适应不同的实现需求。例如,在设计的时候,限定选择一个单计算机系统或者编程模型,通常就是一个很糟糕的想法。
2、效率:一个并行程序仅当它能够随着并行计算机的尺度高效的进行伸缩时(减少运行时间或者存储器消耗),才是有用的。对于一个任务分解,这意味着我们需要足够的任务以保持所有的执行单元(处理单元)的繁忙程度,每一个任务具有足够的工作以补偿管理相关性所带来的开销。但是,效率的驱动可能导致缺乏灵活性的复杂分解。
3、简单性:任务的分解需要足够的复杂以完成工作,但是也需要足够的简单,以简化程序调试和维护。
解决方案:
在共享存储器的编程环境中,例如OpenMP,数据的分解常常是由任务分解所隐含的。但是,在大多数情形中,数据分解需要手工完成,因为存储器是物理分布的,又因为数据相关性太复杂,不具有明确的数据分解,或在NUMA计算机上获得可以接受的效率。
如果一个基于任务的分解已经完成,则数据分解由每个任务的需要所驱动。如果每个任务能够与定义完善的不同数据相关联,数据分解将现对比较容易。
但是,当从数据分解开始进行并行计算的算法设计时,我们不需要查看任务,但需要查看定义问题的重型数据结构,考虑它们是否能被分解为多个可以并行操作的数据块。包括一下几种常见的示例:
1、基于数组的计算:可以根据数组不同的更新来定义并行性,如果数组是多维数组,则可以采用多种方式划定它(行、列或者其他的形状)。
2、递归数据结构:例如,我们可以考虑通过将一个大型树状数据结构分解为若干个可以并行更新的子树,来分解该结构的并行更新。
不考虑底层数据结构的本质定义,如果数据分解是驱动问题的主要原因,则它将作为并行算法的组织原则。
当考虑如何分解问题的数据结构时,要时刻记住竞争问题。
灵活性:数据块的大小和数目应当灵活,以支持不同类型的并行系统。一种方法就是采用少量的参数来控制所定义的数据块的大小和数目,这些参数定义了一些粒度块(granularity knob),可以改变它们以修改数据块的大小,从而匹配底层硬件的需求(但是注意,许多设计并不是无限制的适应粒度)。
查看粒度对数据分解的影响的最容易的地方是,管理数据块间相关性的所需要的开销,管理相关性所需要的时间必须远远小于总体运行时间。在一个优秀的数据分解中,相比于与每个数据块相关联的计算量,相关性的伸缩尺度很低。例如,在许多有限差别的程序中,数据块边界间的单元,也就是数据块的表面,必须是共享的,相关单元的大小随着表面积的大小而变化,而计算所需的工作量随着数据块的容量而伸缩,这意味着计算量是可以伸缩的(基于数据块的容量),以弥补与数据相关性联系的开销(基于数据块表面面积的)。
效率:数据块必须足够大,以使更新数据块的工作量能够弥补管理相关性所需要的开销。一个更加棘手的问题就是如何将数据块映射到处理单元上。一个高效的并行算法能够平衡处理单元之间的负载,如果处理不当,某些处理单元的工作量可能不成比例,整体的性能受到影响,这将需要灵活的方式来处理问题。例如,如果问题从左向右处理矩阵中的列,则矩阵的列映射将使得具有靠左边列的处理单元先于其他处理单元完成工作。基于行的数据块分解或者是一个数据块周期(block-cyclic)的分解(在该分解中,行被周期性的分配给处理单元)都能够很好的保持所有的处理器繁忙。后面会有更加详细的讨论。
简单性:过度复杂的数据分解将导致调试非常困难。一个数据分解常常需要一个全局索引空间映射到一个任务局部索引空间,进行这样的映射抽象将使得它很容易被测试。
数据分解后,下一步就是查看数据所包含的任务分解。
10:07:05 | 添加评论 | 发送消息 | 固定链接 | 查看引用通告 (0) | 写入日志 | 分布式并行计算
2006/9/11
并行计算——寻找并发性
我们使用下面的框图来说明怎样寻找我们希望的并发性:

我们使用模式进行分解:
1、分解模式:存在两种分解模式,任务分解和数据分解。使用分解模式将问题分解为多个能够并行的小片段。
2、相关性分析模式:这一组包括3种模式,用于分组任务和分析任务间的相关性:分组任务、排序任务和数据共享。通常,模式是以这种顺序被应用。但是,实际上常常需要重新应用某一个模式,或者甚至可能需要重新使用分解模式。
3、设计评估模式:这个设计中的最后一个模式用于指导算法设计者分析已经完成的工作,然后再转向“算法结构”空间中的模式。这种模式非常重要,因为最好的设计常常不是第一次就能发现的,越早的识别出设计缺陷,就能越容易地更正它们。通常,使用设计中的模式是一个反复的过程。
使用分解模式
我们的分解考虑发生在两个维度之内:
1、任务分解维度:将问题看作是一个指令流,指令流中的指令可以被分解为多个成为任务的序列,所有的任务能够同时执行。为了使计算能够高效地执行,组成一个任务的操作应该尽量独立于其他任务的操作。
2、数据分解维度:集中于分析任务所需要的数据,分析如何将数据分解为多个不同的块。仅当数据块能够被相对独立的操作的时候,与数据块相关的操作才能够高效的执行。
虽然它们两个维度之间有些许“交融”的地方,但是作为一个模式的思考方式,我们从一个独立的角度看问题会容易一些。
任务分解模式
问题:如何将一个问题分解为多个能够并行执行的任务?
背景:
每一个并行算法的出发点都说一样的,即很好的理解所要求解的问题。程序言必须了解问题的哪些部分是计算密集的部分、关键数据结构,以及随着问题的展开,如何使用数据。
下一步是定义组成问题的任务和任务中所隐含的数据分解。通常每一个并行算法包含一个能够并行执行的任务集合。主要的挑战是寻找这些任务,并将其构造成为一个算法。使这些任务能够并行的运行。
在一些情况下,问题将能够很自然的分解为一个独立的(或接近于独立的)任务的集合,并且很容易的开始一个基于任务的分解。在其他情况中,任务的分离可能是非常困难的,因此较好的切入点是数据的分解。至于哪一种方法最好,没有一个统一的标准,通常需要开发者自己思考的时候同时思考两个方式。
面临的问题:
主要问题在于:灵活性、效率和简单性
1、灵活性:设计中的灵活性将使得它能够适应不同的实现需求。例如,在设计的时候,限定选择一个单计算机系统或者编程模型,通常就是一个很糟糕的想法。
2、效率:一个并行程序仅当它能够随着并行计算机的尺度高效的进行伸缩时(减少运行时间或者存储器消耗),才是有用的。对于一个任务分解,这意味着我们需要足够的任务以保持所有的执行单元(处理单元)的繁忙程度,每一个任务具有足够的工作以补偿管理相关性所带来的开销。但是,效率的驱动可能导致缺乏灵活性的复杂分解。
3、简单性:任务的分解需要足够的复杂以完成工作,但是也需要足够的简单,以简化程序调试和维护。
解决方案
一个高效的任务分解的关键在于确保任务充分的独立,以使得管理相关性仅占用程序所有执行时间的一小部分。确保任务的执行能够均匀的分配在所有处理单元上,也是非常重要的(负载平衡问题)。
在一个理想的世界中,编译器会为我们做这一切,帮助我们寻找任务。遗憾的是,这些从来都不会发生。取而代之的是,人们通常必须根据问题和所需要的代码的知识手工完成。在某些情况下,可能需要将问题构造为另一种形式,以揭示相对独立的任务。
对于基于任务的分解,我们将问题看作截然不同的任务的一个集合,并特别注意:
1、解决问题所采取的行动中(具有足够的行动以保持目标机器上的处理元素繁忙吗?)
2、这些行动是截然不同的而且相对独立的吗?
我们应该尽可能的分解任务,这里“过犹不及”就不是那么的正确了,合并问题的消耗要小于分解问题。
我们可以从很多地方找到任务:
1、在某些情况下,每一个任务对应于一个函数的不同调用。为每一个函数调用定义一个任务有时候称为功能分解。
2、另一个寻找任务的地方位于一个算法内循环的不同迭代中。如果一个循环的每一层迭代是独立的,并且具有足够的迭代,则基于任务的分解能够很好的起作用,将每一层的迭代映射到一个任务。这种类型的基于任务的分解有时候称为循环分离(loop-splitting)。
3、任务在数据驱动的分解中也起着重要的作用。在这种情况下,大数据结构被分解,每一个处理单元并发的更新了数据结构的不同块。在这种情况下,任务是在每一个数据块上的更新工作。
另外也需要注意“面临的问题”部分中出现的问题:
1、灵活性:设计在产生任务数目方面需要具备灵活性。通常这通过适当的尺度参数化任务的数目和大小来完成。这将使得设计能够适应多种具有不同处理器数量的并行计算机。
2、效率:在任务分解中,需要考虑两种主要的效率问题。第一,每个任务必须包含足够的工作,以补偿创建任务和处理它们的相关性所带来的开销;第二,任务的数目应该足够大,使得所有的处理单元在整个计算周期内保持繁忙,并做有意义的事情。
3、简单性:定义任务的方式应使得调试和维护简单。如果可能,所定义的任务应当可以重新使用解决相关的问题的现有串行程序的代码。
下一部分我们将介绍一下数据分解。
14:05:43 | 添加评论 | 发送消息 | 固定链接 | 查看引用通告 (0) | 写入日志 | 分布式并行计算
并行计算的度量
实现并行计算的主要目标有两个:1、更高的性能;2、解决更大的问题。
假定一个计算由3部分构成:准备(setup)、计算(computation)、结束(finalization)。一个处理单元(可以是一台计算机,也可以是一个CPU,主要由观察的层次所决定)上运行该程序的总运行时间可以给出:
T_total(1) = T_setup + T_computation + T_finalization
如果在一台具有多个处理单元的并行计算机上执行这个计算的情况我们也可以想象的出,我们假定程序开始和结束的部分没有办法进行并行化处理,但是计算部分可以进行有效的并行化,被分解为多个任务,这些任务并行的运行与多个处理单元上,而且计算步骤的数目与初始计算中的步骤相同。计算在P个处理单元上需要的总运行时间如下:
T_total(p) = T_setup + T_computation(1)/P + T_finalization
上面的公司描述了一个非常理想的状态。但是,计算包含串行比例(对该部分的任务来说,额外的处理单元是没有任何用处的)和并行部分(对该部分来说,更多的处理单元将有效的降低运行时间)的思想是具有实际意义的。我们可以通过上面的简单模型得到一些重要的关系。
处理单元起到的作用的一个重要的度量就是相对加速比S,它描述了一个问题在并行情况下运行比在串行情况下运行要快多少。
S(P) = T_total(1) / T_total(P)
另一个相关的度量是效率E,它是加速比与处理单元的数目的比值:
E(P) = S(P) / P = T_total(1) / (P * T_total(P))
理论上我们都趋向于让加速比等于P,这种情况不过是“理想”,被称为完全线性加速,遗憾的是,我们不可能达到,或者说目前没有办法达到,只能趋近。因为准备部分和完成部分的时间没办法通过添加更多的处理单元来降低,故限制了加速比的大小。无法并行运行的部分的期间称为串行时间。它们的运行时间占总运行时间的比例称为串行比例(serial fraction),符号为γ。
γ = (T_setup + T_finalization) / T_total(1)
于是花费在程序的可并行部分的时间比例为(1-γ).可以重写在P个处理单元情况下的总运行时间的表达式:
T_total(p) = γ * T_total(1) + (1-γ) * T_total(1) / P
现在,利用新的表达式T_total(P)重写S,得到著名的Amdahl法则:
S(P) = T_total(1) / ((γ + (1-γ) / P) * T_total(1)) = 1 / (γ + (1-γ) / P)
这样,在并行部分并行部分不具有额外开销的理想并行环境中,加速比的计算可以依据上面的公式。假定我们的并行算法非常有效,而且我们具有非常多的处理单元可以使用,加速比会有什么样的变化呢?当P趋近于无穷大的时候,取极限得到S的公式:
S = 1 / γ
该公式给出了串行比例为γ时,所能够达到的加速比的理论上限。
对于一个并行算法设计者来说,这些概念至关重要。在设计并行算法时,了解串行比例的值是非常重要的。这样能够实际的了解所能获得的性能。如果算法的串行比例占到10%或者更高,那么实现一个复杂的,任意伸缩的算法就是没有任何意义的。
注意:Amdahl法则是具有假设的,现实生活中,这些假设可能为真,也可能为假,要看具体的情况而定。
我们同时也可以注意到,某些情况下,现实情况更加复杂。例如我们创建一个3D动画电影,我们在不断的添加处理器的时候,我们也在修改渲染的参数,让场景变得更加精细,或者让分辨率提高,这将抵消处理器增长带来的时间的缩小。在这个时候,Amdahl法则或者固定大小情况下的加速比,并不能正确的反映额外处理器的优点。
因此,我们重写公式,给出具有P个处理器的系统的性能加速比。前面的公式T_total(P)是一个处理单元上执行的串行时间的执行时间和并行部分的处理时间推导而来的。这里,我们从另一个方面考虑问题,根据在P个处理器上执行时的串行时间和并行时间的执行时间来推导T_total(1)。
T_total(1) = T_setup + P * T_computation(P) + T_finalization
现在,定义了我们需要的可伸缩串行比例(scaled serial fraction),符号为γ_scaled,如下:
γ_scaled = (T_setup + T_finalization) / T_total(P)
于是有了:
T_total(1) = γ_scaled * T_total(P) + P * (1-γ_scaled) * T_total(P)
为这个加速比重写公式,并进行化简,得到可伸缩的加速比(固定时间的加速比):
S(P) = P + (1 - P) * γ_scaled
这个加速比实质上与Amdahl法则给出的结果相同,但是当增加处理器数量时,它允许考虑一个不同的问题。由于γ_scaled依赖于P,所以我们的极限结果并不能直接给出,但最终与Amdahl法则中的一样。假设取P的极限,保持T_computation不变,是γ_scaled成为常量,即增加问题的大小,当处理器数量增加时,总运行时间可以保持不变(隐含假设:问题大小增加时,串行时间的时间不变)。在这种情况下,加速比与P成线性关系。
这样,单处理器较少,添加新的处理器解决一个固定大小的问题时,应该使用Amdahl法则判定加速比极限,如果问题本身随着处理器数目的增加而增加则应该使用Gastafson法则。
通信问题
在基于消息传递的模型或者其他需要传递信息的系统中,下面的模型很简单,但是很实用。它将传递消息的总时间描述为一个固定开销加上一个可变开销(类似于网络系统中的传输延迟、传播延迟等概念),其中可变开销依赖于消息的长度:
T_message_transfer = α + N / β
固定开销α称为延迟,实际上是通过通信媒介发送一条空消息所使用的传递时间,及从发送例程调用到接受例程接收到所需要的时间,它包括了软件开销和硬件开销,加上在媒介中的传输时间(一般来说是以光束传播的)。带宽β是通讯媒介的容量的一种度量,N是消息的长度。
对于不同的系统,延迟和带宽是有很大差别的,这依赖于所使用的软件系统和硬件系统的质量。我们现在可以使用一些方便的工具来测量这些值的大小,并且根据具体情况进行优化,以提高系统的整体性能。例如,在一个系统中,它的延迟非常厉害,我们就需要减少短小的消息的发送次数,尽量合并为长消息进行发送,减少发送的次数。遇到带宽紧张的系统,可能采用压缩算法效果不错。
下面来介绍一下重叠通讯(异步通讯)和隐藏延迟,假设现在有两个系统A和B,A系统发出一个消息后需要等待B系统的回应,这时候系统A处于等待中,直到系统B返回消息的响应,我们可以将该过程异步化,A系统发送消息后处理其他的信息,当系统B返回响应后系统A切换回来继续刚才的任务,而不是“傻傻的”等待,于是虽然会存在切换之间的开销,但是已经大大减少了系统的空白等待时间,提高了运行的效率,我们也可以得出,该异步方式的使用,实际上期待了屏蔽系统延迟的作用。
在现在的许多并行系统中使用的另一种技术就是将多个执行单元(处理单元)分配给一个实际的处理单元(一台计算机或者一个CPU),当当前的执行单元阻塞的时候,实际的处理单元立刻切换到其他的执行单元进行执行,而不用等待阻塞的任务,这也是一个隐藏延迟的方法。目前已经有越来越多的系统采用这种方式来提高效率。例如:Cray公司的MTA系统。
11:04:49 | 添加评论 | 发送消息 | 固定链接 | 查看引用通告 (0) | 写入日志 | 分布式并行计算
简单说一说并行编程
并行计算的关键在于“可开发的并行性”。在一个计算性问题中,如果该问题能够被分解成多个子问题,并且这些子问题能够在同样的时间内同时安全的执行,则该问题就存在并发性。所构造的代码必须能够揭示并发性,并且允许子问题能够确实的并行的运行:也就是说,并发性必须是可开发的。
大多数大型计算性问题包含可开发的并发性。程序员处理可开发的并发性的方式是创建一个并行算法,并在一个并行编程环境中实现这个算法。当最终的并行程序运行在一个具有多个处理器的系统上时,获得的结果将缩短。另外,多处理器系统相对于单处理器系统来说,更能解决大型问题。
作为一个简单的示例,假设一个计算部分包含计算一个大型数据集的和。如果能够使用多处理器,则可以不将所有的值按顺序加在一起,而是划分数据集,并计算子集的和,每个子集的计算位于不同的处理器中,然后将所有的子集的和组合在一起,获得最终的答案。这样,使用多处理器并行的计算,将能够更快的得到结果。如果每个处理器都有自己的存储器,在处理器之间划分数据可以使得大型问题更可能解决。
这个简单的示例演示了并行计算的本质。目标是使用多个处理器在更短时间内解决问题,以及解决在比单处理器上可能解决的更大的问题。程序员的任务就是鉴别出问题的并发性,并构造算法以开发并发性,然后使用合适的编程环境来实现解决方案,最后是在并行系统上执行代码。
并行编程带来一些独特的挑战。通常,组成问题的并发任务包含一些依赖性,这些依赖性必须被识别出来并妥善管理。任务执行顺序的问题可能改变计算的答案。例如,在前面描述的并行求和的例子中,某一部分的总和知道它本身的计算完成后才能够与其他部分组合在一起。该算法对所有任务强制采用一种顺序(即所有任务必须完成,然后它们的总和才能够被组合在一起)。更进一步的分析,当求和的运算顺序不同时,总和的数值可能会有少许的不同,因为浮点计算是非结合性的。一个优秀的并行程序员必须非常谨慎,以确保这些不确定性不会影响最终答案。创建安全的并行程序是程序员所必需注意的。
即使一个并行程序是“正确”的,它也可能没法提供期望的性能改善。必须是非常谨慎,以确保管理并发性说带来的额外的开销不会超过程序的运行时间。另外一种平衡的方式在处理器间划分工作通常不会像求和程序中那样简单。一个并行算法的效率依赖于它映射到的底层并行计算机的程度,因此一个并行算法在某一个并行计算体系结构上可能表现的非常高效,但是在另一个体系结构上却异常糟糕。
程序员的工作很清楚——
1、寻找并行性
2、算法结构
3、支持结构
4、实现机制
如图:

寻找并发性设计空间构造问题,揭示可开发的并发性,这个层次的设计者将注意力集中在高级算法问题上,并推导出问题潜在的并发性。算法结构设计空间构造算法,获得潜在并发性的好处,这个层次的设计者考虑如何使用寻找并发性模式期间揭示的并发性。算法结构空间模式描述了开发并发性的整体策略。支持结构设计空间在算法结构设计空间和实现机制设计空间之间提供了一个中间层次,这个设计空间存在两个重要的模式组,一个是表示程序构造方法的模式组,一个是表示通用共享数据结构的模式组。实现机制设计空间将较高级别空间的模式映射到特定的环境。它描述进程\线程管理(例如进程的创建和销毁)和进程\线程交互(信号量、栅栏、消息传递等)的通用机制。这个设计空间的条目并不被表示为模式,在许多情形中,它们直接被映射到特定并行编程环境中的元素。它们都被包含在模式语言中,提供了从问题描述到编码的一个完整的路径。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics