Estou atormentando meu cérebro há uma semana tentando concluir essa tarefa e espero que alguém aqui possa me levar ao caminho certo. Deixe-me começar com as instruções do instrutor:

Sua tarefa é o oposto de nossa primeira tarefa de laboratório, que era otimizar um programa de números primos. Seu objetivo nesta tarefa é pessimizar o programa, ou seja, torná-lo mais lento. Ambos são programas com uso intenso de CPU. Eles levam alguns segundos para serem executados em nossos computadores de laboratório. Você não pode alterar o algoritmo.

Para desoptimizar o programa, use seu conhecimento de como o pipeline Intel i7 opera. Imagine maneiras de reordenar os caminhos das instruções para introduzir WAR, RAW e outros perigos. Pense em maneiras de minimizar a eficácia do cache. Seja diabolicamente incompetente.

A tarefa deu uma escolha de programas Whetstone ou Monte-Carlo. Os comentários sobre a eficácia do cache são aplicáveis ​​apenas ao Whetstone, mas eu escolhi o programa de simulação de Monte-Carlo:

// Un-modified baseline for pessimization, as given in the assignment
#include <algorithm>    // Needed for the "max" function
#include <cmath>
#include <iostream>

// A simple implementation of the Box-Muller algorithm, used to generate
// gaussian random numbers - necessary for the Monte Carlo method below
// Note that C++11 actually provides std::normal_distribution<> in 
// the <random> library, which can be used instead of this function
double gaussian_box_muller() {
  double x = 0.0;
  double y = 0.0;
  double euclid_sq = 0.0;

  // Continue generating two uniform random variables
  // until the square of their "euclidean distance" 
  // is less than unity
  do {
    x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1;
    euclid_sq = x*x + y*y;
  } while (euclid_sq >= 1.0);

  return x*sqrt(-2*log(euclid_sq)/euclid_sq);
}

// Pricing a European vanilla call option with a Monte Carlo method
double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(S_cur - K, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

// Pricing a European vanilla put option with a Monte Carlo method
double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) {
  double S_adjust = S * exp(T*(r-0.5*v*v));
  double S_cur = 0.0;
  double payoff_sum = 0.0;

  for (int i=0; i<num_sims; i++) {
    double gauss_bm = gaussian_box_muller();
    S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm);
    payoff_sum += std::max(K - S_cur, 0.0);
  }

  return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T);
}

int main(int argc, char **argv) {
  // First we create the parameter list                                                                               
  int num_sims = 10000000;   // Number of simulated asset paths                                                       
  double S = 100.0;  // Option price                                                                                  
  double K = 100.0;  // Strike price                                                                                  
  double r = 0.05;   // Risk-free rate (5%)                                                                           
  double v = 0.2;    // Volatility of the underlying (20%)                                                            
  double T = 1.0;    // One year until expiry                                                                         

  // Then we calculate the call/put values via Monte Carlo                                                                          
  double call = monte_carlo_call_price(num_sims, S, K, r, v, T);
  double put = monte_carlo_put_price(num_sims, S, K, r, v, T);

  // Finally we output the parameters and prices                                                                      
  std::cout << "Number of Paths: " << num_sims << std::endl;
  std::cout << "Underlying:      " << S << std::endl;
  std::cout << "Strike:          " << K << std::endl;
  std::cout << "Risk-Free Rate:  " << r << std::endl;
  std::cout << "Volatility:      " << v << std::endl;
  std::cout << "Maturity:        " << T << std::endl;

  std::cout << "Call Price:      " << call << std::endl;
  std::cout << "Put Price:       " << put << std::endl;

  return 0;
}

As alterações que fiz pareciam aumentar o tempo de execução do código em um segundo, mas não sei ao certo o que posso alterar para interromper o pipeline sem adicionar código. Um ponto na direção certa seria incrível, agradeço qualquer resposta.

Atualização: o professor que atribuiu esta tarefa publicou alguns detalhes

Os destaques são:

• É uma aula de arquitetura do segundo semestre de uma faculdade comunitária (usando o livro de Hennessy e Patterson).
• os computadores de laboratório têm CPUs Haswell
• Os alunos foram expostos às CPUIDinstruções e como determinar o tamanho do cache, bem como intrínsecas e CLFLUSHinstruções.
• quaisquer opções do compilador são permitidas, assim como asm inline.
• Escrever o seu próprio algoritmo de raiz quadrada foi anunciado como estando fora do claro

