System Specification 하순회 (서울대학교, 컴퓨터공학부) Copyrightⓒ2003.

Presentation on theme: "System Specification 하순회 (서울대학교, 컴퓨터공학부) Copyrightⓒ2003."— Presentation transcript:

1 System Specification 하순회 (서울대학교, 컴퓨터공학부) Copyrightⓒ2003

2 과목 개요(Learning Map) Copyrightⓒ2003

3 (모듈4) System Specification
학습 목표 SoC로 구현할 시스템의 Behavior를 명세하는 방법에 따라 SoC 설계 과정이 어떻게 영향을 받는지를 알아본다. 상용의 시스템 설계 도구와 시스템의 여러 명세 방법의 연관성에 대하여 이해하도록 한다. 선수지식 논리설계 C, VHDL 언어 Copyrightⓒ2003

4 목차 Introduction Types of specification
Formal models of computation for a single task Task level specification Copyrightⓒ2003

5 SoC Specification Document-based specification
Performance requirements Real-time constraints Hard real-time: deadline may not be violated – reactive system Soft real-time: deadline violation is somewhat tolerable. It is a QoS (Quality of service) metric. – interactive system Non real-time: there is no deadline – batch system Design Constraints Cost(Area) constraints Power constraints System Structure Executable specification Precise behavior specification Task specification Inter-task dependency in a multi-task system Precise behavior description Focus of this module Copyrightⓒ2003

6 Adhoc (but Current) Design Practice
prototype Matlab, C Debugging, optimization System specification Architecture decision by experts Prototyping test High cost & inefficient design loop Functional simulation C VHDL, Verilog Software development HW development ECAD tools SW development tools Initial system specification is for functional simulation only. Different specification is used for HW and SW development. Copyrightⓒ2003

7 Problems of Adhoc Methodology
Long design time Debugging becomes more difficult as system complexity increases Manual decision of optimal system architecture Past experience, simple profiling technique time Arch. decision HW prototyping Application SW dev. SW porting/debugging Copyrightⓒ2003

8 HW/SW Codesign: Systematic Design
Concurrent design of HW/SW components Evaluate the effect of a design decision at early stage by “virtual prototyping”. Explore the design space in a systematic way. time time HW SW Integration HW/SW codesign iteration HW codesign 방법론의 개념에서 가장 중요한 두가지를 복습한다. 하드웨어를 직접 만들기 전에 Virtual prototyping (co-simulation) 에 의하여 성능 평가를 한다. 시스템의 최적의 구조와 하드웨어/소프트웨어 분할등을 결정하는 것을 설계공간 탐색이라고 하는데, 설계공간 탐색을 체계적으로 한다. 우측의 그림이 좌측과 다른 점은, 1. HW/SW를 통합하여 성능을 평가하는 시간이 단축된 것과 2. 설계 가격이 줄어들도록 Design space exploration 을 위한 iteration 을 수행한 것이다. 이 경우, 초기 설계가 지나치게 over-design 한 것을 가정하고 그림으로 보였다. HW SW HW SW Integration cost cost Copyrightⓒ2003

9 Design Space Exploration by Mapping
System Function System Microarchitecture Architecture selection Platform selection Algorithm development - Functional Simulation mapping HW/SW partitioning Function on Microarchitecture Architecture fine-tuning 설계가 이루어지는 과정에서 어떻게 설계공간 탐색을 체계적으로 할 수 있는가를 보면 시스템의 기능(function)과 시스템의 아키텍쳐를 구별하여 명세를 하고 그 둘 사이의 mapping 과정을 통하여 HW/SW 분할을 하도록 하는 것이 바람직하다. [참고문헌 1: orthogonalization of function and architecture] 이 모듈의 주제는 어떻게 시스템의 기능을 명세하는가에 관한 것이다. 시스템의 기능을 명세하는 방법에 따라 시스템의 설계과정, 특히 설계공간탐색 과정이 달라지게 된다. HW/SW coverification Refine HW/SW /Interface synthesis Implementation of system Copyrightⓒ2003

10 Where to start? System Level Specification Issues
How to specify the system functionality? Issues User friendliness Executable / simulatable Implementation Independence Design validation / error detection capability Design Maintenance and collaboration Well defined path to synthesis 바람직한 시스템의 기능 명세 방법을 생각해 보자. 모든 항목이 다 중요하다고 할 수 있다. 하지만, 그중에서 강조하고 싶은것은 아직 이 단계에서는 시스템의 아키텍쳐가 결정이 되지 않았든지, 혹은 아키텍쳐가 결정이 되었다고 하더라도 HW/SW partitioning 결정이 나지 않은 상태라는 것이다. 그렇다면 명세는 Implementation independent 한 것이 좋다. 그리고, 시스템의 기능이 복잡할 수록 초기 설계시간 보다 debugging 시간이 더 오래 걸린다. 그래서, design validation/ early error detection 의 중요성이 더 커지고 있다. 이 두가지 점을 특별히 강조한다. Copyrightⓒ2003

