Introdução

Athapascan-1 é uma biblioteca C++ para programação paralela multi-thread. Ela é implementada como uma macro linguagem de fluxo de dados: ambas, a computação e os dados têm granularidade explicitamente definidos. Em Athapascan-1 a semântica do acesso compartilhado de memória é baseado na ordem lexicográfica. Uma característica importante é o fato de Athapascan ser assíncrono, com isso é possível fazer uma eficiente analise "on-line" do fluxo de dados que descreve a execução. Assim é possível a criação de novos algoritmos de escalonamento baseados no conhecimento prévio da estrutura do grafo do fluxo de execução.

A seguir é apresentado o KAAPI, que á uma biblioteca C++ que fornece uma série de funcionalidades para o Athapascan-1(não vou falar mais, senão não terei o que falar na seção ...). Na seção seguinte é abordada a biblioteca Athapascan-1, sua sintaxe, memória compartilhada e consistência dessa, bem como o modelo de sincronização, já que Athapascan-1 é uma meta linguagem assíncrona. Nas seções que seguem é apresentado respectivamente, como fazer download e instalar e a apresentação de um exemplo.

KAAPI

KAPPI (Kernel for Adaptative, Asynchronous Parallel and Interactive programming) é uma biblioteca em C++ que permite a execução de multithread com sincronização entre threads. Essa biblioteca permite media/fina granularidade de programas em maquinas distribuídas. O grafo de fluxo de dados é criado e atualizado em tempo de execução.

Projetado para ser usado em clusters de máquinas SMP, a máquina virtual provida por KAAPI apresenta 3 níveis de memória:

As threads de controle é uma seqüência de execução não interruptível, chamada de "task". O balanceamento de carga é baseado no algoritmo de roubo de trabalho, onde as processadores que não possuem mais tarefas roubam dos outros processadores escolhidos randomicamente. KAAPI tem um custo muito pequeno para criar tarefas, sendo por volta de 10 "tempos" para invocar as funções.

Linguagem Athapascan-1

Athapascan-1 é uma linguagem de fluxo de dados projetada para computação paralela. O paralelismo é explícito através de chamadas de função remotas, denominadas Tasks, que se comunicam e são sincronizadas somente pelo acesso a memória compartilhada.

A semântica conferida ao Athapascan-1 garante que um dado só pode ser acessado na memória desde que ele não seja alterado anteriormente. Assim a execução de tarefas paralelas respeitam a ordem Lexicográfica, respeitando a ordem de escrita/leitura na memória. Se uma tarefa depende de um dado que ainda pode ser alterado na memória, ela fica esperando até que esse possível alteração seja feita, mantendo assim a consistência dos dados da memória compartilhada.

A biblioteca Athapascan-1 é implementada em C++ e é compatível com C e C++. É uma extensão do padrão ANSI C, que sofre um pré-processamento e as palavras-chave são convertidas para construções C++.

Quando uma tarefa é definida, é necessário que todas as variáveis de acesso à memória, que serão usadas, sejam parâmetros da função. Baseado nessas informações é possível gerar um grafo de dependências de acesso à memória e fluxo de dados. Esse grafo é gerado em tempo de execução e pode ser alterado a medida que as dependências mudam. Assim como dependências são satisfeitas e tarefas finalizadas, novas tarefas podem ser criadas e dependências com estas.

O acesso à memória compartilhada é feito pela declaração de variáveis do tipo Share. O acesso pode ser de leitura, leitura/escrita, escrita ou acumulativa escrita, dependendo da necessidade de acesso ao dados. Não convém usar sempre leitura/escrita, já que na geração do grafo de dependências isso gerará uma dependência que não existiria se fosse usado somente leitura. Uma tarefa, quando na geração de outra tarefa filha, somente pode atribuir permissões de acesso à memória iguais ou menores que as suas.

A definição das tarefas (1) é similar a definição de procedures C, onde task representa uma computação seqüencial que tem granularidade definida pelo programador. A instância de uma tarefa (2) é feita pela palavra reservada fork, e com isso é criado um objeto chamado de closure, que é uma estrutura de dados que contém a instância da tarefa e a lista de parâmetros dessa. Caso haja alguma dependência de dados, closure fica no estado de waiting, caso contrário, em estado de ready. O estado de closure está diretamente ligado aos parâmetros de acesso à memória das tarefas.

task user_task(<params>) {<statements>} (1)

fork user_task( <args> ); (2)

Download e instalação

