Introdução

Este documento tem o objetivo de apresentar a arquitetura do modelo de threads conhecida por Nano-Threads. Este modelo é baseado em tecnologia disponibilizada pelo compilador utilizado visando obter um modelo bastante otimizado para aplicações com diferentes graus de granularidade. Além de combinar tecnologia a nível de compilador e também a nível de kernel, outras características que distinguem este modelo incluem a capacidade de adaptar o nível de granulosidade durante a execução do programa, levando em conta parâmetros do próprio processo e também parâmetros do sistema. Devido a esta característica, os programas que utilizam Nano-Threads não são afetados pela configuração do hardware pois eles se adaptam a configuração subjacente. Outra característica importante deste modelo é que ele disponibiliza uma maneira coordenada e controlada de comunicação entre os escalonadores a nível de usuário e a nível de kernel.

Arquitetura do Modelo

A organização geral da aquitetura do modelo Nano-Threads é mostrada na Figura 1. No nível 1 do modelo encontra-se o kernel do sistema operacional e no nível 2 encontra-se o compilador. Neste modelo o kernel (nível 1) tem controle sobre todos os recursos de hardware, conhecimento do estado de alocação dos processadores e da memória entre os processos ativos. Este nível possui conhecimento a respeito da carga de trabalho populacional, bem como dos atributos de cada processo que são visíveis pelo kernel ou inferidos através do monitoramento do histórico de execução. Neste nível nenhuma predição a respeito do tamanho e do perfil de paralelismo de um processo pode ser feito sem alguma entrada fornecida ou pelo usuário ou pelo próprio compilador. Com posse das informações a respeito da quantidade de processos, tipo dos processos e as suas prioridades o kernel decide como compartilhar o espaço (numero de processadores) e o tempo (quantum) entre os processos ativos. Este compartilhamento, ou distribuição dos recursos entre os processos é "fixo" somente enquanto a carga de trabalho permanece inalterada. Havendo a chegada de um novo processo ou o término da execução de um processo, uma nova "distribuição" dos recursos é executada de maneira totalmente distribuída.

O objetivo desta sistemática é realizar a redistribuição de maneira a não revocar todas as alocações feitas mantendo o overhead o mais baixo possível. Isto é obtido através da reflexão das mudanças ocorridas em todos os processos que estão na fila esperando para serem executados.

O modelo de Nano-Threads, mostrado na Figura 1 consiste dos seguintes componentes:

O kernel possui uma fila lógica na qual todos os processos aptos a execução são enfileirados. Nesta fila cada processo é representado por uma entrada, independente do seu grau de paralelismo. Estes processos são alocados aos processadores disponíveis seguindo uma política round-robin .

No modelo Nano-Threads as threads são locais aos processos e invisíveis para o kernel. Um processo apto a execução envia uma requisição ao kernel indicando o número máximo de processadores que ele deseja utilizar. Dentro deste contexto é o kernel quem decide quantos processadores alocar a este processo e também o time quantum deste processo para cada processador que ele recebeu. Um processador quando alocado a um processo é gerenciado somente por código a nível de usuário, enquanto durar o time quantum do processo. Cada processo é composto por uma lista de threads e duas filas lógicas utilizadas para gerenciar a execução: a ready queue e a suspended queue. Processos executam threads contidas em sua fila (ready queue) seguindo a política citada acima até que um dos seguintes eventos ocorra:

Quando um evento do tipo 2,3 ou em alguns casos 4 ocorrer o processador retorna para o modo de execução protegido (kernel mode). No caso de uma interrupção de relógio, somente o processador em questão retorna para o modo de execução protegido. Ou outros processadores (se existirem) continuam a executar normalmente. Threads suspendidas podem estar ou no estado ready suspended ou no estado blocked suspended. Threads no estado ready suspended são enfileiradas na fila ready enquanto que threads no estado block suspended são enfileiradas na fila blocked. Cada thread possui código necessário para a instanciação e enfileiramento das threads dependentes dela. Seja esta dependência de dados ou de controle. Desra maneira as regras de criação e execução das threads são resolvidas em tempo de compilação.

Conceitos Básicos

