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.

Software transactional memory as a building block for parallel embedded realtime systems

The recent trends of chip architectures with higher number of heterogeneous cores, and non-uniform memory/non-coherent caches, brings renewed attention to the use of Software Transactional Memory (STM) as a fundamental building block for developing parallel applications. Nevertheless, although STM promises to ease concurrent and parallel software development, it relies on the possibility of aborting conflicting transactions to maintain data consistency, which impacts on the responsiveness and timing guarantees required by embedded real-time systems. In these systems, contention delays must be (efficiently) limited so that the response times of tasks executing transactions are upper-bounded and task sets can be feasibly scheduled. In this paper we assess the use of STM in the development of embedded real-time software, defending that the amount of contention can be reduced if read-only transactions access recent consistent data snapshots, progressing in a wait-free manner. We show how the required number of versions of a shared object can be calculated for a set of tasks. We also outline an algorithm to manage conflicts between update transactions that prevents starvation.

A parallel programming model for ada

Over the last three decades, computer architects have been able to achieve an increase in performance for single processors by, e.g., increasing clock speed, introducing cache memories and using instruction level parallelism. However, because of power consumption and heat dissipation constraints, this trend is going to cease. In recent times, hardware engineers have instead moved to new chip architectures with multiple processor cores on a single chip. With multi-core processors, applications can complete more total work than with one core alone. To take advantage of multi-core processors, parallel programming models are proposed as promising solutions for more effectively using multi-core processors. This paper discusses some of the existent models and frameworks for parallel programming, leading to outline a draft parallel programming model for Ada.

Bridge architecture to interconnect hybrid wired/wireless PROFIBUS networks

The integration of wired and wireless technologies in modern manufacturing plants is now of paramount importance for the competitiveness of any industry. Being PROFIBUS the most widely used technology in use for industrial communications, several solutions have been proposed to provide PROFIBUS networks with wireless communications. One of them, the bridge-based hybrid wired/wireless PROFIBUS network approach, proposes an architecture in which the Intermediate Systems operate at Data Link Layer level, as bridges. In this paper, we propose an architecture for the implementation of such a bridge and the required protocols to handle communication between stations in different domains and the mobility of wireless stations.

Repeater vs. Bridge-based hybrid wired/wireless PROFIBUS networks: a comparative performance analysis

In the last years, several solutions have been proposed to extend PROFIBUS in order to support wired and wireless network stations in the same network. In this paper we compare two of those solutions, one in which the interconnection between wired and wireless stations is made by repeaters and another in which the interconnection is made by bridges. The comparison is both qualitative and numerical, based on simulation models of both architectures.

Parallel hyperspectral unmixing on GPUs

This letter presents a new parallel method for hyperspectral unmixing composed by the efficient combination of two popular methods: vertex component analysis (VCA) and sparse unmixing by variable splitting and augmented Lagrangian (SUNSAL). First, VCA extracts the endmember signatures, and then, SUNSAL is used to estimate the abundance fractions. Both techniques are highly parallelizable, which significantly reduces the computing time. A design for the commodity graphics processing units of the two methods is presented and evaluated. Experimental results obtained for simulated and real hyperspectral data sets reveal speedups up to 100 times, which grants real-time response required by many remotely sensed hyperspectral applications.

Parallel texts alignment

Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática

A shared-disk parallel cluster file system

Dissertação apresentada para obtenção do Grau de Doutor em Informática Pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

A debugging engine for parallel and distributed programs

Dissertação apresentada para a obtenção do Grau de Doutor em Informática pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia.

Control of a 6-DOF parallel manipulator through a mechatronic approach

This paper shows that a hierarchical architecture, distributing several control actions in growing levels of complexity and using resources of reconfigurable computing, enables one to take into account the ease of future modifications, updates and improvements in robotic applications. An experimental example of a Stewart—Gough platform control (a platform applied as the solution to countless practical problems) is presented using reconfigurable computing. The software and hardware developed are structured in independent blocks. This open architecture implementation allows easy expansion of the system and better adaptation of the platform to its related tasks.

Estudo de uma instalação de climatização adiabática

Esta dissertação teve como objetivo o estudo de uma central de climatização adiabática, que tem como finalidade controlar a temperatura e a humidade de um salão com equipamentos de torcedura e de bobinagem, pertencente à Continental - ITA. Foi realizado um levantamento de dados relativamente à temperatura e humidade interior e exterior do referido salão. Verificou-se que estes parâmetros não estavam dentro dos valores ótimos desejados, 26 ± 1˚C e 50 ± 5%, e por isso foi necessário estimar as necessidades nominais de arrefecimento. Este valor foi determinado a partir do Regulamento das Características de Comportamento Térmico dos Edifícios (RCCTE), obtendo-se o valor de 79 kWh/m2.˚C. No sentido de avaliar se as centrais de climatização instaladas no salão em estudo satisfaziam estas necessidades, calcularam-se as suas capacidades de arrefecimento obtendo-se um valor máximo de 64 kWh/m2.˚C. Paralelamente a este estudo, foi calculada a eficiência de humidificação para cada central nos meses de março e setembro. Os valores obtidos foram oscilantes obtendo-se um valor máximo de 100% em setembro. Este fato deve-se à temperatura exterior neste mês ser mais alta e, por consequência, a eficiência de humidificação da central é maior, pois a quantidade de água que o ar pode conter na sua composição é também mais elevada. Com o objetivo de colmatar a diferença entre as necessidades nominais de arrefecimento e a capacidade de arrefecimento das centrais, foram analisadas algumas soluções que, a serem implementadas, poderiam ajudar na poupança energética. Uma dessas soluções era a substituição do sistema atual de humidificação por um sistema mais eficiente de alta pressão. Com o estudo económico deste investimento obteve-se um período de retorno de dois anos. Foram ainda apresentados mais dois investimentos onde foi alterado o sistema de controlo automático existente, obtendo-se para um, dois anos de período de retorno e para o outro três anos e meio.