Real-time Parallel Applications on Many-core Architectures

Presented at INForum - Simpósio de Informática (INFORUM 2015). 7 to 8, Sep, 2015. Portugal.

Parallel Software framework for time-critical many-core systems

The recent technological advancements and market trends are causing an interesting phenomenon towards the convergence of High-Performance Computing (HPC) and Embedded Computing (EC) domains. On one side, new kinds of HPC applications are being required by markets needing huge amounts of information to be processed within a bounded amount of time. On the other side, EC systems are increasingly concerned with providing higher performance in real-time, challenging the performance capabilities of current architectures. The advent of next-generation many-core embedded platforms has the chance of intercepting this converging need for predictable high-performance, allowing HPC and EC applications to be executed on efficient and powerful heterogeneous architectures integrating general-purpose processors with many-core computing fabrics. To this end, it is of paramount importance to develop new techniques for exploiting the massively parallel computation capabilities of such platforms in a predictable way. P-SOCRATES will tackle this important challenge by merging leading research groups from the HPC and EC communities. The time-criticality and parallelisation challenges common to both areas will be addressed by proposing an integrated framework for executing workload-intensive applications with real-time requirements on top of next-generation commercial-off-the-shelf (COTS) platforms based on many-core accelerated architectures. The project will investigate new HPC techniques that fulfil real-time requirements. The main sources of indeterminism will be identified, proposing efficient mapping and scheduling algorithms, along with the associated timing and schedulability analysis, to guarantee the real-time and performance requirements of the applications.

Parallel run-time for CO-OPN

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Avaliação dos mecanismos de concorrência na API do Java 8

As plataformas com múltiplos núcleos tornaram a programação paralela/concorrente num tópico de interesse geral. Diversos modelos de programação têm vindo a ser propostos, facilitando aos programadores a identificação de regiões de código potencialmente paralelizáveis, deixando ao sistema operativo a tarefa de as escalonar dinamicamente em tempo de execução, explorando o maior grau possível de paralelismo. O Java não foge a esta tendência, disponibilizando ao programador um número crescente de bibliotecas de mecanismos de sincronização e paralelização de código. Neste contexto, esta tese apresenta e discute um conjunto de resultados obtidos através de testes intensivos à eficiência de algoritmos de ordenação implementados com recurso aos mecanismos de concorrência da API do Java 8 (Threads, Threadpools, ExecutorService, CountdownLach, ExecutorCompletionService e ForkJoinPools) em sistemas com um número de núcleos variável. Para cada um dos mecanismos, são apresentadas conclusões sobre o seu funcionamento e discutidos os cenários em que o seu uso pode ser rentabilizado de modo a serem obtidos melhores tempos de execução.

Parallel programming in biomedical signal processing

Dissertação para obtenção do Grau de Mestre em Engenharia Biomédica

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.

A system’s approach to cache hierarchy-aware decomposition of data-parallel computations

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Optimization of breast tomosynthesis image reconstruction using parallel computing

Breast cancer is the most common cancer among women, being a major public health problem. Worldwide, X-ray mammography is the current gold-standard for medical imaging of breast cancer. However, it has associated some well-known limitations. The false-negative rates, up to 66% in symptomatic women, and the false-positive rates, up to 60%, are a continued source of concern and debate. These drawbacks prompt the development of other imaging techniques for breast cancer detection, in which Digital Breast Tomosynthesis (DBT) is included. DBT is a 3D radiographic technique that reduces the obscuring effect of tissue overlap and appears to address both issues of false-negative and false-positive rates. The 3D images in DBT are only achieved through image reconstruction methods. These methods play an important role in a clinical setting since there is a need to implement a reconstruction process that is both accurate and fast. This dissertation deals with the optimization of iterative algorithms, with parallel computing through an implementation on Graphics Processing Units (GPUs) to make the 3D reconstruction faster using Compute Unified Device Architecture (CUDA). Iterative algorithms have shown to produce the highest quality DBT images, but since they are computationally intensive, their clinical use is currently rejected. These algorithms have the potential to reduce patient dose in DBT scans. A method of integrating CUDA in Interactive Data Language (IDL) is proposed in order to accelerate the DBT image reconstructions. This method has never been attempted before for DBT. In this work the system matrix calculation, the most computationally expensive part of iterative algorithms, is accelerated. A speedup of 1.6 is achieved proving the fact that GPUs can accelerate the IDL implementation.

A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP

The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.

Age effects on EEG correlates of the Wisconsin card sorting test

