Task Assignment Algorithms for Heterogeneous Multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising a constant number (denoted by t) of distinct types of processors—such a platform is referred to as a t-type platform. We present two algorithms, LPGIM and LPGNM, each providing the following guarantee. For a given t-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet their deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then: (i) LPGIM succeeds in finding such an assignment where the same restriction on task migration applies (intra-migrative) but given a platform in which only one processor of each type is 1 + α × t-1/t times faster and (ii) LPGNM succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which every processor is 1 + α times faster. The parameter α is a property of the task set; it is the maximum of all the task utilizations that are no greater than one. To the best of our knowledge, for t-type heterogeneous multiprocessors: (i) for the problem of intra-migrative task assignment, no previous algorithm exists with a proven bound and hence our algorithm, LPGIM, is the first of its kind and (ii) for the problem of non-migrative task assignment, our algorithm, LPGNM, has superior performance compared to state-of-the-art.

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set τ of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m k processors of type-k, where k∈{1,2,…,t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by R. For each task τ i , there is a resource set R i ⊆R such that for each job of τ i , during one phase of its execution, the job requests to hold the resource set R i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R i and (ii) at all times, when a job of τ i holds R i , no other job holds any resource in R i . Each job of task τ i may request the resource set R i at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance. We propose an algorithm, LP-EE-vpr, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors 4×(1+MAXP×⌈|P|×MAXPmin{m1,m2,…,mt}⌉) times as fast. (Here MAXP and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to 4×(1+⌈|R|min{m1,m2,…,mt}⌉). To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.

Estrutura a partir do Movimento em Sistemas Autónomos

Mestrado em Engenharia Electrotécnica e de Computadores - Ramo de Sistemas Autónomos

Alternativas Processuais e Valorização de Correntes da Refinaria de Matosinhos.

Evolução, ato ou efeito de evoluir, sequência de transformações, desenvolvimento progressivo. Se tudo à nossa volta se transforma, a indústria tem de acompanhar esse sistema evolutivo, tornando assim imprescindível alterar ou melhorar processos de produção quando estes não se enquadram com a realidade, ou porque o mercado se altera, ou porque as necessidades mudam, ou por simplesmente ser mais rentável. Sendo a Galp Energia uma empresa que se encontra sempre na vanguarda da evolução tecnológica, encontra no Departamento de Engenharia Química do Instituto Superior de Engenharia do Porto um aliado na procura do melhor modo de valorizar os seus produtos. A Refinaria de Matosinhos tem atualmente duas correntes de gasolina leve e uma de refinado que apresentam grande potencialidade de valorização. Parte destas correntes incorporam atualmente a pool de nafta química da refinaria que é vendida à Repsol Polímeros. O desafio que é proposto baseia-se em valorizar essas correntes através da sua isomerização aumentando o seu RON podendo então ter como fim a pool de gasolinas. Tirando partido da tecnologia disponível para este efeito são apresentados quatro cenários de possíveis soluções. Sendo os dois primeiros excluídos por violarem restrições impostas, o terceiro e quarto cenários foram analisados de um ponto de vista económico. O terceiro cenário conduz a gasolina leve da Fábrica de Aromáticos para a pool de gasolinas sem qualquer tratamento e a gasolina leve da Fábrica de Combustíveis continua a integrar a pool de nafta química. O refinado da Fábrica de Aromáticos será enviado para um splitter, sendo a corrente de topo destinada à pool de nafta química e a corrente de fundo enviada a um reator de isomerização, Isomalk-4SM, passando previamente por uma torre de argila de forma a assegurar que a restrição em teor de olefinas no reator não é violada. O efluente, com RON maior, integrará igualmente a pool de gasolinas. No quarto cenário a corrente de refinado da Fábrica de Aromáticos não sofre qualquer tratamento, continuando a alimentar a unidade de solventes, a gasolina leve da Fábrica de Aromáticos irá diretamente para a pool de gasolinas e a gasolina leve da Fábrica de Combustíveis passará pelo Isomalk-2SM para aumentar o índice de octanos garantido assim ter condições de integrar a pool de gasolinas. Dissertação de Mestrado em Engenharia Química Isomerização de Gasolina Leve O terceiro cenário apresenta um aumento de 4 576 773 € anuais nas receitas e o quarto alcança 11 333 982 € anuais. O investimento inicial total do terceiro cenário é de 28 821 608 € quando o quarto cenário carece de um investimento inicial de apenas 18 028 349 €. Quanto aos custos associados à implementação da unidade estes demonstram-se elevados, o terceiro cenário apresenta um custo de 23 133 429 € enquanto o do quarto cenário é de 13 998 797 €. O quarto cenário apresenta-se assim como a solução mais rentável para o objetivo desta dissertação.

Incremental Recomputation of Pig Latin’s Nest and Unnest Operators

This master’s thesis addresses the maintenance of pre-computed structures, which store a frequent or expensive query, for the nested bag data type in the high level work-flow language Pig Latin. This thesis defines a model suitable to accommodate incremental expressions over nested bags on Pig Latin. Afterwards, the partitioned normal form for sets is extended with further restrictions, in order to accommodate the nested bag model, allow the Pig Latin nest and unnest operators revert each other, and create a suitable environment to the incremental computations. Subsequently, the extended operators – extended union and extended difference – are defined for the nested bag data model with the partitioned normal form for bags (PNF Bag) restriction, and semantics for the extended operators are given. Finally, incremental data propagation expressions are proposed for the nest and unnest operators on the data model proposed with the PNF Bag restriction, and the proof of correctness is given.

Neural Mechanisms of Exercise: Effects on Gut Miccrobiota and Depression

Microbiota is a set of microorganisms resident in gut ecosystem that reacts to psychological stressful stimuli, and is involved in depressed or anxious status in both animals and human being. Interestingly, a series of studies have shown the effects of physical exercise on gut microbiota dynamics, suggesting that gut microbiota regulation might act as one mediator for the effects of exercise on the brain. Recent studies found that gut microbiota dynamics are also regulated by metabolism changes, such as through physical exercise or diet change. Interestingly, physical exercise modulates different population of gut bacteria in compared to food restriction or rich diet, and alleviates gut syndromes to toxin intake. Gut microbiota could as well contribute to the beneficial effects of exercise on cognition and emotion, either directly through serotonin signaling or indirectly by modulating metabolism and exercise performance.