Implementing slot-based task-splitting multiprocessor scheduling

Consider the problem of scheduling a set of sporadic tasks on a multiprocessor system to meet deadlines using a task-splitting scheduling algorithm. Task-splitting (also called semi-partitioning) scheduling algorithms assign most tasks to just one processor but a few tasks are assigned to two or more processors, and they are dispatched in a way that ensures that a task never executes on two or more processors simultaneously. A particular type of task-splitting algorithms, called slot-based task-splitting dispatching, is of particular interest because of its ability to schedule tasks with high processor utilizations. Unfortunately, no slot-based task-splitting algorithm has been implemented in a real operating system so far. In this paper we discuss and propose some modifications to the slot-based task-splitting algorithm driven by implementation concerns, and we report the first implementation of this family of algorithms in a real operating system running Linux kernel version 2.6.34. We have also conducted an extensive range of experiments on a 4-core multicore desktop PC running task-sets with utilizations of up to 88%. The results show that the behavior of our implementation is in line with the theoretical framework behind it.

The utilization bound of static-priority preemptive partitioned multiprocessor scheduling is 50%

This paper studies static-priority preemptive scheduling on a multiprocessor using partitioned scheduling. We propose a new scheduling algorithm and prove that if the proposed algorithm is used and if less than 50% of the capacity is requested then all deadlines are met. It is known that for every static-priority multiprocessor scheduling algorithm, there is a task set that misses a deadline although the requested capacity is arbitrary close to 50%.

Computing semantic relatedness using DBPedia

Extracting the semantic relatedness of terms is an important topic in several areas, including data mining, information retrieval and web recommendation. This paper presents an approach for computing the semantic relatedness of terms using the knowledge base of DBpedia — a community effort to extract structured information from Wikipedia. Several approaches to extract semantic relatedness from Wikipedia using bag-of-words vector models are already available in the literature. The research presented in this paper explores a novel approach using paths on an ontological graph extracted from DBpedia. It is based on an algorithm for finding and weighting a collection of paths connecting concept nodes. This algorithm was implemented on a tool called Shakti that extract relevant ontological data for a given domain from DBpedia using its SPARQL endpoint. To validate the proposed approach Shakti was used to recommend web pages on a Portuguese social site related to alternative music and the results of that experiment are reported in this paper.

Sequencing cutting patterns with colored interval graphs

The problem addressed here originates in the industry of flat glass cutting and wood panel sawing, where smaller items are cut from larger items accordingly to predefined cutting patterns. In this type of industry the smaller pieces that are cut from the patterns are piled around the machine in stacks according to the size of the pieces, which are moved to the warehouse only when all items of the same size have been cut. If the cutting machine can process only one pattern at a time, and the workspace is limited, it is desirable to set the sequence in which the cutting patterns are processed in a way to minimize the maximum number of open stacks around the machine. This problem is known in literature as the minimization of open stacks (MOSP). To find the best sequence of the cutting patterns, we propose an integer programming model, based on interval graphs, that searches for an appropriate edge completion of the given graph of the problem, while defining a suitable coloring of its vertices.

Energy-aware task mapping onto heterogeneous platforms using DVFS and sleep states

Heterogeneous multicore platforms are becoming an interesting alternative for embedded computing systems with limited power supply as they can execute specific tasks in an efficient manner. Nonetheless, one of the main challenges of such platforms consists of optimising the energy consumption in the presence of temporal constraints. This paper addresses the problem of task-to-core allocation onto heterogeneous multicore platforms such that the overall energy consumption of the system is minimised. To this end, we propose a two-phase approach that considers both dynamic and leakage energy consumption: (i) the first phase allocates tasks to the cores such that the dynamic energy consumption is reduced; (ii) the second phase refines the allocation performed in the first phase in order to achieve better sleep states by trading off the dynamic energy consumption with the reduction in leakage energy consumption. This hybrid approach considers core frequency set-points, tasks energy consumption and sleep states of the cores to reduce the energy consumption of the system. Major value has been placed on a realistic power model which increases the practical relevance of the proposed approach. Finally, extensive simulations have been carried out to demonstrate the effectiveness of the proposed algorithm. In the best-case, savings up to 18% of energy are reached over the first fit algorithm, which has shown, in previous works, to perform better than other bin-packing heuristics for the target heterogeneous multicore platform.

Investigation on AUTOSAR-Compliant Solutions for Many-Core Architectures

As of today, AUTOSAR is the de facto standard in the automotive industry, providing a common software architec- ture and development process for automotive applications. While this standard is originally written for singlecore operated Elec- tronic Control Units (ECU), new guidelines and recommendations have been added recently to provide support for multicore archi- tectures. This update came as a response to the steady increase of the number and complexity of the software functions embedded in modern vehicles, which call for the computing power of multicore execution environments. In this paper, we enumerate and analyze the design options and the challenges of porting AUTOSAR-based automotive applications onto multicore platforms. In particular, we investigate those options when considering the emerging many- core architectures that provide a more scalable environment than the traditional multicore systems. Such platforms are suitable to enable massive parallel execution, and their design is more suitable for partitioning and isolating the software components.

Geomecânica aplicada à estabilidade de explorações mineiras bench and fill: o caso do jazigo de Feitais, Minas de Aljustrel

