3

Estou utilizando a versão 3.4 do python

Como descubro que meus códigos estão realmente funcionando e fazendo o que deveriam? Ao olhar no System Monitor (do linux) eu reparei que os códigos utilizando multiprocessing e threading não utilizam outra CPU, eles ficam forçando o mesmo CPU a 100% sempre. Eles não deveriam dividir o trabalho automaticamente entre as outras CPU's? Estou fazendo a implementação correta dos códigos?

Este é o exemplo de como deveria ser a saída dos códigos, e os resultados deveriam ser os mesmos para os três códigos, porém, o código utilizando multiprocessing sempre retorna 0 no total de número primos:

total de números primos no intervalo definido = 5133
tempo gasto para processar = 23.84818319s (*tempo varia óbvio*)

O problema em si de dizer qual o total de números primos nem é a grande questão, porque o objetivo maior é comparar o tempo de execução das 3 implementações. Porém gostaria de entender o porque este comportamento do código multiprocessing não me retornar nada no total

Código utilizando multiprocessing:

from multiprocessing import Process
import time

primos=0
def ePrimo():
    global primos
    limite=50000
    for numero in range (2,limite+1):
        for i in range (2,numero):
            if numero % i == 0: break
        else:
            primos+=1
tic = time.time()
if __name__ == '__main__':
    p = Process(target=ePrimo)
    p.start()
    p.join()
toc = time.time()


print("total de números primos no intervalo definido = "+ str(primos))
print("tempo gasto para processar = " + str(toc-tic)+"s")

Código utilizando threading:

import threading
import time

primos=0
def ePrimo():
    global primos
    limite=50000
    for numero in range (2,limite+1):
        for i in range (2,numero):
            if numero % i == 0: break
        else:
            primos+=1

t = threading.Thread(target=ePrimo)
tic = time.time()   
t.start()
t.join()
toc = time.time()


print("total de números primos no intervalo definido = "+ str(primos))
print("tempo gasto para processar = " + str(toc-tic)+"s")

Código serial:

import time

primos=0
def ePrimo():
    global primos
    limite=50000
    for numero in range (2,limite+1):
        for i in range (2,numero):
            if numero % i == 0: break
        else:
            primos+=1

tic = time.time()   
ePrimo()
toc = time.time()




print("total de números primos no intervalo definido = "+ str(primos))
print("tempo gasto para processar = " + str(toc-tic)+"s")
1
  • 1
    multiprocessing utiliza processos que, diferente de threads, não compatilham memória. A variável 'primos' está sendo incrementada apenas num processo. Experimenta colocar o print embaixo do loop for.
    – Fabiano
    Commented 10/04/2017 às 21:08

1 Resposta 1

5

Então - o problema é que seus programas acima não são paralelos - eles são seriais.

A questão de paralelizar um código não é tão trivial assim, para alguns problemas pode ser bem difícil, e sobretudon, não há mágica envolvida.

O seu "algoritmo principal", vamos dizer, para verificar se um número é primo é o for mais interno - essas duas linhas:

    for i in range (2,numero):
        if numero % i == 0: break

A parte de outras otimizações possíveis desse algoritmo (você pode contar de 2 em 2, e você só precisa verificar até a raiz quadrada do número) - perceba que, de fato, uma interação do for não depende dos valores anteriores do "for" - então essa é a chave pra saber se um calculo é paralelizavel ou não. Ou seja, nesse caso, se cada verificação de divisão rodasse numa thread ou processo distinto, esse algoritmo poderia se beneificiar de paralelização. Só que ele não está rondando em paralelo - nos dois casos em que você acha que está paralelizando algo, você chama UMA função que percorre todos os números em sequência, e para cada número percorre todos os divisores em potencial - mas essa função em si é um único bloco sequencial: ela vai rodar num único núcleo mesmo!

Paralelizar a verificação de primos em si não é tão simples - por que ter 50000 processos, por exemplo, um para verificar cada divisor de um de seus números, não seria efetivo: a computação necessária é pequena (só verificar o resto de uma divisão), enquanto que os recursos necessários para se criar um processo, ou mesmo outra thread, são muitos - envolvendo a execução de dezenas de milhares de instruções nativas (em contraste com poucas dezenas para a verificação de resto em Python ou com uma única instrução se esse código fosse em C)

Agora, quebrar as funções um pouco mais: uma que verifica se um único número é primo - e outra que faz a chamada para essas funções, facilitaria a paralelização aí. Mesmo isso não é de graça: você precisa criar um número razoável de threads e/ou processos - o número ótimo é algo perto do número de núcleos que você tem - e distribuir as tarefas de forma que processos e threads ja criados sejam reaproveitados para processar novos números - e - guardar o resultado de tudo isso, para sua contabilidade final.

Felizmente o Python resolve o problema de paralelização por esse caminho com o módulo concurrent.futures da biblioteca padrão.

Então, antes de refatorar seu código para usar esse caminho, duas outras considerações:

(1) o comentário do Fabiano está perfeito: tarefas executadas em processos distintos não compartilham variáveis globais - em contraste com tarefas em múltiplas threads. O concurrent.futures permite que as tarefa retornem valores, e ela se encarrega de transpota-los entre os processos.

