readme

          Pontifícia Universidade Católica de Minas Gerais
                       Computação Paralela

Projeto 01 – Implementação Paralela de uma Técnica de Inteligência
                            Artificial

Davidson Francis Gonçalves de Lima
Guilherme David Matias Ferreira
Rama Alvim Sales Schiavo

1) Genann
---------

Genann (https://github.com/codeplea/genann) é uma simples rede neural
de código aberto com suporte a backpropagation escrita em ANSI C.
Consiste apenas de 2 arquivos (genann.c, genann.h) e pode ser facilmen-
te incluída em qualquer projeto.

2) Base de dados
----------------

A base de dados utilizada é a famosa IRIS, que consiste na classifi-
cação de três tipos de plantas Iris (Setosa, Versicolor e Virgínica)
baseado na altura e largura das pétalas e sépalas. Possui 150
instâncias (50 instâncias de cada classe) e 4 atributos de tipo 'real'.

Uma classe é linearmente separável das outras duas, enquanto a última
não é. Portanto, embora pequena, é uma boa base para testes de aprendi-
zado de máquina.

3) Compilação
-------------

O processo de compilação é bem simples, e pode ser feito com a seguinte
linha de código: gcc iris.c genann.c -o iris -lm, acrescente -fopenmp
para testar a versão paralela ou configure o número de threads via a
variável de ambiente OMP_NUM_THREADS.

4) Alterações
-------------

Foram feitas duas alterações no código:

1a) Realizada no genann.c, essa alteração permite paralelizar o loop
que percorre todos os neurônios de uma determinada camada.

--- genann-orig.c	2018-09-27 20:05:34.344235604 -0300
+++ genann.c	    2018-09-27 21:37:06.000000000 -0300
@@ -317,6 +317,7 @@
         /* Find first weight in following layer (which may be hidden or output). */
         double const * const ww = ann->weight + ((ann->inputs+1) * ann->hidden) + ((ann->hidden+1) * ann->hidden * (h));

+		#pragma omp parallel for
         for (j = 0; j < ann->hidden; ++j) {

             double delta = 0;

2a) Realizada no iris.c, essa alteração permite paralelizar os treina-
mentos, i.e: executar e vincular blocos de entradas para determinadas
threads do sistema. Foi a modificação que de fato introduziu SpeedUp
ao código.

--- iris-orig.c	2018-09-27 20:05:45.409235048 -0300
+++ iris.c      2018-09-27 21:36:55.116237575 -0300
@@ -91,7 +91,7 @@

     /* Train the network with backpropagation. */
     printf("Training for %d loops over data.\n", loops);
-
+    #pragma omp parallel for
     for (i = 0; i < loops; ++i) {
         for (j = 0; j < samples; ++j) {
             genann_train(ann, input + j*4, class + j*3, .01);


Discussão sobre o problema
--------------------------

Muito embora a aplicação tenha apresentado um SpeedUp máximo de 2.78 para
8 threads, há alguns pontos que gostaríamos de ressaltar.

A abordagem inicial foi executar a aplicação no GProf e Intel Advisor
como forma de identificar os pontos críticos e possivelmente prováveis
de paralelização. Pôde-se perceber então que existem três loops aninha-
dos de destaque na função genann_train(), loops esses que processam as
camadas, neurônios e as saídas respectivamente.

O objetivo então consistia em paralelizar o loop do 'meio', loop este
que realiza a maior parte do trabalho, uma vez que a rede foi configu-
rada para 4 entradas, 1 camada oculta (como forma de maximar o nível
de paralelismo para entradas pequenas), 500 neurônios/camada e 3 saídas.

Embora este objetivo tenha sido realizado conforme abordado na seção
4-1a), não houve um speedup e esta modificação foi incluída e menciona-
da aqui apenas para fins de constatação.

---
Com a falta de sucesso com o objetivo 1a), nosso segundo objetivo passou
a ser a modificação realizada em 2a). Como dito anteriormente, esta mo-
dificação consiste na paralelização dos treinamentos, e, embora tenha
garantido um speedup de cerca de ~2.71 para 4 cores (parcode) há
algumas coisas que gostaríamos de ressaltar:

O treinamento de rede neural sequencial e a paralela apresentam ligeiras
diferenças na taxa de acerto. Essas diferenças são de certa forma signi-
ficativas pois há dependência de dados. A forma como a paralelizaçâo da
rede neural foi implementada trata cada conjunto de treinamento como uma
thread. Há 3 saidas em cada thread e a rede neural usa backpropagation
para ser treinada.

Foram realizados testes para 64, 256, 500 e 5000 treinamentos, e,
obteve-se uma taxa de acerto maior na rede neural sequencial até cerca
64 treinamentos. A partir daí, os treinamentos da rede neural paralela
apresentaramm mais acertos do que a sequencial, chegando às vezes a mais
de 98% com uma quantidade de 5000 treinamentos, enquanto a sequencial não
passa de 98%.

O grupo especula que ao realizar o treinamento com backpropagation, a
rede neural deixou de alterar alguns pesos e gravou outros. A longo
prazo, esses pesos sofreram um efeito colateral (não vamos chamar de
erro aqui), que serviram para aproximar ainda mais do resultado desejado,
aumentando a taxa de acerto em cerca de 1%. É necessário entender o que
acontece do ponto de vista estatístico, já que a rede neural paralela,
ao realizar o join, trata certas variáveis que exercem impacto na mudan-
ça de pesos. Utilizando o Intel Inspector, foram identificadas 3 con-
diçôes de corrida, como pode ser observado na imagem (imagens/insp.png)
inclusive no acesso ao valor dos pesos.

Talvez seja possivel aumentar ainda mais a taxa de acerto da rede neu-
ral se esse efeito de gravação de pesos for identificado e puder ser
induzido naturalmente em uma rede neural paralela.

Tempos (parcode)
----------------

Foram realizados os seguintes testes com a base IRIS, na rede abaixo:
5000 treinamentos
4    entradas
1    camada oculta
500  neurônios por camada oculta
3    saídas

Sequencial:
~~~~~~~~~~~

real 1m5.698s
user 1m4.906s
sys	 0m0.776s

Paralelo:
~~~~~~~~~

2 threads:
real 0m48.641s
user 1m29.166s
sys	 0m0.840s
SpeedUP: 1.35

4 threads:
real 0m24.183s
user 1m32.600s
sys	 0m0.772s
SpeedUP: 2.71

8 threads:
real 0m23.614s
user 1m33.192s
sys	 0m0.760s
SpeedUP: 2.78