11 Motivational Example VOD example Multi-task
Signal processing + control function Hardware + software parts UI Control control Network QoS Client Layer Internet data Packet Decoder Audio Video 궇현하고자 하는 시스템의 예로 VOD 시스템을 생각해 보자. 이 시스템은 그림과 같이 논리적인 6개의 태스크로 구성된다. 노란색으로 표현된 태스크들은 네트웍으로부터 데이터 샘플을 받아서 화면으로 출력하기 까지 필요한 신호 처리 태스크들이고, 푸른색으로 표현된 태스크들은 사용자의 명령이나 시스템의 상태에 따라 신호처리 태스크들의 동작을 제어하는 제어 태스크들이다. 이 시스템이 어떻게 구현될 지는 아직 결정되지 않았지만, 계산량이 많은 Video decoder 와 같은 태스크는 하드웨어와 소프트웨어로 나뉘어 구현될 것이다. 이 예제를 어떻게 표현하면 좋을지 생각해 보자. Copyrightⓒ2003

12 목차 Introduction Types of specification
Formal models of computation for a single task Task level specification Copyrightⓒ2003

13 Types of Specification
Language based approach 시스템의 기능을 잘 알려진 프로그래밍 언어(C나 VHDL)을 이용하여 기술한다. 잘 알려진 알고리즘을 간단한 구조의 시스템으로 구현하고자 할 때 효과적이다. Formal modeling approach 시스템의 기능을 Formal model of computation 을 이용하여 기술한다. 2가지 방법으로 대별을 할 수 있다. Language-based approach 와 formal modeling approach Formal model of computation 에 대하서는 뒤에서 설명을 한다. Copyrightⓒ2003

14 Example: Language Based Approach
신호 처리 태스크와 제어 태스크의 구별이 없다. 각 태스크가 수행되는 조건은 코드에 정의된다 (예를 들면) Network Layer 태스크는 입력 데이터가 들어오면 수행된다. Packet decoder 는 Buffer 조건에 따라 수행여부를 결정한다. Audio, video decoder 태스크는 일정한 주기를 가지고 수행된다 (실시간적인 특성) Simulation으로 전체 성능을 검증한다. UI Control control Network QoS Client Layer Internet data Packet Decoder Audio Video Copyrightⓒ2003

15 (Informal) Programming in C, C++?
Not Good For Initial Specification. Why? Imperative Language: not easy to exploit concurrency Not good for HW implementation Simulation based verification Not easy to detect semantic error Not easy to debug and maintain the code Code reuse is difficult Not easy to cooperate with others Productivity is low Executable한 시스템의 기능 명세로 가장 널리 쓰이고 있으며 사람들이 선호하는 방법은 C 언어로 프로그래밍하는 것이다. 예를 들어 H.264 알고리즘의 경우 C 코드로 reference 코드가 주어진다. 이 코드로 부터 알고리즘의 기능은 검증이 되지만…. 시스템 설계는 어렵다. 왜? CPU core 를 여러 개 사용하는 경우, 어떻게 병렬화 시켜야 하는지, 그리고 어느 부분을 하드웨어 IP 를 사용하여야 하는지 결정하기 어렵다. 코드자체를 이해하고 수정하기 어렵다. 그래서, 협력작업이 어렵다. 처음부터 C 코드를 작성하여 명세를 하는 경우, 바른 코드를 만들기가 어렵다. Semantic error 찾기가 어렵다. 코드 재사용이 어렵다. 등등…. 결국 설계생산성이 매우 떨어질 것으로 예상된다. (주의할 것: 우리가 장차 설계할 SoC 는 결코 간단한 시스템이 아니다. 복잡한 시스템일 수록 위의 단점들은 더 부각될 것이다, 지금은 감당할 수 있을지 몰라도….) -> 결론: 정형적인 계산 모델을 사용하는 것이 주목을 받고 있다. Need of Formal Model of Computation Copyrightⓒ2003

16 Review: System Level Design
Design Methodology: Top Down Aspect: Orthogonalization of Concerns: Separate Implementation from Conceptual Aspects Separate computation from communication Formalization: precise unambiguous semantics Abstraction: capture the desired system details (do not overspecify) Decomposition: partitioning the system behavior into simpler behaviors Successive Refinements: refine the abstraction level down to the implementation by filling in details and passing constraints Bottom Up Aspect: IP Re-use (even at the algorithmic and functional level) Components of architecture from pre-existing library Copyrightⓒ2003

17 Formal Specification Model
(비교) CASE tool for software design is getting popular Coding rule for design maintenance and easy debugging Software design is a subset of system design Precise and unambiguous semantics Functional specification: f (input, output, state) Well defined function composition Properties and Constraints 정형적인 명세라고 하면 막연한 거부감이 있는 것이 사실이다. (Engineer 는 자기가 익숙한 것에 과도한 집착이 있고, 새로운 방법을 배우길 싫어한다!) 한가지 추세: 최근에는 소프트웨어를 개발하는 사람도 규칙을 따르며 코딩을 하는 유익을 알고 있다. 정형적인 명세란 특별히 어려운 것이 아니다. 시스템의 기능을 함수(혹은 기능블록, 모듈, 액터)로 나누어 기술한다: structured design (2) 그림에서와 같이 기능블록(짧게, 블록)들 간에는 포트를 통해 서로 연결이 되어 있다. (3) 각 기능블록이 언제 수행되는지, 기능블록들 간에 데이터는 어떻게 전달되는지 등에 대한 규칙이 있다. 그리고, 이 시스템 전체가 만족시켜야 하는 제약 조건들이 명시된다. (3)의 조건에 따라 다양한 계산 모델이 존재한다. port f() g() Module or actor (function) Copyrightⓒ2003