Body and brain undergo several changes with aging. One of the domains in which these changes are more remarkable relates with cognitive performance. In the present work, electroencephalogram (EEG) markers (power spectral density and spectral coherence) of age-related cognitive decline were sought whilst the subjects performed the Wisconsin Card Sorting Test (WCST). Considering the expected age-related cognitive deficits, WCST was applied to young, mid-age and elderly participants, and the theta and alpha frequency bands were analyzed. From the results herein presented, higher theta and alpha power were found to be associated with a good performance in the WCST of younger subjects. Additionally, higher theta and alpha coherence were also associated with good performance and were shown to decline with age and a decrease in alpha peak frequency seems to be associated with aging. Additionally, inter-hemispheric long-range coherences and parietal theta power were identified as age-independent EEG correlates of cognitive performance. In summary, these data reveals age-dependent as well as age-independent EEG correlates of cognitive performance that contribute to the understanding of brain aging and related cognitive deficits.

An evolutionary approach to the use of Petri net based models: from parallel controllers to HW/SW co-design

"A workshop within the 19th International Conference on Applications and Theory of Petri Nets - ICATPN’1998"

An illustrated flora of the northern United States, Canada and the British possessions : from Newfoundland to the parallel of the southern boundary of Virginia, and from the Atlantic Ocean westward to the 102d meridian / by Nathaniel Lord Britton and Hon. Addison Brown.

3

Participación del tráfico y la distribución de proteínas en la polaridad y el desarrollo de procesos neuronales. Protein sorting and trafficking participation in neuronal processes polarity and development.

El estudio del tráfico intracelular en neuronas ha despertado gran interés en los últimos años, debido a que un gran número de enfermedades neurodegenerativas y neuropsiquiátricas parecen tener origen en en el transporte defectuoso de proteínas en estos tipos celulares. Mediante el uso de técnicas de biología celular y molecular, fuimos capaces de describir una de las vías que regula la fisión de las vesículas que llevan su cargo desde la última cisterna del Aparato de Golgi hacia la superficie celular en células epiteliales no polarizadas. Uno de los componentes clave de esa vía resultó ser la Proteina Kinasa D1 (PKD1), cuya actividad en el Aparato de Golgi es esencial para un normal transporte intracelular. Sorprendentemente, observamos que la PKD1 en neuronas con polaridad establecida no regula la fisión en el Golgi, pero si estaría involucrada en la selectividad y distribución (sorting) de vesículas cuyo cargo debe ser específicamente dirigido a las membranas dendríticas. El bloqueo de la actividad de la PKD1 no solamente cambia el destino final de estos cargos, que son enviados de esta forma a la membrana terminal del axón, sino que también es capaz de inducir defectos en el desarrollo y crecimiento de los procesos dendríticos a largo plazo. En este proyecto estudiaremos de que manera influye la perturbación del sorting, en ausencia de PKD1 activa y de otros componentes que la regulan, en la distribución de receptores de factores neurotróficos y de neurotransmisores glutamatérgicos, y cómo estos cambios en su distribución afectan el número, tamaño, y funcionalidad de los procesos neuronales (axones y dendritas). Estos resultados contribuirán a adquirir mayores conocimientos de los mecanismos dependientes del transporte y sorting de proteínas de membrana que participan en la regulación del crecimiento neuronal, los cuales a su vez aportarán información valiosa en la comprensión de un gran número de enfermedades neurológicas. The study of intracellular trafficking in neurons has arisen a great deal of interest in the last years, since a great number of neurodegenerative and neuropsychiatric disorders seem to be originated in abnormal protein transport in these type of cells. Using cell and molecular biology methodologies, we have been capable of describe one of the pathways that regulate the fission of vesicles that carry their cargo from the last Golgi Apparatus cisternae to the cell surface in non-polarized epithelial cells. One of the key components in this pathway is the Protein Kinase D1 (PKD1), whose activity in the Golgi Apparatus is essential for a normal intracelular transport. Surprisingly, we have observed that PKD1 does not regulate fission in neurons with established polarity, but it would be involved in vesicles' sorting at Golgi, particularly of those that carry specific dendritic cargo. Blocking PKD1 activity changes the final destination of these cargoes, which is now sent to the axons' terminal membranes, and also produces late dendritic development and growing defects. In this project we will study how sorting perturbation in absence of PKD1 and its regulators activities influences selectivity and distribution of neurotrophic and neurotransmitter receptors, and how these sorting changes affect number, size and functionality of neuronal processes (axons and dendrites). These results will help to acquire greater knowledge about transport and sorting mechanisms of neuronal growth regulatory membrane proteins. In addition, these studies will contribute with new valuable information necessary to understand numerous neurological diseases.

An illustrated flora of the northern United States, Canada and the British possessions : from Newfoundland to the parallel of the southern boundary of Virginia, and from the Atlantic Ocean westward to the 102d meridian / by Nathaniel Lord Britton and Hon. Addison Brown.

2