Multicore Scheduling of Real-Time Irregular Parallel Algorithms in Linux

Face à estagnação da tecnologia uniprocessador registada na passada década, aos principais fabricantes de microprocessadores encontraram na tecnologia multi-core a resposta `as crescentes necessidades de processamento do mercado. Durante anos, os desenvolvedores de software viram as suas aplicações acompanhar os ganhos de performance conferidos por cada nova geração de processadores sequenciais, mas `a medida que a capacidade de processamento escala em função do número de processadores, a computação sequencial tem de ser decomposta em várias partes concorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamento adicionais e completar mais rapidamente. A programação paralela implica um paradigma completamente distinto da programação sequencial. Ao contrário dos computadores sequenciais tipificados no modelo de Von Neumann, a heterogeneidade de arquiteturas paralelas requer modelos de programação paralela que abstraiam os programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplicações concorrentes. Os modelos de programação paralela mais populares incitam os programadores a identificar instruções concorrentes na sua lógica de programação, e a especificá-las sob a forma de tarefas que possam ser atribuídas a processadores distintos para executarem em simultâneo. Estas tarefas são tipicamente lançadas durante a execução, e atribuídas aos processadores pelo motor de execução subjacente. Como os requisitos de processamento costumam ser variáveis, e não são conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinado dinamicamente, em resposta a alterações imprevisíveis dos requisitos de execução. `A medida que o volume da computação cresce, torna-se cada vez menos viável garantir as suas restrições temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real se começam a adaptar ao paradigma de computação paralela, há uma crescente aposta em integrar execuções de tempo real com aplicações interativas no mesmo hardware, num mundo em que a tecnologia se torna cada vez mais pequena, leve, ubíqua, e portável. Esta integração requer soluções de escalonamento que simultaneamente garantam os requisitos temporais das tarefas de tempo real e mantenham um nível aceitável de QoS para as restantes execuções. Para tal, torna-se imperativo que as aplicações de tempo real paralelizem, de forma a minimizar os seus tempos de resposta e maximizar a utilização dos recursos de processamento. Isto introduz uma nova dimensão ao problema do escalonamento, que tem de responder de forma correcta a novos requisitos de execução imprevisíveis e rapidamente conjeturar o mapeamento de tarefas que melhor beneficie os critérios de performance do sistema. A técnica de escalonamento baseado em servidores permite reservar uma fração da capacidade de processamento para a execução de tarefas de tempo real, e assegurar que os efeitos de latência na sua execução não afectam as reservas estipuladas para outras execuções. No caso de tarefas escalonadas pelo tempo de execução máximo, ou tarefas com tempos de execução variáveis, torna-se provável que a largura de banda estipulada não seja consumida por completo. Para melhorar a utilização do sistema, os algoritmos de partilha de largura de banda (capacity-sharing) doam a capacidade não utilizada para a execução de outras tarefas, mantendo as garantias de isolamento entre servidores. Com eficiência comprovada em termos de espaço, tempo, e comunicação, o mecanismo de work-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefas com paralelismo dinâmico e irregular. O algoritmo p-CSWS combina escalonamento baseado em servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamento dos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permite partilhar os recursos de processamento sem interferências a nível dos atrasos, uma nova política de work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma exploração de paralelismo que melhora os tempos de resposta das aplicações e melhora a utilização do sistema. Esta tese propõe uma implementação do algoritmo p-CSWS para o Linux. Em concordância com a estrutura modular do escalonador do Linux, ´e definida uma nova classe de escalonamento que visa avaliar a aplicabilidade da heurística p-CSWS em circunstâncias reais. Ultrapassados os obstáculos intrínsecos `a programação da kernel do Linux, os extensos testes experimentais provam que o p-CSWS ´e mais do que um conceito teórico atrativo, e que a exploração heurística de paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplicações de tempo real, bem como a performance e eficiência da plataforma multiprocessador.

Kdd, semma crisp-dm: a parallel overviee