18 Formal Specification Inside a Function (or module, actor)
Its behavior is written in a popular programming language: C, VHDL, Verilog Function is a reusable module. IP is naturally regarded as a reusable module Formal model is a coordination language between functions Formal specification determines when to execute the functions and how to communication data between functions. Formal model itself can be written in a programming language such as C, C++, and SystemC Copyrightⓒ2003

19 Formal Specification Models
Process-based specification A module is a task, also a partitioning unit Signal processing task should be partitioned manually into smaller sub tasks (ex) Kahn Process Network, CSP (Communicating Sequential Processes) Application specific specification Control oriented application: FSM Signal processing application: Dataflow Network simulation: Discrete event (for simulation) Synchronous/reactive, PDE, etc Formal model은 다음과 같이 분류된다. Process-based model 은 기능블록이 하나의 독립적인 프로세스로 구현되는 것을 가정하는 모델이다. Kahn process network 이나 CSP 등이 널리 알려진 process network 모델이다. 반면에, 특정 응용에 특화된 모델들이 개발되어 왔다. 제어응용에는 FSM 모델에 기초한 모델들, DSP 응용에는 Dataflow 모델 그리고, 네트웍 시뮬레이션 용에는 Discrete event model, 하드웨어 설계에는 SR (Synchronous/Reactive) model 등이 있다. 이들 중 몇가지에 대하여는 뒤에서 설명하도록 한다. Copyrightⓒ2003

20 Advantages of Formal Specification
Amenable to property validation, simulation, and analysis by computers Top-down refinement from specification to implementation Design reuse and maintenance IP can be regarded as a function block and reused. Described what to do: design space exploration Productivity is high Formal model 을 써서 명세를 하면 다음과 같은 장점들이 있다. Formal model 을 쓰면 얻는 가장 큰 장점은 static analysis 를 통해서 시스템의 특성을 분석할 수 있다는 점이다. 예를 들어 deadlock 발생 가능성이나 buffer overflow 와 같은 에러를 모델링 단계에게 검증이 가능하다는 점이다. 그리고, formal model 이 가지고 있는 규칙을 준수하도록 시스템을 구현을 할 수 있으며 그럴 경우, 설계의 검증에 사용되는 시간이 훨씬 줄어든다. 또한, 규칙을 이해하는 사용자가 그 명세를 보면 시스템의 기능을 정확하게 이해할 수 있으므로 설계의 재사용성이나 유지, 보수가 쉬워진다. 그런데… 왜 formal model 들이 잘 사용되지 않는가? 장점들에도 불구하고 formal model 을 사용하기 어려운 점들이 존재하기 때문이다. 다음 슬라이드를 본다. Copyrightⓒ2003

21 Weaknesses of Formal Specification
Barrier to learn a new rule of specification will be overcome if benefit is large (ex: CASE tools) Limited expression capability Can express all system behaviors (specially for dynamic behavior)? Inefficient synthesis result Performance comparison with manually designed (optimized) result Current status There exist some tools for a specialized set of applications. There exist tools for co-simulation, but not for co-synthesis yet. Formal model 에 대한 거부감이 있다. 그리고, formal model 은 규칙이 있는데, 그 규칙으로 표현하지 못하는 시스템의 behavior 가 있다. 예를 들어 dataflow 모델을 사용해서는 시스템의 동적 기능변화를 표현하기 어렵다. 또한 구현된 시스템이 formal model 의 규칙을 만족시키는 경우, 시스템의 성능이 떨어지는 단점이 있다. 규칙을 지키기 위한 오버헤드가 클 수 있다는 점이다. 그래서, 지금까지 일부 응용에서만 사용되어 왔다. 그러나, 최근들어 이러한 단점들이 극복되는 연구결과가 나오고 있고, formal model 을 사용하는 장점이 부각되고 있어서 formal model 에 기반한 설계도구들이 개발되고 있다. Copyrightⓒ2003

22 Formal Model에 기반한 설계도구들
FSM model STATEMATE (statechart), POLIS (CFSM) Dataflow model SPW(CoWare), COSSAP(Synopysis) Kahn Process Network model COSY (YAPI) Heterogeneous approach: mixture of several formal models Ptolemy II: hierarchical composition Cocentric System Studio: FSM + Dataflow in algorithm simulation PeaCE 어느 설계 도구든지 초기 명세가 어떻게 주어지는가에 따라 그 설계도구가 수행하는 기능의 범위를 예측할 수 있다. Copyrightⓒ2003

23 목차 Introduction Types of specification
Formal models of computation for a single task Task level specification Copyrightⓒ2003

24 FSM Well-known semantics Rich analytical properties
Reachability analysis, liveness System Under Design power_on init on done error power_on/timer time-out a timer a time-out 먼저 제어 태스크를 명세하는 Formal model로 널리 쓰이는 FSM 을 살펴보도록 한다. FSM은 Digital Logic 에서 Sequential logic을 설계하기 위한 표현으로 널리 알려져 있다. 블록은 시스템의 상태를 나타내고, arc 는 입력 이벤트에 대한 상태의 천이를 나타낸다. FSM 은 정적인 분석을 통하여 시스템의 여러 특성들을 검증할 수 있다. Copyrightⓒ2003

