Essa implementaçao não é paralalizável "de verdade", além de ser uma "catástrofe". Sim, você quer saber como calcular diferentes fibonaccis em threads ou processos paralelos - a resposta para isso seria um exemplo de threadpool ou processpoll (dica, olhe concurrent.futures) - mas não vou tocar nesse assunto aqui.
O que não é paralelizável é que você não tem como ter, num mesmo thread, o fibo(10) sem ter calculado antes o fibo(5) - mesmo que a sua função fibo mande calcular fibo(n-1) e fibo(n-2) em threads/processos separados, vai ter que esperar ambos terminarem. (e a catastrofe seria ainda maior - por que threads e processos são MUITO mais pesados em termos de consumo de memória do que chamadas simples)
A implementação funciona muito bem para fins didáticos, até fibonacci de 10 - talvez até 15 - mas se você pedir um fibonacci de 40 nela, vai travar seu computador. De 80 vai travar possivelmente o maior supercomputador do mundo.
Isso acontece por que você tem duas chamadas de função dentro de cada chamada do fibonacci.
O Python, para chamar uma função cria em memória um novo objeto do tipo "frame" - (junto com um objeto para cada variável local da função, etc.. - no caso será só a variável 'n' - mas sendo um inteiro em Python usa uns bons 30 bytes - mas o frame tem uns 400 bytes).
Bom, se você pedir fibonacci de "3", isso é o frame inicial, mais o frame de fibo(1), mais o frame de fibo(2) - que or sua vez chama de novo fibo(1) e fibo(0) -- sao 5 chamadas - agora perceba que se pedir fibo(5) vão ser essas 5 chamadas para o fibo(3), e mais 7 chamadas para o fibo(4) ? Ou seja: o número de chamadas de função que voce faz cresce com o QUADRADO do número "n" (o que chamaos de complexidade O(n²) ) - por exemplo, se fibo(5) for usar ai uns 1000 bytes (2**10), fibo(10) já vai usar 2**20 bytes: 1 megabyte e fibo (30) um GB.
As soluções são: Use um decorador de cache: functools.lru_cache
em seu fibonacci - isso fará que para qualquer valor já conhecido, a função retorne imediatemente, sem executar seu corpo (e portano sem duas outras chamadas) - ou seja, para calculcar fibo(7), fibo(6) será chamado uma vez, mas quando fibo(5) for chamado, seu valor já vai ser conhecido, e não vão ser necessárias novas chamadas aos valores 4, 3, 2, 1, 0 no ramo do (5).
Mas melhor que isso ainda é: deixe o exemplo recursivo para entender recursão no quadro branco, e escreva a função de forma interativa - passe longe da forma exponencial.