Por que a divisão é muito mais complexa do que outras operações aritméticas?

Recentemente, encontrei um caso em que precisava de uma operação de divisão inteira em um chip que não possuía um (ARM Cortex-A8). Enquanto tentava pesquisar por que isso deveria ser, descobri que na divisão geral são necessários muito mais ciclos do que adição, subtração ou multiplicação em praticamente qualquer arquitetura inteira (ou ponto fixo). Por que esse é o caso? Não é representável com uma lógica AND-OR de duas camadas, como todo o resto?

Divisão é um algoritmo iterativo em que o resultado do quociente deve ser deslocado para o restante usando uma medida euclidiana, veja 2 ; enquanto que a multiplicação pode ser reduzida a uma série (fixa) de truques de manipulação de bits.

Embora todas as CPUs atuais pareçam usar uma abordagem iterativa, como o aterrel sugere , houve algum trabalho realizado em abordagens não iterativas. Divisão de ponto flutuante de precisão variável e raiz quadrada fala sobre uma implementação não iterativa de divisão de ponto flutuante e raiz quadrada em um FPGA , usando tabelas de pesquisa e expansão da série taylor.

Suspeito que as mesmas técnicas possam tornar essas operações reduzidas a um único ciclo (taxa de transferência, se não latência), mas é provável que você precise de grandes tabelas de pesquisa e, portanto, áreas imensamente grandes de imóveis de silício para fazer isso .

Por que não seria viável?

Ao projetar CPUs, há muitas vantagens e desvantagens. Funcionalidade, complexidade (número de transistores), velocidade e consumo de energia estão inter-relacionados e as decisões tomadas durante o projeto podem causar um enorme impacto no desempenho.

Um processador moderno provavelmente poderia ter uma unidade principal de ponto flutuante que dedique transistores suficientes no silício para executar uma divisão de ponto flutuante em um único ciclo , mas seria improvável que seja um uso eficiente desses transistores.

O ponto flutuante multiplicado fez essa transição de iterativo para não iterativo há uma década. Atualmente, a multiplicação de ciclo único e a acumulação de multiplicação são comuns, mesmo em processadores móveis.

Antes de se tornar um uso eficiente do orçamento do transistor, a multiplicação, como a divisão, era frequentemente realizada por um método iterativo. Naquela época, os processadores DSP dedicados podiam dedicar a maior parte de seu silício a uma única unidade rápida de multiplicação múltipla (MAC) . Uma CPU Core2duo possui uma latência de multiplicação de ponto flutuante de 3 (o valor sai do ciclo do pipeline 3 após a entrada), mas pode ter 3 multiplicações em voo ao mesmo tempo, resultando em uma taxa de transferência de ciclo único, enquanto a unidade SSE2 pode bombeie múltiplas multiplicações FP em um único ciclo.

Em vez de dedicar grandes áreas de silício a uma unidade de divisão de ciclo único, as CPUs modernas têm várias unidades, cada uma das quais pode executar operações em paralelo, mas são otimizadas para suas próprias situações específicas. De fato, depois de levar em conta as instruções do SIMD , como SSE ou os gráficos integrados à CPU do Sandy Bridge ou CPUs posteriores, pode haver muitas dessas unidades de divisão de ponto flutuante na sua CPU.

Se a divisão de ponto flutuante genérica fosse mais importante para as CPUs modernas, talvez faça sentido dedicar área de silício suficiente para torná-lo um ciclo único, no entanto, a maioria dos fabricantes de chips decidiu obviamente que pode fazer melhor uso desse silício usando esses portões para outras coisas. . Portanto, uma operação é mais lenta, mas no geral (para cenários de uso típico) a CPU é mais rápida e / ou consome menos energia.