计算机科学的前景

计算机科学远景-从系统

角度出发

格勒诺布尔，法国

11月3日，2011

JosephSifakis

VERIMAG实验室

计算机科学的演化

■计算与电信交汇

■图形界面，鼠标

科学计算多核系统

-国防应用

WEB-

信息社会

1945198019902010

1936197020002015

嵌入式系统:

H建立-Alan

计算+实体

Turing,Kurt

|Godel■无缝革命

-95%的芯片被嵌入

■信息系统:商业应用物联网:

■集成电路嵌入式和网络交汇

Evolutiondrivenbyexponentialprogressintechnologyandexplosionofapplications

SystemsEverywhere-Moore'sLaw

1MB存储器的价格

76000€

6000€

450€

1973

1977120€

30€

4.5€

0.46€

19900.06€、

摩尔定律:单位集成电路上可容

1995的0.004€

纳的晶体管数目每隔2年会增加一

倍2000三!

、2005

系统无处不在

系统集成软件和硬件，共同和特定的设计提供功能性通常是关键.

系统无处不在

40chips

elsewhere

80chips家用电器、

ATM,cellphone,PDA,

TV,DVDplayer,phone,games,

washer,dryer,dishwasher,etc.

40chips

工作

每个人每天使用250个芯片

printers,scanners,PC,

phonesystems,etc.

70chips

每人每年使用十亿晶汽车

体管(2008)

dooropener,ABS,airbag,GPS,

radio,enginecontrol,etc.

系统无处不在-影响

系统技术

□巨大的经济和社会影响

□让我们能应对人口增长，健康，服务，创新的全球挑战

系统是

□物联的

国家的大部分事情都可以被度量，感知和监控

□互联的

人和物体能够使用全新的方法相互交流和接触

□智能的

增强事件的可预测性和资源使用的优化

6

□从程序到系统

口系统设计

口三大挑战

■实体与计算结合

■组件设计

■自适应性

概要

□计算机科学的远景

7

手动计算

两个最主要的突破

计算理论-基本事实

可计算性:

口计算模型的研究-所有的计算模型是等价的（图灵论题）

口存在某些函数不能计算比如一个程序终止，一个程序的变量X由某些值约

束

复杂性：每个问题的算法解决方案是以它的复杂性为特点的,这个复杂性就是

所需要解决这个问题的时间和空间需求.

口相同的问题能够使用复杂度不同的算法解决

□问题的复杂度低于某个确定的边界（正如热燃机的效率低于100%）

从程序到系统

□I/O值□I/O流值

□终止性□非终止

□确定性口非确定

□平台■独立行为□平台-非独立行为

□计算理论□没有统一的理论框架

系统的重要事实

软件+硬件

系统的重要事实

系统=软件+硬件

□没有理论能够预测软件在一个给定的硬件平台上的行

为（即使我们分别对软件和硬件非常的了解）

□计算理论忽视了物理时间和资源，只捕捉软件的功能

性质

□系统设计不应该只考虑系统软件和硬件的交互，更应

该并且最重要的应该考虑系统和它的受控环境

系统设计-简介

系统设计是让程序软件和硬件系统结合以满足给出要求的过程

考虑用户和环境的系统的期望

行为

不同于纯软件:需求

或者硬件设计

可执行满足要求的独立模型

规划

软件系统由硬件和软件组成-硬件

硬件平台可能已经给出

□从程序到系统

□系统设计^^^

口三大挑战

■实体与计算结合

■组件设计

■自适应性

概要

□计算机科学的远景

15

系统设计-新趋势

新趋势打破了传统计算系统工程.

同时满足下面的技术要求是困难的：

■反应性:对已知的反应，并保证无延迟

例如：飞行控制器

■自主性:可以在无人介入的情况下提供连续服务

例如：没有手工启动，最佳能源管理

■可靠性：任何情况下保证服务

例如:攻击，硬件失败，软件执行错误

-可扩展性：运行时或进化时扩展（由于资源线性性能增长）

例如：重新配置，可扩展服务

…有时候在最优代价/质量考虑中也把经济因素加入

技术挑战:

在一个可接受代价的前期下建立能保证功能和质量的系统的能力

16

统设计-目前发展水平

-低复杂性安全保密关键系统

□飞行控制器,智能卡

-复杂系统

远程通信系统,以web为基础的应用

我们需要：

-负担得起的关键系统

M

OEx:运输,健康，能源管理

tr-异构系统的成功整合系统

cOc

I

A□物联网

I

O

l□智能交通系统

□智能电网

□智能环境感知

t系统设计-仍有很长的路要走

