Towards an algorithmic skeleton framework for programming the Intel R Xeon PhiTM processor

The Intel R Xeon PhiTM is the first processor based on Intel’s MIC (Many Integrated Cores) architecture. It is a co-processor specially tailored for data-parallel computations, whose basic architectural design is similar to the ones of GPUs (Graphics Processing Units), leveraging the use of many integrated low computational cores to perform parallel computations. The main novelty of the MIC architecture, relatively to GPUs, is its compatibility with the Intel x86 architecture. This enables the use of many of the tools commonly available for the parallel programming of x86-based architectures, which may lead to a smaller learning curve. However, programming the Xeon Phi still entails aspects intrinsic to accelerator-based computing, in general, and to the MIC architecture, in particular. In this thesis we advocate the use of algorithmic skeletons for programming the Xeon Phi. Algorithmic skeletons abstract the complexity inherent to parallel programming, hiding details such as resource management, parallel decomposition, inter-execution flow communication, thus removing these concerns from the programmer’s mind. In this context, the goal of the thesis is to lay the foundations for the development of a simple but powerful and efficient skeleton framework for the programming of the Xeon Phi processor. For this purpose we build upon Marrow, an existing framework for the orchestration of OpenCLTM computations in multi-GPU and CPU environments. We extend Marrow to execute both OpenCL and C++ parallel computations on the Xeon Phi. We evaluate the newly developed framework, several well-known benchmarks, like Saxpy and N-Body, will be used to compare, not only its performance to the existing framework when executing on the co-processor, but also to assess the performance on the Xeon Phi versus a multi-GPU environment.

A logical foundation for session-based concurrent computation

Linear logic has long been heralded for its potential of providing a logical basis for concurrency. While over the years many research attempts were made in this regard, a Curry-Howard correspondence between linear logic and concurrent computation was only found recently, bridging the proof theory of linear logic and session-typed process calculus. Building upon this work, we have developed a theory of intuitionistic linear logic as a logical foundation for session-based concurrent computation, exploring several concurrency related phenomena such as value-dependent session types and polymorphic sessions within our logical framework in an arguably clean and elegant way, establishing with relative ease strong typing guarantees due to the logical basis, which ensure the fundamental properties of type preservation and global progress, entailing the absence of deadlocks in communication. We develop a general purpose concurrent programming language based on the logical interpretation, combining functional programming with a concurrent, session-based process layer through the form of a contextual monad, preserving our strong typing guarantees of type preservation and deadlock-freedom in the presence of general recursion and higher-order process communication. We introduce a notion of linear logical relations for session typed concurrent processes, developing an arguably uniform technique for reasoning about sophisticated properties of session-based concurrent computation such as termination or equivalence based on our logical approach, further supporting our goal of establishing intuitionistic linear logic as a logical foundation for sessionbased concurrency.

Machine ethics via logic programming

Machine ethics is an interdisciplinary field of inquiry that emerges from the need of imbuing autonomous agents with the capacity of moral decision-making. While some approaches provide implementations in Logic Programming (LP) systems, they have not exploited LP-based reasoning features that appear essential for moral reasoning. This PhD thesis aims at investigating further the appropriateness of LP, notably a combination of LP-based reasoning features, including techniques available in LP systems, to machine ethics. Moral facets, as studied in moral philosophy and psychology, that are amenable to computational modeling are identified, and mapped to appropriate LP concepts for representing and reasoning about them. The main contributions of the thesis are twofold. First, novel approaches are proposed for employing tabling in contextual abduction and updating – individually and combined – plus a LP approach of counterfactual reasoning; the latter being implemented on top of the aforementioned combined abduction and updating technique with tabling. They are all important to model various issues of the aforementioned moral facets. Second, a variety of LP-based reasoning features are applied to model the identified moral facets, through moral examples taken off-the-shelf from the morality literature. These applications include: (1) Modeling moral permissibility according to the Doctrines of Double Effect (DDE) and Triple Effect (DTE), demonstrating deontological and utilitarian judgments via integrity constraints (in abduction) and preferences over abductive scenarios; (2) Modeling moral reasoning under uncertainty of actions, via abduction and probabilistic LP; (3) Modeling moral updating (that allows other – possibly overriding – moral rules to be adopted by an agent, on top of those it currently follows) via the integration of tabling in contextual abduction and updating; and (4) Modeling moral permissibility and its justification via counterfactuals, where counterfactuals are used for formulating DDE.

