① 项目来源背景或目的
多核技术是近期非常热门的话题，这在一定程度上是由于各大CPU厂商的卖力宣传，更多的也体现出一种趋势：尽管我们使用的集成电路技术还在不断的发展，但是芯片的集成度不可能无限提高，人们认识到光依靠提高主频的方式来提高处理器性能的做法已经越来越低效率了，我们需要优化CPU的内部结构，使用新的架构。
1996年Stanford的一篇论文提出SCMP（Single-Chip Multi-Processor）模型，并论证这样的结构比传统的效率更高。实际上经典的VLSI复杂度模型也有类似的理论：用超大规模集成电路芯片计算问题的算法复杂性的下界应当用芯片面接（A）和计算时间（T）的平方的乘积（AT^2）来表示更为合理。如果对于某个问题我们已经得出这个下界，并且有一个面积为(n^2)*A的硅片用于制造计算这个问题的芯片，我们可以有至少2种方案：1，制造n^2个面积为A的部件，计算时间为T；另一种我们考虑把计算时间缩短为T/n，根据对下界的估算，我们实现这个算法的芯片面积就至少为A的n^2倍，也就是说，我们只能做一个这样的新片了。如何选择方案其实很简单：当这个计算问题是大量的并且是可以同时做的，前者的总效率将为后者的n倍。
实际上这也正是软件界如此关注多核的原因。这一次的CPU进化方式和以前都不同：曾经当你完成一款软件，性能上的瑕疵可能并不那么重要，因为明天CPU就会更快而你的软件也会自然而然地运行得更好；然而，如果你的软件没有任何并发的成分，它在单核和100核的CPU上的运行速度将会是相同的。有人将此总结为一句话：免费午餐的时代结束了。
在另一方面，相对于多核趋势对于并行计算的需求，尽管多线程的编程已经出现很长时间了，尽管目前存在很多的多线程软件和工具，但总体上看，大部分的应用软件还依然是单线程的，大部分的程序员对多线程的了解也比较少。
还需要指出的是，多线程程序设计的思想方法与常规的思维和编程训练相去甚远，被最广泛使用的命令式程序设计语言在线程间的变量共享等方面存在较大的缺陷，这些都是软件界进入并发时代的障碍。可以考虑的解决思路大致上有三类：一种不改变现有的语言基础，依靠辅助工具处理框架中的多线程部分；第二种也不改变现有的语言基础，甚至也不用改变现有的单线程编程习惯，靠并行化编译器将单线程程序转化为并发的；第三种为设计适应多线程程序开发的语言。
本项目实际上是一种第三类的解决方案，系统的主要构成为Pandaria语言的设计，编译器和虚拟机。Pandaria设计为函数式语言，可以避免线程间的变量共享带来的一系列问题。她的语法类似于lisp，支持lambda演算。目前的构想是没有显式地支持多线程，而是通过对表达式的非确定性的支持，在编译期转化为并发程序。这样设计是希望避免过多的对线程和线程间通信关注，而让程序员把主要的精力放在软件设计上，同时在不对原有的编程思路进行太大改变的基础上让多线程的引入真正意义上的带来语言表达力的提高。编译器为项目的核心内容。虚拟机由于技术上的难度，目前的计划是暂时采用爱立信公司的开源平台Erlang（http://www.erlang.org）的虚拟机（非常优秀的并发平台）。
② 当前同类软件横向比较
目前并没有和这个项目完全类似的软件。所以我在这里进行的比较都是和其他多线程软件开发工具或者平台之间进行的。
首先的代码分析工具Intel VTune Performance Analyzer，它通过采集、分析并显示上至系统范围、下至源代码范围的性能数据，帮助查找并消除软件性能瓶颈。无论用 Fortran、C#、C/C++、Delphi还是用Java编程，Intel® VTune Performance Analyzer均能帮助优化您的软件。分析器支持包括Microsoft Visual Studio.NET、Intel® C/C++ 与Fortran 编译器、Compaq Visual Fortran、Java、Borland 编译器（Delphi、C++ Builder）以及IBM Visual Age。Linux 支持通过远程代理提供。
主要功能包括：采样功能、调用图功能、计数器监视器以及经过改进的Intel® 调优助手。Intel® VTune Performance Analyzer在Windows平台上同时提供图形化与命令行界面；允许选择是否与Visual Studio .NET 集成；为基于IA-32与Intel® 安腾® 处理器的Linux应用程序提供远程支持；还可以对基于Intel® PXA250、PXA255 与 PXA26x 处理器的应用程序进行采样。
产品特点
* 采样功能使开发人员用几乎可以忽略不计的开销换来对软件实际性能的最准确表示;
* 调用图评测功能用图形显示程序流程，帮助开发人员快速确定重要的函数与调用序列;
* 计数器监视器可供开发人员跟踪运行时系统活动，帮助确定系统级性能问题;
* 远程代理，针对Linux的远程代理具备采集远程 Linux 系统性能数据的功能，同时保持Windows图形用户界面的易用性，方便分析与诠释数据;
* Intel® 调优助手根据丰富的知识库自动建议代码改进办法，提高开发人员工作效率;
* Visual Studio .NET 集成，提供在Visual Studio .NET IDE中使用Intel® VTune Performance Analyzer的能力，帮助改善易用性、提高工作效率;
* Windows命令行功能在VTune分析器图形用户界面之外提供一种强大、灵活的数据采集手段，支持自动采样;
Vtune的功能确实非常强大，但是当我们在项目中大量使用代码分析工具进行辅助开发的话，不必要的细节过多将会导致我们对软件设计本身的关注降低，同时使项目开发的系统复杂性大幅度提升。
编译器方面，Stanford的SUIF研究组（http://suif.stanford.edu）的SUIF编译器在优化和并行化方面作了很多有益的探索，我对此关注并不多。编译器层面上实现的并发化是最理想的，可以完全隔离底层硬件的影响，只是可能在生成的程序的效率和缺陷控制上存在一些问题。
③ 项目可行性分析
首先此项目显然并非一个商业项目，可行性方面不需要考虑任何经济因素。剩下来需要关注的问题第一是项目能否完成，第二是完成后的应用价值。
首先，Pandaria的语法设计并不复杂，所谓非确定性表现为表达式的多值性，这正是并行计算的一种非常自然的表达方式。同时作为函数式的语言，在并行化的时候不存在任何变量共享，锁，序列化的问题，系统核心编译器的结构不会过于复杂。
其次关于应用前景的问题，在项目来源或目的已有阐述，这里不再赘述。
④ 初步拟定的设计规划和实现方法
选用开发语言为C++，选择的出发点是我对语言的熟悉程度。
Pandaria的语言设计
数据类型：整型数，amb（非确定数据l类型）
运算符：整型数所支持的算数运算和部分逻辑运算
数据结构：只有一种，序对。序对由2个任意数据元素（包括lambda表达式）构成，序对本身也是数据元素。创建方式为(cons operand_left operand_right)，若c为一序对，则(car c)的值为operand_left，(cdr c)的值为operand_right。
表：一个表可以表示为(cons list_element1 (cons list_element2 (cons list_element3 (…（cons list_elementN nil）…))))，nil定义为空表。或者简单的表达为(list element1 element2 …elementN)。一个表的car为一个element，cdr为一个表。
名字：(define name val)将名字name绑定于val，val为数据元素。
Lambda表达式：(lambda (operand1 operand2 … operandN) exp )为lambda表达式，其中exp为表达式。
表达式：数据元素（整数，序对，表，lambda，amb）是表达式，运算符表达式是表达式，表达式序列是表达式，if表达式是表达式。表达式都可以求值，求值结果为一数据元素。
运算符表达式：(op operand1 … operandN)为运算符表达式，当op为运算符或lambda表达式，并且operand1…N都是表达式。
表达式序列：(begin (exp1 exp2 … expN) )为表达式序列，当exp1…N都是表达式。其值为最后一个表达式的值。
If表达式：( if(exp) branch_true branch_false )为if表达式，exp，branch_true和branch_false都是表达式。若exp的值为0，则if表达式的值为branch_false的值，否则为branch_true。banch_false可以为空，那样的话如果exp为0，则整个表达式的值没有定义。
Amb：(amb val1 val2 … valN)定义为amb，其含义为可能返回val1…N中的任意一个，对amb求值将导致对val1，val2…valN的并发求值。（当线程过多时系统提供回溯方式求值的缓冲机制）。对空amb求值将导致求值失败，不会返回任何值。
Amb约束：(require exp)定义为(if(not exp) (amb))。
编译器的结构与一般编译器类似，大致上lexical analyzer—(tokens)àparser---(syntax tree)àtarget code generatoràdone。其中lexical analyzer和parser已经基本完成。目标代码方面由于目前对Erlang虚拟机的指令集了解非常有限，暂时直接选用erlang语言本身作为目标语言。
系统的重要特性：
处理amb时的并发性：回溯是单处理器机器上实现的对并发的模拟。而将自动搜索结合到程序设计语言中有着悠久的历史，代表机制有按历史回溯，依赖导向回溯和后者的改进真值保持。这些都可以通过并发更好的实现。
require语句的处理：处理为定义的形式实现简单，也可以考虑作特别处理，检查程序中的每一个amb对require的依赖性，即时检查require条件的成立与否，减少并发分支。
线程过多时候的回溯缓冲。
Erlang程序示例（8皇后问题用并发替代回溯）：
%queens.erl
-module(queens).
-export( [start/0,val_list_gen/2] ).
start()->
val_list_gen( [], [ [0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7],
[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7],[0,1,2,3,4,5,6,7] ]).
val_list_gen( Val_list, [ [First|Rest] | Rest_list ] )->
Tmp = test_queens:start_test(Val_list),
if
Tmp == true ->
%---注释部分的程序如果替代现有的语句的话就会变成按历史回溯
spawn( queens, val_list_gen, [ Val_list++[First], Rest_list ] ),
%val_list_gen( Val_list++[First], Rest_list ),
%---
val_list_gen( Val_list, [Rest|Rest_list] );
true->ok
end;
val_list_gen( Val_list, [ [] | Rest_list] )->ok;
val_list_gen( Val_list, [] )->
Tmp = test_queens:start_test(Val_list),
if
Tmp == true ->
io:format("~w~n",[Val_list]);
true->ok
end.
%test_queens.erl
-module(test_queens).
-export([start_test/1,test_loop/2,test_set/2,comb_gen/4]).
get_list_item(N,[])->unfilled;
get_list_item(0,[Head|Rest])->Head;
get_list_item(N,[Head|Rest])->get_list_item(N-1,Rest).
start_test(Val_list)->
Tester = spawn(test_queens,test_loop,[Val_list,self()]),
spawn(test_queens,comb_gen,[nil,[0,1,2,3,4,5,6,7],outer,Tester]),
receive
false->false;
true->true
end.
test_loop(Val_list,Pid)->
receive
{Q0,Q1}->
Tmp=test_set({Q0,Q1},Val_list),
if
Tmp==true->test_loop(Val_list,Pid);
true->
Pid!false
end;
done->Pid!true
end.
test_set({Q0,Q1},Val_list)->
Tmp0 = get_list_item(Q0,Val_list),
Tmp1 = get_list_item(Q1,Val_list),
if
(Tmp0 == unfilled )or( Tmp1 == unfilled )->true;
true->
(Tmp0 /= Tmp1) and
(Tmp0+Q0 /= Tmp1+Q1) and
(Tmp0-Q0 /= Tmp1-Q1)
end.
comb_gen(Pos,[Head|Rest],inner,Tester)->
Tester!{Pos,Head},
comb_gen(Pos,Rest,inner,Tester);
comb_gen(Pos,[],inner,Tester)->done;
comb_gen(nil,[Head|Rest],outer,Tester)->comb_gen(Head,Rest,outer,Tester);
comb_gen(Pos,[Head|Rest],outer,Tester)->
comb_gen(Pos,[Head|Rest],inner,Tester),
comb_gen(Head,Rest,outer,Tester);
comb_gen(Pos,[],outer,Tester)->Tester!done,done.
⑤ 团队人员构成
南京大学软件学院06级 毛海鉴 061251105
No comments:
Post a Comment