O modelo de programação Nano-Threads, cuja arquitetura foi apresentada anteriormente, a fim de provêr threads que se adaptam de maneira dinâmica a configuração de hardware subjacente, utiliza-se de código gerado pelo compilador. Sendo assim é o compilador quem identifica o máximo paralelismo contido na aplicação através de uma análise de dependência tanto de dados quanto de controle. Através desta análise um grafo representando as dependências encontradas é gerado.

É a partir deste grafo, chamado de grafo hierárquico de tarefas (Hierarchical Task Graph - HTG) que o compilador gera código paralelo utilizando os serviços disponibilizados pela biblioteca que implementa este modelo. É durante o processo de geração de código que o compilador determina de maneira estática a melhor granularidade das tarefas paralelas a serem exploradas.

Grafo Herarquico de Tarefas - HTG

O grafo hierárquico de tarefas (HTG) é um grafo que contém nodos simples e nodos compostos. Nodos simples são nodos que contém um conjunto de operações que necessitam ser executadas sequencialmente ou que não possuem trabalho suficiente para ser executado em paralelo. Nodos compostos contém computações mais complexas e desta maneira encapsulam um novo nível na hierarquia. Eles são compostos por outros nodos simples ou compostos. Nodos compostos geralmente encapsulam laços e blocos complexos de código que contem instruções paralelas. Eles possuem dois nodos de controle chamados respectivamente de start e stop. O nodo start é o ponto de entrada para o nodo e é ele quem gerencia a execução dos nodos internos. O nodo stop é o ponto de saída do nodo composto e é ele quem sinaliza aos nodos sucessores do grafo o final da execução deste nodo composto. Nodos que encontram-se no mesmo nível da hierarquia no HTG são conectados por arestas caso exista alguma dependência de dados ou de controle entre eles. Uma dependência de dados entre um nodo y e um nodo x ocorrem quando ambos acessam ao mesmo dado e pelo menos um deles modifica este dado. Uma dependência de controle acontece quando, por exemplo, a execução do nodo y depende da execução do nodo x. Estas depenências impõem uma ordem parcial na execução dos nodos do grafo.

A Figura 2 demonstra um programa e o grafo correspondente gerado pelo compilador. O grafo possui três níveis de nodos. No nível mais externo encontra-se um nodo composto representando o programa inteiro. No próximo nível os nodos PROGRAM e END representam respectivamente os nodos start e stop do nodo. Dentro deste nodo encontra-se mais quatro nodos compostos representando as chamadas de funcção z(),g(), h() e o laço DO. O nodo representando o laço contém três nodos simples (representando os operadores de atribuição aos vetores A e B e a avaliação da condição da chamada IF) e três nodos compostos (representando os blocos de código associados as clausulas THEN e ELSE bem como a chamada da função f). Dependências são representadas por arestas, onde as arestas sólidas representam as dependências de dados e as arestas tracejadas representam as dependências de controle.

Como pode ser visto no grafo da Figura 2, o nodo representando a função h é dependente dos dados dos nodos representado a chamada de função z e o laço DO. Este nodo também possui dependência de controle do nodo PROGRAM. Da mesma maneira os nodos THEN e ELSE são dependentes do nodo IF.

Dentro deste contexto uma tarefa é definida como uma coleção de nodos do grafo que estão no mesmo nível da hierarquia e que possuem granularidade suficiente para serem executados como uma thread a nível de usuário. Esta decião fica a cargo do compilador que encontra o melhor nível de granularidade baseado no overhead necessário para a criação e gerenciamento destas threads. Na Figura 2 uma tarefa foi criada para os nodos A, B e f(). As dependências no grafo representam as relações de precedência entre as tarefas correspondentes. Estas relações estabelecem uma relação sucessor/predecessor entre as tarefas e devem ser preservadas durante a execução paralela. O compilador gera uma função para cada tarefa do grafo de modo que o programa resultante pode ser visto como uma representação (na forma de um programa executável) do grafo.

