Task interaction graphs for concurrency analysis

Abstract

A representation for concurrent programs, called task inter- action graphs, is presented. Task interaction graphs divide a program into maximal sequential regions connected by edges representing task interactions. This representation is illustrated and it is shown how it can be used to create concurrency graph representations that are much smaller than those created from control flow graph representations. Both task interaction graphs and their corresponding concurrency graphs facilitate analysis of concurrent programs. Some analyses and optimizations on these representations are also described.