Paralelismo em Nível de Instrução

O paralelismo em nível de instrução (ILP) é o potencial para executar múltiplas instruções de um único programa simultaneamente, explorado por processadores superescalares e VLIW que emitem e completam várias instruções por ciclo.

Definition

O paralelismo em nível de instrução é o grau em que as instruções de um único programa podem ser executadas em paralelo; os processadores o exploram emitindo, executando e completando mais de uma instrução por ciclo de clock, sujeitos a dependências de dados e controle.

Scope

Este tópico aborda o paralelismo disponível dentro de um único fluxo de instruções e como o hardware e os compiladores o extraem: emissão superescalar de múltiplas instruções por ciclo, projetos de palavra de instrução muito longa (VLIW), análise de dependência, renomeação de registradores e especulação. Também aborda os limites do ILP disponível. Exclui o paralelismo em nível de thread e de dados entre núcleos e pistas (arquitetura paralela e multicore) e o pipeline básico de emissão única (pipelining e hazards).

Core questions

• Quanto paralelismo está inerentemente disponível entre as instruções de um programa típico?
• Como os processadores superescalares decidem quais instruções podem ser emitidas juntas?
• Como os projetos VLIW transferem a carga de encontrar paralelismo para o compilador?
• Quais dependências e riscos limitam a quantidade de ILP que pode ser realizada?

Key concepts

• emissão superescalar
• palavra de instrução muito longa (VLIW)
• dependências de dados e nomes
• renomeação de registradores
• múltiplas unidades funcionais
• especulação
• limites de ILP
• instruções por ciclo (IPC)

Key theories

Agendamento dinâmico de instruções

O hardware pode descobrir e explorar o ILP em tempo de execução, rastreando dependências e agendando instruções prontas para múltiplas unidades funcionais; o algoritmo de Tomasulo, com estações de reserva e renomeação de registradores, é o mecanismo canônico que permite a emissão fora de ordem e paralela.

Mechanisms

Processadores superescalares buscam e decodificam várias instruções por ciclo, verificam suas dependências, renomeiam registradores para remover falsas dependências e emitem instruções independentes para múltiplas unidades funcionais. Os projetos VLIW, em vez disso, dependem do compilador para agrupar operações independentes em palavras de instrução amplas. As verdadeiras dependências de dados e o fluxo de controle estabelecem um limite superior para o paralelismo realizável, que a especulação e janelas de instrução maiores tentam estender.

Clinical relevance

As técnicas de ILP impulsionaram décadas de crescimento do desempenho de thread único e permanecem centrais para núcleos de CPU de alto desempenho. Seus retornos decrescentes — à medida que os limites de paralelismo e complexidade disponíveis foram atingidos — foram uma razão fundamental pela qual a indústria se voltou para multicore e paralelismo explícito para uma escalabilidade adicional.

History

Múltiplas unidades funcionais e agendamento dinâmico apareceram no CDC 6600 e no IBM System/360 Modelo 91 na década de 1960. Os projetos superescalares tornaram-se predominantes na década de 1990, e as arquiteturas VLIW, como o Itanium da Intel, buscaram o paralelismo impulsionado pelo compilador. Estudos dos limites do ILP no início da década de 1990 esclareceram por que o paralelismo dentro de um único thread é limitado.

Debates

ILP impulsionado por hardware versus impulsionado por compilador

O hardware superescalar fora de ordem encontra paralelismo dinamicamente ao custo de complexidade e energia, enquanto o VLIW depende do compilador para agendar o paralelismo estaticamente; a experiência mostrou que as abordagens dinâmicas são mais robustas em diferentes cargas de trabalho, enquanto as abordagens estáticas permanecem atraentes para projetos previsíveis e de baixa potência.

Key figures

• Robert Tomasulo
• Yale Patt
• John L. Hennessy
• Joseph A. Fisher
• James E. Smith

Seminal works

• hennessy2019
• tomasulo1967

Frequently asked questions

Qual é a diferença entre superescalar e VLIW?

Ambos executam múltiplas operações por ciclo. Um processador superescalar decide em hardware, em tempo de execução, quais instruções podem ser emitidas juntas; um processador VLIW depende do compilador para agrupar operações independentes em instruções amplas com antecedência, simplificando o hardware, mas exigindo mais do compilador.

Por que existe um limite para o paralelismo em nível de instrução?

Programas reais têm verdadeiras dependências de dados e ramificações frequentes que restringem quantas instruções podem ser executadas em paralelo. Além de uma certa janela, o paralelismo alcançável satura, então extrair mais ILP produz retornos decrescentes em relação à complexidade e energia adicionadas do hardware.