Software method level speculation for Java

Speculative multithreading (SpMT), also known as thread level speculation (TLS), is a dynamic parallelization technique that relies on out-of-order execution, dependence buffering, and misspeculation rollback to achieve speedup of sequential programs on multiprocessors. A large number of hardware studies have shown good results for irregular programs, as have a smaller number of software studies in the context of loop level speculation for unmanaged languages.In this thesis we explore software method level speculation for Java. A software environment means that speculation will run on existing multiprocessors, at the cost of extra overhead. Method level speculation (MLS) is a kind of SpMT / TLS that creates threads on method invocation, executing the continuation speculatively. Although MLS can subsume loop level speculation, it is still a relatively unexplored paradigm. The Java programming language and virtual machine environment are rich and complex, posing many implementation challenges, but also supporting a compelling variety of object-oriented programs.We first describe the design and implementation of a prototype system in a Java bytecode interpreter. This includes support for various MLS components, such as return value prediction and dependence buffering, as well as various interactions with features of the Java virtual machine, for example bytecode interpretation, exception handling, and the Java memory model. Experimentally we found that although high thread overheads preclude speedup, we could extract significant parallelism if overheads were excluded. Furthermore, profiling revealed three key areas for optimization.The first key area for optimization was the return value prediction system. In our initial model, a variety of predictors were all executing naïvely on every method invocation, in order that a hybrid predictor might select the best performing ones. We developed an adaptive system wherein hybrid predictors dynamically specialize on a per-callsite basis, thus dramatically reducing speed and memory costs whilst maintaining high accuracy.The second area for optimization was the nesting model. Our initial system only allowed for out-of-order nesting, wherein a single parent thread creates multiple child threads. Enabling support for in-order nesting exposes significantly more parallelization opportunities, because now speculative child threads can create their own children that are even more speculative. This required developing a memory manager for child threads based on recycling aggregate data structures. We present an operational semantics for our nesting model derived from our implementation.Finally, we use this semantics to address the third area for optimization, namely a need for better fork heuristics. Initial heuristics based on online profiling made it difficult to identify the best places to create threads due to complex feedback interactions between speculation decisions at independent speculation points. This problem grew exponentially worse with the support for in-order nesting. Instead, we chose to clarify the effect of program structure on runtime parallelism. We did this by systematically exploring the interaction between speculation and a variety of coding idioms. The patterns we identify are intended to guide both manual parallelization and static compilation efforts.L'exécution spéculative multifils (SpMT), aussi connue sous le nom de spéculation au niveau des fils d'exécution (TLS), est une technique de parallélisation dynamique qui se base sur l'exécution dans le désordre, la mise en mémoire tampon des dépendances spéculatives, et le refoulement des erreurs de spéculation pour atteindre l'accélération des programmes séquentiels sur les multiprocesseurs. D'extensives études architecturales ont révélé de bons résultats dans le cas des programmes irréguliers, tout comme plusieurs études logiciel dans la spéculation au niveau des boucles dans un langage non géré. Dans ce mémoire, nous explorons la spéculation logiciel au niveau des méthodes pour Java. Un environnement logiciel signifie que la spéculation s'exécute sur les multiprocesseurs existants, au coût de charge additionnelle. La spéculation au niveau des méthodes (MLS) est une sorte de SpMT / TLS où des fils d'exécution sont créés à chaque invocation de méthode, exécutant les instructions qui suivent de manière spéculative. Malgré la possibilité de subsomption de la spéculation au niveau des boucles par la spéculation au niveau des méthodes, ce paradigme est relativement peu exploré. Le langage de programmation Java, ainsi que l'environnement de sa machine virtuelle, sont riches et complexes, ce qui pose plusieurs difficultés à l'implémentation, mais qui a l'avantage de supporter une grande variété de programmes orientés objet. Nous décrivons d'abord la conception et l'implémentation d'un système prototype dans un interpréteur de code-octet Java. Cette implémentation supporte une variété de composantes de la spéculation au niveau des méthodes, telles la prédiction des valeurs de retour, la mise en mémoire tampon des dépendances spéculatives, ainsi qu'une variété d'interactions avec des caractéristiques de la machine virtuelle Java (JVM), par exemple, l'interprétation du code-octet, le gestion des exceptions et le modèle de la mémoire de Java. Des expériences nous ont permis de constater d'encourageants résultats quant à la parallélisation des programmes, malgré une charge additionnelle importante dû à l'embranchement des fils d'exécution, ce qui empêche d'obtenir une accélération significative. De plus, le profilage effectué a révélé trois secteurs d'optimisation importants. La première optimisation étudié est la prédiction des valeurs de retour. Notre modèle initial utilisait plusieurs outils de prédiction différents pour chaque invocation de méthode, afin qu'un outil de prédiction hybride puisse choisir les plus performants. Nous avons développé un système adaptatif où les outils de prédiction hybrides se spécialisent dynamiquement pour chaque site d'invocation, réduisant drastiquement la charge mémoire additionnelle et les ralentissements tout en préservant un haut degré de précision. Le deuxième secteur d'optimisation étudié est celui des modèles d'emboîtement. Notre modèle initial permettait seulement l'emboîtement dans le désordre, où un seul fil d'exécution peut en créer plusieurs fils d'exécution spéculatifs. L'introduction du support de l'emboîtement en ordre expose un nombre conséquent d'opportunités de parallélisation, parce qu'un fil d'exécution spéculatif peut maintenant en créer un autre, encore plus spéculatif. Pour ce faire, nous avons développé un gestionnaire de mémoire pour les fils d'exécution spéculatifs basé sur le recyclage des structures de donnée agrégés. Nous présentons une sémantique des opérations de notre modèle d'emboîtement dérivée de notre implémentation. Finalement, nous utilisons cette sémantique des opérations pour optimiser nos heuristiques d'embranchement. Nous avons choisi de clarifier l'effet de la structure des programmes sur son parallélisme. Pour ce faire, nous avons exploré systématiquement l'interaction de la spéculation avec une variété d'idiomes de programmation. Les patrons identifiés sont utiles pour guider les efforts de parallélisation manuelle ainsi que de compilation statique