Introdução

Este tutorial apresenta, de forma sintetizada, uma introdução sobre a linguagem de programação Unified Parallel C (UPC), focando na instalação de um compilador para a linguagem, execução de aplicações e em exemplos de códigos com caráter ilustrativo.

Linguagem de Programação UPC

Unified Parallel C é uma extensão da conhecida linguagem de programação C, e foi projetada para o uso em processamento de alto desempenho em máquinas Symmetric Multi-Processors (SMP) e em agregados de computadores (conhecidos simplesmente por clusters). A linguagem provê um modelo de programação uniforme para ambas as arquiteturas. Ao programador é apresentada uma única memória, compartilhada, num espaço de endereçamento particionado, onde as variáveis podem ser tanto lidas como escritas por qualquer processador, embora fisicamente estejam associadas a um único. UPC faz uso do modelo de computação Single Program Multiple Data (SPMD), onde um único programa é escrito e instanciado em cada nodo do computador paralelo e, desta forma, cada programa roda independentemente.

Modelo de Execução

O modelo de execução utilizado por UPC é similar ao utilizado por linguagens baseadas em mensagens, tais como Message Passing Interface (MPI) e Parallel Virtual Machine (PVM). Este modelo é denominado Single Program Multiple Data (SPMD) e é um modelo explicitamente paralelo. No caso especial de UPC, o veículo de execução do programa é definido como thread. A linguagem introduz uma variável privada definida como MYTHREAD, que pode ser utilizada para diferenciar cada thread UPC em execução, uma vezque UPC executa de forma independente cada uma destas threads.

A linguagem não define qualquer correspondente entre threads UPC e de sistema, desta forma threads UPC podem ser implementadas tanto como processos do Sistema Operacional ou threads (de usuário ou em nível de kernel). E um sistema paralelo um programa UPC em execução com dados compartilhados contém, necessariamente, pelo menos uma thread UPC por processador físico disponível.

Na página do GNU UPC, na página referente ao compilador para a arquitetura x86 é descrito o modelo implementado: cada thread UPC é criada como um processo no sistema operacinal. Segue o texto do site:

"An operating system process is created for each UPC thread. Therefore, the maximum number of supported threads is further constrained by system capacity limitations, such as available swap space and process load. Typically, a UPC program will fail with the diagnostic "UPC initialization failed. Reason: Resource temporarily unavailable, if there are insufficient system resources to create the requested number of threads."

Para representar a concorrência da aplicação em número de threads UPC, a linguagem introduz uma outra variável privada, THREADS. O valor atribuído a esta pode ser feita de duas formas distintas. A primeira é em tempo de compilação, útil quando se conhece a concorrência da aplicação a priori, ou em tempo de execução, que permite ao usuário informar por linha de comando o número de threads, por exemplo, ou deixar que o próprio programa faça suas escolhas.

Memória Compartilhada

UPC faz distinção entre os dados disponíveis por uma thread. A diferenciação é feita entre dados privados e compartilhados. Essa distinção é explicitada com o uso de um novo tipo de variável, shared. Todo dado declarado como shared estará disponível por todas as threads do programa UPC.

A linguagem define, também, associações físicas entre os dados compartilhados e threads UPC. Essas associações, definidas como affinity, indicam que um dado em particular pertence a uma thread específica. Do ponto de vista de implementação, affinity traduz dados compartilhados em memória física enquanto a thread UPC está em execução.

Quando é definida uma affinity, a linguagem permite a distinção de dados entre escalares e vetorias. Todos os dados escalares (tipos definidos pela linguagem C, ponteiros ou tipos definidos pelo usuário) tem afinidade com a thread 0 (zero). Para vetores, a linguagem permite três formas de afinidade, que devem ser selecionadas de acordo com a estratégia que será utilizada de acordo com a implementação.