25 Problems of Pure FSMs Flat and and unstructured Inherently sequential
very large number of states and transitions representation and analysis become difficult Harel’s extension (1) hierarchy (OR decomposition) (2) Concurrency (AND decomposition) FSM 모델의 가장 큰 단점은 너무 복잡하고 이해하기 어렵다는 것이다. 그러나, Harel 이라는 사람이 제안한 2가지 확장에 의하여 그 효용성이 크게 증대되었다. Harel 은 statechart 라는 모델을 제안하였는데, 그것은 FSM model 에 hierarchy 와 concurrency를 추가한 것이다. Copyrightⓒ2003

26 FSM Hierarchy a B A BC BD a c/u A C D b/v
b’c/u c/u A C D b/v Structural description: does not reduce the number of states Does reduce the number of transitions What happens when input c and b both exist in state C? (one solution) external FSM take actions first. B 라는 super state는 FSM sub-graph 를 내포하고 있다. 예를 들어, A는 시스템이 off 인 상태이고 B 는 시스템이 on 인 상태라고 하자. 시스템이 on 인 상태 중에서 run 상태 (C) 와 idle 상태 (D)가 나뉠 수 있다. 이와 같은 계층적 FSM 모델이 모호성이 있는데 이러한 모호성을 해결해 주어야 한다. 즉, 상태 C에 있을때 입력 이벤트 b,c 가 동시에 들어오면 어떤 출력을 내야 하는가가 정의되어야 한다. 왼쪽의 hierarchical 한 FSM 은 우측의 flat 한 FSM으로 변환 가능하다. Copyrightⓒ2003

27 AND Decomposition ac’ Concurrent execution of multiple FSMs
BC AD BD ac’ bc’ a b a’c b’c bc ac A B b c C D Concurrent execution of multiple FSMs Solve state explosion problem How to support inter-FSM communication? Internal events 두개의 FSM 이 동시에 수행되는 것과 같은 concurrency 를 AND decomposition 으로 표현하였다. 이것을 flat FSM 으로 표현하면 우측과 같이 복잡해 진다. 시스템을 구성하는 component 들이 각각 별도의 FSM 모델로 표현되고 그 둘 사이에 event 를 가지고 정보를 교환하는 표현을 허용함으로써 복잡한 시스템의 명세 가능성을 획기적으로 높혔다. Copyrightⓒ2003

28 Example : Traffic Light
concurrency hierarchy 이 그림은 hierarchy 와 concurrency 를 가진 FSM표현으로 신호등의 동작을 명세한 것이다. 위의 3신호는 차량용 신호이고 아래의 2신호는 보행자 신호이다. 신호 변경 전에 깜빡거리는 것 까지 모델을 하였다. 이렇게 16개의 state로 표현된 FSM 을 만약 flat 한 FSM 으로 표현한다면 192개의 state 가 필요하다고 한다. Copyrightⓒ2003

29 iLogix’s STATEMATE Control-oriented reactive applications
Conceptual model FUNCTIONALITY functional decomposition & information flow BEHAVIOR control and temporal relation activity chart statechart STATEMATE 에서는 시스템의 명세를 3가지 chart 로 나누어 기술한다. statechart 는 시스템의 control behavior 를 명세하고, activity chart 는 시스템의 processing 을 명세하고 module chart 는 시스템의 실제 architecture 를 명세한다. STRUCTURE physical decomposition module chart Copyrightⓒ2003

30 Harel’s Statechart Hierarchy, AND decomposition, reset states
D.Harel, “Statecharts: A visual formalism for complex systems”, Science of Computer Programming, Vol. 8, pp , 1987. Hierarchy, AND decomposition, reset states Transitions are NOT level restricted. Perfect synchrony hypothesis A B C D E x y z w F G H u 이 그림은 statechart 의 간단한 예이다. 계층성과 병렬성을 관찰할 수 있다. 점과 연결된 state 는 super state 로 변경될 때에 초기 상태를 표현한다. 이를 reset state 라고 한다. 여기서의 특징은 G->H 로서 transition 이다. Boundary 를 거치는 것과 그렇지 않은 것과의 차이가 있다. 표현력을 높이는 대신 compositionability를 희생하였다. 이와 같은 statechart 로 제어태스크의 내부를 명세한다. Perfect synchronoy hypothesis 란 state transition 이 일어나는데 시간이 걸리지 않는다는 가정이다. 즉 State transition 시간이 0 이다. Copyrightⓒ2003

31 Activity chart 3 types of objects 2 types of arcs
Statechart inside 3 types of objects transformation data-store control activity (content: Statechart) 2 types of arcs dataflow: solid line control flow: dashed line connection between activity chart and statechart transition labeling (ex) forms language C T D Activity chart는 태스크들의 간의 연결관계를 명세한다. 우측에서 푸른 태스크는 제어 태스크를 나타나고 노란 태스크는 신호처리 태스크 (transformation)를 의미한다. 제어 태스크의 속은 statechart 로 명세된다. 신호처리 태스크의 내부를 어떻게 표현하는지는 여러 가능성이 있다. 점선으로 표현된 것은 태스크가 아니라 data-store 이다. 2종류의 arc가 있는데 solid line 은 데이터가 전달되는 것을 표현하고 점선은 control 정도만 전달된다. 아래의 S1->S2 의 그래프는 statechart 에서의 transition 을 나타낸다고 하자. 그 transition 이 발생할 때 suspend(T) 라는 스크립트가 수행되면 activity chart 에서 명세된 T 태스크가 Suspend 된다는 것을 의미한다. 이와 같이 statechart 와 activity chart를 이용하면 VOD 예제 시스템을 명세할 수 있다. statechart /suspend(T) S1 S2 Copyrightⓒ2003

