Etude de l'interaction bas niveau entre le parallélisme d'instructions et les caches
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
The scheduling problems (of instructions or tasks) that are studied in the litterature consider a well knowledge of execution time of each instruction. However, adding a cache to a processor does not permit in advance to know the access delay to the memory hierarchy. The uncertainty of the data localisation in memory hierarchy induces uncertainty of the memory instruction delays. Thus, the studied theorical scheduling models are simple, and they only consider fixed latency for memory instructions. In fact, the cache effects on instruction scheduling vary the program execution time inducing the impossibility to perform a temporal analysis of the generated code and then a resource under-utilisation. We propose an optimisation that takes into account the cache effects during the compilation time. Then, we combine the linear prefetch optimisation with it. Moreover, we note that the addition of the data prefetch instructions permits to overlap the memory access latency. However, litterature describes only linear access prefetch and does not offer alternative for the non-linear accesses. In this context, we propose an analysis method of the accessed address stream based on the spectral analysis. It permits to detect the repetitive patterns if they exist. Based on these repetitive patterns, data becomes prediction possible. This may leads to prefetch repetitive irregular patterns. Finally, the granularity of data accesses is often neglected when the prefetch optimisation is applied. However, this parameter can be used to propose an adapted optimisation. Indeed, in opposition to the classical fine level granularity of data prefetching, we propose to prefetch at large grain granularity. In other word, instead of prefetching cache-lines, we propose to prefetch a whole memory block. We perform experiments on the sparse matrix vector multiplication. In addition, we developed a test of data regularity to classify the matrices.
Abstract FR:
Les problèmes d’ordonnancement (d’instructions ou de tâches) étudiées dans la littérature considèrent majoritairement une connaissance parfaite du temps d’exécution de chaque instruction. Or, la présence d’un cache ne permet pas la connaissance à priori des délais d’accès à la hiérarchie mémoire. L’incertitude de la localisation des données dans la hiérarchie mémoire conduit à l’incertitude des délais consommés par les instructions d’accès mémoire. Ainsi, les modèles théoriques d’ordonnancement étudiés sont bien simplifiés, ne considèrent que des latences fixes pour les différentes instructions. Or en réalité les effets de caches sur les ordonnancements d’instructions font varier les temps d’exécution des programmes induisant l’impossible de faire une analyse temporelle du code et une sous-utilisation des ressources. Nous proposons une optimisation qui prend en compte les effets de cache lors de la compilation et nous y associons les optimisations de pré-chargement de données de manière linéaire. De plus, nous constatons que l’ajout d’instruction de pré-chargement de données dans le code bas niveau permet de couvrir les latences d’accès à la mémoire. Cependant, la littérature ne décrit que les méthodes d’accès linéaire et ne propose que peu de solutions pour les accès non linéaires. Dans ce contexte, nous proposons une méthode d’analyse de flux d’adresses accédées durant l’exécution. Cette méthode est basée sur l’analyse spectrale. Celle-ci permet de détecter les patterns répétitifs et donc de prédire les prochaines adresses accédées. En dernier, la granularité d’accès aux données est un point souvent négligé lors de l’insertion d’instruction de pré-chargement dans le code bas niveau. Or, il nous semble nécessaire de prendre en compte ce paramètre afin de proposer des solutions plus appropriées. Pour cela nous nous somme basées sur une granularité gros grain pour prefetcher des bloques de données. Nous avons montré l’efficacité de la méthode sur la multiplication matricielle creuse. Plus de 1400 matrices furent utilisées et nous avons développé un test de régularité de données afin de classifier ces matrices.