The Experts below are selected from a list of 7290 Experts worldwide ranked by ideXlab platform
Samarjit Chakraborty - One of the best experts on this subject based on the ideXlab platform.
-
Exploiting GPU On-chip Shared Memory for Accelerating Schedulability Analysis
2010 International Symposium on Electronic System Design, 2010Co-Authors: Swaroop Nunna, Unmesh D. Bordoloi, Samarjit Chakraborty, Petru Eles, Zebo PengAbstract:Embedded electronic devices like mobile phones and automotive control units must perform under strict timing constraints. As such, Schedulability Analysis constitutes an important phase of the design cycle of these devices. Unfortunately, Schedulability Analysis for most realistic task models turn out to be computationally intractable (NP-hard). Naturally, in the recent past, different techniques have been proposed to accelerate Schedulability Analysis algorithms, including parallel computing on Graphics Processing Units (GPUs). However, applying traditional GPU programming methods in this context restricts the effective usage of on-chip memory and in turn imposes limitations on fully exploiting the inherent parallel processing capabilities of GPUs. In this paper, we explore the possibility of accelerating Schedulability Analysis algorithms on GPUs while exploiting the usage of on-chip memory. Experimental results demonstrate upto 9× speedup of our GPU-based algorithms over the implementations on sequential CPUs.
-
fast Schedulability Analysis using commodity graphics hardware
Embedded and Real-Time Computing Systems and Applications, 2007Co-Authors: Jimin Feng, Samarjit Chakraborty, Bertil Schmidt, Unmesh Weiguo Liu, Unmesh D. BordoloiAbstract:In this paper we explore the possibility of using commodity graphics processing units (GPUs) to speedup standard Schedulability Analysis algorithms. Our long-term goal is to exploit GPUs to accelerate common electronic design automation algorithms, most of which tend to be computationally expensive. Our main contribution in this paper is a reformulation of a standard demand bound criteria-based Schedulability Analysis algorithm as a streaming algorithm expressed in terms of computer graphics primitives. This allows the algorithm to be efficiently implemented on a GPU, thereby resulting in very attractive speedups.
-
Interactive Schedulability Analysis
ACM Transactions on Embedded Computing Systems, 2007Co-Authors: Unmesh D. Bordoloi, Samarjit ChakrabortyAbstract:A typical design process for real-time embedded systems involves choosing the values of certain system parameters and performing a Schedulability Analysis to determine whether all deadline constraints can be satisfied. If such an Analysis returns a negative answer, then some of the parameters are modified and the Analysis is invoked once again. This iteration is repeated until a schedulable design is obtained. However, the Schedulability Analysis problem for most task models is intractable (usually co-NP hard) and, hence, such an iterative design process is often very expensive. To get around this problem, we introduce the concept of “interactive” Schedulability Analysis. It is based on the observation that if only a small number of system parameters are changed, then it is not necessary to rerun the full Schedulability Analysis algorithm, thereby making the iterative design process considerably faster. We refer to this Analysis as being “interactive” because it is supposed to be run in an interactive mode. This concept is fairly general and can be applied to a wide variety of task models. In this paper, we have chosen the recurring real-time task model, because it can be used to represent realistic applications from the embedded systems domain (containing conditional branches and fine-grained deadline constraints). Our experimental results show that using our scheme can lead to more than 20× speedup for each invocation of the Schedulability Analysis algorithm, compared to the case where the full algorithm is run.
-
SYNASC - Path-Constrained Relaxed Schedulability Analysis
Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2007), 2007Co-Authors: Stefan Andrei, Samarjit ChakrabortyAbstract:The Schedulability Analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of Schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion of relaxed Schedulability, which is parameterized in terms of the number of paths in a task set. In the model we consider, each task is represented by a directed acyclic graph where the nodes of such a graph are annotated with execution times and deadlines. Our proposed notion of Schedulability allows a certain number of paths from each task graph to be non-schedulable. For describing the relaxed Schedulability Analysis, we formally define a measure called pseudo-K-Schedulability, which corresponds to the situation when the task set has exactly K schedulable paths. At one extreme is the classical notion of Schedulability Analysis, where the problem is NP hard in our and many other task models. At the other extreme of this spectrum we have the trivial notion of Schedulability Analysis, where no path needs to be schedulable. Problems in between allow for a flexible notion of Schedulability. This paper studies the relaxed Schedulability because not all paths in a code are executed. This paper shows a fundamental result, namely the membership of the pseudoSchedulability problem to the class of NP-hard problems.
-
RTCSA - Fast Schedulability Analysis Using Commodity Graphics Hardware
13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), 2007Co-Authors: Jimin Feng, Samarjit Chakraborty, Bertil Schmidt, Unmesh Weiguo Liu, Unmesh D. BordoloiAbstract:In this paper we explore the possibility of using commodity graphics processing units (GPUs) to speedup standard Schedulability Analysis algorithms. Our long-term goal is to exploit GPUs to accelerate common electronic design automation algorithms, most of which tend to be computationally expensive. Our main contribution in this paper is a reformulation of a standard demand bound criteria-based Schedulability Analysis algorithm as a streaming algorithm expressed in terms of computer graphics primitives. This allows the algorithm to be efficiently implemented on a GPU, thereby resulting in very attractive speedups.
Anatoly Bahmurov - One of the best experts on this subject based on the ideXlab platform.
-
stopwatch automata based model for efficient Schedulability Analysis of modular computer systems
Parallel Computing Technologies, 2017Co-Authors: Alevtina B Glonina, Anatoly BahmurovAbstract:In this paper we propose a stopwatch automata-based model of a modular computer system operation. This model provides an ability to perform Schedulability Analysis for a wide class of modular computer systems. It is formally proven that the model satisfies a set of correctness requirements. It is also proven that all the traces, generated by the model interpretation, are equivalent for Schedulability Analysis purposes. The traces equivalence allows to use any trace for Analysis and therefore the proposed approach is much more efficient than Model Checking, especially for parallel systems with many simultaneous events. The software implementation of the proposed approach is also presented in the paper.
-
PaCT - Stopwatch Automata-Based Model for Efficient Schedulability Analysis of Modular Computer Systems
Lecture Notes in Computer Science, 2017Co-Authors: Alevtina B Glonina, Anatoly BahmurovAbstract:In this paper we propose a stopwatch automata-based model of a modular computer system operation. This model provides an ability to perform Schedulability Analysis for a wide class of modular computer systems. It is formally proven that the model satisfies a set of correctness requirements. It is also proven that all the traces, generated by the model interpretation, are equivalent for Schedulability Analysis purposes. The traces equivalence allows to use any trace for Analysis and therefore the proposed approach is much more efficient than Model Checking, especially for parallel systems with many simultaneous events. The software implementation of the proposed approach is also presented in the paper.
Nan Guan - One of the best experts on this subject based on the ideXlab platform.
-
Schedulability Analysis of synchronous digraph real time tasks
Euromicro Conference on Real-Time Systems, 2016Co-Authors: Morteza Mohaqeqi, Jakaria Abdullah, Nan GuanAbstract:Real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real Time task model (DRT) to specify branching and loop structures of real-time embedded software. For independent DRT tasks, efficient techniques for Schedulability Analysis have been developed in previous work. In this paper, we extend the DRT model to specify inter-task synchronization through a rendezvous mechanism. We present an abstraction technique for static priority Schedulability Analysis of the corresponding tasks. Our experiments show that, despite the high computational complexity of the problem, the proposed technique scales very well for large sets of dependent tasks.
-
ECRTS - Schedulability Analysis of Synchronous Digraph Real-Time Tasks
2016 28th Euromicro Conference on Real-Time Systems (ECRTS), 2016Co-Authors: Morteza Mohaqeqi, Jakaria Abdullah, Nan GuanAbstract:Real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real Time task model (DRT) to specify branching and loop structures of real-time embedded software. For independent DRT tasks, efficient techniques for Schedulability Analysis have been developed in previous work. In this paper, we extend the DRT model to specify inter-task synchronization through a rendezvous mechanism. We present an abstraction technique for static priority Schedulability Analysis of the corresponding tasks. Our experiments show that, despite the high computational complexity of the problem, the proposed technique scales very well for large sets of dependent tasks.
-
Schedulability Analysis of global fixed priority or edf multiprocessor scheduling with symbolic model checking
International Symposium on Object Component Service-Oriented Real-Time Distributed Computing, 2008Co-Authors: Nan Guan, Qingxu DengAbstract:As Moore's law comes to an end, multi-processor (MP) systems are becoming increasingly important in embedded systems design, hence real-time Schedulability Analysis for MP systems has become an important research topic. In this paper, we present an exact method for Schedulability Analysis of global multiprocessor scheduling with either fixed-priority (FP) or earliest-deadline-first (EDF) algorithms using the model-checker NuSMV. Compared to safe but pessimistic Schedulability tests based on processor utilization bounds, model-checking can provide an exact answer to the Schedulability of a taskset, as well as quantitative information on each task's best-case and worst- case response times.
-
exact Schedulability Analysis for static priority global multiprocessor scheduling using model checking
Software Technologies for Embedded and Ubiquitous Systems, 2007Co-Authors: Nan Guan, Qingxu Deng, Shuaihong GaoAbstract:To determine Schedulability of priority-driven periodic tasksets on multi-processor systems, it is necessary to rely on utilization bound tests that are safe but pessimistic, since there is no known method for exact Schedulability Analysis for multi-processor systems analogous to the response time Analysis algorithm for single-processor systems. In this paper, we use model-checking to provide a technique for exact multiprocessor scheduability Analysis by modeling the real-time multi-tasking system with Timed Automata (TA), and transforming the Schedulability Analysis problem into the reachability checking problem of the TA model.
Marco Di Natale - One of the best experts on this subject based on the ideXlab platform.
-
assessing the pessimism of current multicore global fixed priority Schedulability Analysis
ACM Symposium on Applied Computing, 2018Co-Authors: Youcheng Sun, Marco Di NataleAbstract:This work provides a formal assessment on the pessimism of existing methods for the Schedulability Analysis of multicores with global fixed priority (FP) scheduling. We show how according to the existing Analysis methods for FP scheduling, it is relatively easy to define a simple task allocation strategy followed by local Analysis that dominates existing global-FP feasibility Analysis algorithms, in terms of deadline guarantees. Rather than being an indication of a true comparison between the effectiveness of local and global policies, we consider the result as an indication of the limited maturity of multicore global Analysis (and its outstanding pessimism). In addition, we show how a simple change in the task model, consisting in splitting the task execution and performing the Analysis in two stages, allows to provide a better global Schedulability Analysis that overcomes this limitation.
-
Schedulability Analysis of periodic tasks implementing synchronous finite state machines
Euromicro Conference on Real-Time Systems, 2012Co-Authors: Haibo Zeng, Marco Di NataleAbstract:Model-based design of embedded systems using Synchronous Reactive (SR) models is among the best practices for software development in the automotive and aeronautics industry. The correct implementation of an SR model must guarantee the synchronous assumption, that is, all the system reactions complete before the next event. This assumption can be verified using Schedulability Analysis, but the Analysis can be quite challenging when the system also consists of blocks implementing finite state machines, as in modern modeling tools like Simulink and SCADE. In this paper, we discuss the Schedulability Analysis of such systems, including the applicability of traditional task Analysis methods and an algorithmic solution to compute the exact demand and request bound functions. In addition, we define conditions for computing these functions using a periodic recurrent term, even when there is no cyclic recurrent behavior in the model.
-
UML for Real - Schedulability Analysis with UML
UML for Real, 2003Co-Authors: Marco Di Natale, Manas SaksenaAbstract:The growing complexity of real-time software is generating an increasing demand for (specialized) UML as a modeling language for real-time systems. Verification of non-functional properties is key in hard real-time systems, which are required to perform correctly both in the value and time domains. Schedulability Analysis provides algorithms and methods for assigning physical and logical resources to the software objects and for analyzing and guaranteeing their time properties at design time. Furthermore, it provides guidelines on the deployment of logical architecture into physical architecture. Unfortunately, UML behavioral models are based on an implicit eventtriggered model, quite unlike those assumed in real-time scheduling research. Furthermore, until the recent development of a specialized UML profile for Schedulability Analysis, the use of UML has been hindered by the lack of explicit support for common hard real-time abstractions. This chapter shows how fixed and dynamic priority scheduling theory can be applied to designs developed using a specialization of UML for real-time software. It provides a reference architecture for the development of real-time systems amenable to Schedulability Analysis and features a short survey on the most common real-time scheduling and Analysis concepts and policies.
Poul Hougaard - One of the best experts on this subject based on the ideXlab platform.
-
Schedulability Analysis using uppaal herschel planck case study
Leveraging Applications of Formal Methods, 2010Co-Authors: Marius Mikucionis, Kim Guldstrand Larsen, Jacob Illum Rasmussen, Brian Nielsen, Arne Skou, Steen Ulrik Palm, Jan Storbank Pedersen, Poul HougaardAbstract:We propose a modeling framework for performing Schedulability Analysis by using UPPAAL real-time model-checker [2]. The framework is inspired by a case study where Schedulability Analysis of a satellite system is performed. The framework assumes a single CPU hardware where a fixed priority preemptive scheduler is used in a combination with two resource sharing protocols and in addition voluntary task suspension is considered. The contributions include the modeling framework, its application on an industrial case study and a comparison of results with classical response time Analysis.
-
ISoLA (2) - Schedulability Analysis using Uppaal: Herschel-Planck case study
Lecture Notes in Computer Science, 2010Co-Authors: Marius Mikucionis, Kim Guldstrand Larsen, Jacob Illum Rasmussen, Brian Nielsen, Arne Skou, Steen Ulrik Palm, Jan Storbank Pedersen, Poul HougaardAbstract:We propose a modeling framework for performing Schedulability Analysis by using UPPAAL real-time model-checker [2]. The framework is inspired by a case study where Schedulability Analysis of a satellite system is performed. The framework assumes a single CPU hardware where a fixed priority preemptive scheduler is used in a combination with two resource sharing protocols and in addition voluntary task suspension is considered. The contributions include the modeling framework, its application on an industrial case study and a comparison of results with classical response time Analysis.
