Implementing multicore real-time scheduling algorithms based on task splitting using ada 2012

Multiprocessors, particularly in the form of multicores, are becoming standard building blocks for executing reliable software. But their use for applications with hard real-time requirements is non-trivial. Well-known realtime scheduling algorithms in the uniprocessor context (Rate-Monotonic [1] or Earliest-Deadline-First [1]) do not perform well on multiprocessors. For this reason the scientific community in the area of real-time systems has produced new algorithms specifically for multiprocessors. In the meanwhile, a proposal [2] exists for extending the Ada language with new basic constructs which can be used for implementing new algorithms for real-time scheduling; the family of task splitting algorithms is one of them which was emphasized in the proposal [2]. Consequently, assessing whether existing task splitting multiprocessor scheduling algorithms can be implemented with these constructs is paramount. In this paper we present a list of state-of-art task-splitting multiprocessor scheduling algorithms and, for each of them, we present detailed Ada code that uses the new constructs.

Multi-agent system for distributed manufacturing scheduling with genetic algorithms and tabu search

Computerized scheduling methods and computerized scheduling systems according to exemplary embodiments. A computerized scheduling method may be stored in a memory and executed on one or more processors. The method may include defining a main multi-machine scheduling problem as a plurality of single machine scheduling problems; independently solving the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; integrating the plurality of near optimal single machine scheduling problem solutions into a main multi-machine scheduling problem solution; and outputting the main multi-machine scheduling problem solution.

Towards realistic core-failure-resilient scheduling and analysis

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

Towards realistic core-failure-resilient scheduling and analysis

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

Real-time Task-Splitting scheduling algorithms framework

Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível prá

On the implementation of real-time slotbased task-splitting scheduling algorithms for multiprocessor systems

In this paper we discuss challenges and design principles of an implementation of slot-based tasksplitting algorithms into the Linux 2.6.34 version. We show that this kernel version is provided with the required features for implementing such scheduling algorithms. We show that the real behavior of the scheduling algorithm is very close to the theoretical. We run and discuss experiments on 4-core and 24-core machines.

Engineering real-time applications with WorldFIP: tools and analysis

WorldFIP is standardised as European Norm EN 50170 - General Purpose Field Communication System. Field communication systems (fieldbuses) started to be widely used as the communication support for distributed computer-controlled systems (DCCS), and are being used in all sorts of process control and manufacturing applications within different types of industries. There are several advantages in using fieldbuses as a replacement of for the traditional point-to-point links between sensors/actuators and computer-based control systems. Indeed they concern economical ones (cable savings) but, importantly, fieldbuses allow an increased decentralisation and distribution of the processing power over the field. Typically DCCS have real-time requirements that must be fulfilled. By this, we mean that process data must be transferred between network computing nodes within a maximum admissible time span. WorldFIP has very interesting mechanisms to schedule data transfers. It explicit distinguishes to types of traffic: periodic and aperiodic. In this paper we describe how WorldFIP handles these two types of traffic, and more importantly, we provide a comprehensive analysis for guaranteeing the real-time requirements of both types of traffic. A major contribution is made in the analysis of worst-case response time of aperiodic transfer requests.

SPARTS: simulator for power aware and real-time systems

Real-time systems demand guaranteed and predictable run-time behaviour in order to ensure that no task has missed its deadline. Over the years we are witnessing an ever increasing demand for functionality enhancements in the embedded real-time systems. Along with the functionalities, the design itself grows more complex. Posed constraints, such as energy consumption, time, and space bounds, also require attention and proper handling. Additionally, efficient scheduling algorithms, as proven through analyses and simulations, often impose requirements that have significant run-time cost, specially in the context of multi-core systems. In order to further investigate the behaviour of such systems to quantify and compare these overheads involved, we have developed the SPARTS, a simulator of a generic embedded real- time device. The tasks in the simulator are described by externally visible parameters (e.g. minimum inter-arrival, sporadicity, WCET, BCET, etc.), rather than the code of the tasks. While our current implementation is primarily focused on our immediate needs in the area of power-aware scheduling, it is designed to be extensible to accommodate different task properties, scheduling algorithms and/or hardware models for the application in wide variety of simulations. The source code of the SPARTS is available for download at [1].

