| 1. |
- Andrei, Alexandru, 1977-
(author)
-
Energy Efficient and Predictable Design of Real-Time Embedded Systems
- 2007
-
Doctoral thesis (other academic/artistic)abstract
- This thesis addresses several issues related to the design and optimization of embedded systems. In particular, in the context of time-constrained embedded systems, the thesis investigates two problems: the minimization of the energy consumption and the implementation of predictable applications on multiprocessor system-on-chip platforms.Power consumption is one of the most limiting factors in electronic systems today. Two techniques that have been shown to reduce the power consumption effectively are dynamic voltage selection and adaptive body biasing. The reduction is achieved by dynamically adjusting the voltage and performance settings according to the application needs. Energy minimization is addressed using both offline and online optimization approaches. Offline, we solve optimally the combined supply voltage and body bias selection problem for multiprocessor systems with imposed time constraints, explicitly taking into account the transition overheads implied by changing voltage levels. The voltage selection technique is applied not only to processors, but also to buses with repeaters and fat wires. We investigate the continuous voltage selection as well as its discrete counterpart. While the above mentioned methods minimize the active energy, we propose an approach that combines voltage selection and processor shutdown in order to optimize the total energy.In order to take full advantage of slack that arises from variations in the execution time, it is important to recalculate the voltage and performance settings during run-time, i.e., online. However, voltage scaling is computationally expensive, and, thus, performed at runtime, significantly hampers the possible energy savings. To overcome the online complexity, we propose a quasi-static voltage scaling scheme, with a constant online time complexity O(1). This allows to increase the exploitable slack as well as to avoid the energy dissipated due to online recalculation of the voltage settings.Worst-case execution time (WCET) analysis and, in general, the predictability of real-time applications implemented on multiprocessor systems has been addressed only in very restrictive and particular contexts. One important aspect that makes the analysis difficult is the estimation of the system’s communication behavior. The traffic on the bus does not solely originate from data transfers due to data dependencies between tasks, but is also affected by memory transfers as result of cache misses. As opposed to the analysis performed for a single processor system, where the cache miss penalty is constant, in a multiprocessor system each cache miss has a variable penalty, depending on the bus contention. This affects the tasks’ WCET which, however, is needed in order to perform system scheduling. At the same time, the WCET depends on the system schedule due to the bus interference. In this context, we propose, an approach to worst-case execution time analysis and system scheduling for real-time applications implemented on multiprocessor SoC architectures.
|
|
| 2. |
|
|
| 3. |
- Giannopoulou, Georgia, et al.
(author)
-
Timed Model Checking with Abstractions: Towards Worst-Case Response Time Analysis in Resource-Sharing Manycore Systems
- 2012
-
In: Proc. International Conference on Embedded Software (EMSOFT). - : ACM Press. ; , s. 63-72
-
Conference paper (peer-reviewed)abstract
- Multicore architectures are increasingly used nowadays in embedded real-time systems. Parallel execution of tasks feigns the possibility of a massive increase in performance. However, this is usually not achieved because of contention on shared resources. Concurrently executing tasks mutually block their accesses to the shared resource, causing non-deterministic delays. Timing analysis of tasks in such systems is then far from trivial. Recently, several analytic methods have been proposed for this purpose, however, they cannot model complex arbitration schemes such as FlexRay which is a common bus arbitration protocol in the automotive industry. This paper considers real-time tasks composed of superblocks, i. e., sequences of computation and re- source accessing phases. Resource accesses such as accesses to memories and caches are synchronous, i. e., they cause execution on the processing core to stall until the access is served. For such systems, the paper presents a state-based modeling and analysis approach based on Timed Automata which can model accurately arbitration schemes of any complexity. Based on it, we compute safe bounds on the worst-case response times of tasks. The scalability of the approach is increased significantly by abstracting several cores and their tasks with one arrival curve, which represents their resource accesses and computation times. This curve is then incorporated into the Timed Automata model of the system. The accuracy and scalability of the approach are evaluated with a real-world application from the automotive industry and benchmark applications.
|
|
| 4. |
- Guan, Nan, 1981-
(author)
-
New Techniques for Building Timing-Predictable Embedded Systems
- 2013
-
Doctoral thesis (other academic/artistic)abstract
- Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design.On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework.On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem.On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.
|
|
| 5. |
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
- Thiele, Lothar, et al.
(author)
-
A Preference-Based Evolutionary Algorithm for Multi-Objective Optimization
- 2009
-
In: Evolutionary Computation. - : MIT Press - Journals. - 1063-6560 .- 1530-9304. ; 17:3, s. 411-436
-
Journal article (peer-reviewed)abstract
- In this paper, we discuss the idea of incorporating preference information into evolutionary multi-objective optimization and propose a preference-based evolutionary approach that can be used as an integral part of an interactive algorithm. One algorithm is proposed in the paper. At each iteration, the decision maker is asked to give preference information in terms of his or her reference point consisting of desirable aspiration levels for objective functions. The information is used in an evolutionary algorithm to generate a new population by combining the fitness function and an achievement scalarizing function. In multi-objective optimization, achievement scalarizing functions are widely used to project a given reference point into the Pareto optimal set. In our approach, the next population is thus more concentrated in the area where more preferred alternatives are assumed to lie and the whole Pareto optimal set does not have to be generated with equal accuracy. The approach is demonstrated by numerical examples.
|
|
| 9. |
- Thiele, Lothar, et al.
(author)
-
A Preference-Based Interactive Evolutionary Algorithm for Multiobjective Optimization
- 2007
-
Reports (other academic/artistic)abstract
- In this paper, we discuss ideas of incorporating preference information intoevolutionary multiobjective optimization and propose a preference-based evolutionaryalgorithm that can be used as an integral part of an interactive algorithm that we alsointroduce. At each iteration of the interactive algorithm, the DM is asked to givepreference information in terms of his/her reference point consisting of desirableaspiration levels for objective functions. The information is used in an evolutionaryalgorithm that generates a new population by combining the fitness function with anachievement scalarizing function containing the reference point. In the field ofmultiple criteria decision making, achievement scalarizing functions are widely usedfor projecting the reference point into the Pareto optimal set. In our approach, the nextpopulation is more concentrated in the area where more preferred alternatives areassumed to lie and the whole Pareto optimal set does not have to be generated withequal accuracy. The approach is demonstrated by numerical examples.
|
|
| 10. |
- Woehrle, Matthias, et al.
(author)
-
Conformance testing for cyber-physical systems
- 2012
-
In: ACM Transactions on Embedded Computing Systems. - New York : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 11:4, s. 84:1-23
-
Journal article (peer-reviewed)abstract
- Cyber-Physical Systems (CPS) require a high degree of reliability and robustness. Hence it is important to assert their correctness with respect to extra-functional properties, like power consumption, temperature, etc. In turn the physical quantities may be exploited for assessing system implementations. This article develops a methodology for utilizing measurements of physical quantities for testing the conformance of a running CPS with respect to a formal description of its required behavior allowing to uncover defects. We present foundations and implementations of this approach and demonstrate its usefulness by conformance testing power measurements of a wireless sensor node with a formal model of its power consumption.
|
|
| 11. |
- Wylensek, David, et al.
(author)
-
A collection of bacterial isolates from the pig intestine reveals functional and taxonomic diversity
- 2020
-
In: Nature Communications. - : Nature Publishing Group. - 2041-1723. ; 11:1
-
Journal article (peer-reviewed)abstract
- Our knowledge about the gut microbiota of pigs is still scarce, despite the importance of these animals for biomedical research and agriculture. Here, we present a collection of cultured bacteria from the pig gut, including 110 species across 40 families and nine phyla. We provide taxonomic descriptions for 22 novel species and 16 genera. Meta-analysis of 16S rRNA amplicon sequence data and metagenome-assembled genomes reveal prevalent and pig-specific species within Lactobacillus, Streptococcus, Clostridium, Desulfovibrio, Enterococcus, Fusobacterium, and several new genera described in this study. Potentially interesting functions discovered in these organisms include a fucosyltransferase encoded in the genome of the novel species Clostridium porci, and prevalent gene clusters for biosynthesis of sactipeptide-like peptides. Many strains deconjugate primary bile acids in in vitro assays, and a Clostridium scindens strain produces secondary bile acids via dehydroxylation. In addition, cells of the novel species Bullifex porci are coccoidal or spherical under the culture conditions tested, in contrast with the usual helical shape of other members of the family Spirochaetaceae. The strain collection, called 'Pig intestinal bacterial collection' (PiBAC), is publicly available at www.dsmz.de/pibac and opens new avenues for functional studies of the pig gut microbiota. The authors present a public collection of 117 bacterial isolates from the pig gut, including the description of 38 novel taxa. Interesting functions discovered in these organisms include a new fucosyltransferease and sactipeptide-like molecules encoded by biosynthetic gene clusters.
|
|
| 12. |
- Zimmerling, Marco, et al.
(author)
-
On modeling low-power wireless protocols based on synchronous packet transmissions
- 2013
-
In: Proceedings - IEEE Computer Society's Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, MASCOTS. - 9780769551029 ; , s. 546-555
-
Conference paper (peer-reviewed)abstract
- Mathematical models play a pivotal role in understanding and designing advanced low-power wireless systems. However, the distributed and uncoordinated operation of traditional multi-hop low-power wireless protocols greatly complicates their accurate modeling. This is mainly because these protocols build and maintain substantial network state to cope with the dynamics of low-power wireless links. Recent protocols depart from this design by leveraging synchronous transmissions (ST), whereby multiple nodes simultaneously transmit towards the same receiver, as opposed to pair wise link-based transmissions (LT). ST improve the one-hop packet reliability to an extent that efficient multi-hop protocols with little network state are feasible. This paper studies whether ST also enable simple yet accurate modeling of these protocols. Our contribution to this end is two-fold. First, we show, through experiments on a 139-node test bed, that characterizing packet receptions and losses as a sequence of independent and identically distributed (i.i.d.) Bernoulli trials-a common assumption in protocol modeling but often illegitimate for LT-is largely valid for ST. We then show how this finding simplifies the modeling of a recent ST-based protocol, by deriving (i) sufficient conditions for probabilistic guarantees on the end-to-end packet reliability, and (ii) a Markovian model to estimate the long-term energy consumption. Validation using test bed experiments confirms that our simple models are also highly accurate, for example, the model error in energy against real measurements is 0.25%, a figure never reported before in the related literature.
|
|
| 13. |
- Zimmerling, Marco, et al.
(author)
-
Poster abstract : Synchronous transmissions enable simple yet accurate protocol modeling
- 2013
-
In: SenSys 2013 - Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems. - New York, NY, USA : Association for Computing Machinery. - 9781450320276
-
Conference paper (peer-reviewed)abstract
- Traditional low-power wireless protocols maintain distributed network state to cope with link dynamics. Modeling the pro- tocol operation as a function of network state is dificult as the state is frequently updated in an uncoordinated fashion. Recent protocols use synchronous transmissions (ST): mul- tiple nodes send simultaneously towards the same receiver, as opposed to pairwise link-based transmissions (LT). ST en- able eficient multi-hop protocols with little network state. We studied whether ST in Glossy enable simple yet accu- rate protocol modeling [10]. Based on extensive testbed experiments and statistical analyses, we found that: (i) unlike LT, packet receptions and losses with ST largely adhere to a sequence of independent and identically distributed (i.i.d.) Bernoulli trials; (ii) this property greatly simplifies accurately modeling ST-based protocols, as we demonstrated by obtaining model errors below 0.25% in energy for the Glossy based Low-Power Wireless Bus (LWB).
|
|
| 14. |
|
|
| 15. |
|
|