Os comentários de Cowmoogun sobre o meta thread indicam que não estava claro que otimizações do compilador pudessem fazer parte disso, e assumiu-O0 , e que um aumento de 17% no tempo de execução era razoável.

Parece que o objetivo da tarefa era fazer com que os alunos reordenassem o trabalho existente para reduzir o paralelismo no nível da instrução ou coisas assim, mas não é uma coisa ruim que as pessoas tenham se aprofundado e aprendido mais.

Lembre-se de que esta é uma questão de arquitetura de computador, não uma questão sobre como tornar o C ++ lento em geral.

Leitura de fundo importante: o microarquivo pdf de Agner Fog e provavelmente também o que todo programador deve saber sobre memória, de Ulrich Drepper. Veja também os outros links nox86 tag wiki, especialmente os manuais de otimização da Intel e os de David Kanter análise de microarquitetura Haswell, com diagramas .

Tarefa muito legal; muito melhor do que aqueles que vi onde os alunos foram solicitados a otimizar algum códigogcc -O0 , aprendendo vários truques que não importam em código real. Nesse caso, você está sendo solicitado a aprender sobre o pipeline da CPU e usá-lo para orientar seus esforços de des otimização, não apenas para adivinhar às cegas. A parte mais divertida disso é justificar cada pessimização com "incompetência diabólica", não com malícia intencional.

Problemas com a redação e o código da tarefa :

As opções específicas do uarch para este código são limitadas. Ele não usa nenhuma matriz, e grande parte do custo é de chamadas paraexplog funções da / library. Não há uma maneira óbvia de ter mais ou menos paralelismo no nível de instrução, e a cadeia de dependência transportada por loop é muito curta.

Eu adoraria ver uma resposta que tentasse desacelerar ao reorganizar as expressões para alterar as dependências e reduzir o ILP da apenas das dependências (riscos). Eu não tentei.

As CPUs da família Intel Sandybridge são projetos agressivos e fora de ordem, que gastam muitos transistores e energia para encontrar paralelismo e evitar perigos (dependências) que poderiam incomodar um pipeline RISC clássico em ordem . Normalmente, os únicos riscos tradicionais que diminuem a velocidade são as dependências RAW "verdadeiras" que fazem com que a taxa de transferência seja limitada pela latência.

Os riscos de WAR e WAW para registros não são praticamente um problema, graças à renomeação de registros . (exceto parapopcnt/lzcnt/tzcnt, que tem uma dependência falsa como destino nos CPUs Intel , mesmo que seja somente para gravação. ou seja, WAW sendo tratado como um risco RAW + uma gravação). Para o pedido de memória, as CPUs modernas usam filas de armazenamento para atrasar a confirmação no cache até a aposentadoria, evitando também os riscos WAR e WAW .

Por que os mulss levam apenas 3 ciclos em Haswell, diferente das tabelas de instruções de Agner? tem mais informações sobre como renomear registradores e ocultar a latência FMA em um loop de produto de ponto FP.

O nome da marca "i7" foi introduzido com Nehalem (sucessor do Core2) , e alguns manuais da Intel dizem "Core i7" quando parecem significar Nehalem, mas mantiveram a marca "i7" para Sandybridge e microarquiteturas posteriores. SnB é quando a família P6 evoluiu para uma nova espécie, a família SnB . De muitas maneiras, Nehalem tem mais em comum com o Pentium III do que com o Sandybridge (por exemplo, paradas de leitura de registro e paradas de leitura de ROB não ocorrem no SnB, porque mudou para o uso de um arquivo de registro físico. Também um cache uop e um interno interno diferente uop). O termo "arquitetura i7" não é útil, porque faz pouco sentido agrupar a família SnB com Nehalem, mas não com o Core2. (A Nehalem introduziu a arquitetura de cache L3 inclusiva compartilhada para conectar vários núcleos juntos. E também GPUs integradas. Portanto, no nível de chip, a nomeação faz mais sentido.)

Resumo das boas idéias que a incompetência diabólica pode justificar

É improvável que mesmo os diabolicamente incompetentes adicionem trabalho obviamente inútil ou um loop infinito, e fazer uma bagunça com as classes C ++ / Boost está além do escopo da tarefa.