Modelação não-linear do comportamento de vigas-parede

Com a evolução dos recursos computacionais e o desenvolvimento dos modelos constitutivos disponíveis na avaliação do comportamento estrutural de elementos de betão armado, é comum recorrer-se cada vez mais a modelos numéricos que consideram a não-linearidade física e geométrica. As simulações numéricas obtidas com recurso a este tipo de modelos computacionais permitem obter um historial completo do comportamento estrutural, desde o início da aplicação do carregamento, até ao colapso total da estrutura. Contudo, verifica-se que em zonas de descontinuidade geométrica em estruturas de betão armado, a evolução do padrão de fendilhação é um fenómeno relativamente complexo, cuja simulação numérica representa um desafio considerável. O objectivo deste trabalho é o de verificar a aplicabilidade do Método dos Elementos Aplicados no estudo do desenvolvimento do padrão de fendilhação em paredes de betão armado, solicitadas por um carregamento monotónico. Foi analisado um conjunto de dez paredes, todas com uma abertura que provoca uma zona de descontinuidade geométrica e, consequentemente, um padrão de fendilhação mais complexo. Cada parede tem uma pormenorização de armadura diferente, permitindo verificar a fiabilidade do modelo computacional. Os resultados numéricos foram comparados com ensaios experimentais realizados por Bounassar Filho [8], permitindo tirar conclusões sobre as vantagens e as limitações deste método, quando aplicado ao estudo de estruturas de betão armado solicitadas por cargas monotónicas.

Sintonização de controladores difusos através de técnicas de optimização não-linear com restrições

A presente dissertação tem como objetivo principal a implementação de uma arquitetura baseada em algoritmos evolutivos para a sintonização dos parâmetros do controlador PID (Proporcional-Integral-Derivativo) difuso, sendo o conceito de desempenho em malha fechada explicitamente tido em conta. A sintonização dos parâmetros do controlador difuso é realizada tendo em conta um problema de otimização com restrições, em que a função de custo a ser minimizada é descrita em termos do desempenho em malha fechada, com a dinâmica do sistema a ser aproximada por um modelo não linear. Como nas metodologias de otimização existentes, a incorporação de mecanismos de adaptação referentes às funções de pertença não é comum, na presente dissertação é tido em conta, para além da usual sintonização dos fatores de escala, a sintonização dos fatores de escala e funções de pertença em simultâneo. Os resultados experimentais realizados num sistema de referência, visam demonstrar os benefícios de incorporar as funções de pertença no processo de otimização em diferido. É também utilizado um método analítico de segunda ordem como referência, por forma a comparar o desempenho de uma abordagem de otimização global contra uma de otimização local. Finalmente é implementada uma abordagem em-linha, usando o método analítico de segunda ordem, na otimização dos fatores de escala e funções de pertença.

EFFECT – Efficient finite element code

