Improving the structural testing of concurrent programs: a deterministic and parallel approach

• Grant number: 12/14285-4
• Support Opportunities: Scholarships in Brazil - Master
• Start date: November 01, 2012
• End date: May 31, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Paulo Sérgio Lopes de Souza
• Grantee: Raphael Negrisoli Batista
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

The testing of concurrent programs is an expensive task, mainly because it needs to test a high number of synchronization sequences, in order to validate such programs. One of the most used techniques to test communication and synchronization of concurrent programs is the automatic generation of different synchronizations pairs (or generation of race variants). Race variants are generated from the trace files of a non-deterministic execution, and the deterministic executions force the coverage of different synchronizations. This work approaches this problem in a more general way. It reduces the response time of the structural testing of concurrent programs when different variants are required. There are three main contributions in this work: the generation of trace files and the total or partial deterministic execution, the automatic generation of race variants and the parallelization of execution of race variants. The proposed algorithms take into account concurrent programs that interact simultaneously with message passing and shared memory, including six primitives with distinct semantics: blocking and non-blocking point-to-point, all-to-all/one-to-all/all-to-one collectives and shared memory. The Java algorithms implemented are in the application level, they are language independent and do not need system privileges to execute. Results obtained during the validation and evaluation phase are also presented and they show that the proposed objectives are reached with success. From the tester viewpoint, the response time of structural testing of concurrent programs was reduced, while the coverage of the concurrent programs with both paradigms increased with automatic and transparent procedures. The experiments showed speedups close to linear, when comparing the sequential and parallel versions.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

SOUZA, PAULO S. L.; SOUZA, SIMONE S.; ROCHA, MURILO G.; PRADO, RAFAEL R.; BATISTA, RAPHAEL N.; ALEXANDROV, V; LEES, M; KRZHIZHANOVSKAYA, V; DONGARRA, J; SLOOT, PMA. Data flow testing in concurrent programs with message passing and shared memory paradigms. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 18, p. 10-pg., 2013-01-01. (11/19051-9, 12/01901-9, 12/14285-4)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BATISTA, Raphael Negrisoli. Improving the structural testing of concurrent programs: a deterministic and parallel approach. 2015. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.