Paralelismo em CPU com OpenMP¶
Objetivo¶
- Paralelismo em CPU: como dividir o trabalho entre múltiplos cores.
- Threads: cada thread executa uma parte do trabalho.
- OpenMP: diretivas em OpenMP para paralelizar loops.
- Scheduling: forma como as iterações do loop são distribuídas entre threads (
static
,dynamic
,guided
).
Os processadores atuais possuem múltiplos núcleos de execução (cores). Para aproveitar essa capacidade, podemos dividir o trabalho em partes menores que possam ser executadas simultaneamente. Essa divisão é feita por meio de threads, onde cada thread executa uma fração das instruções.
No caso de laços de repetição, o paralelismo é obtido ao repartir as iterações entre várias threads. Em vez de uma única thread percorrer todo o laço, cada thread recebe um subconjunto de iterações, reduzindo o tempo total de execução. O OpenMP facilita esse processo por meio de diretivas como #pragma omp parallel for
.
Tip
Para saber mais, veja o material disponível em Guia de Pragmas OpnMP
Scheduling no OpenMP¶
Quando um laço é paralelizado, é preciso definir como as iterações serão distribuídas entre as threads. Essa estratégia é chamada de schedule (escalonamento).
- static → divide as iterações em blocos fixos, atribuídos antecipadamente a cada thread.
- dynamic → as iterações são distribuídas em blocos sob demanda, conforme as threads terminam suas tarefas.
- guided → inicia com blocos maiores e reduz gradualmente o tamanho, equilibrando a carga de trabalho.
- auto → delega ao compilador a escolha da estratégia.
- runtime → a estratégia é definida em tempo de execução pela variável de ambiente
OMP_SCHEDULE
.
A escolha do escalonamento não altera o resultado final da computação, mas impacta diretamente o desempenho e o balanceamento da carga de trabalho.
O programa omp_schedulers.cpp
é um código exemplo para visualizar a distribuição das iterações de um laço entre threads em diferentes estratégias de schedule
.
Para cada política de escalonamento, o programa registra quais iterações foram executadas por cada thread e exibe uma saída gráfica com *
, indicando a distribuição.
Dessa forma, é possível observar o comportamento de cada política:
omp_schedulers.cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <omp.h> // OpenMP (omp_get_thread_num, diretivas)
// -----------------------------------------------------------------------------
// print_iterations:
// - Recebe uma descrição, um vetor de vetores 'vectors' (4 vetores, um por thread),
// e 'n' (número total de iterações do laço).
// - Constrói 4 strings com '*' indicando quais iterações cada thread executou.
// - Imprime a distribuição para visualizar o efeito do 'schedule'.
// -----------------------------------------------------------------------------
void print_iterations(const std::string& description,
const std::vector< std::vector<int> >& vectors,
const int n)
{
std::vector<std::string> strings(4, std::string()); // 4 linhas de saída, uma por thread
for (int i = 0; i != n; i++) // varre todas as iterações 0..n-1
{
for (int j = 0; j != 4; j++) // para cada "thread" (0..3)
{
const auto& vector = vectors[j]; // vetor com as iterações que a thread j executou
auto it = std::find(vector.begin(), vector.end(), i); // procura o i dentro do vetor da thread j
if (it != vector.end())
{
strings[j] += "*"; // se a thread j executou a iteração i, marca '*'
}
else
{
strings[j] += " "; // caso contrário, espaço em branco
}
}
}
std::cout << description << std::endl; // título/descrição da experiência
for (auto& s : strings) // imprime as 4 linhas (uma por thread)
{
std::cout << s << "\n";
}
std::cout << std::endl;
}
// -----------------------------------------------------------------------------
// schedule (template):
// - Função "driver" que recebe outra função 'function' (uma política de agendamento),
// a descrição e 'n'.
// - Aloca 'vectors' (4 vetores: um por thread) e chama 'function' para preenchê-los.
// - Depois imprime o resultado com print_iterations.
// -----------------------------------------------------------------------------
template <typename T>
void schedule(T function,
const std::string& description,
const int n)
{
std::vector<std::vector<int>> vectors(4, std::vector<int>()); // 4 threads simuladas
function(vectors, n); // executa a política (preenche vectors)
print_iterations(description, vectors, n); // visualiza distribuição
}
// -----------------------------------------------------------------------------
// Cada função 'scheduleXYZ' abaixo:
// - Abre uma região paralela com 4 threads (num_threads(4))
// - Faz um for paralelo '#pragma omp for' sobre i = 0..n-1
// - Cada thread registra a iteração 'i' que executou em vectors[tid]
// Observação didática: push_back em 'vectors[tid]' é aceitável aqui para fins
// de visualização (em geral, acessos concorrentes a containers exigem cuidado).
// -----------------------------------------------------------------------------
// Default: sem especificar 'schedule' explicitamente (deixa o runtime decidir)
void scheduleDefault(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i); // registra a iteração i sob a thread atual
}
}
}
// schedule(static): divide as iterações em blocos fixos, um por thread (tamanho auto)
void scheduleStatic(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(static)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(static, 4): blocos fixos de 4 iterações por vez
void scheduleStatic4(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(static, 4)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(static, 8): blocos fixos de 8 iterações por vez
void scheduleStatic8(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(static, 8)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(dynamic): threads pegam blocos sob demanda (tamanho padrão do runtime)
void scheduleDynamic(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(dynamic)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(dynamic, 1): blocos dinâmicos de 1 iteração (alto overhead, ótimo balanceamento)
void scheduleDynamic1(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(dynamic, 1)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(dynamic, 4): blocos dinâmicos de 4 iterações
void scheduleDynamic4(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(dynamic, 4)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(dynamic, 8): blocos dinâmicos de 8 iterações
void scheduleDynamic8(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(dynamic, 8)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(guided): blocos começam grandes e vão diminuindo (bom p/ carga irregular)
void scheduleGuided(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(guided)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(guided, 2): guided com bloco mínimo de 2
void scheduleGuided2(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(guided, 2)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(guided, 4): guided com bloco mínimo de 4
void scheduleGuided4(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(guided, 4)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(guided, 8): guided com bloco mínimo de 8
void scheduleGuided8(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(guided, 8)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(auto): deixa o runtime escolher o melhor esquema
void scheduleAuto(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(auto)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
// schedule(auto): deixa o compilador escolher a melhor estratégia
void scheduleRuntime(std::vector<std::vector<int>>& vectors, int n)
{
#pragma omp parallel num_threads(4) shared(vectors, n)
{
#pragma omp for schedule(auto)
for (int i = 0; i < n; i++)
{
vectors[omp_get_thread_num()].push_back(i);
}
}
}
int main()
{
const int n = 64; // número de iterações do laço a serem distribuídas entre 4 threads
// Executa cada política de agendamento e imprime a “faixa” de iterações por thread.
schedule(scheduleDefault, "default: ", n);
schedule(scheduleStatic, "schedule(static): ", n);
schedule(scheduleStatic4, "schedule(static, 4): ", n);
schedule(scheduleStatic8, "schedule(static, 8): ", n);
schedule(scheduleDynamic, "schedule(dynamic): ", n);
schedule(scheduleDynamic1, "schedule(dynamic, 1): ", n);
schedule(scheduleDynamic4, "schedule(dynamic, 4): ", n);
schedule(scheduleDynamic8, "schedule(dynamic, 8): ", n);
schedule(scheduleGuided, "schedule(guided): ", n);
schedule(scheduleGuided2, "schedule(guided, 2): ", n);
schedule(scheduleGuided4, "schedule(guided, 4): ", n);
schedule(scheduleGuided8, "schedule(guided, 8): ", n);
schedule(scheduleAuto, "schedule(auto): ", n);
schedule(scheduleRuntime, "schedule(runtime): ", n);
return 0;
}
Compilar o código com OpenMP
g++ -fopenmp omp_schedulers.cpp -o omp_schedulers
Rodar no cluster com SLURM definindo o número de threads:
srun --partition=normal --ntasks=1 --cpus-per-task=4 ./omp_schedulers
ou
#!/bin/bash
#SBATCH --job-name=omp_scheduler_test # nome do job
#SBATCH --output=output_omp_schedulers.out # arquivo de saída
#SBATCH --ntasks=1 # 1 processo (1 task MPI)
#SBATCH --cpus-per-task=4 # 4 CPUs para essa task → 4 threads OMP
#SBATCH --time=00:05:00 # tempo máximo de execução
#SBATCH --mem=2G # Memória total do job (ex.: 2 GB)
# garante que o OpenMP use exatamente os recursos alocados pelo SLURM
export OMP_NUM_THREADS=${SLURM_CPUS_PER_TASK}
# executa o binário
./omp_schedulers
Analisando os Schedulers no OpenMP¶
Cada scheduler do OpenMP se comporta de maneira diferente, e você deve observar o impacto de cada um:
static: As iterações são divididas igualmente entre as threads.
dynamic: As threads pegam blocos de iterações conforme terminam o trabalho.
guided: Distribui blocos maiores no início e menores no final, equilibrando a carga.
auto: Deixa o compilador escolher a melhor estratégia.
runtime: Usa a estratégia definida em tempo de execução.
Atividade 03 - Paralelismo com OpenMP¶
Código base para a atividade 03:
paralelo.cpp
// Compile: g++ -FlagDeOtimização -fopenmp paralelo.cpp -o paralelo
// Execute: ./paralelo [N] (N padrão = 10'000'000)
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <omp.h>
int main(int argc, char** argv) {
// ------------------------------
// Parâmetros e dados de entrada
// ------------------------------
const int N = (argc >= 2 ? std::stoi(argv[1]) : 10'000'000);
std::cout << "N = " << N << "\n";
// Vetor base (valores aleatórios em [0,1))
std::vector<float> a(N);
{
std::mt19937 rng(123); // seed fixa só p/ reprodutibilidade
std::uniform_real_distribution<> U(0.0, 1.0);
for (int i = 0; i < N; ++i) a[i] = static_cast<float>(U(rng));
}
// =========================================================
// TAREFA A: Transformação elemento-a-elemento (map)
// =========================================================
const float alpha = 2.0f, beta = 35.5f;
std::vector<float> c(N);
double t0 = omp_get_wtime();
for (int i = 0; i < N; ++i) {
c[i] = alpha * a[i] + beta;
}
double t1 = omp_get_wtime();
std::cout << "[A] tempo = " << (t1 - t0) << " s\n";
int idx = N/2; // pega o elemento do meio do vetor
std::cout << "[A] c[" << idx << "] = " << c[idx] << "\n";
// =========================================================
// TAREFA B: Soma (redução) da norma L2 parcial
// =========================================================
t0 = omp_get_wtime();
double soma = 0.0;
for (int i = 0; i < N; ++i) {
soma += static_cast<double>(c[i]) * static_cast<double>(c[i]);
}
t1 = omp_get_wtime();
std::cout << "[B] tempo = " << (t1 - t0) << " s | soma = " << soma << "\n";
return 0;
}
g++ -FlagDeOtimização -fopenmp paralelo.cpp -o paralelo
Para Executar:
#!/bin/bash
#SBATCH --job-name=paralelo_todo # Nome do job
#SBATCH --output=paralelo.txt # nome do arquivo de saida
#SBATCH --ntasks=1 # Sempre 1 processo (o programa roda só uma vez)
#SBATCH --cpus-per-task=4 # Esse processo tem 4 CPUs disponíveis para usar
#SBATCH --mem=2G # Memória solicitada
#SBATCH --time=00:05:00 # Tempo solicitado (hh:mm:ss)
#SBATCH --partition=normal # fila
# ------------------------------
# Configurações OpenMP
# ------------------------------
export OMP_NUM_THREADS=${SLURM_CPUS_PER_TASK} # OpenMP abre 4 threads e distribui o trabalho entre elas
export OMP_PLACES=cores # Fixa threads em cores
export OMP_PROC_BIND=close # Coloca threads próximas (melhor cache)
# Troque aqui o Schedule do seu teste
export OMP_SCHEDULE=static
echo "==== Configuração de Execução ===="
echo "Job ID : $SLURM_JOB_ID"
echo "CPUs-per-task : $SLURM_CPUS_PER_TASK"
echo "Memória total : $SLURM_MEM_PER_NODE MB"
echo "OMP_NUM_THREADS : $OMP_NUM_THREADS"
echo "OMP_SCHEDULE : $OMP_SCHEDULE"
echo "=================================="
# ------------------------------
# Executa o programa
# ------------------------------
# paralelo (4 threads, por ex.)
export OMP_NUM_THREADS=${SLURM_CPUS_PER_TASK} # OpenMP abre 4 threads e distribui o trabalho entre elas
./paralelo
Objetivo¶
Paralelizar laços com OpenMP, comparar o efeito de schedule
no desempenho.
Tarefa A - Map: transformação elemento-a-elemento¶
Solicitações de Implementação
- Paralelize o código correspondente a Tarefa A.
- Registre tempo e valor da conta em 3 execuções para cada
OMP_SCHEDULE = static
,dynamic
,guided
. - O que está sendo paralelizado nesse for? O que está sendo distribuido entre as threads?
Tarefa B - Redução ingênua: soma de quadrados¶
Solicitações de Implementação
- Paralelize o código correspondente a Tarefa B.
- Registre tempo e valor da soma em 3 execuções para cada
OMP_SCHEDULE = static
,dynamic
,guided
. - Compare com a execução sequencial (threads=1).
- O que está sendo paralelizado nesse for? O que está sendo distribuido entre as threads?
Coleta de Resultados (mínimo)¶
- Tabela tempos (Parte 1):
scheduler
,execução
,tempo (s)
. - Tabela tempos (Parte 2):
schedule
,threads
,média (s)
,desvio
. - Tabela soma (Parte 3):
schedule
,tempo (s)
,soma obtida
.
Parâmetros de Execução¶
- Varie
OMP_NUM_THREADS
em {1, 2, 4, 8} (quando solicitado). - Mantenha os mesmos N (tamanho do problema) em todas as comparações do mesmo grupo.
Perguntas de Análise
- Houve speedup com mais threads? Até onde?
static
vsdynamic
vsguided
: quem foi melhor? Alguma diferença relevante?- Alguma mudança no resultado das contas?
Faça um relatório com as suas análises e entregue até as 23h59 de 28/08 pelo GitHub Classroom