# Presentation: 367265

## Swarms and Bundles:  Bioinformatics and Biostatistics on Biowulf

- David Hoover
- Scientific Computing Branch, Division of Computer System Services
- CIT, NIH

**Notes:**
Molecular dynamics applications, as detailed by my colleague Susan Chacko, distribute the computational workload among multiple cluster nodes, passing the contents of their independent memories via fast network intercommunications.  When the Biowulf cluster was first made public, it was soon realized that the majority of computational biology applications were either not available with distributed memory capability, or were not readily adaptable to such an architecture.  Instead, these bioinformatic and biostatistical applications could only be accelerated on the cluster by being run in large numbers independently on individual processors.  In computer science, such a situation is known as Embarrassingly Parallel.

## Embarrassingly Parallel Problems

- GWAS, with huge numbers of SNPs

- Sequence analysis, assembly, and mapping

- Testing and validating statistical models

- Protein folding and threading

- Molecular docking and compound screening

- Tomographic reconstruction

**Notes:**
Here are some examples of Embarrassingly Parallel Problems that are run on the Biowulf cluster.

Genome-wide association studies correlate genetic variations, or SNPs, with diseases.  Such a study requires hundreds of thousands to millions of SNPs per individual, and typically hundreds of individuals in the diseased and healthy groups.  The same statistical analysis program would be run again and again on sets of SNPs.

Sequence analysis on a genome scale can be parallelized easily, because genomic sequence can be divided into chromosomes or contigs.

Statistical models for clinical or mathematical data can be tested easily, as this entails generating and analyzing randomly generated trial sets.

Protein folding and threading involves generating and minimizing a huge number of structural models using random starting points.

Drug discovery using molecular docking to find which of thousands of trial compounds fit best into a protein or enzyme drug target.

Aligning, scaling, and classifying hundreds to thousands of raw images from PET, MRI, electron microscopy and others prior to volumetric reconstruction.

## Characterization of Surface Protein 3 from Malaria Parasite P. Falciparum

- Tsai et al., *Mol. Biochem. Parasitology*, online preprint 2008

- Protein folding calculations with Rosetta++
- 100,000 cpu hours

- Characterization of Surface Protein 3 from Malaria Parasite *P. Falciparum*

**Notes:**
To give more detail about an Embarrasingly Parallel Problem, I’ll focus on protein structure prediction.

NIAID’s Bioinformatics and Computational Biosciences Branch provides bioinformatics expertise to NIAID scientists and collaborators. This group routinely uses Biowulf for their computational heavy lifting.  In a recent investigation for malaria vaccine candidates, the group predicted the structure of MSP3, a surface protein from plasmodium, using a program called Rosetta.  The predicted structure was later validated by fitting the structure into electron microscopy images.

Rosetta works by randomly assembling structural fragments that match the secondary structure prediction for a given protein sequence into a model, then energetically minimizing the model.  The best model is determined by clustering all models generated and finding the one with both high representation and lowest free energy.

As the probability of randomly creating a model that is close enough to the correct structure to allow least squares or monte carlo minimization to reach it, the trick to running Rosetta productively is to generate enough models to saturate the folding landscape and uncover the global minimum.  And this takes a whole lot of running model generation and minimization over and over and over again...

## How to run multiple independent processes in parallel

- 16 independent processes

- input

- command

- output

- input

- output

- command

**Notes:**
So, how might one run a large number of independent processes on Biowulf?  First, I’ll introduce my schematic for a set of processes.  For simplicity, I’ll limit the set to 16, although in reality this can be thousands.  The green hexagons are input to the program, the arrow is the execution of the program itself, and the red hexagons are output.  Each pair of hexagons separated by an arrow is what I’ll term a single process. 

## Biowulf Cluster Batch System

**Notes:**
The Biowulf cluster uses a batch system for assigning processes to nodes and keeping track of when they are done.  The batch system requires that the process be encapsulated in a script, and the script is submitted to the batch system to be run somewhere on one of the nodes in the cluster.  The next processes would be submitted, and then the next, and again, and again...

In this context, each submitted process is its own batch job.   Each job generates standard output and error files which are transferred back to the user from the assigned node.  For large sets of independent jobs, submitting each job gets messy and time consuming, and the amount of overhead for both the user and batch system can be overwhelming.

## Swarm

- Node 1

- Node 2

- Node 3

- Node 4

- job1

- job2

- job3

- job4

- job1.out

- job2.out

- job3.out

- job4.out

**biowulf% swarm -f file**

**Notes:**
The problem of overwhelming inefficiency gave rise to the concept of swarm.  Rather than create a new batch job for every process, it would be easier to create a single batch job that runs one process per CPU on a node.  So, rather than 16 jobs, swarm creates 4 jobs of 4 processes each.

## Bundled Swarm

- Node 1

- job1

- job1.out

**biowulf% swarm -f file -b 4**

**Notes:**
To further simplify things, swarms can be bundled, so that multiple processes can be assigned to a single CPU on a node, like a ‘to-do list’.  Each CPU chugs through the processes until the list is empty.  The node is made free after all the processes are finished.  Since there is virtually no time delay between processes, a bundled swarm is much more efficient if each process is very short (10-100 seconds each), instead of wasting time waiting in the batch system queue.

## Swarm Facts

- Written and maintained by Helix Systems Staff

- swarm introduced in late 2000

- 82% of all batch jobs run on the cluster since 2002 are swarm jobs

- ~60% of all wall time spent on swarm jobs

- swarm has been shared with clusters around the world

**Notes:**
Swarm was originally written by Steve Bailey, but it has been modified by others in our group as the cluster has grown and changed.

It was introduced in late 2000 soon after the cluster was put into production.

Swarm is the most popular way of submitting jobs to the cluster – 82% of all jobs run on the cluster are swarm jobs.  

While a single molecular dynamics job can dominate the cluster in terms of CPU load and total time of node allocation, applications that do not distribute memory (both single- and multi-threaded) hold their own; 60% of all wall time spent on the cluster is allocated to swarm jobs.  

Lastly, swarm and the swarm algorithms have been shared with other clusters all over the world.  This is testament to its popularity, as it is very simple and adaptable to other batch systems other than the one used on Biowulf.  

## Swarm World Records

- Largest swarm: 683,445 commands
- Largest bundle: 24,000 commands per CPU

**Notes:**
I’ve compiled a list of swarm world records on the Biowulf cluster for this symposium.  To date, the largest swarm job contained more than 600,000 independent commands.  Fortunately, the user who submitted this bundled these.  Without bundling, such a swarm could overwhelm the batch system.

As mentioned, bundling processes in swarm is encouraged when there are a huge number of processes, so as not to overwhelm the batch system with a tsunami of new jobs.  The largest number of processes bundled per CPU is 24,000.  Of course, such huge swarms are in fact quite rare.

## Future Challenges

- How to deal with larger multicore nodes?

- Node 1

- Node 2

- Node 3

**Notes:**
As computer technology evolves, the multicore paradigm for accelerating processing speed will necessitate changes to swarm.  Currently, the standard commodity architecture available for Biowulf has 8 CPUs per node (so-called quad-core).  In the case of submitting of swarm of 17 processes, what is the best way to distribute the processes onto three quad-core nodes?

As computer hardware continues to evolve, swarm will be adapted to continue simplifying bioinformatics on the Biowulf cluster.