| 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. |
- Bao, Min, 1981-
(författare)
-
System-Level Techniques for Temperature-Aware Energy Optimization
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Energy consumption has become one of the main design constraints in today’s integrated circuits. Techniques for energy optimization, from circuit-level up to system-level, have been intensively researched.The advent of large-scale integration with deep sub-micron technologies has led to both high power densities and high chip working temperatures. At the same time, leakage power is becoming the dominant power consumption source of circuits, due to continuously lowered threshold voltages, as technology scales. In this context, temperature is an important parameter. One aspect, of particular interest for this thesis, is the strong inter-dependency between leakage and temperature. Apart from leakage power, temperature also has an important impact on circuit delay and, implicitly, on the frequency, mainly through its influence on carrier mobility and threshold voltage. For power-aware design techniques, temperature has become a major factor to be considered. In this thesis, we address the issue of system-level energy optimization for real-time embedded systems taking temperature aspects into consideration.We have investigated two problems in this thesis: (1) Energy optimization via temperature-aware dynamic voltage/frequency scaling (DVFS). (2) Energy optimization through temperature-aware idle time (or slack) distribution (ITD). For the above two problems, we have proposed off-line techniques where only static slack is considered. To further improve energy efficiency, we have also proposed online techniques, which make use of both static and dynamic slack. Experimental results have demonstrated that considerable improvement of the energy efficiency can be achieved by applying our temperature-aware optimization techniques. Another contribution of this thesis is an analytical temperature analysis approach which is both accurate and sufficiently fast to be used inside an energy optimization loop.
|
|
| 3. |
- Cortés, Luis Alejandro, 1971-
(författare)
-
A Petri Net based Modeling and Verification Technique for Real-Time Embedded Systems
- 2001
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are used in a wide spectrum of applications ranging from home appliances and mobile devices to medical equipment and vehicle controllers. They are typically characterized by their real-time behavior and many of them must fulfill strict requirements on reliability and correctness.In this thesis, we concentrate on aspects related to modeling and formal verification of realtime embedded systems.First, we define a formal model of computation for real-time embedded systems based on Petri nets. Our model can capture important features of such systems and allows their representations at different levels of granularity. Our modeling formalism has a welldefined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process.Second, we propose an approach to the problem of formal verification of real-time embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking ools. Various examples, including a realistic industrial case, demonstrate the feasibility of our approach on practical applications.
|
|
| 4. |
- 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.
|
|
| 5. |
- Karlsson, Daniel, 1975-
(författare)
-
Towards Formal Verification in a Component-based Reuse Methodology
- 2003
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are becoming increasingly common in our everyday lives. As techonology progresses, these systems become more and more complex. Designers handle this increasing complexity by reusing existing components (Intellectual Property blocks). At the same time, the systems must still fulfill strict requirements on reliability and correctness.This thesis proposes a formal verification methodology which smoothly integrates with component-based system-level design using a divide and conquer approach. The methodology assumes that the system consists of several reusable components. Each of these components are already formally verified by their designers and are considered correct given that the environment satisfies certain properties imposed by the component. What remains to be verified is the glue logic inserted between the components. Each such glue logic is verified one at a time using model checking techniques.The verification methodology as well as the underlying theoretical framework and algorithms are presented in the thesis.Experimental results have shown the efficiency of the proposed methodology and demonstrated that it is feasible to apply it on real-life examples.
|
|
| 6. |
- 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.
|
|
| 7. |
- Manolache, Sorin
(författare)
-
Schedulability analysis of real-time systems with stochastic task execution times
- 2002
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Systems controlled by embedded computers become indispensable in our lives and can be found in avionics, automotive industry, home appliances, medicine, telecommunication industry, mecatronics, space industry, etc. Fast, accurate and flexible performance estimation tools giving feedback to the designer in every design phase are a vital part of a design process capable to produce high quality designs of such embedded systems.In the past decade, the limitations of models considering fixed task execution times have been acknowledged for large application classes within soft real-time systems. A more realistic model considers the tasks having varying execution times with given probability distributions. No restriction has been imposed in this thesis on the particular type of these functions. Considering such a model, with specified task execution time probability distribution functions, an important performance indicator of the system is the expected deadline miss ratio of tasks or task graphs.This thesis proposes two approaches for obtaining this indicator in an analytic way. The first is an exact one while the second approach provides an approximate solution trading accuracy for analysis speed. While the first approach can efficiently be applied to monoprocessor systems, it can handle only very small multi-processor applications because of complexity reasons. The second approach, however, can successfully handle realistic multiprocessor applications. Experiments show the 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. |
- Pop, Paul, 1974-
(författare)
-
Scheduling and Communication Synthesis for Distributed Real-Time Systems
- 2000
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Embedded systems are now omnipresent: from cellular phones to pagers, from microwave ovens to PDAs, almost all the devices we use are controlled by embedded systems. Many embedded systems have to fulfill strict requirements in terms of performance and cost efficiency. Emerging designs are usually based on heterogeneous architectures that integrate multiple programmable processors and dedicated hardware components. New tools which extend design automation to system level have to support the integrated design of both the hardware and software components of such systems. This thesis concentrates on aspects of scheduling and communication for embedded real-time systems. Special emphasis has been placed on the impact of the communication infrastructure and protocol on the overall system performance. The scheduling and communication strategies proposed are based on an abstract graph representation which captures, at process level, both the dataflow and the flow of control. We have considered non-preemptive static cyclic scheduling and preemptive scheduling with static priorities for the scheduling of processes, while the communications are statically scheduled according to the time triggered protocol. We have developed static cyclic scheduling algorithms for time-driven systems with control and data dependencies. We show that by considering aspects of the communication protocol, significant improvements can be gained in the schedule quality. In the context of event-driven systems we have proposed a less pessimistic schedulability analysis that is able to handle both control and data dependencies. Moreover, we have provided a schedulability analysis for the time-triggered protocol, and we have proposed several optimization strategies for the synthesis of communication protocol parameters. Extensive experiments as well as real-life examples demonstrate the efficiency of our approaches.
|
|
| 10. |
- Pop, Ruxandra
(författare)
-
Mapping Concurrent Applications to Multiprocessor Systems with Multithreaded Processors and Network on Chip-Based Interconnections
- 2011
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Network on Chip (NoC) architectures provide scalable platforms for designing Systems on Chip (SoC) with large number of cores. Developing products and applications using an NoC architecture offers many challenges and opportunities. A tool which can map an application or a set of applications to a given NoC architecture will be essential.In this thesis we first survey current techniques and we present our proposals for mapping and scheduling of concurrent applications to NoCs with multithreaded processors as computational resources.NoC platforms are basically a special class of Multiprocessor Embedded Systems (MPES). Conventional MPES architectures are mostly bus-based and, thus, are exposed to potential difficulties regarding scalability and reusability. There has been a lot of research on MPES development including work on mapping and scheduling of applications. Many of these results can also be applied to NoC platforms.Mapping and scheduling are known to be computationally hard problems. A large range of exact and approximate optimization algorithms have been proposed for solving these problems. The methods include Branch-and–Bound (BB), constructive and transformative heuristics such as List Scheduling (LS), Genetic Algorithms (GA) and various types of Mathematical Programming algorithms.Concurrent applications are able to capture a typical embedded system which is multifunctional. Concurrent applications can be executed on an NoC which provides a large computational power with multiple on-chip computational resources.Improving the time performances of concurrent applications which are running on Network on Chip (NoC) architectures is mainly correlated with the ability of mapping and scheduling methodologies to exploit the Thread Level Parallelism (TLP) of concurrent applications through the available NoC parallelism. Matching the architectural parallelism to the application concurrency for obtaining good performance-cost tradeoffs is another aspect of the problem.Multithreading is a technique for hiding long latencies of memory accesses, through the overlapped execution of several threads. Recently, Multi-Threaded Processors (MTPs) have been designed providing the architectural infrastructure to concurrently execute multiple threads at hardware level which, usually, results in a very low context switching overhead. Simultaneous Multi-Threaded Processors (SMTPs) are superscalar processor architectures which adaptively exploit the coarse grain and the fine grain parallelism of applications, by simultaneously executing instructions from several thread contexts.In this thesis we make a case for using SMTPs and MTPs as NoC resources and show that such a multiprocessor architecture provides better time performances than an NoC with solely General-purpose Processors (GP). We have developed a methodology for task mapping and scheduling to an NoC with mixed SMTP, MTP and GP resources, which aims to maximize the time performance of concurrent applications and to satisfy their soft deadlines. The developed methodology was evaluated on many configurations of NoC-based platforms with SMTP, MTP and GP resources. The experimental results demonstrate that the use of SMTPs and MTPs in NoC platforms can significantly speed-up applications.
|
|
