\chapter{Introdução}
    \label{chap:intro}
    \epigraph{``E então a totalidade da aritmética se situava, repentinamente, dentro das possibilidades
    da mecânica''}{Charles Babbage - 1864}

    \sigla{EPOS}{Embedded Parallel Operating System}
    \sigla{HLS}{High-Level Synthesis}
    \sigla{BLP}{Bit-Level Paralelism}
    \sigla{FPGA}{Field-Programmable Gate Array}
    \sigla{EDA}{Electronic Design Automation}
    \sigla{VHSIC}{Very High-Speed Integrated Circuit}
    \sigla{VHDL}{VHSIC Hardware Description Language}

    Alan Turing, em 1936, criou uma sólida base para a Ciência da Computação como conhecemos
    nos dias atuais com seu modelo de uma máquina de computação \footnote{do inglês
    ``Computing machine''}, definida no célebre artigo \emph{``On computable numbers with an
    application to the Entscheidungsproblem''}\cite{computable-numbers}. Simultaneamente Alonzo
    Church dava uma definição bastante diferente do conceito de \emph{função computável}, através
    do Cálculo Lambda. A noção mais frequente e difundida que temos de algoritmo advém da máquina de
    Turing. Nesse contexto um algoritmo é uma \emph{sequência} de operações, de fato uma sequência
    de \emph{estados} da máquina de Turing, a qual ao chegar em seu estado final terá produzido a
    saída da função.
        
    Essa, porém, está longe de ser a única maneira de se descrever um algoritmo. É também
    controverso afirmar que ela é a \emph{melhor} ou \emph{mais intuitiva} maneira de realizar
    tal descrição. John Backus, o inventor da linguagem FORTRAN, já a criticava no seu discurso
    de aceitação do prêmio Turing, recebido em 1977\cite{backuslecture}. Um outro modelo de
    computação com o mesmo poder de expressão do que a máquina de Turing são os circuitos booleanos.
    Nesse modelo, um algoritmo é representado por um grafo onde os nodos são portas lógicas
    fundamentais (and, or e not) e as arestas representam as conexões entre tais portas.
    
    Apesar de já ser sabido há um bom tempo que todo e qualquer algoritmo pode ser implementado
    por um circuito, questões essencialmente tecnológicas impediram por muito tempo o uso de
    circuitos booleanos como um modelo para a implementação de algoritmos em larga escala.
    O problema fundamental no uso de circuitos booleanos era a falta de \emph{flexibilidade}.
    Até recentemente, uma vez que
    um circuito fosse fabricado, ele não poderia mais ser alterado ou reconfigurado para
    exercer tarefa diferente daquela para qual foi projetado. A forma de se obter uma máquina
    \emph{universal}, capaz de resolver qualquer problema computável, foi projetando-se um
    circuito capaz de interpretar instruções codificadas em binário e realizar diferentes
    operações de acordo com o tipo de instrução. Essa arquitetura, uma implementação física da
    máquina universal de Turing, é a tão conhecida arquitetura de von Neumann\cite{edvac}, e
    ainda hoje é a base para quase todos os processadores.
    
    Apesar de algumas desvantagens inerentes à arquitetura de von Neumann, a hegemonia por ela
    conquistada é simples de se explicar. Os avanços na tecnologia de fabricação de transistores
    vinham permitindo que o poder de computação dos processadores aumentasse
    sem grandes remodelagens arquiteturais. Durante muito tempo, a frequência dos processadores
    cresceu seguindo uma função exponencial.
    
    De fato, o cofundador da Intel\textregistered, Gordon E. Moore, previu essa
    ``tendência'' da indústria de microprocessadores com um célebre artigo\cite{moore}.
    Tal tendência foi verificada quase exatamente por décadas, porém vem perdendo validade
    gradativamente nos dias atuais. Embora a miniaturização dos transistores continue, 
    o \emph{aumento na frequência} dos processadores perde força devido à grande quantidade
    de potência dissipada em forma de calor\cite{powerwall}.

    Levando em conta essa perda de velocidade no aumento da frequência dos processadores,
    a comunidade profissional e acadêmica volta-se para modelos de programação paralela. Cresce
    também cada vez mais o interesse pela implementação de algoritmos diretamente em hardware, dado
    o seu paralelismo inerente e os recentes avanços na tecnologia de lógica programável.
    Um fator que dificulta a ampla implementação de algoritmos em hardware é a escassez de técnicas
    e ferramentas que permitam descrições dos algoritmos em alto nível de abstração, e a síntese automática
    de tais descrições. Investigar o estado da arte na área de síntese de alto nível, assim como
    realizar um estudo de caso implementando um algoritmo de uso prático, são as metas deste trabalho.
    
    \section{Justificativa}
        \label{sec:justificativa}
        Grande parte das desvantagens da arquitetura de von Neumann são causadas, de certa
        forma, pela ``uniformização'' na maneira com que os algoritmos são executados. Para que o
        processador não seja um circuito demasiadamente grande e complexo, há um número reduzido
        de instruções, um conjunto pequeno e fixo de unidades funcionais para realizar todo e
        qualquer programa possível. Essas restrições, apesar de manter a generalidade da máquina,
        fazem com que possíveis otimizações inerentes ao problema em questão não possam
        ser aplicadas.

        Um exemplo que ilustra muito bem uma desvantagem de tal ``uniformização'' é a grande
        dificuldade atual para aproveitar a capacidade de processamento dos \emph{multicores}.
        Após notar que a frequência dos processadores já não aumentaria num passo tão rápido,
        a indústria investiu na inclusão de vários processadores independentes num mesmo chip,
        na esperança de que os programadores reescrevessem seus algoritmos aproveitando a possível
        execução paralela de vários fluxos de instruções.

        Agora, porém, os incrementos na performance são mais difíceis de serem alcançados;
        há muito mais a ser feito do que esperar o aumento ``natural'' das frequências de clock.
        Avanços significativos têm sido feitos em vários níveis de abstração, desde as técnicas de
        BLP e ILP até o aparecimento de novas bibliotecas e linguagens de programação voltadas
        a modelar o paralelismo. Esses avanços têm dois grandes objetivos: tirar das mãos do programador
        a responsabilidade pela paralelização de seu programa, deixando esse trabalho para o compilador
        e hardware; e facilitar o trabalho do programador para \emph{expressar} o paralelismo presente
        nas aplicações.
        
        Em uma vertente paralela, uma boa parte dos fatores que impediam a implementação de algoritmos
        diretamente em circuitos lógicos vem se revertendo. A tecnologia de lógica programável deu um
        grande salto a partir de 1985 e durante toda a década de 90, com a introdução dos FPGAs.
        Tais dispositivos são flexíveis, e permitem a implementação de todo e qualquer circuito
        booleano. Alguns FPGA mais recentes permitem até mesmo reconfiguração dinâmica e parcial, ou
        seja, partes da malha lógica podem ser reconfiguradas enquanto o restante do dispositivo está
        ativo (executando um algoritmo).

        Além disso, a indústria de EDA vem trabalhando para aproximar o processo
        de projetar um circuito integrado do processo de desenvolver software. Esse esforço teve
        um início na década de 80, quando da criação das linguagens VHDL e Verilog; voltadas para a descrição
        de hardware com enfoque arquitetural, mas com construções típicas de linguagens de programação
        (por exemplo, laços e condicionais). O aparecimento das linguagens de descrição de hardware
        foi um passo inicial para encurtar a distância entre o mundo dos projetistas de hardware e o
        dos programadores.

        Caso programadores pudessem descrever algoritmos de uma maneira não muito distante da que
        o fazem no desenvolvimento de software -- ou seja, de maneira \emph{comportamental} -- e mesmo
        assim implementá-los em hardware, as vantagens seriam muitas. Talvez a maior vantagem de todas
        seria a exploração do paralelismo inerente à aplicação desenvolvida. Bons compiladores poderiam
        explorar esse paralelismo nos vários níveis (bit, instrução, dados, tarefa), aproveitando a
        flexibilidade da arquitetura subjacente. Algumas alternativas nesse sentido já existem atualmente,
        e são implementadas tanto como novas linguagens e novos compiladores ou como linguagens embutidas
        (na forma de bibliotecas e \emph{frameworks}). Alguns exemplos são, por exemplo, a linguagem
        Single-assignment C\cite{sac}, a biblioteca C++ Accelerator\cite{accelerator} e a ferramenta
        Catapult-C\cite{catapult}. Esses avanços são discutidos com mais detalhes no capítulo de
        trabalhos correlatos.

    \section{Objetivos}
        \label{sec:objetivos}
        Atualmente a indústria de EDA, conjuntamente com pesquisadores da área, vem buscando
        desenvolvimentos em HLS. Novas linguagens foram criadas com esse propósito, além de
        metodologias e ferramentas que visam obter um sistema completo, com todos os seus componentes
        de software e hardware, a partir de uma modelo algorítmico em alto nível de abstração.

        O objetivo deste trabalho se insere nesse cenário como um estudo de viabilidade. Será realizada a
        modelagem em hardware de um componente de sistema operacional comumente implementado em
        software, um \emph{escalonador}. O modelo será descrito em uma linguagem de alto nível,
        e implementado utilizando uma ferramenta que permite a síntese direta para hardware, com o mínimo
        possível de intervenção humana.

        Um escalonador foi escolhido como algoritmo a ser implementado em nosso estudo de caso por
        situar-se em uma área de aplicação (Sistemas Operacionais) suficientemente diferente das
        encontradas na bibliografia relacionada e por ter implementação em hardware suficientemente
        complexa. Um escalonador, dentre as várias famílias de abstrações em um Sistema Operacional, é
        a única que demonstra comportamento tanto \emph{assíncrono} como
        \emph{autônomo}\cite{marcondes-hybrid}, tornando um desafio a sua implementação em hardware.
        Certas implementações em hardware de um escalonador dão ao sistema em que se inserem a
        característica de possuir tempo de execução totalmente determinístico, o que pode ser crucial
        no suporte à execução de aplicações \emph{hard real-time}.

        Várias possibilidade de microarquitetura para o mesmo algoritmo serão exploradas, e o componente
        sintetizado em um FPGA será integrado aos componentes restantes do EPOS, 
        que executarão em um soft-processor no mesmo FPGA.
        
        A verificação de corretude do modelo se dará através de simulações funcionais com a elaboração
        de um \emph{testbench} auto-verificável, englobando casos de teste das situações de contorno
        para cada operação do modelo. Resultados da síntese de hardware -- tais como área ocupada e
        atraso máximo -- serão coletados e comparados com os mesmos dados obtidos de uma implementação
        RTL do mesmo componente.
