MARTES 2006 at MoDELS 2006
International workshop on Modeling and
Analysis of Real-Time and Embedded Systems
Research Report 343 S. Gerard, S. Graf, Ø. Haugen, I. Ober, B. Selic
I SBN 82-7368-299-4 I SSN 0806-3036
October 2006
Session I : Visions and standards (1h20) 09:40 - 10:30 Keynote talk: to be announced
10:30 - 11:00 Towards a UML-based Modeling Standard for Schedulability Analysis of Real-time systems
H. Espinoza, J. Medina, H. Dubois, S. Gerard, F. Terrier
5
Session II : Validation and tools (1h30)
11:30 - 12:00 A3S method and tools for analysis of real time embedded systems
S. Rouxel, G. Gogniat, J-P. Diguet, J-L. Philippe, C. Moy
15
12:00 - 12:20 Modeling with logical time in UML for real-time embedded system design
Ch. André, A. Cuccuru, R. de Simone, Th. Gautier, F. Mallet, and JP. Talpin (work-in-progress)
27
12:20 - 12:40 Analysis and Modeling of Real-Time Systems with Mechatronic UML taking Clock Drift into Account H. Giese, S. Henkler, and M. Hirsch (work-in-progress)
41
12:40 - 13:00 Analyzing Robustness of UML State Machines
S. Prochnow, G. Schaefer, K. Bell, and R. von Hanxleden (work-in-progress)
61
Session III : New language ideas (1h30) 14:30 - 15:00 Time Exceptions in Sequence Diagrams
O. Halvorsen, R. K. Runde, Ø. Haugen
81 15:00 - 15:30 An Approach to Performance Modeling of Software Product
Lines
J. A. Street and H. Gomaa
101
15:30 - 16:00 Concurrency and Real time specifications in UML K. Lano, K. Androutsopolous, D. Clark
117
Session IV : Experience reports (1h45)
16:30 - 16:50 Modeling WS-BPEL with RT-UML Diagrams
M.-E. Cambronero, J-J. Pardo, G. Diaz, and V. Valero (work-in-progress)
137
16:50 - 17:10 Applying Model Intelligence Frameworks for Deployment Problem in Real Time and Embedded Systems
A. Nechypurenko, E. Wuchner, J. White, D. C. Schmidt
151
7RZDUGVD80/%DVHG0RGHOLQJ6WDQGDUGIRU 6FKHGXODELOLW\$QDO\VLVRI5HDO7LPH6\VWHPV
+XiVFDU(VSLQR]D-XOLR0HGLQD+XEHUW'XERLV6pEDVWLHQ*pUDUGDQG)UDQoRLV7HUULHU
&($6DFOD\'57'76,62///63)*LIVXU<YHWWH&HGH[)UDQFH
{huascar.espinoza, julio.medina, hubert.dubois, sebastien.gerard}@cea.fr
$EVWUDFW
7KLVSDSHUSUHVHQWVDJHQHULFPRGHOLQJIUDPHZRUNIRU VSHFLI\LQJ DQDO\]DEOH 80/ PRGHOV RI UHDOWLPH V\VWHPV 7KHXQGHUO\LQJZRUNZDVFDUULHGRXWLQWKHFRQWH[WRIWKH 20* LQLWLDWLYH IRU VWDQGDUGL]LQJ D 80/ SURILOH IRU 0RGHOLQJ DQG $QDO\VLV RI 5HDO7LPH DQG (PEHGGHG V\VWHPV0$57(ZKLFKUHSODFHVDQGH[WHQGVWKHSURILOH IRU 6FKHGXODELOLW\ 3HUIRUPDQFH DQG 7LPH 6SHFLILFDWLRQ 637 :H IRFXV RQ VRPH XVDELOLW\ DQG IOH[LELOLW\
ZHDNQHVVHVRIWKH637PRGHOLQJIUDPHZRUNDQGGHVFULEH WKH LPSURYHPHQWV EURXJKW RII LQ 0$57( 7KH 80/
H[WHQVLRQV LQFOXGH QHZ DQDO\VLVVSHFLILF FRQFHSWV DLPHG WR VXSSRUW D EURDGHU UDQJH RI TXDQWLWDWLYH DQDO\VLV WHFKQLTXHV$GGLWLRQDOO\WKHPRGHOLQJDSSURDFKLQYROYHV D SUHFLVH ODQJXDJH WR XQDPELJXRXVO\ GHFODUH DQG DQQRWDWH QRQIXQFWLRQDO SURSHUWLHV ZLWK H[WHQGHG GDWD W\SHVYDULDEOHVDQGFRPSOH[H[SUHVVLRQV$VLOOXVWUDWLRQ ZH VKRZ KRZ WKLV SURILOH LV XVHG LQ WKH $&&25'_80/
PHWKRGRORJ\ WR HQDEOH VFKHGXODELOLW\ DQDO\VLV RI DQQRWDWHG80/PRGHOV
,QWURGXFWLRQ
7KH FUHDWLRQ RI PRGHOV VXLWDEOH IRU SUHGLFWLYH DQG TXDQWLWDWLYHDQDO\VLVLVDNH\FRQFHUQLQDQ\PHWKRGRORJ\
IRU UHDOWLPH V\VWHPV GHYHORSPHQW 7KH WLJKWHU WKH OLQN EHWZHHQ WKH UHDOWLPH DQQRWDWLRQV DQG WKH PRGHOLQJ DUWLIDFWV XVHG DORQJ WKH GHYHORSPHQW SURFHVV WKH VRRQHU WKHYHULILFDWLRQVIRUGHWHFWLQJDQGUHPRYLQJHUURUVFDQEH GRQH DQG WKH HDVLHU WKH GHVLJQ WUDGHRIIV IRU UHVRXUFHV DOORFDWLRQ EHFRPH >@ ,QGHHG WKH DELOLW\ WR HYDOXDWH 1RQ)XQFWLRQDO 3URSHUWLHV 1)3V EDVHG RQ PDWKHPDWLFDOO\ GHULYHG UHVXOWV VWHPPLQJ IURP DFFXUDWH PRGHOVLVIDUEHWWHUWKDQUHO\LQJH[FOXVLYHO\RQLQWXLWLRQ 7KH UHDOWLPH V\VWHPV FRPPXQLW\ KDV LQYHVWHG VSHFLDO HIIRUWVLQLQFRUSRUDWLQJWKHDELOLWLHVWRGHVFULEHWLPHOLQHVV SURSHUWLHV ZLWK HQRXJK H[SUHVVLYH SRZHU ZKLOH VWLOO SUHVHUYLQJ WKH PRGHOLQJ DEVWUDFWLRQ OHYHO XVHG E\
SUDFWLWLRQHUV
/LNH LQ RWKHU VRIWZDUH HQJLQHHULQJ GRPDLQV WKH
LQFUHDVH GHVLJQHUV¶ SURGXFWLYLW\ DQG FRSH ZLWK FRPSOH[LW\ DV ZHOO DV WKH IDFLOLW\ WKDW LW EULQJV WR FRPPXQLFDWHGHVLJQLQWHQWV DQG JHQHUDWHGRFXPHQWDWLRQ KDYH HQFRXUDJHG WKH XVDJH RI WKH 8QLILHG 0RGHOLQJ /DQJXDJH 80/ >@ LQ WKH UHDOWLPH GRPDLQ $V D VWDQGDUG LW DGGV D QXPEHU RI RWKHU ZHOONQRZQ DGYDQWDJHV WKDW PDNH LW D SULPDU\ PRGHOLQJ ODQJXDJH DORQJWKHVRIWZDUHOLIHF\FOH0RUHRYHUWKH0RGHO'ULYHQ 'HYHORSPHQW SDUDGLJP DQG SDUWLFXODUO\ WKH 0RGHO 'ULYHQ $UFKLWHFWXUH 0'$ LQLWLDWLYH >@ ZKRVH PRGHOLQJVXSSRUWLVSURYLGHGE\80/OHDGDSURPLVLQJ DSSURDFKIRUUHGXFLQJWLPHWRPDUNHWDQGHQULFKVRIWZDUH HQJLQHHULQJSUDFWLFHVE\PRYLQJWKHGHYHORSPHQWSURFHVV IURP OLQHVRIFRGH WR FRDUVHUJUDLQHG DUFKLWHFWXUDO HOHPHQWV
+RZHYHU80/SHUVHLVVRPHKRZVWLOOLPSUHFLVHDQG WKHUHIRUH LQ PDQ\ FDVHV LQVXIILFLHQW IRU HQDEOLQJ TXDQWLWDWLYH DQDO\VLV RI UHDOWLPH V\VWHPV >@ >@ >@
7KH TXHVWLRQ RI KRZ WR DGG UHDOWLPH PRGHOLQJ FDSDELOLWLHV WR 80/ KDV EHHQ DGGUHVVHG LQ GLIIHUHQW UHVHDUFKDQGLQGXVWULDOFRQWH[WVPRVWO\E\WKHGHILQLWLRQ RI ³SURILOHV´ ZKLFK LV WKH EXLOWLQ PHFKDQLVP WR H[WHQG 80/WRGLIIHUHQWVSHFLDOL]HGGRPDLQV7KXVIRUH[DPSOH WKH 20(*$ >@ SURILOH SURYLGHV D SUHFLVH IRUPDO VHPDQWLFV GHGLFDWHG WR WHPSRUDO DVSHFWV 80/0$67
>@ FRQVLGHUV WLPLQJ SURSHUWLHV DQG VFKHGXODELOLW\
DQDO\VLV IRU GLVWULEXWHG UHDOWLPH V\VWHPV DQG UHFHQWO\ D GUDIW 80/ SURILOH IRU WKH $YLRQLFV $UFKLWHFWXUH 'HVFULSWLRQ /DQJXDJH $$'/ KDV EHHQ SURSRVHG >@
ZKLFK ZRXOG DOORZ WR HDVLO\ LQWHJUDWH $$'/ DQDO\VLV WRROV ZLWK 80/ &$6( WRROV 3URILOHV DUH D SRZHUIXO H[WHQVLRQ PHFKDQLVP KRZHYHU PRVW RI WKHVH SURILOHV VXIIHUDODFNRIVWDQGDUGL]DWLRQ7KLVLVYHU\SUREOHPDWLF DVWKHLGHDRIDVWDQGDUGODQJXDJHZRXOGJHWORVW
6WDQGDUGL]DWLRQ SURYLGHV FRPPRQ VHPDQWLFV DQG QRWDWLRQVZKLOHDGRSWLQJWKHEHVWSUDFWLFHVIRUPRGHOLQJ UHDOWLPH V\VWHPV 6WDQGDUGV DUH DOVR D FRVW HIIHFWLYH VROXWLRQVLQFHLQWHURSHUDELOLW\DOORZVXVLQJGLIIHUHQWWRROV RQ WKH VDPH PRGHO DQG EHFDXVH RI WKH ORZHU RYHUDOO WUDLQLQJFRVWV$GGLWLRQDOO\WKLVKHOSVWRPDQDJHWKHULVN RQ WKH HYROXWLRQ RI WKH WRROV SURYLGHUV PDUNHW UHGXFLQJ WKH GHSHQGHQF\ RQ RQH VLQJOH WRRO $V DQ LQGXVWULDO
80/H[WHQVLRQVIRUPRGHOLQJWHPSRUDOSURSHUWLHVDVZHOO DVRWKHUQRQIXQFWLRQDODVSHFWVRIFRPSXWHUV\VWHPV
7KH 80/ 3URILOH IRU ³0RGHOLQJ 4XDOLW\ RI 6HUYLFH DQG )DXOW 7ROHUDQFH &KDUDFWHULVWLFV DQG 0HFKDQLVPV´
4R6 )7>@PDNHVXSSDUWRIWKHVHHIIRUWV,WGHILQHVD IUDPHZRUNWRGHILQHDQGDQQRWDWH4R6SURSHUWLHVLQ80/
PRGHOV 4R6 LV KHUH XVHG DV D JHQHUDO WHUP WR GHQRWH 1)3V 7KH 4R6 )7 SURILOH SURYLGHV D IOH[LEOH PHFKDQLVP WR GHILQH PRVW FRPPRQ 4R6 FKDUDFWHULVWLFV IRU GLIIHUHQW DSSOLFDWLRQ GRPDLQV E\ PHDQV RI 4R6 FDWDORJV 7KH 4R6 )7 DQQRWDWLRQ PHFKDQLVP LV VXSSRUWHG RQ D WZRVWHS SURFHVV ZKLFK LPSOLHV WKH FUHDWLRQ RI H[WUD REMHFWV UHTXLUHG MXVW IRU DQQRWDWLRQ SXUSRVHV 7KLV WZRVWHS SURFHVV KRZHYHU UHTXLUHV WRR PXFK HIIRUW IRU WKH XVHUV DQG PD\ LQGXFH QRW UHDGDEOH PRGHOV>@0RUHRYHU4R6 )7LJQRUHVVRPHQHFHVVDU\
DVSHFWV WR PRGHO 1)3 VSHFLILFDWLRQV LQ WKH UHDOWLPH GRPDLQ VXFK DV YDULDEOHV VSHFLILFDWLRQ DQG FRPSOH[
H[SUHVVLRQVHJWLPHH[SUHVVLRQV
7KHUHFHQW6\V0/ODQJXDJH>@LVEHLQJFRQVLGHUHGWR EHDGRSWHGE\WKH20*DVDODQJXDJHWRPRGHOFRPSOH[
V\VWHPV LQFOXGLQJ VRIWZDUH KDUGZDUH IDFLOLWLHV DQG SURFHVV DVSHFWV $OWKRXJK VWLOO LQVXIILFLHQW IRU WKH UHDO WLPHGRPDLQ6\V0/SURYLGHVVRPHXVHIXOPHFKDQLVPVWR PRGHO WKLV NLQG RI FRQFHUQV )RU LQVWDQFH WKH ³EORFN´
PRGXODU XQLW SURYLGHV FDSDELOLWLHV WR VSHFLI\ UHXVDEOH
³PRGHORULHQWHG FRPSRQHQWV´ GHILQLQJ D FROOHFWLRQ RI IHDWXUHV WKDW LQFOXGHV SDUDPHWHUV FRQVWUDLQWV DQG YDOXH VSHFLILFDWLRQVTXDOLILHGE\PHDVXUHPHQWXQLWV
$ WKLUG 20* VWDQGDUG LQWHQGHG WR VXSSRUW QRQ IXQFWLRQDO DQQRWDWLRQV LV WKH 80/ SURILOH IRU 6FKHGXODELOLW\3HUIRUPDQFHDQG7LPHVSHFLILFDWLRQ637
>@ ,W SURYLGHG D VWUDLJKWIRUZDUG DQQRWDWLRQ PHFKDQLVP ZLWK D PLQLPDO VHW RI FRPPRQ DQQRWDWLRQV WR SHUIRUP YHU\ EDVLF TXDQWLWDWLYH DQDO\VLV HVVHQWLDOO\ 50$ DQG TXHXLQJWKHRU\EDVHGDQDO\VLV1HYHUWKHOHVVLWVVWUXFWXUH ZDV QRW IOH[LEOH HQRXJK WR DOORZ IRU QHZ XVHUGHILQHG DQQRWDWLRQV RU IRU GLIIHUHQW DQDO\VLV WHFKQLTXHV 0RVW H[SHULHQFHV RI WKH SURILOH KDYH OHG WR D QXPEHU RI VLJQLILFDQWVXJJHVWLRQVIRULPSURYHPHQWDQGFRQVROLGDWLRQ
> @ GHHPHG WRR GLVUXSWLYH IRU D VLPSOH UHYLVLRQ 7KLV LQFOXGHG DOVR QHZ UHTXLUHPHQWV IRU VSHFLI\LQJ ERWK VRIWZDUH DQG KDUGZDUH DVSHFWV 0'$ FRPSOLDQFH IRU GHILQLQJ VHSDUDWHO\ WKH SODWIRUP WKH DSSOLFDWLRQ DQG DOORFDWLRQ PRGHOV DQG PRGHOLQJ RI RWKHU NLQGV RI 1)3V VXFKDVSRZHUFRQVXPSWLRQRUPHPRU\VL]H
+HQFHWKH20*FDOOHGIRUWKHGHYHORSPHQWRIDQHZ 80/SURILOHIRUWKH0RGHOLQJDQG$QDO\VLVRI5HDO7LPH DQG (PEHGGHG V\VWHPV 0$57( >@ 7KH UHVXOWV SUHVHQWHGLQWKLVSDSHUZHUHSHUIRUPHGLQWKHIUDPHZRUN
QDPHO\ VFKHGXODELOLW\ :H LQFRUSRUDWH LQ 0$57( D QXPEHU RI DGGLWLRQDO IHDWXUHV ZKLOH UHGXFHV WKH LPSOLFLW FRPSOH[LW\ RI 4R6 )7 0$57( DOVR LQWURGXFHV D SUHFLVH YDOXH VSHFLILFDWLRQ ODQJXDJH WKDW VXSSRUWV V\PEROLF YDULDEOHV DQG FRPSOH[ H[SUHVVLRQV IRU VSHFLI\LQJ 1)3V %XW PDLQO\ WKLV IUDPHZRUN SURYLGHV D FRPPRQPRGHOLQJIUDPHZRUNIRUGLIIHUHQWVFKHGXODELOLW\
DQDO\VLV WHFKQLTXHV E\ IDFWRUL]LQJ RXW FRQFHSWV XVHG LQ GLIIHUHQWDQDO\VLVPRGHOV
7KHSDSHULVRUJDQL]HGDVIROORZV,QWKHQH[WVHFWLRQ ZHSUHVHQWDTXLFNYLHZRIWKH0$57(SURILOH6HFWLRQ GHVFULEHV LWV PRGHOLQJ IUDPHZRUN WR VSHFLI\ 1)3V 6HFWLRQ GHVFULEHV WKH IUDPHZRUN IRU 6FKHGXODELOLW\
$QDO\VLV 0RGHOLQJ 6$0 ,Q 6HFWLRQ ZH VKRZ WKH XVDJH RI WKH SURILOH E\ PHDQV RI DQ H[DPSOH LQ WKH IUDPHZRUNRIWKH$&&25'_80/PHWKRGRORJ\>@
7KH80/SURILOHIRU0$57(
80/ XVHV WKH PHWDPRGHOLQJ WHFKQLTXH WR GHILQH LWV DEVWUDFWV\QWD[0HWDPRGHOVGHILQHODQJXDJHVHQDEOLQJWR H[SUHVV PRGHOV 7KLV PHDQV WKDW D PHWDPRGHO GHVFULEHV WKH YDULRXV NLQGV RI FRQWDLQHG PRGHO HOHPHQWV DQG WKH ZD\WKH\DUHDUUDQJHGUHODWHGDQGFRQVWUDLQHG+HQFHD 80/PRGHOLVVDLGWRFRQIRUPWRLWVPHWDPRGHO
3URILOHV FXVWRPL]H 80/ IRU D VSHFLILF GRPDLQ RU SXUSRVH XVLQJ H[WHQVLRQ PHFKDQLVPV DEOH WR HQULFK WKH VHPDQWLFV DQG QRWDWLRQ RI WKH PHWDPRGHO HOHPHQWV $ VWHUHRW\SHLVWKHEDVLFQRWLRQWKDWDOORZVH[WHQGLQJ80/
$ VWHUHRW\SH FDQ EH YLHZHG DV D VXEFODVV RI DQ H[LVWLQJ 80/FRQFHSWZKLFKSURYLGHVWKHFDSDELOLW\RIPRGHOLQJ GRPDLQVSHFLILF FRQFHSWV RU SDWWHUQV 6WHUHRW\SHV PD\
KDYH W\SHG SURSHUWLHV FDOOHGWDJ GHILQLWLRQV ZKLFK PD\
UHSUHVHQW DWWULEXWHV RU UHODWLRQV ZLWK RWKHU PHWDPRGHO HOHPHQWV &RPSOHPHQWDU\ VWHUHRW\SHV FDQ EH DOVR LQIOXHQFHGE\UHVWULFWLRQVH[SUHVVHGLQFRQVWUDLQWV
7KH 0$57( VWDQGDUG FRPSULVHV ERWK D FRQFHSWXDO GRPDLQ PRGHO DQG WKH FRQFUHWH80/ H[WHQVLRQ SURILOH 7KH ILUVW RQH GHILQHV NH\ FRQFHSWV DQG UHODWLRQVKLSV EHWZHHQ WKHP XVHG IRU GHVFULELQJ UHDOWLPH FRPSXWLQJ V\VWHPV 7KH VHFRQG RQH LV WKH VSHFLILFDWLRQ RI KRZ WKH HOHPHQWV RI WKH GRPDLQ PRGHO DUH UHDOL]HG E\ PHDQV RI VWHUHRW\SHVDQGKRZWKH\H[WHQG80/PHWDFODVVHV
$V )LJXUH VKRZV 0$57( LV VWUXFWXUHG DURXQG D FRUH SDFNDJH 7&50 ZKLFK GHVFULEHV PRGHOLQJ FRQVWUXFWVIRUWLPHUHVRXUFHVFRQFXUUHQF\DOORFDWLRQDQG 1)3VDQGWZRPDLQJURXSVRIVSHFLDOL]HGSDFNDJHVWKDW XVH DQG UHILQH WKH FRUH RQH 2QH JURXS WR PRGHO GHYHORSPHQWIHDWXUHVRIUHDOWLPHDQGHPEHGGHGV\VWHPV 57(0DQGWKHRWKHU RQH WRDQQRWDWHUHDOWLPHPRGHOV
2Q WKH RWKHU KDQG WKH *4$0 SDFNDJH SURYLGHV D JHQHULF EDVLV IRU GLIIHUHQW TXDQWLWDWLYH DQDO\VLV VXE GRPDLQV 7KH *4$0 SDFNDJH VXSSRUWV WZR PDLQ VXE SURILOHV IRUVFKHGXODELOLW\ DQDO\VLVWR SUHGLFW ZKHWKHU D VHW RI VRIWZDUH WDVNV PHHWV LWV WLPLQJ FRQVWUDLQWV DQG SHUIRUPDQFHDQDO\VLVWRGHWHUPLQHLIDV\VWHPZLWKQRQ GHWHUPLQLVWLFEHKDYLRUFDQSURYLGHDGHTXDWHSHUIRUPDQFH
$GGLWLRQDOO\ WKH SURILOH VWUXFWXUH DOORZV IRU DGGLQJ IXUWKHU DQDO\VLV GRPDLQV VXFK DV SRZHU FRQVXPSWLRQ PHPRU\XVHRUUHOLDELOLW\,WLVWKHLQWHQWLRQWRHQFRXUDJH PRGXODUVXESURILOHVIRUVXFKGRPDLQV
)LJXUH DOVR GHVFULEHV VRPH RI WKH PDLQ SRWHQWLDO DFWRUV WKDW PD\ XVH WKLV VSHFLILFDWLRQ 7KXV PRGHO GHVLJQHUV DUH GHGLFDWHG WR GHILQH WKH KDUGZDUH DQG VRIWZDUHDUFKLWHFWXUHRIUHDOWLPHV\VWHPV0RGHODQDO\VWV DUHPRGHOHUVFRQFHUQHGZLWKDQQRWDWLQJV\VWHPPRGHOVLQ RUGHU WR SHUIRUP VSHFLILF DQDO\VLV WHFKQLTXHV ([HFXWLRQ SODWIRUP SURYLGHUVDUH GHYHORSHUV DQG YHQGRUV RI UXQ WLPH WHFKQRORJLHV KDUGZDUH RUDQG VRIWZDUHEDVHG SODWIRUPV VXFK DV 5HDO7LPH &25%$ UHDOWLPH RSHUDWLQJV\VWHPVDQGVSHFLILFKDUGZDUHFRPSRQHQWV
)LJXUH$UFKLWHFWXUHRIWKH0$57(3URILOH
,Q WKH FRQWH[W RI 80/EDVHG TXDQWLWDWLYH DQDO\VLV DQQRWDWLQJ1)3VLVRIIXQGDPHQWDOUHOHYDQFHDQGLPSOLHV D QXPEHU RI PRGHOLQJ PHFKDQLVPV IRU FRPSOH[LW\
PDQDJHPHQW LQ WKH GHYHORSPHQW F\FOH EXW PDLQO\ IRU VSHFLI\LQJWLPHH[SUHVVLRQVVHPDQWLFDOO\ZHOOIRUPHG7KH IROORZLQJVHFWLRQGHVFULEHVWKH1)3PRGHOLQJSDFNDJHDV WKH EDVLF IUDPHZRUN WR PRGHO TXDQWLWDWLYH DQDO\VLV DVSHFWV
7KH1)30RGHOLQJ)UDPHZRUN
ORJLFDO RSHUDWLRQV FRQILJXUDWLRQV PRGHV PRGHOLQJ YLHZV DQG WKH SURSHUWLHV RIWKRVHPRGHOHOHPHQWV,WLV FRPPRQWRJURXSHOHPHQWSURSHUWLHVLQWRWZRFDWHJRULHV IXQFWLRQDOSURSHUWLHVZKLFKDUHSULPDULO\FRQFHUQHGZLWK WKH SXUSRVH RI DQ DSSOLFDWLRQ LH ZKDW LW GRHV DW UXQ WLPH DQG QRQIXQFWLRQDO SURSHUWLHV 1)3V ZKLFK DUH PRUHFRQFHUQHGZLWKLWVILWQHVVIRUSXUSRVHLHKRZZHOO LW GRHV LW RU LW KDV WR GR LW >@ 1)3V SURYLGHV LQIRUPDWLRQ DERXW GLIIHUHQW FKDUDFWHULVWLFV DV IRU H[DPSOH WKURXJKSXW GHOD\V RYHUKHDGV VFKHGXOLQJ SROLFLHVFRUUHFWQHVVVHFXULW\PHPRU\XVDJHDQGVRRQ
7KH 1)3 PRGHOLQJ IUDPHZRUN >@>@ LV HVSHFLDOO\
IRFXVHGRQIRUPDOL]LQJDVHWRIPRGHOLQJ80/FRQVWUXFWV WRVSHFLI\QRQIXQFWLRQDOLQIRUPDWLRQLQDSUHFLVHZD\,Q IDFW RQH RI WKH FRPPRQ FULWLFLVPV WR WKH637SURILOHLV WKHYHU\VXSHUILFLDOVHPDQWLFLQIRUPDWLRQWKDWLWSURYLGHV LQ SDUWLFXODU IRU SURPRWLQJ FRPPRQ XQGHUVWDQGLQJ RI VSHFLILFDWLRQ DQG H[FKDQJH RI VSHFLILFDWLRQV EHWZHHQ GLIIHUHQWWRROV7KXVGLIIHUHQWWRROVRUDQDO\VLVWHFKQLTXHV FRXOG XVH GLIIHUHQW PHWULFV IRU WKH VDPH FRQFHSW )RU LQVWDQFH D WDVN SULRULW\ DWWULEXWH IURP D VFKHGXOLQJ SHUVSHFWLYHLVGHILQHGLQWKHFRQWH[WRID³SULRULW\´VFDOH ZLWK HLWKHU LQFUHDVLQJ RU DOWHUQDWLYHO\ GHFUHDVLQJ QXPHULFDO YDOXHV 8QOHVV ZH SURSHUO\ TXDOLI\ 1)3V QR FRPPRQ PHDQLQJ ZLOO EH DGRSWHG UHJDUGOHVV RI KRZ GHWDLOHG DQG H[SUHVVLYH D SURSHUW\ QDPH PLJKW EH 7KH 1)3 PRGHOLQJ IUDPHZRUN DWWHPSWV WR RYHUFRPH WKHVH NLQGVRIDPELJXLWLHV
)LJXUH VKRZV D SDUWLDO YLHZ RI WKH PHWDPRGHO WKDW VXSSRUWV WKLV IUDPHZRUN 7KLV PHWDPRGHO SURYLGHV NH\
FRQVWUXFWV IRU PRGHOLQJ WKLV NLQG RI SURSHUWLHV DW WZR IXQGDPHQWDO VWDJHV GHFODUDWLRQ DQG VSHFLILFDWLRQ 1)3 GHFODUDWLRQLVLQWHQGHGWRTXDOLI\DQGDVVLJQH[WHQGHGGDWD W\SHV WR 1)3 YDOXHV 1)3 VSHFLILFDWLRQ DOORZV GHVFULELQJ YDOXHV DV FRQVWDQWV YDULDEOHV FRPSOH[ H[SUHVVLRQV LQFOXGLQJWLPHH[SUHVVLRQVLQDVWDQGDUGWH[WXDOODQJXDJH
1)3V DUH TXDOLILHG E\ WZR EDVLF DWWULEXWHV DQG E\ D GDWDW\SH1)3B7\SH%RWKDWWULEXWHVRI1)3VVWDWLVWLFDO TXDOLILHUDQGGLUHFWLRQKDYHEHHQDGRSWHGIURPWKH80/
SURILOH IRU 4R6 )7 >@ $ VWDWLVWLFDO TXDOLILHU LQGLFDWHV WKHW\SHRI³VWDWLVWLFDO´PHDVXUHRIDJLYHQSURSHUW\HJ PD[LPXP PLQLPXP UDQJH PHDQ YDULDQFH SHUFHQWLOH GLVWULEXWLRQ 7KHGLUHFWLRQ DWWULEXWH LH LQFUHDVLQJ RU GHFUHDVLQJGHILQHVWKHW\SHRITXDOLW\RUGHUUHODWLRQLQWKH DOORZHG YDOXH GRPDLQ RI 1)3V ,QGHHG WKLV DOORZV PXOWLSOHLQVWDQFHVRI1)3YDOXHVWREHFRPSDUHGZLWKWKH UHODWLRQ ³KLJKHUTXDOLW\WKDQ´ LQ RUGHU WR LGHQWLI\ ZKDW YDOXHUHSUHVHQWVWKHKLJKHUTXDOLW\RULPSRUWDQFH2QWKH RWKHU KDQG 1)3 7\SHV DGG WKH DELOLW\ WR FDUU\ D PHDVXUHPHQWXQLWIRU1)3YDOXHVDVVRFLDWHGZLWKSK\VLFDO GLPHQVLRQ PHDVXUHV $GGLWLRQDOO\ ZH SURYLGH WKH FDSDELOLW\RIGHILQLQJQHZXVHUVSHFLILFXQLWVLQWHUPVRI H[LVWLQJEDVHXQLWVWKURXJKDJLYHQFRQYHUVLRQIDFWRU
6LQFH D 80/ YLHZSRLQW 1)3V DUH LPSOHPHQWHG LQ 0$57( DVWDJ GHILQLWLRQV TXDOLILHG DQG W\SHG DV 1)3V 0$57( GHILQHV D VHW RI 1)3 7\SHV FRPPRQO\ XVHG LQ WKHUHDOWLPHDQGHPEHGGHGV\VWHPGRPDLQ([DPSOHVRI 1)37\SHVDUH'XUDWLRQ'DWD7UDQVPLVVLRQ5DWH'DWD 6L]H3RZHU EHWZHHQ RWKHUV $V LOOXVWUDWLRQ )LJXUH VKRZVWKHGHFODUDWLRQRIWKH'XUDWLRQ1)3W\SH
)LJXUH([DPSOHRIGHFODUDWLRQRIWKH'XUDWLRQ1)3W\SH $ PRGHO RI D V\VWHP ZKLFK LV FRQVLGHUHG WR EH H[SUHVVHG LQ 80/ FDQ EH DQQRWDWHG E\ VSHFLILF 1)3 YDOXHV H[SUHVVLQJ FRQFHSWV IURP D JLYHQ PRGHOLQJ FRQFHUQRUGRPDLQYLHZSRLQWIRUH[DPSOH6FKHGXODELOLW\
$QDO\VLV$QDQQRWDWHGPRGHOHOHPHQWGHVFULEHVFHUWDLQ RI LWV QRQIXQFWLRQDO DVSHFWV E\ PHDQV RI 1)3 DQQRWDWLRQV 7KHVH DQQRWDWLRQV DUH VSHFLILHG E\ WKH GHVLJQHU LQ WKH PRGHOV DQG DWWDFKHG WR GLIIHUHQW PRGHO HOHPHQWV([DPSOHVDUHWKHUHVSRQVHWLPHRIDWDVNZKHQ H[HFXWHGWKHXWLOL]DWLRQRIDUHVRXUFH7KXVD1)36ORW
WR TXDOLI\ GLIIHUHQW YDOXH YHUVLRQV DV IRU H[DPSOH UHTXLUHG HVWLPDWHG RU FDOFXODWHG DQ DVVRFLDWHG PHDVXUHPHQWXQLWHJPV.%V0%WKDWRYHUZULWHVWKH GHIDXOWYDOXHGHFODUHGLQWKH1)37\SHGHILQLWLRQDQGD TXDOLILHUIRUGHVFULELQJWKHUHTXLUHGRURIIHUHGQDWXUHRID 1)3YDOXHUHT2IIHU
2Q WKH RWKHU KDQG1)3 9DOXH 6SHFLILFDWLRQ GHILQHV WKH WH[WXDO H[SUHVVLRQV DVVRFLDWHG ZLWK 1)3 VORWV 7KH 1)3PRGHOLQJIUDPHZRUNSURYLGHVDQDEVWUDFWV\QWD[DQG D JUDPPDU IRU VSHFLI\LQJ WKH YDOXHV RI 1)3V ,QGHHG ZKLOH1)3VYDOXHVDUHRIWHQDVVXPHGWREHVLPSOHYDOXHV WKHUH DUH FHUWDLQ FDVHV ZKHUH LW PD\ EH QHFHVVDU\ WR H[SUHVVVXFKYDOXHVLQDPRUHFRPSOH[ZD\)RUH[DPSOH LW PD\ EH UHTXLUHG IRU RQH 1)3 YDOXH WR EH UHODWHG LQ VRPH ZD\ WR DQRWKHU 7KLV UHTXLUHV ERWK D ZD\ RI UHIHUHQFLQJ WKH YDOXH RI DQRWKHU SURSHUW\ DV ZHOO DV WKH DELOLW\ WR XVH H[SUHVVLRQV VXFK DV DULWKPHWLF RU WLPH H[SUHVVLRQV 7KXV HDFK YDOXH FDQ EH VSHFLILHG DV D FRQVWDQWDVDYDULDEOHDVDFRPSOH[H[SUHVVLRQYDOXHD VSHFLDOGXUDWLRQRULQVWDQWH[SUHVVLRQRUDVDQLQWHUYDORI YDOXHVSHFLILFDWLRQV
7DEOHVKRZVW\SLFDOH[DPSOHVRIWKHQRWDWLRQIRUWKH ERG\RIYDOXHVSHFLILFDWLRQV
NFP Value Specification Example
Real Number 1.2E-3
Variable $timeout
Ordered Collection (1, 2, 5, 88)
Interval [1..251]
DateTime 12/01/06 12:00:00
Duration (between two events) ($startEvent, $endEvent) Duration (number of clock ticks) 5*t{refClock}
Constraints $deadline < $timeout + 5.0 Logical Expression $V1=(($clients<6)?(exp(6)))
7DEOH([DPSOHVRI1)39DOXH6SHFLILFDWLRQV ,Q6HFWLRQZHVKRZVRPHH[DPSOHVIRUVSHFLI\LQJ1)3 YDOXHVDQGDWWDFKLQJWKHPWR80/HOHPHQWVE\PHDQVRI WDJJHGYDOXHV
0RGHOLQJIRU6FKHGXODELOLW\$QDO\VLV
$OODQDO\VLVPHWKRGVXVHDVLPSOLILHGDEVWUDFWYLHZRI WKHV\VWHPWRDQDO\]HZKLFKIRFXVHVRQWKRVHDVSHFWVWKDW DUHUHOHYDQWWRWKHDVVRFLDWHGDQDO\VLVWHFKQLTXH7KXVWKH DQDO\VLV PRGHOLQJ FRQFHSWV UDUHO\ PDS RQHIRURQH WR DSSOLFDWLRQOHYHO PRGHOLQJ FRQFHSWV 3DUWLFXODUO\ LQ VFKHGXODELOLW\DQDO\VLVDNH\DEVWUDFWLRQLVWKHQRWLRQRID
LPSOLHGE\WKHSUHVHQFHRIPRGHOHOHPHQWVVXFKDVDFWLYH REMHFWVDQGDV\QFKURQRXVPHVVDJHV
7KH637SURILOHDOUHDG\LQFOXGHGDEDVLFFROOHFWLRQRI 80/ H[WHQVLRQV UHTXLUHG WR GHILQH DQDO\VLV PRGHOLQJ YLHZV SDUWLFXODUO\ IRU SHUIRUPDQFH DQG VFKHGXODELOLW\
DQDO\VHV +RZHYHU LW ZDV DFWXDOO\ VWDWHG WKDW WKH\ ZHUH LQVXIILFLHQW IRU D QXPEHU RI DQDO\VLV WHFKQLTXHV DQG IRU FHUWDLQ UHDOWLPH FRPSXWLQJ LPSOHPHQWDWLRQV OLNH GLVWULEXWHG V\VWHPV RU KLHUDUFKLFDO VFKHGXOLQJ >@ $V D FRQVHTXHQFHPRVW80/EDVHGDQDO\VLVPHWKRGVGLGQRW XVHUHILQHWKH637SURILOHDVSODQQHGLQVWHDGWKH\FUHDWHG WKHLURZQUHILQHGQRQVWDQGDUGH[WHQVLRQV>@>@
7R RYHUFRPH WKHVH SUREOHPV WKH 6$0 IUDPHZRUN GHVFULEHGLQWKLVVHFWLRQGHILQHVDFROOHFWLRQRIH[WHQGHG PRGHOLQJ FRQFHSWV DV ZHOO DV D VHW RI JHQHULF DQG H[WHQVLEOHUHSODFHDEOH 1)3V IRU WKHP RULHQWHG WR PRGHO UHDOWLPH FRPSXWLQJ V\VWHPV IURP D ZLGHU UDQJH RI VFKHGXODELOLW\ DQDO\VLV WHFKQLTXHV SHUVSHFWLYH 0$57(
SURYLGHVDPLQLPDOVHWRIFRPPRQDQQRWDWLRQVIRUPRGHO EDVHG VFKHGXODELOLW\ DQDO\VLV 7KLV PLQLPDO VHW IXUQLVKHV HQRXJK LQIRUPDWLRQ WR SHUIRUP FRPPRQ VFKHGXODELOLW\
DQDO\VHV +RZHYHU HDFKYHQGRULVHQFRXUDJHGWRVXSSO\
VSHFLDOL]HG1)3DQQRWDWLRQVWKDWH[WHQGWKLVVHWLQRUGHU WRSHUIRUPPRGHODQDO\VLVWKDWLVPRUHH[WHQVLYH
'RPDLQPRGHOIRUVFKHGXODELOLW\DQDO\VLV 7KH6FKHGXODELOLW\$QDOLV\V0RGHOLQJ6$0GRPDLQ PRGHOLVRUJDQL]HGDVLQ637XQGHUWKHFRQFHSWRID5HDO 7LPH 6LWXDWLRQ )URP WKH SUHGLFWLYH SRLQW RI YLHZ VFKHGXODELOLW\ DQDO\VLV PRGHOV DUH LQWULQVLFDOO\ LQVWDQFH EDVHG +HQFH D UHDOWLPH VLWXDWLRQ LV VWLOO D NLQG RI DQDO\VLVFRQWH[WWKDWUHSUHVHQWVDVSHFLILFVLWXDWLRQRIWKH V\VWHP ZRUNLQJ LQ D SDUWLFXODU PRGH DQG FRQILJXUDWLRQ DQGZLWKFRQFUHWHFRPSXWDWLRQDOUHVRXUFHV1HYHUWKHOHVV KLJKOHYHOGHVFULSWRUEDVHGPRGHOVFDQDOVREHHVWDEOLVKHG XVLQJWKH 57(0VXESURILOHVDQGWKHQFRQFUHWHDQDO\VLV PRGHOVPD\EHLQVWDQWLDWHGIRUVSHFLILFDQDO\VHV
$ UHDOWLPH VLWXDWLRQ FROOHFWV WKH UHOHYDQW TXDQWLWDWLYH LQIRUPDWLRQUHTXLUHGWRSHUIRUPVSHFLILFDQDO\VLV6WDUWLQJ ZLWK WKH UHDOWLPH VLWXDWLRQ DQG LWV HOHPHQWV D WRRO FDQ IROORZ WKH OLQNV RI WKH PRGHO WR H[WUDFW WKH LQIRUPDWLRQ WKDW LW QHHGV WR SHUIRUP WKH PRGHO DQDO\VLV $ UHDOWLPH VLWXDWLRQLVGHVFULEHGE\VHSDUDWHGPRGHOVDVVRFLDWHGZLWK WKUHHJHQHULFPRGHOLQJFRQFHUQV)LJXUH
:RUNORDG 6LWXDWLRQ D FRQVWDQW ORDG RI HQGWRHQG UHVSRQVHVWULJJHUHG E\ H[WHUQDOHJHQYLURQPHQWDO HYHQWVRULQWHUQDOHJDWLPHUVWLPXOL
%HKDYLRU ([HFXWLRQ D GHVFULSWLRQ RI WKH H[HFXWHG DFWLRQVFKDLQDVUHVSRQVHWRWKHZRUNORDGLQFOXGLQJ
7KLVVHSDUDWLRQRIPRGHOLQJFRQFHUQVSHUPLWVWRRUJDQL]H WKHGRPDLQPRGHOVLQWRFRPSUHKHQVLEOHSDUWV0RUHRYHU WKHVHFRQFHUQVPD\DFWDVDVHWRIGHVLJQVXEYLHZVDWWKH XVHU PRGHOLQJ OHYHO WKXV DOORZLQJ WR UHGXFH FKDQJLQJ LPSDFW DQG WR IDFLOLWDWH HYROXWLRQ DQG UHXVDELOLW\
+RZHYHUWKLVLVQRWDPDQGDWRU\XVHUPRGHORUJDQL]DWLRQ 8VHUVPD\FUHDWHGLIIHUHQWYLHZVLIGHVLUHGZLWKEDVLVRQ WKHIXQGDPHQWDO6$0FRQFHSWV
)LJXUH7KHPRGHOLQJFRQFHUQVRID5HDO7LPH6LWXDWLRQ
7KH :RUNORDG GRPDLQ PRGHO 7KLV PRGHO GHVFULEHV WKH FRQVWUXFWV UHTXLUHG WR VSHFLI\ WKH FRPSXWDWLRQ ORDG RQ WKH V\VWHP DQG WKH DVVRFLDWHG TXDQWLWDWLYH LQIRUPDWLRQ DERXW HQGWRHQG VWLPXOL UHVSRQVHVDQGWHPSRUDOUHTXLUHPHQWV
$ZRUNORDGVLWXDWLRQRIDUHDOWLPHV\VWHPLVW\SLFDOO\
GHILQHGE\WKHVHWRIVWLPXOLVWDUWLQJFRPSXWDWLRQV,QWKH 6$0 IUDPHZRUN ZH UHIHU WR DQ LQVWDQFH RI D SDUWLFXODU VWLPXOXV DV DQ HYHQW RFFXUUHQFH 6LQFH WKH VWLPXOXV FDQ RFFXU UHSHDWHGO\ ZH UHIHU WR UHFXUUHQFH RI HYHQWV DV D WULJJHU
$FRPSXWDWLRQWKDWLVSHUIRUPHGDVDFRQVHTXHQFHRID WULJJHU LV UHIHUUHG WR DV WKH UHVSRQVH WR LWV HYHQW RFFXUUHQFHV 'HSHQGLQJ RQ WKHLPSOHPHQWDWLRQQDWXUHRI UHVSRQVHV WKH\ FRXOG EH FRQFUHWL]HG LQ D VLQJOH WDVN H[HFXWLQJ LQ RQH SURFHVVRU RU LQ GHSHQGHQW WDVNV LQWR VLQJOH RU PXOWLSOH SURFHVVRUV :H GR QRW LQFOXGH LQ WKLV PRGHOWKHGHWDLOHGEHKDYLRULQYROYLQJDUHVSRQVHZHGRLW LQWKH%HKDYLRUPRGHO
1RWLFH WKDW WKHWULJJHU DQGUHVSRQVH FRQFHSWV VSHFLI\
RQO\HQGWRHQGEHKDYLRUVVSHFLILFDOO\WKHLU³FDXVH´VLGH DQGWKHLU³HIIHFW´VLGH7KXVLQRUGHUWRJURXSWKHVHWZR FRQFHSWVLQWRDVLQJOHPRGHOLQJXQLWZHDGRSWWKHFRQFHSW RIWUDQVDFWLRQ $ WUDQVDFWLRQ >>@@ UHIHUV WR WKH HQWLUH FDXVHHIIHFW HQGWRHQG EHKDYLRU GHVFULELQJ D VHSDUDWH FRPSXWDWLRQ LQ WKH V\VWHP +HQFH WKH VHW RI SDUWLFXODU WUDQVDFWLRQV GHILQLQJ RQH ORDG VFHQDULR IRU DQDO\VLV
)LJXUH7KH:RUNORDGGRPDLQPRGHO
$GGLWLRQDOO\ WKH WUDQVDFWLRQ WULJJHU DQG UHVSRQVH FRQFHSWV KDYH D VHW RI 1)3V XVHG IRU SHUIRUPLQJ TXDQWLWDWLYH DQDO\VLV :H GHILQH 1)3V DV WDJ GHILQLWLRQV GLVDPELJXDWHG E\ D VWDWLVWLFDO TXDOLILHU DQG D GLUHFWLRQ DWWULEXWH QRW VKRZQ KHUH IRU VSDFH UHDVRQV 'LIIHUHQW DQDO\VLV WHFKQLTXHV FRPPRQO\ XVH GLVVLPLODU 1)3V +RZHYHU WKH 6$0 PRGHO GHILQHV D SUHGHFODUHG VHW RI 1)3VXVHIXOIRUPRVWRIWKHDQDO\VLVWHFKQLTXHV
)RU LQVWDQFH D WULJJHU LV FKDUDFWHUL]HG E\ LWVDUULYDO SDWWHUQ ZKLFK LV D VWUXFWXUHG GDWD W\SH FRQWDLQLQJ FRQFUHWH DWWULEXWHV DV IRU H[DPSOHDUULYDO NLQGSHULRG PLQLPXP DUULYDO WLPH GLVWULEXWLRQ IXQFWLRQ DPRQJ RWKHUV 2Q WKH RWKHU KDQG UHVSRQVHV VSHFLI\ D VHW RI ODWHQF\ 1)3V FRQFUHWL]HG E\ HQGWRHQG GHOD\V RU WHPSRUDO UHTXLUHPHQWV HJHQGWRHQG WLPH GHDGOLQHV 7UDQVDFWLRQVPD\EHDOVRDQQRWDWHGZLWKHIILFLHQF\1)3V DV IRU H[DPSOHVODFN RUVSDUH FDSDFLW\REWDLQHG IURP VFKHGXODELOLW\ DQDO\VLV WRROV 7LPLQJ FRQVWUDLQWV RI WUDQVDFWLRQVDUHH[SUHVVHGLQWKHIRUPRI1)3FRQVWUDLQWV ZKLFK UHODWHV WR REVHUYHUV LPSOHPHQWHG E\ 1)3 YDULDEOHV WKDW PXVW EH DWWDFKHG DW VRPH SRLQW LQ WKH VHTXHQFHVRIDFWLRQVWKDWGHVFULEHWKHUHVSRQVHVFHQDULR 7KH %HKDYLRU GRPDLQ PRGHO )LJXUH VXPPDUL]HV WKH GRPDLQ FRQFHSWV IRU GHILQLQJ %HKDYLRU PRGHOLQJ DVSHFWV ,Q WKLV PRGHO WKHEHKDYLRUH[HFXWLRQ FRQFHSW VHUYHV WR FROOHFW GHWDLOHG GHVFULSWLRQV RI WKH EHKDYLRURIUHVSRQVHVZKLFKDUHFDOOHGLQWXUQUHVSRQVH VFHQDULRV %\ UHVSRQVH VFHQDULR ZH PHDQ WKH VSHFLILFDWLRQ RI WKH VPDOOHU VHJPHQW RI FRGH H[HFXWLRQ DQGWKHLUSUHFHGHQFHDQGFRQFXUUHQFHUHODWLRQVKLSV7KLV PRGHOLQJDVSHFWLVFRUHIRUTXDQWLWDWLYHDQDO\VLVLQRUGHU WRHYDOXDWHKRZWKHH[HFXWLRQVHJPHQWVFRQWHQGIRUXVH
H[HFXWLRQV FDOOHG VFKHGXOLQJ DFWLRQV 6$FWLRQ
&RQVLGHULQJ D KROLVWLF DSSURDFK IRU WKH DQDO\VLV DQ 57 DFWLRQ PD\ UHSUHVHQW WKH WLPH LW WDNHV D SLHFH RI FRGH H[HFXWLRQ DVZHOODVWKH VHQGLQJRIDPHVVDJHWKURXJK D QHWZRUN7KHRUGHULQJRI6$FWLRQVIROORZVDSUHGHFHVVRU VXFFHVVRU SDWWHUQ ZLWK WKH SRVVLELOLW\ RI PXOWLSOH FRQFXUUHQW VXFFHVVRUV DQG SUHGHFHVVRUV VWHPPLQJ IURP FRQFXUUHQW WKUHDG MRLQV DQG IRUNV UHVSHFWLYHO\ 7KH JUDQXODULW\ RI D 6$FWLRQ LV RIWHQ D PRGHOLQJ FKRLFH WKDW GHSHQGV RQ WKH OHYHO RI GHWDLO WKDW LV EHLQJ FRQVLGHUHG +HQFH D 6$FWLRQ DW RQH OHYHO RI DEVWUDFWLRQ PD\ EH GHFRPSRVHG IXUWKHU LQWR D VHW RI ILQHUJUDLQHG 6$FWLRQV 5HVSRQVH 6FHQDULRV XVH UHVRXUFH VHUYLFHV IRU H[HFXWLRQ WKURXJKWKHDOORFDWLRQRI6$FWLRQVWRVFKHGXODEOHHQWLWLHV DQG IRU RWKHU SODWIRUP VHUYLFHV WKURXJK FDOOV WRVKDUHG UHVRXUFHVDFTXLUHDQGUHOHDVHDFWLRQV
)LJXUH7KH%HKDYLRUGRPDLQPRGHO
7KH6$FWLRQFRQFHSWLVFRQVLVWHQWZLWK637DQGKHQFH LWLVFKDUDFWHUL]HGE\DVLPLODUVHWRI1)3VHQULFKHGZLWK VRPHRWKHUDQGH[WHQVLEOHODWHQF\SURSHUWLHVOLNHEHVWDQG DYHUDJHFDVHH[HFXWLRQWLPH
7KH 3ODWIRUP GRPDLQ PRGHO ,Q WKH 6$0 IUDPHZRUNWKHFRQFHSWRIUHVRXUFHVSODWIRUPPDWFKHVWR WKHPRGHORIHQJLQHHULQJUHVRXUFHVLQWURGXFHGLQWKH637 SURILOH >>@@ >>@@ 7KLV LQFOXGHV QRW RQO\ KDUGZDUH UHVRXUFHV &38 GHYLFHV EDFNSODQH EXVHV QHWZRUN UHVRXUFHV EXW DOVR VRIWZDUH RQHV WKUHDGV WDVNV EXIIHUV )LJXUH VKRZV D IUDPHZRUN WR GHVFULEH WKH SODWIRUPRIUHVRXUFHV
VFKHGXODELOLW\ DQDO\VLV DQG ZLWKRXWGLVWLQJXLVKLQJ DPRQJ GLIIHUHQW DEVWUDFWLRQ OHYHOV KDUGZDUH 5726 RU PLGGOHZDUH
7KHSODWIRUPPRGHOFRQVLVWVRIDVHWRIUHVRXUFHVZLWK H[SOLFLW 1)3V 7KLV PRGHO GLVWLQJXLVKHV WZR NLQGV RI SURFHVVLQJ HQJLQHVH[HFXWLRQ HQJLQHVHJ SURFHVVRUV FRSURFHVVRUVDQGFRPPXQLFDWLRQHQJLQHVHJQHWZRUNV EXVHV )RU HDFK WKH 6$0 IUDPHZRUN DVVLJQV JHQHULF 1)3V6SHFLILFDOO\WKURXJKSXWSURSHUWLHVHJSURFHVVLQJ UDWH RU WUDQVPLVVLRQ UDWH HIILFLHQF\ SURSHUWLHV HJ XWLOL]DWLRQVODFNDQGRYHUKHDGSURSHUWLHVDVIRUH[DPSOH EORFNLQJWLPHVLQWHUUXSWRYHUKHDGWLPHV
6FKHGXODEOH HQWLW\ LV D NLQG RI DFWLYH SURWHFWHG UHVRXUFH WKDW LV XVHG WR H[HFXWH 6$FWLRQV RU FRPSOHWH 5HVSRQVH6FHQDULRV,QD5726WKLVLVWKHPHFKDQLVPWKDW UHSUHVHQWVDXQLWRIFRQFXUUHQWH[HFXWLRQVXFKDVDWDVND SURFHVVRUDWKUHDG,QDQHWZRUNLWUHSUHVHQWVDFKDQQHO RUPHVVDJHPDQDJHPHQWXQLWWKDWFDQEHFKDUDFWHUL]HGE\
FRQFUHWH VFKHGXOLQJ SDUDPHWHUV OLNH WKH SULRULW\ IRU D
&$1EXV
3URFHVVLQJ HQJLQHV RZQ VKDUHG UHVRXUFHV DV IRU H[DPSOH,2 GHYLFHV'0$FKDQQHOVFULWLFDOVHFWLRQVRU QHWZRUN DGDSWHUV 6KDUHG UHVRXUFHV DUH G\QDPLFDOO\
DOORFDWHG WR VFKHGXODEOH HQWLWLHV E\ PHDQV RI DQ DFFHVV SROLF\&RPPRQDFFHVVSROLFLHVDUH),)2SULRULW\FHLOLQJ SURWRFRO KLJKHVW ORFNHU SULRULW\ TXHXH DQGSULRULW\
LQKHULWDQFHSURWRFRO
6FKHGXOHUV FDQ SOD\ WZR UROHV LQ WKLV PRGHOV\VWHP VFKHGXOHUV W\SLFDOO\ D 5726 VFKHGXOHU WKDW RIIHU WKH ZKROH SURFHVVLQJ FDSDFLW\ RI LWV DVVRFLDWHG EDVH SURFHVVRUVWRLWVDOORFDWHGVFKHGXODEOHHQWLWLHVDQGRWKHU VHFRQGDU\ VFKHGXOHUVWKDW RQO\ SURYLGH WKH SURFHVVLQJ FDSDFLW\ RIIHUHG E\ LWV KRVWLQJ VFKHGXODEOH HQWLW\ 7KLV KLHUDUFKLFDOVWUXFWXUHLVW\SLFDOO\XVHGLQ576ZKHQXVHUV DUH LQWHUHVWHG LQ DSSO\LQJ G\QDPLF VFKHGXOLQJ RQ WRS RI FRPPHUFLDO 5726 VXSSRUWLQJ RQO\ VWDWLF VFKHGXOLQJ /LNHZLVH QRYHO DOJRULWKPV H[LVW WKDW PDNH SRVVLEOH WR SHUIRUP UHDOWLPH DQDO\VLV RI WKHVH KLHUDUFKLFDO FRQILJXUDWLRQVRIVFKHGXOHUV>@
8VLQJWKH6$0VXESURILOH
:HQRZH[DPLQHKRZWKHGRPDLQFRQFHSWVSUHYLRXVO\
SUHVHQWHG FDQ EH UHSUHVHQWHG PDSSHG LQ WKH 80/
PRGHOLQJVSDFH7KHDQQRWDWLRQVKDYHEHHQPDGHRYHUD FDVH VWXG\ DSSOLFDWLRQ IRU WKH UHDOWLPH PRGHOLQJ DQG DQDO\VLVRIDVLPSOHGLVWULEXWHGV\VWHPIRUWKHWHOHRSHUDWHG FRQWURO RI D URERWL]HG FHOO >@ 7KLV H[DPSOH KDV EHHQ UHIRUPXODWHG LQ WKH FRQWH[W RI WKH $&&25'_80/
PHWKRGRORJ\IRUGHYHORSLQJUHDOWLPHHPEHGGHGV\VWHPV
$&&25'_80/ FRQVLVWV RI D IXOO 0'$ GHYHORSPHQW SURFHVV DQG WKH XQGHUO\LQJ PRGHOLQJ DQG H[HFXWLRQ SODWIRUPV FRYHULQJ IURP UHTXLUHPHQWV PRGHOLQJ HDUO\
TXDQWLWDWLYHDQDO\VLVWRIXOOLPSOHPHQWDWLRQ
7KHDSSOLFDWLRQV\VWHPLVFRPSRVHGRIWZRSURFHVVRUV LQWHUFRQQHFWHGWKURXJKD&$1EXV7KHILUVWSURFHVVRULVD WHOHRSHUDWLRQVWDWLRQ6WDWLRQLWKRVWVD*8,DSSOLFDWLRQ ZKHUH WKH RSHUDWRU FRPPDQGV WKH URERW DQG ZKHUH LQIRUPDWLRQ DERXW WKH V\VWHP VWDWXV LV GLVSOD\HG 7KH VHFRQG SURFHVVRU &RQWUROOHU LV DQ HPEHGGHG PLFURSURFHVVRUWKDWLPSOHPHQWVWKHFRQWUROOHURIWKHURERW VHUYRVDQGLWVDVVRFLDWHGLQVWUXPHQWDWLRQ
7KHVRIWZDUHDUFKLWHFWXUHLVGHVFULEHGE\PHDQVRIWKH FODVV GLDJUDP VKRZQ LQ )LJXUH 7KH VRIWZDUH RI WKH
&RQWUROOHU SURFHVVRU FRQWDLQV WKUHH DFWLYH FODVVHV FDOOHG UHDO WLPH REMHFW ±572 LQ $&&25'_80/ DQG D SDVVLYH RQH ZKLFK LVXVHGE\WKH DFWLYHFODVVHV WRFRPPXQLFDWH 6HUYR&RQWUROOHULVDSHULRGLF572WKDWLVWULJJHUHGE\D WLFNHU WLPHU ZLWK D SHULRG RI PV 7K H5HSRUWHU 572 SHULRGLFDOO\DFTXLUHVDQGWKHQQRWLILHVDERXWWKHVWDWXVRI WKHVHQVRUV,WVSHULRGLVPV7KH&RPPDQG0DQDJHU 572 LV DSHULRGLF DQG LV DFWLYDWHG E\ WKH DUULYDO RI D FRPPDQGPHVVDJHIURPWKH&$1EXV
7KH VRIWZDUH RI SURFHVVRU 6WDWLRQ KDV WKH W\SLFDO DUFKLWHFWXUH RI D *8, DSSOLFDWLRQ 7KH &RPPDQG ,QWHUSUHWHU572KDQGOHVWKHHYHQWVWKDWDUHJHQHUDWHGE\
WKHRSHUDWRUXVLQJWKH*8,FRQWUROHOHPHQWV7KH'LVSOD\
KDYH D VSHFLILF FRPPXQLFDWLRQ VRIWZDUH OLEUDU\ DQG D EDFNJURXQG WDVN IRU PDQDJLQJ WKH FRPPXQLFDWLRQ SURWRFRO
)LJXUH6RIWZDUHDUFKLWHFWXUHRIWKH7HOHRSHUDWHG5RERW 7R RUJDQL]H WKH $&&25'_80/PRGHOV DQQRWDWHG IRU VFKHGXODELOLW\ DQDO\VLV ZH DGRSW WKH FRQFHSW RIYLHZV ZKLFK UHSUHVHQW WKH FRQFHUQ PRGHOV FRPSRVLQJ WKH 6$0¶VDQDO\VLVFRQWH[WFRQFHSW,QWKLVZD\ZHSURYLGH VHSDUDWHG GLDJUDPV IRU VSHFLI\LQJ WKH 6$0 FRQFHSWV RI ZRUNORDG VLWXDWLRQEHKDYLRU H[HFXWLRQ DQGUHVRXUFHV SODWIRUP 1H[W ZH VKRZ VRPH H[DPSOHV WKDW LOOXVWUDWH WKLVRUJDQL]DWLRQ
([DPSOHRI:RUNORDG6LWXDWLRQ0RGHO
7KH 57B6LWXDWLRQ WR EH DQDO\]HG FRQWDLQV WKUHH WUDQVDFWLRQV ZLWK KDUG UHDOWLPH UHTXLUHPHQWV 7KH\ DOO XVH WKH SURFHVVLQJ UHVRXUFHV 6WDWLRQ &RQWUROOHU DQG
&$1B%XVDQGLQWHUDFWE\DFFHVVLQJSURWHFWHGREMHFWV 7KH&RQWURO 6HUYRV WUDQVDFWLRQ H[HFXWHV WKH &RQWURO UHVSRQVH ZLWK D SHULRG DQG D GHDGOLQH RI PV 7KH 5HSRUW 3URFHVV WUDQVDFWLRQ WUDQVIHUV WKH VHQVRUV DQG
SDWWHUQ EXW LWV LQWHUDUULYDO WLPH EHWZHHQ HYHQWV LV ERXQGHGWRV
)LJXUHVKDSHVD80/,QWHUDFWLRQ2YHUYLHZ'LDJUDP ,2'IRUWKH7HOHRSHUDWHG5RERWH[DPSOH7KLVDFWLYLW\
GLDJUDPUHSUHVHQWVDZRUNORDGVLWXDWLRQPRGHOFRQVLVWLQJ RI WKH WKUHH DERYHPHQWLRQHG WUDQVDFWLRQV FKDUDFWHUL]HG E\WKHLUWULJJHUVDQGUHVSRQVHV7KHVHWKUHHWUDQVDFWLRQV H[SOLFLWO\ LQWURGXFH WKH VHPDQWLF RI FRQFXUUHQF\ IRU WKH DFWLYLW\ SDUWLWLRQV7ULJJHUV LQWURGXFH WKH VHPDQWLF RI HYHQW VHTXHQFH DUULYDOV IRU WKH H[HFXWLRQ RI HDFK LQWHUDFWLRQ LQYRFDWLRQ :H DOVR LQFOXGH VRPH 1)3 DQQRWDWLRQVIRUWULJJHUDQGUHVSRQVHV
)LJXUH([DPSOHRI:RUNORDG6LWXDWLRQPRGHO ([DPSOHRI%HKDYLRU([HFXWLRQ0RGHO
7KH %HKDYLRU ([HFXWLRQ FRQFHSW H[WHQGV WKH 80/
PHWDFODVV,QWHUDFWLRQZKLFKFDQEHPRGHOHGE\DVHWRI VHTXHQFH RU FRPPXQLFDWLRQ GLDJUDPV LQ 80/ ,Q RXU H[DPSOH ZH DSSOLHG LW WR VHTXHQFH GLDJUDPV 7KXV WULJJHUV H[WHQG WKH PHWDFODVVPHVVDJH6$FWLRQV H[WHQG WKH 80/ FRQFHSW RIH[HFXWLRQ VSHFLILFDWLRQ )LQDOO\
VKDUHG UHVRXUFHV DUHOLIHOLQHV RI WKH VHTXHQFH GLDJUDPV 7KH FKDLQ RI DFWLRQV FRQQHFWHG E\ WKH VXFFHVVRU SUHGHFHVVRUSDWWHUQVV\PEROL]HVWKHFRQFHSWRIUHVSRQVH VFHQDULR
,Q)LJXUHZHSUHVHQWRQHRIWKHWKUHHVFHQDULRVIRUWKH 5HSRUWWUDQVDFWLRQ7KLVVFHQDULRUHSUHVHQWVWKHEHKDYLRU
)LJXUH([DPSOHRI%HKDYLRU([HFXWLRQPRGHO ([DPSOHRI5HVRXUFHV3ODWIRUP0RGHO
,Q )LJXUH WKH ³([HFXWLRQ (QJLQH´ GRPDLQ FRQFHSW H[WHQGVWKHPHWDFODVVQRGHVDQGWKHPHWDFODVV,QVWDQFH 6SHFLILFDWLRQVDUH XVHGWRUHSUHVHQWVFKHGXODEOHHQWLWLHV VKDUHGUHVRXUFHVDQGHYHQWXDOO\VFKHGXOHUV
6RPH6FKHGXODELOLW\$QDO\VLV5HVXOWV
7DEOHVKRZVWKHPRVWUHOHYDQWUHVXOWVREWDLQHGIURP WKH0$67VFKHGXODELOLW\DQDO\VLVWRROV>@,QWKLVWDEOH ZH KDYH FRPSDUHG WKH HQGWRHQG WLPHV RI HDFK RI WKH WKUHH WUDQVDFWLRQV RI WKH 5HDO 7LPH 6LWXDWLRQ ZLWK WKHLU DVVRFLDWHGUHVSRQVHV
Transaction/Response Slack EndToEndTime Deadline
Control_Servos Control
101.56%
3.05 ms 5 ms Report_Process
Report
189.84%
39.1 ms 100 ms Execute_Command
Command 186.72%
359 ms 1000 ms
7DEOH5HVXOWVRI6FKHGXODELOLW\$QDO\VLVZLWKWKH0$67WRRO
DQG V\VWHP VODFNV 7KHVH DUH WKH SHUFHQWDJHV E\ ZKLFK WKHH[HFXWLRQWLPHVRIWKHRSHUDWLRQVLQDWUDQVDFWLRQFDQ EHLQFUHDVHG\HWNHHSLQJWKHV\VWHPVFKHGXODEOH
1RWLFH WKDW PRVW DQDO\VLV WRROV RSHUDWH RQ D VLPSOLILHG YLHZ RI D V\VWHP DV ZDV LOOXVWUDWHG LQ WKLV H[DPSOH +RZHYHU WKLV SURILOH DOORZV DQQRWDWLRQV DQG LQWHUSUHWDWLRQVWREHDWWDFKHGDWWKHOHYHORIGHWDLOGHVLUHG E\WKHGHVLJQHU,QGHHGHYHQLIWKHVSHFLILFDWLRQFRQWDLQV H[WUHPHGHWDLOWKHDQQRWDWLRQVPD\RSWLRQDOO\EHDSSOLHG WRDJJUHJDWHV7KLVLVDQRYHUULGLQJUHDVRQWRILQGDSDWK WR DQQRWDWLRQV WKDW UHTXLUH D PLQLPXP RI HIIRUW ZLWK D PLQLPXPRIDGGLWLRQVWRWKHGHVLJQPRGHODQGZLWKFOHDU QRQIUDJPHQWHGVSHFLILFDWLRQVRI1)3V,WLVDOVRHVVHQWLDO WKDW1)3VFDQEHDWWDFKHGWRDUHDOVRIWZDUHGHVLJQUDWKHU WKDQ UHTXLULQJ D VSHFLDOYHUVLRQRIDGHVLJQFUHDWHG RQO\
IRUDQDO\VLV
&RQFOXVLRQV
7KLV SDSHU GHVFULEHV WKH 0$57( VFKHGXODELOLW\
DQDO\VLV VXESURILOH IRU HQDEOLQJ WLPLQJ SUHGLFWLRQV 2QH RI WKH PDLQ JRDOV EHKLQG WKLV VXESURILOH LV WR SURYLGH D FRPPRQ IUDPHZRUN ZLWKLQ 80/ WKDW IXOO\ HQFRPSDVVHV WKH PRVW FRPPRQ VFKHGXODELOLW\ DQDO\VLV WHFKQLTXHV EXW VWLOOOHDYHVHQRXJKIOH[LELOLW\IRUGLIIHUHQWVSHFLDOL]DWLRQV
7KH DSSURDFK LV VXSSRUWHG RQ WKH 1)3 PRGHOLQJ IUDPHZRUN,WGHILQHVDVHWRIPHFKDQLVPVWRGHFODUHDQG VSHFLI\ 1)3V WKDW DUH QHFHVVDU\ IRU GLIIHUHQW NLQGV RI TXDQWLWDWLYH DQDO\VHV 7KH UHODWLRQVKLSV EHWZHHQ 1)3V DQQRWDWLRQV DQG 80/ PRGHOLQJ HOHPHQWVLV GLVFXVVHGLQ RUGHUWRVKRZKRZWRGHFODUHGRPDLQVSHFLILF1)3VDQG KRZWRH[SUHVV1)3YDOXHVDWWDFKHGWRPRGHOHOHPHQWV
7KH VFKHGXODELOLW\ DQDO\VLV PRGHOLQJ 6$0 IUDPHZRUN SURYLGHV D FRPPRQ PRGHOLQJ EDVLV IRU GLIIHUHQW DQDO\VLV WHFKQLTXHV E\IDFWRUL]LQJ FRQFHSWVWKDW DUH XVHG E\ WKH YDULRXV VFKHGXODELOLW\ PHWKRGV 7KLV IUDPHZRUNH[WHQGVWKHSUHYLRXV637¶VVFKHGXODELOLW\VXE SURILOH DQG UHRUJDQL]HV LW LQWR JHQHULF DQG FRQVLVWHQW PRGHOLQJ FRQFHUQV ZRUNORDG EHKDYLRU DQG SODWIRUP 6$0DWWHPSWVWRHQKDQFHWKHH[SUHVVLYHSRZHURI80/
PRGHOV DQG WKH SURILOH XVDELOLW\ E\ HDVLQJ WKH FRPSUHKHQVLRQRIWKHJOREDOIUDPHZRUN
7KHXVDJHRI1)3DQG6$0IUDPHZRUNVDUHLOOXVWUDWHG E\WKHXWLOL]DWLRQRIWKHSURSRVHGDQQRWDWLRQVRQDW\SLFDO GLVWULEXWHGUHDOWLPHDSSOLFDWLRQIRUPXODWHGLQWKHIUDPH RIWKH$&&25'_80/PHWKRGRORJ\7KLVZRUNFDQEHVHHQ DV D ILUVW UHIOHFWLRQ RI WKH 80/ 0$57( SURILOH¶V VFKHGXODELOLW\DQDO\VLVFDSDELOLWLHV
5HIHUHQFHV
>@ 2EMHFW 0DQDJHPHQW *URXS 80/ 3URILOH IRU 6FKHGXODELOLW\ 3HUIRUPDQFH DQG 7LPH 9HUVLRQ
>@ 6 *pUDUG HGLWHG E\ 5HSRUW RQ 6,92(6¶637 :RUNVKRSRQWKHXVDJHRIWKH80/SURILOHIRU6FKHGXOLQJ 3HUIRUPDQFHDQG7LPH0DLWK7RURQWR&DQDGD
>@ 2EMHFW0DQDJHPHQW*URXS80/3URILOHIRU0RGHOLQJDQG
$QDO\VLV RI 5HDO7LPH DQG (PEHGGHG V\VWHPV 0$57(
5)320*GRFXPHQWUHDOWLPH
>@ 2EMHFW 0DQDJHPHQW *URXS 80/ 3URILOH IRU 0RGHOLQJ 4XDOLW\ RI 6HUYLFH DQG )DXOW 7ROHUDQFH &KDUDFWHULVWLFV DQG 0HFKDQLVPV20*GRFXPHQWSWF
>@ % 6HOLF $ *HQHULF )UDPHZRUN IRU 0RGHOLQJ 5HVRXUFHV ZLWK80/,(((&RPSXWHU9RO1SS-XQH
>@ 6 *pUDUG 0RGpOLVDWLRQ 80/ H[pFXWDEOH SRXU OHV V\VWqPHV HPEDUTXpV GH ODXWRPRELOH 3K' 7KHVLV (YU\3DULV
>@ 2EMHFW 0DQDJHPHQW *URXS 6\VWHPV 0RGHOLQJ /DQJXDJH 6\V0/6SHFLILFDWLRQ9HUVLRQ'UDIW
>@ 7 + 3KDQ $QDO\VH GRUGRQQDQoDELOLWp GDSSOLFDWLRQV WHPSV UpHO PRGpOLVpHV HQ 80/ 3K' 7KHVLV (YU\
3DULV
>@ -/0HGLQD0*+DUERXUDQG-0'UDNH0$675HDO 7LPH 9LHZ $ *UDSK LF 80/ 7RRO IRU 0RGHOLQJ 2EMHFW 2ULHQWHG 5HDO7LPH6\VWHPV 3URFRIWKHWK,(((5HDO 7LPH6\VWHPV6\PSRVLXPSS'HFHPEHU
>@ 5 &K HQ 0 6JURL * 0DUWLQ / /DYDJQR $ / 6DQJLRYDQQL9LQFHQWHOOL - 5DEDH\80/IRU5HDO'HVLJQ RI (PEHGGHG 5HDO7LPH 6\VWHPV (GLWHG E\ % 6HOLF / /DYDJQR * 0DUWLQ SS .OXZHU $FDGHPLF 3XEOLVKHUV0D\
>@ 2EMHFW 0DQDJHPHQW *URXS 0'$ *XLGH 9HUVLRQ
>@ 2EMHFW 0DQDJHPHQW *URXS 8QLILHG 0RGHOOLQJ /DQJXDJH 6XSHUVWUXFWXUH 9HUVLRQ 20* GRFXPHQW SWF
>@ 6 *UDI , 2EHU , 2EHU $ UHDOWLPH SURILOH IRU 80/
6777 ,QW -RXUQDO RQ 6RIWZDUH 7RROV IRU 7HFKQRORJ\
7UDQVIHU6SULQJHU9HUODJ
>@ . 7LQGHOO $GGLQJ 7LPH2IIVHWV WR 6FKHGXODELOLW\
$QDO\VLV 7HFKQLFDO 5HSRUW <&6 'HSDUWPHQW RI
&RPSXWHU6FLHQFH8QLYHUVLW\RI<RUN-DQXDU\
>@ 6KD/$EGHO]DKHU7$U]HQ.(&HUYLQ$%DNHU7
%XUQV $ %XWWD]]R * &DFFDPR 0 /HK RF]N\ - 0RN
$ . 5HDO 7LPH 6FKHGXOLQJ 7KHRU\ $ +LVWRULFDO 3HUVSHFWLYH 5HDO7LPH 6\VWHPV -RXUQDO 9RO 1R SS,6611RYHPEHU'HFHPEHU
>@ +(VSLQR]D+'XERLV6*HUDUG-0HGLQD'&3HWULX 0 :RRGVLGH $QQRWDWLQJ 80/ 0RGHOV ZLWK 1RQ )XQFWLRQDO 3URSHUWLHV IRU 4XDQWLWDWLYH $QDO\VLV 3URF RI 0R'(/66DWHOOLWH(YHQWV/HFWXUH1RWHVLQ&RPSXWHU 6FLHQFH6SULQJHU
>@ 2EMHFW 0DQDJHPHQW *URXS 80/ 3URILOH IRU 0RGHOOLQJ DQG $QDO\VLV RI 5HDO7LPH DQG (PEHGGHG V\VWHPV 0$57( ,QLWLDO 6XEPLVVLRQ 3UR0$57( WHDP 20*GRFXPHQWUHDOWLPH
>@ ( &ROEHUW 2YHUYLHZ RI WKH 80/ 3URILOH IRU WKH 6$(
$$'/ SUHVHQWDWLRQ
S. Rouxel, G. Gogniat, J-P. Diguet, J-L. Philippe
LESTER. CNRS FRE 2734 University Research Laboratory
France
<rouxel, gogniat, diguet, philippe>@univ- ubs.fr
C. Moy
SCEE Group, SUPELEC Cesson-Sévigné
France
[email protected]
Abstract
This paper describes a fast prototyping tool targeting software radio applications. It is based on the Unified Modeling Language (UML) and combines a Software Defined Radio UML profile to implement an MDA approach within EDA tools for multi-level verifications from type compatibility to schedulability analysis and memory use rate over an heterogeneous platform. Our approach relies on performance analysis to improve architecture and application matching thanks to non-functional criteria. The main contributions of our work are the improvement of the original meta-model of the Software Radio UML profile and its integration within a unified design framework. From a high abstraction level of a software application we perform extensive verifications and analysis to validate the designer hardware architecture choice and the corresponding implementations.
1. Introduction
Complex System on Chip (SoC) challenge is now achievable since both required hardware resources and integration technologies correspond to reality. The telecom domain is a great example where the SoC paradigm already enables the design of multi-standard chips (e.g. GSM, IEEE 802.11, IS-95). Such an evolution promotes the Software Radio concept for the management of multiple standards [1][2]. However, the design of such systems based on heterogeneous platforms (e.g. DSP, FPGA, GPP, memory) and intensive-computation software applications (e.g.
encryption, scrambling algorithm, and service management) cannot anymore be addressed with
design constraints, like CoWare, that uses SystemC/C++ hardware language specifications, or CoFluent studio, that is based on the MCSE methodology (Co-design Methodology for Electronic Systems) [3][4]. However regarding the current initiatives our approach is original in the way that we combine a Software Defined Radio (SDR) UML profile to implement an MDA approach within EDA tools for multi-level verifications over an heterogeneous platform. Furthermore we have defined very precise models through the A3S profile to perform accurate performance evaluations at the first stages of the design flow. In this paper we present our unified way to fill the gap between the specification and the prototyping phases by using UML. Our work is illustrated through an UMTS transceiver case study.
Major projects related to software radio are described in UML which enables modeling systems through a graphical approach. Furthermore UML continuously evolves to consider new specific characteristics from different activity domains thanks to the development of new profiles. A profile extends the UML language for a work context, which offers scalability. It specifies all characteristics (e.g. elements for real-time application) and relations between the UML elements. It allows model-based a priori verifications. A designer relies on the profile to analyze, generate code and specify various application and architecture constraints. Moreover, dependencies, inheritance, or groupings between profiles can be performed to promote the reuse of domain specific needs. Regarding the software radio application, three profiles are of interest: UML profile for Software Radio [5], UML profile for Schedulability Performance and Time [6] and UML profile QoS and Fault tolerance [7]. Each profile brings out some specific
proposes to extend their coverage through the development of a new and specific one. Its purpose is to highlight standard concepts required for system prototyping and to add hardware attributes that are not currently taken into account for Software Defined Radio applications. Furthermore the goal of our A3S project (System Application Architecture Adequacy) is not limited to the definition of the A3S profile but also targets its implementation within a rapid-prototyping tool to evaluate the feasibility of complex applications over heterogeneous platforms (with DSP, FPGA components). Specification of dynamic reconfiguration is also investigated since this feature will be mandatory especially for Software Radio applications.
The remainder of this paper is the following. Section 2 presents various high level system specifications and most relevant tools relying on the MDA approach.
Section 3 provides a global approach of system modeling as promoted within our project. Section 4 details the A3S profile and the UML modeling by giving the set of parameters required to compute verifications and performance evaluation. Section 5 details the scheduling analysis technique and the approach for design space exploration. Section 6 gives an example of an UMTS application modeling. Section 7 concludes the paper and gives an overview of future work.
2. Related Work
Many tools aim at modeling systems, performing verifications, simulations, validations, and synthesis.
Different modeling styles with different granularities are considered, different input specification languages as C, SystemC, VHDL, are also used to validate, verify, simulate or emulate a system [8][9]. First co- design tools, like VULCAN are using simple and limited hardware architecture models, others like COSYMA are based on dedicated hardware co- processors to speed up software execution [10][11].
COWARE and PTOLEMY consider heterogeneous specifications to respectively design specific applications (embedded telecom) and co-simulate heterogeneous HW/SW systems [12]. However these approaches are limited as they require the use of different tools that must be kept updated. Actually the goal is to perform both modeling and design specification of hardware platform and software
and application specifications, component properties, constraints specification) will be mandatory to accelerate the design cycle and to promote the design reuse. To target such a philosophy, the most recent rapid prototyping tools integrate methodology of hardware-software co-design into the concept of MDA (Model Driven Architecture) through UML.
ZeligSoft proposes a code generator that produces Software Communications Architecture (SCA) artifacts for Corba compliant targets. This approach is sizable regarding different aspects such as the SCA core framework [15] but no SoC meta-model is provided. In [16] the authors focus on the deployment design step but the analysis method is limited to Interface Definition Language (IDL), type compatibility and pure software concerns. There is no analysis addressing embedded systems issues such as memory, bus, real- time, power.
The Prompt2Implementation targets an MDA for SoC design. It is based on the ISP UML profile [17] for parallelism expression at task and data levels and on model to model engines. The main objective is to produce a simulation code (e.g. SystemC TLM) based on mapping rules. This is a very ambitious project restricted to very intensive signal processing, but the tools seem to be under development. Moreover, this approach does not address the SDR concept. The association between UML and SystemC is a promising approach, which is also explored in [18]. In this work, a UML SystemC profile is proposed and used to generate SystemC code. An object-oriented HW/SW synthesis flow based on an UML initial specification is described in [19]. The MOCCA compiler implements an MDA approach based on system, platform and deployment models. The current implementation is based on a processor/FPGA platform where SW and HW components have been implemented. This work is interesting but does not rely on SDR UML profile. In [20] the authors present a framework for software design space exploration based on performance and power estimation issued from an UML specification.
The method is based on a pre-characterized platform and enables the evaluation of software implementation solutions specified by the designer. FZI is developing a framework for the communication conflict analysis in a SoC context. In this approach [21] UML and SysML are combined to specify architectures when on the other side a sequence diagram is used to specify the
standardized profiles and extends them. This profile improves and offers more hardware specification possibilities that are essential for software radio or other electronic systems in order to specify hardware and software architecture systems. In addition our high abstraction level specification alleviates the modeling and the validation of applications that belong to other specific application domains. Moreover, as we consider applications as a set of IPs, components are only characterized by non-functional parameters instead of source codes (which depend on their implementations and need different tools).
3. A3S Design Approach
A3S approach proposes a UML software framework where the designer can rapidly and easily prototype his system and check if constraints are met in terms of timing, memory, area, and power consumption [22].
The main steps of our design flow for virtual prototyping are depicted in Figure 1.
Figure 1. A3S design flow
One important question is to know who the final user of the tool will be. Two kinds of actors can take benefit of the A3S framework:
• The component designers. They are concerned by the components definition (HW and SW) which takes place within the modelling and specification tool. They will create the software and hardware components libraries (IPs). For this kind of actors, some ergonomic wizards included in the design tool will help them to provide the correct values when creating new hardware and software components.
The verifications performed by the tools are related to the A3S profile (see Section 4). They allow the designer to see in a simple glance the errors within his design during each step of the A3S design flow. It is always possible, in spite of the existence of the GUI, that the designer gives values that are not coherent.
Thus, extensive verifications enable a faster and safer design flow. Some errors can be related to the architecture of a platform, or the connection between the software application and the embedded platform.
The designer can perform the verifications for the main points of a design (libraries of hardware components and software components, hardware platform and software application) or for a whole project.
Each step of the design flow is now detailed in the next sections.
3.1. Application specification (1st step)
With the MDA approach, software application and hardware architecture can be specified independently, so 1st step and 2nd step (see Figure 1) can be exchanged. To manage complexity, an application is split into several functions that are represented by independent generic software (SW) components. This view corresponds to PIM (Platform Independent Model) since each function can be potentially mapped onto any hardware component. SW components have specific non-functional parameters that correspond to specification constraints coming from the application or from some designer requests. An example of these parameters is the periodicity of the SW component which is independent from any implementation. More information about these parameters is detailed in Section 4. At this stage of the design flow SW components can represent any function.
A3S Project
HW/SW Components Designers
UML Components
Libraries
Software Radio Designers
A3S profile
A3S profile (UML meta-model)
Objecteering UML tool Application Specification
(PIM)
Embedded Platform specification
HW / SW Deployment
(PSM)
Verification Web Server (XAPA tool)
Non-functional verifications (Schedulability, resources workload) SW
Lib.
HW Lib.
XML schedulability
result XMI
Architecture definition
1st step 2nd step
3rd step
parameters related to the exchanged data (e.g. number, size). For each component, the designer specifies the corresponding parameters value. An Activity Diagram has been considered since it enables the description of the dynamicity of a system. Activity Diagrams allow the modeling of the process described by activity chains with information related to transmission, connection management, and activity responsibility description.
An activity diagram example for an UMTS-FDD receiver is given Figure 2. This diagram also addresses the links between the different SW components to specify the system radio functionality. The black dot represents the input of the application which takes place at the propagation channel side. Each arrow corresponds to an edge (transition) and represents a data-flow dependency. The UMTS-FDD receiver is mainly a data-flow application with periodic and iterative functions (FrameProcessing, SlotProcessing, RadioProcessing, TransportBloc). The black dot in the circle is the output of the application; it corresponds to the exchanged data between the physical layer and the higher layers of the OSI model.
Through this model the designer can easily replace, add, move/remove a SW component, or modify some parameters to enhance the algorithm and thus test various configurations. By this way, he can analyze the impact of different reconfigurations, which is of major importance in a software radio context. Once the application model is completed, some coherency constraints verifications are performed. Among them, the tool verifies that all connections between SW components have been correctly done, through compatible data format and that all required parameters have been settled. These verifications have been implemented within the Objecteering case tool [23].
3.2. Embedded platform specification (2nd step) This step deals with the platform specification. Each hardware component is described in a hardware library (DSP, FPGA, GPP, memory, interconnect and ASIC) corresponding to an UML package. Each component has specific attributes defined through its stereotypes (this point is developed in Section 4). The designer builds his platform by assembling hardware component instantiation (in UML sense) through a UML deployment diagram. Many hardware platforms can be realized, especially heterogeneous platforms. This kind
3.3. Hardware/Software deployment (3rd step) After the software application and hardware platform modeling steps, the designer chooses which dedicated SW component is implemented onto which hardware component. For each SW component, the designer selects the corresponding function in the software component library as a SW component corresponds to a processing element that is not dedicated to a specific target (PIM). Thus, the function represents an implementation of the SW component onto a processor (e.g. DSP, GPP, μC), a FPGA or an ASIC. The target hardware component selected to implement the SW component is obtained by defining an instance of a hardware component within the hardware platform in the UML deployment diagram.
Figure 3. Deployment diagram after mapping When a SW component has been deployed onto an hardware resource new attributes are highlighted which represent the implementation details. This refinement corresponds to the transition from a PIM to PSM (Platform Specific Model) model where specific parameters are requested to do a performance analysis.
A broad range of implementation solutions can be tested for a specific platform due to all possible combinations. The example in Figure 3 depicts an hardware platform composed of two DSPs (DSP_A, DSP_C) on which different software components are implemented (e.g. scrambling function is implemented
functions (SCR, SUM, SPRdpcch, DPCCHctrl).
3.4. Non-functional verifications
During the specification steps, non-functional verifications are automatically performed thanks to the use of the A3S meta-model. Verifications within the Objecteering case tool are stored in a tree which allows the definition of priority levels for all non-functional verifications. Methods related to the verification rules are connected to the branches and the leaves of the tree.
Verifications can be simple numeric value checking (attribute value different from zero) or more complex techniques to verify specific properties (data production and consumption coherency). All the methods are coded using the J language which is dynamic and interpreted. J language exploits the meta- class, meta-associations and meta-attributes to get access to the attributes which are stored as taggedValues. The verification report is generated while traveling through the tree and displayed to the designer (Figure 4).
Figure 4. Checking procedure of a SW application after deployment – first part (PIM)
– second part (PSM) for each HW platform
3.5. Schedulability analysis results (4th step)
Results are provided through a schematic view defined in a UML sequence diagram which is close to a Gantt diagram. The results emphasize the performances achieved for a heterogeneous platform with multi- processor resources to perform the application. For example, execution time, resources use rate, system evolution (scheduling), allocated memory resources are exhibited. Scheduling information is very important as if the system cannot be scheduled or if it does not reach
application onto different platforms and with different implementations for a same platform. It also promotes testing different configurations and re-configurations of the system. The design space exploration is performed manually and iteratively in the current methodology. It is also possible to modify some hardware characteristics by changing hardware component parameters value. Moreover, this tool returns results that help designer to perform modifications according to identified critical functions.
3.6. Ergonomics – wizard – GUI
To provide an intuitive verification tool, the checking preserves the hierarchy of the elements within a project (components, application/platform, deployment) and indicates through a message the possible errors or warnings. Thus, it is easy for the designer to analyze where the problem comes from and to further help him the tool points out the element affected by the error when clicking on an error message.
Figure 4 shows the consistency report as it is provided to the designer. As we can see an error is highlighted which enables the designer to change his specification before going through the non-functional verifications tool that analyzes the schedulability of the system.
Figure 5. Relation between A3S profile and the OMG standard profiles
4. A3S profile and UML Modeling
4.1. A3S Profile
One of the goals of A3S is to emphasize non- functional characteristics on PIM and PSM and to
applications, it can be extended through the use of stereotypes coming from the QoS profile and the Real Time Scheduling and Performances profile on each of the components addressed by the Software Radio profile.
In order to address the DSP/FPGA specific domain, it is possible to extend the software radio profile by introducing specific DSP and FPGA stereotypes representing DSP and FPGA components derived from the processor stereotype of the software radio profile.
These new stereotypes will be tagged with stereotypes extracted from the QoS profile to describe the quality of service metric of the DSP and the FPGA.
Using standardized profiles and the components they introduce, will allow the designer to reuse some legacy components by wrapping them into a standard
system composition, instead of being compelled to discover and/or create new components from scratch.
This method is already used for a long time by software developers to de-couple from third-party provided components. Such an approach is the only way to enable a smooth transition from existing methods to new ones. It also allows the integration of non-compliant external component.
The A3S profile formalizes through a rigorous semantic the elements that will be used to build the software radio architecture models. Our formalization enables the definition of the verification rules. These elements extend or use some elements extracted from the previously explained OMG standard profiles, as illustrated in Figure 5.
A3S OMG
a3s-CommEquipement
a3s-Processor
a3s-SoftwareProcessor
a3s-GPP a3s-DSP
a3s-GPPvirtual a3s-DSPvirtual
a3s-ProgrammableLogicalDevice
SoftwareProcessor
ProgrammableLogicalDevice Processor
CommEquipement Device
a3s-Memory
a3s-Memoryvirtual
a3s-OMAP a3s-DigitalPort
a3s-Port a3s-CommEquipementConnector
Port
DigitalPort CommEquipementConnector
Connector
1
*
1 AggregationPrefixa3s-DigitalPort
*
AggregationPrefixa3s-Port
1
*
*
*
*
*
AggregationPrefixDigitalPort
1 AggregationPrefixPort*
*
AggregationPrefixa3s-Processor
0..1
*
*
0..1
Internat Memory (composed)
and the reusability of the A3S models. Since the interfaces can be standardized by this way, it is then possible to work and verify any A3S model assuming that the tools have the A3S profile. This A3S profile main interest resides in the fact that all the interfaces may be standardized, and that all the elements are redefined from the basic types, warranting an automatic generation of interface specification through the IDL syntax language.
Figure 6 illustrates the hardware meta-model of the profile that defines the stereotypes that will be used to design Software Radio platforms. It extends the OMG software radio model (on the right part of the figure), by defining new stereotypes prefixed by the “a3s-“
keyword. They inherit from each of the main components of the OMG software radio profile and provide some non-functional information (on the left part of the figure). For instance, according to the OMG software radio profile, each hardware component of a software radio can be stereotyped by the CommEquipment element and that the CommEquipment are connected to each other through some CommEquipmentConnectors linked to their DigitalPort. A3S provides the same elements extended with QoS characteristics, that may range from data size and processing frequency to power consumption. Such an inheritance is generic enough to envision the future addition of new QoS characteristics to an element of the A3S profile, without disturbing all the models of the software radio platform.
The first step for QoS definition of software radio elements is to specify the QoS language that will be used during the modeling phase. For our purpose, it will allow the specification of a particular kind of software radio component, the fields that are relevant to quality of service and that must be filled with accurate values in the PSM model. The definition of such a QoS language specific to the A3S issues is performed using the QoSCharacteristic elements of the QoS and Fault Tolerance profile. QoSCharacteritics can be extracted directly from the catalog of well known QoSCharacteristics of the QoSProfile, but can also be defined from scratch, inherited from other QoSCharacteristics or aggregated by others. The set of QoSCharacteristics obtained by this way, is then stored in a QoSCatalog dedicated to the A3S needs. At the design time, these QoSCharacteristics will be implemented into QoSValues which will be applied to
Figure 7. Definition of the QoS characteristic of a FPGA
Figure 8. Definition of the QoS value that a specific FPGA may have
4.2. UML Modeling
During the application and platform specification steps, the designer provides the values of the software and the hardware component attributes to perform the coherency verification and schedulability analysis of the system. Each component (software and hardware) can be characterized in three parts as described in Figure 9. First part corresponds to the non-functional characteristics (attributes) of the component.
components it corresponds to the clock frequency, the type and quantity of internal/external memory. This view mainly corresponds to specification constraints.
As our approach relies on IP cores, the internal view of the component is not explicitly represented since we assume that IP cores functional behavior (C, C++, SystemC, VHDL) is validated through other means that are not in the scope of this paper. In our case attributes can be provided using the IP characteristics.
UML stereotypes permit to identify and characterize any element by assigning different parameters called
“attributes”. So each element of UML can be specialized by using different stereotypes that are used to define the component parameters.
Generic SW components which are not yet implemented have different attributes (e.g. a function is periodic or not, it has an initialization part or not) compared to a dedicated SW component which represents one implementation choice of a generic SW component. Each implementation choice adds some specific constraints that are highlighted through the non-functional attributes. They deal with function periodicity, execution time, code size, priority level if a RTOS is used, and other attributes like data/code localization, and access memory types. HW components have different stereotypes, which lead to the difference between HW processing components (DSP, ASIC, processor), memory components (FIFO, RAM, ROM), reconfigurable components (FPGA) and communication components (Bus, wire). Specific performance parameters are considered according to the hardware component (frequency, data/program memory size, port type, data width, throughput).
All the parameters are required to perform the performance analysis. They are used during the scheduling analysis step (see Figure 1), to compute resources use rates, to perform constraints verification and to check the coherency of the system.
4.3. XAPA tool for schedulability analysis
Once specification and mapping have been completed and coherency verifications have been performed (i.e. no error about HW/SW connection, all attribute settled), the A3S tool generates a XML file gathering the information about the system. The file contains the diagrams (activity, deployment), the hardware/software component allocated, and the attributes value. More precisely the UML activity
consider the corresponding method to perform period derivation [24]. This method computes the period of each task within the GTG even if some are previously unknown. The GTG nodes represent tasks (functions), and the GTG oriented edges are channels from producers (tasks) to consumers (tasks). Each task can be triggered by a data. Each edge contains producer and consumer information corresponding to data to be exchanged between functions. For applications implemented onto multi-processor, functions implementation can lead to additional communication tasks (in case of two tasks connected to each other and implemented on different hardware devices). The period derivation step is performed to compute the timing constraints (periods) that have not been settled by the designer during the specification steps. This point is important, since this kind of computation is very error prone and can be efficiently done with our tool.
The GTG obtained from the XML is then used with the HW architecture characteristics within our real time analysis tool RTDT [25]. This tool performs automatically complex scheduling verification and provides performance analysis results which help designer to drive his choices. Such automatic bridges and tools are essential to improve time to market and quality designs.
5. Real time analysis tool (RTDT)
5.1. Real time scheduling strategy 5.1.1. Task classification
Usually, real-time embedded systems require a simple and safe scheduler which can guarantee that critical aperiodic or periodic tasks meet their deadlines.
For these reasons, a static HPF (High Priority First) scheduling policy has been adopted, where the fixed priorities are computed as the inverse of the task period. The worst case response time is computed with an exact analysis [26] or is provided from the library of IPs.
In a first approach we consider two kinds of tasks.
The first category is composed of the periodic tasks that are scheduled by means of hard real time constraints (RTC), and sporadic tasks with hard RTC.
Like in [27], we consider the sporadic tasks as periodic
can be fixed by the designer. The task priority is computed as the inverse of the task period.
The question of multi-rate dependencies is solved by shifting the release time computation as detailed in [28].
5.1.2. Response time computation
The exact response time is computed iteratively with the following equation:
Where:
– HP(i): is the set of tasks with higher priority compared to task i (Ti);
– Ri: is the worst case response time of task i;
– Di: is the execution deadline for task i, – Ci: is the execution time of task i;
– Bi: is the longest time that task i can be delayed by lower priority tasks,
– Pj: is the period of task j, – Csw: is the context switching;
With:
–δ0: is the context switching overhead without any coprocessor,
–δ(k): is the overhead due to the coprocessor k.
The context switching overhead is the delay between the preemption of a given task and the activation of another task.
5.2. RTOS overhead
The difficulty is that Csw depends not only on the target processor and on the RTOS and its configuration but also on the number of tasks in the system and on the number of coprocessors. Without coprocessor, the available overhead metric is usually an average value estimated with different task sets. We have defined an accurate model for the RTOS overhead which takes into account the following parameters: initialization of the RTOS, context switching, scheduler, task, semaphore, mutex, mailbox, message queue and flag creation, and post/pend of the previous mechanisms.
Many parameters influence the model and they must be
γ corresponds to the delay due to a scheduler interrupt. The execution time of a task with an OS is thus increased based on the period of the scheduler tick and depends on the number of time a task has been preempted by the scheduler. The influence of the coprocessor is also related to the number of data and status registers.
5.3. Design space exploration for HW/SW partitioning
5.3.1. Cost function
The cost function takes into account the global area of the SoC and its energy consumption. At a high level of abstraction, only relative estimations can be used for SW and HW IPs and the cost function is used to guide the selection of a reduced set of solutions. In order to eliminate solutions, relative costs are used to evaluate the cost value for a given schedulable solution S:
with α + β = 1 and where MinArea is the schedulable solution with the minimal area without any power consideration and MinPw is the schedulable solution with the minimal power without any area consideration. Note that the area cost influences the power consumption through the static power evaluation. So, the α parameter also acts on the power optimization.
5.3.2. Area Cost
The area cost includes the data and code memory size for software implementations, the area of coprocessors that can be shared by various tasks, the area of hardware accelerators and finally the area of memories added for communications.
5.3.3. Power Cost
The model for power evaluation is much more complex. Firstly, the dynamic power consumption
( ) (
j sw)
i HP
j j
i i
i i i i
j C C
P R R
C R D R i HP
T × +
⎥⎥
⎥
⎤
⎢⎢
⎢ + ⎡ +
=
≤
∃
∈
∀ (), / ∈
∑
()∑
+
=
k
sw
k
C δ
0δ ( )
MinPw MinPw S
Pw MinArea
MinArea S
S Area
Cost = ( )− + ( )−
)
( α β
+
⎥ ×
⎢ ⎦ + ⎣
= κ γ
ler tickschedu
psexewithOS
P
⎟⎟ ⎠
⎞
⎜⎜ ⎝
⎛ ⎥ −
⎦
⎢ ⎥
⎣
× ⎢
⎥ +
⎦
⎢ ⎥
⎣
× ⎢
= 4 1
ler tickschedu
ps ler
tickschedu ps
