\chapter{Fundamentos}
    \label{chap:conceitos}

    \sigla{ASIC}{Application-Specific Integrated Circuit}
    \sigla{GPP}{General Purpose Processor}
    \sigla{RDPA}{Reconfigurable Data-Path Array}
    \sigla{ULA}{Unidade Lógico-Aritmética}
    \sigla{HDL}{Hardware Description Language}
    \sigla{ESL}{Electronic System Level}
    \sigla{HLS}{High-Level Synthesis}
    \sigla{DFG}{Data Flow Graph}
    \sigla{SoC}{System-on-Chip}

    Neste capítulo são detalhados os conceitos teóricos e tecnologias mais importantes nas quais
    este trabalho se baseia. 
    
    \section{Computação Reconfigurável}
        \label{sec:rc}
        Até recentemente, havia majoritariamente duas maneiras de se implementar um
        algoritmo\cite{rc-survey}: A primeira consiste em projetar um circuito lógico digital que
        realiza a computação necessária; tipicamente um ASIC
        ou então (mais raro) a integração de componentes eletrônicos discretos em uma placa.
        Essa abordagem é extremamente inflexível, pois após a fabricação de um circuito para
        um algoritmo específico ele não poderá ser alterado, e executará o mesmo algoritmo por toda
        sua vida útil.
        
        A segunda forma de se implementar um algoritmo é executá-lo em um processador. Um processador
        é capaz -- essencialmente -- de interpretar uma sequência de instruções (dentre um conjunto
        pré-definido). Escolhendo-se adequadamente tal conjunto de instruções pode-se fazer com que
        um processador seja universal, ou seja, capaz de resolver todo e qualquer problema decidível.

        Dado esse contexto, pode-se dizer que a \emph{Computação Reconfigurável} é uma forma
        alternativa de se realizar algoritmos, um \emph{paradigma de implementação}. A figura
        \ref{fig:escalaflex} situa a computação reconfigurável com relação aos ASIC e aos
        GPP. Considerando-se uma escala de flexibilidade pode-se dizer que os ASIC ocupam
        o extremo inferior, enquanto os GPP ocupam o extremo superior. A região intermediária em
        tal escala é ocupada por dispositivos de computação reconfigurável, sendo que a posição exata
        de um dispositivo dentro dessa região depende de parâmetros discutidos mais adiante.
        \begin{figure}[h]
            \begin{center}
                \includegraphics[width=0.70\textwidth]{imagens/performance-flexibilidade.pdf}
            \end{center}
            \caption[Flexibilidade vs. performance de processadores]
            {Escala de flexibilidade/performance comparando GPP,
            ASIC e Computação Reconfigurável}
            \label{fig:escalaflex}
        \end{figure}
        
        O paradigma de computação reconfigurável consiste, praticamente, na implementação de
        algoritmos em dispositivos de hardware reconfigurável. Tais dispositivos podem ter suas
        funções lógicas digitais, assim como malhas internas de comunicação, redefinidas
        após a fabricação. Alguns dispositivos permitem a reconfiguração até mesmo \emph{durante}
        a execução de um algoritmo.
        
        A utilização de dispositivos reconfiguráveis para acelerar a execução de algoritmos encontra-se
        em crescimento, e pode ser observada em diversas áreas de aplicação com marcantes
        características de paralelismo. Alguns exemplos citados na frequentemente na
        literatura\cite{rc-survey} são:
        \begin{itemize}
            \item Criptografia e quebra de cifras
            \item Reconhecimento de padrões
            \item Algoritmos genéticos
            \item Computação científica
            \item Processamento Digital de Sinais (a área com maior utilização)
        \end{itemize}
        
        
        \subsection{Famílias de dispositivos reconfiguráveis}
            \label{sec:familias-reconfiguraveis}
            Existem muitas arquiteturas de dispositivos reconfiguráveis atualmente implementadas, e
            uma medida crítica para classificar essas arquiteturas é a \emph{granularidade} de
            configuração. Pode-se dividir os dispositivos, de acordo com essa granularidade, em
            dois grandes grupos:
            
            \begin{description}
                \item[FPGA] Em um FPGA, a customização dos blocos funcionais e das interconexões
                entre blocos pode ser feita a nível de bit. Cada bloco funcional de um FPGA tipicamente
                implementa uma expressão lógica definida de forma tabular (uma memória armazena a tabela-verdade
                da função). Além disso, cada fio de interconexão entre blocos é um caminho que pode ser aberto
                ou fechado na programação. A figura \ref{fig:fpga} mostra a arquitetura de um FPGA.
                \begin{figure}[h]
                    \begin{center}
                        \subfloat[Estrutura global de um FPGA] {
                            \label{fig:fpga_fabric}
                            \includegraphics[width=0.45\textwidth]{imagens/fpga_fabric.pdf}
                        }
                        \subfloat[Uma interconexão programável] {
                            \label{fig:fpga_switch}
                            \includegraphics[width=0.45\textwidth]{imagens/fpga_switch.pdf}
                        }
                    \end{center}
                    \caption{Arquitetura de um FPGA}
                    \label{fig:fpga}
                \end{figure}
                
                \item[RDPA]
                Já em um RDPA, a unidade básica de reconfiguração é normalmente uma ULA, sendo
                que alguns dispositivos também trazem unidades funcionais específicas para operações
                comuns em processamento de sinais. Os caminhos de conexão entre as unidades funcionais
                são barramentos ao invés de simples fios, e portanto o \emph{quantum} de informação que
                circula entre os blocos de um RDPA é em geral uma palavra, e não um bit.
            \end{description}
        
        
    \section{Linguagens de descrição de hardware}
        \label{sec:hdls}
        Linguagens de descrição de hardware (HDL) são linguagens que visam modelar o
        \emph{comportamento} e a \emph{estrutura} de um circuito digital que implementa um algoritmo,
        e sua utilização iniciou-se em meados da década de 80 com a criação da linguagem Verilog.
        As HDL têm bastante em comum com linguagens convencionais de programação de software; sua
        sintaxe de comandos de controle de fluxo de execução, expressões lógico-aritméticas, etc.
        são bastante semelhantes. Porém, ao contrário de linguagens de programação de software, as
        HDL possuem construções específicas para a modelagem de aspectos temporais.
        
        Quando de sua criação, as HDL foram utilizadas principalmente para a modelagem e
        simulação de circuitos; somente com o desenvolvimento tecnológico tornou-se então
        possível realizar a síntese de ASIC a partir de código-fonte escrito em uma HDL.
        Um grande passo para o aumento massivo na utilização das HDL veio com surgimento dos
        FPGA a partir do início da década de 90. As cadeias de ferramentas dos fabricantes de
        FPGA aceitam código-fonte VHDL e/ou Verilog como a entrada ``natural'' para o processo
        de síntese.
        
        As linguagens de descrição de hardware são bastante versáteis, e permitem modelar um
        sistema digital em vários níveis de abstração. Em geral, porém, as ferramentas de síntese
        dos fabricantes de FPGA suportam subconjuntos de VHDL e Verilog. O padrão IEEE1076.6
        \cite{vhdl_synth} descreve o subconjunto sintetizável da linguagem VHDL, enquanto o
        padrão IEEE1364.1\cite{verilog_synth} é o correspondente para a linguagem Verilog.
        
        Em geral, quando se realiza a descrição \emph{sintetizável} de um circuito em VHDL
        ou Verilog, tal descrição é feita a nível de transferência de registradores. O
        projetista modela seu circuito como um conjunto de registradores e unidades funcionais
        (funções lógico/aritméticas). As etapas de computação ocorrem quando da
        transferência de um dado entre registradores, passando através de uma
        unidade funcional. Esse tipo de descrição está longe da forma como algoritmos são
        normalmente descritos, e exige um conhecimento que a maioria dos programadores não tem.

        A figura \ref{fig:soma-c-vhdl} demonstra essas diferenças entre uma linguagem
        de descrição de hardware e uma linguagem de programação. Um função \emph{soma} foi escrita
        em VHDL e em C. 
        \begin{figure}[h!]
            \begin{center}
                \subfloat[Função soma em C] {
                    \lstinputlisting[language=C]{code-figures/adder.c}
                    \label{fig:soma-c}
                }
                \hspace{35pt}
                \subfloat[Função soma em VHDL] {
                    \lstinputlisting[language=VHDL]{code-figures/adder.vhd}
                    \label{fig:soma-vhdl}
                }
            \end{center}
            \caption[Código C e VHDL de uma soma]
            {Comparação entre o código C e VHDL de uma função soma}
            \label{fig:soma-c-vhdl}
        \end{figure}

        A descrição em C é consideravelmente mais concisa que em VHDL, e isso é explicado
        pela necessidade que há de se descrever, no modelo VHDL, detalhes relativos à
        implementação da função em hardware. Por exemplo, no código C o tipo dos parâmetros
        para a função \emph{add} é \emph{int}, um tipo cujo tamanho é definido pela
        arquitetura subjacente. Já em VHDL o projetista precisa realizar uma análise das
        situações onde o circuito será usado e definir explicitamente tamanhos para os tipos.

        Outro ponto a se considerar é o tratamento da situação de \emph{carry}
        \footnote{A soma binária de dois operandos de tamanho n pode resultar em um valor de tamanho
        n+1. Quando essa situação ocorre, diz-se que o somador produziu um bit de \emph{carry}}.
        Em nenhum ponto da descrição em C aparece qualquer referência a esse tratamento, já que
        ele também é realizado pelo processador de maneira transparente ao programador. Em VHDL,
        por outro lado, o número de bits presentes no resultado da soma foi definido
        explicitamente (para não perder o caso de \emph{carry}), e o bloco possui de fato
        2 sinais de saída, um deles sendo o indicador de carry.

    \section{Síntese de alto nível}
        \label{sec:hls}
        O processo de síntese de \emph{alto nível} (HLS) consiste na geração de blocos de hardware
        a partir de uma descrição \emph{comportamental} de um algoritmo\cite{hls-other-book}
        \footnote{O processo de síntese de alto nível também é conhecido pelos nomes de síntese
        algorítmica, síntese no nível ESL, dentre outros}. Esta descrição comportamental se opõe
        à descrição \emph{arquitetural} realizada quando se utiliza o subconjunto sintetizável das
        linguagens VHDL ou Verilog.

        A entrada para a síntese de alto nível normalmente é código-fonte escrito em uma linguagem de
        programação convencional. De fato, um dos princípios da síntese de alto nível é que o algoritmo deve
        ser primeiramente testado em software e só então rodar, com pouca ou nenhuma alteração, como um
        bloco de hardware. Certamente as linguagens mais populares utilizadas como entrada no processo
        de síntese de alto nível são C e C++, devido à sua ubiquidade no domínio de sistemas embarcados
        e à grande comunidade de desenvolvedores e engenheiros que as dominam.

        Comumente, o resultado final do processo é uma descrição arquitetural em nível RTL do algoritmo
        modelado, em código VHDL ou Verilog, apesar de algumas ferramentas poderem gerar também
        \emph{netlists}\footnote{uma netlist é uma representação do circuito como um grafo onde os vértices
        são portas lógicas básicas e as arestas são fios. Existem formatos padronizados de representação de
        netlists, como por exemplo o EDIF.}. Tal resultado pode então ser processado por ferramentas
        dos fabricantes de FPGAs. A figura \ref{fig:hls-flow} resume o \emph{fluxo de projeto} da síntese
        de alto nível.
        \begin{figure}[h]
            \begin{center}
                \includegraphics[width=0.45\textwidth]{imagens/hls-flow.pdf}
            \end{center}
            \caption{Fluxo de projeto da síntese de alto nível}
            \label{fig:hls-flow}
        \end{figure}


        \subsection{Etapas da síntese de alto nível}
            \label{subsec:hls-flow}
            Durante o processo de síntese de um algoritmo descrito em C ou C++ para RTL, vários
            parâmetros do sistema digital devem ser especificados, pois não podem ser inferidos
            automaticamente a partir da descrição na linguagem fonte. Esse ciclo: escolha dos parâmetros
            arquiteturais; síntese do sistema; verificação da adequação das características à
            especificação do projeto e escolha de novos parâmetros (caso seja necessário), é chamado
            de \emph{exploração do espaço de projeto}.

            De fato, a exploração do espaço de projeto na síntese de um sistema digital é um problema típico
            de otimização, bastante sujeito à automatização. As ferramentas de síntese de alto nível buscam
            facilitar esse processo através de uso de scripts para a definição de parâmetros, de maneira a
            tornar possível a interação com ferramentas que busquem a otimização automática desses parâmetros.

            Os parâmetros cuja definição é necessária em cada etapa da síntese, assim como a influência de
            cada parâmetro nas etapas posteriores, são os seguintes\cite{hls-bluebook}:
            \begin{description}
                \item[Análise do código-fonte] Nessa etapa são coletados os limites de loops, assim como
                    informações sobre o uso dos parâmetros de funções; também é construído um grafo de
                    dependências de dados (DFG). Loops ilimitados irão causar dificuldades
                    em posteriores otimizações, e parâmetros que são ao mesmo tempo de entrada e saída
                    exigirão lógica adicional na geração de RTL.
                \item[Definição da macroarquitetura] Frequência de clock, tecnologia subjacente e limites
                    gerais para o mapeamento de estruturas de dados em memórias são definidos nessa fase.
                    A frequência de clock irá influenciar o escalonamento, definindo se operações podem ser
                    realizadas em um único ciclo ou devem ocupar vários. A família de tecnologia subjacente
                    também influencia o escalonamento, pois o atraso de um componente define se ele ``cabe''
                    em um ciclo de clock.
                \item[Definição da microarquitetura] Nessa fase do processo o projetista já pensa em
                    detalhes de implementação do bloco de hardware: quais serão os protocolos de comunicação
                    pelos quais os parâmetros serão recebidos e enviados, a escolha precisa do tipo de
                    armazenamento para cada array (registradores, RAM, ROM), \emph{pipelines},
                    paralelização e fusão de loops.
                \item[Escalonamento] Escalonar um algoritmo em um circuito digital consiste em definir
                    quais operadores serão ativados em quais ciclos de clock, e com quais entradas. O
                    escalonamento toma como entrada o DFG e as características de \emph{timing}
                    dos operadores (dependentes de tecnologia). Nessa etapa possivelmente são gerados 
                    pipelines, inserindo-se registradores e lógica de controle conforme necessário.
                \item[Geração de código RTL] O passo final na síntese de alto nível. Nessa fase a
                    representação intermediária do circuito, já escalonada, é convertida para um (ou mais)
                    arquivo(s) VHDL/Verilog ou então para uma \emph{netlist}. Tipicamente, as
                    ferramentas de HLS possuem uma biblioteca de componentes em VHDL e/ou Verilog,
                    os quais são instanciados e interligados convenientemente em um grande arquivo que
                    contém o bloco projetado pelo usuário e todas as suas dependências. Esse grande arquivo
                    RTL pode então servir de entrada para as ferramentas das fabricantes de FPGAs.
            \end{description}

    
    \section{O sistema operacional EPOS}
        \label{sec:epos}
        O sistema operacional EPOS\cite{aoosbook} é um sistema operacional voltado para
        aplicações embarcadas. Ele foi programado em C++ utilizando-se de técnicas como orientação
        a aspectos e metaprogramação estática para alcançar um alto grau de configurabilidade e
        mesmo assim atender aos requisitos estritos de sistemas embarcados (como performance e
        tamanho de código). Várias aplicações interessantes e inovadoras demonstram a
        aplicabilidade do EPOS, por exemplo as aplicações em redes de sensores
        sem fio\cite{wanner-wsn}, envolvendo a plataforma EPOSMote\textregistered

        O EPOS utiliza a metodologia de desenvolvimento de sistemas embarcados orientados
        à aplicação\footnote{do inglês ``Application-Driven Embedded System Design}, guiando
        o desenvolvimento conjunto de componentes de software e hardware adaptáveis aos
        requisitos particulares de cada aplicação. De fato, pode-se dizer que o EPOS é um
        repositório de componentes de software e hardware, juntamente com ferramentas
        capazes de integrar tais componentes e produzir um ambiente de suporte à execução.

        O sistema assim gerado possui somente os componentes julgados necessários para
        a aplicação. A figura \ref{fig:epos-tools}\cite{froehlich} detalha os vários processos de
        integração e configuração dos componentes e aspectos que podem fazer parte de uma imagem de
        sistema EPOS. Também se destaca o fato de que uma aplicação que utiliza o EPOS pode
        ser implementada como um SoC, utilizando-se de componentes implementados em hardware
        e em software.
        \begin{figure}
            \begin{center}
                \includegraphics[width=0.7\textwidth]{imagens/epos_tools.pdf}
            \end{center}
            \caption[Geração de uma imagem de sistema EPOS]
            {Processo de integração e adaptação dos componentes para produzir uma imagem
            de sistema EPOS}
            \label{fig:epos-tools}
        \end{figure}

        Conceitos fundamentais de sistemas operacionais (por exemplo o conceito de
        \emph{escalonador}, de \emph{thread}, de \emph{semáforo}) são descritos como
        famílias de abstrações. Técnicas de programação orientada a aspectos são 
        utilizadas para adaptar essas abstrações às peculiaridades do ambiente
        em que o sistema irá executar (convenção de chamadas, número de registradores,
        ordem de bytes, entre outras). A entidade responsável por realizar essa adaptação
        da abstração ao cenário de execução é convenientemente chamada de \emph{Adaptador de
        cenário}. A figura \ref{fig:epos-scenario-adapters}\cite{froehlich} demonstra a relação
        entre adaptador de cenário, cenário, aspectos, componentes do sistema operacional e a
        aplicação.
        \begin{figure}[h]
            \begin{center}
                \includegraphics[width=0.6\textwidth]{imagens/scenario_adapter.pdf}
            \end{center}
            \caption[Relações entre as entidades do sistema EPOS]
            {diagrama UML identificando as relações entre os principais conceitos
            do sistema EPOS}
            \label{fig:epos-scenario-adapters}
        \end{figure}
        
        Um dos ideais do EPOS é que os componentes do sistema operacional possam ser implementados
        tanto em software (executando em um GPP) como diretamente em hardware. De fato, o conceito de
        \emph{componente híbrido} já foi bastante pesquisado, e em \citeonline{marcondes-hybrid} é dada
        a definição de uma arquitetura para a comunicação transparente entre componentes em hardware e
        em software.

        Dois grandes problemas ainda restam, porém: 1) As descrições em VHDL/Verilog são pouco
        suscetíveis à aplicação de aspectos (a aplicação de aspectos sobre código-fonte dessas
        linguagens não é comum). 2) O mesmo componente deve ser descrito em duas linguagens diferentes
        (C++ e VHDL/Verilog), com grandes diferenças no estilo e na semântica das descrições,
        aumentando a chance de serem introduzidos \emph{bugs} no sistema;

        Uma proposta de solução para o primeiro problema mencionado está sendo pesquisada
        \cite{aspect-systemc-tiago} ativamente. Ela consiste em realizar a descrição RTL dos
        componentes a serem implementados em hardware utilizando o \emph{framework} SystemC, em
        seu subconjunto sintetizável. Desse modo, todas as técnicas já conhecidas de aplicação de
        aspectos sobre C++ podem ser utilizadas, ao mesmo tempo em que a descrição pode ser sintetizada
        automaticamente (ferramentas de síntese de SystemC RTL já são relativamente comuns).

        Já o segundo problema mencionado é bem mais complexo: idealmente, deveria haver apenas uma
        versão de código-fonte C++ para um componente híbrido, e a versão desse componente
        implementada em hardware deveria ser sintetizada automaticamente, sem requerer uma tradução
        manual para RTL. O presente Trabalho de Conclusão de Curso busca contribuir com a solução
        dessa questão através de um estudo de caso, tentando demonstrar a plausibilidade da
        utilização de HLS para a descrição de componentes híbridos de SO.