32 POLIS: Codesign FSM Politecnico di Torino, Italy and U.C.Berkeley CAD group -Alberto Sangiovanni-Vincentelli et. al. CFSM Formal model as an intermediate representation during the system design process. (relatively small real-time control systems) Front-end specification: Esterel, StateCharts, a subset of VHDL Low level enough to be efficiently co-synthesized. a network of interacting FSMs FSMs communicate through “events” broadcast communication model each computing element takes a non-zero unbounded time Codesign FSM도 concurrent FSM 을 지원하는데, AND composition 을 사용하는 것이 아니라, FSM network 을 구성한다는 면에서 차이가 있다. 또 state Copyrightⓒ2003

33 CFSM Example Five seconds after the key is turned on, if the belt has not been fastened, an alarm will beep for ten seconds or until the key is turned off. *TICK WAIT OFF ALARM *KEY=OFF or *BELT = ON => *END = 5 => *ALARM = ON *KEY=ON => *START *END = 10 or *BELT = ON or *KEY = OFF => *ALARM = OFF Timer FSM *START *END Copyrightⓒ2003

34 Synchronous Dataflow 1 1 1 1 2 enabled fired 2 1 enabled fired
UPSAMPLE 1 1 UPSAMPLE 1 2 enabled fired 2 DOWNSAMPLE 이제 신호 처리 태스크를 표현하는데 가장 널리 쓰인 데이터 플로우 모델을 생각해 보도록 하자. 각 노드가 수행되는 조건은 모든 입력 포트에 정해진 개수의 데이터가 존재할 때이다. 각 포트마다 한개씩의 데이터를 소비하고 생성하는 것이 homogeneous dataflow 라고 하고 일반적으로 알려진 dataflow 인데, 한 개 이상의 데이터를 소비하거나 생성할 수 있도록 하는 모델을 synchronous dataflow 라고 한다. 각 arc는 unbounded FIFO 로 구성되었다고 가정한다. 각 노드를 C 프로그램에서 한 함수라고 가정하자. 그리고 포트를 입력 argument 라고 하면, 이 모델은 다음과 같이 해석된다. 함수의 입력인자가 모두 주어질 경우에만 함수가 수행되는 것이다. 이러한 제약은 이미 C 프로그램에서 사용되는 제약이므로 이 모델을 사용하여 프로그램을 하는 것은 intuitive 하다. 이와 같이 formal model 은 각 노드가 수행되는 조건, 그리고 arc 의 구성을 정의함으로 구별된다. DOWNSAMPLE 1 enabled fired Copyrightⓒ2003

35 Synchronous Dataflow Model
Useful to describe Multi-rate DSP algorithms A node represents a function block (ex: FIR, DCT) An arc represents the data dependency (FIFO queue) A block is fireable (executable when it receives all required number of input samples) Statically scheduled at compile-time. A B C D 2 1 1 2 1 1 SDF 모델을 사용하면 기능블록 간의 partial order (true dependency) 만이 표현되어 병렬적으로 수행 가능한 노드들을 쉽게 구별할 수 있다, 그리고 노드간에 전달되는 샘플의 개수를 통하여 노드들간의 수행횟수를 비를 결정할 수 있다. 예를 들어 노드 A 는 노드 B 보다 2배 더 많이 수행되어야 한다. 왜냐하면 노드 A 는 한번 수행할 때에 한 개의 샘플을 생성하고 노드 B는 한번 수행에 2개의 샘플을 소비하기 때문이다. 또한 노드들의 수행순서를 정할 수 있는데 이를 schedule 이라고 한다. 동일한 그래프에 대하여 여러 스케쥴을 정할 수 있으며 가장 좋은 스케쥴을 찾는 것이 중요하다. 스케쥴이 정해지면 각 arc 에 쌓이는 샘플의 최대치를 결정할 수 있고 그것이 이 알고리즘을 구현할 때에 필요한 buffer size 가 된다. Schedule: A-C-A-C-B-D Buffer size: AB(2), AC(1), CD(2), BD(1) Copyrightⓒ2003

36 Example: H.263 Encoder Delay – initial sample Motion Estimation
Distributor Macro Block Encoding Variable Length Coding Decoding Compensation Write To Device Read From 1 99 H.263 encoder 알고리즘을 간략한 SDF 모델로 표현한 예이다. 이 모델을 이용하면 알고리즘의 구성을 누구나 쉽게 이해할 수 있지 않은가? 이와 같이 VOD 예제에서 필요한 audio decoder 나 video decoder 등은 SDF 모델로 쉽게 표현될 수 있다. 이 모델에서 주의할 점은 delay 이다 Motion Estimation 노드가 초기에 수행될려면 feedback arc 에 초기 데이터가 존재하여야 한다. 이를 SDF 모델에서는 delay 로 표현하며 initial sample 로 해석한다. Delay – initial sample Copyrightⓒ2003

37 SDF Scheduling 2 3 2 1 A B C repetition counts
Valid schedules are not unique because the graph describes the partial order (true dependency) between blocks (ex) AABCCABCC – schedule for minimum buffer size (3A)(2(B(2C))) – schedule with loop structure What is the best schedule? Depends on the design objectives (informal) programming describes just one schedule – no guarantee of optimality ! 이 슬라이드는 SDF scheduling의 예를 보인 것이다. 각 노드들의 수행횟수의 비를 repetition counts 라고 한다. 그리고 이 그래프의 노드 수행 순서는 여러가지이며 가장 좋은 schedule 은 design objective 에 따라 다르다. Copyrightⓒ2003

