| 1. |
- Horga, Adrian, 1989-
(author)
-
Performance and Security Analysis for GPU-Based Applications
- 2022
-
Doctoral thesis (other academic/artistic)abstract
- Graphics Processing Units (GPUs) are becoming more and more prevalent in general-purpose computing. GPUs are used in areas from embedded systems to super-computing. With applications ranging from fluid dynamics simulations to image processing, machine learning, and encryption, GPU programs need to satisfy not only performance requirements but also various other non-functional constraints. Besides the aspects regarding performance, also security and the worst case execution time (WCET) need to be considered for such GPU applications. In our work, we study such non-functional properties and present approaches to detect and solve issues regarding them.First, we focus on the performance of GPU applications by detecting cache related performance bottlenecks. We detect the root causes of such bottlenecks and provide solutions to reduce their negative impact on performance. We also discuss and compare the impact of cache replacement policies and thread scheduling policies on the performance of GPU applications.Then, we present a measurement-based technique, which combines symbolic execution and genetic algorithms, and is used for estimating the WCET of GPU programs. Our proposed technique helps to produce test inputs that lead towards the WCET of a program. We also propose solutions to alleviate the inherent complexity of GPU programs due to branching behavior and high number of threads running in parallel.In continuation, we propose a technique to expose the side-channel leakage of shared memory in GPU implementations of cryptographic algorithms. We evaluate the robustness of such algorithms in the context of shared memory side-channel leakage. Also, we discuss the security and side-channel leakage for different implementations of the same algorithm.Finally, a formal approach is presented for the detection of GPU shared memory bank conflicts. We explore and discuss the impact of such conflicts on the performance and security of GPU applications. We show how our approach can help in producing inputs that can lead towards the WCET. We also discuss how our approach can be used to evaluate the leakage of the shared memory side-channel for GPU implementations of cryptographic algorithms.
|
|
| 2. |
- Ganjei, Zeinab, 1989-
(author)
-
Parameterized Verification of Synchronized Concurrent Programs
- 2021
-
Doctoral thesis (other academic/artistic)abstract
- There is currently an increasing demand for concurrent programs. Checking the correctness of concurrent programs is a complex task due to the interleavings of processes. Sometimes, violation of the correctness properties in such systems causes human or resource losses; therefore, it is crucial to check the correctness of such systems. Two main approaches to software analysis are testing and formal verification. Testing can help discover many bugs at a low cost. However, it cannot prove the correctness of a program. Formal verification, on the other hand, is the approach for proving program correctness. Model checking is a formal verification technique that is suitable for concurrent programs. It aims to automatically establish the correctness (expressed in terms of temporal properties) of a program through an exhaustive search of the behavior of the system. Model checking was initially introduced for the purpose of verifying finite‐state concurrent programs, and extending it to infinite‐state systems is an active research area.In this thesis, we focus on the formal verification of parameterized systems. That is, systems in which the number of executing processes is not bounded a priori. We provide fully-automatic and parameterized model checking techniques for establishing the correctness of safety properties for certain classes of concurrent programs. We provide an open‐source prototype for every technique and present our experimental results on several benchmarks.First, we address the problem of automatically checking safety properties for bounded as well as parameterized phaser programs. Phaser programs are concurrent programs that make use of the complex synchronization construct of Habanero Java phasers. For the bounded case, we establish the decidability of checking the violation of program assertions and the undecidability of checking deadlock‐freedom. For the parameterized case, we study different formulations of the verification problem and propose an exact procedure that is guaranteed to terminate for some reachability problems even in the presence of unbounded phases and arbitrarily many spawned processes. Second, we propose an approach for automatic verification of parameterized concurrent programs in which shared variables are manipulated by atomic transitions to count and synchronize the spawned processes. For this purpose, we introduce counting predicates that related counters that refer to the number of processes satisfying some given properties to the variables that are directly manipulated by the concurrent processes. We then combine existing works on the counter, predicate, and constrained monotonic abstraction and build a nested counterexample‐based refinement scheme to establish correctness. Third, we introduce Lazy Constrained Monotonic Abstraction for more efficient exploration of well‐structured abstractions of infinite‐state non‐monotonic systems. We propose several heuristics and assess the efficiency of the proposed technique by extensive experiments using our open‐source prototype. Lastly, we propose a sound but (in general) incomplete procedure for automatic verification of safety properties for a class of fault‐tolerant distributed protocols described in the Heard‐Of (HO for short) model. The HO model is a popular model for describing distributed protocols. We propose a verification procedure that is guaranteed to terminate even for unbounded number of the processes that execute the distributed protocol.
|
|
| 3. |
- Zhou, Yuanbin, 1991-
(author)
-
Synthesis of Safety-Critical Real-Time Systems
- 2022
-
Doctoral thesis (other academic/artistic)abstract
- Modern safety-critical real-time systems are becoming more and more complex, due to sophisticated applications such as advanced driving assistance, automated driving, advanced infotainment, and applications involving machine learning and deep learning. This has led to increased requirements for the communication infrastructures. Real-time bus-based communication techniques, such as CAN and FlexRay, have been widely adopted for decades, due to their low cost and reliable communication capability. However, the bandwidth provided by these technologies is often not enough for modern safety-critical systems. Time-Sensitive Networking (TSN) is a promising technique that can handle the increasing bandwidth requirements, while meeting real-time constraints and providing Ethernet compatible solutions. We have studied the synthesis of schedules and routes for TSN, in order to fulfill timing and reliability requirements for safety-critical systems. Functional safety is an important goal for such systems, to ensure that no unreasonable risks are taken. This involves handling random and systematic faults, both of which are considered in this work. We synthesize schedules and routes for TSN so that the probability of faulty transmission due to random faults is below a certain threshold.ASIL Decomposition, introduced in the automotive industry, is applied to handle systematic faults, while achieving overall cost minimization. In order to improve schedulability, preemption support in TSN has also been studied. Heuristic algorithms are proposed for all the above contributions to address scalability issues characterized for the constrained synthesis and optimization problem addressed.Traditional designs for safety-critical systems usually deploy a federated architecture, where several processors are available and each processor implements one dedicated function. An important goal is to achieve fault containment. However, due to the increasing complexity of modern safety-critical systems, this architecture is no longer scalable. Therefore, several tasks with different criticality levels are usually integrated on the same computing platform. A key aspect for such systems is to achieve the required independence between tasks at different criticality levels and to guarantee that they do not interfere each other. We have developed a partitioned scheduling technique for mixed-criticality systems to achieve temporal independence, while minimizing the CPU usage.
|
|
| 4. |
- Aghaee Ghaleshahi, Nima, 1980-
(author)
-
Thermal Issues in Testing of Advanced Systems on Chip
- 2015
-
Doctoral thesis (other academic/artistic)abstract
- Many cutting-edge computer and electronic products are powered by advanced Systems-on-Chip (SoC). Advanced SoCs encompass superb performance together with large number of functions. This is achieved by efficient integration of huge number of transistors. Such very large scale integration is enabled by a core-based design paradigm as well as deep-submicron and 3D-stacked-IC technologies. These technologies are susceptible to reliability and testing complications caused by thermal issues. Three crucial thermal issues related to temperature variations, temperature gradients, and temperature cycling are addressed in this thesis.Existing test scheduling techniques rely on temperature simulations to generate schedules that meet thermal constraints such as overheating prevention. The difference between the simulated temperatures and the actual temperatures is called temperature error. This error, for past technologies, is negligible. However, advanced SoCs experience large errors due to large process variations. Such large errors have costly consequences, such as overheating, and must be taken care of. This thesis presents an adaptive approach to generate test schedules that handle such temperature errors.Advanced SoCs manufactured as 3D stacked ICs experience large temperature gradients. Temperature gradients accelerate certain early-life defect mechanisms. These mechanisms can be artificially accelerated using gradient-based, burn-in like, operations so that the defects are detected before shipping. Moreover, temperature gradients exacerbate some delay-related defects. In order to detect such defects, testing must be performed when appropriate temperature-gradients are enforced. A schedule-based technique that enforces the temperature-gradients for burn-in like operations is proposed in this thesis. This technique is further developed to support testing for delay-related defects while appropriate gradients are enforced.The last thermal issue addressed by this thesis is related to temperature cycling. Temperature cycling test procedures are usually applied to safety-critical applications to detect cycling-related early-life failures. Such failures affect advanced SoCs, particularly through-silicon-via structures in 3D-stacked-ICs. An efficient schedule-based cycling-test technique that combines cycling acceleration with testing is proposed in this thesis. The proposed technique fits into existing 3D testing procedures and does not require temperature chambers. Therefore, the overall cycling acceleration and testing cost can be drastically reduced.All the proposed techniques have been implemented and evaluated with extensive experiments based on ITC’02 benchmarks as well as a number of 3D stacked ICs. Experiments show that the proposed techniques work effectively and reduce the costs, in particular the costs related to addressing thermal issues and early-life failures. We have also developed a fast temperature simulation technique based on a closed-form solution for the temperature equations. Experiments demonstrate that the proposed simulation technique reduces the schedule generation time by more than half.
|
|
| 5. |
- Aminifar, Amir, 1987-
(author)
-
Analysis, Design, and Optimization of Embedded Control Systems
- 2016
-
Doctoral thesis (other academic/artistic)abstract
- Today, many embedded or cyber-physical systems, e.g., in the automotive domain, comprise several control applications, sharing the same platform. It is well known that such resource sharing leads to complex temporal behaviors that degrades the quality of control, and more importantly, may even jeopardize stability in the worst case, if not properly taken into account.In this thesis, we consider embedded control or cyber-physical systems, where several control applications share the same processing unit. The focus is on the control-scheduling co-design problem, where the controller and scheduling parameters are jointly optimized. The fundamental difference between control applications and traditional embedded applications motivates the need for novel methodologies for the design and optimization of embedded control systems. This thesis is one more step towards correct design and optimization of embedded control systems.Offline and online methodologies for embedded control systems are covered in this thesis. The importance of considering both the expected control performance and stability is discussed and a control-scheduling co-design methodology is proposed to optimize control performance while guaranteeing stability. Orthogonal to this, bandwidth-efficient stabilizing control servers are proposed, which support compositionality, isolation, and resource-efficiency in design and co-design. Finally, we extend the scope of the proposed approach to non-periodic control schemes and address the challenges in sharing the platform with self-triggered controllers. In addition to offline methodologies, a novel online scheduling policy to stabilize control applications is proposed.
|
|
| 6. |
- Aysan, Hüseyin, 1982-
(author)
-
Fault-Tolerance Strategies and Probabilistic Guarantees for Real-Time Systems
- 2012
-
Doctoral thesis (other academic/artistic)abstract
- Ubiquitous deployment of embedded systems is having a substantial impact on our society, since they interact with our lives in many critical real-time applications. Typically, embedded systems used in safety or mission critical applications (e.g., aerospace, avionics, automotive or nuclear domains) work in harsh environments where they are exposed to frequent transient faults such as power supply jitter, network noise and radiation. They are also susceptible to errors originating from design and production faults. Hence, they have the design objective to maintain the properties of timeliness and functional correctness even under error occurrences. Fault-tolerance plays a crucial role towards achieving dependability, and the fundamental requirement for the design of effective and efficient fault-tolerance mechanisms is a realistic and applicable model of potential faults and their manifestations. An important factor to be considered in this context is the random nature of faults and errors, which, if addressed in the timing analysis by assuming a rigid worst-case occurrence scenario, may lead to inaccurate results. It is also important that the power, weight, space and cost constraints of embedded systems are addressed by efficiently using the available resources for fault-tolerance. This thesis presents a framework for designing predictably dependable embedded real-time systems by jointly addressing the timeliness and the reliability properties. It proposes a spectrum of fault-tolerance strategies particularly targeting embedded real-time systems. Efficient resource usage is attained by considering the diverse criticality levels of the systems' building blocks. The fault-tolerance strategies are complemented with the proposed probabilistic schedulability analysis techniques, which are based on a comprehensive stochastic fault and error model.
|
|
| 7. |
- Bao, Min, 1981-
(author)
-
System-Level Techniques for Temperature-Aware Energy Optimization
- 2010
-
Licentiate thesis (other academic/artistic)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.
|
|
| 8. |
- Bujosa Mateu, Daniel
(author)
-
Enhancing TSN Adoption by Industry : Tools to Support Migrating Ethernet-based Legacy Networks into TSN
- 2023
-
Licentiate thesis (other academic/artistic)abstract
- New technologies present opportunities and challenges for industries. One major challenge is the ease, or even feasibility, of its adoption. The Time-Sensitive Networking (TSN) standards offer a range of features relevant to various applications and are key for the transition to Industry 4.0. These features include deterministic zero-jitter, low-latency data transmission, transmission of traffic with various levels of time-criticality on the same network, fault tolerance mechanisms, and advanced network management allowing dynamic reconfiguration.This thesis aims to develop tools that enable the industry to adopt TSN easily and efficiently. Specifically, we create tools that facilitate the migration of legacy networks to TSN, enabling the preservation of most of the legacy systems and solutions while reducing costs and adoption time. Firstly, we introduce LETRA (Legacy Ethernet-based Traffic Mapping Tool), a tool for mapping Ethernet-based legacy traffic to the new TSN traffic classes. Secondly, we develop HERMES (Heuristic Multi-queue Scheduler), a heuristic Time-Triggered (TT) traffic scheduler that can meet the characteristics of legacy systems and provide quick results suitable for reconfiguration. Thirdly, we develop TALESS (TSN with Legacy End-Stations Synchronization), a mechanism to avoid adverse consequences caused by the lack of synchronization between legacy systems and TSN-based ones, as not all legacy systems need to support the TSN synchronization mechanisms. Finally, we improve Stream Reservation Protocol (SRP) to enhance Audio-Video Bridging (AVB) traffic configuration in terms of termination and consistency.
|
|
| 9. |
- He, Zhiyuan, 1976-
(author)
-
Temperature Aware and Defect-Probability Driven Test Scheduling for System-on-Chip
- 2010
-
Doctoral thesis (other academic/artistic)abstract
- The high complexity of modern electronic systems has resulted in a substantial increase in the time-to-market as well as in the cost of design, production, and testing. Recently, in order to reduce the design cost, many electronic systems have employed a core-based system-on-chip (SoC) implementation technique, which integrates pre-defined and pre-verified intellectual property cores into a single silicon die. Accordingly, the testing of manufactured SoCs adopts a modular approach in which test patterns are generated for individual cores and are applied to the corresponding cores separately. Among many techniques that reduce the cost of modular SoC testing, test scheduling is widely adopted to reduce the test application time. This thesis addresses the problem of minimizing the test application time for modular SoC tests with considerations on three critical issues: high testing temperature, temperature-dependent failures, and defect probabilities.High temperature occurs in testing modern SoCs and it may cause damages to the cores under test. We address the temperature-aware test scheduling problem aiming to minimize the test application time and to avoid the temperature of the cores under test exceeding a certain limit. We have developed a test set partitioning and interleaving technique and a set of test scheduling algorithms to solve the addressed problem.Complicated temperature dependences and defect-induced parametric failures are more and more visible in SoCs manufactured with nanometer technology. In order to detect the temperature-dependent defects, a chip should be tested at different temperature levels. We address the SoC multi-temperature testing issue where tests are applied to a core only when the temperature of that core is within a given temperature interval. We have developed test scheduling algorithms for multi-temperature testing of SoCs.Volume production tests often employ an abort-on-first-fail (AOFF) approach which terminates the chip test as soon as the first fault is detected. Defect probabilities of individual cores in SoCs can be used to compute the expected test application time of modular SoC tests using the AOFF approach. We address the defect-probability driven SoC test scheduling problem aiming to minimize the expected test application time with a power constraint. We have proposed techniques which utilize the defect probability to generate efficient test schedules.Extensive experiments based on benchmark designs have been performed to demonstrate the efficiency and applicability of the developed techniques.
|
|
| 10. |
- Holsmark, Rickard, 1970-
(author)
-
Deadlock Free Routing in Mesh Networks on Chip with Regions
- 2009
-
Licentiate thesis (other academic/artistic)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.
|
|