Comparing the schedulers and power saving strategies with SPARTS

We have developed SPARTS, a simulator of a generic embedded real-time device. It is designed to be extensible to accommodate different task properties, scheduling algorithms and/or hardware models for the wide variety of applications. SPARTS was developed to help the community investigate the behaviour of the real-time embedded systems and to quantify the associated constraints/overheads.

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

CardioML: integrating personal cardiac information for ubiquous diagnosis and analysis

The latest medical diagnosis devices enable the performance of e-diagnosis making the access to these services easier, faster and available in remote areas. However this imposes new communications and data interchange challenges. In this paper a new XML based format for storing cardiac signals and related information is presented. The proposed structure encompasses data acquisition devices, patient information, data description, pathological diagnosis and waveform annotation. When compared with similar purpose formats several advantages arise. Besides the full integrated data model it may also be noted the available geographical references for e-diagnosis, the multi stream data description, the ability to handle several simultaneous devices, the possibility of independent waveform annotation and a HL7 compliant structure for common contents. These features represent an enhanced integration with existent systems and an improved flexibility for cardiac data representation.

Some reflections on acquisition, processing and analysis of statistical data in forest soils

Beyond the classical statistical approaches (determination of basic statistics, regression analysis, ANOVA, etc.) a new set of applications of different statistical techniques has increasingly gained relevance in the analysis, processing and interpretation of data concerning the characteristics of forest soils. This is possible to be seen in some of the recent publications in the context of Multivariate Statistics. These new methods require additional care that is not always included or refered in some approaches. In the particular case of geostatistical data applications it is necessary, besides to geo-reference all the data acquisition, to collect the samples in regular grids and in sufficient quantity so that the variograms can reflect the spatial distribution of soil properties in a representative manner. In the case of the great majority of Multivariate Statistics techniques (Principal Component Analysis, Correspondence Analysis, Cluster Analysis, etc.) despite the fact they do not require in most cases the assumption of normal distribution, they however need a proper and rigorous strategy for its utilization. In this work, some reflections about these methodologies and, in particular, about the main constraints that often occur during the information collecting process and about the various linking possibilities of these different techniques will be presented. At the end, illustrations of some particular cases of the applications of these statistical methods will also be presented.

The development and implementation of math projects in a HEI: expectations, objectives, experiences and analysis

An overwhelming problem in Math Curriculums in Higher Education Institutions (HEI), we are daily facing in the last decade, is the substantial differences in Math background of our students. When you try to transmit, engage and teach subjects/contents that your “audience” is unable to respond to and/or even understand what we are trying to convey, it is somehow frustrating. In this sense, the Math projects and other didactic strategies, developed through Learning Management System Moodle, which include an array of activities that combine higher order thinking skills with math subjects and technology, for students of HE, appear as remedial but important, proactive and innovative measures in order to face and try to overcome these considerable problems. In this paper we will present some of these strategies, developed in some organic units of the Polytechnic Institute of Porto (IPP). But, how “fruitful” are the endless number of hours teachers spent in developing and implementing these platforms? Do students react to them as we would expect? Do they embrace this opportunity to overcome their difficulties? How do they use/interact individually with LMS platforms? Can this environment that provides the teacher with many interesting tools to improve the teaching – learning process, encourages students to reinforce their abilities and knowledge? In what way do they use each available material – videos, interactive tasks, texts, among others? What is the best way to assess student’s performance in these online learning environments? Learning Analytics tools provides us a huge amount of data, but how can we extract “good” and helpful information from them? These and many other questions still remain unanswered but we look forward to get some help in, at least, “get some drafts” for them because we feel that this “learning analysis”, that tackles the path from the objectives to the actual results, is perhaps the only way we have to move forward in the “best” learning and teaching direction.

População e Enriquecimento de Ontologias através de Web Scraping

