Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

A framework for scientific computing with GPUs

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

An agent based architecture for material handling systems

Dissertação para obtenção do Grau de Mestre em Engenharia Electrotécnica e de Computadores

A distributed platform for the volunteer execution of workflows on a local area network

Thesis submitted in fulfilment of the requirements for the Degree of Master of Science in Computer Science

Caraterização do acesso ao Centro Hospitalar Lisboa Norte, EPE : análise do acesso e da utilização da consulta externa e da urgência do Centro Hospitalar Lisboa Norte, EPE

RESUMO - Introdução: As alterações verificadas no dimensionamento e na redistribuição da rede de prestação de cuidados hospitalares, nomeadamente no que confere à reorganização das áreas de influência, e, cumulativamente, à abertura do Hospital Beatriz Ângelo, tornam evidente a necessidade de se analisar o acesso e a utilização da consulta externa e da urgência, antes e depois destas alterações. Objetivo: Este trabalho de investigação tem como principal objetivo analisar o acesso e a utilização da consulta externa e da urgência do Centro Hospitalar Lisboa Norte e verificar a evolução desse mesmo acesso, no período de 2010 a 2013. Material e Métodos: Estudo descritivo que visa determinar a frequência e a distribuição dos episódios de Consulta Externa e de Urgência do Centro Hospitalar Lisboa Norte. Foram considerados todos os episódios de consulta externa (3785579 episódios) e de urgência (1140052 episódios) ocorridos entre 1 de janeiro de 2010 e 31 de dezembro de 2013. Resultados: Entre 2010 e 2013, verificou-se o aumento de +2,3% no número de primeiras consultas e de +5%, em consultas subsequentes. As especialidades médicas com maior afluência são Oftalmologia, Dermatologia I, Pediatria e Otorrinolaringologia I. Observou-se, no total de consultas, qual a percentagem que, em cada ano, obteve um tempo de espera inferior a 1 mês, entre a marcação e a realização da consulta: 56,7%, em 2010; 54,3%, em 2011; 55% em 2012; 56,2%, em 2013. Verificou-se o decréscimo do número de atendimentos de urgência, no período em análise, de -38,9%. Cerca de 90% dos atendimentos de urgência respeitam a utentes que acorrem diretamente à urgência sem virem referenciados de outras unidades de saúde. Os meses de janeiro e fevereiro são aqueles que registam maior afluência, 9,9% e 8,8%, respetivamente. O período de maior afluência regista-se entre as 9 e as 11 horas, representando 20,7% dos episódios, em 2010, 21,2%, em 2011, 21% e 20,5%, em 2012 e 2013, respetivamente. Conclusão: Face à alteração da área de influência do Centro Hospitalar Lisboa Norte, torna-se necessária a adaptação da capacidade instalada para haja um sobredimensionamento face à procura, bem como a adequação de recursos internos, financeiros, humanos e tecnológicos.

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.