A execução do programa paralelo consiste na execução das funções associadas as tarefas do grafo, respeitando-se as precedências pré-definidas. Desta maneira, uma função é executada somente quando todas as funções as quais ela depende ja tiverem executado. Sendo assim uma nano-thread corresponde a intanciação de uma tarefa do grafo na forma de um fluxo de execução independente a nível de usuário. Uma tarefa pode ser instanciada como uma nano-thread quando pelo menos uma de suas dependências de controle foi resolvida devido ao término de uma tarefa predecessora. O ambiente de execução, a nível de usuário, permite que nano-threads instanciem as tarefas necessárias como threads a nível de usuário. Sendo assim uma nano-thread instancia uma ou mais tarefas dependendo do seu nível na hierarquia e da disponibilidade de processadores. Desta maneira uma nano-thread pode executar diversas tarefas de maneira sequencial devido a falta de processadores disponíveis. Uma nano-thread quando instanciada pode não estar apta a execução devido alguma dependència não resolvida. No momento em que todas as dependências são resolvidas a nano-thread é inserida na ready queue disponibilizada pelo ambiente de execução. É nesta fila que todas as nano-threads aptas a execução ficam aguardando para serem executadas por algum processador.

A execução do programa inicia com a preparação do nodo principal sendo inserido na ready queue como uma nano-thread. A execução de um nodo composto, que é visto como candidato a criar um novo paralelismo, inicia no seu nodo start. A função gerada para este nodo fica encarregada do escalonamento a nível de aplicação das tarefas contidas no nodo. Esta função avalia em tempo de execução a disponibilidade de recursos e o paralelismo que pode ser gerado baseado nas dependências de suas tarefas internas. Com base nestas informações a decisão da criação de novas nano-threads para execução das tarefas internas é tomada. A função stop de um nodo composto possui duas funções:

Implementação do Ambiente de Execução

A implementação descrita a seguir é baseada no trabalho desenvolvido em [2]. Nesta implementação a execução do código associado a cada nodo do grafo HTG é auxiliada por uma biblioteca de rotinas que agrupa os serviços necessários para os pontos de entrada e saída de cada nodo (nodos start e stop). Os principais serviços disponibilizados pela biblioteca são os seguintes:

Visando obter simplicidade no gerenciamento das nano-threads e consequentemente uma melhor eficiência na execução desta biblioteca, a estrutura de uma nano-thread foi implementada de maneira fixa. Esta estrutura, mostrada na Figura 3, contém todas as informações necessárias a uma nano-thread, incluindo seu espaço de endereçamento.

Como demonstrado na Figura 3, a estrutura de uma nano-thread é composta de duas partes: o descritor na nano-thread e a pilha da nano-thread. Em um primeiro instante esta estrutura é alocada utilzando serviços disponibilizados pelo sistema operacional e posteriormente não é mais desalocada. Ela fica sendo reutilizada para a criação de novas nano-threads, diminuindo assim o overhead necessário. Adicionalmente, as políticas de escalonamento a nível de usuário ajudam a manter o número de estruturas alocadas a fim de reduzir a quantidade de memória alocada para elas. O tamanho desta estrutura normalmente é múltiplo do tamanho da página física de memória. Esta estrutura é inicializada no momento da criação da nano-thread, modificada por outros serviços disponíveis na biblioteca e liberada quando a função associada ao nodo correspondente a esta nano-thread retornar. Nano-threads são identificadas por um ponteiro que referencia o descritor da nano-thread. O conteúdo do descritor de uma nano-thread é mostrado abaixo.

			typedef volatile int spint_t;
			
			struct nth_desc{
				struct nth_desc* next;
				void* sp;
				int ndep;
				spin_t mutex;
				struct nth_desc* sucessor;
			};
			

Onde o ponteiro next aponta para a próxima nano-thread na ready queue. O ponteiro sp armazena o stack pointer quando a nano-thread não está no estado ativo. O campo ndep armazena a quantidade de dependência de dados existentes nesta nano-thread. A variável mutex é utilizada para modificar de maneira atômica este valor. O ponteiro sucessor aponta para a próxima nano-thread que depende dos dados modificados por esta nano-thread.

Criação de Nano-threads

Quando a aplicação em execução chega a um ponto em que todas as dependências de controle para um dado nodo estão resolvidas e ela resolve executar em paralelo, a instanciação (criação) da nano-thread representando este nodo é executada. Esta criação é feita através da seguinte função:

	struct nth_desc* nth_create(void (*routine)(), int ndep,
		struct nth_desc* sucessor, int narg,...);
	

