João Lourenço

Most known teaching experiences focus on parallel computing courses only, but some teaching experiences on distributed computing courses have also been reported. In this paper we describe a course on Parallel and Distributed Processing that is taught at undergraduate level in the Computer Science degree of our University.This course presents an integrated approach concerning concurrency, parallelism, and distribution issues. It's a breadth-first course addressing a wide spectrum of abstractions: the theoretical component focus on the fundamental abstractions to model concurrent systems, including process cooperation schemes, concurrent programming models, data and control distribution, concurrency control and recovery in transactional systems, and parallel processing models; the practical component illustrates the design and implementation issues involved in selected topics such as a data and control distribution problem, a distributed transaction-based support system and a parallel algorithm.We also discuss how this approach has been contributing to prepare the student to further actions regarding research and development of concurrent, distributed, or parallel systems.

In the recent past, multiple techniques and tools have been proposed and contributed to improve the distributed debugging functionalities, in several distinct aspects, such as handling the non-determinism, allowing cyclic interactive debugging of parallel programs, and providing more user-friendly interfaces. However, most of these tools are tied to a specific programming language and provide rigid graphical user interfaces. So they cannot easily adapt to support distinct abstraction levels or user interfaces. They also don't provide adequate support for cooperation with other tools in a software engineering environment. In this paper we discuss several dimensions which may contribute to develop more flexible distributed debuggers. We describe Fiddle, a distributed debugging tool which aims at overcoming some of the above limitations.

Software Transactional Memory algorithms associate metadata with the memory locations accessed during a transactions lifetime. This metadata may be stored in an external table and accessed by way of a function that maps the address of each memory location with the table entry that keeps its metadata (this is the out-place or external scheme); or alternatively may be stored adjacent to the associated memory cell by wrapping them together (the in-place scheme). In transactional memory multi-version algorithms, several versions of the same memory location may exist. The efficient implementation of these algorithms requires a one-to-one correspondence between each memory location and its list of past versions, which is stored as metadata. In this chapter we address the matter of the efficient implementation of multi-version algorithms in Java by proposing and evaluating a novel in-place metadata scheme for the Deuce framework. This new scheme is based in Java Bytecode transformation techniques and its use requires no changes to the application code. Experimentation indicates that multi-versioning STM algorithms implemented using our new in-place scheme are in average 6 × faster than when implemented with the out-place scheme.

We discuss debugging prototypes that can easily support new functionalities, depending on the requirements of high-level computational models, and allowing a coherent integration with other tools in a software engineering environment. Concerning the first aspect, we propose a framework that identifies two distinct levels of functionalities that should be supported by a parallel and distributed debugger using: a process and thread-level, and a coordination level concerning sets of processes or threads. An incremental approach is used to effectively develop prototypes that support both functionalities. Concerning the second aspect, we discuss how the interfacing with other tools has influenced the design of a process-level debugging interface (PDBG) and a distributed monitoring and control layer called (DAMS).

To provide high-level graphical support for PVM (Parallel Virtual Machine) based program development, a complex programming environment (GRADE) is being developed. GRADE currently provides tools to construct, execute, debug, monitor and visualise message-passing parallel programs. It offers high-level graphical programming abstraction mechanism to construct parallel applications by introducing a new graphical language called GRAPNEL. GRADE also provides the programmer with the same graphical user interface during the program design and debugging stages. A distributed debugging engine (DDBG) assists the user in debugging GRAPNEL programs on distributed memory computer architectures. Tape/PVM and PROVE support the performance monitoring and visualization of parallel programs developed in the GRADE environment.

n/a

In this paper we address a solution for detecting and tolerating one of the most typical concurrency bugs: atomicity violations. More specifically, we address High-Level Atomicity Violations (HLAV). High-level atomicity violations result from the misspecification of the scope of an atomic block, by splitting it in two or more atomic blocks which may be interleaved with other atomic blocks. Figure 1 shows an example of this type of atomicity violation. The intuitive idea behind HLAV is that if two shared data items (e.g., memory locations) were both accessed inside an atomic block, they are interrelated and probably the programmer intention is that there shall be no interleavings between these two accesses. Therefore, if (in the same program) this two addresses are accessed separately in different atomic blocks, an unfortunate interleaving may cause an atomicity violation.

Most known teaching experiences focus on parallel computing courses only, but some teaching experiences on distributed computing courses have also been reported. In this paper we describe a course on Parallel and Distributed Processing that is taught at undergraduate level in the Computer Science degree of our University.This course presents an integrated approach concerning concurrency, parallelism, and distribution issues. It's a breadth-first course addressing a wide spectrum of abstractions: the theoretical component focus on the fundamental abstractions to model concurrent systems, including process cooperation schemes, concurrent programming models, data and control distribution, concurrency control and recovery in transactional systems, and parallel processing models; the practical component illustrates the design and implementation issues involved in selected topics such as a data and control distribution problem, a distributed transaction-based support system and a parallel algorithm.We also discuss how this approach has been contributing to prepare the student to further actions regarding research and development of concurrent, distributed, or parallel systems.

