Se você tiver acesso físico, você pode baixar o pacote parallel_20130922-1_all.deb do link e instalar como qualquer outro debian pacote. Você também pode precisar localizar e obter os pacotes dos quais depende e instalá-los primeiro. Sempre Certifique-se de que você tenha backups recentes e um plano de recuperação antes de fazer alterações em um sistema de produção. Claro que você provavelmente já sabe disso.
Divulgação completa. Eu não tentei nem testei isso. A resposta é baseada na experiência com a instalação de outros pacotes debian no ubuntu, nada mais
Você pode instalar com o dpkg -i pkgname, se você tem dependências não resolvidas, você pode querer verificar este tópico
Como buscar automaticamente as dependências ausentes quando instalando software de .deb?