Multithreading and parallel programming add complexity to programming. Among various programming languages, Haskell and Clojure provide the best language level support to handle the concurrecy.
http://stackoverflow.com/questions/3011668/how-difficult-is-haskell-multi-threading
It is also possible to gain speed by making algorithmic improvements.
Hardware acceleration is the third option for gaining speed. Bioinformaticians are looking into GPU and FPGA.
Last, but not the least, we need to remember that biology is an experimental science. There are many scopes from improvement by designing the experiment in different ways.