Infra-Estrutura de Software – Engenharia da
Computação
Lista de POSIX Threads – 2013.2
Leia com atenção as seguintes considerações:
1. Esta lista contém de 7 questões de programação em POSIX
Threads (PThreads). Dentre estas, algumas questões poderão
conter também uma parte teórica.
2. A lista deverá ser respondida individualmente ou em
dupla. Se qualquer tentativa de cópia for identificada, todos
os envolvidos terão suas listas zeradas.
3. As respostas das questões de programação deverão ser
enviadas através do site da disciplina
(www.cin.ufpe.br/~if677ec) na seção “Listas”, até a data
limite estipulada.
As questões devem, também, estar organizadas em arquivos
separados, um por questão, com o nome no formato
“Q[número da questão].c” ou “Q[número da questão].cpp”,
sem aspas. Questões com o nome diferente deste formato não
serão aceitas.
4. As duas seguintes condições devem ser cumpridas para
que a lista seja aceita:
- Pelo menos 1 das seguintes questões deve ser feita: Q6 e Q7.
- Pelo menos 2 das seguintes questões devem ser feitas: Q3, Q4
e Q5.
1
5. Em caso de dúvidas, envie um email para
[email protected] (somente monitores) ou
[email protected] (monitores e alunos).
QUESTÕES:
Q1. Eleição Moderna
Uma cidade começou a usar um novo sistema eletrônico de votação
para as eleições de prefeito. Após o período de votação, os votos de
cada bairro estão em um arquivo e precisam agora ser contabilizados.
Faça um programa que receba um número N de arquivos e um
número T <= N de threads utilizadas para fazer a contagem e um
número C de candidatos a prefeito. Após isso o programa deverá abrir
os N arquivos nomeados “x.in” onde 1 <= x <= N. Cada arquivo terá
1 voto por linha que será um número y | 0 <= y <= C em que 0
significa voto em branco, 1 significa voto ao candidato 1 e assim
sucessivamente.
Ao final imprima na tela o total de votos, a porcentagem de votos
recebidos por cada candidato (e dos em branco também) e o número
do candidato vencedor (que será o candidato com mais votos não
importando a porcentagem).
Exemplo1:
ENTRADA:
N = 2; C = 3; T = 2
Aquivo “1.in”:
0
1
0
2
3
3
Aquivo “2.in”:
0
1
0
2
2
3
3
2
2
2
2
SAÍDA:
Total de votos: 16
Percentual de votos em branco: 25%
Percentual de votos ao candidato 1: 12.5%
Percentual de votos ao candidato 2: 37.5%
Percentual de votos ao candidato 3: 25%
Candidato 2 é o Vencedor.
Q2. Merge sort e Quicksort
Um dos problemas computacionais mais antigos é o de ordenação. Há
muito tempo estuda-se uma maneira eficiente de ordenar uma
sequência de dados de diversos tipos, sendo os mais comuns
números e ordem alfabética. Disso nasceram os algoritmos de
ordenação, que são vários: Bubble, Insert, Gnome, etc. Dois desses
nos interessam em particular: Merge sort e Quicksort. Esses dois
algoritmos usam o princípio do “Divide to conquer”, que consiste em
dividir o problema em partes menores para maximizar a eficiência.
Nossa ideia é tornar esses dois algoritmos ainda mais eficientes,
dividindo-os em execuções paralelas para um computador com até 2,
4 ou 8 cores (threads abertas do inicio ao fim da execução) e
observem o comportamento. Evitem espera ocupada. Façam também
uma versão do programa que não tenha controle do número máximo
de threads, e observem o tempo de execução entre as versões.
Comente brevemente a diferença e justifique.
Q3. #pragma omp for
Essa questão tem uma parte prática e outra teórica. A
parte prática deve ser enviada sem main, apenas a
3
implementação da função pedida (Com tudo o que for
necessário para que esta funcione: Outras funções,
estruturas, variáveis globais e bibliotecas de acordo com o
que jugar necessário).
A parte teórica deve ser um comentário em bloco
deixando claro que diz respeito à parte teórica e não
explicação do código, no começo do código. Essa parte vale
30% da nota da questão e pode ser feita independentemente
do código, apesar de ser recomendado a fazê-la depois da
implementação.
OMP (Open MP) é uma API de C e Fortran muito usada para
paralelismo cientifico, ela provê implementações muito sucintas, mas
poderosas. Um simples #pragma omp parallel antes de chaves faz
com que todas aquelas linhas sejam executas repetidas vezes por N
threads (N definido por variável de ambiente), ainda mais simples um
#pragma omp for parralel antes de um for faz com que esse laço
seja paralelizado de tal forma que cada iteração só ocorra uma vez,
mas que todas ocorram até o final do for em qualquer ordem. OMP
possui muitos outros recursos, mas em si não passa de um padrão.
Suas implementações são dependentes da máquina, compilador de C
ou Fortran, Sistema operacional e N outras variantes. OMP é até
implementado usando Pthreads às vezes (o que é fazer um padrão de
padrões, já que a pthread ainda terá outra implementação mais baixo
nível).
Então sua missão é implementar uma função em C que simule
um #pragma omp for parallel em pthread.
Para isso sabemos que OMP é uma API inteligente e não gera
threads desnecessárias, nem fecha e depois abre outras threads sem
motivo. Dentro de suas variáveis de ambiente há uma variável
chamada OMP_NUM_THREADS que será aqui emulada por uma macro
de mesmo nome. Essa variável costuma ter o mesmo número da
quantidade de núcleos que o sistema possui afim de usar
completamente
a
maquina,
mas
sem
gerar
overheads
desnecessários.
Sendo assim quando um for aparece no código, OMP entrega a
cada uma das N threads uma parcela do trabalho daquele for. E
espera que todas as N threads acabem seu trabalho. Como exemplo
temos :
#pragma omp for parallel
for(int i = 0 ; i < 10 ; i++)
{
CODIGO...
}
4
Se o número de threads a ser criada é 4, OMP destribuiria o trabalho
possivelmente assim:
Thread 0: for(int i = 0; i
Thread 1: for(int i = 3; i
Thread 2: for(int i = 6; i
Thread 3: for(int i = 8; i
Espera as threads acabarem.
<
<
<
<
3
6
8
10
;
;
;
;
i++)
i++)
i++)
i++)
CODIGO...
CODIGO...
CODIGO...
CODIGO...
Repare que nenhum trabalho é realizado mais de uma vez, e
que nenhuma thread pegou mais trabalho que a outra de forma
considerável. Nenhuma trabalho não pedido também foi distribuído
(como uma implementação errada poderia fazer as Threads 2 e 3
terem também 3 iterações, o que transformaria o for entre 0 e 12!
Um absurdo)
No final OMP esperaria que todas as 4 threads acabassem para
continuar.
De fato como OMP divide o trabalho não é tão rígido, e é ai que
você entra. Sabemos que #omp for parallel possui uma clausula
chamada schedule (definida por padrão quando omitida) que recebe
dois argumentos o tipo de escalonamento das threads e o tamanho
do chunk_size. Os tipos de escalonamento são: static, dynamic,
guided, runtime, auto. O chunk_size é um valor entre 1 e o número
total de iterações.
O chunk_size é o quanto as iterações devem estar juntas,
exemplo com chunk_size igual a 3 as iterações são passadas de 3 em
3 para as threads, respeitando o final das iterações. No primeiro
exemplo desta questão o chunk_size era igual a 3, mesmo assim as
ultimas threads pegaram 2 iterações cada ( o mais próximo de 3
possível ).
Segue agora as definições dos schedules:
static: Antes de todas as threads rodarem já é definido quais
iterações cada um vai executar e não há nenhuma comunicação
entre a thread pai e as filhas até elas terminarem. As iterações são
passadas em round-robin a cada chunk_size.
Ex.1.: Um for entre 0 e 100(exclusivo) com chunk_size igual a
10 e 4 threads seria divido (deterministicamente):
Thread
Thread
Thread
Thread
0:
1:
2:
3:
0-9, 40-49, 80-84
10-19, 50-59, 85-89
20-29, 60-69, 90-94
30-39, 70-79, 95-99
5
Ex.2: Um for entre 0 e 100(exclusivo) com chunk_size igual a 20
e 4 threads seria divido (deterministicamente):
Thread
Thread
Thread
Thread
0:
1:
2:
3:
0-19, 80-84
20-39, 85-89
40-59, 90-94
60-79, 95-99
dynamic: As threads são inicializadas sem iterações definidas e
conforme vão necessitando elas pedem mais iterações. Deve ser
passado tantas iterações quanto sejam definidas em chunk_size na
ordem original do for desde que não se ultrapasse o limite definido no
for, caso não haja mais trabalho a thread deve ser fechada. Reparem
que condições de corrida são implícitas nesse modelo.
Ex.1.: Um for entre 0 e 15(exclusivo) com chunk_size igual a 2 e
4 threads será executado possivelmente assim(dependendo de
condições de corrida):
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
0
0
2
3
1
3
3
0
2
1
2
3
0
a 3 são criadas.
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: É fechada.
pede iterações: É fechada.
pede iterações: É fechada.
pede iterações: É fechada.
0-1
2-3
4-5
6-7
8-9
10-11
12-13
14
Ex.2.: Um for entre 0 e 20(exclusivo) com chunk_size igual a 4 e
4 threads seria executado possivelmente assim (dependendo de
condições de corrida):
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
Thread
0
0
1
3
2
1
0
2
3
1
a 3 são criadas.
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: Recebe iterações
pede iterações: É fechada.
pede iterações: É fechada.
pede iterações: É fechada.
pede iterações: É fechada.
0-3
4-7
8-11
12-15
16-19
6
Além dessas duas tecnicas de schedule OMP suporta também
guided, auto e runtime que não serão cobradas nesta questão.
Sendo assim a parte prática é implementar a função em
C/C++ com a seguinte assinatura:
void omp_for(int inicio , int passo , int final , int
schedule , int chunk_size , void (*f)(int));
Onde simularia um:
#pragma omp for
for(int i = inicio ; i < final ; i += passo)
{
f(i);
}
Repare que f é um ponteiro de função e schedule deve
receber um entre vários tipos enumerados ou macros para cada uma
das 2 politicas de escalonamento.
Parte teórica (Valendo 30% da questão, com ou sem a
implementação): Discuta brevemente as diferenças entre o
desempenho das diferentes schedules static e dynamic em
desempenho e em quais aplicações cada uma é mais adequada.
Discuta também o impacto da escolha correta do tamanho das
chunks_sizes e quais seriam boas escolhas para diversas aplicações.
Recomendo o fazer depois de testes da sua própria implementação
desta questão, ou em teste usando OMP. Adicionalmente você pode
comparar sua implementação com OMP.
Q4. N-ésimo Número Primo
Crie um programa em pthreads que encontre o N-ésimo número
primo natural. Uma técnica simples para determinar se um certo
número natural é primo é a “divisão por tentativa”. Basta dividi-lo por
todos os números menores (Exceto pelo número 1) ou iguais à sua
raiz quadrada. Se nenhuma dessas “tentativas” resultar em uma
divisão exata (Divisão cujo resto é igual a 0) o número é considerado
primo. Caso contrário ele é considerado composto. O número 1 não é
considerado um número primo e nem composto.
O usuário deverá informar pelo teclado o número T de threads a
serem criadas e o número N. As T threads só poderão ser criadas no
começo do programa e só poderão ser encerradas depois que o
número primo N já tenha sido determinado. Cada thread deverá fazer
várias divisões por tentativas em números diferentes. Assim que uma
7
thread terminar de testar as divisões em um número, ela
imediatamente deverá testar em outro.
O número procurado deverá ser impresso no console da tela.
Observação: Nessa questão a sincronização entre as threads é algo
fundamental. Um programa que não esteja perfeitamente
sincronizado poderá determinar não o N-ésimo número primo, mas
sim um número primo próximo a ele.
Dica: O único número primo par é o número 2 e todos os outros são
múltiplos dele. Para efeitos práticos, então, evite utilizar esses
números tanto para testá-los quanto para testar outros números.
Exemplo1.:
ENTRADA:
Numero T: 1
Numero N: 5
SAÍDA:
Exemplo2.:
ENTRADA:
N-esimo numero primo: 11
Numero T: 4
Numero N: 34156
SAÍDA:
N-esimo numero primo: 404021
Exemplo3.:
ENTRADA:
Numero T: 8
Numero N: 89336
SAÍDA:
N-esimo numero primo: 1150489
Q5. Matrizes Esparsas
Uma matriz esparsa é uma matriz em que a maioria de seus
elementos tem valor zero. Matrizes desse tipo aparecem
frequentemente em aplicações científicas. Ao contrário de uma matriz
densa, em que é necessário levar em consideração todos os valores
da matriz, em uma matriz esparsa podemos nos aproveitar da
estrutura da matriz para acelerar a computação de resultados. Muitas
vezes, faz-se mesmo necessário aproveitar essa estrutura, ao se lidar
com matrizes esparsas de dimensões imensas (da ordem de 10^6 x
10^6) para que a computação termine em um tempo razoável, visto
que a multiplicação de matrizes tradicional tem complexidade
O(n^3).
8
Nesta questão, você deverá implementar algoritmos para realizar
algumas operações comuns sobre matrizes esparsas de números de
ponto-flutuante. Para auxiliar na definição de uma matriz esparsa,
definiremos primeiramente um vetor esparso:
Um vetor esparso será dado por um vetor de pares (índice,valor), no
qual o primeiro elemento do par indica o índice de um elemento nãozero do vetor, e o segundo elemento indica seu valor. Portanto, o
vetor {0,0,0,1.0,0,2.0}, em forma de vetor esparso, será
representado por {Par (3,1.0),Par (5,2.0)} A implementação dos
vetores esparsos fica a cargo do aluno. Uma matriz esparsa será dada
por um vetor de vetores esparsos.
Portanto, a matriz esparsa a seguir:
2.0 -1.0 0.0 0.0
-1.0 2.0 -1.0 0.0
0.0 -1.0 2.0 -1.0
0.0 0.0 -1.0 2.0
Seria representada como: {{(0,2.0),(1,-1.0)},
{(0,-1.0),(1,2.0),(2,-1.0)},
{(1,-1.0),(2,2.0),(3,-1.0)},
{(2,-1.0),(3,2.0)}}
O aluno deve implementar as seguintes operações sobre matrizes
esparsas:
- Multiplicação de uma matriz esparsa por um vetor denso (vetor
comum de C)
- Multiplicação de uma matriz esparsa por outra matriz esparsa
- Multiplicação de uma matriz esparsa por uma matriz densa (matriz
comum de C)
Todas essas funções devem usar paralelismo, tanto na operação de
produto interno (que deve dividir os vetores envolvidos de forma que
cada thread processe uma parte do vetor) quanto na multiplicação
(em que cada linha da matriz deve ser gerenciada por uma thread).
Portanto, deve-se ter uma thread para cada linha da matriz, que, por
sua vez, lance várias threads que realizem a operação de produto
interno. Para que as funções que multiplicam vetores esparsos por
densos sejam executadas de forma eficiente, é importante notar que
9
dividir o vetor denso em partes iguais leva a operações
desnecessárias. Portanto, o aluno deve implementar a lógica da
questão de forma tal que cada thread receba uma parte de tamanho
diferente do vetor denso, levando ao menor número de operações
que o aluno consiga implementar. A eficiência da implementação será
levada em consideração, além da corretude da questão e da ausência
de deadlocks, livelocks, e starvations.
Q6. Grafos Bicoloríveis
Escreva um programa que determine se um dado grafo conexo e
bidirecional é bicolorível ou não. Um grafo é bicolorível se existir uma
maneira de o colorir somente com duas cores na qual vértices
adjacentes não sejam da mesma cor.
Rodando uma busca em largura a partir de uma raiz qualquer no
grafo se deve criar uma nova thread para cada novo vértice ainda
não visitado, enquanto a thread pai deverá obrigatoriamente dormir
enquanto espera as threads filhas terminarem de colorir o grafo. No
final da execução deve ser aberta uma e somente uma thread por nó
no grafo.
Cada thread marcará o seu vértice como visitado e tentará o colorir
com cor diferente do pai, se ele for a raiz do grafo uma cor arbitraria
deve ser escolhida. Caso uma thread tente colorir um vértice que já
foi visitado com uma cor diferente da que ele tem no momento o
programa já pode retornar erro, pois não há como bicolorir esse grafo.
Caso se consiga bicolorir o grafo completamente o programa deverá
informar que o grafo é bicolorível. Os grafos de entrada serão
obrigatoriamente conexos.
Serão passados por um arquivo de entrada com o nome “Entrada.txt”
o número V de vértices, seguido do número A de arestas e,
consequentemente, de A arestas.
Exemplo1.:
ENTRADA: 11 13
12
1 11
23
2 10
38
45
58
59
10
SAÍDA:
5 11
6 11
7 11
9 10
10 11
E bicolorivel.
Exemplo2.:
ENTRADA: 10 15
12
13
1 10
26
24
37
35
45
48
59
67
69
78
8 10
9 10
SAÍDA:
Nao e bicolorivel.
Q7. Superescalar de Vetores - SupVet®
Processadores modernos de uso geral são costumeiramente
superescalares, ou seja dentro de um mesmo núcleo há paralelismo
interno à nível de instrução de assembly. Em outras palavras eles são
capazes de executar mais de uma instrução ao mesmo tempo dentro
de um único núcleo, mas dando ao programador a ilusão de
serialidade. Não confunda superescalar com múltiplas núcleos ou
hyper-thread, são coisas totalmente independentes. Um exemplo
disso são todos os processadores da linha Pentium 3, eles são todos
superescalares, mas sem hyper-threading e com apenas um núcleo.
Outro exemplo são os processadores i3, i5 e i7 que são todos
multiplos núcleos, com hyper-threading e ainda superescalares. E
ainda no meio de caminho temos processadores como o AMD X4 ou
X6 que são superespalares, com múltiplos núcleos, mas não usam
hiper-threading.
11
Um processador superescalar possui uma buffer de instruções
de tamanho fixo, uma única unidade de fetch e múltiplas unidades
somadoras, multiplicadoras, divisoras, de acesso à memoria e etc. O
buffer é preenchido com as instruções do código até seu limite. A
unidade de fetch lança as instruções as unidades de processadores se
e somente se elas não possuem dependências, no mais ela também é
responsável por checar quando as mesmas forem finalizadas para
poder lançar novas instruções (dependentes ou não aquelas). Cada
uma das unidades de processamento (somadores, multiplicadores e
etc.) compartilham um buffer menor (também de tamanho fixo) com
suas unidades de processamento irmãs, ou seja, há um buffer de
comandos de multiplicação, outro buffer para soma e assim
sucessivamente. Destes buffers as unidades de processamento vão
lendo os comandos sem se importar com dependências, apenas
removendo os e executando. Depois de finalizado cada comando as
unidades de processamento sinalizam ao fetch seu termino. Cada
unidade de processamento é independente das demais. De fato a
dificuldade de se implementar um processador superescalar se
resume a reparar quando instruções são independentes e quando são
dependentes. Quando há dependência as instruções mais antigas
devem ser executadas primeiro..
Exemplo de como um trecho de assembly em x86 seria
executado:
add EAX, EBX;
add ECX, EBX; Pode rodar em paralelo com a primeira
instrução.
add EBX, EBX; Tem que esperar que a 1 e a 2 instruções
terminem, pois EBX terá valor modificado.
mul EDX; Precisa esperar a 1 instrução terminar pois
esta instrução escreve em EAX e EDX.
mov ESI, [label]; É completamente independente e pode
rodar sem esperar nenhuma das anteriores.
Um comando (Em x86 ou no SupVet®) recebe parâmetros que
podem ser de entrada(leitura), saída (escrita) ou ambos. Uma
dependência acontece nas seguintes situações:
O comando tem um parâmetro de entrada que esta sendo
usado como parâmetro de saída por outra unidade de processamento.
O comando tem um parâmetro de saída que esta sendo usado
como parâmetro de qualquer tipo em outra unidade de
processamento.
Nessas situações o comando espera a finalização dos comandos
anteriores.
Usando esses conceitos foi então elaborado um projeto de um
novo superescalar, o SupVet®. Que por motivos de orçamento deve
ser por enquanto apenas simulado com um único núcleo usando
12
pthreads. Alguns especialistas em hardware alegam também que o
SupVet® nunca será viável de ser implementado, mas isso não afeta
o fato que ele é sim simulável.
O SupVet® opera somente com vetores de floats. E eles tem
tamanho reajustado automaticamente em suas instruções.
Na entrada da simulação terão comandos em um arquivo
chamado in.txt. Na primeira linha da entrada teremos um número dizendo
quantas variáveis serão inicializadas durante sua execução, se seguiram então
N linhas com o comando “new” cada um destes comandos inicializando uma
variável com um nome. Essas variáveis devem permanecer até o final do
programa, e não serão criadas novas variáveis depois deste inicio.
new TAMANHO VARIAVEL valor valor … valor
Onde TAMANHO é o tamanho do vetor e VARIAVEL é o label a
qual este vetor deve ser vinculado. Igualmente se seguirá TAMANHO
valores de float na mesma linha um para cada casa deste novo vetor.
Esta primeira parte do código, onde se inicializam variáveis, não precisa
ser paralelizado e deve ser feito apenas pela thread-fetch.
Depois destas N linhas os comandos possíveis são os seguintes e
iram seguir um por linha até o final do arquivo:
print VARIAVEL
mov VARIAVEL_A
mul VARIAVEL_A
div VARIAVEL_A
add VARIAVEL_A
sub VARIAVEL_A
VARIAVEL_B
VARIAVEL_B
VARIAVEL_B
VARIAVEL_B
VARIAVEL_B
VARIAVEL_C
VARIAVEL_C
VARIAVEL_C
VARIAVEL_C
Os nomes das variável seguem o padrão de C.
Na segunda parte do código não haverá comandos do tipo new.
O comando print deve imprimir na tela o nome da variável e
todas as suas casas em uma tabulação legível escolhida pelo aluno.
Os operadores de soma, multiplicação, subtração e divisão são
aplicados valor a valor ao longo do vetor. O padrão sempre é a
primeira variável recebe a operação aplicada as outras duas. Caso um
dos vetores de entrada seja menor que o outro, a parte restante deve
ser operada com o valor 0 para soma e subtração e com valor 1 para
divisão e multiplicação. Sendo assim a saída sempre terá tamanho
igual a max ( TAMANHO(VARIAVEL_B) , TAMANHO(VARIAVEL_C) ). Caso
seja preciso realoque o vetor da VARIAVEL_A para se ajustar, para
mais ou para menos ao seu novo tamanho.
O comando mov apenas copia os valores e o tamanho da
VARIVEL_B para a VARIAVEL_A.
VARIAVEL_A, VARIVEL_B e VARIAVEL_C podem ser a mesma
variável.
13
Haverá 6 tipos de threads:
Thread-fetch
Thread-multiplicadora
Thread-IO
Thread-divisora
Thread-subtradora
Thread-somadora
As unidades de IO tem com função processar os comandos de
print. Nestes a unidade de IO imprime os valores na tela, mas deve
ser garantido que não haverá race-condition no uso do stdout.
As saídas na tela devem ser na ordem que foram chamadas no
código, vocês podem interpretar que todo print tem stdout como
parâmetro de saída, e que assim todos os print tem dependência
entre si.
Os comandos new e a desalocação no final de toda a execução
devem ser interpretado pelo próprio featch, que tem como função
também administrar as variáveis.
Não haverão erros de sintaxe na entrada.
Seu programa deve aceitar os seguintes parâmetros de précompilação(#define) com valores maiores ou iguais a 1:
NUM_THREADS_MUL
NUM_THREADS_DIV
NUM_THREADS_SUB
NUM_THREADS_SOM
TAMANHO_BUFFER_FETCH // Tamanho do buffer de fetch
TAMANHO_BUFFER_PROC // Tamanho dos buffers de processamento
( um por tipo de unidade de processamento ).
O número de threads-fetch e threads-IO serão sempre 1 (para
cada). A thread-fetch deve ser a própria thread-main do seu
programa.
As threads devem ser reutilizadas do começo ao fim do
programa.
A thread fetch deve ler o próprio buffer de comandos e
seguindo a ordem dos comandos e dependências deve despachar
para os buffers das unidades de processamento. Quando uma
instrução se finalizar na unidade de processamento a mesma pode
ser removida do buffer do fetch e só então se ler mais comandos do
arquivo de entrada.
É totalmente proibido o uso de espera ocupada nessa
questão. Cada buffer deve ter associado a ele um mutex e
uma variável de condição, quando uma unidade (fetch ou não)
não tiver mais o que produzir a mesma deve dormir associada
a uma variável de condição onde ela pode ser acordada com a
necessidade de mais trabalho.
14
As unidades de processamento apenas removem suas
instruções de suas filas e ao finalizar estes comandos vão ao buffer
da unidade de fetch e os marcam como comandos finalizados.
Boa modularização dos buffers, comandos, estruturas de cada
vetor-variável, estruturas do que é um comando são de encargo da
dupla que esta fazendo a lista e devem ser legíveis e de fácil
entendimento. Igualmente alocação dinâmica bem realizada,
programa livre de acesso indevido, deadlocks ou starvation também
são vossa responsabilidade.
Reparem que a saída para o usuário é determinística. No
entanto a ordem da execução dos passos internos não o é.
Exemplo:
4
new 3 a 0 0 0
new 3 b 2.0 3.0 4.0
new 3 c 1.0 2.0 3.0
new 1 aux 0
print aux
add a b c
add aux a
print a
print aux
mul b b c
print b
Saida de exemplo ( a formatação dos valores é de escolha do
aluno como já dito):
aux
a =
aux
b =
=
{
=
{
{ 0.0
3.0 ,
{ 3.0
2.0 ,
}
5.0 , 7.0 }
, 5.0 , 7.0 }
6.0 , 12.0 }
15