In the last years there has been a huge growth and consolidation of the Data Mining field. Some efforts are being done that seek the establishment of standards in the area. Included on these efforts there can be enumerated SEMMA and CRISP-DM. Both grow as industrial standards and define a set of sequential steps that pretends to guide the implementation of data mining applications. The question of the existence of substantial differences between them and the traditional KDD process arose. In this paper, is pretended to establish a parallel between these and the KDD process as well as an understanding of the similarities between them.

KDD, SEMMA and CRISP-DM: a parallel overview

In the last years there has been a huge growth and consolidation of the Data Mining field. Some efforts are being done that seek the establishment of standards in the area. Included on these efforts there can be enumerated SEMMA and CRISP-DM. Both grow as industrial standards and define a set of sequential steps that pretends to guide the implementation of data mining applications. The question of the existence of substantial differences between them and the traditional KDD process arose. In this paper, is pretended to establish a parallel between these and the KDD process as well as an understanding of the similarities between them.

Energy efficiency analysis considering the use of an intelligent systems management in a smart home

In this abstract is presented an energy management system included in a SCADA system existent in a intelligent home. The system control the home energy resources according to the players definitions (electricity consumption and comfort levels), the electricity prices variation in real time mode and the DR events proposed by the aggregators.

Effect of the compact Ti layer on the efficiency of dye-sensitized solar cells assembled using stainless steel sheets

Titanium films have been deposited on stainless steel metal sheets using dc magnetron sputtering technique at different substrate temperatures. The structure of the titanium films strongly depend on the substrate temperature. The titanium film deposited at the substrate temperature lower than 300 ◦C has a loose flat sheet grains structure and the titanium film prepared at the substrate temperature higher than 500 ◦C has a dense nubby grains structure. The DSSC assembled using stainless steel sheet coated with titanium film deposited at high substrate temperature has a low charge transfer resistance in the TiO2/Ti interface and results in a high conversion efficiency. The DSSC assembled using stainless steel sheet coated with titanium film deposited at temperature higher than 500 ◦C has higher conversion efficiency than that assembled using titanium metal sheet as the substrate. The maximum conversion efficiency, 2.26% is obtained for DSSC assembled using stainless steel sheet coated with titanium film deposited at 700 ◦C substrate temperature, which is about 70% of the conversion efficiency of the FTO reference cell used in this study.

Evaluating the efficiency of a vegetal coagulant in the treatment of industrial effluents

The present work aims at evaluating the efficiency of an organic polymer from vegetal source used as coagulant for treating different types of industrial effluents. This coagulant (Flox-QT) is obtained from the Black Acacia (Acacia mearnsii). The effluents studied were produced in petrochemical, leather, cork stoppers, metalworking, olive oil, glue, paint (printing), textile and paper industries. The parameters analyzed in the effluents before and after treatment were selected according to the type of wastewater and included pH, conductivity, apparent colour, turbidity, total suspended solids (TSS), chemical oxygen demand (COD) and some metals. The coagulant proved to be efficient for almost all effluents tested. The best results were obtained for the paper industry wastewater, with 91% removal of chemical oxygen demand and 95% of total suspended solids removal. The estimated cost of this treatment would be only 0.24 Euro per cubic meter of treated effluent, only regarding the price of the coagulant and the required dosage. The use of this coagulant is also adequate for the valorisation of the sludge obtained, which in this case could be recycled for paper production.

Aplicação de metodologias lean na manutenção da simoldes aços