McMCCDtion06hiKocciralatOOZ8：C11B3M)CInWDD18fcVB0(03)•

oooowbo.nilsMBScalledfroa0CK*tt:ClllM<X2lLn施vul!ratJi((M)♦

00000000.nnaybeoosslbletocontinuencvwim.

•Press4mM*61ioatlcwittocontlnu(?.

•Press(:血XLIdtLSMtorevtyuut*uMtiuter.Ybu«tlll

losenn9MiMwdinfnrwiiionInmiwplioitions.

Pressany皿toccmttrue

计算系统工程缺乏类似构造结

果

传统的系统工程学科是建立在■对特定的设计问题只有部分答案

坚实的理论构建和它们生命周■在设计时间上可预见性很难保证

期中可以预见的行为.

■后验确认对保证正确性是必要的

系统设计-仍有很长的路要走

设计一个大的IT系统是一件有风险的事件，需要动用数百的工程师话费数年时间.

困难

□复杂性-主要是可以使用已有的组件构建系统

□要求经常是不完备并且模糊不清的

（指定的自然语言）

□设计方法是经验主义并且需要专业

结论

□大的IT系统经常超预算超时交付的时彳

□40%失败,30%部分成功，30%成功.

系统设计-仍有很长的路要走

他们工作的基础设计原则.

大部分抽象数学和理论工作是枯燥的因为他们与实际计算没很好的切合点.

ChristopherStrachey(1916-1975)

□从程序到系统

口系统设计

口三大挑战

■实体与计算结合

■组件设计

■自适应性

概要

□计算机科学的远景

21

三大挑战

系统是

物联化:我们需要包括连续和离散动力学去预测系统的全局行为的模型

n实体和计算结合

互联化:我们需要理论模型工具使用装配组件去构建复杂系统

n组件设计

智能化:我们需要能够适用变化环境而自调整行为的系统

n自适用性

□从程序到系统

口系统设计

口三大挑战

■实体与计算结合

■组件设计

■自适应性

概要

□计算机科学的远景

23

实体与计算结合

硬件平台:

■速度B

・存储

■功率

■失败率;1

电

琵

・温度1三

7莪

一

i卷..

:»0

W.

::1=呈

件

软

用#t

「

">®件1.

B，

^系

纾

克

乡

尸

fi0.

.孝.

，

於

24

实体与计算结合

/.1

二

二

a:■三i

ftp

lsow<areeo:n1sV.V

"app2l

lieetwlaI

malsdlre

-o

25

实体与计算结合

HWPlatform:

■CPUspeed

■memory

"powdr

■failurerates;/.三

0二

7

、

■temperature善

y1

-_IMtaaaaMaaaaiia

B一

1=-­

件

软

.£

"B>件1

系

纾

.

，

26

软件设计前后一致整合这些

HWPlatform:

■CPUspeed

■memory

■powSr

■failurerates/.

47

■teipperature"、

窘1.

抵wa:

■一5a6arueeo:nsV

lic

/mPP2Iewa

登oscllre

我们需要重新计算并修正来自电子工程和控制的整合方法

实体与计算的结合-实例

物理系统工程计算系统工程

分析模型计算模型

组件:传递函数组件:子程序

结构：并行结构：串行

连接:数据流连接:控制流

Pb:分析和计算模型一致的组合

28

RelativeSlip

Matlab/Simulink。叩V""1090-2000讣*Mathwoiks,inc.

29

□从程序到系统

口系统设计

口三大挑战

■实体与计算结合

■组件设计

・自适应性

概要

□计算机科学的远景

31

组件设计

□使用构件组装众多优点比如生产力和正确性建立复杂系统

□构件组装精心策划部件交互.它是并行计算的核心.

组件设计-异构性

异构性：系统设计者处理大量有不同的特性的组件,来自不同的观点，每个

来自系统不同的维度

TSpacesConcurrentFortranJavaC

SoftbenchNesC

SWbusBPEL,

CorbaSES/Workbench

MPISysML

JavabeansAADL

.NETStatecharts

FractalMatlab/Simulink,

VerilogVHDLSystemCTLM

影响:

□使用形式化语义无关，例如程序，硬件描述和模拟，破坏设计流的一致性并

且危害它的联接

□系统开发与验证和评价是解耦的.

组件设计-执行的异步性

同步组件（硬件，多媒体应用软件）

□执行是一连串的非可执行的步骤

异步组件（通用应用软件）

□没有预先定义的执行步骤

未解决的问题：包含同步和异步单元的理论,比如GALS

组件设计-相互作用的异构性

两个基本协议

集合：原子对称同步广播:由发生者引发的不对称同步

□任何交互机构都可以表示为分层次的集合和广播的组合

□存在的形式化和理论是不够丰富表达的

-各种各样低水平协调装置包括信号监控器信息传递函数调用

-通常点对点交互使用集合或者广播

组件设计-粘合的概念

构建一个满足P的组件C：

■Co由它们自己行为描述的原子组件集合

"GL=叫…,g!„...）组件粘合操作集合

satP

□粘合操作是协调机制比如协议、调度、总线

□我们需要一个统一的范例去描述分析各组件之间的协调

组件设计-粘合的要求

组合性:由正确的组件建立正确

的系统的规则

satPjimpliesgl

Qisatgl(Pl5..,Pn)

gi

我们需要组合结果去保留进度属性比如死锁-自由和活性以及额外的功能属性

组件设计-粘合的要求

可组合性:当组件整合的时候保

留基本属性

andsatP'

gl㊉gi'satP&P'

impliesooo

性能稳定现象尚不清楚.我们需要可组合结果,例如,非相互作用的特点在中

间件,调度算法的可组合性,web服务的方面

□从程序到系统

口系统设计

口三大挑战

■实体与计算结合

■组件设计

■自适应性

概要

□计算机科学的远景

39

适应性-智能系统

智能系统的两个

自适应性

□系统的行为适合满足以给定的需要包括安全性能，其外部环境和可执行

环境的不确定存在

□由控制技术正确执行

适应性-处理不确定性

系统必须提供一个满足给定需求在非确定性环境下的交互

非确定性可以被看作是平均和极端系统行为之间的不同

资源的不确定性:

口物理环境

■不确定性行为e.g.不同吞吐量

■攻击，恶毒行为

口执行平台

■由制造业的误差或者老化引起的可变性

•由于分层缓存投机执行引起的不同的执行时间

■时序异常（物理增加平台速度而降低性能）

适应性-可预测性

不确定行直接通过模型和分析影响行为的可预测性

可预测是一个系统的行为通过定性或者定量应该被正确预测的一个度.

缺乏可预测性

□由于非确定性，系统模型代表实际系统行为的安全抽象

□进一步，给定一个模型，由于所有关键系统性能的不可计算行，精

确分析技术是不可能的

后果

□缺乏可预测性表示额外的不确定性

□对于复杂系统，在设计时预测所有可能的关键状态时不可能的

A

A

三

q

e

q

o

QI

ForsimpleoperationsWCETmaybe300xBCE

自适用性-苛求和尽力服务工程

两个相异的设计范式

苛求系统工程是以最坏分析和静态资最佳效果工程是以平均情况分析和

源保留为基础的，比如，硬实时方法动态资源管理为基础的。比如，

和大量冗余。优化速度的服务质量,存储带宽，

电源可用性保证

导致维度过大的系统

适应性-加强可预测性

联合架构导致增加开发成本e.g.汽车工业

2.系统的自适应控制技术整合苛求和最佳效果特点，比如IMA

■一个可预测的足够大的全局资源满足临界属性

■最佳效果的应用需要有效的最优化使用现有的资源

・自适性-自适应控制

学习：预估执行时间

基目标管理：找出一个质量最大化的日程安排并且满足

相截止日期

计划：对给定质量计算最好的日程安排

(schedule,q)time

46

适用性-自适应控制

学习

去：1）体育场2）电影院3）餐馆

47

适应性-自适应控制

5oocontrolledquality,buffersizeK=1

constantqualityq=4,buffersizeK=2

O

O

A4oo

U

W

)

e7\32o

E30o

-

l

6

2oo

.EP

0

0

U

01oo

0

0100200300400500600

frames

48

□从程序到系统

□系统设计

□三大挑战

■实体与计算结合

O■组件设计

V

E

R■自适应性

V

I□计算机科学的远景

E

W

计算机科学的远景

计算机科学

□由于技术和应用的指数级发展而产生，是一个年轻却发展迅速的学科

口着重于系统构建，因此系统设计是该学科的核心

口现存的计算模型应该扩展，用以兼容物理特性-物质资源，例如内存、

时间、功耗，应该是首要考虑要素

口补充并增强理论知识，以及需要深层次理解动态离散系统的模型

□提出建设性的并有效可行的世界观，这一世界观可补充经典的陈述性

的被物理学采用的方法

工计算机科学远景-TheFrontiersofCS

0K»VP9»O*C

6J5%tt<HHBMIwl*«

=丰

»e«uWtS•Mlf

it4・e・，e*IM?"beqgto

eaztvrIM*

-onCommandWl0Bu^-X

-O