38 Syntax check Sample rate inconsistency Deadlock 1 B A 2 C
Some arc accumulates tokens without bound Deadlock Graph can not start its execution A B C 1 2 SDF model 은 정적인 분석을 통하여 buffer overflow 의 경우나 deadlock 을 찾아낼 수 있다. Copyrightⓒ2003

39 SDF Limitations Expression Capability Efficiency Problem
SDF model can not express control structures (dynamic constructs) such as conditional execution and data dependent iteration Efficiency Problem SDF model does not allow shared memory (global states) between blocks due to side effect. SDF model does not allow pointer operation, but copies structured data as a token. 이와 같은 장점때문에 SDF model은 특정한 범주에 속하는 DSP algorithm 을 표현하는데 널리 사용되어 왔다. 그러나, 중요한 단점이 있는데, 첫째는 동적 구문을 표현하지 못한다는 점이고 둘째는 SDF model 이 resource sharing 을 표현하지 못하기 때문에 SDF model 을 따르는 implementation 의 경우 resource 가 많이 필요하고 성능이 최적화되지 못한다. Copyrightⓒ2003

40 목차 Introduction Types of specification
Formal models of computation for a single task Task level specification 이제는 태스크 수준에서 명세를 하는 경우의 정형적인 명세방법을 알아보도록 하자. Copyrightⓒ2003

41 Kahn Process Networks A process is a mapping from input sequences to output sequences. Blocking read, non-blocking write Concurrent processes communicate only through one-way FIFO channels with unbounded capacity. B A Determinate: independent of execution order of A and B Process network 들은 하나의 노드를 process 로 간주하고 각 프로세스들간에 어떻게 통신이 이루어지는 지를 규정한다. SoC 설계를 위한 설계 도구 개발을 위해 가장 널리 사용되는 process model 이 Kahn process model 이다. 이 모델의 특징을 푸른 글씨로 강조하였다. 중요한 성질이 바로 blocking read 라는 점이다, 이 모델을 사용하여 시스템을 기술하면 각 프로세스의 동작 속도나 순서에 관계없이 수행 결과가 동일하다는 것이다. 이와 같은 “determinate execution” 은 시스템의 검증을 위해 매우 유용한 성질이다., { read AC read BC } D C Copyrightⓒ2003

42 Design Framework : COSY
IP-based real-time design methodology YAPI: extension of the Kahn process network model Kahn process network + “select” operation coarse grain mix-and-match of several IP blocks User Control control path control path control path VOD 예제를 이와 같은 process network 으로 표현하는 예를 나타내었다. 이는 COSY 라는 설계 환경에서 사용하는 표현이다. 여기서 주의할 점은 pure Kahn process network 을 사용하면, MPEG decoder 가 Stream Parser 로 오는 데이터를 처리하다가 User control 로 부터 오는 data 를 받아들일 수 없다는 점이다. 그래서, Kahn process network 에 “select” 연산을 확장한 YAPI 모델을 사용한다. Stream Parser MPEG Decoder Image Display data path data path data path data path Copyrightⓒ2003

43 YAPI Processes Directed FIFO Process network
read, write are blocked when data is not available or cannot be delivered “select” takes two input ports as input and returns a port ID, If neither input port has data available, it blocks. If both have, select one non-deterministically. Directed FIFO Process network n = select (in1, in2) if (n == 0) { read (in1, x); f1(x); } else if (n == 1) { read (in2, y); f2(y); } Select 연산이란 어느 입력 포트에 데이터가 있는지를 확인하고 그 포트로 부터 데이터를 읽도록 하는 기능을 추가한 것이다. 왜냐하면 read 가 blocking 이므로 데이터가 없는 곳을 기다리고 있으면 시스템이 blocking 되기 때문이다. 그러나 이러한 추가로 말미암아 Kahn process network 이 갖는 장점인 determinacy 가 손상된다. Code fragment Copyrightⓒ2003

44 Discrete-Event Model Event-driven Simulation Application
Processing events in the chronological order Reveal the system dynamic characteristics Application (queueing) network simulation, hardware simulation B Event Queue A-C, 5us, 1.0 각 프로세스가 입력 포트중에서 이벤트가 오는 순서대로 처리를 하는 모델이다. 이 모델은 시스템의 시뮬레이션을 위해서 널리 사용되는 모델이지만, 엄밀한 의미로서는 정형성이 없는 모델이다. 왜냐하면, determinacy도 보장되지 않고, deadlock 이나 기타 중요한 성질을 검증할 수 있는 분석 방법을 제공하지 못하기 때문이다. 이 모델에서 각 프로세스는 샘플을 전달할 때에 time stamp 를 같이 전달하고 프로세스는 입력 포트로 부터 오는 이벤트 중에서 가장 빠른 time-stamp 를 갖는 이벤트를 먼저 처리한다. 이 모델은 HW/SW co-simulation 환경에서 사용하는 모델이다. A B-C, 5us, 0.0 B-C, 2us, 3.0 A-C, 1us, 2.0 C event path event time value Copyrightⓒ2003