Esta função recicla (ou aloca) a estrutura representando uma nano-thread, constrói o seu descritor e prepara a sua pilha. O número de dependências é incializado levando-se em conta as dependências que ainda não foram resolvidas para que esta nano-thread execute. Além destes também são inicializados o ponteiro para a nano-thread sucessora e os argumentos que a rotina associada deve receber. A pilha desta nano-thread é inicializada com os argumentos que q rotina criada deve receber. Os valores dos parâmetros da função associada e esta nano-thread devem ser conhecidos no momento da criação desta nano-thread.

Resolução de Dependências

Dependências de entrada são armazenadas na forma de um contador no descritor na nano-thread. Quando uma nano-thread avalia um dado e este resolve uma dependência em outra nano-thread a primeira nano-thread envia uma mensagem a segunda nano-thread através da seguinte função:

		int nth_depsatisfy(struct nth_desc* nth);
			

O número de dependências existente na nano-thread apontada por nth é decrementado de maneira atômica, e caso ele seja zero a função retorna true, caso contrário retorna false. Ao retornar true, a nano-thread que executou a chamada fica responsável de enfileirar a nano-thread nth na fila ready queue.

Adição de Dependências

Mesmo depois da criação de uma nano-thread é possível acrescentar dinâmicamente dependências de dados através da seguinte função:

		void nth_depadd (struct nth_desc* nth, int ndep);
			

O número de dependências é incrementado de maneira atômica.

Auto identificação

Tanto a nível de programa quanto a nível de biblioteca, muitas vezes se faz necessário identificar a nano-thread que está sendo executada. Esta informação é obtida através da seguinte função

		struct nth_desc* nth_self ();
			

Ela retorna um ponteiro para o descritor da nano-thread em execução.

Gerenciamento de Fila

Funções específicas são utilizadas para gerenciar a ready queue. Elas são utilizadas para manter uma lista de nano-threads prontas para serem executadas e também para obtenção do número de nano-threads aguardando na lista.

		void nth_to_rq (struct nth_desc * nth);
			

Insere a nano-thread apontada por nth no início da ready queue.

		void nth_to_rq_end (struct nth_desc * nth);
			

Insere a nano-thread apontada por nth no final da ready queue.

		int nth_nths_in_rq;
			

Esta variável contém o número de nano-threads que estão aguardando na ready queue. Ela é utilizada como parâmetro no escalonamento a nível de usuário.

Bloqueando Nano-threads

Esta função faz com que a nano-thread que a execute bloqueie esperando o paralelismo que ela criou termine. Ao ser chamada esta função cria mais um nodo no grafo que herda o espaço de endereçamento do nodo atual e que depende do paralelismo criado anteriormente. A execução do novo nodo inicia logo após a chamada desta função.

		void nth_block();
			

Internamente o número de dependências desta nano-thread é incrementado e ela espera (perde o processador) até que ele chegue a zero.

Ferramenta

Esta seção demonstra a instalação e donfiguração do compilador NANOS Mercurium. Este compilador utiliza diretivas OpenMP [4] para gerar código paralelo para a aplicação. Utilizando um sistema de tradução source to source baseado em templates, este compilador utiliza a implementação da biblioteca nano-threads descrita anteriormente. A seguir serão apresentados os procedimentos de instalação e compilação Maiores informações sobre este compilador podem ser obtidas em [3].

Procediemntos de Instalacao

Nesta seção serão apresentados os procedimentos de instalação do compilador NANOS Mercurium. O processo de instalação descrito a seguir se refere a versão binária do compilador. Existe também a opção da instalação a partir do código fonte.

A distribuição binária do compilador NANOS Mercurium é distribuída na forma de um arquivo compactado com a extensão .tar.gz . O nome do arquivo é da seguinte forma:

		mcc-bin-V.tar.gz
			

Onde V é a versão atual do compilador. Atualmente a versão corrente é a 0.3. Para completar a instalação é necessário efetuar o download de uma distribuição template utilizada na geração de código. Esta distribuição também é destribuída na forma de um arquivo compactado com a extensão .tar.gz . O nomde deste arquivo é da seguinte forma:

		mcc-LIBRARY-ARCH-templates.tar.gz

Onde LIBRARY é a biblioteca OpenMP para a qual o compilador NANOS Mercurium gera código. Atualmente a única biblioteca disponível é a NthLib (nano-threads) e ARCH é a arquitetura alvo. Atualmente somente i686.

