Identifying Tuple Usage Patterns in an Optimizing Linda Compiler

The associative tuplespace access and uncoupled communication of Linda parallel programs are the key to the power and flexibility of Linda, but also lie at the heart of the compiler and run-time system implementation challenges. This paper provides concrete steps towards advanced compile-time analysis and optimization of the uncoupled communication of Linda programs. In particular, as part of an optimizing Linda compiler, we have developed and implemented a data flow framework which statically estimates the count of tuples at run-time for each of the tuplespace partitions. This information is crucial in identifying tuple usage patterns which form the basis for compile-time optimization of Linda's uncoupled communication. We have also designed algorithms for the identification of shared variable tuples and a class of synchronization tuples. Our empirical findings show that over 28% of tuplespace partitions in a suite of real application programs never contain more than one tuple. These ..