To achieve a certain degree of confidence that a given program follows its specification, a testing phase must be included in the program development process, and also a complementary debugging phase to help locating the program's bugs. This paper presents an environment which results of the composition and integration of two basic tools: STEPS (Structural TEsting of Parallel Software), which is a testing tool, and DDBG (Distributed DeBuGger), which is a debugging tool. The two tools are presented individually as stand-alone tools, and we describe how they were combined through the use of another intermediate tool: DEIPA (Deterministic re-Execution and Interactive Program Analysis). We claim that the result achieved is a very effective testing and debugging environment.

n/a

A evolução do hardware dos computadores para arquitecturas paralelas, incentivou a concepção de novos modelos de programação e o desenvolvimento dos sistemas de suporte à execução correspondentes, de forma a conseguir uma melhor exploração do paralelismo. A linguagem de programação Prolog, pelas suas características declarativas e operacionais, tem vindo a ser objecto de estudo nesta área, através de adaptações da linguagem e/ou da sua máquina de inferência. Este trabalho incide sobre os aspectos de concepção e implementação de um modelo de um sistema de suporte à execução de programas em Prolog, em arquitecturas de múltiplos processadores, com unidades de memória fisicamente distribuídas. O modelo propõe extensões a um executor de Prolog convencional, de forma a disponibilizar funcionalidades que permitam o controlo do paralelismo e da distribuição. Estas funcionalidades podem ser utilizadas para a implementação de modelos de linguagens lógicas concorrentes de mais alto nível, ou então serem utilizadas directamente para a programação de sistemas distribuídos, em que múltiplos executores Prolog cooperam na resolução de um golo, comunicando com base em mensagens. Para avaliar a funcionalidade do modelo proposto, concebeu-se e implementou-se um sistema de distribuição de golos Prolog, que permite recorrer a diversas estratégias para composição sequencial e paralela de golos, escondendo os aspectos de gestão explícita dos recursos efectivos. A dissertação inclui uma discussão dos aspectos mais relevantes da realização do protótipo do modelo proposto sobre uma arquitectura baseada em Transputers.

n/a

This document describes a work-in-progress development of NGen-VM, a distributed infrastructure that manages execution environments with run-time and programming language support targeting applications developed in the Java programming language, deployed over clusters of many-core computers. For each running application or suite of related applications, a dedicated single-system image will be provided, regardless of the concurrent threads running on a single machine (on several cores) or scattered on different computers. Such system images rely on a single model for concurrency management (Transactional Shared Memory Model), in order fill the gap between the hardware infrastructure of clusters of many-core nodes and the application runtime that is independent from that hardware infrastructure. Interactions between threads in the same tasks will be supported by a Transactional Memory framework that provides the programming language with Atomic and Isolated code regions. Interactions between thread on different machines will also use the Transactional Memory model, but now resorting to a Distributed Shared Memory abstraction.

Transactional memory (TM) is an increasingly popular technique for synchronising threads in multi-threaded programs. To address both correctness and performance-related issues of TM programs, one needs to monitor and analyse their execution. However, monitoring concurrent programs (including TM programs) may have a non-negligible impact on their behaviour, which may hamper the objectives of the intended analysis. In this paper, we propose several approaches for monitoring TM programs and study their impact on the behaviour of the monitored programs. The considered approaches range from specialised lightweight monitoring to generic heavyweight monitoring. The implemented monitoring tools are publicly available to the scientific community, and the implementation techniques used for lightweight monitoring of TM programs may be used as an inspiration for developing other specialised lightweight monitors.

n/a

The recent developments in virtualization change completely the panorama of the Hardware/OS deployment. New bottlenecks arise in the deployment of application stacks, where IT industry will spend most of the time to assure automation. VIRTU tool aims at managing, configuring and testing distributed ground applications of space systems on a virtualized environment, based on open tools and cross virtualization support. This tool is a spin-off of previous activities performed by the European Space Operations Center (ESOC) and thus it covers the original needs from the ground data systems infrastructure division of the European Space Agency. VIRTU is a testing oriented solution. Its ability to group several virtual machines in an assembly provides the means to easily deploy a full testing infrastructure, including the client/server relationships. The possibility of making on-demand request of the testing infrastructure will provide some infrastructure optimizations, specially having in mind that ESA maintains Ground Control software of various missions, and each mission cam potentially have a different set of System baselines and last up to 15 years. The matrix array of supported system combinations is therefore enormous and any improvement on the process provides substantial benefits to ESA, by reducing the effort and schedule of each maintenance activity. The ESOC's case study focuses on the development and validation activities of infrastructure or mission Ground Systems solutions. The Ground Systems solutions are typically composed of distributed systems that could take advantage of virtualized environments for testing purposes. Virtualization is used as way to optimize maintenance for tasks such as testing new releases and patches, test different system's configurations and replicate tests. The main benefits identified are related to deployment test environment and the possibility to have on-demand infrastructure.