(2) Justamente para garantir a integridade de variáveis e estruturas como listas e dicionários, o Python não executa threads verdadeiramente em paralelo - a nao ser que haja alguma tarefa de entrada/saída, apenas uma thread executa código Python por vez - o runtime to Python faz isso usando um Lock global do interpretador - o "GIL". Extençoes em C, ou usando Cython, programadas de forma que código paralelo não vá deixar outras estruturas de dados inconsistentes, pode liberar o GIL e tirar proveito de multi-threading.

Então, primeiro o seu programa, só refatorando a função que checa um único número primo - mas também com as otimzações que mencionei acima: se você não encontra nenhum fator de um número até chegar na sua raiz quadrada, não vai haver nenhum fator depois dela (por exemplo, 17, a raiz é 4.1 - se "4" não é divisor de 17, os fatores do 5 em diante, multiplicados por qualquer outro fator de 5 em diante, vão resultar num número maior que 17).

Para números até 50000 isso fica 100 vezes mais rápido - se buscar em números maiores, esse fator vai aumentar:

import time

def checa_primo_raiz(numero):
    if numero == 2:
        return True
    if not numero % 2:
        return False
    raiz = numero ** 0.5
    if raiz == int(raiz):
        return False
    for i in range(3, int(raiz + 1), 2):
        if not numero % i:
            return False
    return True


def checa_primo_nutella(numero):
    for i in range(2, numero):
        if not numero % i:
            return False
    return True


def ePrimo(checa_primo):
    global primos
    limite=50000
    primos = 0
    for numero in range(2,limite + 1 ):
        if checa_primo(numero):
            primos += 1
            m1.add(numero)


def teste():
    for func in (checa_primo_raiz, checa_primo_nutella):
        tic = time.time()
        ePrimo(func)
        toc = time.time()

        print("Função {}:".format(func.__name__))
        print("total de números primos no intervalo definido = "+ str(primos))
        print("tempo gasto para processar = " + str(toc-tic)+"s")

if __name__ == "__main__":
    teste()

E, por fim, vamos lá para uma versão do seu código usando concurrent.futures e multiplos processos - eu não mencionei acima, mas quebrar cada tarefa e fazer a chamada interprocessos também toma tempo - então mesmo se fizermos isso para cada número na sequência o fato do Python ter que serializar a chamada, coordenara a chamada do método no outro processo, e serializar o resultado de volta, usa bastante processamento comparado com a tarefa trivial de buscar divisores entre 2 e sqrt(50000) (que é ~71.) Por isso aproveitei que mudei o código para comparar métodos diferentes, e comparo a paralelização em diferentes intervalos. Minha máquina tem 2 núcleos físicos e 4 se contar as "hyperthreads" e eu notei um speed-up de exatas duas vezes com a paralelização em "fatias maiores" - e quase nenhum ganho com fatias menores (o número passado no parametro para ProcessPoolExecutor é a quantidade de processos "workers" que vão trabalhar nas tarefas):

import time

from concurrent.futures import ProcessPoolExecutor, as_completed

def checa_primo(numero):
    if numero == 2:
        return True
    if not numero % 2:
        return False
    raiz = numero ** 0.5
    if raiz == int(raiz):
        return False
    for i in range(3, int(raiz + 1), 2):
    #for i in range(2, numero):
        if not numero % i:
            return False
    return True


def checa_intervalo(inicio, tamanho):
    return sum(int(checa_primo(numero)) for numero in range(inicio, inicio + tamanho))


def ePrimo(limite, intervalo=100):

    primos = 0

    processos  = ProcessPoolExecutor(4)
    checagens = set()
    for numero in range(2,limite + 1, intervalo):
        final = min(limite - numero, intervalo)
        checagens.add(processos.submit(checa_intervalo, numero, final))

    for checagem in as_completed(checagens):
        primos += checagem.result()

    return primos

def teste():
    for intervalo in (4, 10, 50, 100, 1000, 5000, 10000):
        tic = time.time()
        primos = ePrimo(100000, intervalo)
        toc = time.time()

        print("\n Agrupando {} números por tarefa:".format(intervalo))
        print("total de números primos no intervalo definido = "+ str(primos))
        print("tempo gasto para processar = " + str(toc-tic)+"s")

if __name__ == "__main__":
    teste()

Conclusão

Paralelização acelera as coisas - mas para poder paralelizar o programador tem que saber oq eu está fazendo, saber escolher o método, e saber escolher os parâmetros - e muitas vezes o método para paralelizar não vai ser nem um pouco trivial. Por outro lado, apenas ajustando o algoritmo, tivemos um ganho de perto de 100 vezes na velocidade de execução do seu programa inicial. Por isso que um dos expoentes da Ciência da Computação já dizia "A Otimização prematura é a raiz de todos os males" (Donald Knuth) - alguém pode dizer que "está demorando, vamos paralelizar" de repente vai gatar um monte de recursos e não melhorar quase nada, se não souber o que está fazendo.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .