計(jì)算機(jī)科學(xué)的前景

計(jì)算機(jī)科學(xué)遠(yuǎn)景-從系統(tǒng)

角度出發(fā)

格勒諾布爾，法國

11月3日，2011

JosephSifakis

VERIMAG實(shí)驗(yàn)室

計(jì)算機(jī)科學(xué)的演化

■計(jì)算與電信交匯

■圖形界面，鼠標(biāo)

科學(xué)計(jì)算多核系統(tǒng)

-國防應(yīng)用

WEB-

信息社會(huì)

1945198019902010

1936197020002015

嵌入式系統(tǒng):

H建立-Alan

計(jì)算+實(shí)體

Turing,Kurt

|Godel■無縫革命

-95%的芯片被嵌入

■信息系統(tǒng):商業(yè)應(yīng)用物聯(lián)網(wǎng):

■集成電路嵌入式和網(wǎng)絡(luò)交匯

Evolutiondrivenbyexponentialprogressintechnologyandexplosionofapplications

SystemsEverywhere-Moore'sLaw

1MB存儲(chǔ)器的價(jià)格

76000€

6000€

450€

1973

1977120€

30€

4.5€

0.46€

19900.06€、

摩爾定律:單位集成電路上可容

1995的0.004€

納的晶體管數(shù)目每隔2年會(huì)增加一

倍2000三!

、2005

系統(tǒng)無處不在

系統(tǒng)集成軟件和硬件，共同和特定的設(shè)計(jì)提供功能性通常是關(guān)鍵.

系統(tǒng)無處不在

40chips

elsewhere

80chips家用電器、

ATM,cellphone,PDA,

TV,DVDplayer,phone,games,

washer,dryer,dishwasher,etc.

40chips

工作

每個(gè)人每天使用250個(gè)芯片

printers,scanners,PC,

phonesystems,etc.

70chips

每人每年使用十億晶汽車

體管(2008)

dooropener,ABS,airbag,GPS,

radio,enginecontrol,etc.

系統(tǒng)無處不在-影響

系統(tǒng)技術(shù)

□巨大的經(jīng)濟(jì)和社會(huì)影響

□讓我們能應(yīng)對(duì)人口增長，健康，服務(wù)，創(chuàng)新的全球挑戰(zhàn)

系統(tǒng)是

□物聯(lián)的

國家的大部分事情都可以被度量，感知和監(jiān)控

□互聯(lián)的

人和物體能夠使用全新的方法相互交流和接觸

□智能的

增強(qiáng)事件的可預(yù)測(cè)性和資源使用的優(yōu)化

6

□從程序到系統(tǒng)

口系統(tǒng)設(shè)計(jì)

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

■自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

7

手動(dòng)計(jì)算

兩個(gè)最主要的突破

計(jì)算理論-基本事實(shí)

可計(jì)算性:

口計(jì)算模型的研究-所有的計(jì)算模型是等價(jià)的（圖靈論題）

口存在某些函數(shù)不能計(jì)算比如一個(gè)程序終止，一個(gè)程序的變量X由某些值約

束

復(fù)雜性：每個(gè)問題的算法解決方案是以它的復(fù)雜性為特點(diǎn)的,這個(gè)復(fù)雜性就是

所需要解決這個(gè)問題的時(shí)間和空間需求.

口相同的問題能夠使用復(fù)雜度不同的算法解決

□問題的復(fù)雜度低于某個(gè)確定的邊界（正如熱燃機(jī)的效率低于100%）

從程序到系統(tǒng)

□I/O值□I/O流值

□終止性□非終止

□確定性口非確定

□平臺(tái)■獨(dú)立行為□平臺(tái)-非獨(dú)立行為

□計(jì)算理論□沒有統(tǒng)一的理論框架

系統(tǒng)的重要事實(shí)

軟件+硬件

系統(tǒng)的重要事實(shí)

系統(tǒng)=軟件+硬件

□沒有理論能夠預(yù)測(cè)軟件在一個(gè)給定的硬件平臺(tái)上的行

為（即使我們分別對(duì)軟件和硬件非常的了解）

□計(jì)算理論忽視了物理時(shí)間和資源，只捕捉軟件的功能

性質(zhì)

□系統(tǒng)設(shè)計(jì)不應(yīng)該只考慮系統(tǒng)軟件和硬件的交互，更應(yīng)

該并且最重要的應(yīng)該考慮系統(tǒng)和它的受控環(huán)境

系統(tǒng)設(shè)計(jì)-簡介

系統(tǒng)設(shè)計(jì)是讓程序軟件和硬件系統(tǒng)結(jié)合以滿足給出要求的過程

考慮用戶和環(huán)境的系統(tǒng)的期望

行為

不同于純軟件:需求

或者硬件設(shè)計(jì)

可執(zhí)行滿足要求的獨(dú)立模型

規(guī)劃

軟件系統(tǒng)由硬件和軟件組成-硬件

硬件平臺(tái)可能已經(jīng)給出

□從程序到系統(tǒng)

□系統(tǒng)設(shè)計(jì)^^^

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

■自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

15

系統(tǒng)設(shè)計(jì)-新趨勢(shì)

新趨勢(shì)打破了傳統(tǒng)計(jì)算系統(tǒng)工程.

同時(shí)滿足下面的技術(shù)要求是困難的：

■反應(yīng)性:對(duì)已知的反應(yīng)，并保證無延遲

例如：飛行控制器

■自主性:可以在無人介入的情況下提供連續(xù)服務(wù)

例如：沒有手工啟動(dòng)，最佳能源管理

■可靠性：任何情況下保證服務(wù)

例如:攻擊，硬件失敗，軟件執(zhí)行錯(cuò)誤

-可擴(kuò)展性：運(yùn)行時(shí)或進(jìn)化時(shí)擴(kuò)展（由于資源線性性能增長）

例如：重新配置，可擴(kuò)展服務(wù)

…有時(shí)候在最優(yōu)代價(jià)/質(zhì)量考慮中也把經(jīng)濟(jì)因素加入

技術(shù)挑戰(zhàn):

在一個(gè)可接受代價(jià)的前期下建立能保證功能和質(zhì)量的系統(tǒng)的能力

16

統(tǒng)設(shè)計(jì)-目前發(fā)展水平

-低復(fù)雜性安全保密關(guān)鍵系統(tǒng)

□飛行控制器,智能卡

-復(fù)雜系統(tǒng)

遠(yuǎn)程通信系統(tǒng),以web為基礎(chǔ)的應(yīng)用

我們需要：

-負(fù)擔(dān)得起的關(guān)鍵系統(tǒng)

M

OEx:運(yùn)輸,健康，能源管理

tr-異構(gòu)系統(tǒng)的成功整合系統(tǒng)

cOc

I

A□物聯(lián)網(wǎng)

I

O

l□智能交通系統(tǒng)

□智能電網(wǎng)

□智能環(huán)境感知

t系統(tǒng)設(shè)計(jì)-仍有很長的路要走

McMCCDtion06hiKocciralatOOZ8：C11B3M)CInWDD18fcVB0(03)?

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

00000000.nnaybeoosslbletocontinuencvwim.

?Press4mM*61ioatlcwittocontlnu(?.

?Press(:血XLIdtLSMtorevtyuut*uMtiuter.Ybu?tlll

losenn9MiMwdinfnrwiiionInmiwplioitions.

Pressany皿toccmttrue

計(jì)算系統(tǒng)工程缺乏類似構(gòu)造結(jié)

果

傳統(tǒng)的系統(tǒng)工程學(xué)科是建立在■對(duì)特定的設(shè)計(jì)問題只有部分答案

堅(jiān)實(shí)的理論構(gòu)建和它們生命周■在設(shè)計(jì)時(shí)間上可預(yù)見性很難保證

期中可以預(yù)見的行為.

■后驗(yàn)確認(rèn)對(duì)保證正確性是必要的

系統(tǒng)設(shè)計(jì)-仍有很長的路要走

設(shè)計(jì)一個(gè)大的IT系統(tǒng)是一件有風(fēng)險(xiǎn)的事件，需要?jiǎng)佑脭?shù)百的工程師話費(fèi)數(shù)年時(shí)間.

困難

□復(fù)雜性-主要是可以使用已有的組件構(gòu)建系統(tǒng)

□要求經(jīng)常是不完備并且模糊不清的

（指定的自然語言）

□設(shè)計(jì)方法是經(jīng)驗(yàn)主義并且需要專業(yè)

結(jié)論

□大的IT系統(tǒng)經(jīng)常超預(yù)算超時(shí)交付的時(shí)彳

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

系統(tǒng)設(shè)計(jì)-仍有很長的路要走

他們工作的基礎(chǔ)設(shè)計(jì)原則.

大部分抽象數(shù)學(xué)和理論工作是枯燥的因?yàn)樗麄兣c實(shí)際計(jì)算沒很好的切合點(diǎn).

ChristopherStrachey(1916-1975)

□從程序到系統(tǒng)

口系統(tǒng)設(shè)計(jì)

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

■自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

21

三大挑戰(zhàn)

系統(tǒng)是

物聯(lián)化:我們需要包括連續(xù)和離散動(dòng)力學(xué)去預(yù)測(cè)系統(tǒng)的全局行為的模型

n實(shí)體和計(jì)算結(jié)合

互聯(lián)化:我們需要理論模型工具使用裝配組件去構(gòu)建復(fù)雜系統(tǒng)

n組件設(shè)計(jì)

智能化:我們需要能夠適用變化環(huán)境而自調(diào)整行為的系統(tǒng)

n自適用性

□從程序到系統(tǒng)

口系統(tǒng)設(shè)計(jì)

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

■自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

23

實(shí)體與計(jì)算結(jié)合

硬件平臺(tái):

■速度B

?存儲(chǔ)

■功率

■失敗率;1

電

琵

?溫度1三

7莪

一

i卷..

:?0

W.

::1=呈

件

軟

用#t

「

">?件1.

B，

^系

紓

克

鄉(xiāng)

尸

fi0.

.孝.

，

於

24

實(shí)體與計(jì)算結(jié)合

/.1

二

二

a:■三i

ftp

lsow<areeo:n1sV.V

"app2l

lieetwlaI

malsdlre

-o

25

實(shí)體與計(jì)算結(jié)合

HWPlatform:

■CPUspeed

■memory

"powdr

■failurerates;/.三

0二

7

、

■temperature善

y1

-_IMtaaaaMaaaaiia

B一

1=--

件

軟

.￡

"B>件1

系

紓

.

，

26

軟件設(shè)計(jì)前后一致整合這些

HWPlatform:

■CPUspeed

■memory

■powSr

■failurerates/.

47

■teipperature"、

窘1.

抵wa:

■一5a6arueeo:nsV

lic

/mPP2Iewa

登oscllre

我們需要重新計(jì)算并修正來自電子工程和控制的整合方法

實(shí)體與計(jì)算的結(jié)合-實(shí)例

物理系統(tǒng)工程計(jì)算系統(tǒng)工程

分析模型計(jì)算模型

組件:傳遞函數(shù)組件:子程序

結(jié)構(gòu)：并行結(jié)構(gòu)：串行

連接:數(shù)據(jù)流連接:控制流

Pb:分析和計(jì)算模型一致的組合

28

RelativeSlip

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

29

□從程序到系統(tǒng)

口系統(tǒng)設(shè)計(jì)

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

?自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

31

組件設(shè)計(jì)

□使用構(gòu)件組裝眾多優(yōu)點(diǎn)比如生產(chǎn)力和正確性建立復(fù)雜系統(tǒng)

□構(gòu)件組裝精心策劃部件交互.它是并行計(jì)算的核心.

組件設(shè)計(jì)-異構(gòu)性

異構(gòu)性：系統(tǒng)設(shè)計(jì)者處理大量有不同的特性的組件,來自不同的觀點(diǎn)，每個(gè)

