Os algoritmos são classificados na notação big-o afetada pelo paralelismo? - algoritmo, processamento paralelo, big-o

Acabei de ler um artigo sobre um avanço emmultiplicação da matriz; um algoritmo que é O (n ^ 2.373). Mas eu acho que a multiplicação de matrizes é algo que pode ser paralelizado. Então, se alguma vez começarmos a produzir processadores de milésimos núcleos, isso se tornará irrelevante? Como as coisas mudariam?

Respostas:

Se a computação quântica chegar a algo prático algum dia, então sim, a complexidade dos algoritmos mudará.

Enquanto isso, paralelizar um algoritmo, comum número fixo de processadores, justs divide seu tempo de execução proporcionalmente (e que, no melhor dos casos, quando não há dependências entre as tarefas executadas em cada processador). Isso significa dividir o tempo de execução por uma constante e, assim, a complexidade permanece a mesma.

A execução paralela não muda o básico dea complexidade de um algoritmo em particular - na melhor das hipóteses, você está apenas ocupando o tempo de um determinado tamanho e dividindo pelo número de núcleos. Isso pode reduzir o tempo de um determinado tamanho por um fator constante, mas não afeta o complexidade do algoritmo.

Ao mesmo tempo, a execução paralela às vezes muda qual algoritmo (s) que você deseja usar para tarefas específicas. Alguns algoritmos que funcionam bem em código serial simplesmente não se dividem em tarefas paralelas muito bem. Outros que têm maior complexidade pode ser mais rápido para problemas de tamanho prático, porque eles funcionam melhor em paralelo.

Para um número extremamente grande de núcleos, oA complexidade do cálculo em si pode tornar-se secundária a simplesmente obter os dados necessários de / para todos os núcleos para fazer o cálculo. a maioria dos cálculos de big-O não leva esses efeitos em consideração para um cálculo serial, mas pode se tornar muito importante para cálculos paralelos, especialmente para alguns modelos de máquinas paralelas que não fornecem acesso uniforme a todos os nós.

Por Lei de Amdahl, para o mesmo tamanho de problema, a paralelização chegará a um ponto dediminuindo o retorno com o aumento do número de núcleos (teoricamente). Na realidade, a partir de um certo grau de paralelização, a sobrecarga de paralelização realmente diminuirá o desempenho do programa.

No entanto, por A lei de Gustafson, o aumento do número de núcleos realmente ajudaà medida que o tamanho do problema aumenta. Essa é a motivação por trás da computação em cluster. Como temos mais poder computacional, podemos resolver o problema em maior escala ou com maior precisão com a ajuda da paralelização.

Algoritmos que aprendemos como podem ou não serparalelizável. Às vezes, um algoritmo separado deve ser usado para executar com eficiência a mesma tarefa em paralelo. De qualquer forma, a notação Big-O deve ser re-analisada para o caso paralelo para levar em consideração o efeito da paralelização na complexidade de tempo do algoritmo.