Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$4,681.00

Testing and debugging concurrent software by deterministic execution

EF 2009-10

Résumé
Testing any software is difficult because of the large number of paths through the code. To test different paths, the program must be run with a variety of inputs. Concurrent software makes this already-difficult problem harder by adding non-determinism. In concurrent software, a program is decomposed into units called threads, which run independently but share data in memory. Each thread reads and writes shared data, but the order of these operations changes with each run of the program depending on the timing of thread execution. This non- deterministic order can occur even if the program is run with the same input, and can impact the final results. Not long ago, concurrent software was rare. It has become more mainstream recently and will only increase in importance in the future. Hyperthreaded and multicore CPUs create environments in which concurrent programs can achieve performance benefits by using different parts of a CPU simultaneously. Getting full performance from these new environments will require programmers to write concurrent code. My approach to the problem of testing concurrent software is to execute a concurrent program deterministically - that is, run the program where the order of events is determined in advance. My approach, which forms the basis of this research proposal, uses advanced compiler analysis techniques to identify places in a concurrent program where thread timing can impact values for read events. This analysis is then used to control program execution by supplying values to read events that simulate the desired event order. Testing and debugging are crucial parts of the software development process. Quite simply, software errors cost real money. As concurrent code becomes increasingly important, it is essential that testing and debugging tools keep pace. Otherwise, software with new classes of errors that are difficult to detect and correct will reach consumers. For example, after Intel announced hyperthreading, several commercial programs emerged to exploit the potential benefits, including Adobe Photoshop and Symantec Anti-Virus. My goal is to improve software quality by helping developers produce correct applications in the important concurrent domain.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
261413-2007
Name nom
MacDonald, Steven
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
4681
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
330
Committee name en
Computing and Information Sciences - A
Committee name fr
Informatique - A
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
3
Nb partie
3
Application title
Testing and debugging concurrent software by deterministic execution
Keyword
NA
Application summary
Testing any software is difficult because of the large number of paths through the code. To test different paths, the program must be run with a variety of inputs. Concurrent software makes this already-difficult problem harder by adding non-determinism. In concurrent software, a program is decomposed into units called threads, which run independently but share data in memory. Each thread reads and writes shared data, but the order of these operations changes with each run of the program depending on the timing of thread execution. This non- deterministic order can occur even if the program is run with the same input, and can impact the final results. Not long ago, concurrent software was rare. It has become more mainstream recently and will only increase in importance in the future. Hyperthreaded and multicore CPUs create environments in which concurrent programs can achieve performance benefits by using different parts of a CPU simultaneously. Getting full performance from these new environments will require programmers to write concurrent code. My approach to the problem of testing concurrent software is to execute a concurrent program deterministically - that is, run the program where the order of events is determined in advance. My approach, which forms the basis of this research proposal, uses advanced compiler analysis techniques to identify places in a concurrent program where thread timing can impact values for read events. This analysis is then used to control program execution by supplying values to read events that simulate the desired event order. Testing and debugging are crucial parts of the software development process. Quite simply, software errors cost real money. As concurrent code becomes increasingly important, it is essential that testing and debugging tools keep pace. Otherwise, software with new classes of errors that are difficult to detect and correct will reach consumers. For example, after Intel announced hyperthreading, several commercial programs emerged to exploit the potential benefits, including Adobe Photoshop and Symantec Anti-Virus. My goal is to improve software quality by helping developers produce correct applications in the important concurrent domain.