Tecnhiques and architecture for trace detection and speculative execution

Orientador: Guido Costa Souza de AraújoTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: É sabido que o modelo de desenvolvimento de micro-processadores baseado na extração de Instruction-Level Parallelism (ILP) de código sequencial atingiu seu limite. Encontrar soluções escaláveis e eficientes que permitam a manutenção de inúmeras instruções em execução simultaneamente tem se mostrado um desafio maior que o imaginado. Neste sentido, arquitetos e micro-arquitetos de computadores vêm buscando soluções alternativas para o desenvolvimento de novas arquiteturas. Dentre as soluções existentes, vêm ganhando força as baseadas na extração de Thread-Level Parallelism (TLP). Resumidamente, TLP é um tipo de paralelismo que tenta quebrar um programa sequencial em tarefas relativamente independentes entre si para executá-las em paralelo. TLP pode ser extraído por hardware ou software. Idealmente, uma solução híbrida deve ser utilizada, com o software realizando a identificação das oportunidades de extração de TLP, e com o hardware provendo suporte para execução do código gerado. Com tal solução de compromisso, o hardware fica livre da necessidade de especular, e o software pode trabalhar com maiores garantias. Nesta Tese, estudaram-se formas automáticas de paralelização e extração de TLP. Inicialmente, focou-se em traces dinâmicos de execução de programas sequenciais. Técnicas existentes (tais como MRET e Trace Trees) mostraram-se inapropriadas, de modo que desenvolveu-se uma nova técnica chamada Compact Trace Tree (CTT), que mostrou-se mais rápida que Trace Trees. Trace Tree (TT) também apresentam grande nível de especialização de código (tail duplication), característica ausente em MRET. Além de CTT, esta Tese apresenta Trace Execution Automata (TEA), um autômato que representa traces de execução. Esta representação revelou, em nossos experimentos, quase 80% de economia de espaço quando comparada com a representação usual. A seguir, o foco da Tese foi voltado para laços de execução e para paralelização estática de código sequencial através de Decoupled Software Pipeline (DSWP). Nosso primeiro resultado nesta direção, usando Java, mostrou claramente que sem nenhum suporte em hardware, a paralelização estática de programas poderia atingir um ganho de desempenho médio de 48% nas aplicações paralelizadas. Finalmente, a Tese propõe um modelo de execução paralelo baseado em DSWP que permite a consistência de dados entre as diversas threads de programas paralelizados. Apesar de não avaliar esta arquitetura completamente, os resultados iniciais são promissores. Além disso, o suporte necessário em hardware é simples e acomoda-se sobre o protocolo de coerência de cache existente, sem alterações sensíveis no processadorAbstract: The usual, Insturction-Level Parallelism (ILP)-oriented, microprocessor development model is known to have reached a hard-to-break limit. Finding scalable and efficient solutions that keep several instructions on-the-fly simultaneously has proven to be moredifficult than imagined. In this sense, computer architects and micro-architects have been seeking alternatives to develop new architectures. Among all, the TLP-based solutions are gaining strength. In short, TLP strives to break a sequential program into quasi-independent tasks in order to execute them in parallel. TLP can be extracted either by hardware or software. Ideally, a hybrid solution would be employed, with the software being responsible to identifying TLP opportunities, and the hardware offering support for the parallel code execution. With such solution, the hardware is free from the heavy speculation burden, whilst the software can be parallelized with more warranties. In this Thesis, automatic parallelization and TLP strategies were studied. The research first focused on dynamic execution traces. Existing techniques, such as MRET and Trace Trees proved unsuitable for our goals, which led us to develop a new trace identification technique called Compact Trace Trees, which showed to be faster than Trace Trees. Compact Trace Trees also present trace specialization, which MRET lacks. Besides Compact Trace Trees, this Thesis presents a new trace representation called Trace Execution Automata, an automaton representing the execution traces. This technique revealed nearly 80% memory size savings when compared to the usual, code duplication representation. Next, the Thesis' focus shifted to parallelizing loops statically. Our initial result in this direction, using Java and without any hardware support, clearly revealed that static parallelization of sequential programs could reach a 48% average speedup when compared to their sequential execution. Finally, a new, Decoupled Software Pipelining-based execution model with automatic data coherence amongst parallelized programs'threads is proposed by the Thesis. Despite the lack of a full model evaluation, the initial results are promising. Differently from other proposals, the hardware support necessary for this architecture is simple and builds upon the existing cache coherence protocol, without any modifications to this sensitive system componentDoutoradoDoutor em Ciência da Computaçã