Para instalar o compilador NANOS Mercurium os seguintes passos devem ser seguidos:

  1. Selecione o diretório de instalação e descompacte o arquivo extraindo todo o seu conteúdo neste diretório.
    					
    	$ cd ~
    	$ gunzip < mcc-bin-V.tar.gz | tar xvf -
    					

    Neste ponto a seguinte estrutura de diretórios estará criada:

    	~mcc --> Diretório de instalação do compilador
    		\_ config.ex		-->Exemplo de um arquivo de configuração para o compilador
    		\_libraries		-->Diretório vazio onde deve ser instalada a distribuição template
    		\_mcc			-->Compilador NANOS Mercurium
    		\_mcc-config.sh		-->Script utilizado para criar os arquivos de configuração do compilador
    					
  2. Dentro do diretório onde foi realizada a instalação do compilador, o aqrquivo contendo os templates deve ser descompactado. Este arquivo descompacta seu conteúdo dentro do diretório libraries por padrão
    	$ cd ~/mcc
       $ gunzip mcc-LIBRARY-ARCH-templates.tar.gz | tar xvf -
    					
    Neste ponto a seguinte estrutura de diretórios estará criada:
    			
    	\_ libraries
    		\_nanos - Nthlib (NANOS) distribuição template
    			\_ config.ex - exemplo de arquivo de configuração para a distribuição template
    			\_ includes\* - arquivos include (.h) para a distribuição template
    			\_ templates\* - arquivos contendo os templates utilizados na geração de código
    
    			
  3. Crie o arquivo de configuração utilizando para isto o script mcc-config.sh
    	
    		gustavo@lermen:~/mcc ./mcc-config.sh
    		What library you want to compile for?[nanos]
    		nanos
    		Where is nanos library installed?[]
    		~/nanos      -------------- diretório onde a biblioteca nthlib foi instalada
    		Configuration:
    		=====================================================
    		Compiler used:          gcc
    		Preprocessor flags:     -std=c99
    		Compiler flags:         -std=c99
    		Templates used:         nanos
    		Path to nanos library   /home/jbalart/nanos
    		Press enter to generate configuration
    			
    		O sscript irá criar os seguintes arquivos:
    			
    		~/mcc/config
    		~/mcc/config/libraries/nanos/config
    		
  4. Adicione o diretório do compilador na variável de ambiente PATH (dependendo do tipo de shell):
     
    		export PATH=~/mcc:$PATH
    		ou
    		setenv PATH ~/mcc:$PATH
    			

Instalação da biblioteca NANOS

Para instalar a biblioteca NANOS os seguintes passos devem ser tomados:

  1. Declare as seguintes variáveis em algum script de inicialização (para uma instalação no diretório ~/nanos:
    alias $=
    $ export NNTH_HOME=~/nanos
    $ export NANOS_HOME=${NNTH_HOME}/local
    $ export LD_LIBRARY_PATH=${NNTH_HOME}/local/lib
    unalias $
    			
  2. Descompacte o arquivo:
    		
    $ gunzip <  nanos-bin-dynamic.tar.gz | tar xf -
    			

Exemplo de uso

Nesta seção será apresentado um exemplo simples de uso do compilador NANOS Mercurium.

//Arquivo teste.c
#include "stdio.h"
int MATRIX_SIZE=10;
void initialize(int m[MATRIX_SIZE][MATRIX_SIZE]);
void main(void)
{
	int matriz[MATRIX_SIZE][MATRIX_SIZE];
	int i,j;
	initialize(matriz);
	#pragma omp parallel
        {
		#pragma omp sections
		{
			for (i = 0; i  MATRIX_SIZE; i++){
				#pragma omp section
				{
				    for (j=0;j MATRIX_SIZE;j++){
					matriz[i][j] = matriz[i][j] + j;
					printf(" %d",matriz[i][j]);
				    }
				    printf("\n");
				}

			}

		}
	}
}

void initialize(int m[MATRIX_SIZE][MATRIX_SIZE])
{
	int i,j;
	for (i = 0; i  MATRIX_SIZE; i++){
		for (j = 0; j  MATRIX_SIZE; j++){
			m[i][j] = 0;
		}
	}
}

Para compilar o programa acima (assumindo que o nome do arquivo é teste.c) deve-se utilizar o seguinte comando:

mcc teste.c -L $LD_LIBRARY_PATH -lnthmain -lnthreads -lintone   -o teste
			

Referências