The theme of this dissertation is the finite element method applied to mechanical structures. A new finite element program is developed that, besides executing different types of structural analysis, also allows the calculation of the derivatives of structural performances using the continuum method of design sensitivities analysis, with the purpose of allowing, in combination with the mathematical programming algorithms found in the commercial software MATLAB, to solve structural optimization problems. The program is called EFFECT – Efficient Finite Element Code. The object-oriented programming paradigm and specifically the C ++ programming language are used for program development. The main objective of this dissertation is to design EFFECT so that it can constitute, in this stage of development, the foundation for a program with analysis capacities similar to other open source finite element programs. In this first stage, 6 elements are implemented for linear analysis: 2-dimensional truss (Truss2D), 3-dimensional truss (Truss3D), 2-dimensional beam (Beam2D), 3-dimensional beam (Beam3D), triangular shell element (Shell3Node) and quadrilateral shell element (Shell4Node). The shell elements combine two distinct elements, one for simulating the membrane behavior and the other to simulate the plate bending behavior. The non-linear analysis capability is also developed, combining the corotational formulation with the Newton-Raphson iterative method, but at this stage is only avaiable to solve problems modeled with Beam2D elements subject to large displacements and rotations, called nonlinear geometric problems. The design sensitivity analysis capability is implemented in two elements, Truss2D and Beam2D, where are included the procedures and the analytic expressions for calculating derivatives of displacements, stress and volume performances with respect to 5 different design variables types. Finally, a set of test examples were created to validate the accuracy and consistency of the result obtained from EFFECT, by comparing them with results published in the literature or obtained with the ANSYS commercial finite element code.

Rely-guarantee protocols for safe interference over shared memory

Mutable state can be useful in certain algorithms, to structure programs, or for efficiency purposes. However, when shared mutable state is used in non-local or nonobvious ways, the interactions that can occur via aliases to that shared memory can be a source of program errors. Undisciplined uses of shared state may unsafely interfere with local reasoning as other aliases may interleave their changes to the shared state in unexpected ways. We propose a novel technique, rely-guarantee protocols, that structures the interactions between aliases and ensures that only safe interference is possible. We present a linear type system outfitted with our novel sharing mechanism that enables controlled interference over shared mutable resources. Each alias is assigned separate, local roles encoded in a protocol abstraction that constrains how an alias can legally use that shared state. By following the spirit of rely-guarantee reasoning, our rely-guarantee protocols ensure that only safe interference can occur but still allow many interesting uses of shared state, such as going beyond invariant and monotonic usages. This thesis describes the three core mechanisms that enable our type-based technique to work: 1) we show how a protocol models an alias’s perspective on how the shared state evolves and constrains that alias’s interactions with the shared state; 2) we show how protocols can be used while enforcing the agreed interference contract; and finally, 3) we show how to check that all local protocols to some shared state can be safely composed to ensure globally safe interference over that shared memory. The interference caused by shared state is rooted at how the uses of di↵erent aliases to that state may be interleaved (perhaps even in non-deterministic ways) at run-time. Therefore, our technique is mostly agnostic as to whether this interference was the result of alias interleaving caused by sequential or concurrent semantics. We show implementations of our technique in both settings, and highlight their di↵erences. Because sharing is “first-class” (and not tied to a module), we show a polymorphic procedure that enables abstract compositions of protocols. Thus, protocols can be specialized or extended without requiring specific knowledge of the interference produce by other protocols to that state. We show that protocol composition can ensure safety even when considering abstracted protocols. We show that this core composition mechanism is sound, decidable (without the need for manual intervention), and provide an algorithm implementation.

Quadratic programming versus second order con programming in portfolio optimization

Despite the extensive literature in finding new models to replace the Markowitz model or trying to increase the accuracy of its input estimations, there is less studies about the impact on the results of using different optimization algorithms. This paper aims to add some research to this field by comparing the performance of two optimization algorithms in drawing the Markowitz Efficient Frontier and in real world investment strategies. Second order cone programming is a faster algorithm, appears to be more efficient, but is impossible to assert which algorithm is better. Quadratic Programming often shows superior performance in real investment strategies.

Implementação de um modelo de geometric semantic genetic programming para aplicação naval