O trabalho presente nesta dissertação incidiu sobre a aplicação das metodologias Lean no âmbito da manutenção de uma empresa metalomecânica de produção de Moldes – Simoldes Aços. No atual enquadramento, com os mercados nacionais e internacionais debaixo de feroz competição, as empresas são obrigadas a estudar métodos e técnicas que permitam eliminar desperdícios, reduzir custos e tempos de produção, ao mesmo tempo que são exigidos maiores níveis de qualidade dos produtos fabricados com vista ao aumento da competitividade. Sendo a Manutenção uma área funcional com um impacto elevado no desempenho da produção, é percebido que o desempenho desta, tem influência direta no comportamento do fluxo produtivo e nos respetivos níveis de eficácia e eficiência. No decorrer do trabalho desta dissertação de mestrado foi realizada uma análise abrangente do estado atual do sector de atividade de manutenção na empresa SIMOLDES SA, o que permitiu identificar as áreas e os pontos a intervir e desenhar as soluções de melhoria na atividade de manutenção. Na fase concludente do trabalho foram implementadas algumas dessas propostas de melhoria, ao passo que outras ficaram agendadas para futura implementação. Na base do trabalho desenvolvido esteve a metodologia Lean, que apresenta um papel relevante na implementação de uma abordagem integrada da função manutenção na manutenção dos objetivos da produção. O presente projeto baseou a sua estratégia de implementação na aplicação da ferramenta do 5S’ em paralelo com o TPM (Total Productive Maintenance). Ambas as ferramentas visam a redução de desperdícios e o aumento da fiabilidade dos processos, pelo aumento da disponibilidade dos equipamentos, da melhoria do desempenho dos processos e da plena integração de todos os colaboradores no processo de fabrico. Com a implementação das melhorias propostas, foram observados melhorias significativas no fluxo das atividades da manutenção, assim como uma maior visibilidade das mesmas em todo o processo produtivo.

Remediation efficiency of vapour extraction of sandy soils contaminated with cyclohexane: influence of air flow rate, water and natural organic matter content

Abstract This work reports the analysis of the efficiency and time of soil remediation using vapour extraction as well as provides comparison of results using both, prepared and real soils. The main objectives were: (i) to analyse the efficiency and time of remediation according to the water and natural organic matter content of the soil; and (ii) to assess if a previous study, performed using prepared soils, could help to preview the process viability in real conditions. For sandy soils with negligible clay content, artificially contaminated with cyclohexane before vapour extraction, it was concluded that (i) the increase of soil water content and mainly of natural organic matter content influenced negatively the remediation process, making it less efficient, more time consuming, and consequently more expensive; and (ii) a previous study using prepared soils of similar characteristics has proven helpful for previewing the process viability in real conditions.

Structural modification of TiO2 nanorod films with an influence on the photovoltaic efficiency of a dye-sensitized solar cell (DSSC).

TiO2 nanorod films have been deposited on ITO substrates by dc reactive magnetron sputtering technique. The structures of these nanorod films were modified by the variation of the oxygen pressure during the sputtering process. Although all these TiO2 nanorod films deposited at different oxygen pressures show an anatase structure, the orientation of the nanorod films varies with the oxygen pressure. Only a very weak (101) diffraction peak can be observed for the TiO2 nanorod film prepared at low oxygen pressure. However, as the oxygen pressure is increased, the (220) diffraction peak appears and the intensity of this diffraction peak is increased with the oxygen pressure. The results of the SEM show that these TiO2 nanorods are perpendicular to the ITO substrate. At low oxygen pressure, these sputtered TiO2 nanorods stick together and have a dense structure. As the oxygen pressure is increased, these sputtered TiO2 nanorods get separated gradually and have a porous structure. The optical transmittance of these TiO2 nanorod films has been measured and then fitted by OJL model. The porosities of the TiO2 nanorod films have been calculated. The TiO2 nanorod film prepared at high oxygen pressure shows a high porosity. The dye-sensitized solar cells (DSSCs) have been assembled using these TiO2 nanorod films prepared at different oxygen pressures as photoelectrode. The optimum performance was achieved for the DSSC using the TiO2 nanorod film with the highest (220) diffraction peak and the highest porosity.

Real-time scheduling of parallel tasks in the Linux Kernel

