Projeto IPPD — Minimum Weight Polygon Decomposition

Paralelização com OpenMP do Problema C da 9th Marathon of Parallel Programming (WSCAD 2014).

Disciplina	Introdução ao Processamento Paralelo e Distribuído (IPPD)
Equipe	Julia Amadio, João Bastasini, Leandro Zirondi, Narumi Momoeda
Código paralelo	polygon_cut.c
Linha de base sequencial	old_polygon_cut.c (código do enunciado)

Documentação:

• docs/CONCEITO_PROBLEMA.md — o problema e o algoritmo sequencial
• docs/RELATORIO.md — o relatório da disciplina: justificativa de cada diretiva, correção e desempenho
• docs/HISTORICO.md — registro de engenharia: defeitos encontrados e como foram corrigidos

Compilar e rodar

make          # polygon_cut      (paralelo, -O2 -fopenmp)
make seq      # polygon_cut_seq  (sequencial, -O2)

./polygon_cut < tests/input_enunciado.txt

./tests/run_tests.sh            # correção: seq vs OpenMP em várias threads
./tests/bench.sh                # desempenho: tempo, speedup, eficiência

macOS (Apple Silicon): o Apple Clang não suporta -fopenmp nativamente. Use o GCC do Homebrew:

brew install gcc
make CC=gcc-16       # ajuste o sufixo (-14, -15, -16) para a versão instalada
make seq CC=gcc-16

---

Estado do trabalho

O núcleo técnico está pronto e validado: o algoritmo foi paralelizado, a correção está verificada e toda a justificativa das diretivas está escrita.

A bateria final foi executada em 30/07/2026, 02:02–04:10, no Xeon, e as Seções 13, 15 e 16 do relatório foram reescritas sobre ela. Dados brutos em resultados/.

O empacotamento (qualidade de código e requisitos de entrega) foi concluído.

Bloco	Situação
Algoritmo e paralelização	✅ pronto
Correção verificada	✅ 40/40 comparações idênticas, até 16 threads
Justificativa das diretivas (relatório §2–12)	✅ escrito
Infraestrutura de teste e benchmark	✅ pronta (bateria.sh retomável)
Medições de desempenho (§13, 15, 16)	✅ bateria de 30/07 no Xeon
Qualidade de código (item 19)	✅ resolvido
Requisitos de entrega (item 20)	✅ resolvido

O achado mais importante da bateria: o fator dominante de escalabilidade mudou de identidade. Saiu o número de núcleos físicos e entrou o subsistema de memória, que na lista antiga era o fator 5 de 7. Consequência prática — a alocação das matrizes em bloco único (item 2.x, "otimizações não exploradas") passou de melhoria cosmética a otimização de maior retorno esperado. Ver Seção 16 do relatório e Apêndice A.3, que confronta as previsões antigas com os dados.

---

Prioridade 1 — bloqueiam a entrega

1.1 Refazer todas as medições no Xeon — feito

Bateria de 30/07/2026, 02:02–04:10. Máquina: Intel Xeon E5-2650 v2, 8 núcleos físicos / 16 lógicos, L3 de 20 MB, Windows 10 + WSL2 (Ubuntu 24.04, gcc 13.3.0), com afinidade fixada (OMP_PLACES=cores, OMP_PROC_BIND=close). Resultados em resultados/, tabelas na Seção 15 do relatório.

Para repetir:

./tests/bateria.sh              # ~3h40 completa, ~2h reaproveitando a correção
./tests/bateria.sh --status     # o que já terminou

Ambiente detalhado e ressalvas da rodada no Apêndice B do relatório; como reduzir ruído e interpretar o aviso de carga, em tests/README.md.

1.2 Reescrever a Seção 16 — feito

Reescrita em torno de custo por iteração interna em vez de razões de speedup. Duas descobertas que mudaram a seção:

• O working set cabe nos 20 MB de L3 (15,26 MB no caso máximo), como previsto — mas memória continua sendo o fator dominante, por latência e contenção, não por capacidade.
• O speedup paralelo não é monotônico no tamanho da entrada: 5,39× → 4,07× → 5,69× em 16 threads. O caso de 600 vértices, recuperado nesta bateria, é o que revela isso. As barreiras respondem por ~1% do déficit.

1.3 Reescrever a Seção 13 — feito

Tabela de ambiente substituída; blockquote dos "2 núcleos físicos" trocado pelos dois detalhes que agora governam a leitura (8 núcleos e L3 de 20 MiB). Acrescentadas as subseções de afinidade de threads e de carga concorrente e o eco do próprio experimento, além da limitação de virtualização do WSL2.

1.4 Corrigir o número cravado na prosa da Seção 2 — feito

Era 3,4×; a bateria final dá 2,9× no caso de 400 vértices. O parágrafo agora também registra que o ganho cai para 1,4× em 1000 vértices e aponta para a Seção 16.

1.5 Criar o script de execução da entrega — feito

Criado o script run.sh na raiz do projeto. Ele compila o código paralelo e executa o binário com um arquivo de entrada passado como argumento, simplificando a avaliação.

1.6 Confirmar os requisitos com a disciplina — feito

