Pré-relatório do Trabalho de MC723
060450 – Erivelton Oliveira
064304 – Rodrigo Chiossi
070168 - Andre Petris Esteve
1. Introdução
Neste projeto iremos desenvolver uma plataforma de hardware baseada na plataforma ARP para
simular um hardware dedicado à função de Ordenação de Inteiros. A motivação deste projeto é a criação de
uma plataforma capaz de executar de maneira otimizada o software IS (Integer Sort) pertencente ao pacote
NPB 3.3.1 (NAS Parallel Benchmarks) desenvolvido pela NASA. Uma das motivações do desenvolvimento
do NPB foi criar um conjunto de programas capazes de se aproveitar de processamento paralelo de
maneira a permitir avaliar o desempenho de algoritmos de paralelização. Esta afinidade com paralelização
nos permitirá desenvolver uma plataforma com múltiplos processadores e distribuir a execução do software
entre eles.
O diagrama abaixo apresenta a estrutura da plataforma a ser desenvolvida:
No diagrama estão presentes os dois componentes a serem desenvolvidos durante este projeto. O
projeto inicial é adicionar duas copias de cada componente para permitir uso dedicado de cada um por parte
dos processadores para permitir maior paralelismo, uma vez que apenas a memória seria então
compartilhada. Esta estrutura proposta pode ser reduzida para apenas um componente de cada tipo,
compartilhados entre os processadores caso se mostre mais conveniente durante o desenvolvimento do
projeto.
Os componentes Lock e ID permitem o compartilhamento de recursos e a identificação dos
processadores. O componente lock implementa uma operação atômica de “compare and assign”, permitindo
implementar locks em software. O componente de ID implementa um contador que é adicionado sempre
que uma leitura ao componente é realizada, de maneira que nenhuma leitura a este componente retornará o
mesmo resultado. Este componente permite separar o fluxo de execução uma vez que os dois
processadores não irão obter o mesmo valor após a leitura desde componente, o que pode ser utilizado
para identificá-los.
2. Novos Componentes
2.1. Componente randlc
2.1.1. Descrição
Este componente gera um número pseudo-aleatório com precisão de um double no
intervalo de [0, 1] utilizando o gerador congruente linear: X_{k+1} = A * X_{k} mod (2^46),
gerando 2^44 números antes de ocorrer uma repetição.
O componente recebe dois doubles como parâmetros, A e X, onde A é o mesmo A
mencionado na fórmula acima e X é o X_{0} da fórmula acima, portanto chamadas com os
mesmos argumentos produzem uma seqüência contínua.
2.1.2. Protocolo e interface
O componente possui um endereçamento de 24 bytes, sendo os 16 primeiros bytes
para receber os parâmetros (par de doubles). Os últimos 8 bytes são reservados para a
saída do componente, um outro double. O componente funcionará sob demanda, ao
receber um pedido de leitura em seu endereçamento reservado para a saída, ele realizará
as operações sobre os valores nos endereços de entrada e disponibilizará no espaçamento
de saída o resultado.
A implementação em software para a utilização do componente deve ser feita
escrevendo dois doubles nos endereços de entrada da memória do componente e em
seguida lendo um double de seu endereço de saída.
Cada processador terá uma implementação dedicada deste componente para
atender as suas requisições.
2.2. Componente sort
2.2.1. Descrição
Este componente é responsável pela ordenação das chaves internas de cada
bucket. Ao final do algoritmo, uma vez separados os elementos nos buckets, este
componente é responsável por finalizar a ordenação das chaves já separadas. Como cada
bucket pode ser ordenado separadamente, o uso de dois destes componentes permite
divisão do trabalho de ordenação. O algoritmo utilizado para a ordenação das chaves nos
buckets neste componente é o insertion sort.
2.2.2. Protocolo e interface
Este componente tem endereçamento variável em tempo de compilação de maneira
que possa ser ajustado para permitir melhor desempenho. De maneira geral, ele deve
possuir endereço de entrada igual ao numero de chaves de um bucket e endereço de saída
de mesmo tamanho. O processador deve escrever as chaves do bucket no espaço de
entrada do componente e ler o resultado do espaço de saída.
A ordenação é feita através de operações de comparação da mesma maneira que
implementado em software. O objetivo deste componente é reduzir o custo das operações
de ordenação direto em memória, o que é muito custoso.
3. Software
O Software a ser executado na plataforma corresponde a um sistema de ordenação de Inteiros. O
algoritmo de ordenação utilizado é o bucketsort. O sistema em software será responsável por sintetizar o
vetor de entrada, separar os elementos em buckets e reordenar os elementos de cada bucket ao final.
Nenhum elemento do fluxo principal foi abstraído em hardware.
A análise do software através do programa Gprof revelou que a maior consumo de tempo do
algoritmo se encontra no método de geração de números aleatórios. Devido a este fato, este método foi
abstraído em um componente dedicado de hardware na plataforma. As demais operações custosas do
sofware correspondem às operações de manipulação de dados em memória. Pensando em reduzir este
custo, o componente de ordenação de chaves foi criado.
De modo geral, não serão necessárias alterações no fluxo de execução do algoritmo com exceção
dos pontos a serem paralelizados. Estes pontos, porem, apenas necessitam que o fluxo de execução seja
redirecionado para um processador distinto, sem que haja necessidade de alterar o algoritmo.
4. Alocação atividades
A proposta inicial de divisão de atividades para este trabalho fé atribuir o desenvolvimento de cada
um dos componentes a um membro do grupo, sendo o terceiro membro responsável por adaptar o software
IS à plataforma. Previamente ao temido do desenvolvimento dos componentes, este mesmo membro do
grupo deve ser responsável por estruturar a plataforma de maneira a acomodar os novos componentes
desenvolvidos.