liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Cortés, Luis Alejandro
Alternative names
Publications (10 of 25) Show all publications
Cortes, L.-A., Eles, P. I. & Peng, Z. (2006). A Quasi-Static Approach to Minimizing Energy Consumption in Real-Time Systems under Reward Constraints. In: 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2006. Paper presented at 12th International Conference on Embedded and Real-Time Computing Systems and Applications, 16-18 August 2006, Sydney, Australia (pp. 279-286). IEEE Computer Society
Open this publication in new window or tab >>A Quasi-Static Approach to Minimizing Energy Consumption in Real-Time Systems under Reward Constraints
2006 (English)In: 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2006, IEEE Computer Society, 2006, p. 279-286Conference paper, Published paper (Refereed)
Abstract [en]

In some real-time applications, it is desirable to trade off precision for timeliness. For such systems, considered typically under the Imprecise Computation model, a function assigns reward to the application depending on the amount of computation allotted to it. Also, many such applications run on battery-powered devices where the energy consumption is of utmost importance. We address in this paper the problem of energy minimization for Imprecise-Computation systems that have reward and time constraints. We propose a Quasi-Static (QS) approach that exploits, with low on-line overhead, the dynamic slack that arises from variations in the actual number of execution cycles: first, at design-time, a set of solutions are computed and stored (off-line phase); second, the selection among the precomputed assignments is left for run-time, based on actual values of time and reward (on-line phase).

Place, publisher, year, edition, pages
IEEE Computer Society, 2006
Keywords
real-time systems, embedded systems, quasi-static scheduling, voltage scaling, energy consumption
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-35459 (URN)10.1109/RTCSA.2006.8 (DOI)000240851900039 ()26912 (Local ID)0-7695-2676-4 (ISBN)26912 (Archive number)26912 (OAI)
Conference
12th International Conference on Embedded and Real-Time Computing Systems and Applications, 16-18 August 2006, Sydney, Australia
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2018-01-13
Varea, M., Al-Hashimi, B., Cortes, L.-A., Eles, P. I. & Peng, Z. (2006). Dual Flow Nets: Modelling the Control/Data-Flow Relation in Embedded Systems. ACM Transactions on Embedded Computing Systems, 5(1), 54-81
Open this publication in new window or tab >>Dual Flow Nets: Modelling the Control/Data-Flow Relation in Embedded Systems
Show others...
2006 (English)In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 5, no 1, p. 54-81Article in journal (Refereed) Published
Abstract [en]

This paper addresses the interrelation between control and data flow in embedded system models through a new design representation, called Dual Flow Net (DFN). A modeling formalism with a very close-fitting control and data flow is achieved by this representation, as a consequence of enhancing its underlying Petri net structure. The work presented in this paper does not only tackle the modeling side in embedded systems design, but also the validation of embedded system models through formal methods. Various introductory examples illustrate the applicability of the DFN principles, whereas the capability of the model to with complex designs is demonstrated through the design and verification of a real-life Ethernet coprocessor.

Keywords
embedded systems, verification, control flow, dual flow net, Petri net, design modeling
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-28505 (URN)10.1145/1132357.1132360 (DOI)13654 (Local ID)13654 (Archive number)13654 (OAI)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2018-01-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2005). Quasi-Static Assignment of Voltages and Optional Cycles for Maximizing Rewards in Real-Time Systems with Energy Constraints. In: 42nd Design Automation Conference,2005: . Paper presented at 42nd Design Automation Conference,2005 (pp. 889). Anaheim, CA, USA: IEEE Computer Society Press
Open this publication in new window or tab >>Quasi-Static Assignment of Voltages and Optional Cycles for Maximizing Rewards in Real-Time Systems with Energy Constraints
2005 (English)In: 42nd Design Automation Conference,2005, Anaheim, CA, USA: IEEE Computer Society Press , 2005, p. 889-Conference paper, Published paper (Refereed)
Abstract [en]

There exist real-time systems for which it is possible to trade off precision for timeliness. In these cases, a function assigns reward to the application depending on the amount of computation allotted to it. At the same time, many such applications run on battery-powered devices with stringent energy constraints. This paper addresses the problem of maximizing rewards subject to time and energy constraints. We propose a quasi-static approach where the problem is solved in two steps: first, at design-time, a number of solutions are computed and stored (off-line phase); second, one of the precomputed solutions is selected at run-time based on actual values of time and energy (on-line phase). Thus our approach is able to exploit, with low on-line overhead, the dynamic slack caused by tasks executing less number of cycles than in the worst case. We conduct numerous experiments in order to show the advantages of our approach.

Place, publisher, year, edition, pages
Anaheim, CA, USA: IEEE Computer Society Press, 2005
Keywords
real-time systems, quasi-static scheduling, energy optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-24587 (URN)10.1145/1065579.1065813 (DOI)6762 (Local ID)1-59593-058-2 (ISBN)6762 (Archive number)6762 (OAI)
Conference
42nd Design Automation Conference,2005
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2005). Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks. In: 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05,2005: . Paper presented at 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05 (pp. 422). Hong Kong: IEEE Computer Society Press
Open this publication in new window or tab >>Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks
2005 (English)In: 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05,2005, Hong Kong: IEEE Computer Society Press , 2005, p. 422-Conference paper, Published paper (Refereed)
Abstract [en]