45 Ptolemy II hierarchical composition of diverse models of computation
Being developed for embedded software design tool. But, no result on automatic software synthesis yet. A C D B x y z G F E FSM domain Modal model XXX domain YYY domain Copyrightⓒ2003

46 Discrete Events with FSM
DE a a/x x c c/y a b y b a b A B Most straightforward combination from a control perspective. The FSM system appears to the DE system as a zero-delay actor Absence of token implies null event. - no transition should be made by null event. DE 모델의 한 노드를 FSM 으로 명세하는 것은 자연스럽다. Copyrightⓒ2003

47 PeaCE from SNU CAP Lab. Hybrid approach of STATEMATE and Ptolemy
Restricted composition of heterogeneous models of computations fFSM: control logic specification SPDF : computation (signal processing) specification A novel Task-model is used for top-level task-level specification Motivation Use models consistently from specification to synthesis synthesis path from fFSM and SPDF is well established. Use natural combinations of heterogeneous models. 서울대학교 CAP 연구실에서 개발한 PeaCE 설계 도구는 STATEMATE 와 Ptolemy 의 장점을 취한 명세 방법을 사용한다. STATEMATE 에서의 activity chart 대신 새로운 Task-Model 을 제안하여 사용한다. 제어 태스크는 statechart 와 비슷한 concurrent and hierarchical 한 FSM 을 사용한다. 그리고 신호처리 태스크는 SDF model 의 단점을 보완하도록 확장한 SDF 모델을 사용한다. Copyrightⓒ2003

48 Communication between fFSM and SDF
Synchronous interaction Backplane Event Display source 1. data transfer “ a ” fFSM SDF a/out “ out ” C A X Y 2. execution FSM 과 Dataflow model 사이에 직접 데이터를 주고 받을 수 있다. 이 경우 데이터가 도착하면 즉시 반응을 하게 된다. B flag “ flag ” 3. result(flag) transfer Copyrightⓒ2003

49 Asynchronous Interaction
Change the scheduling state of a dataflow module Change a block parameter Dataflow active suspend stop run status 1. signal transfer fFSM 2. change run status 2. change block parameter STATEMATE 와 같이 FSM 모델에서 script 언어를 사용하여 Dataflow task 의 동작을 제어할 수 있다. Dataflow 1. signal transfer fFSM source decode variable gain Copyrightⓒ2003

50 DIVX Player System Specification
suspend==1 divxread H.263 Decoder divx run divx suspend AVI Reader MP3 Decoder script in divxrun {run divx} start==1 script in divsuspend {suspend divx} exit divx scripts in divx {deliver ui filename divxread filename} {run divx} stop==1/ tostart=1 divx start 푸른 색으로 둘러쌓인 노드는 hierarchical and concurrent FSM 모델로 구성된 제어 태스크이고 빨간 색으로 둘러쌓인 노드는 dataflow 로 표현된 태스크이다. suspend text==4 stop script in divxstop {stop divx} exitDivx ==1 exit 1 text divxstop start script in exit state {get divx exit exitDivx} tostart==1 Copyrightⓒ2003

51 Task-Level Specification Model
Task-level specification model bridges gaps between formality of basic models and flexibility of expression Definition of task-level specification model Tasks which are specified by SDF or FSM models Specification for execution types and port semantics at task wrapper Execution Type Task-level specification model bridges gaps between formality of basic models and flexibility of expression. Definition of task-level specification models is based on basic task block which are specified by SDF or FSM models inside and includes specification for execution types and port semantics at task wrapper which translates properties of basic models to those of task-level specification model. port semantic Basic Task Block (SDF or FSM) Task Wrapper Copyrightⓒ2003

52 Diverse Task Execution Types
Function type Basic execution type of SDF and FSM model When data is available, it starts an iteration and sends output data Periodic task Specify “period” of the task at task wrapper After triggered by time period, it becomes active Sporadic task Specify “interrupt conditions” of the task at task wrapper When the condition is met, it is activated Network layer Internet Packet decoder H.263 MP3 player periodic function sporadic interrupt condition no type period To solve diverse execution types of tasks, we specify an execution condition at task wrapper. The task wrapper creates proper execution condition of the task by translating the given execution type. If no execution type is specified at task wrapper, basic execution type of SDF and FSM model becomes function type. When data is available, it starts an iteration and sends output data. If user specifies “period” of the task at task wrapper, the SDF and FSM model becomes a periodic task. After triggered by time period, it becomes active. If user specifies “interrupt conditions” of the task at task wrapper, it is a sporadic task. When the condition is met, it is activated. Copyrightⓒ2003

53 Dynamic Execution Rate
constant rate streaming dynamic-rate variable-size queue Port properties data rate : static or dynamic data size : static or variable port type : queue or buffer Automatic translation for basic ports in SDF and FSM models Explicit specification for dynamic rate port at task wrapper Creates additional information to handle blocking operations dynamic rate connection Network layer Internet Packet decoder H.263 MP3 player To overcome dynamic execution rate problem, task-level specification model provides various port semantics which are combinations of port properties. Data rate can be static or dynamic, data size be static or variable and port type be queue or buffer. Basic ports in SDF and FSM models are automatically translated to port semantics in task-level specification. But for dynamic execution rate, we explicitly specify dynamic rate port properties at task wrapper. Then task wrapper creates additional information to handle blocking operations properly in operating systems. Copyrightⓒ2003

