Publication

Static Branch Frequency and Program Profile Analysis

James Richard Larus
1994
Article de conférence
Résumé

Program profiles identify frequently executed portions of a program, which are the places at which optimizations offer programmers and compilers the greatest benefit. Compilers, however, infrequently exploit program profiles, because, profiling a program requires a programmer to instrument and run the program. An attractive alternative is for the complier to statically estimate program profiles. This paper presents several new techniques for static branch prediction and profiling. The first technique combines multiple predictions of a branch's outcome into a prediction of the probability that the branch is taken. Another technique uses these predictions to estimate the relative execution frequency (i.e., profile) of basic blocks and control-flow edges within a procedure. A third algorithm uses local frequency estimates to predict the global frequency of calls, procedure invocations, and basic block and control-flow edge executions. Experiments on the SPEC92 integer benchmarks and Unix applications show that the frequently executed blocks, edges, and functions identified by our techniques closely match those in a dynamic profile.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (35)
Prédiction de branchement
La prédiction de branchement est une fonctionnalité d'un processeur qui lui permet de prédire le résultat d'un branchement. Cette technique permet à un processeur de rendre l'utilisation de son pipeline plus efficace. Avec cette technique, le processeur va faire de l’exécution spéculative : il va parier sur le résultat d'un branchement, et va poursuivre l’exécution du programme avec le résultat du pari. Si le pari échoue, les instructions chargées par erreur dans le pipeline sont annulées.
Bloc de base
En informatique, un bloc de base est une portion du code source d'un programme caractérisé par certaines propriétés utiles qui le rendent facile à analyser. Les compilateurs décomposent la plupart du temps les programmes en leurs blocs de base dans une première étape du processus d'analyse. Les blocs de base forment les nœuds d'un graphe de flot de contrôle.
Graphe de flot de contrôle
En informatique, un graphe de flot de contrôle (abrégé en GFC, control flow graph ou CFG en anglais) est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution. Dans un GFC, les sommets du graphe représentent un bloc de base, c'est-à-dire un bout de code d'un seul tenant sans sauts ni cibles de sauts. Les cibles de sauts marquent le début d'un bloc de base, tandis que les sauts en marquent la fin. Les arcs représentent les sauts dans le flot de contrôle.
Afficher plus
Publications associées (32)

DASS: Combining Dynamic & Static Scheduling in High-Level Synthesis

Paolo Ienne, Lana Josipovic

A central task in high-level synthesis is scheduling: the allocation of operations to clock cycles. The classic approach to scheduling is static, in which each operation is mapped to a clock cycle at compile-time, but recent years have seen the emergence o ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs

Marco Mattavelli, Simone Casale Brunet, Endri Bezati, Anatoly Prihozhy

Large dataflow designs are a result of behavioral specification of modern complex digital systems and/or a result of unfolding and transforming looped and branched programs. Since deep-submicron silicon technology provides large amounts of available resour ...
SPRINGER2020

Efficient Dynamic Optimisation Heuristics for Dataflow Pipelines

Marco Mattavelli, Simone Casale Brunet, Endri Bezati

Large dataflow designs appear as a result of functional specification of modern complex digital systems and/ or a result of unfolding and behavioral transformation of looped and branched programs. Since deep-submicron silicon technology provides large amou ...
IEEE2018
Afficher plus