Lista 1 Resolvida
De BCC Wiki
Lista: Lista 1 PDF
Tabela de conteúdo |
Exercício 1
a
Versão com Threads
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#define N ? /* Define o valor de N, substituir ? */
int array[N];
int c = 0;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
void soma(int x){
/* Regi�o Cr�tica */
pthread_mutex_lock(&mut);
c = c + array[x];
pthread_mutex_unlock(&mut);
}
int main(){
int i;
pthread_t ids[N];
/* Inicializa o vetor para testes
for (i = 0; i < N; i ++){
array[i] = i;
}*/
for (i = 0; i < N; i++){
pthread_create(&ids[i],NULL,soma,i);
}
for (i = 0; i < N; i++){
pthread_join(ids[i],NULL);
}
printf("Results is %d\n",c);
return 0;
}
Versão com OpenMP
#pragma omp parallel for reduction(+:c)
for (c=i=0; i < N; i++)
{
c = c + a[i];
}
Exercício 2
(a) O número máximo de processadores é 3, porque as linhas 3-5, 6-8 e 9-10 não têm dependências verdadeiras então podem ser paralelizadas, a sequência de execução pode ser
thread 1 2 3
1
2
3 4 5
sync 6 7 8
sync 9 10 11
sync 12
havendo sincronização antes de cada linha marcada com sync
Fiz de outra maneira, usando Ordenação Topológica
thread 1 2 3
1
2 4 7
8 3 5
9 6 10
11 12
(b) O tempo de execução é 6, dado pelo número de linhas da tabela anterior
(c) A aceleração é S(3) = T(1) / (ts + tp/3) => S(3) = 12 / (3 + 9/3) = 12 / 6 = 2
Exercício 3
É chamada de verdadeira porque é a única que não pode ser desfeita. A anti-depêndencia pode ser desfeita inserindo uma nova variável, por exemplo
c = a + d; a = b;
pode virar uma dependência verdadeira inserindo a variável k
k = a; a = b; c = k + d;
e a dependência de saída se vier sozinha não faz sentido e pode ser desfeita facilmente
Por exemplo:
a = b; a = c;
é uma dependência de saída que pode ser trocado por
a = c;
Se não estiver sozinha ela vem acompanhada das outras duas depêndencias
Por exemplo:
a = b; k = a + 3; a = c;
Que é transformado numa dependência verdadeira usando o mesmo mecanismo da anti-paralela
a = b; d = a; a = c; k = d + 3;
Exercício 4
O custo correspondente na memória compartilhada é dado pelo barramento da memória, de quão rápido os dados são enviados da memória sendo compartilhada até o cache do processador que vai executar o trecho de código
Exercício 5
To-Do
Exercício 6
Os programas Embarrasing Parallel são programas que não é necessário nenhum grande empenho em segmentar o programa em um grande número de tarefas paralelizáveis e não há nenhuma dependência essencial entre estas tarefas paralelizáveis.
Exercício 7
To-Do
Exercício 8
To-Do
Exercício 9
Semáforo x Busy Waiting
Um Busy Waiting faz uma verificação repetidamente para a modificação de uma determinada variável ou recurso. Um exemplo é a captura de eventos de um teclado ou a espera por uma trava se destravar.
Um semáforo recebe um valor máximo de quantos processos podem acessar um recurso e consiste de duas operações: wait e signal. O wait decrementa o valor do semáforo, e se este valor for 0, o processo é posto para dormir. O signal incrementa o valor do semáforo. Se o valor for 0, e houver algum processo dormindo, acorda o processo adormecido. Caso contrário, incrementa o valor do semáforo.
O Busy Waiting parece gastar mais CPU, por se tratar de uma verificação "exaustiva". Porém, no caso de um BW, a atualização acontece mais rápido.
