Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:48:35Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:49:13Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) / Made available in DSpace on 2018-02-08T12:49:13Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5)
Previous issue date: 2017-09-29 / The power wall is a barrier to improvement in the processor design process due to the
power consumption of components. The production of energy optimum systems demands
knowledge of different disciplines. The usage of heterogeneous multicore platforms is appealing
for recent applications, e.g., hard real-time systems. The motivation is the potential
reduced energy consumption offered by such platforms. Hard real-time systems are
present in life critical environments. Reducing the energy consumption on such systems
is an onerous process. Scheduling becomes particularly challenging to improve system
utilization and minimize system energy consumption and peak temperature on such platforms,
specially subject to hard real-time constraints.
Therefore, we propose a study to effectively answer the pertinent research question: “How
to offer users timing correctness and guarantees of hard real-time systems executed on heterogeneous
multicore systems with energy and temperature constraints?”. Finding optimal
solutions for such question has still several open research questions.
The main aim of this thesis is to propose an energy optimization method for hard realtime
system on heterogeneous multicore platform demonstrating that it is possible to timely
compute timing correctness and guarantees using a sufficient and necessary condition; accounting
for energy, temperature, preemption, precedence, shared resources constraints,
and architectural interference. The proposal is a two fold approach. First, we investigate
the process of finding the optimal task to core and frequency to task processes by means
of applying exact schedulability tests for heterogeneous multicore platforms. Second, the
outcome of the optimization analysis shall be used as reference to the on-line scheduler.
We believe that we have achieved the main objective of this research by combining: (a)
schedulability analysis from hard real-time systems, (b) representative mathematical formulations,
based on integer linear programming, covering modern processors technological
characteristics and using a classical combinatorial mathematical formulation (Multilevel
Generalized Assignment Problem), and (c) robust exact implicit enumeration algorithmic
strategies from combinatorial optimization, such as branch-and-cut and branch-and-price.
The systematic literature review in the research subject reveals that the field has open
questions to be answered. For instance, to the knowledge of the author only five works
in the state-of-the-art literature deal with the problem by providing optimal solutions.
Typically, the existing approaches focus on either heuristics or approximation algorithms.
Also, only one work has a proposal to evaluate the schedulability in this scenario with
an exact test. The typical formulation in the specialized literature is a 0/1 integer linear
programming model which considers a continuous processor frequency domain and determines
a single operating frequency per processor. One of the hypotheses tested in this
research is: stronger feasibility analysis offers tighter bounds for the problem. We believe that this can be observed, for example, in the results produced by solvers for fixed priority
schedulers, by means of an analysis based on a comparative study. By applying less accurate
schedulability tests, such as utilization based, the solvers take longer to converge to
optimal solutions, when compared to solvers that apply exact schedulability tests based
on response time analysis. Another hypothesis tested in this research is: practical instances
of the problem are timely solvable to optimal. We have experimented, by means of a comparative
study, on finding feasible solutions for workload for fixed priority schedulers with
up to 50 tasks distributed on four processors with seven different available frequencies. On
independent hard real-time tasks scheduled using EDF policy, we found optimal distribution
of up to 90 tasks on four processors with seven different available frequencies. In both
cases, the solutions were found within 30 min of execution time. Similarly, on dependent
tasks workload, we have optimally distributed 22 tasks, from an automotive control hard
real-time application, on four processors with seven different available frequencies, with
two shared resources and 23 precedence constraints within 1.5 h. We consider a few hours
in the design phase a price worth paying in this context. / .
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/6148 |
| Date | 29 September 2017 |
| Creators | Valentin, Eduardo Bezerra, 92-36710870 |
| Contributors | secretaria@icomp.ufam.edu.br, Barreto, Raimundo da Silva, Rodrigues, Rosiane de Freitas, Carvalho, José Reginaldo Hughes, Cordeiro, Lucas Carvalho, Oliveira, Rômulo Silva de, Azevedo, Carlos Renato Belo |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600, 500, 4163267508810754609 |
Page generated in 0.004 seconds