The blast programs are written in C and the parallization was done with the Pvm library (Parallel Virtual Machine, described in [PVM 93]). Every parallel blast application has one master and a certain predetermined number of slaves, each running on a different processor. The master sends the command line arguments to the slaves, and every time a slave is finished with a chunk, the master gets the partial results from the slave, adds them to the results already received, and sends the next chunk. Note, not the portions of the database are sent, but just a chunk number. The database is accessed via the network with NFS, which with the type of network at our installation (FDDI) is pretty fast. But, this is still a point to investigate, if it would be better to send the actual portions of the database, so that each slave, makes just local accesses. At the end, when the master has collected the results from all the slaves, the master prints the results.
Blast3 is a little bit more complicated, because, after the first search, it searches for ``three-way alignments'' on the results. We did not parallelize blast3, because it is no more supported in the blast 1.4 version.
An effort was made, to parallelize the applications automatically, i.e. to translate the serial version to the parallel version with a program and not by hand. This is quite a simple program written in perl. It looks for some characteristic lines in the original program, and inserts some additional commands for the pvm version. If future serial versions are not too different from the current ones, the parallel version will be generated automatically. However, during this project we found out, that this is an illusion, because different serial versions can be very different.
In order to serve many requests at a time, things become a little more complicated. The parallel blast program (blast_pvm) calls a deamon, which reserves for that particular request some workstations according to their load. The deamon starts the master, and the master starts the slaves on the designated workstations. The deamon is now ready to accept other requests. When the master finishes, it notifies the deamon and tells blast_pvm to get the results. The deamon sets the workstations free again.