欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > PPT文档下载
    分享到微信 分享到微博 分享到QQ空间

    Building Unreliable Systems out of Reliable Components-The .ppt

    • 资源ID:379156       资源大小:1.06MB        全文页数:42页
    • 资源格式: PPT        下载积分:2000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要2000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    Building Unreliable Systems out of Reliable Components-The .ppt

    1、Building Unreliable Systems out of Reliable Components: The Real Time Story,Edward A. Lee Professor, Chair of EE, and Associate Chair of EECS CHESS: Center for Hybrid and Embedded Software Systems UC Berkeley,Monterey Workshop Series 2005 Theme: Workshop on Networked Systems: realization of reliable

    2、 systems on top of unreliable networked platforms September 23-25, 2005 Laguna Beach, CA,Electronics Technology Delivers Timeliness, and the overlaying abstractions discard it.,Computation in the 20th Century,f : 0,1* 0,1*,Computation in the 20th Century,initial state,final state,sequence,f : State

    3、State,Time is irrelevantAll actions are orderedNontermination is a defectConcurrency is an illusion,Alan Turing,Exploiting the 20th Century Abstraction,Programming languages Debuggers Virtual memory Caches Dynamic dispatch Speculative execution Power management (voltage scaling) Memory management (g

    4、arbage collection) Just-in-time (JIT) compilation Multitasking (threads and processes) Networking (TCP) Theory (complexity),What about timeliness?,Moores law has saved us!,In Core Software Abstractions: Real-Time is Not,Time is not in the semantics of programs. Have to step outside the semantics to

    5、specify timing.Timing is a consequence of implementation not a property of design. Measured on the bench For a particular realizationResulting systems are brittle. Small changes have big consequences Ports to new platforms require redesign,The Myth of WCET Worst-Case Execution Time,True WCET can be

    6、thousands of times bigger than actual execution time.In many implementations, true WCET is not a useful number.Dubious WCET is what is actually used.Correctness of even safety-critical systems depends on WCET being correct.,What is Done in Practice,Real-time systems are boxes, not software services.

    7、Critical real-time systems use idiosyncratic, non-mainstream processors (like DSPs).Designs are bench tested, then encased.,APOT,The question: What would have to change to achieve absolutely, positively on time (APOT)?The answer: nearly everything.,What to do?,Put time into programming languages Pro

    8、mising start: Simulink, Giotto, Discrete-event models Rethink the OS/programming language split Promising start: TinyOS/nesC Rethink the hardware/software split Promising start: FPGAs with programmable cores Memory hierarchy with predictability Promising start: Scratchpad memories vs. caches Memory

    9、management with predictability Promising start: Bounded pause time garbage collection Predictable, controllable deep pipelines Promising start: Pipeline interleaving + stream-oriented languages Predictable, controllable, understandable concurrency Promising start: Synchronous languages, SCADE Networ

    10、ks with timing Promising start: Time triggered architectures, time synchronization Computational dynamical systems theory Promising start: Hybrid systems,Recall: Computation in the 20th Century,f : 0,1* 0,1*,Computation in the 21st Century,f : T 0,1*P T 0,1*P,We Need Component and Composition Models

    11、 with Time and Concurrency,Stuff happens to objects,Actors make things happen,The First (?) Actor-Oriented Platform The On-Line Graphical Specification of Computer Procedures W. R. Sutherland, Ph.D. Thesis, MIT, 1966,MIT Lincoln Labs TX-2 Computer,Bert Sutherland with a light pen,Partially construct

    12、ed actor-oriented model with a class definition (top) and instance (below).,Bert Sutherland used the first acknowledged object-oriented framework (Sketchpad, created by his brother, Ivan Sutherland) to create the first actor-oriented programming framework.,Your Speaker in 1966,Modern Examples of Act

    13、or-Oriented Platforms,Simulink (The MathWorks) LabVIEW (National Instruments) Modelica (Linkoping) OPNET (Opnet Technologies) Giotto and xGiotto (UC Berkeley) Polis & Metropolis (UC Berkeley) Gabriel, Ptolemy, and Ptolemy II (UC Berkeley) OCP, open control platform (Boeing) GME, actor-oriented meta-

    14、modeling (Vanderbilt) SPW, signal processing worksystem (Cadence) System studio (Synopsys) ROOM, real-time object-oriented modeling (Rational) Easy5 (Boeing) Port-based objects (U of Maryland) I/O automata (MIT) VHDL, Verilog, SystemC (Various) ,Ptolemy II: Our Laboratory for Actor-Oriented Models o

    15、f Computation,Concurrency management supporting dynamic model structure.,Models of Computation Implemented in Ptolemy II,CI Push/pull component interaction Click Push/pull with method invocation CSP concurrent threads with rendezvous CT continuous-time modeling DE discrete-event systems DDE distribu

    16、ted discrete events DDF Dynamic dataflow DPN distributed process networks DT discrete time (cycle driven) FSM finite state machines Giotto synchronous periodic GR 2-D and 3-D graphics PN process networks SDF synchronous dataflow SR synchronous/reactive TM timed multitasking,Most of these are actor o

    17、riented.,A Start on a 21st Century Theory of Computation: The Tagged Signal Model,Lee & Sangiovanni-Vincentelli, 1998A set of values V and a set of tags T An event is e T V A signal s is a set of events. I.e. s T V A functional signal is a (partial) function s: T V The set of all signals S = 2T V Re

    18、lated models: Interaction Categories Abramsky, 1995 Interaction Semantics Talcott, 1996 Abstract Behavioral Types Arbab, 2005,Actors, Ports, and Behaviors,An actor has a set of ports PA behavior is a function : PA SAn actor is a set of behaviors A PA S = S PA,PA = p1, p2, p3, p4 ,Actor Composition,C

    19、omposition is simple intersection (of sets of functions),P1 = p1, p2,P2 = p3, p4,P = P1 P2,Connectors,Connectors are trivial actors.,P1 = p1, p2,P2 = p3, p4,Pc = p2, p3,c,A,Tagged Signal Model Gives a Fixed-Point Semantics to Arbitrary Composition,Tagged Signal Model can be used on a Wide Variety of

    20、 Concurrent and Timed Models of Computation,CSP concurrent threads with rendezvous CT continuous-time modeling DE discrete-event systems DDF Dynamic dataflow DT discrete time Giotto synchronous periodic PN process networks SDF synchronous dataflow SR synchronous/reactive,Application of this Theory o

    21、f Computation: Discrete-Event Systems,CI Push/pull component interaction Click Push/pull with method invocation CSP concurrent threads with rendezvous CT continuous-time modeling DE discrete-event systems DDE distributed discrete events DDF Dynamic dataflow DPN distributed process networks DT discre

    22、te time (cycle driven) FSM finite state machines Giotto synchronous periodic GR 2-D and 3-D graphics PN process networks SDF synchronous dataflow SR synchronous/reactive TM timed multitasking,Discrete Events (DE): A Timed Concurrent Model of Computation,Event source,Time line,Reactive actors,Signal,

    23、Semantics Clears Up Subtleties: Simultaneous Events,By default, an actor produces events with the same time as the input event. But in this example, we expect (and need) for the BooleanSwitch to “see” the output of the Bernoulli in the same “firing” where it sees the event from the PoissonClock. Eve

    24、nts with identical time stamps are also ordered, and reactions to such events follow data precedence order.,Semantics Clears Up Subtleties: Feedback,Data precedence analysis has to take into account the non-strictness of this actor (that an output can be produced despite the lack of an input).,Seman

    25、tics Clears Up Subtleties: Zeno Systems,DE systems may have an infinite number of events in a finite amount of time. Carefully constructed semantics gives these systems meaning.,Example of Current Research Challenges,Use distributed discrete-event systems as a timed model of computation for embedded

    26、 software in unreliable, sporadically connected networks, such as wireless sensor networks.The most interesting possibilities are based on distributed consensus algorithms (as in Croquet, Reed, Lamport).Research challenges include:Defining the semanticsCombining the semantics heterogeneously with ot

    27、hers. E.g.: Signal processing for channel modeling TinyOS for node functionalityCreating efficient runtime environmentsBuilding the design environment,Application of this Theory of Computation: Hybrid Systems,CI Push/pull component interaction Click Push/pull with method invocation CSP concurrent th

    28、reads with rendezvous CT continuous-time modeling DE discrete-event systems DDE distributed discrete events DDF Dynamic dataflow DPN distributed process networks DT discrete time (cycle driven) FSM finite state machines Giotto synchronous periodic GR 2-D and 3-D graphics PN process networks SDF sync

    29、hronous dataflow SR synchronous/reactive TM timed multitasking,Standard Model for Continuous-Time Signals,The usual formulation of the signals of interest is a function from the time line T (a connected subset of the reals) to the reals:Such signals are continuous at t T if (e.g.):,Piecewise Continu

    30、ous Signals,In hybrid systems of interest, signals have discontinuities.Piecewise continuous signals are continuous at all t T D where D T is a discrete set.11A set D with an order relation is a discrete set if there exists an order embedding to the integers.,Operational Semantics of Hybrid Systems,

    31、A computer execution of a hybrid system is constrained to provide values on a discrete set:Given this constraint, choosing T as the domain of these functions is an unfortunate choice. It makes it impossible to unambiguously represent discontinuities.,Definition: Continuously Evolving Signal,Change t

    32、he domain of the function:Where T is a connected subset of the reals and is the set of natural numbers.At each time t T , the signal x has a sequence of values. Where the signal is continuous, all the values are the same. Where is discontinuous, it has multiple values.,Simple Example: Hysteresis,Thi

    33、s model shows the use of a two-state FSM to model hysteresis. Semantically, the output of the ModalModel block is discontinuous. If transitions take zero time, this is modeled as a signal that has two values at the same time, and in a particular order.,Signals Must Have Multiple Values at the Time o

    34、f a Discontinuity,Discontinuities need to be semantically distinguishable from rapid continuous changes.,Initial and Final Value Signals,A signal has no chattering Zeno condition if there is an integer m 0 such thatA non-chattering signal has a corresponding final value signal, where It also has an

    35、initial value signal where,Piecewise Continuous Signals,A piecewise continuous signal is a non-chattering signalwhere The initial signal xi is continuous on the left, The final signal xf is continuous on the right, and The signal x has only one value at all t T D where D T is a discrete set.,Our Cur

    36、rent Projects,Abstract semantics (Cataldo, Liu, Matsikoudis, Zheng) Behavioral polymorphism Actor semantics (prefire, fire, postfire) Compositional directors Time semantics Causality interfaces Distributed computing (Feng, Zhao) Robust distributed consensus Data coherence (distributed caches) Time s

    37、ynchronization Real-time software (Bandyopadhyay, Cheong, Zhou) Time-based models vs. dataflow models Deterministic, understandable multitasking Memory hierarchy with scratchpad memory Code generation Hybrid systems (Cataldo, Zheng) Operational semantics Stochastic hybrid systems Aspect-oriented multi-view modeling Code generation,Conclusion,The time is right to create the 21-st century theory of (embedded) computing.,


    注意事项

    本文(Building Unreliable Systems out of Reliable Components-The .ppt)为本站会员(eveningprove235)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开