來自系統(tǒng)不同的維度

TSpacesConcurrentFortranJavaC

SoftbenchNesC

SWbusBPEL,

CorbaSES/Workbench

MPISysML

JavabeansAADL

.NETStatecharts

FractalMatlab/Simulink,

VerilogVHDLSystemCTLM

影響:

□使用形式化語義無關(guān)，例如程序，硬件描述和模擬，破壞設(shè)計(jì)流的一致性并

且危害它的聯(lián)接

□系統(tǒng)開發(fā)與驗(yàn)證和評(píng)價(jià)是解耦的.

組件設(shè)計(jì)-執(zhí)行的異步性

同步組件（硬件，多媒體應(yīng)用軟件）

□執(zhí)行是一連串的非可執(zhí)行的步驟

異步組件（通用應(yīng)用軟件）

□沒有預(yù)先定義的執(zhí)行步驟

未解決的問題：包含同步和異步單元的理論,比如GALS

組件設(shè)計(jì)-相互作用的異構(gòu)性

兩個(gè)基本協(xié)議

集合：原子對(duì)稱同步廣播:由發(fā)生者引發(fā)的不對(duì)稱同步

□任何交互機(jī)構(gòu)都可以表示為分層次的集合和廣播的組合

□存在的形式化和理論是不夠豐富表達(dá)的

-各種各樣低水平協(xié)調(diào)裝置包括信號(hào)監(jiān)控器信息傳遞函數(shù)調(diào)用

-通常點(diǎn)對(duì)點(diǎn)交互使用集合或者廣播

組件設(shè)計(jì)-粘合的概念

構(gòu)建一個(gè)滿足P的組件C：

■Co由它們自己行為描述的原子組件集合

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

satP

□粘合操作是協(xié)調(diào)機(jī)制比如協(xié)議、調(diào)度、總線

□我們需要一個(gè)統(tǒng)一的范例去描述分析各組件之間的協(xié)調(diào)

組件設(shè)計(jì)-粘合的要求

組合性:由正確的組件建立正確

的系統(tǒng)的規(guī)則

satPjimpliesgl

Qisatgl(Pl5..,Pn)

gi

我們需要組合結(jié)果去保留進(jìn)度屬性比如死鎖-自由和活性以及額外的功能屬性

組件設(shè)計(jì)-粘合的要求

可組合性:當(dāng)組件整合的時(shí)候保

留基本屬性

andsatP'

gl十gi'satP&P'

impliesooo

性能穩(wěn)定現(xiàn)象尚不清楚.我們需要可組合結(jié)果,例如,非相互作用的特點(diǎn)在中

間件,調(diào)度算法的可組合性,web服務(wù)的方面

□從程序到系統(tǒng)

口系統(tǒng)設(shè)計(jì)

口三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

■組件設(shè)計(jì)

■自適應(yīng)性

概要

□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

39

適應(yīng)性-智能系統(tǒng)

智能系統(tǒng)的兩個(gè)

自適應(yīng)性

□系統(tǒng)的行為適合滿足以給定的需要包括安全性能，其外部環(huán)境和可執(zhí)行

環(huán)境的不確定存在

□由控制技術(shù)正確執(zhí)行

適應(yīng)性-處理不確定性

系統(tǒng)必須提供一個(gè)滿足給定需求在非確定性環(huán)境下的交互

非確定性可以被看作是平均和極端系統(tǒng)行為之間的不同

資源的不確定性:

口物理環(huán)境

■不確定性行為e.g.不同吞吐量

■攻擊，惡毒行為

口執(zhí)行平臺(tái)

■由制造業(yè)的誤差或者老化引起的可變性

?由于分層緩存投機(jī)執(zhí)行引起的不同的執(zhí)行時(shí)間

■時(shí)序異常（物理增加平臺(tái)速度而降低性能）

適應(yīng)性-可預(yù)測(cè)性

不確定行直接通過模型和分析影響行為的可預(yù)測(cè)性

可預(yù)測(cè)是一個(gè)系統(tǒng)的行為通過定性或者定量應(yīng)該被正確預(yù)測(cè)的一個(gè)度.

