\chapter{Desenvolvimento}
    \label{chap:desenvolvimento}
    \epigraph{``A elegância não é luxo supérfluo, mas uma qualidade \emph{decisiva} entre o
        sucesso e o fracasso''}{Edsger Wybe Dijkstra}

    \sigla{BRAM}{Block RAM} 
    \sigla{AMBA}{Advanced Microcontroller Bus Architecture}
    \sigla{AXI}{Advanced eXtensible Interface}
    \sigla{EDF}{Earliest Deadline First}

    A solução desenvolvida para alcançar os objetivos previstos, com todos seus detalhes de implementação,
    é apresentada neste capítulo. São também justificadas as escolhas de projeto feitas durante o
    desenvolvimento.

    Nossa implementação de um escalonador em hardware para o EPOS iniciou-se com uma análise da
    atual implementação (em software) do escalonador do sistema. Propositadamente, tentamos nos
    aproximar o máximo possível da implementação em software, realizando na modelagem e no código
    somente as alterações impostas pela ferramenta de síntese de alto nível.

    A ferramenta de síntese de alto nível utilizada foi o Catapult-C\textregistered , da fabricante
    Mentor Graphics. O uso desta ferramenta em particular se justifica, principalmente, pelo seu
    suporte abrangente às várias funcionalidades da linguagem C++ (linguagem em que a maior parte do
    EPOS está implementada). Sem o suporte do Catapult-C à \emph{templates}, em especial, seria
    praticamente impossível sintetizar código EPOS.
    
    Apesar de não termos testado outras ferramentas, cremos que as limitações com as quais nos
    deparamos durante o trabalho (detalhadas nas seções seguintes) são gerais, referindo-se ao próprio
    cenário de implementação (hardware) e não à ferramenta que escolhemos.    
    
    Nenhuma otimização ou alteração foi feita no código C++ visando especificamente a implementação
    em hardware. Dessa maneira, podemos situar o presente trabalho como um ``extremo oposto'' em
    nível de abstração, se comparado à modelagem RTL.

    Nas seções seguintes é mostrado o escalonador atual do sistema EPOS (sua implementação em software) e
    é feita uma análise de suas estruturas de dados. Logo após, damos uma visão geral da implementação de
    referência em hardware (nível RT) com a qual nossa modelagem será comparada. Por fim, descrevemos em
    detalhes nossa proposta de implementação.


    \section{O escalonador do EPOS em software}
        \label{sec:escalonador-epos}
        O componente escalonador atual do sistema EPOS está modelado no \emph{template} de classe
        System::Scheduler\textless T\textgreater, e portanto é capaz de escalonar recursos de um
        tipo arbitrário, e com um critério de escalonamento também arbitrário. Os requisitos
        a serem seguidos pelo parâmetro T são os mesmos impostos pelo template 
        System::Scheduling\_Queue\textless T\textgreater ,
        e tais requisitos são detalhados na seção \ref{sec:estruturas-escalonador}. De fato,
        a classe Scheduler \emph{herda} seus métodos da classe Scheduling\_Queue, adicionando alguns
        outros para exportar uma interface mais conveniente. A figura \ref{fig:scheduler-sw-inheritance}
        mostra as relações de herança em que a classe Scheduler se envolve.
        \begin{figure}[h]
            \begin{center}
                \includegraphics[width=0.6\textwidth]{imagens/scheduler-epos-inheritance.pdf}
            \end{center}
            \caption[Diagrama de herança do escalonador do EPOS]
            {Diagrama mostrando as relações de herança e especialização do escalonador atual do EPOS
            (implementação em software). A linha pontilhada indica uma especialização de template.
            \label{fig:scheduler-sw-inheritance}}
        \end{figure}

        Em vários sistemas operacionais o escalonador é o componente de software responsável pelo
        gerenciamento do recurso CPU, a ordenação das threads que concorrem pelo seu uso e a troca
        de contexto no momento da escolha de uma nova thread para ocupar a CPU. Já no EPOS o componente
        escalonador tem a \emph{única responsabilidade} de gerenciar uma (ou várias) filas de entidades
        que concorrem ao recurso (CPU ou outros). As responsabilidades de gerar interrupções periódicas
        para \emph{sensibilizar} o escalonador e de realizar a troca de contexto propriamente dita ficam
        por conta dos componentes \emph{Alarm} e \emph{CPU}, respectivamente.

        Essa boa separação de responsabilidades\cite{hursch} no projeto do EPOS contribui para uma
        maior facilidade na implementação dos componentes-chave do sistema operacional em hardware.
        Tal separação se manifesta de maneira bastante clara nas estruturas de dados do sistema operacional,
        que têm aspectos de encadeamento e armazenamento fatorados e integrados em tempo de compilação
        através de metaprogramação estática\cite{aoosbook}.
        

    \section{Estruturas de dados utilizadas}
        \label{sec:estruturas-escalonador}
        O diagrama \ref{fig:estruturas-escalonador} mostra a hierarquia de herança entre as classes
        de estruturas de dados utilizadas pelo escalonador atual do EPOS (em software).
        \begin{figure}
            \begin{center}
                \includegraphics[width=0.96\textwidth]{imagens/scheduler-structures.pdf}
            \end{center}
            \caption[Hierarquia das estruturas de dados do escalonador]
            {Diagrama das relações de herança e especialização entre as estruturas de dados da
            implementação do escalonador, destacando-se a fila de escalonamento
            \label{fig:estruturas-escalonador}}
        \end{figure}

        A estrutura de dados fundamental do escalonador é uma fila de escalonamento, objeto da
        classe System::Scheduling\_Queue\textless T,Q\textgreater, com os parâmetros:
        \begin{description}
            \item[T:] O tipo de objeto a ser escalonado. Como a fila é genérica, não apenas
                \emph{Threads} são passíveis de escalonamento. Qualquer tipo pode ser
                utilizado como T, devendo satisfazer apenas aos seguintes requisitos:
                \begin{itemize}
                    \item Declarar um tipo chamado ``Criterion'', que será usado como critério de
                        ordenamento da fila.
                    \item Declarar um método ``link'', para satisfazer à interface de elemento de lista.
                \end{itemize}

            \item[Q:] parâmetro de tipo inteiro sem sinal, indica \emph{quantas} filas de escalonamento
                devem ser utilizadas.
        \end{description}

        Sobre a hierarquia de listas e filas do EPOS cabem ainda alguns comentários adicionais:
        \begin{description}
            \item[List\textless T, El\textgreater] É um template de lista duplamente encadeada,
                onde o parâmetro El encapsula o encadeamento.
                \begin{itemize}
                    \item El deve implementar \emph{getters} e \emph{setters} para os
                        atributos ``next'' e ``prev''.
                    \item El é um parâmetro \textbf{opcional} do template, e seu valor padrão \\
                        é List\_Elements::Doubly\_Linked\textless T\textgreater
                \end{itemize}

            \item[Ordered\_List\textless T, R, El, relative\textgreater]
                Subclasse de List\textless T, El\textgreater, este é um template de lista ordenada,
                que recebe dois parâmetros adicionais:
                \begin{description}
                    \item[R:] um tipo que encapsula o conceito de \emph{rank} de um elemento.
                        Qualquer tipo de dados \emph{isomórfico} aos números inteiros pode ser
                        usado como R, devendo implementar o método de \emph{cast} para int. Este
                        parâmetro é \textbf{opcional} e seu valor padrão é List\_Element\_Rank.
                    \item[relative:] um parâmetro booleano indicando se a lista é \emph{relativa}.
                        Diz-se que uma lista ordenada é relativa quando cada elemento armazena
                        apenas a diferença entre seu rank e o de seu antecessor. Este parâmetro
                        é \textbf{opcional} e seu valor padrão é false.
                \end{description}
        \end{description}


        \subsection{Lista duplamente encadeada}
            \label{subsec:lista-encadeada}
            A raiz na hierarquia de classes a serem implementadas em hardware, e portanto a estrutura
            de dados fundamental para o escalonador, é uma lista duplamente encadeada. O diagrama UML
            da figura \ref{fig:lista-uml} mostra as operações implementadas pela lista.
            \begin{figure}[h]
                \begin{center}
                    \includegraphics[width=0.4\textwidth]{imagens/list_uml.pdf}
                \end{center}
                \caption[Diagrama de classe da lista duplamente encadeada]{Diagrama de classe UML
                da lista duplamente encadeada usada no trabalho \label{fig:lista-uml}}
            \end{figure}
            
            Dada a importância
            dessa estrutura nós decidimos implementá-la antes de partir para a implementação do
            escalonador em si, como maneira de explorar a ferramenta de síntese e conhecer mais a fundo
            suas limitações. O código C++ da lista, do seu gerenciador de alocação, assim como do 
            testbench de verificação funcional VHDL e o script com as diretivas da síntese se
            encontram no apêndice \ref{ap:lista}.

            A estratégia de verificação por \emph{asserções} foi utilizada, com o uso das palavras-chave
            \emph{assert} e \emph{report} da linguagem VHDL. O testbench consiste de vários
            casos de teste autoverificáveis, que são executados em sequência. Cada caso de teste
            compara o valor de uma saída produzida pelo bloco sob teste com uma saída esperada. Caso haja
            discrepância entre os valores, tanto o valor esperado quanto o produzido são relatados.


        \subsection{Lista ordenada}
            \label{subsec:lista-ordenada}
            A lista ordenada do EPOS (classe Ordered\_List\textless T, R, El\textgreater) estende a lista
            duplamente encadeada, e possui a mesma interface (mesmos métodos públicos) que aquela. Duas
            diferenças são notáveis, porém:
            \begin{itemize}
                \item Há um parâmetro extra (R) para o template: esse parâmetro é o tipo de \emph{rank} usado
                    na ordenação dos elementos. Um tipo T qualquer, para poder servir de rank, deve
                    realizar a sobrecarga do operador de cast para tipo inteiro.
                \item A classe Ordered\_List\textless T, R, El\textgreater reimplementa os métodos insert e
                    remove da sua superclasse, para realização a inserção sempre \emph{em ordem} (de acordo
                    com o rank), bem como a atualização dos ranks vizinhos na remoção (no caso de rank
                    relativo).
            \end{itemize}


        \subsection{Fila de escalonamento}
            \label{subsec:fila-escalonamento}
            Seguindo a filosofia de implementação do EPOS, o comportamento de filas de escalonamento está
            isolado dos seus detalhes de implementação (como alocação e armazenamento) e implementado na
            classe \emph{Scheduling\_Queue\textless T, Q\textgreater}. O parâmetro T é o tipo de entidade
            a ser escalonado, enquanto o parâmetro Q define o número de filas a serem usadas no escalonamento.

            Qualquer tipo T de entidade pode ser escalonado, desde que satisfaça ao seguinte requisito:
            \begin{itemize}
                \item T deve declarar um tipo ``Criterion''. O tipo T::Criterion será utilizado como critério de
                    ordenação das filas subjacentes ao escalonador, e define qual é o algoritmo de
                    escalonamento a ser utilizado. Alguns critérios já implementados no EPOS são Round-Robin,
                    Rate monotonic e EDF.
            \end{itemize}

            O diagrama \ref{fig:scheduling-queue-thread} detalha os métodos públicos da classe
            Scheduling\_Queue, assim como um exemplo de entidade escalonável, uma \emph{Thread}
            \begin{figure}[h]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imagens/scheduling-queue-thread.pdf}
                \end{center}
                \caption[Diagramas de classe das classes Scheduling\_Queue e Thread] 
                {Diagrama de classe UML da fila de escalonamento utilizada no trabalho e da classe
                Thread, um exemplo de entidade escalonável \label{fig:scheduling-queue-thread}}
            \end{figure}



    \section{Implementação RTL de referência}
        \label{sec:escalonador-hugo}
        Para avaliar a eficácia do processo de síntese de alto nível nós realizamos uma análise comparativa
        (em termos de área ocupada e atraso) com uma implementação de referência; os detalhes dessa análise
        encontram-se no capítulo \ref{chap:resultados}.

        Nossa referência é a implementação de um escalonador em nível RT (escrito na linguagem VHDL),
        descrito em \cite{marcondes-hybrid}. A figura \ref{fig:scheduler-rtl} mostra a arquitetura
        geral desse escalonador.
        \begin{figure}[h]
            \begin{center}
                \includegraphics[width=0.75\textwidth]{imagens/scheduler-rtl.pdf}
            \end{center}
            \caption[Implementação RTL de referência do escalonador]
            {Diagrama de blocos da implementação de referência do escalonador (descrita em VHDL nível RT)
            \label{fig:scheduler-rtl}}
        \end{figure}
        
        O bloco escalonador contém vários pequenos sub-blocos, cada um encapsulando um dos serviços fornecidos.
        Além desses blocos algorítmicos, ainda compõem o escalonador uma memória que armazena a fila de
        escalonamento, um bloco responsável pelo gerenciamento de recursos e uma interface que faz a
        interpretação dos comandos recebidos do mundo externo e ativa o bloco algorítmico correspondente.

        Para proporcionar uma comparação válida com a referência nossa proposta de escalonador aceita em
        sua interface o mesmo conjunto de comandos. A tabela \ref{tab:scheduler-rtl-commands} detalha
        cada uma das operações oferecidas pela implementação de referência (e também na implementação
        proposta, por consequência).
        \input{tabelas/scheduler-rtl-commands.tex}



    \section{Nossa proposta de escalonador em hardware}
        \label{sec:escalonador-nosso}
        Como já foi mencionado no início do capítulo, nossa implementação de um escalonador a ser
        implementado em hardware foi guiada pelo desejo de se realizar o menor número possível de
        modificações em relação ao escalonador que executa em software. Em particular, quanto às
        alterações que tiveram de ser realizadas, dois princípios foram seguidos:
        \begin{itemize}
            \item As alterações devem permitir que o componente possa \emph{continuar} a executar
                em software sem alteração de semântica, mesmo que com penalidade de performance.
            \item Deve-se, sempre que possível, encapsular as alterações em classes, evitando alterar
                diretamente o código-fonte do componente a ser sintetizado.
        \end{itemize}

        As alterações realizadas foram ditadas pelas restrições impostas pela ferramenta de síntese
        (Catapult-C, seção \ref{subsec:ansic-correlatos}). A seguir é detalhado cada um dos tipos
        de alterações realizados sobre o código C++ original do EPOS, justificando-se a necessidade
        de tal alteração e o raciocínio por trás da solução adotada.


        \subsection{O tipo Maybe\textless T\textgreater}
            \label{subsec:maybe}
            Durante o fluxo de síntese de alto nível, estruturas do tipo array\footnote{uma sequência
            de elementos de dados residentes em uma faixa contínua do espaço de endereçamento} presentes
            no código são mapeadas para bancos de registradores ou memórias, e as variáveis do tipo
            ponteiro são mapeadas para índices dos arrays aos quais se referem.

            Em um código C++ sintetizável, todo ponteiro deve se referir a uma estrutura de dados
            definida no código. Uma análise estática do código é realizada pela ferramenta de síntese
            para garantir que em nenhum dos possíveis fluxos de execução um ponteiro inválido seja
            desreferenciado. Em particular, são proibidas atribuições de literais inteiras a variáveis
            do tipo ponteiro.

            As interfaces das estruturas de dados do EPOS em geral, e a da classe Scheduling\_Queue, em
            particular, trabalham com ponteiros, e em várias situações ponteiros nulos (inválidos), são
            retornados para sinalizar situações de falha. Para contornar essa inadequação aos requisitos
            de síntese introduzimos o \emph{tipo opção}\footnote{do inglês ``Option Type''. 
            \url{http://en.wikipedia.org/wiki/Option_type}} Maybe\textless T\textgreater .

            O tipo Maybe\textless T\textgreater  pode ser conceitualmente definido da seguinte maneira:
            \begin{center}
            \begin{lstlisting}
                    Maybe T = Nothing | Just T
            \end{lstlisting}
            \end{center}

            Ou seja, há dois construtores possíveis para obter-se um valor do tipo
            Maybe\textless T\textgreater : Um construtor vazio (chamado de \emph{Nothing}) e um construtor
            que toma um parâmetro (chamado de \emph{Just}).
            
            O conceito de tipo opção advém de linguagens de programação funcionais, e é uma maneira popular
            de se modelar operações que podem falhar. Em nosso caso, por exemplo, o método de remoção de
            um elemento da fila de escalonamento fica com a seguinte assinatura:
            \begin{center}
            \begin{lstlisting}
                    Maybe<Element*> remove(Element* e)
            \end{lstlisting}
            \end{center}

            A operação de remoção pode falhar (no caso de o elemento procurado não estar presente na fila),
            e essa falha é então representada pelo retorno de um valor Nothing. 

            O código completo da classe Maybe\textless T\textgreater  implementada neste trabalho segue:
            \begin{center}
                \lstinputlisting[language=C++]{code-figures/maybe.h}
            \end{center}


        \subsection{Gerenciamento de alocação}
            \label{subsec:escalonador-prealloc}
            Uma das limitações da implementação de algoritmos em hardware, como já discutido no capítulo
            de fundamentos, é a impossibilidade de se utilizar alocação dinâmica de memória.

            Por outro lado, todas as estruturas de dados do EPOS são independentes da forma com que seus
            elementos estão alocados. Isso permitiu que não fizéssemos qualquer alteração no código das
            estruturas nesse sentido. Devido, porém, justamente a essa independência, tivemos que
            implementar separadamente um gerenciador de alocação para as filas de escalonamento.

            A classe Scheduler\_PreAlloc implementa esse gerenciador. Um objeto da classe 
            Scheduler\_PreAlloc é um \emph{invólucro} para um objeto da classe Scheduling\_Queue, e exporta
            publicamente uma interface bastante semelhante à do objeto envolvido. Duas grandes diferenças
            podem ser notadas: as operações possuem semântica de passagem \emph{por valor} e nas inserções e
            remoções são feitas alocações e liberações de espaço no armazenamento subjacente. A figura
            \ref{fig:scheduler-blocks} mostra um diagrama de blocos do gerenciador, enquanto seu código
            se encontra no apêndice \ref{ap:escalonador:prealloc}.
            \begin{figure}[h]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imagens/scheduler-blocks.pdf}
                \end{center}
                \caption[Diagrama de blocos do gerenciador de alocação]
                {Diagrama de blocos do gerenciador de alocação para a fila de escalonamento Scheduling\_Queue
                \label{fig:scheduler-blocks}}
            \end{figure}

            O armazenamento para os elementos das filas de escalonamento é realizado em uma estrutura de
            dados do tipo array. A figura \ref{fig:busca-alloc} mostra o código da busca por uma
            posição livre no array, realizada quando há a necessidade de alocar espaço para um novo elemento.
            \begin{figure}[h]
                \centering \lstinputlisting[language=C++]{code-figures/alloc-search.cpp}
                \caption[Busca por posição livre no bitmap de armazenamento]
                {Busca por uma posição livre no bitmap de armazenamento da classe Scheduler\_PreAlloc
                \label{fig:busca-alloc}}
            \end{figure}

            Este código faz uma busca linear sobre um bitmap de alocação para o array. O laço que percorre
            o bitmap pode ser desenrolado, e essa é, de fato, uma das otimizações discutidas no capítulo de
            resultados.
            

        \subsection{Wrapper da interface raiz}
            \label{subsec:escalonador-wrapper}
            Uma das restrições mais importantes da ferramenta de síntese de alto nível utilizada se refere
            à forma como é feita a inferência das portas de entrada e saída do bloco de hardware sendo
            modelado. O projetista deve designar \emph{uma única} função em todo o seu código como
            a função ``raiz'' do bloco. Isso é feito colocando-se o \emph{pragma}\footnote{anotação
            não-padronizada feita no código que dá ao compilador informações extras sobre o software, não
            presentes na linguagem fonte} ``hls\_design top'' sobre a assinatura da função.

            A ferramenta de síntese irá então inferir, a partir dos parâmetros presentes na assinatura e da
            forma como eles são utilizados, as portas de entrada e saída do bloco de hardware sendo
            modelado, sendo que os tipos dos parâmetros definirão os tamanhos das portas.

            Nosso escalonador é um objeto, e sua interface possui um método para cada operação oferecida,
            com parâmetros diferentes para cada método. A figura \ref{fig:scheduler-toplevel} mostra a
            solução adotada para adaptar a interface da classe \emph{Scheduler\_PreAlloc} à função
            que define a interface do bloco em hardware.
            \begin{figure}[h]
                \begin{center}
                    \includegraphics[width=0.55\textwidth]{imagens/scheduler-toplevel.pdf}
                \end{center}
                \caption[Diagrama do bloco raiz do escalonador]
                {Diagrama do bloco raiz do escalonador sintetizado, enfatizando as portas
                de entrada e saída e a lógica de \emph{dispatch} das operações
                \label{fig:scheduler-toplevel}}
            \end{figure}

            Basicamente, a união de todos os possíveis parâmetros dos métodos da classe Scheduler\_PreAlloc
            é manifestada na assinatura da função \emph{call} (que é anotada com o pragma ``hls\_design
            top``). Além disso, a função call possui um parâmetro extra do tipo \emph{MethodId}. O tipo
            MethodId é um tipo enumerado e um valor desse tipo identifica uma operação realizável pelo
            bloco de hardware.

            Dois parâmetros de saída estão presentes na função call: \emph{status} e \emph{return\_val}. A
            ferramenta de síntese não impede que a função raiz possua valor de retorno, porém a utilização
            de parâmetros passados por referência como forma de saída de dados foi escolhida por a
            considerarmos uma maneira mais uniforme de expressar as saídas.