Cíclica por elementos
Elementos sucessivos de um vetor têm afinidade com sucessivas threads, como mostra a figura abaixo.
Thread 0 Thread 1 Thread 2 Thread 3
x[0] x[1] x[2] x[3]
x[4] x[5] x[6] x[7]
x[8] x[9] x[10] x[11]
z

Cíclica por blocos (definido pelo usuário)
O vetor é dividido em blocos definidos pelo usuário e os blocos são distribuídos de forma cíclica entre as threads, como mostra a próxima figura.
Thread 0 Thread 1 Thread 2
x[0] x[3] x[6]
x[1] x[4] x[7]
x[2] x[5] x[8]
x[9]
x[10]
x[11]

Blocos (em tempo de execução)
Cada thread tem afinidade com as partes contíguas do vetor. O tamanho da parte contígua é determinado quando as partes são distribuídas entre as threads.

Primitivas de Sincronização

UPC não faz uso implícito de interações entre thread. Toda interação é explicamente manuseada pelo programador através de primitivas que a linguagem apresenta: locks, barriers, memory fences.

Consistência da Memória

Para definir a interação entre acessos a memória para dados compartilhados, UPC provê dois controles de consistência de memória que são manuseados pelo usuário. Cada referência a memória em um prorama, pode ser expressocomo strict ou relaxed.

Download e instalação

Embora existam diversos compiladores para Unified Parallel C, entre eles alguns comerciais, foi escolhido o compilador GCC Unified Parallel C, como toolset de compilação e execução.

Os arquivos para download estão disponíveis na página de downloads do próprio site, sendo possível escolher entre diversas arquiteturas. Entre elas:

A instalação escolhida foi na arquitetura x86, porém a página oficial oferece os pacotes de instação (binários) para RedHat. A instalação para este texto foi feita em uma máquina executando Gentoo Linux e, desta forma, foi feito o download do código fonte para posterior compilação.

Até a data deste texto, a versão disponível para download era a 3.4.4.1, sendo o download do source ser feito através do terminal com o comando:

$ wget ftp://ftp.intrepid.com/pub/upc/rls/upc-3.4.4.1/upc-3.4.4.1.src.tar.gz

Feito o download do arquivo, deve-se descompartar a ferramenta, o que pode ser feito com o comando:

$ tar -zxvf upc-3.4.4.1.src.tar.gz

Com a ajuda do comando ls -l é possível perceber que foi criado um diretório após a extração do arquivo. Deve-se entrar no diretório para efetura a compiltação:

$ cd upc-3.4.4.1

O próximo passo é escolher um local adequado para a instalação. Este local de instalação está diretamente ligado aos privilégios do usuário no ambiente linux em questão. Usuários sem acesso a conta de superusuários devem estabelecer um caminho para a instalação de aplicativos, ao contrário do administrador, que pode instalar diretamente na árvore do sistema.

Será aborada a instalação por um usuário sem permissão de super-usuário, que deseja instalar o compilador em um diretório localizado em /work/UPC. Deve-se certificar de que o diretório existe. Caso negativo deve ser criado:

$ mkdir -p /work/UPC

E então - no diretório upc-3.4.4.1 - setar a configuração para a compilação:

$ ./configure --prefix=/work/UPC

Ao final desta configuração não devem haver erros. Se algum for detectado, há alguma falha nas dependências necessárias para prosseguir, e devem ser reavaliadas.

É feita, então, a compilação da ferramenta:

$ make

Novamente se não surgirem imprevistos durante o processo, pode ser feita a instalação no local especificado:

$ make install

Como resultado, os arquivos são criados e instalados no sistema. É possível encontrar no diretório /work/UPC/bin/ os seguintes arquivos;

-rwxr-xr-x  1 user 326K Nov 21 18:19 cpp
-rwxr-xr-x  3 user 325K Nov 21 18:19 gcc
-rwxr-xr-x  1 user  16K Nov 21 18:19 gccbug
-rwxr-xr-x  1 user 112K Nov 21 18:19 gcov
-rwxr-xr-x  3 user 325K Nov 21 18:19 i686-pc-linux-gnu-gcc
-rwxr-xr-x  1 user  64K Nov 21 18:19 upc
-rwxr-xr-x  3 user 325K Nov 21 18:19 i686-pc-linux-gnu-gcc-3.4.4

