Sincronização de threads em hardware SIMD

Abstract

Performance is constrained by power consumption in modern computer architectures.One way to reduce power consumption, and hence increase performance, is to eliminate redundant operations between assembly instructions.This redundancy elimination, however, is difficult, because it involves solving a costly on-line problem: the shortest common supersequence.Previous work have proposed many different heuristics to solve this problem at either the architecture, or at the compiler level.The sheer number of different algorithms, and the vast search space makes a comparison between them a herculean task.In this dissertation, we dive into this task, providing the most extensive comparative analysis of these different heuristics ever seen in the literature.We match the different heuristics along several dimensions, including the amount of thread-level or data-level parallelism that they deliver.Our results show that relatively simple heuristics, such as the so called MinPcSp can outperform very convoluted algorithms.From this comparison we draw subsidies to design, test and implement new heuristics to share redundant work between parallel threads.Our new algorithms improve on the previous works in non-trivial ways.When testing these algorithms in industrial-strength benchmarks, we have observed that some of them are able to reduce the number of instructions to be processed by a factor of 3x.