This paper proposes a global multiprocessor scheduling algorithm for the Linux kernel that combines the global EDF scheduler with a priority-aware work-stealing load balancing scheme, enabling parallel real-time tasks to be executed on more than one processor at a given time instant. We state that some priority inversion may actually be acceptable, provided it helps reduce contention, communication, synchronisation and coordination between parallel threads, while still guaranteeing the expected system’s predictability. Experimental results demonstrate the low scheduling overhead of the proposed approach comparatively to an existing real-time deadline-oriented scheduling class for the Linux kernel.

Supporting real-time parallel task models with work-stealing

Dynamic parallel scheduling using work-stealing has gained popularity in academia and industry for its good performance, ease of implementation and theoretical bounds on space and time. Cores treat their own double-ended queues (deques) as a stack, pushing and popping threads from the bottom, but treat the deque of another randomly selected busy core as a queue, stealing threads only from the top, whenever they are idle. However, this standard approach cannot be directly applied to real-time systems, where the importance of parallelising tasks is increasing due to the limitations of multiprocessor scheduling theory regarding parallelism. Using one deque per core is obviously a source of priority inversion since high priority tasks may eventually be enqueued after lower priority tasks, possibly leading to deadline misses as in this case the lower priority tasks are the candidates when a stealing operation occurs. Our proposal is to replace the single non-priority deque of work-stealing with ordered per-processor priority deques of ready threads. The scheduling algorithm starts with a single deque per-core, but unlike traditional work-stealing, the total number of deques in the system may now exceed the number of processors. Instead of stealing randomly, cores steal from the highest priority deque.

Parallel real-time support for distributed adaptive embedded applications

Real-time embedded applications require to process large amounts of data within small time windows. Parallelize and distribute workloads adaptively is suitable solution for computational demanding applications. The purpose of the Parallel Real-Time Framework for distributed adaptive embedded systems is to guarantee local and distributed processing of real-time applications. This work identifies some promising research directions for parallel/distributed real-time embedded applications.

A framework for the development of parallel and distributed real-time embedded systems

Embedded real-time applications increasingly present high computation requirements, which need to be completed within specific deadlines, but that present highly variable patterns, depending on the set of data available in a determined instant. The current trend to provide parallel processing in the embedded domain allows providing higher processing power; however, it does not address the variability in the processing pattern. Dimensioning each device for its worst-case scenario implies lower average utilization, and increased available, but unusable, processing in the overall system. A solution for this problem is to extend the parallel execution of the applications, allowing networked nodes to distribute the workload, on peak situations, to neighbour nodes. In this context, this report proposes a framework to develop parallel and distributed real-time embedded applications, transparently using OpenMP and Message Passing Interface (MPI), within a programming model based on OpenMP. The technical report also devises an integrated timing model, which enables the structured reasoning on the timing behaviour of these hybrid architectures.

Dynamic global scheduling of parallel real-time tasks

High-level parallel languages offer a simple way for application programmers to specify parallelism in a form that easily scales with problem size, leaving the scheduling of the tasks onto processors to be performed at runtime. Therefore, if the underlying system cannot efficiently execute those applications on the available cores, the benefits will be lost. In this paper, we consider how to schedule highly heterogenous parallel applications that require real-time performance guarantees on multicore processors. The paper proposes a novel scheduling approach that combines the global Earliest Deadline First (EDF) scheduler with a priority-aware work-stealing load balancing scheme, which enables parallel realtime tasks to be executed on more than one processor at a given time instant. Experimental results demonstrate the better scalability and lower scheduling overhead of the proposed approach comparatively to an existing real-time deadline-oriented scheduling class for the Linux kernel.

Server-based scheduling of parallel real-time tasks

Multicore platforms have transformed parallelism into a main concern. Parallel programming models are being put forward to provide a better approach for application programmers to expose the opportunities for parallelism by pointing out potentially parallel regions within tasks, leaving the actual and dynamic scheduling of these regions onto processors to be performed at runtime, exploiting the maximum amount of parallelism. It is in this context that this paper proposes a scheduling approach that combines the constant-bandwidth server abstraction with a priority-aware work-stealing load balancing scheme which, while ensuring isolation among tasks, enables parallel tasks to be executed on more than one processor at a given time instant.