We address in this paper the problem of scheduling for multiprocessor real-time systems with hard and soft tasks. Utility functions are associated to soft tasks to capture their relative importance and how the quality of results is affected when a soft deadline is missed. The problem is to find a task execution order that maximizes the total utility and guarantees the hard deadlines. In order to account for actual execution times, we consider time intervals for tasks rather than fixed execution times. A single static schedule computed off-line is pessimistic, while a purely on-line approach, which computes a new schedule every time a task completes, incurs an unacceptable overhead. We propose therefore a quasi-static solution where a number of schedules are computed at design time, leaving for run-time only the selection of a particular schedule, based on the actual execution times. We propose an exact algorithm as well as heuristics that tackle the time and memory complexity of the problem. We evaluate our approach through synthetic examples and a realistic application.

Place, publisher, year, edition, pages
Hong Kong: IEEE Computer Society Press, 2005
Keywords
real-time systems, quasi-static scheduling, hard tasks, soft tasks
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-28504 (URN)10.1109/RTCSA.2005.72 (DOI)13653 (Local ID)0-7695-2346-3 (ISBN)13653 (Archive number)13653 (OAI)
Conference
11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2018-01-13
Cortés, L. A. (2005). Verification and Scheduling Techniques for Real-Time Embedded Systems. (Doctoral dissertation). Institutionen för datavetenskap
Open this publication in new window or tab >>Verification and Scheduling Techniques for Real-Time Embedded Systems
2005 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Embedded computer systems have become ubiquitous. They are used in a wide spectrum of applications, ranging from household appliances and mobile devices to vehicle controllers and medical equipment. This dissertation deals with design and verification of embedded systems, with a special emphasis on the real-time facet of such systems, where the time at which the results of the computations are produced is as important as the logical values of these results. Within the class of real-time systems two categories, namely hard real-time systems and soft real-time systems, are distinguished and studied in this thesis.

First, we propose modeling and verification techniques targeted towards hard real-time systems, where correctness, both logical and temporal, is of prime importance. A model of computation based on Petri nets is defined. The model can capture explicit timing information, allows tokens to carry data, and supports the concept of hierarchy. Also, an approach to the formal verification of systems represented in our modeling formalism is introduced, in which model checking is used to prove whether the system model satisfies its required properties expressed as temporal logic formulas. Several strategies for improving verification efficiency are presented and evaluated.

Second, we present scheduling approaches for mixed hard/soft real-time systems. We study systems that have both hard and soft real-time tasks and for which the quality of results (in the form of utilities) depends on the completion time of soft tasks. Also, we study systems for which the quality of results (in the form of rewards) depends on the amount of computation allotted to tasks. We introduce quasi-static techniques, which are able to exploit at low cost the dynamic slack caused by variations in actual execution times, for maximizing utilities/rewards and for minimizing energy.

Numerous experiments, based on synthetic benchmarks and realistic case studies, have been conducted in order to evaluate the proposed approaches. The experimental results show the merits and worthiness of the techniques introduced in this thesis and demonstrate that they are applicable on real-life examples.

Place, publisher, year, edition, pages
Institutionen för datavetenskap, 2005. p. 213
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 920
Keywords
Computer systems, Embedded computer systems, real-time systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-5023 (URN)91-85297-21-6 (ISBN)
Public defence
2005-03-02, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Supervisors
Available from: 2005-03-23 Created: 2005-03-23 Last updated: 2020-04-01
Cortes, L.-A., Eles, P. I. & Peng, Z. (2004). Combining Static and Dynamic Scheduling for Real-Time Systems. In: Workshop on Software Analysis and Development for Pervasive Systems SONDA 2004,2004 (pp. 32). Southampton, UK: University of Southampton
Open this publication in new window or tab >>Combining Static and Dynamic Scheduling for Real-Time Systems
2004 (English)In: Workshop on Software Analysis and Development for Pervasive Systems SONDA 2004,2004, Southampton, UK: University of Southampton , 2004, p. 32-Conference paper, Published paper (Refereed)
Abstract [en]

We address in this paper the combination of static and dynamic scheduling into an approach called quasi-static scheduling, in the context of real-time systems composed of hard and soft tasks. For the particular problem discussed in this paper, a single static schedule is too pessimistic while a purely dynamic scheduling approach causes a very high on-line overhead. In the proposed quasi-static solution we compute at design-time a set of schedules, and leave for run-time only the selection of a particular schedule based on the actual execution times. We propose an exact algorithm as well as heuristics that tackle the time and memory complexity of the problem. The approach is evaluated through synthetic examples.