• Multiencadeamento com um único contador de loop compartilhado std::atomic<uint64_t> , para que o número total certo de iterações aconteça. O uint64_t atômico é especialmente ruim com -m32 -march=i586. Para obter pontos de bônus, organize o desalinhamento e cruze o limite da página com uma divisão desigual (e não 4: 4).
• O compartilhamento falso de algumas outras variáveis ​​não atômicas -> o pipeline de especulação incorreta da ordem da memória é limpo, além de falhas adicionais de cache.
• Em vez de usar -nas variáveis ​​FP, XOR o byte alto com 0x80 para inverter o bit de sinal, causando paradas de encaminhamento de loja .
• Cronometre cada iteração independentemente, com algo ainda mais pesado que RDTSC. por exemplo, CPUID/ RDTSCou uma função de hora que faz uma chamada do sistema. As instruções de serialização são inerentemente hostis ao pipeline.
• Alterar multiplica por constantes para dividir por suas recíprocas ("para facilitar a leitura"). div é lento e não está totalmente em pipeline.
• Vectorize a multiplicação / sqrt com o AVX (SIMD), mas falhe ao usar vzeroupperantes das chamadas para a biblioteca exp()e log()funções matemáticas escalares , causando paradas de transição do SSE do AVX <-> SSE .
• Armazene a saída RNG em uma lista vinculada ou em matrizes que você percorre fora de ordem. O mesmo para o resultado de cada iteração e soma no final.

Também coberto nesta resposta, mas excluído do resumo: sugestões que seriam tão lentas em uma CPU sem pipeline ou que não parecem justificáveis ​​mesmo com a incompetência diabólica. por exemplo, muitas idéias do gimp-the-compiler que produzem obviamente diferentes / piores condições.

Multi-thread mal

Talvez use o OpenMP para loops multithread com muito poucas iterações, com muito mais sobrecarga do que ganho de velocidade. Seu código monte-carlo tem paralelismo suficiente para obter uma aceleração, no entanto, esp. se conseguirmos tornar cada iteração lenta. (Cada thread calcula uma parcial payoff_sum, adicionada no final). #omp parallelnesse loop provavelmente seria uma otimização, não uma pessimização.

Multiencadeamento, mas force os dois segmentos a compartilhar o mesmo contador de loop (com atomicincrementos para que o número total de iterações esteja correto). Isso parece diabolicamente lógico. Isso significa usar uma staticvariável como um contador de loop. Isso justifica o uso de atomiccontadores de loop for e cria ping-ponging real na linha de cache (desde que os threads não sejam executados no mesmo núcleo físico com hyperthreading; isso pode não ser tão lento). De qualquer forma, isso é muito mais lento do que o argumento não discutido lock inc. E lock cmpxchg8bpara incrementar atomicamente um contend uint64_tem um sistema de 32 bits, será necessário tentar novamente em um loop, em vez de o hardware arbitrar um atômico inc.

Crie também um compartilhamento falso , em que vários encadeamentos mantêm seus dados privados (por exemplo, estado RNG) em diferentes bytes da mesma linha de cache. (Tutorial da Intel sobre o assunto, incluindo os contadores de desempenho a serem observados) . Há um aspecto específico da microarquitetura : as CPUs Intel especulam que a falta de pedidos de memória não está acontecendo e há um evento perf de limpeza da máquina para detectar isso, pelo menos no P4 . A penalidade pode não ser tão grande em Haswell. Como esse link indica, uma lockinstrução ed assume que isso acontecerá, evitando erros de especulação. Uma carga normal especula que outros núcleos não invalidarão uma linha de cache entre o momento em que a carga é executada e a retirada em ordem de programa (a menos que você usepause ). O compartilhamento verdadeiro sem lockinstruções de edição geralmente é um bug. Seria interessante comparar um contador de loop compartilhado não atômico com o caso atômico. Para realmente pessimizar, mantenha o contador de loop atômico compartilhado e cause um compartilhamento falso na mesma ou em uma linha de cache diferente para alguma outra variável.

Idéias aleatórias específicas do uarch:

Se você puder introduzir ramificações imprevisíveis , isso reduzirá substancialmente o código. As CPUs x86 modernas têm pipelines bastante longos, portanto, uma previsão incorreta custa ~ 15 ciclos (quando executada no cache uop).

Cadeias de dependência:

Eu acho que essa foi uma das partes pretendidas da tarefa.

Derrote a capacidade da CPU de explorar o paralelismo no nível de instruções, escolhendo uma ordem de operações que possua uma longa cadeia de dependência em vez de várias cadeias curtas de dependência. Os compiladores não têm permissão para alterar a ordem das operações dos cálculos de FP, a menos que você use -ffast-math, porque isso pode alterar os resultados (conforme discutido abaixo).