KAAPI e Athapascan-1 apesar de necessitarem ser instalados separadamente, e em ordem, primeiro KAAPI depois Athapascan 1, eles são disponibilizados em um único arquivo para download. Para testes realizados para o desenvolvimento desse tutorial, foi necessário ter permissão de super-usuário para fazer a instalação. Atualmente KAAPI/Athapascan-1 é portado para a maioria das plataformas UNIX. Como pré-requisitos, é necessário POSIX e interface de socket (SysV socket). As redes KAAPI podem ser portadas para diferentes interfaces e protocolos, como redes GM/Myrinet. Uma distribuição especial é fornecida para MacOS X, sendo está simples de instalar, mas requer permissão de administrador. Atualmente KAAPI é para os seguintes sistemas e plataformas:


Architecture
 System
Compiler
Distribution
IA32
Linux
g++3.2.x, 3.3.x
Intel iCC
KAAPI.tgz
Opteron
Linux
g++3.2.x, 3.3.x
KAAPI.tgz
IA64 Itanium
Linux
g++3.2.x, 3.3.x
Intel iCC
KAAPI.tgz
PowerPC
(32 or 64 bits)
MacOSX
10.2, 10.3
10.4
g++ 3.2.x, 3.3.x
XCode project is available
KAAPI.tgz

MIPS,Origin3800 IRIX
g++
avalaible on demand

Durante o desenvolvimento desse material, foi instalado o KAAPI/Athapascan-1 em máquinas rodando linux, distribuição Gentoo. Para a instalação foi necessário permissão de super-usuário.

O pacote com os fontes pode ser obtido nos links da tabela. Para descompactar use o camando abaixo. Dois diretórios serão criados, Kaapi e Athapascan-4, contendo os fontes das referidas bibliotecas. Cada uma das bibliotecas deve ser compilada em um diretório diferente de onde se encontram os fontes. Nas duas seções seguintes a instalação destes.

  # gzip -dc KAAPI.tgz | tar xfv -

Instalando KAAPI

  # mkdir compila
  # mkdir compila/kaapi
  # cd compila/kaapi

Para configurar a biblioteca, é necessário que seja indicado o diretório onde será feita a instalação, sendo que esse diretório é necessário para compilar e rodar os programas KAAPI. Nesse tutorial, a instalação será feita em /usr/local/kaapi, mas pode ser qualquer outro caminho. Assim, o comando fica:

  # ../../Kaapi/configure --prefix=/usr/local/kaapi

O resulatado desse comando é uma longa lista de configurações automáticas de diferentes ferramentas, bibliotecas, funções, ... e determinações do compilador C++. O script de configuração usa o compilador padrão, caso deseje usar outro, as variáveis de ambiente CXX devem ser alteradas antes de rodar o comando de configuração. Se correu tudo bem até aqui, é hora de compilar a biblioteca KAAPI:

  # make

Se compilou certo, para instalar a biblioteca no diretório anteriormente especificado /usr/local/kaapi, basta executar o comando make install:

  # make install

Caso não tenha ocorrido nenhum erro, no diretório onde se encontram os fontes do KAAPI, existe um diretório com exemplos, compile e execute:

  # cd examples
  # make
  # ./fibo1 30 1 15

O exemplo é o calculo do fibonacci de 30, fazendo 1 execução com um threshold de parada recursiva de 15. Os exemplos possuem um help, basta executar o exemplo com a opção --help.

Instalando Athapascan-1

  # mkdir compila/Athapascan
  # cd compila/Athapascan

Criado o diretório, dentro desse deve ser rodado o script de configuração, passando como parametro o diretório de instalação do KAAPI e o diretório onde será instalado o Athapascan. O KAAPI foi instalado em /usr/local/kaapi e o Athapascan será instalado em /usr/local/athapascan:

  # ../../Athapascan-v4/configure --prefix=/usr/local/athapascan \
                                  --with-kaapi=/usr/local/kaapi

Feito isso, é só compilar e instalar:

  # make && make install

No diretório onde foi instalado o Athapascan-1, nesse caso, /usr/local/athapascan, o diretório bin contém os seguintes scripts:

  • bin/atha.sh : define as variáveis de ambiente ATHAPASCAN1_CPPFLAGS, ATHAPASCAN1_LDFLAGS
  • bin/atha.csh : idem para csh e tcsh shells
  • bin/atharun : script para executar os programas Athapascan. Documentação pode ser visualizada usando a opção --help.

Exemplo

Alguns exemplos de Athapascan podem ser vistos em Athapascan-v4/exemplos. Aqui será apresentado o exemplo de Fibonacci.

Fibonacci

#include <athapascan-1>
#include <iostream>

inline double gettime()
{
   struct timeval tmp2 ;
   gettimeofday (&tmp2, 0) ;
   return (double) tmp2.tv_sec + ((double) tmp2.tv_usec) * 1e-6;
}

/* Sequential fibo function
*/
int fiboseq(int n)
{ return (n<2 ? n : fiboseq(n-1)+fiboseq(n-2) ); }