Place, publisher, year, edition, pages
Southampton, UK: University of Southampton, 2004
Keywords
quasi-static scheduling, embedded systems, dynamic scheduling, static scheduling
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-23202 (URN)2613 (Local ID)2613 (Archive number)2613 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2004). Quasi-Static Scheduling for Real-Time Systems with Hard and Soft Tasks. In: Design, Automation and Test in Europe DATE 2004,2004: . Paper presented at Design, Automation and Test in Europe DATE 2004 (pp. 1176). Paris, France: IEEE Computer Society Press
Open this publication in new window or tab >>Quasi-Static Scheduling for Real-Time Systems with Hard and Soft Tasks
2004 (English)In: Design, Automation and Test in Europe DATE 2004,2004, Paris, France: IEEE Computer Society Press , 2004, p. 1176-Conference paper, Published paper (Refereed)
Abstract [en]

This paper addresses the problem of scheduling for real-time systems that include both hard and soft tasks. The relative importance of soft tasks and how the quality of results is affected when missing a soft deadline are captured by utility functions associated to soft tasks. Thus the aim is to find the execution order of tasks that makes the total utility maximum and guarantees hard deadlines. We consider time intervals rather than fixed execution times for tasks. Since a purely off-line solution is too pessimistic and a purely on-line approach incurs an unacceptable overhead due to the high complexity of the problem, we propose a quasi-static approach where a number of schedules are prepared at design-time and the decision of which of them to follow is taken at run-time based on the actual execution times. We propose an exact algorithm as well as different heuristics for the problem addressed in this paper.

Place, publisher, year, edition, pages
Paris, France: IEEE Computer Society Press, 2004
Keywords
scheduling, quasi-static, hard task, soft tasks, embedded systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-23289 (URN)10.1109/DATE.2004.1269051 (DOI)2715 (Local ID)0-7695-2085-5 (ISBN)2715 (Archive number)2715 (OAI)
Conference
Design, Automation and Test in Europe DATE 2004
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2004). Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks. In: The IEEE International Workshop on Electronic Design, Test and Applications DELTA 2004,2004: . Paper presented at The IEEE International Workshop on Electronic Design, Test and Applications DELTA 2004 (pp. 115-120).
Open this publication in new window or tab >>Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks
2004 (English)In: The IEEE International Workshop on Electronic Design, Test and Applications DELTA 2004,2004, 2004, p. 115-120Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we address the problem of static scheduling of real-time systems that include both hard and soft tasks. We consider that hard as well as soft tasks are periodic and that there exist data dependencies among tasks. In order to capture the relative importance of soft tasks and how the quality of results is affected when missing a soft deadline, we use utility functions associated to soft tasks. Thus our objective is to find an execution order for tasks that maximizes the total utility and at the same time guarantees hard deadlines. We use the expected duration of tasks for evaluating utility functions whereas we use the maximum duration of tasks for ensuring that hard deadlines are always met. We present an algorithm for finding the optimal schedule and also different heuristics that find near-optimal solutions at reasonable computational cost. The proposed algorithms are evaluated using a large number of synthetic examples.

Keywords
static scheduling, hard tasks, soft tasks, real-time systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-23290 (URN)10.1109/DELTA.2004.10041 (DOI)2716 (Local ID)0-7695-2081-2 (ISBN)2716 (Archive number)2716 (OAI)
Conference
The IEEE International Workshop on Electronic Design, Test and Applications DELTA 2004
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2003). Modeling and formal verification of embedded systems based on a Petri net representation. Journal of systems architecture, 49(12-15), 571-598
Open this publication in new window or tab >>Modeling and formal verification of embedded systems based on a Petri net representation
2003 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 49, no 12-15, p. 571-598Article in journal (Refereed) Published
Abstract [en]

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined 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 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 tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications. © 2003 Elsevier B.V. All rights reserved.

Keywords
Embedded systems, Formal verification, Model checking, Modeling, Petri nets
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-46395 (URN)10.1016/S1383-7621(03)00096-1 (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-13
Cortes, L.-A., Eles, P. I. & Peng, Z. (2003). Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks. Linköping, Sweden: Embedded Systems Lab, IDA, Linköping University
Open this publication in new window or tab >>Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks
2003 (English)Report (Other academic)
Abstract [en]

We address in this report the problem of scheduling for multiprocessor real-time systems comprised of hard and soft tasks. We use utility functions associated to soft tasks that capture their relative importance and how the quality of results is influenced when a soft deadline is missed. The problem is thus finding a task execution order that maximizes the total utility and guarantees meeting the hard deadlines. We consider time intervals rather than fixed execution times for tasks. On the one hand, a single static schedule computed off-line is too pessimistic. On the other hand, a purely on-line approach, which computes a new schedule every time a task completes considering the actual conditions, incurs an overhead that is unacceptable due to the high complexity of the problem. We propose a quasi-static solution where a number of schedules are computed at design-time, letting only for run-time the selection of a particular schedule based on the actual execution times. We propose an exact algorithm as well as heuristics that tackle the time and memory complexity of the problem. We evaluate our approach through synthetic examples and a realistic application.

Place, publisher, year, edition, pages
Linköping, Sweden: Embedded Systems Lab, IDA, Linköping University, 2003
Keywords
quasi-static scheduling, real-time systems, hard tasks, soft tasks
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-23311 (URN)2739 (Local ID)2739 (Archive number)2739 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Organisations

Search in DiVA

Show all publications