Para realmente tornar isso eficaz, aumente o comprimento de uma cadeia de dependência transportada por loop. Porém, nada é tão óbvio: os loops escritos têm cadeias de dependência muito curtas e carregadas em loop: apenas um complemento de FP. (3 ciclos). Várias iterações podem ter seus cálculos em andamento ao mesmo tempo, porque podem começar bem antes payoff_sum +=do final da iteração anterior. ( log()e expsiga muitas instruções, mas não muito mais do que a janela fora de ordem de Haswell para encontrar paralelismo: tamanho do ROB = 192 uops de domínio fundido e tamanho do planejador = 60 uops de domínio não fundido. Assim que a execução da iteração atual progride o suficiente para liberar espaço para que as instruções da próxima iteração sejam emitidas, qualquer parte dela que tenha suas entradas prontas (por exemplo, cadeia de dep independente / separada) poderá começar a executar quando instruções mais antigas deixarem as unidades de execução grátis (por exemplo, porque estão com gargalo na latência, não na taxa de transferência).

O estado RNG quase certamente será uma cadeia de dependência mais longa do que a addps.

Use operações de FP mais lentas / mais (especialmente mais divisão):

Divida por 2,0 em vez de multiplicar por 0,5 e assim por diante. A multiplicação de FP é fortemente canalizada nos projetos da Intel e tem uma taxa de transferência de 0,5 por cento na Haswell e mais tarde. FP divsd/ divpdé canalizado apenas parcialmente . (Embora a Skylake tenha uma taxa de transferência impressionante por 4c divpd xmm, com latência de 13 a 14c, em comparação com nenhum canal em Nehalem (7-22c)).

A do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0);é claramente testando para uma distância, de forma tão clara que seria adequado para sqrt()ele. : P ( sqrté ainda mais lento que div).