缺乏可預(yù)測(cè)性

□由于非確定性，系統(tǒng)模型代表實(shí)際系統(tǒng)行為的安全抽象

□進(jìn)一步，給定一個(gè)模型，由于所有關(guān)鍵系統(tǒng)性能的不可計(jì)算行，精

確分析技術(shù)是不可能的

后果

□缺乏可預(yù)測(cè)性表示額外的不確定性

□對(duì)于復(fù)雜系統(tǒng)，在設(shè)計(jì)時(shí)預(yù)測(cè)所有可能的關(guān)鍵狀態(tài)時(shí)不可能的

A

A

三

q

e

q

o

QI

ForsimpleoperationsWCETmaybe300xBCE

自適用性-苛求和盡力服務(wù)工程

兩個(gè)相異的設(shè)計(jì)范式

苛求系統(tǒng)工程是以最壞分析和靜態(tài)資最佳效果工程是以平均情況分析和

源保留為基礎(chǔ)的，比如，硬實(shí)時(shí)方法動(dòng)態(tài)資源管理為基礎(chǔ)的。比如，

和大量冗余。優(yōu)化速度的服務(wù)質(zhì)量,存儲(chǔ)帶寬，

電源可用性保證

導(dǎo)致維度過大的系統(tǒng)

適應(yīng)性-加強(qiáng)可預(yù)測(cè)性

聯(lián)合架構(gòu)導(dǎo)致增加開發(fā)成本e.g.汽車工業(yè)

2.系統(tǒng)的自適應(yīng)控制技術(shù)整合苛求和最佳效果特點(diǎn)，比如IMA

■一個(gè)可預(yù)測(cè)的足夠大的全局資源滿足臨界屬性

■最佳效果的應(yīng)用需要有效的最優(yōu)化使用現(xiàn)有的資源

?自適性-自適應(yīng)控制

學(xué)習(xí)：預(yù)估執(zhí)行時(shí)間

基目標(biāo)管理：找出一個(gè)質(zhì)量最大化的日程安排并且滿足

相截止日期

計(jì)劃：對(duì)給定質(zhì)量計(jì)算最好的日程安排

(schedule,q)time

46

適用性-自適應(yīng)控制

學(xué)習(xí)

去：1）體育場2）電影院3）餐館

47

適應(yīng)性-自適應(yīng)控制

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

□從程序到系統(tǒng)

□系統(tǒng)設(shè)計(jì)

□三大挑戰(zhàn)

■實(shí)體與計(jì)算結(jié)合

O■組件設(shè)計(jì)

V

E

R■自適應(yīng)性

V

I□計(jì)算機(jī)科學(xué)的遠(yuǎn)景

E

W

計(jì)算機(jī)科學(xué)的遠(yuǎn)景

計(jì)算機(jī)科學(xué)

□由于技術(shù)和應(yīng)用的指數(shù)級(jí)發(fā)展而產(chǎn)生，是一個(gè)年輕卻發(fā)展迅速的學(xué)科

口著重于系統(tǒng)構(gòu)建，因此系統(tǒng)設(shè)計(jì)是該學(xué)科的核心

口現(xiàn)存的計(jì)算模型應(yīng)該擴(kuò)展，用以兼容物理特性-物質(zhì)資源，例如內(nèi)存、

時(shí)間、功耗，應(yīng)該是首要考慮要素

口補(bǔ)充并增強(qiáng)理論知識(shí)，以及需要深層次理解動(dòng)態(tài)離散系統(tǒng)的模型

□提出建設(shè)性的并有效可行的世界觀，這一世界觀可補(bǔ)充經(jīng)典的陳述性

的被物理學(xué)采用的方法

工計(jì)算機(jī)科學(xué)遠(yuǎn)景-TheFrontiersofCS

0K?VP9?O*C

6J5%tt<HHBMIwl*?

=豐

?e?uWtS?Mlf

it4?e?，e*IM?"beqgto

eaztvrIM*

-onCommandWl0Bu^-X

-O