Recaí sob a responsabilidade da Marinha Portuguesa a gestão da Zona Económica Exclusiva de Portugal, assegurando a sua segurança da mesma face a atividades criminosas. Para auxiliar a tarefa, é utilizado o sistema Oversee, utilizado para monitorizar a posição de todas as embarcações presentes na área afeta, permitindo a rápida intervenção da Marinha Portuguesa quando e onde necessário. No entanto, o sistema necessita de transmissões periódicas constantes originadas nas embarcações para operar corretamente – casos as transmissões sejam interrompidas, deliberada ou acidentalmente, o sistema deixa de conseguir localizar embarcações, dificultando a intervenção da Marinha. A fim de colmatar esta falha, é proposto adicionar ao sistema Oversee a capacidade de prever as posições futuras de uma embarcação com base no seu trajeto até à cessação das transmissões. Tendo em conta os grandes volumes de dados gerados pelo sistema (históricos de posições), a área de Inteligência Artificial apresenta uma possível solução para este problema. Atendendo às necessidades de resposta rápida do problema abordado, o algoritmo de Geometric Semantic Genetic Programming baseado em referências de Vanneschi et al. apresenta-se como uma possível solução, tendo já produzido bons resultados em problemas semelhantes. O presente trabalho de tese pretende integrar o algoritmo de Geometric Semantic Genetic Programming desenvolvido com o sistema Oversee, a fim de lhe conceder capacidades preditivas. Adicionalmente, será realizado um processo de análise de desempenho a fim de determinar qual a ideal parametrização do algoritmo. Pretende-se com esta tese fornecer à Marinha Portuguesa uma ferramenta capaz de auxiliar o controlo da Zona Económica Exclusiva Portuguesa, permitindo a correta intervenção da Marinha em casos onde o atual sistema não conseguiria determinar a correta posição da embarcação em questão.

Mapeamento do uso e cobertura da terra a partir da segmentação e classificação de imagens-fração solo, sombra e vegetação derivadas do modelo linear de mistura aplicado a dados do sensor TM/Landsat5, na região do reservatório de Tucuruí - PA

Técnicas de sensoriamento remoto são fundamentais para o monitoramento das mudanças de uso da terra, principalmente em áreas extensas como a Amazônia. O mapeamento de uso da terra, geralmente é realizado por métodos de classificação manual ou digital pixel a pixel, os quais consomem muito tempo. Este estudo aborda a aplicação do modelo linear de mistura em uma imagem Landsat-TM segmentada para o mapeamento das classes de uso da terra na região do reservatório de Tucuruí-PA para os anos de 1996 e 2001.

Detecção de cicatrizes de áreas queimadas baseada no modelo linear de mistura espectral e imagens índice de vegetação utilizando dados multitemporais do sensor MODIS/TERRA no estado do Mato Grosso, Amazônia brasileira

O objetivo desta pesquisa foi avaliar os dados do sensor MODIS para detectar e monitorar cicatrizes de áreas recém queimadas. Utilizamos imagens da reflectância de superfície do sensor MODIS: produto MOD09 (dia 5 de outubro) e produto MOD13A1 (meses de outubro e novembro). Foi avaliada também uma série temporal de um ano dos índices de vegetação (IV) EVI e NDVI (produto MOD13A1). Uma imagem do sensor ETM+ (dia 5 de outubro) foi utilizada como base para a delimitação dos polígonos amostrais e avaliação dos dados MODIS devido a sua melhor resolução espacial. A metodologia focou na aplicação do modelo linear de mistura espectral nas imagens reflectância para a geração das imagens fração sombra. Análises de regressão foram efetuadas para comparação entre o percentual de sombra derivado da imagem ETM+ e das imagens MODIS. As alterações multitemporais nas imagens IV foram avaliadas com base no teste de Tukey. Os resultados mostraram que a imagem fração sombra gerada a partir do produto MOD09 apresentou um R² = 0,66 (p < 0,01) em relação aos dados ETM+. Para as imagens do produto MOD13A1 não foram identificadas relações significativas. Os IV dentro dos mesmos polígonos apresentaram uma variação sazonal durante o ano. No entanto, não houve uma diminuição significativa dos valores destes índices nos meses onde foram observadas as cicatrizes de áreas recém queimadas. Portanto, o produto MOD09 mostrou-se mais eficiente que o produto MOD13A1 para a detecção de cicatrizes de áreas recém queimadas. A análise multitemporal dos IV sugeriu que não foi possível detectar este mesmo padrão na área de estudo.