E na pasta /work/UPC/lib os arquivos:

drwxr-xr-x  3 user 4.0K Nov 21 18:19 gcc/
-rw-r--r--  1 user 161K Nov 21 18:19 libgcc_s.so.1
-rw-r--r--  1 user 410K Nov 21 18:19 libiberty.a
-rw-r--r--  1 user  80K Nov 21 18:19 libupc.a
-rw-r--r--  1 user  81K Nov 21 18:19 libupc_pt.a
-rwxr-xr-x  1 user  722 Nov 21 18:19 libupc.la*
-rwxr-xr-x  1 user  731 Nov 21 18:19 libupc_pt.la*
lrwxrwxrwx  1 user   13 Nov 21 18:19 libgcc_s.so -> libgcc_s.so.1

É útil setar no arquivo .bashrc localizado no $HOME do usuário as seguintes variáveis de ambiente referentes ao compilador. Basta abrir o arquivo e adicionar as seguintes linhas:

export PATH=$PATH:/work/UPC/bin
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/work/UPC/lib

A ferramenta está pronta para ser utilizada.

Exemplos

A seguir são apresentados alguns programas que ilustram o uso da linguagem, bem como são apresentadas algumas características e instruções oferecidas por ela.

Primeiro Exemplo (MYTHREAD e THREADS)

O primeiro exemplo se refere a uma simples aplicação que resume a idéia de Um programa, múltiplos dados. Neste caso um programa com uma simples função de impressão é chamado por cada uma das threads UPC em execução, gerando uma saída estocástica como mostrada na seqüência

#include <stdio.h>

int main(int ac, char **av)
{

	printf("Ola' em %d de %d!\n", MYTHREAD, THREADS);

	return 0;
}

$ upc PrimeiroExemplo.upc -o primeiro
$ ./primeiro -n 10
Ola' em 0 de 10!
Ola' em 1 de 10!
Ola' em 3 de 10!
Ola' em 4 de 10!
Ola' em 5 de 10!
Ola' em 6 de 10!
Ola' em 7 de 10!
Ola' em 8 de 10!
Ola' em 9 de 10!
Ola' em 2 de 10!

Segundo Exemplo (Thread específica)

Este exemplo apresenta diferenciação entre o trabalho de duas threads UPC apenas pelo identificador da thread. Após o código segue a compilação e resultado de execução.

#include <stdio.h>
#include <math.h>

int main(int ac, char **av)
{
	int i;

	if(!MYTHREAD)
		printf("Estou em %d\n", MYTHREAD);
	else {
		printf("Ola' em %d de %d!\n", MYTHREAD, THREADS);
	}

	return 0;
}

$ upc SegundoExemplo.upc -o segundo 
$ ./segundo -n 10
Estou em 0
Ola' em 1 de 10!
Ola' em 3 de 10!
Ola' em 4 de 10!
Ola' em 5 de 10!
Ola' em 6 de 10!
Ola' em 7 de 10!
Ola' em 8 de 10!
Ola' em 2 de 10!
Ola' em 9 de 10!

Terceiro Exemplo (Barrier)

Este exemplo utiliza a estrutura compartilhada shared e faz uso da instrução upc_barrier. Esta instrução é utilizada para que todas as threads sejam sincronizadas antes de continuar a execução. É largamente utilizada quando existe dependência de dados entre as threads.

#include <stdio.h>

shared int a = 0;
int b;

int computation(int temp)
{
	return temp+5;
}

int main()
{
	int result = 0, i = 0;

	do {
		if (!MYTHREAD) {
			result = computation(a);
			a = result * THREADS;
		}

		upc_barrier;

		b = a;

		printf("THREAD %d: b = %d\n", MYTHREAD, b);

		i++;

	} while (i < 4);

	return 0;
}

