SYRANT: SYmmetric Resource Allocation on Not-taken and Taken Paths

Nathanaël Prémillieu (1) , André Seznec (1)

1 ALF - Amdahl's Law is Forever

In the multicore era, achieving ultimate single process performance is still an issue e.g. for single process workload or for sequential sections in par- allel applications. Unfortunately, despite tremendous research effort on branch prediction, substantial performance potential is still wasted due to branch mis- predictions. On a branch misprediction resolution, instruction treatment on the wrong path is essentially thrown away. However, in most cases after a conditional branch, the taken and the not-taken paths of execution merge after a few instruc- tions. Instructions that follow the reconvergence point are executed whatever the branch outcome is. We present SYRANT (SYmmetric Resource Allocation on Not-taken and Taken paths), a new technique for exploiting control independence. SYRANT essentially uses the same pipeline structure as a conventional processor. SYRANT tries to enforce the allocation of the exact same resources on the out-of-order execution mechanism (physical register, load/store queue and reorder buffer) for both the taken and not-taken paths. Thus, on a branch misprediction, the result of an in- struction already executed on the wrong path after the reconvergence point can be conserved in the same structure when it is data independent. Adding SYRANT on top of an aggressive superscalar execution core allows to improve performance for applications suffering a significant branch misprediction rate. As a side but important extra contribution, we introduce ABL/SBL a simple and non-intrusive hardware reconvergence detection mechanism. ABL/SBL can be used in a conventional superscalar processor to improve branch prediction ac- curacy through exploiting the execution of branches along the wrong path.

De plus en plus d'avancées dans le domaine de l'architecture des processeurs sont basées sur l'exécution spéculative des instructions. Dans le cas particulier de la spéculation liée aux branchements, le chemin d'exécution pour le branchement pris et le branchement non pris reconverge souvent après quelques instructions. Ce phénomène est appelé reconvergence du flot de contrôle. Il en résulte que ces instructions sont exécutées quelque soit la direction du branchement. On parle alors d'indépendance de contrôle. Plusieurs techniques ont été précédement pro- posées pour l'exploiter. Elles sont étudiées dans ce rapport. Une nouvelle technique exploitant l'indépendance de contrôle est présentée dans ce rapport. Nommée SYRANT (SYmmetric Resource Allocation on Not- taken and Taken paths), elle consiste à forcer l'allocation des mêmes ressources sur le chemin pris et non pris. Ainsi, lors d'une mauvaise prédiction, le travail déjà effectué sur le mauvais chemin et situé après le point de reconvergence peut être conservé.

Mots clés: Architecture; sequential; multicore; manycore; control independence; control flow reconvergence; SYRANT

Domaines: Architectures Matérielles [cs.AR]

Nathanaël Prémillieu, André Seznec. SYRANT: SYmmetric Resource Allocation on Not-taken and Taken Paths. ACM Transactions on Architecture and Code Optimization, 2012, 8 (4), pp.Article No.: 43. ⟨10.1145/2086696.2086722⟩. ⟨inria-00539647⟩