Confirmado pelo enunciado oficial: a avaliação será feita com base na corretude do código, ganho de desempenho e no relatório. Não é necessário seguir os padrões estritos de entrada/saída automáticos da maratona original. O repositório com código sequencial, paralelo e o relatório no GitHub atende a todos os requisitos.

---

Prioridade 2 — qualidade e infraestrutura

2.1 Qualidade de código (item 19)

• Verificar o retorno do scanf — corrigido em a6c906a
• int main() → int main(void) — corrigido em a6c906a
• Constante nomeada para o "infinito" — macro INF(size), corrigido em a6c906a
• -Wall -Wextra -Wpedantic limpo; target make check adicionado em 171e959

2.2 bench.sh — pendências

Nove defeitos de infraestrutura de medição já foram corrigidos ao longo do trabalho; o registro de cada um está em docs/HISTORICO.md, com índice na Seção 17 do relatório. O que continua aberto:

• A linha "Compilador" reporta cc (usa ${CC:-cc}), enquanto o Makefile resolve /usr/bin/gcc. A tabela de ambiente do relatório sai imprecisa.
• "Governor: n/d" é o correto no WSL, mas merece nota explicando por quê.

2.3 Repositório

• .gitattributes versionado (commit 3318e5c). Normaliza line endings em LF e resolve os "modified" fantasma ao alternar entre Windows, WSL e Linux.

Já fechados nesta rodada

As lacunas da rodada anterior (caso de 600 vértices, linha de 2 threads do caso máximo, repetições do caso máximo) foram todas cobertas — ver Apêndice A.4 do relatório. O Apêndice A em si deixou de ser roteiro e virou registro, com as previsões que fazia confrontadas com os dados em A.3.

---

Prioridade 3 — investigação e otimizações

3.1 Investigar o platô de 4 → 8 threads — respondido pela bateria R1

A investigação usava o caso de 400 vértices e propunha um teste: se o platô fosse falta de trabalho para amortizar a barreira, ele deveria atenuar monotonicamente de 400 para 600 para 1000 vértices; se persistisse igual nos três, a causa seria a camada de vCPU. A bateria R1 rodou os três pontos e a resposta foi nenhuma das duas:

Vértices	Speedup 4t	8t	16t	Ganho marginal 4→8
400	3,17	4,14	5,39	+0,97
600	3,48	3,69	4,07	+0,21 ← o platô está aqui
1000	3,53	4,83	5,69	+1,30

O platô não atenua com o tamanho: ele é pior no meio, o que mata a hipótese de trabalho por barreira. A causa é contenção de memória, e o argumento completo — por que as barreiras não podem explicar o déficit — está na Seção 16 do relatório.

Em 400 vértices, com afinidade fixada e REPS=5, o platô que motivou esta investigação não reaparece (+0,97 de 4 para 8 threads). Os números originais vinham de séries de 3 repetições cujas faixas se sobrepunham quase inteiras — ressalva que o próprio item registrava. O fenômeno real estava em 600 vértices, caso que não existia quando isto foi escrito.

Das três hipóteses que o item havia descartado por medição, as duas de instrumentação seguem descartadas (relógio do WSL saltando; decaimento térmico). A terceira era a afinidade de threads, e a conclusão do item se sustenta: sob virtualização o pin não reduz a variância de forma mensurável. Ele entrou no protocolo por reprodutibilidade e não por desempenho — as duas medições estão no Apêndice B do relatório.

3.2 Otimizações não exploradas

Descritas e justificadas na Seção 17 do relatório. Em ordem de retorno esperado, à luz da bateria R1:

• Alocação das matrizes em bloco contíguo único — a de maior retorno, agora que a Seção 16 mostra memória como fator dominante.
• Cláusula if na região paralela, para entradas pequenas.
• schedule ajustado ou guided — provavelmente não vale: não há desbalanceamento a corrigir.

---

Referência — os 20 itens originais

Numeração preservada: a Seção 18 do docs/RELATORIO.md faz referência cruzada a estes números.

#	Item	Situação
1	Corrigir o Makefile (OpenMP)	✅ feito; bug de detecção de compilador corrigido
2	Manter versão sequencial	✅ make seq
3	Criar entradas de teste	✅ 8 casos em tests/
4	Automatizar comparação de saídas	✅ tests/run_tests.sh
5	Medir tempo de execução	✅ bateria de 30/07 no Xeon; relatório §15
6	Calcular speedup e eficiência	✅ relatório §15
7	Documentar a transformação da recursão	✅ relatório §2
8	Documentar o papel de span	✅ relatório §3
9	Documentar a paralelização do laço de a	✅ relatório §4
10	Explicar a barreira implícita	✅ relatório §5
11	Explicar a região paralela persistente	✅ relatório §6
12	Explicar as variáveis privadas	✅ relatório §7
13	Explicar por que não foi usado mutex	✅ relatório §8
14	Documentar schedule(static)	✅ relatório §9
15	Documentar a inicialização paralela	✅ relatório §10
16	Documentar a redução final	✅ relatório §11
17	Analisar a escalabilidade	✅ relatório §16, reescrito sobre a bateria
18	Registrar a complexidade	✅ relatório §12
19	Ajustes de qualidade no código	✅ corrigido (a6c906a, 171e959)
20	Verificar requisitos da entrega	✅ feito (1.5, 1.6)