| 1. |
- Holsmark, Rickard, 1970-
(författare)
-
Deadlock Free Routing in Mesh Networks on Chip with Regions
- 2009
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- There is a seemingly endless miniaturization of electronic components, which has enabled designers to build sophisticated computing structureson silicon chips. Consequently, electronic systems are continuously improving with new and more advanced functionalities. Design complexity ofthese Systems on Chip (SoC) is reduced by the use of pre-designed cores. However, several problems related to the interconnection of coresremain. Network on Chip (NoC) is a new SoC design paradigm, which targets the interconnect problems using classical network concepts. Still,SoC cores show large variance in size and functionality, whereas several NoC benefits relate to regularity and homogeneity. This thesis studies some network aspects which are characteristic to NoC systems. One is the issue of area wastage in NoC due to cores of varioussizes. We elaborate on using oversized regions in regular mesh NoC and identify several new design possibilities. Adverse effects of regions oncommunication are outlined and evaluated by simulation. Deadlock freedom is an important region issue, since it affects both the usability and performance of routing algorithms. The concept of faultyblocks, used in deadlock free fault-tolerant routing algorithms has similarities with rectangular regions. We have improved and adopted one suchalgorithm to provide deadlock free routing in NoC with regions. This work also offers a methodology for designing topology agnostic, deadlockfree, highly adaptive application specific routing algorithms. The methodology exploits information about communication among tasks of anapplication. This is used in the analysis of deadlock freedom, such that fewer deadlock preventing routing restrictions are required. A comparative study of the two proposed routing algorithms shows that the application specific algorithm gives significantly higher performance.But, the fault-tolerant algorithm may be preferred for systems requiring support for general communication. Several extensions to our work areproposed, for example in areas such as core mapping and efficient routing algorithms. The region concept can be extended for supporting reuse ofa pre-designed NoC as a component in a larger hierarchical NoC.
|
|
| 2. |
- Izosimov, Viacheslav, 1980-
(författare)
-
Scheduling and Optimization of Fault-Tolerant Distributed Embedded Systems
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Safety-critical applications have to function correctly and deliver high level of quality-ofservice even in the presence of faults. This thesis deals with techniques for tolerating effects of transient and intermittent faults. Re-execution, software replication, and rollback recovery with checkpointing are used to provide the required level of fault tolerance at the software level. Hardening is used to increase the reliability of hardware components. These techniques are considered in the context of distributed real-time systems with static and quasi-static scheduling.Many safety-critical applications have also strict time and cost constrains, which means that not only faults have to be tolerated but also the constraints should be satisfied. Hence, efficient system design approaches with careful consideration of fault tolerance are required. This thesis proposes several design optimization strategies and scheduling techniques that take fault tolerance into account. The design optimization tasks addressed include, among others, process mapping, fault tolerance policy assignment, checkpoint distribution, and trading-off between hardware hardening and software re-execution. Particular optimization approaches are also proposed to consider debugability requirements of fault-tolerant applications. Finally, quality-of-service aspects have been addressed in the thesis for fault-tolerant embedded systems with soft and hard timing constraints.The proposed scheduling and design optimization strategies have been thoroughly evaluated with extensive experiments. The experimental results show that considering fault tolerance during system-level design optimization is essential when designing cost-effective and high-quality fault-tolerant embedded systems.
|
|
| 3. |
- Larsson, Anders, 1977-
(författare)
-
Test Optimization for Core-based System-on-Chip
- 2008
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The semiconductor technology has enabled the fabrication of integrated circuits (ICs), which may include billions of transistors and can contain all necessary electronic circuitry for a complete system, so-called System-on-Chip (SOC). In order to handle design complexity and to meet short time-to-market requirements, it is increasingly common to make use of a modular design approach where an SOC is composed of pre-designed and pre-verified blocks of logic, called cores.Due to imperfections in the fabrication process, each IC must be individually tested. A major problem is that the cost of test is increasing and is becoming a dominating part of the overall manufacturing cost. The cost of test is strongly related to the increasing test-data volumes, which lead to longer test application times and larger tester memory requirement. For ICs designed in a modular fashion, the high test cost can be addressed by adequate test planning, which includes test-architecture design, test scheduling, test-data compression, and test sharing techniques.In this thesis, we analyze and explore several design and optimization problems related to core-based SOC test planning. We perform optimization of test sharing and test-data compression. We explore the impact of test compression techniques on test application time and compression ratio. We make use of analysis to explore the optimization of test sharing and test-data compression in conjunction with test-architecture design and test scheduling. Extensive experiments, based on benchmarks and industrial designs, have been performed to demonstrate the significance of our techniques.
|
|
| 4. |
- Manolache, Sorin
(författare)
-
Analysis and Optimisation of Real-Time Systems with Stochastic Behaviour
- 2005
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems have become indispensable in our life: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints.The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this thesis, we address two causes of such stochastic behaviour: the application and platform-dependent stochastic task execution times, and the platform-dependent occurrence of transient faults on network links in networks-on-chip.We present three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation.Our contribution is manifold in the area of buffer and time constrained communication along unreliable on-chip links. First, we introduce the concept of communication supports, an intelligent combination between spatially and temporally redundant communication. We provide a method for constructing a sufficiently varied pool of alternative communication supports for each message. Second, we propose a heuristic for exploring the space of communication support candidates such that the task response times are minimised. The resulting time slack can be exploited by means of voltage and/or frequency scaling for communication energy reduction. Third, we introduce an algorithm for the worst-case analysis of the buffer space demand of applications implemented on networks-on-chip. Last, we propose an algorithm for communication mapping and packet timingfor buffer space demand minimisation.All our contributions are supported by sets of experimental results obtained from both synthetic and real-world applications of industrial size.
|
|
| 5. |
- He, Zhiyuan, 1976-
(författare)
-
System-on-Chip test scheduling with defect-probability and temperature considerations
- 2007
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Electronic systems have become highly complex, which results in a dramatic increase of both design and production cost. Recently a core-based system-on-chip (SoC) design methodology has been employed in order to reduce these costs. However, testing of SoCs has been facing challenges such as long test application time and high temperature during test. In this thesis, we address the problem of minimizing test application time for SoCs and propose three techniques to generate efficient test schedules.First, a defect-probability driven test scheduling technique is presented for production test, in which an abort-on-first-fail (AOFF) test approach is employed and a hybrid built-in self-test architecture is assumed. Using an AOFF test approach, the test process can be aborted as soon as the first fault is detected. Given the defect probabilities of individual cores, a method is proposed to calculate the expected test application time (ETAT). A heuristic is then proposed to generate test schedules with minimized ETATs.Second, a power-constrained test scheduling approach using test set partitioning is proposed. It assumes that, during the test, the total amount of power consumed by the cores being tested in parallel has to be lower than a given limit. A heuristic is proposed to minimize the test application time, in which a test set partitioning technique is employed to generate more efficient test schedules.Third, a thermal-aware test scheduling approach is presented, in which test set partitioning and interleaving are employed. A constraint logic programming (CLP) approach is deployed to find the optimal solution. Moreover, a heuristic is also developed to generate near-optimal test schedules especially for large designs to which the CLP-based algorithm is inapplicable.Experiments based on benchmark designs have been carried out to demonstrate the applicability and efficiency of the proposed techniques.
|
|
| 6. |
- Karlsson, Daniel, 1975-
(författare)
-
Verification of Component-based Embedded System Designs
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are becoming increasingly common in our everyday lives. As technology progresses, these systems become more and more complex. Designers handle this increasing complexity by reusing existing components. At the same time, the systems must fulfill strict functional and non-functional requirements.This thesis presents novel and efficient techniques for the verification of component-based embedded system designs. As a common basis, these techniques have been developed using a Petri net based modelling approach, called PRES+.Two complementary problems are addressed: component verification and integration verification. With component verification the providers verify their components so that they function correctly if given inputs conforming to the assumptions imposed by the components on their environment.Two techniques for component verification are proposed in the thesis. The first technique enables formal verification of SystemC designs by translating them into the PRES+ representation. The second technique involves a simulation based approach into which formal methods are injected to boost verification efficiency.Provided that each individual component is verified and is guaranteed to function correctly, the components are interconnected to form a complete system. What remains to be verified is the interface logic, also called glue logic, and the interaction between components.Each glue logic and interface cannot be verified in isolation. It must be put into the context in which it is supposed to work. An appropriate environment must thus be derived from the components to which the glue logic is connected. This environment must capture the essential properties of the whole system with respect to the properties being verified. In this way, both the glue logic and the interaction of components through the glue logic are verified. The thesis presents algorithms for automatically creating such environments as well as the underlying theoretical framework and a step-by-step roadmap on how to apply these algorithms.
|
|
| 7. |
- Larsson, Anders, 1977-
(författare)
-
System-on-Chip Test Scheduling and Test Infrastructure Design
- 2005
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- There are several challenges that have to be considered in order to reduce the cost of System-on-Chip (SoC) testing, such as test application time, chip area overhead due to hardware introduced to enhance the testing, and the price of the test equipment. In this thesis the test application time and the test infrastructure hardware overhead of multiple-core SoCs are considered and two different problems are addressed. First, a technique that makes use of the existing bus structure on the chip for transporting test data is proposed. Additional buffers are inserted at each core to allow test application to the cores and test data transportation over the bus to be performed asynchronously. The non-synchronization of test data transportation and test application makes it possible to perform concurrent testing of cores while test data is transported in a sequence. A test controller is introduced, which is responsible for the invocation of test transportations on the bus. The hardware cost, introduced by the buffers and test controller, is minimized under a designer-specified test time constraint. This problem has been solved optimally by using a Constraint Logic Programming formulation, and a tabu search based heuristic has also been implemented to generate quickly near-optimal solutions. Second, a technique to broadcast tests to several cores is proposed, and the possibility to use overlapping test vectors from different tests in a SoC is explored. The overlapping tests serve as alternatives to the original, dedicated, tests for the individual cores and, if selected, they are broadcasted to the cores so that several cores are tested concurrently. This technique allows the existing bus structure to be reused; however, dedicated test buses can also be introduced in order to reduce the test time. Our objective is to minimize the test application time while a designer-specified hardware constraint is satisfied. Again Constraint Logic Programming has been used to solve the problem optimally. Experiments using benchmark designs have been carried out to demonstrate the usefulness and efficiency of the proposed techniques.
|
|
| 8. |
- Mohamed, Abdil, 1971-
(författare)
-
High-Level Techniques for Built-In Self-Test Resources Optimization
- 2005
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Design modifications to improve testability usually introduce large area overhead and performance degradation. One way to reduce the negative impact associated with improved testability is to take testability as one of the constraints during high- level design phases so that systems are not only optimized for area and performance, but also from the testability point of view. This thesis deals with the problem of optimizing testing-hardware resources by taking into account testability constraints at high-levels of abstraction during the design process. Firstly, we have provided an approach to solve the problem of optimizing built-in selftest (BIST) resources at the behavioral and register-transfer levels under testability and testing time constraints. Testing problem identification and BIST enhancement during the optimization process are assisted by symbolic testability analysis. Further, concurrent test sessions are generated, while signature analysis registers sharing conflicts as well as controllability and observability constraints are considered. Secondly, we have introduced the problem of BIST resources insertion and optimization while taking wiring area into account. Testability improvement transformations have been defined and deployed in a hardware overhead minimization technique used during a BIST synthesis process. The technique is guided by the results of symbolic testability analysis and inserts a minimal amount of BIST resources into the design to make it fully testable. It takes into consideration both BIST components cost and wiring overhead. Two design space exploration approaches have been proposed: a simulated annealing based algorithm and a greedy heuristic. Experimental results show that considering wiring area during BIST synthesis results in smaller final designs as compared to the cases when the wiring impact is ignored. The greedy heuristic uses our behavioral and register-transfer levels BIST enhancement metrics to guide BIST synthesis in such a way that the number of testability improvement transformations performed on the design is reduced.
|
|
| 9. |
- Andrei, Alexandru, 1977-
(författare)
-
Energy Efficient and Predictable Design of Real-Time Embedded Systems
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)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.
|
|
| 10. |
- Izosimov, Viacheslav, 1980-
(författare)
-
Scheduling and Optimization of Fault-Tolerant Embedded Systems
- 2006
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Safety-critical applications have to function correctly even in presence of faults. This thesis deals with techniques for tolerating effects of transient and intermittent faults. Reexecution, software replication, and rollback recovery with checkpointing are used to provide the required level of fault tolerance. These techniques are considered in the context of distributed real-time systems with non-preemptive static cyclic scheduling.Safety-critical applications have strict time and cost constrains, which means that not only faults have to be tolerated but also the constraints should be satisfied. Hence, efficient system design approaches with consideration of fault tolerance are required.The thesis proposes several design optimization strategies and scheduling techniques that take fault tolerance into account. The design optimization tasks addressed include, among others, process mapping, fault tolerance policy assignment, and checkpoint distribution.Dedicated scheduling techniques and mapping optimization strategies are also proposed to handle customized transparency requirements associated with processes and messages. By providing fault containment, transparency can, potentially, improve testability and debugability of fault-tolerant applications.The efficiency of the proposed scheduling techniques and design optimization strategies is evaluated with extensive experiments conducted on a number of synthetic applications and a real-life example. The experimental results show that considering fault tolerance during system-level design optimization is essential when designing cost-effective fault-tolerant embedded systems.
|
|
| 11. |
- Pop, Traian, 1975-
(författare)
-
Analysis and Optimisation of Distributed Embedded Systems with Heterogeneous Scheduling Policies
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The growing amount and diversity of functions to be implemented by the current and future embedded applications (like, for example, in automotive electronics) have shown that, in many cases, time-triggered and event-triggered functions have to coexist on the computing nodes and to interact over the communication infrastructure. When time-triggered and event-triggered activities have to share the same processing node, a natural way for the execution support can be provided through a hierarchical scheduler. Similarly, when such heterogeneous applications are mapped over a distributed architecture, the communication infrastructure should allow for message exchange in both time-triggered and event-triggered manner in order to ensure a straightforward interconnection of heterogeneous components.This thesis studies aspects related to the analysis and design optimisation for safety-critical hard real-time applications running on hierarchically scheduled distributed embedded systems. It first provides the basis for the timing analysis of the activities in such a system, by carefully taking into consideration all the interferences that appear at run-time between the processes executed according to different scheduling policies. Moreover, due to the distributed nature of the architecture, message delays are also taken into consideration during the timing analysis. Once the schedulability analysis has been provided, the entire system can be optimised by adjusting its configuration parameters. In our work, the entire optimisation process is directed by the results from the timing analysis, with the goal that in the end the timing constraints of the application are satisfied. The analysis and design methodology proposed in the first part of the thesis is applied next on the particular category of distributed systems that use FlexRay as a communication protocol. We start by providing a schedulability analysis for messages transmitted over a FlexRay bus, and then by proposing a bus access optimisation algorithm that aims at improving the timing properties of the entire system.For all the problems that we investigated, we have carried out extensive experiments in order to measure the efficiency of the proposed solutions. The results have confirmed both the importance of the addressed aspects during system-level design, and the applicability of our techniques for analysing and optimising the studied systems.
|
|