Como @Paul Clayton sugere, reescrever expressões com equivalentes associativos / distributivos pode introduzir mais trabalho (desde que você não use -ffast-mathpara permitir que o compilador otimize novamente). (exp(T*(r-0.5*v*v))poderia se tornar exp(T*r - T*v*v/2.0). Observe que, embora a matemática em números reais seja associativa, a matemática em ponto flutuante não é , mesmo sem considerar o estouro / NaN (é por isso que -ffast-mathnão está ativado por padrão). Veja o comentário de Paulo para uma pow()sugestão aninhada muito peluda .

Se você pode escalar os cálculos para números muito pequenos, as operações matemáticas de FP levam ~ 120 ciclos extras para capturar o microcódigo quando uma operação em dois números normais produz um estado anormal . Consulte o pdf da microarca de Agner Fog para obter os números e detalhes exatos. Isso é improvável, pois você tem muitas multiplicações; portanto, o fator de escala seria elevado ao quadrado e estouraria até 0,0. Não vejo como justificar a escala necessária com incompetência (mesmo diabólica), apenas com malícia intencional.

Se você pode usar intrínsecos ( <immintrin.h>)

Use movntipara remover seus dados do cache . Diabólico: é novo e com uma ordem fraca, de modo que deve permitir que a CPU o execute mais rápido, certo? Ou veja a pergunta vinculada para um caso em que alguém corria o risco de fazer exatamente isso (para gravações dispersas em que apenas alguns dos locais estavam quentes). clflushprovavelmente é impossível sem malícia.

Use embaralhamento inteiro entre operações matemáticas de FP para causar atrasos no desvio.

A mistura de instruções SSE e AVX sem o uso adequado de vzerouppercausas causa grandes paradas no pré-Skylake (e uma penalidade diferente no Skylake ). Mesmo sem isso, vetorizar mal pode ser pior que escalar (mais ciclos gastos embaralhando dados para dentro / fora de vetores do que salvos executando as operações add / sub / mul / div / sqrt para 4 iterações de Monte-Carlo de uma só vez, com 256b vetores) . as unidades de execução add / sub / mul são totalmente pipelines e de largura total, mas div e sqrt em vetores 256b não são tão rápidos quanto em vetores 128b (ou escalares), portanto, a aceleração não é dramáticadouble.

exp()e log()não possui suporte de hardware, de modo que essa parte exigiria a extração de elementos vetoriais de volta ao escalar e a chamada da função de biblioteca separadamente, e a reprodução dos resultados em um vetor. A libm geralmente é compilada para usar apenas o SSE2, portanto, as codificações legadas-SSE das instruções matemáticas escalares. Se o seu código usa vetores e chamadas de 256b expsem vzeroupperprimeiro, você está parado. Depois de retornar, uma instrução AVX-128 como vmovsdconfigurar o próximo elemento vetorial como um argumento para exptambém será interrompida. E, em seguida, exp()irá parar novamente quando executar uma instrução SSE. Foi exatamente o que aconteceu nesta pergunta , causando uma desaceleração de 10x. (Obrigado @ZBoson).

Veja também os experimentos de Nathan Kurz com a lib de matemática da Intel vs. glibc para esse código . O glibc futuro virá com implementações vetorizadas exp()e assim por diante.

Se segmentar pré-IvB, ou esp. Nehalem, tente fazer com que o gcc cause paradas parciais no registro com operações de 16 bits ou 8 bits, seguidas pelas operações de 32 ou 64 bits. Na maioria dos casos, o gcc será usado movzxapós uma operação de 8 ou 16 bits, mas aqui está um caso em que o gcc modifica ahe depois lêax

Com (inline) asm:

Com (inline) asm, você pode interromper o cache uop: um pedaço de código de 32B que não se encaixa em três linhas de cache 6uop força uma troca do cache uop para os decodificadores. Um incompetente ALIGNusando muitos bytes simples em nopvez de alguns longos nops em um destino de ramificação dentro do loop interno pode fazer o truque. Ou coloque o preenchimento de alinhamento após o rótulo, em vez de antes. : P Isso só importa se o frontend for um gargalo, o que não acontecerá se conseguirmos pessimizar o restante do código.

Use o código de modificação automática para ativar a limpeza de pipeline (também conhecida como nukees de máquinas).

É improvável que o LCP pare de instruções de 16 bits com imediatos grandes demais para caber em 8 bits. O cache uop no SnB e posterior significa que você paga a penalidade de decodificação apenas uma vez. No Nehalem (o primeiro i7), ele pode funcionar para um loop que não cabe no buffer de loop de 28 uop. O gcc às vezes gera essas instruções, mesmo com -mtune=intele quando poderia ter usado uma instrução de 32 bits.

Um idioma comum para o tempo é CPUID(serializar) entãoRDTSC . Tempo cada iteração separadamente com um CPUID/ RDTSCpara garantir que o RDTSCnão é reordenada com instruções anteriores, que irá retardar as coisas um monte . (Na vida real, a maneira inteligente de cronometrar é cronometrar todas as iterações juntas, em vez de cronometrar cada uma separadamente e adicioná-las).

Causar muitas falhas de cache e outras lentidões de memória

Use a union { double d; char a[8]; }para algumas de suas variáveis. Cause um bloqueio de encaminhamento de loja executando um armazenamento restrito (ou Read-Modify-Write) em apenas um dos bytes. (Esse artigo da wiki também cobre muitas outras coisas microarquiteturais para filas de carregamento / armazenamento). por exemplo, vire o sinal de um doubleXOR 0x80 usando apenas o byte alto , em vez de um -operador. O desenvolvedor diabolicamente incompetente pode ter ouvido que o FP é mais lento que o número inteiro e, portanto, tenta fazer o máximo possível usando operações com números inteiros. (Um compilador muito bom visando a matemática FP em registros SSE pode compilar isso em umxorps com uma constante em outro registro xmm, mas a única maneira que isso não é terrível para o x87 é se o compilador perceber que está negando o valor e substituir o próximo complemento por uma subtração.)

Use volatilese você estiver compilando com -O3ou não std::atomic, para forçar o compilador a realmente armazenar / recarregar em todo o lugar. Variáveis ​​globais (em vez de locais) também forçarão alguns armazenamentos / recarregamentos, mas a ordem fraca do modelo de memória C ++ não exige que o compilador derrame / recarregue na memória o tempo todo.

Substitua vars locais por membros de uma grande estrutura, para que você possa controlar o layout da memória.

Use matrizes na estrutura para preenchimento (e armazenamento de números aleatórios, para justificar sua existência).

Escolha seu layout de memória para que tudo entre em uma linha diferente no mesmo "conjunto" no cache L1 . É apenas associativo de 8 vias, ou seja, cada conjunto possui 8 "maneiras". Linhas de cache são 64B.

Melhor ainda, coloque as coisas exatamente em 4096B, uma vez que as cargas têm uma dependência falsa nas lojas para páginas diferentes, mas com o mesmo deslocamento em uma página . As CPUs agressivas e fora de ordem usam a Desambiguação de memória para descobrir quando as cargas e os armazenamentos podem ser reordenados sem alterar os resultados , e a implementação da Intel possui falsos positivos que impedem o início antecipado das cargas. Provavelmente, eles apenas verificam os bits abaixo do deslocamento da página, para que a verificação possa começar antes que o TLB traduza os bits altos de uma página virtual para uma página física. Além do guia de Agner, consulte uma resposta de Stephen Canon e também uma seção perto do final da resposta de @Krazy Glew sobre a mesma pergunta. (Andy Glew foi um dos arquitetos da microarquitetura P6 original da Intel.)

Use __attribute__((packed))para permitir o desalinhamento de variáveis ​​para que elas abranjam os limites da linha de cache ou mesmo da página. (Então, uma carga de umdouble precisa de dados de duas linhas de cache). Cargas desalinhadas não têm penalidade em nenhum uarch Intel i7, exceto ao cruzar linhas de cache e linhas de página. As divisões da linha de cache ainda levam ciclos extras . O Skylake reduz drasticamente a penalidade para cargas de divisão de página, de 100 para 5 ciclos. (Seção 2.1.3) . Talvez relacionado à capacidade de fazer duas caminhadas de página em paralelo.

Uma divisão de página em um atomic<uint64_t>deve ser o pior caso , esp. se tiver 5 bytes em uma página e 3 bytes na outra página ou qualquer coisa que não seja 4: 4. Mesmo divisões no meio são mais eficientes para divisões de linhas de cache com vetores 16B em alguns uarches, IIRC. Coloque tudo em um alignas(4096) struct __attribute((packed))(para economizar espaço, é claro), incluindo uma matriz para armazenamento dos resultados RNG. Atingir o desalinhamento usando uint8_tou uint16_tpara algo antes do balcão.

Se você conseguir que o compilador use modos de endereçamento indexado, isso derrotará a micro fusão . Talvez usando #defines para substituir variáveis ​​escalares simples por my_data[constant].

Se você pode introduzir um nível extra de indireção, para que os endereços de carregamento / armazenamento não sejam conhecidos desde o início, isso pode ser mais pessimista.

Atravessar matrizes em ordem não contígua

Acho que podemos apresentar uma justificativa incompetente para introduzir uma matriz em primeiro lugar: permite separar a geração de números aleatórios do uso de números aleatórios. Os resultados de cada iteração também podem ser armazenados em uma matriz, para serem somados posteriormente (com mais incompetência diabólica).

Para "aleatoriedade máxima", poderíamos ter um thread em loop sobre o array aleatório escrevendo novos números aleatórios nele. O encadeamento que consome os números aleatórios pode gerar um índice aleatório para carregar um número aleatório. (Há algumas obras aqui, mas na microarquitetura ajuda a conhecer os endereços de carregamento com antecedência, para que qualquer latência de carga possível possa ser resolvida antes que os dados carregados sejam necessários.) O pipeline de especulação é limpo (conforme discutido anteriormente para o caso de compartilhamento falso).

Para máxima pessimização, faça um loop sobre sua matriz com um passo de 4096 bytes (ou seja, 512 duplos). por exemplo

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

Portanto, o padrão de acesso é 0, 4096, 8192, ...,
8, 4104, 8200, ...
16, 4112, 8208, ...

Isso é o que você obteria ao acessar uma matriz 2D como double rng_array[MAX_ROWS][512] na ordem errada (fazendo um loop sobre linhas, em vez de colunas dentro de uma linha no loop interno, conforme sugerido por @JesperJuhl). Se a incompetência diabólica pode justificar uma matriz 2D com dimensões assim, a incompetência do mundo real da variedade de jardins justifica facilmente o loop com o padrão de acesso errado. Isso acontece no código real na vida real.

Ajuste os limites do loop, se necessário, para usar muitas páginas diferentes, em vez de reutilizar as mesmas poucas páginas, se a matriz não for tão grande. A pré-busca de hardware não funciona (também / de todo) nas páginas. O pré-buscador pode rastrear um fluxo para frente e para trás dentro de cada página (o que acontece aqui), mas só atuará se a largura de banda da memória ainda não estiver saturada com a não-busca prévia.

Isso também gerará muitas falhas de TLB, a menos que as páginas sejam mescladas em uma página enorme (o Linux faz isso oportunisticamente para alocações anônimas (sem backup de arquivos) como malloc/ newque usammmap(MAP_ANONYMOUS) ).

Em vez de uma matriz para armazenar a lista de resultados, você pode usar uma lista vinculada . Então, toda iteração exigiria uma carga de perseguição de ponteiro (um verdadeiro risco de dependência RAW para o endereço de carga da próxima carga). Com um alocador incorreto, você pode conseguir dispersar os nós da lista na memória, derrotando o cache. Com um alocador diabolicamente incompetente, ele poderia colocar todos os nós no início de sua própria página. (por exemplo, aloque mmap(MAP_ANONYMOUS)diretamente, sem quebrar páginas ou rastrear tamanhos de objetos para dar suporte adequado free).

Elas não são realmente específicas da microarquitetura e têm pouco a ver com o pipeline (a maioria delas também seria uma desaceleração em uma CPU sem pipeline).

Um pouco fora do tópico: faça o compilador gerar código pior / faça mais trabalho:

Use C ++ 11 std::atomic<int>e std::atomic<double>para o código mais pessimal. As MFENCEs e as lockinstruções ed são bastante lentas, mesmo sem contenção de outro encadeamento.

-m32tornará o código mais lento, porque o código x87 será pior que o código SSE2. A convenção de chamada de 32 bits baseada em pilha leva mais instruções e passa até argumentos de FP na pilha para funções como exp(). atomic<uint64_t>::operator++on -m32requer um lock cmpxchg8Bloop (i586). (Então use isso para contadores de loops! [Risada maligna]).

-march=i386também pessimize (obrigado @Jesper). O FP compara com fcommais lento que 686 fcomi. O pré-586 não fornece um armazenamento atômico de 64 bits (e muito menos um cmpxchg), portanto, todos os sistemas de 64 bitsatomic operações de compiladas com as chamadas de função libgcc (que provavelmente são compiladas para o i686, em vez de usar um bloqueio). Experimente no link do Godbolt Compiler Explorer no último parágrafo.

Use long double/ sqrtl/ explpara precisão extra e lentidão extra nas ABIs em que sizeof ( long double) é 10 ou 16 (com preenchimento para alinhamento). (IIRC, Windows de 64 bits usa 8 bytes long doubleequivalentes a double. (De qualquer forma, a carga / armazenamento de operandos FP de 10 bytes (80 bits) é de 4/7 uops, contra floatou doubleleva apenas 1 uop cada para fld m64/m32/ fst). Forçar x87 com long doublederrotas na vetor automática, mesmo gcc -m64 -march=haswell -O3.

Se não estiver usando atomic<uint64_t>contadores de loop, use long doublepara tudo, inclusive contadores de loop.

atomic<double>compila, mas operações de leitura, modificação e gravação como +=não são suportadas (mesmo em 64 bits). atomic<long double>precisa chamar uma função de biblioteca apenas para cargas / lojas atômicas. Provavelmente é realmente ineficiente, porque o x86 ISA não suporta naturalmente cargas / lojas atômicas de 10 bytes , e a única maneira de pensar sem bloquear ( cmpxchg16b) requer o modo de 64 bits.

Em -O0, dividir uma grande expressão atribuindo peças a vars temporários causará mais armazenamento / recarregamentos. Sem volatileou algo assim, isso não importa com as configurações de otimização que uma compilação real de código real usaria.

As regras de aliasing permitem chara alias qualquer coisa, então armazenar através de uma char*força o compilador a armazenar / recarregar tudo antes / depois do byte-store, mesmo em -O3. (Esse é um problema para o código deuint8_t vetorização automática que opera em uma matriz de , por exemplo.)

Tente uint16_tcontadores de loop, para forçar o truncamento para 16 bits, provavelmente usando o tamanho de operando de 16 bits (possíveis interrupções) e / ou movzxinstruções extras (seguras). O excesso de sinal assinado é um comportamento indefinido , portanto, a menos que você use, -fwrapvou pelo menos -fno-strict-overflow, os contadores de loop assinados não precisam ser estendidos novamente a cada iteração , mesmo se usados ​​como compensações para ponteiros de 64 bits.

Força a conversão de número inteiro para floate vice-versa. E / ou double<=> floatconversões. As instruções têm latência maior que uma e o escalar int-> float ( cvtsi2ss) foi mal projetado para não zerar o restante do registro xmm. (o gcc insere um extra pxorpara quebrar dependências, por esse motivo.)

Defina frequentemente a afinidade da sua CPU para uma CPU diferente (sugerida por @Egwor). raciocínio diabólico: você não quer que um núcleo fique superaquecido ao executar seu thread por um longo tempo, não é? Talvez a troca para outro núcleo permita que o núcleo turbo atinja uma velocidade de clock mais alta. (Na realidade: eles são tão termicamente próximos um do outro que é altamente improvável, exceto em um sistema com vários soquetes). Agora, apenas entenda errado o ajuste e faça-o com muita frequência. Além do tempo gasto no estado de thread de economia / restauração do SO, o novo núcleo possui caches L2 / L1 frios, cache uop e preditores de ramificação.

A introdução frequente de chamadas desnecessárias do sistema pode atrasá-lo, não importa o que sejam. Embora alguns importantes, porém simples, como este gettimeofdaypossam ser implementados no espaço do usuário, sem transição para o modo kernel. (o glibc no Linux faz isso com a ajuda do kernel, pois o kernel exporta código no vdso).

Para obter mais informações sobre a sobrecarga de chamadas do sistema (incluindo falhas de cache / TLB após retornar ao espaço do usuário, não apenas a troca de contexto em si), o artigo do FlexSC possui uma excelente análise de desempenho da situação atual, bem como uma proposta para sistema de lotes. chamadas de processos massivos de servidores multithread.

Algumas coisas que você pode fazer para que as coisas tenham o pior desempenho possível:

• compile o código para a arquitetura i386. Isso impedirá o uso do SSE e de instruções mais recentes e forçará o uso do FP87 x87.

• use std::atomicvariáveis ​​em qualquer lugar. Isso os tornará muito caros, porque o compilador é forçado a inserir barreiras de memória em todo o lugar. E isso é algo que uma pessoa incompetente pode fazer de maneira plausível para "garantir a segurança do thread".

• certifique-se de acessar a memória da pior maneira possível para o pré-buscador prever (coluna maior vs linha maior).

• para tornar suas variáveis ​​mais caras, você pode garantir que todas tenham 'duração dinâmica de armazenamento' (heap alocado) alocando-as com, em newvez de permitir que elas tenham 'duração automática de armazenamento' (pilha alocada).

• certifique-se de que toda a memória que você aloca esteja muito estranhamente alinhada e evite alocar páginas enormes, pois isso seria muito eficiente em TLB.

• faça o que fizer, não crie seu código com o otimizador de compiladores ativado. E certifique-se de permitir que os símbolos de depuração expressivos máximo que você pode (não vai fazer o código de execução mais lento, mas vai perder algum espaço em disco extra).

Nota: Esta resposta basicamente resume meus comentários que @ Peter Cordes já incorporou em sua resposta muito boa. Sugira que ele receba seu voto se você tiver apenas um de sobra :)

Você pode usar long doublepara computação. No x86, deve ser o formato de 80 bits. Somente o FPU x87 legado tem suporte para isso.

Poucas deficiências da FP87 x87:

1. Falta de SIMD, pode precisar de mais instruções.
2. Baseado em pilha, problemático para arquiteturas super escalares e em pipeline.
3. Conjunto de registros separado e muito pequeno, pode precisar de mais conversão de outros registros e mais operações de memória.
4. No Core i7, existem 3 portas para SSE e apenas 2 para x87, o processador pode executar instruções menos paralelas.

Resposta tardia, mas não acho que tenhamos abusado de listas vinculadas e do TLB o suficiente.

Use mmap para alocar seus nós, de modo que você use principalmente o MSB do endereço. Isso deve resultar em longas cadeias de pesquisa TLB, uma página tem 12 bits, deixando 52 bits para a tradução ou cerca de 5 níveis que ela deve percorrer a cada vez. Com um pouco de sorte, eles precisam ir para a memória todas as vezes para pesquisar 5 níveis mais 1 acesso à memória para chegar ao seu nó, o nível superior provavelmente estará no cache em algum lugar, para que possamos ter acesso à memória 5 *. Posicione o nó de maneira que seja a pior borda, para que a leitura do próximo ponteiro cause outras pesquisas de tradução de 3 a 4. Isso também pode destruir totalmente o cache devido à grande quantidade de pesquisas de tradução. Além disso, o tamanho das tabelas virtuais pode fazer com que a maioria dos dados do usuário seja paginada em disco para um tempo extra.

Ao ler da lista vinculada única, certifique-se de ler o início da lista todas as vezes para causar atraso máximo na leitura de um único número.