Michael Beyer

Static Analysis of Run-time Modes in Kahn Process Networks


Front	Back

ISBN:

978-3-8440-1252-1

Series:

Softwaretechnik

Keywords:

static analysis; Kahn process networks; run-time behavior; modes; polyhedral abstraction

Type of publication:

Thesis

Language:

English

Pages:

142 pages

Figures:

63 figures

Weight:

209 g

Format:

21 x 14,8 cm

Bindung:

Paperback

Price:

45,80 € / 57,25 SFr

Published:

September 2012

Buy:

DOI:

10.2370/9783844012521 (Online document)

Download:

Available PDF-Files for this title:

You need the Adobe Reader, to open the files. Here you get help and information, for the download.

These files are not printable.


	Document		Abstract
	Type		PDF
	Costs		free
	Action		Display of file - 117 kB (120134 Byte)
	Action		Download of file - 117 kB (120134 Byte)


	Document		Document
	Type		PDF
	Costs		34,35 EUR
	Action		Purchase in obligation and display of file - 1,1 MB (1121660 Byte)
	Action		Purchase in obligation and download of file - 1,1 MB (1121660 Byte)


	Document		Table of contents
	Type		PDF
	Costs		free
	Action		Display of file - 178 kB (182616 Byte)
	Action		Download of file - 178 kB (182616 Byte)

User settings for registered users

You can change your address here or download your paid documents again.

User:	Not logged in.
Actions:	Login / Register Forgotten your password?

Recommendation:

You want to recommend this title?

Review copy

Here you can order a review copy.

Link

You want to link this page? Click here.

Abstract

Kahn Process Networks (KPNs) are used for modeling streaming-oriented applications with changing behavior. To meet the performance and energy constraints of embedded devices, such applications must be mapped to parallel architectures in an optimal way. Finding an optimal mapping to the constrained architecture presumes that the behavior of the KPN is statically known. Considering the run-time behavior of streaming-oriented applications, we can identify run-time modes in which the system offers a certain behavior. In this book, we present a static analysis that identifies such run-time modes at compile-time.

To that end, we use abstract interpretation based on polyhedral abstraction and an automata-based representation of KPNs to consider the expected run-time behavior. We have developed a state partitioning algorithm to separate control-oriented parts from transformative parts. The automata states are partitioned according to the run-time behavior. We identify modes and their hierarchies for individual processes by using our graph reduction algorithm to transform state partitioned automata to mode automata. To obtain the overall network behavior, we have developed a composition algorithm for asynchronously communicating mode automata. We abstract from unnecessary considerations of interleaving states by choosing one representative execution. The result is a mode automaton describing the whole network behavior.

To evaluate our method, we have implemented a prototype of our analysis. For an arbitrary KPN, our implementation statically analyzes its run-time modes and their corresponding behaviors. We have evaluated typical case studies, e. g., a reconfigurable Finite Impulse Response filter, which demonstrate the practicability of our approach. Optimizing backends that map KPNs to parallel architectures can be guided by these analysis results.