$ upc TerceiroExemplo.upc -o terceiro
$ ./terceiro.upc -n 5 
THREAD 0: b = 25
THREAD 1: b = 150
THREAD 2: b = 150
THREAD 3: b = 150
THREAD 4: b = 150
THREAD 0: b = 150
THREAD 1: b = 775
THREAD 2: b = 775
THREAD 3: b = 775
THREAD 4: b = 775
THREAD 0: b = 775
THREAD 1: b = 3900
THREAD 2: b = 3900
THREAD 3: b = 3900
THREAD 4: b = 3900
THREAD 0: b = 3900
THREAD 1: b = 3900
THREAD 2: b = 3900
THREAD 3: b = 3900
THREAD 4: b = 3900

Embora o código do programa esteja limitado dentro do bloco main(), apenas a primeira thread é capaz de executar a instrução após o comando do, calculando o valor de a. A instrução após esta atribuição é uma barreira upc_barrier, que garante que nenhuma thread irá executar antes do valor de a ser atribuido pela primeira thread. Logo após todas as threads atribuem o valor da variável privada b com o valor de a.

Sem upc_barrier não há garantia alguma de sincronização.

Quarto Exemplo (Lock/Unlock)

Este exemplo apresenta as instruções upc_lock e upc_unlock, que garantem que um elemento compartilhado não estará acessível por outra thread enquanto não for atualizada pela que executou o lock.

#include <stdio.h>
#include <math.h>

#define N 1000

shared[] int arr[THREADS];

upc_lock_t *lock;

int main ()
{
	int i = 0;

	int index;

	srand(MYTHREAD);

	if (lock = upc_all_lock_alloc() == NULL)
		upc_global_exit(1);
	upc_forall (i = 0; i < N; i++)	{
		index = rand()%THREADS;
		upc_lock(lock);
		arr[index] += 1;
		upc_unlock(lock);
	}
	
	upc_barrier;

	if (MYTHREAD == 0) {
		for (i = 0; i < THREADS; i++)
			printf("TH%2d: # de arr e' %d\n", i, arr[i]);
		upc_lock_free(lock);
	}

	return 0;
}

$ upc QuartoExemplo.upc -lm -o quarto -fupc-threads-10
$ ./quarto   
TH 0: # de arr e' 80
TH 1: # de arr e' 70
TH 2: # de arr e' 120
TH 3: # de arr e' 110
TH 4: # de arr e' 100
TH 5: # de arr e' 90
TH 6: # de arr e' 150
TH 7: # de arr e' 100
TH 8: # de arr e' 70
TH 9: # de arr e' 110

Quinto Exemplo (Cálculo do Pi)

Apenas para ilustrar uma aplicação real, é descrito um quinto exemplo que faz o cálculo do número pi através de uma integração numérica da equação baixo:

O cálculo da área é segmentado entre os processadores e no final de cada passo, é adicionando a variável compartilhada pi.

#include <upc_relaxed.h>
#include <stdio.h>
#include <math.h>

#define N 1000000
#define f(x) (1.0/(1.0 + x*x))

upc_lock_t *l;

shared float pi = 0.0;

int main(int ac, char **av)
{
	float local_pi = 0.0;
	int i;
	l = upc_all_lock_alloc();

	upc_forall(i = 0; i < N; i++; i)
		local_pi += (float) f((0.5 + i)/(N));
	local_pi *= (float) (4.0 / N);

	upc_lock(l);
	pi += local_pi;
	upc_unlock(l);

	upc_barrier;

	if (!MYTHREAD) printf("Pi = %f\n", pi);
	if (!MYTHREAD) upc_lock_free(l);

	return 0;
}

$ upc Pi.upc -lm -o Pi
$ ./Pi -n 10
Pi = 3.141532