12.1.4 Parallel Processing

Because individual conformations in the search tree can be processed independently of one another, CONGEN can operate on different nodes simultaneously. This allows the program to use multiple CPU's to speed the progress of a search.

In order to minimize the interference between processors, CONGEN partitions its activities into three nearly disjoint operations. The most time consuming operation is the sampling of degrees of freedom. This operation takes one partial conformation, samples it, and generates new partial conformations. The second operation is the decision making one, deciding what conformations should be sampled next, and in addition, taking care of the search tree. The third operation is taking new conformations from the sampling operation and putting them into the search tree.

CONGEN maintains two queues in order to minimize the contention between these operations. The first is the work queue (cg_work_q) which stores conformations to be expanded. The second is the new node queue (cg_new_node_q) which holds new conformations for insertion into the search tree.

In order to obtain maximum parallelism, the work queue should be a large as possible. However, for directed searches, it is best to keep the tree up to date so that decisions about what to explore next can be made with the most information. Therefore, directed searches have a requirement to keep the work queue small. There are two variables which control the size of the queue, QMIN and QMAX. QMIN specifies target value for the minimum size of the work queue, and QMAX specifies the target value for the maximum size of the work queue. CONGEN automatically sets these variables depending on the type of search being performed, but they can be changed if you wish.

There is one significant pitfall with CONGEN running in parallel, non-determinism. Since one cannot predict when a processor will finish sampling a conformation, the order in which the search tree is traversed will vary from run to run. In the case of exhaustive searches, this doesn't matter because all runs will produce the same set of conformations, albeit in different orders.

However, in the case of a directed search, the decisions on which node to expand next is made based on the contents of the search tree at the time. Since the contents will vary from run to run, the searches will all be different. It is not known as yet if all the results will be consistent. In simple trials where the peptide backbone is reconstructed from the alpha carbons, consistent results were observed.