\chapter{Trabalhos Correlatos}
    \label{chap:correlatos}
    \epigraph{``Se vi mais longe foi por me apoiar sobre ombros de gigantes''}{Isaac Newton}

    \sigla{OSCI}{Open SystemC Initiative}
    \sigla{TLM}{Transaction-Level Modelling}
    \sigla{NoC}{Network-on-Chip}
    \sigla{DSL}{Domain-Specific Language}
    \sigla{RTL}{Register Transfer Level}
    \sigla{GPU}{Graphics Processing Unit}
    \sigla{SMP}{Symmetric Multiprocessing}
    \sigla{BORPH}{Berkeley Operating system for ReProgrammable Hardware}

    O esforço de se realizar síntese de hardware a partir de descrições comportamentais
    ainda é bastante imaturo, e várias metodologias, linguagens e ferramentas foram
    propostas desde meados dos anos 80. Essas propostas eram voltadas, porém, para aplicações
    específicas, como por exemplo o célebre ``compilador de silício''\footnote{do original
    em inglês \emph{silicon compiler}} \emph{Cathedral}\cite{cathedral}, desenvolvido no IMEC
    (Bélgica), que focava a área de processamento digital de sinais.
    
    Durante a década de 90, o processo de síntese a partir de VHDL/Verilog em nível RTL foi se
    aprimorando e até mesmo foram feitas algumas propostas de utilização de VHDL em nível
    comportamental, resultando em um modelo parcialmente temporal. Porém, tanto esse modelo
    quanto a linguagem se mostraram inadequados para uma descrição de circuitos em alto nível.
    
    Somente a partir dos anos 2000 que ferramentas de síntese de alto nível de \emph{propósito geral}
    passaram a ter uma maior penetração na indústria. Isso pois começaram a ser utilizadas como
    linguagens de entrada C, C++ e SystemC. Circuitos descritos em alto nível usando C, C++ e
    SystemC se assemelham muito mais a software. Além disso, essas são linguagens já amplamente
    conhecidas por programadores ao redor do mundo.

    Atualmente também estão em andamento alguns projetos na área de sistemas operacionais
    para computação reconfigurável. Esses projetos buscam trazer conceitos e modelos
    de SO para a computação em FPGA. Nesse âmbito estão inclusos
    tanto a aplicação de técnicas de SO em computação reconfigurável
    (escalonamento de tarefas, troca de contexto, comunicação inter-processos), como esforços
    de integração entre sistemas operacionais convencionais (executando em software) e
    aplicações implementadas em hardware.

    Nesse capítulo fazemos uma revisão de algumas das metodologias e ferramentas para
    síntese de alto nível com maior relevância atualmente, descrevendo suas
    particularidades. Tal revisão teve o objetivo de ajudar-nos a fazer  uma
    \emph{escolha informada} quanto à plataforma utilizada na implementação
    do trabalho. Levando em conta tal objetivo, procuramos obter na revisão uma
    amostra ampla de soluções, buscando variados fabricantes, linguagens de entrada e
    paradigmas de programação. Também é feita uma revisão de algumas propostas
    de integração de componentes de sistemas operacionais rodando em software e
    hardware.

    \section{Síntese de alto nível}
        \label{sec:hls-correlatos}
        Em uma analogia simplificada entre o projeto de hardware e
        o desenvolvimento de software podemos dizer que atualmente os
        projetistas de hardware ``programam'' seus sistemas em
        linguagem de montagem. As linguagens e ferramentas para
        síntese de alto nível têm como objetivo transportar a
        descrição de um algoritmo em hardware para um nível de
        abstração equivalente à programação de software em linguagens
        como C++, Java, etc.

        Uma das vertentes mais promissoras para atingir esse objetivo é
        a utilização do \emph{framework} SystemC\cite{ieee1666}. O
        SystemC é um grupo padronizado de classes C++ que permite
        a modelagem e simulação de componentes de hardware. Em SystemC
        é possível descrever o comportamento de componentes de hardware
        usando a sintaxe C++, e utilizando-se de várias abstrações para a
        comunicação inter-componentes.

        A OSCI, organização responsável pela
        manutenção e avanço do framework SystemC, disponibiliza também
        sob licença livre uma biblioteca para simulação de modelos SystemC.
        O projetista compila seu projeto descrito em SystemC com a cadeia
        usual de ferramentas (\emph{g++}, \emph{ld}, \emph{as}), e como resultado
        da compilação é gerado um arquivo executável. Ao ser executado, ele
        \emph{simula} o circuito descrito e pode produzir vários tipos de saída
        para depuração (incluindo arquivos com formas de onda). Não há ainda,
        porém, nenhum projeto de software livre para a síntese de hardware a
        partir de SystemC.

        \subsection{Abordagens baseadas em SystemC}
            \label{subsec:systemc-correlatos}
            Dentre os produtos comerciais para síntese de alto nível, um dos que utiliza
            modelos em SystemC como entrada é o \emph{Cynthesizer}\textregistered,
            da Forte Design Systems. os modelos são escritos em SystemC de nível
            TLM e a ferramenta faz a tradução para componentes RTL, os quais podem
            então ser fabricados como ASIC, ou sintetizados em FPGA (utilizando
            as ferramentas dos fornecedores).

            Muitos dos detalhes necessários à implementação do modelo em hardware
            são omitidos na descrição TLM. por isso, a ferramenta
            \emph{Cynthesizer}\textregistered incorpora também um módulo para exploração de
            espaço de projeto, permitindo que o projetista defina restrições e métricas
            sobre o circuito, buscando otimizar tais métricas.


        \subsection{Síntese de ANSI C++}
            \label{subsec:ansic-correlatos}
            Além do SystemC, existem também abordagens que buscam realizar a síntese a partir de
            descrições em ANSI C++. Algumas ferramentas trabalham com C++ padrão ANSI,
            e permitem utilização de construções avançadas da linguagem, tais como ponteiros, classes
            e structs, \emph{arrays} multidimensionais e metaprogramação via \emph{templates}. Já
            outras ferramentas trabalham com subconjuntos mais restritos da linguagem, e usam
            extensões que tornam as descrições de hardware incompatíveis com compiladores
            tradicionais de C++ para software.

            Algumas construções de C++, porém, são invariavelmente inadequadas à uma implementação em
            hardware e, portanto, não são suportadas por nenhuma das ferramentas de síntese pesquisadas.
            Em geral a inadequação dessas construções advém da necessidade de conhecer todos os detalhes
            do algoritmos em tempo de síntese. Tal necessidade proíbe:
            \begin{description}
                \item[Alocação dinâmica de memória] A quantidade de memória a ser utilizada pelo algoritmo
                    precisa ser um valor conhecido em tempo de síntese. Alocar memória dinamicamente em
                    um FPGA significaria reconfigurar partes de um FPGA dinamicamente, uma tarefa
                    atualmente ainda complexa e ineficiente.
                \item[Recursões não limitadas] Funções recursivas sem limite explícito de profundidade
                    de chamadas recaem no uso de alocação dinâmica e são, portanto, inadequadas à
                    implementação em hardware. Isso pois, na chamada de uma nova instância de função
                    recursiva, novo espaço teria de ser alocado para as variáveis no escopo local
                    \emph{daquela} instância. Algumas ferramentas dão suporte à \emph{recursão com
                    profundidade limitada}, implementada utilizando-se de metaprogramação estática
                    via \emph{templates}.
            \end{description}

            Uma cadeia de ferramentas de grande destaque em HLS
            é o \emph{Catapult-C}\textregistered, do fabricante Mentor Graphics\textregistered.
            Uma peculiaridade do Catapult-C é que ele aceita como linguagens de entrada
            no projeto de um sistema tanto C++ (ANSI) como SystemC. Enquanto a entrada
            em C++ modela basicamente o \emph{comportamento} do sistema sendo projetado,
            a entrada em SystemC permite a especificação de mais detalhes arquiteturais,
            tais como a configuração de barramentos e NoC.

            Em um processo de refinamento interativo, o Catapult-C oferece ao projetista
            comparativos entres as várias opções de parâmetros deixados livres pela
            descrição em alto nível, e através de estatísticas e gráficos o projetista
            faz uma decisão informada levando em consideração as prioridades do projeto
            em questão. o Catapult-C também é capaz de realizar a síntese automática
            de interfaces entre componentes, e possui um módulo que faz a otimização do
            consumo de energia nos componentes produzidos, levando em conta as características
            próprias dos dispositivos de vários fabricantes.


        \subsection{Haskell ForSyDe}
            \label{subsec:forsyde}
            Uma abordagem bastante diferente de todas as mencionadas anteriormente chama-se
            ForSyDe (Formal System Design)\cite{forsyde-case}. ForSyDe é uma linguagem de domínio
            específico (DSL) embutida na linguagem Haskell na forma de biblioteca, sendo capaz de
            simular circuitos ou gerar código VHDL sintetizável a partir de uma descrição em alto
            nível. Um fato interessante é que o código VHDL gerado pelo ForSyDe é bem estruturado
            e legível, o que torna bastante fácil realizar alterações no VHDL, caso o projetista
            deseje. Na figura \ref{fig:forsyde-haskell} temos o exemplo de um componente
            \emph{multiply-accumulate}, que implementa a seguinte função:
            \[
                a \leftarrow a + (b \times c)
            \]
            O componente multiplica o valor de seus dois sinais de entrada a cada ciclo do
            relógio, e acumula o resultado da multiplicação em um registrador. A operação
            \emph{multiply-accumulate} é uma operação básica e importantíssima que compõe
            uma vasta quantidade de operações em álgebra linear e processamento digital de
            sinais. Na figura \ref{fig:forsyde-vhdl} está o código VHDL gerado a partir do
            modelo descrito em Haskell.
            \begin{figure}[h]
                \begin{center}
                    \lstinputlisting[language=Haskell]{code-figures/DotProductOnline.hs}
                \end{center}
                \caption{Descrição ForSyDe do componente \emph{multiply-accumulate}}
                \label{fig:forsyde-haskell}
            \end{figure}
            \begin{figure}[h!]
                \begin{center}
                    \lstinputlisting[language=VHDL]{code-figures/dotp.vhd}
                \end{center}
                \caption{VHDL gerado para o componente \emph{multiply-accumulate}}
                \label{fig:forsyde-vhdl}
            \end{figure}

            Talvez a característica que mais chame a atenção na descrição em ForSyDe é o
            tamanho reduzido. Enquanto a descrição em ForSyDe do circuito tem cerca de 20
            linhas, o código VHDL gerado tem mais de 200 linhas (a figura
            \ref{fig:forsyde-vhdl} mostra somente o componente raiz da hierarquia VHDL).

            Os conceitos fundamentais na descrição de um circuito em ForSyDe são o
            \emph{processo} e o \emph{sinal}. 
        
            \begin{description}
                \item[Sinal] Um sinal é um tipo de dados isomórfico à
                uma lista, e onde cada elemento da lista é o valor do sinal em um
                determinado ciclo de relógio (o ForSyDe utiliza um modelo de
                computação síncrono). Um sinal representa um canal de comunicação
                entre processos.

                \item[Processo] É a unidade básica de modelagem em ForSyDe. Um
                processo é uma função que transforma sinais de entrada em sinais
                de saída. Existem vários \emph{construtores de processos}, tanto
                para processos combinacionais quanto sequenciais. Um exemplo de
                um simples processo combinacional (mapSY) é dado na figura
                \ref{fig:forsyde-map}. Ele transforma um sinal de entrada
                em um sinal de saída, aplicando a cada ciclo de relógio uma
                função sobre o valor atual da entrada, produzindo a saída
                correspondente.
            \end{description}

            \begin{figure}[h]
                \begin{center}
                    \includegraphics{imagens/mapSY.pdf}
                \end{center}
                \caption{O construtor de processo mapSY}
                \label{fig:forsyde-map}
            \end{figure}

            Através da combinação recursiva de processos é que se dá a
            construção de um modelo ForSyDe. Dois ou mais processos podem ser combinados
            utilizando-se, por exemplo, de \emph{composição}. Assim, os sinais
            de entrada e saída do processo de mais alto nível nessa árvore definem a
            própria interface do componente sendo modelado.

        \subsection{Microsoft Accelerator}
            \label{subsec:accelerator}
            O Microsoft\textregistered Accelerator é uma abordagem para a expressão de algoritmos
            paralelos em um alto nível de abstração, implementada na forma de uma biblioteca de
            classes C++. Utilizando-se de classes e funções da biblioteca Accelerator o usuário é
            capaz de expressar algoritmos no paradigma de
            \emph{paralelismo aninhado de dados}\footnote{do inglês ``Nested Data Parallelism''}
            \cite{nesl}. Esses algoritmos podem ser executados em variadas plataformas-alvo
            (GPU, SMP, \emph{clusters} e FPGA).

            Através dos objetos da classe \emph{ParallelArray} -- vetores sobre os quais operações são
            realizadas em paralelo -- e de diversos operadores sobrecarregados entre objetos desse tipo,
            a biblioteca Accelerator produz uma árvore de expressão representando o algoritmo. Na figura
            \ref{fig:accelerator-code} temos um exemplo de árvore de expressão Accelerator.
            \begin{figure}[h!]
                \begin{center}
                    \includegraphics[width=0.4\textwidth]{imagens/accelerator-exptree.png}
                \end{center}
                \caption[Árvore de expressão de um objeto ParallelArray]
                {Árvore de expressão gerada por meio de operações sobre um objeto do tipo
                ParallelArray}
                \label{fig:accelerator-code}
            \end{figure}


    \section{Sistemas operacionais para Computação Reconfigurável}
        \label{sec:rc-sos}
        Como já exposto no capítulo de conceitos, a computação reconfigurável é um
        novo paradigma para a execução de algoritmos. A implementação efetiva desse
        paradigma ainda está dando seus primeiros passos, e a comodidade de
        desenvolvimento de sistemas reconfiguráveis é incomparavelmente
        maior do que a do desenvolvimento de software convencional (para a
        arquitetura de \emph{von Neumann}).

        Uma das razões que retardam a adoção ampla de sistemas de computação reconfigurável
        é a falta de um sistema operacional para esse paradigma. Um sistema operacional realiza
        escalonamento de recursos (processador, periféricos, etc.), gerencia entrada e
        saída de dados -- entre outras tarefas -- abstraindo assim vários detalhes
        arquiteturais da máquina subjacente e simplificando a interface de programação.

        Um sistema operacional para sistemas reconfiguráveis poderia ter as seguintes
        responsabilidades\cite{borph}, análogas às responsabilidades de um sistema
        operacional convencional:
        \begin{itemize}
            \item Estabelecer uma noção de \emph{componente de hardware} (análoga à
            noção de processo)

            \item Fornecer uma interface unificada para interação entre componentes de
            hardware e entre componentes de hardware e componentes de software

            \item Realizar o escalonamento do dispositivo FPGA (tanto temporal quanto
            espacial) para acomodar os componentes de hardware atualmente em execução

            \item Controlar a configuração do dispositivo FPGA, realizando a
            reconfiguração das áreas que serão ocupadas por novos componentes
        \end{itemize}

        \subsection{BORPH}
            \label{subsec:borph}
            Em \citeonline{borph}, os autores descrevem a implementação de um
            sistema operacional para computadores reconfiguráveis bastante interessante: o sistema
            BORPH. O BORPH é uma extensão de um sistema Linux padrão, fornecendo suporte 
            de execução a aplicativos em FPGA.

            Nessa extensão do Linux, o conceito de processo é estendido também para aplicativos
            executando em hardware, e tais processos têm (como os processos em software) acesso normal
            a periféricos e ao sistema de arquivos. Processos em hardware podem comunicar-se entre si,
            e também com processos em software, através de arquivos \emph{pipe}, o mecanismo tradicional
            Unix de comunicação inter-processos. A operação de ``carga'' de um processo em hardware se
            dá pela configuração de uma área do FPGA que irá executá-lo, e o código binário para tal
            configuração é armazenado em um formato de arquivo inspirado no ELF.
            
            O BORPH não trata, porém, da questão de implementação de \emph{componentes do SO} em
            hardware. Como este SO segue o modelo de implementação do Linux, o \emph{kernel} do sistema
            é monolítico. Desse modo, componentes como escalonador, timer e sistemas de arquivos não podem
            ser implementados em hardware, pois não são processos.

        \subsection{HybridThreads}
            \label{subsec:hthreads}
            O projeto \emph{HybridThreads}\cite{hthreads} (HThreads), da Universidade de Arkansas, consiste de
            um SO que suporta a implementação de \emph{threads} tanto em hardware quanto em software, e a
            utilização dessas \emph{threads} de forma transparente para o usuário. Um \emph{wrapper} que
            disponibiliza a interface com todas as operações típicas realizadas sobre uma \emph{thread} foi
            implementado como um Soft IP, fazendo com que a interface seja uniforme entre \emph{threads} em
            hardware e em software seja uniforme.

            Uma das características distintivas do HThread é o fato de que, como pode ser observado na
            figura \ref{fig:hthreads}, alguns componentes do SO são implementados em hardware, como
            por exemplo o próprio escalonador, visando a redução de \emph{jitter}\footnote{termo normalmente
            usado para variação de atraso} e melhora no determinismo do tempo de execução dos aplicativos
            usando o sistema. O mesmo objetivo (diminuição de jitter) também é almejado com a nossa
            implementação do escalonador do EPOS em hardware.
            \begin{figure}[h]
                \begin{center}
                    \includegraphics[width=0.9\textwidth]{imagens/hthreads.jpg}
                \end{center}
                \caption{Arquitetura geral de um SoC utilizando HThreads}
                \label{fig:hthreads}
            \end{figure}

            Tanto as \emph{threads} do usuário, quanto os componentes do sistema HThreads que rodam em
            hardware devem ser, porém, descritos em VHDL ou Verilog em nível RTL. Faz parte do projeto 
            \emph{HybridThreads} um esforço para fazer síntese automática a partir de código-fonte C, mas
            esse esforço ainda é bastante imaturo. Talvez a própria modelagem do sistema, considerando uma
            \emph{thread} como componente básico a ter implementação em hardware, seja inadequada.

