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.

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.

O projeto de literacia da informação numa biblioteca da saúde: o caso da Biblioteca da ESTeSL

Introdução – Ao aumento exponencial de informação, sobretudo a científica, não corresponde obrigatoriamente a melhoria de qualidade na pesquisa e no uso da mesma. O conceito de literacia da informação ganha pertinência e destaque, na medida em que abarca competências que permitem reconhecer quando é necessária a informação e de atuar de forma eficiente e efetiva na sua obtenção e utilização. A biblioteca académica assume, neste contexto, o papel de parceiro privilegiado, preparando o momento em que o estudante se sente capaz de produzir e registar novo conhecimento através da escrita. Objectivo – A Biblioteca da ESTeSL reestruturou as sessões desenvolvidas desde o ano lectivo 2002/2003 e deu início a um projecto mais formal denominado «Saber usar a informação de forma eficiente e eficaz». Objectivos: a) promover a melhoria da qualidade dos trabalhos académicos e científicos; b) contribuir para a diminuição do risco de plágio; c) aumentar a confiança dos estudantes nas suas capacidades de utilização dos recursos de informação; d) incentivar uma participação mais ativa em sala de aulas; e) colaborar para a integração dos conteúdos pedagógicos e das várias fontes de informação. Método – Dinamizaram-se várias sessões de formação de curta duração, versando diferentes temas associados à literacia de informação, designadamente: 1) Pesquisa de informação com sessões dedicadas à MEDLINE, RCAAP, SciELO, B-ON e Scopus; 2) Factor de impacto das revistas científicas: Journal Citation Reports e SciMAGO; 3) Como fazer um resumo científico?; 4) Como estruturar o trabalho científico?; 5) Como fazer uma apresentação oral?; 6) Como evitar o plágio?; 7) Referenciação bibliográfica usando a norma de Vancouver; 8) Utilização de gestores de referências bibliográficas: ZOTERO (primeira abordagem para os estudantes de 1º ano de licenciatura) e a gestão de referências e rede académica de informação com o MENDELEY (direcionado para estudantes finalistas, mestrandos, docentes e investigadores). O projecto foi apresentado à comunidade académica no site da ESTeSL; cada sessão foi divulgada individualmente no site e por email. Em 2015, a divulgação investiu na nova página da Biblioteca (https://estesl.biblio.ipl.pt/), que alojava informações e recursos abordados nas formações. As inscrições eram feitas por email, sem custos associados ou limite mínimo ou máximo de sessões para participar. Resultados – Em 2014 registaram-se 87 inscrições. Constatou-se a presença de, pelo menos, um participante em cada sessão de formação. Em 2015, o total de inscrições foi de 190. Foram reagendadas novas sessões a pedido dos estudantes cujos horários não eram compatíveis com os inicialmente agendados. Foram então organizados dois dias de formação seguida (cerca de 4h em cada dia) com conteúdos selecionados pelos estudantes. Registou-se, nestas sessões, a presença contante de cerca de 30 estudantes em sala. No total, as sessões da literacia da informação contaram com estudantes de licenciatura de todos os anos, estudantes de mestrado, docentes e investigadores (internos e externos à ESTeSL). Conclusões – Constata-se a necessidade de introdução de novos conteúdos no projeto de literacia da informação. O tempo, os conteúdos e o interesse demonstrado por aqueles que dele usufruíram evidenciam que este é um projeto que está a ganhar o seu espaço na comunidade da ESTeSL e que a literacia da informação contribui de forma efetiva para a construção e para a produção de conhecimento no meio académico.

Step count algorithm adapted to indoor localization

This paper presents a step count algorithm designed to work in real-time using low computational power. This proposal is our first step for the development of an indoor navigation system, based on Pedestrian Dead Reckoning (PDR). We present two approaches to solve this problem and compare them based in their error on step counting, as well as, the capability of their use in a real time system.

Adaptive offloading for infotainment systems

Infotainment applications in vehicles are currently supported both by the in-vehicle platform, as well as by user’s smart devices, such as smartphones and tablets. More and more the user expects that there is a continuous service of applications inside or outside of the vehicle, provided in any of these devices (a simple but common example is hands-free mobile phone calls provided by the vehicle platform). With the increasing complexity of ‘apps’, it is necessary to support increasing levels of Quality of Service (QoS), with varying resource requirements. Users may want to start listening to music in the smartphone, or video in the tablet, being this application transparently ‘moved’ into the vehicle when it is started. This paper presents an adaptable offloading mechanism, following a service-oriented architecture pattern, which takes into account the QoS requirements of the applications being executed when making decisions.

Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Pre-emption

This article introduces schedulability analysis for global fixed priority scheduling with deferred preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of global fixed priority pre-emptive scheduling (gFPPS) and global fixed priority non-pre-emptive scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final non-pre-emptive region lengths, and provide algorithms which optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.

Logic-based schedulability analysis for compositional hard real-time embedded systems

Over the past decades several approaches for schedulability analysis have been proposed for both uni-processor and multi-processor real-time systems. Although different techniques are employed, very little has been put forward in using formal specifications, with the consequent possibility for mis-interpretations or ambiguities in the problem statement. Using a logic based approach to schedulability analysis in the design of hard real-time systems eases the synthesis of correct-by-construction procedures for both static and dynamic verification processes. In this paper we propose a novel approach to schedulability analysis based on a timed temporal logic with time durations. Our approach subsumes classical methods for uni-processor scheduling analysis over compositional resource models by providing the developer with counter-examples, and by ruling out schedules that cause unsafe violations on the system. We also provide an example showing the effectiveness of our proposal.

An Exact Schedulability Test for Global FP Using State Space Pruning

Presented at 23rd International Conference on Real-Time Networks and Systems (RTNS 2015). 4 to 6, Nov, 2015, Main Track. Lille, France.

Altmetrics in Institutional Repositories: New Perspectives for Assessing Research Impact

Poster (and extended abstract) presented at the 13th International Conference "Libraries in the Digital Age (LIDA 2014)" held on 16-20th June, University of Zadar, Zadar, Croatia

Aux archives de l'animisme. Ethnographie et théorie de la "religion sauvage" chez Edward Tylor

En 1871, Edward Tylor rejeta fermement les récits de son temps qui niaient l'existence de croyances religieuses chez certains peuples alors considérés comme sauvages. C'était le cas, tout particulièrement, de l'explorateur victorien Samuel Baker, dont l'autorité ethnographique fut mise en cause à travers la citation de quelques voyageurs étrangers, dont deux français, qui avaient également observé les peuples nilotiques. Contrairement à d'autres sources de Primitive Culture, la qualité de ces ethnographies oubliées était, hélas, tout à fait médiocre ; mais elles permirent à Tylor de faire l'une des affirmations les plus décisives de son œuvre, celle de l'universalité de l'animisme. Ce passage capital - concernant des peuples qui deviendront célèbres dans l'histoire de l'anthropologie, à commencer par les Nuer - recèle par ailleurs une dimension additionnelle. Tylor voulait élargir à tout être spirituel les critères d'identification d'une religion, sauf que les ethnographes du Nil Blanc suggéraient que ces rudes populations croyaient bel et bien en un être suprême. Le dossier du monothéisme était comme anticipé par la force de ces données ; mais il ne faut pas y voir une contradiction de la part de Tylor. Au contraire, cette dialectique imprévue entre l'ethnographie et la théorie permet de mieux saisir la portée du concept d'animisme dont il fut le créateur.

Fungal communities in archives: assessment strategies and impact on paper conservation and human health

The main results presented in this PhD Dissertation have been published in interna-tional journals included in the Science Citation Index (SCI)

Under the veil of citations

Academics are often ranked on citation counts’, which is considered an adequate proxy for author's quality and reputation. This paper seeks to find what is behind a cited academic / a cited article. We constructed a rich dataset from Portuguese affiliated economists and use zero inflated negative binomial model. This procedure is appropriate for count outcomes, correcting for overdispersion and excess zeros. We also use a fixed effect poisson model to accomodate authors' unobserved heterogeneity. We analyze results in detail comparing with existing literature and making some theoretical considerations around.

Clustering-based approach for categorizing pregnant women in obstetrics and maternity care

When a pregnant woman is guided to a hospital for obstetrics purposes, many outcomes are possible, depending on her current conditions. An improved understanding of these conditions could provide a more direct medical approach by categorizing the different types of patients, enabling a faster response to risk situations, and therefore increasing the quality of services. In this case study, the characteristics of the patients admitted in the maternity care unit of Centro Hospitalar of Porto are acknowledged, allowing categorizing the patient women through clustering techniques. The main goal is to predict the patients’ route through the maternity care, adapting the services according to their conditions, providing the best clinical decisions and a cost-effective treatment to patients. The models developed presented very interesting results, being the best clustering evaluation index: 0.65. The evaluation of the clustering algorithms proved the viability of using clustering based data mining models to characterize pregnant patients, identifying which conditions can be used as an alert to prevent the occurrence of medical complications.

Produção brasileira em periódicos psiquiátricos de alto fator de impacto em 2005

OBJETIVO: Avaliar a produção científica brasileira, no ano de 2005, nas 20 revistas de psiquiatria com maior fator de impacto (FI) segundo o Journal of Citation Report (JCR), 2004. MÉTODOS: Do total de 90 periódicos com FI variando de 11,207 até 0,13, selecionamos todos os artigos dos periódicos com FI acima do percentil 75 (n = 20). Avaliamos, entre esses artigos, quantos apresentavam pelo menos um autor brasileiro, quantos eram compostos por equipe exclusivamente brasileira ou tinham pelo menos o primeiro autor e/ou o autor sênior filiado à instituição nacional. Avaliamos também a respectiva distribuição das publicações por estados de acordo com a instituição de filiação do(s) autor(es). RESULTADOS: Entre 4.859 artigos avaliados, 54 (1,11%) tinham pelo menos um autor com afiliação a instituição brasileira e 22 tinham autor sênior brasileiro, excluindo-se as 32 publicações compostas exclusivamente por pesquisadores brasileiros. Ao se determinar a distribuição, por estados, da instituição de pesquisa à qual está(ão) vinculado(s) o(s) autor(res) brasileiro(s), São Paulo, com 34 publicações (55,73%), ficou na primeira posição, com predominância absoluta do eixo Sudeste-Sul (96,72%). CONCLUSÃO: Apesar de as publicações brasileiras em psiquiatria terem apresentado aparente crescimento quantitativo e qualitativo, a produção científica da área é ainda pequena e altamente concentrada em alguns poucos estados.