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.

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.

Optimization of multi-stage amplifiers in deep-submicron CMOS using a distributed/parallel genetic algorithm

IEEE International Symposium on Circuits and Systems, pp. 724 – 727, Seattle, EUA

A study on parallel versus sequential relational fuzzy clustering methods

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

Parallel run-time for CO-OPN

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

Parallel programming in biomedical signal processing

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

The impacts of free trade agreements on use of antidumping

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Economics from the NOVA – School of Business and Economics

When do trade reforms imply larger poverty reductions?

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Economics from the NOVA – School of Business and Economics

Supply chain integration model: practices and customer values

Dissertation to obtain PhD in Industrial Engineering

Endogenous spillovers in the trade-off between centralization and decentralization

In this paper, we revisit the classical trade-off between centralized and decentralized provision of local public goods, in a setting where interregional spillovers depend on the level of a national public good. We compare the standard benevolent planner approach with a political economy in which decisions, in a centralized system, are undertaken by a non-cooperative legislature with no separation of powers. We observe that the policy-maker in a centralized system is able to play both with local public goods and spillovers, a mechanism that is not available under a decentralized system. When compared to the traditional exogenous spillovers assumption, this improves the case for centralization under the standard benevolent planner approach. However, the same is not necessarily true in the non-cooperative legislature, as in this case the interests of the legislator do not need to be aligned with those of the society. Finally, we extend the traditional political economy analysis by considering a legislature in which decisions are undertaken by different committees (separation of powers), and show that it performs better than the original non-cooperative legislature, greatly improving the case for centralization.

Determinants of Portuguese trade: 1986-2010

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

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