O surgir da World Wide Web providenciou aos utilizadores uma série de oportunidades no que diz respeito ao acesso a dados e informação. Este acesso tornou-se um ato banal para qualquer utilizador da Web, tanto pelo utilizador comum como por outros mais experientes, tanto para obter informações básicas, como outras informações mais complexas. Todo este avanço tecnológico permitiu que os utilizadores tivessem acesso a uma vasta quantidade de informação, dispersa pelo globo, não tendo, na maior parte das vezes, a informação qualquer tipo de ligação entre si. A necessidade de se obter informação de interesse relativamente a determinado tema, mas tendo que recorrer a diversas fontes para obter toda a informação que pretende obter e comparar, torna-se um processo moroso para o utilizador. Pretende-se que este processo de recolha de informação de páginas web seja o mais automatizado possível, dando ao utilizador a possibilidade de utilizar algoritmos e ferramentas de análise e processamento automáticas, reduzindo desta forma o tempo e esforço de realização de tarefas sobre páginas web. Este processo é denominado Web Scraping. Neste trabalho é descrita uma arquitetura de sistema de web scraping automático e configurável baseado em tecnologias existentes, nomeadamente no contexto da web semântica. Para tal o trabalho desenvolvido analisa os efeitos da aplicação do Web Scraping percorrendo os seguintes pontos: • Identificação e análise de diversas ferramentas de web scraping; • Identificação do processo desenvolvido pelo ser humano complementar às atuais ferramentas de web scraping; • Design duma arquitetura complementar às ferramentas de web scraping que dê apoio ao processo de web scraping do utilizador; • Desenvolvimento dum protótipo baseado em ferramentas e tecnologias existentes; • Realização de experiências no domínio de aplicação de páginas de super-mercados portugueses; • Analisar resultados obtidos a partir destas.

Imagiologia Espetral - Análise Forense de Notas e Escrita Manual

A análise forense de documentos é uma das áreas das Ciências Forenses, responsável pela verificação da autenticidade dos documentos. Os documentos podem ser de diferentes tipos, sendo a moeda ou escrita manual as evidências forenses que mais frequentemente motivam a análise. A associação de novas tecnologias a este processo de análise permite uma melhor avaliação dessas evidências, tornando o processo mais célere. Esta tese baseia-se na análise forense de dois tipos de documentos - notas de euro e formulários preenchidos por escrita manual. Neste trabalho pretendeu-se desenvolver técnicas de processamento e análise de imagens de evidências dos tipos referidos com vista a extração de medidas que permitam aferir da autenticidade dos mesmos. A aquisição das imagens das notas foi realizada por imagiologia espetral, tendo-se definidas quatro modalidades de aquisição: luz visível transmitida, luz visível refletida, ultravioleta A e ultravioleta C. Para cada uma destas modalidades de aquisição, foram também definidos 2 protocolos: frente e verso. A aquisição das imagens dos documentos escritos manualmente efetuou-se através da digitalização dos mesmos com recurso a um digitalizador automático de um aparelho multifunções. Para as imagens das notas desenvolveram-se vários algoritmos de processamento e análise de imagem, específicos para este tipo de evidências. Esses algoritmos permitem a segmentação da região de interesse da imagem, a segmentação das sub-regiões que contém as marcas de segurança a avaliar bem como da extração de algumas características. Relativamente as imagens dos documentos escritos manualmente, foram também desenvolvidos algoritmos de segmentação que permitem obter todas as sub-regiões de interesse dos formulários, de forma a serem analisados os vários elementos. Neste tipo de evidências, desenvolveu-se ainda um algoritmo de análise para os elementos correspondentes à escrita de uma sequência numérica o qual permite a obtenção das imagens correspondentes aos caracteres individuais. O trabalho desenvolvido e os resultados obtidos permitiram a definição de protocolos de aquisição de imagens destes tipos de evidências. Os algoritmos automáticos de segmentação e análise desenvolvidos ao longo deste trabalho podem ser auxiliares preciosos no processo de análise da autenticidade dos documentos, o qual, ate então, é feito manualmente. Apresentam-se ainda os resultados dos estudos feitos às diversas evidências, nomeadamente as performances dos diversos algoritmos analisados, bem como algumas das adversidades encontradas durante o processo. Apresenta-se também uma discussão da metodologia adotada e dos resultados, bem como de propostas de continuação deste trabalho, nomeadamente, a extração de características e a implementação de classificadores capazes aferir da autenticidade dos documentos.