54 Automatic Translation for Basic Ports
Port type Port property Data port of SDF model Static-rate static-size queue Data port of FSM model Dynamic-rate static-size buffer Scheduling control port Parameter delivery control port Static-rate static-size buffer Exception handling control port Dynamic-rate static-size queue Control port for periodic task Control port for sporadic task This table shows how port type in basic models are translated to port semantics in task-level specification Copyrightⓒ2003

55 Summary System specification 방법에 따라 설계도구의 특징이 결정된다.
Language-based approach는 platform이 정해진 경우, 그리고 single CPU core SoC의 경우에 유용하다. 일반적인 명세로는 Formal models 을 사용하는 것이 바람직하다. Hierarchical and concurrent FSM 모델과 확장된 SDF 모델을 이용하여 task를 명세하는 것이 많이 쓰인다. Task-level 명세법에는 Process based approach와 heterogeneous approach가 있다. Copyrightⓒ2003

56 평가 문제 1. C 코드로 기술된 알고리즘을 가지고 설계 공간을 탐색하는 것 보다 SDF와 같은 정형적인 명세로 기술된 알고리즘을 가지고 설계 공간을 탐색하는 것이 좋은 이유를 설명하여라. 2. 다음 SDF 그래프에 대한 물음에 답하여라. 각 arc 에 명시된 숫자는 각 노드가 수행될 때 생성하고 소비하는 샘플의 수를 의미한다. (가) consistent 한 SDF 그래프가 되도록 하는 x,y 의 값을 구하여라. 가장 작은 정수 값을 구하도록 한다. (나) (가)의 경우, 1 iteration 동안에 각 노드가 수행되는 횟수 (repetition count) (다) arc에 필요한 buffer 의 수를 최소로 하는 schedule을 구하여라. 이 때, 각 arc에 필요한 buffer 의 수는 얼마가 되는가? 2 3 1 2 A B D 1 y C 2 x Copyrightⓒ2003

57 Continue… 3. [15점] 다음의 동작을 하는 시스템에 대하여 물음에 답하여라. 입력: 사용자의 콘트롤 button B. 데이터 입력 Y 출력: Z Y 입력은 매 클럭 들어오며 콘트롤 입력 B는 비주기적으로 들어오는 입력이다. 콘트롤 버튼 B 입력이 들어올 때 내부적인 콘트롤 신호 X의 값이 toggle 된다. X의 값이 0인 경우에는 Z 는 그 시간부터 시작하여 입력 Y에서 3번째 1이 들어올 때 마다 1을 출력한다. 그러나, X의 값이 1 이 되면 2번째 1이 들어올 때 마다 1을 출력한다. 즉, 아래와 같은 특성을 보인다. (가) Hierarchical 하고 concurrent 한 FSM을 이용하여 이 시스템을 명세하여라. (나) Flat 한 FSM을 이용하여 기술하려면 몇 개의 state 가 필요한가? X 1 Y Z Copyrightⓒ2003

58 Continue… F E y/c G A C x x/b z H B D u/g w/e
4. 다음은 hierarchical & concurrent 한 FSM을 지원하는 Statechart 이다. 각 level 에서의 초기 상태는 점에서 시작하는 arc를 가지고 명시하였다. 즉, 이 FSM 의 초기 상태는 {F(G), E(A)} 이다. F 와 E 는 hiearchical 한 state를 나타낸다. Ambiguity를 해소하기 위하여 다음과 같은 가정을 한다. internal state 가 아닌 경우에는 instantaneous transition을 허용하지 않는다. 계층구조에서는 상위 계층의 transition 에 우선 순위를 둔다. (가) 초기 상태에서 입력event 가 다음과 같은 순서로 들어왔다. 시스템의 최종 상태를 구하고 그 동안 출력된 이벤트를 구하여라. 입력: x,u,x,w (나) pure & flat FSM 으로 치환할 때, state 의 수는 몇 개가 될 것인가? transition arc 의 수는 몇개일까? (다) G에서 H 로 가는 arc 와 B에서 D 로 가는 arc는 statechart 가 compositionality를 만족하지 못함을 보여주고 있다. compositionality를 만족하기 위하여 internal event를 사용하려고 한다. FSM 은 어떻게 치환이 되겠는가? Copyrightⓒ2003

59 참고 문헌 [1] Kurt Keutzer, et. al. “System-Level Design: Orthogonali-zation of Concerns and Platform-Based Design," IEEE TCAD, 19(12), December 2000. [2] E.A.Lee and D.G.Messerschmitt, “Static Scheduling of Synchronous Dataflow Programs for Digital Signal Processing,” IEEE Transactions on Computers, January, 1987. [3] D.Harel, “Statecharts: A visual formalism for complex systems”, Science of Computer Programming, Vol. 8, pp , 1987 [4] A. Girault, B. Lee, and E. A. Lee, ``Hierarchical Finite State Machines with Multiple Concurrency Models,'' IEEE Transactions On Computer-aided Design Of Integrated Circuits And Systems, Vol. 18, No. 6, June 1999. [5] Jie Liu and Edward A. Lee, “Timed Multitasking for Real-Time Embedded Software,” IEEE Control Systems Magazine, pp , February 2003. [6] Dohyung Kim, Minyung Kim and Soonhoi Ha, "A Case Study of System Level Specification and Software Synthesis of Multi-mode Multimedia Terminal," ESTIMedia Oct 2003 Copyrightⓒ2003