嵌入式系统导论-实验课-2-slides2.pdfVIP

1 Swiss Federal Institute of Technology Computer Engineering and Networks Laboratory Exercise 2: Kahn Process Networks and Synchronous Data Flows 29.October 2014 Dr.Kai Huang kai.huang@tum.de Introduction to Embedded Systems 2 Swiss Federal Institute of Technology Computer Engineering and Networks Laboratory Kahn Process Network (KPN) ? Specification model – Proposed as language for parallel programming – Processes communicate via First-In-First-Out (FIFO) queues of infinite size – Read: destructive and blocking ? A process stays blocked on a wait until something is being sent on the channel by another process – Write: non-blocking ? A process can never be prevented from performing a send on a channel 3 Swiss Federal Institute of Technology Computer Engineering and Networks Laboratory KPNs: Graphical Representation ? Oriented graph with labeled nodes and edges – Nodes: processes – Edges: channels (one-directional) ? Incoming edges with only end vertices: inputs ? Outgoing edges with only origin vertices: outputs 4 Swiss Federal Institute of Technology Computer Engineering and Networks Laboratory KPNs: Assumptions and Restrictions – Processes can communicate only via FIFO queues – A channel transmits information within an unpredictable but finite amount of time – At any time, a process is either computing or waiting on exactly one of its input channels ? (i.e., no two processes are allowed to send data on the same channel) – Each process follows a sequential program 5 Swiss Federal Institute of Technology Computer Engineering and Networks Laboratory KPNs: Monotonicity ? A monotonic process F generates from an ordered set of input sequences X ? X’ an ordered set of output sequences: X ? X’? F(X) ? F(X’) – Ordered set of sequences X ? X’ if for each sequence i : X i ? X i ’ ([x 1 ] ? [x 1 , x 2 ] ? [x 1 , x 2 , x 3 , ...]) ? Explanation: – Receiv