In this paper we discuss several issues concerning the design and implementation of a debugger for parallel and distributed applications. This debugger uses a client-server approach to isolate the debugging user-interface from the debugging services, by way of a two-level structured approach: the component-level to observe and act upon individual processes; and the coordination-level to observe the interprocess relations and act upon them.

In this paper we present MoTh, a tool that uses static analysis to enable the automatic verification of concurrency anomalies in Transactional Memory Java programs. Currently MoTh detects high-level dataraces and stale-value errors, but it is extendable by plugging-in sensors, each sensor implementing an anomaly detecting algorithm. We validate and benchmark MoTh by applying it to a set of well known concurrent buggy programs and by close comparison of the results with other similar tools. The results achieved so far are very promising, yielding good accuracy while triggering only a very limited number of false warnings.

Concurrent programs that are free of unsynchronized ac- cesses to shared data may still exhibit unpredictable concurrency errors called atomicity violations, which include both high-level dataraces and stale-value errors. Atomicity violations occur when programmers make wrong assumptions about the atomicity scope of a code block, incorrectly splitting it in two or more atomic blocks and allow them to be interleaved with other atomic blocks. In this paper we propose a novel static analysis algorithm that works on a dependency graph of program variables and detects both high-level dataraces and stale-value errors. The algorithm was implemented for a Java Bytecode analyzer and its effectiveness was evaluated with some well known faulty programs. The results obtained show that our algorithm performs better than previous approaches, achieving higher precision for small and medium sized programs, making it a good basis for a practical tool.

A programação concorrente obriga o programador a sincronizar os acessos concorrentes a regiões de memória partilhada, contudo esta abordagem não é suficiente para evitar todas as anomalias que podem ocorrer num cenário concorrente. Executar uma sequência de operações atómicas pode causar violações de atomicidade se existir uma correlação entre essas operações, devendo o programador garantir que toda a sequência de operações é executada atomicamente. Este problema é especialmente comum quando se usam operações de pacotes ou módulos de terceiros, pois o programador pode identificar incorretamente o âmbito das regiões de código que precisam de ser atómicas para garantir o correto comportamento do programa. Para evitar este problema o programador do módulo pode criar um contrato que especifica quais as sequências de operações do módulo que devem ser sempre executadas de forma atómica. Este trabalho apresenta uma análise estática para verificação destes contratos.

Software developers are expected to protect concurrent accesses to shared regions of memory with some mutual exclusion primitive that ensures atomicity properties to a sequence of program statements. This approach prevents data races but may fail to provide all necessary correctness properties.The composition of correlated atomic operations without further synchronization may cause atomicity violations. Atomic violations may be avoided by grouping the correlated atomic regions in a single larger atomic scope. Concurrent programs are particularly prone to atomicity violations when they use services provided by third party packages or modules, since the programmer may fail to identify which services are correlated. In this paper we propose to use contracts for concurrency, where the developer of a module writes a set of contract terms that specify which methods are correlated and must be executed in the same atomic scope. These contracts are then used to verify the correctness of the main program with respect to the usage of the module(s). If a contract is well defined and complete, and the main program respects it, then the program is safe from atomicity violations with respect to that module. We also propose a static analysis based methodology to verify contracts for concurrency that we applied to some real-world software packages. The bug we found in Tomcat 6.0 was immediately acknowledged and corrected by its development team.

n/a

n/a

n/a

Parallel debugging is complex and difficult. Complex because the programmer has to deal with multiple program flows and process interactions, and difficult due to the very limited choice on effective and easy-to-use debugging tools for parallel programming. Simple and necessary features for parallel debugging are absent even from commercial debuggers, such as a record-replay feature, that allows to re-execute multiple times a parallel application assuring that during each re-execution the internal race conditions are solved in the same way they were in the first time. Some work has been done on record-replay techniques for parallel and distributed applications, but just a few have been applied to specific systems (such as PVM or MPI), and even less have produced working prototypes. In this paper we describe a method designed to work with the PVM system and how it was implemented to provide a working prototype.