/* Print any typed shared
*/
template<class T>
struct Print {
  void operator() ( a1::Shared_r<T> a, double t )
  {
    static double shift = 0;
    double delay = gettime() - t;
    std::cout << a1::System::getRank()
              << ": -----------------------------------------" << std::endl;
    std::cout << a1::System::getRank()
              << ": res  = " << a.read() << std::endl;
    std::cout << a1::System::getRank()
              << ": time = " << delay-shift << " s" << std::endl;
    std::cout << a1::System::getRank()
              << ": -----------------------------------------" << std::endl;
    shift = delay;
  }
};

/* Sum two integers
*/
struct Sum {
  void operator() ( a1::Shared_w<unsigned long long> res,
                    a1::Shared_r<unsigned long long> a,
                    a1::Shared_r<unsigned long long> b)
  {
    res.write(a.read()+b.read());
  }
};

/* Athapascan Fibo function
*/
struct Fibo {
  void operator() ( a1::Shared_w<unsigned long long> res, int n, int seuil )
  {
    if (n < seuil) {
      res.write( (unsigned long long)fiboseq(n) );
    }
    else {
      a1::Shared<unsigned long long> res1;
      a1::Shared<unsigned long long> res2;
      a1::Fork<Fibo>() ( res1, n-1, seuil );
      a1::Fork<Fibo>() ( res2, n-2, seuil );
      a1::Fork<Sum>()  ( res, res1, res2 );
    }
  }
};

/* Main of the program
*/
struct doit {

  void do_experiment(int i, int n, int seuil )
  {
    double t = gettime();
    a1::Shared<unsigned long long> res(31415);
    a1::Fork<Fibo>()(res,n,seuil);
    a1::Fork<Print<unsigned long long> >(a1::SetLocal)(res,t);
  }

  void operator()(int argc, char** argv )
  {
    int n = atoi(argv[1]);
    int seuil = atoi(argv[2]);
    if (seuil <2) seuil =2;
    std::cout << a1::System::getRank() << ":In main: seuil = "

              << seuil << ", Fibo: " << n << "="  << std::endl;

    int niter = atoi(argv[3]);
    for (int i=0; i < niter; ++i)
    {
      do_experiment( i, n, seuil );
    }
  }
};

/* main entry point : Athapascan initialization
*/
int main(int argc, char** argv)
{
  try {
    /* Join the initial group of computation : it is defining

       when launching the program by a1run.
    */
    a1::Community com = a1::System::join_community( argc, argv );

    /* Start computation by forking the main task */
    a1::ForkMain<doit>()(argc, argv);

    /* Leave the community: at return to this call no more athapascan
       tasks or shared could be created.

    */
    com.leave();
  }
  catch (const a1::InvalidArgument& E) {
    std::cout << "Catch invalid arg" << std::endl;
  }
  catch (const a1::BadAlloc& E) {
    std::cout << "Catch bad alloc" << std::endl;
  }
  catch (const a1::Exception& E) {
    std::cout << "Catch : "; E.print(std::cout); std::cout << std::endl;
  }
  catch (...) {
    std::cout << "Catch unknown exception: " << std::endl;
  }

  return 0;
}

Para compilar e executar vá para o diretório Athapascan-v4/exemplos e siga os passos:

  • Compilação:
  # make fibo1
  • Listar as opções:
  # ./fibo1 --help
  • Rodando o exemplo:
* maquina SMP usando 6 (Kaapi-processors) threads
   # atharun -th 6  fibo1 30 10 1
* maquina SMP usando 6 processos UNIX
   # atharun -np 6  fibo1 30 10 1
* cluster usando 6 processos UNIX em diferentes nodos
  listados no arquivo hostfile
   # atharun -np 6 -f hostfile fibo1 30 10 1
   - O arquivo hostfile contém em cada linha o nome de um host
	  nodo01
	  nodo02
	  nodo03
	  nodo04
* cluster usando 6 processos UNIX em diferentes nodos com 2
  Kaapi-processors por processo
   # atharun -np 6 -th 2 -f hostfile fibo1 30 10 1

Os processos são "espalhados" para as máquinas usando rsh ou ssh. Por padrão, KAAPI vem com ssh habilitado, sendo que para alterar isso deve-se mudar o valor da variável de ambiente KAAPI_RSH para 'rsh' ou 'ssh'

Referências

Os dados contidos nessa página estão presentes na seção de downloads e na seção de publicações do site do KAAPI. http://www-id.imag.fr/Laboratoire/Membres/Gautier_Thierry/KAAPI/ . Segundo Thierry Gautier, um dos participantes do projeto, o site do projeto está sendo migrado para https://gforge.inria.fr/projects/kaapi

Os slides desse material podem ser obtidos aqui