Este trabalho pretende abordar a importância de um estudo geomecânico no apoio à otimização e estabilidade de explorações subterrâneas por subníveis, com criação de bancadas e posterior enchimento. O presente envolveu um estudo geológico-geotécnico em quinze galerias situadas a muro, teto e corpo da mineralização com o levantamento das características mais relevantes do maciço rochoso para aplicação das classificações geomecânicas, englobando uma amostragem de mais de 1780 descontinuidades, obtendo um modelo cartográfico subterrâneo com um panorama geral da qualidade do maciço rochoso intercetado pelas escavações nas diferentes zonas. Os dados dos levantamentos de campo levaram à criação de uma base de dados com a aplicação das classificações geomecânicas Q-System, RMR e GSI, por galeria e, em seguida, por zona, com proposta de classe de sustimento a aplicar em cada local, pelo ábaco de Barton, em conjunto com a determinação de parâmetros geomecânicos fundamentais ao refinamento do conhecimento geológico-geotécnico das unidades litológicas em estudo. Na parte final, focando a localização da massa mineralizada de Feitais é efetuada uma abordagem relativa à estabilidade das cavidades geradas pelo desmonte em bancada entre subníveis, com respetivo dimensionamento das larguras admissíveis, em condições de segurança, através da relação entre o número de estabilidade e raio hidráulico, pelo método do gráfico de estabilidade. Com esta metodologia de caracterização geológico geotécnica, é pretendido efetuar um ponto de partida à criação de um modelo geomecânico comportamental do jazigo de Feitais, Mina de Aljustrel, contando com um processo inicial de apoio ao planeamento mineiro aplicado ao método de desmonte em bancada e posterior enchimento por subníveis, atuando nos parâmetros de estabilidade e apoio à extração, favorecendo assim a segurança das operações de trabalho em conjunto com um apoio de otimização da extração.

Predictivity Strength of the Spatial Variability of Phenanthrene Sorption Across Two Sandy Loam Fields

Sorption is commonly agreed to be the major process underlying the transport and fate of polycyclic aromatic hydrocarbons (PAHs) in soils. However, there is still a scarcity of studies focusing on spatial variability at the field scale in particular. In order to investigate the variation in the field of phenanthrene sorption, bulk topsoil samples were taken in a 15 × 15-m grid from the plough layer in two sandy loam fields with different texture and organic carbon (OC) contents (140 samples in total). Batch experiments were performed using the adsorption method. Values for the partition coefficient K d (L kg−1) and the organic carbon partition coefficient K OC (L kg−1) agreed with the most frequently used models for PAH partitioning, as OC revealed a higher affinity for sorption. More complex models using different OC compartments, such as non-complexed organic carbon (NCOC) and complexed organic carbon (COC) separately, performed better than single K OC models, particularly for a subset including samples with Dexter n < 10 and OC <0.04 kg kg−1. The selected threshold revealed that K OC-based models proved to be applicable for more organic fields, while two-component models proved to be more accurate for the prediction of K d and retardation factor (R) for less organic soils. Moreover, OC did not fully reflect the changes in phenanthrene retardation in the field with lower OC content (Faardrup). Bulk density and available water content influenced the phenanthrene transport mechanism phenomenon.

Energy-aware Task Allocation onto Unrelated Heterogeneous Multicore Platform for Mixed Criticality Systems

Presented at Work in Progress Session, IEEE Real-Time Systems Symposium (RTSS 2015). 1 to 4, Dec, 2015. San Antonio, U.S.A..

Cutting path as a rural postman problem

The Rural Postman Problem (RPP) is a particular Arc Routing Problem (ARP) which consists of determining a minimum cost circuit on a graph so that a given subset of required edges is traversed. The RPP is an NP-hard problem with significant real-life applications. This paper introduces an original approach based on Memetic Algorithms - the MARP algorithm - to solve the RPP and, also deals with an interesting Industrial Application, which focuses on the path optimization for component cutting operations. Memetic Algorithms are a class of Metaheuristics which may be seen as a population strategy that involves cooperation and competition processes between population elements and integrates “social knowledge”, using a local search procedure. The MARP algorithm is tested with different groups of instances and the results are compared with those gathered from other publications. MARP is also used in the context of various real-life applications.

Tutor Inteligente para o Ensino em Medicina

O objectivo deste trabalho consistiu no desenvolvimento de um protótipo que possibilita a adaptação do conteúdo disponibilizado de acordo com as características pessoais e psicológicas do aluno, aplicado no ensino da Medicina, nomeadamente na componente de Desenho de Estudos da disciplina de Introdução à Medicina. Para o protótipo desenvolvido foi definida uma arquitectura constituída por três componentes: um Modelo de Aluno que engloba as características pessoais e psicológicas do aluno, um Modelo de Domínio constituído por um grafo de conceitos e um Modelo Pedagógico formado pelas regras de adaptação e mecanismos de interação utilizados para obter uma solução adaptativa. Os diferentes componentes desenvolvidos para este protótipo permitem que este apresente as seguintes funcionalidades: Acesso ao conceito adequado, tendo em consideração o nível de conhecimento do aluno; Visualização de conte udos adequados ao estilo de aprendizagem do aluno; Adaptação do percurso do aluno de acordo com os resultados obtidos; Atualização das preferências de aprendizagem, com base no comportamento demonstrado pelo aluno na interação com o sistema. A primeira versão da ferramenta j a foi implementada. No entanto ainda será realizada a avaliação do protótipo em ambiente de aprendizagem, com a maior brevidade possível.