| 625 |
|
\label{sec:discussion} |
| 626 |
|
|
| 627 |
|
\section*{Appendix A: Computing Convex Hulls on Parallel Computers} |
| 628 |
+ |
|
| 629 |
+ |
In order to use the Langevin Hull for simulations on parallel |
| 630 |
+ |
computers, one of the more difficult tasks is to compute the bounding |
| 631 |
+ |
surface, facets, and resistance tensors when the processors have |
| 632 |
+ |
incomplete information about the entire system's topology. Most |
| 633 |
+ |
parallel decomposition methods assign primary responsibility for the |
| 634 |
+ |
motion of an atomic site to a single processor, and we can exploit |
| 635 |
+ |
this to efficiently compute the convex hull for the entire system. |
| 636 |
+ |
|
| 637 |
+ |
The basic idea is that if we split the original point cloud into |
| 638 |
+ |
spatially-overlapping subsets and compute the convex hulls for each of |
| 639 |
+ |
the subsets, the points on the convex hull of the entire system are |
| 640 |
+ |
all present on at least one of the subset hulls. The algorithm works |
| 641 |
+ |
as follows: |
| 642 |
+ |
\begin{enumerate} |
| 643 |
+ |
\item Each processor computes the convex hull for its own atomic sites |
| 644 |
+ |
(dashed lines in Fig. \ref{fig:parallel}). |
| 645 |
+ |
\item The Hull vertices from each processor are passed out to all of |
| 646 |
+ |
the processors, and each processor assembles a complete list of hull |
| 647 |
+ |
sites (this is much smaller than the original number of points in |
| 648 |
+ |
the point cloud). |
| 649 |
+ |
\item Each processor computes the convex hull of these sites (solid |
| 650 |
+ |
line in Fig. \ref{fig:parallel}) and carries out Delaunay |
| 651 |
+ |
triangulation to obtain the facets of the global hull. |
| 652 |
+ |
\end{enumerate} |
| 653 |
+ |
|
| 654 |
+ |
\begin{figure} |
| 655 |
+ |
\begin{centering} |
| 656 |
+ |
\includegraphics[width=3in]{parallel} |
| 657 |
+ |
\caption{When the sites are distributed among many nodes for parallel |
| 658 |
+ |
computation, the processors first compute the convex hulls for their |
| 659 |
+ |
own sites (dashed lines in upper panel). The positions of the sites |
| 660 |
+ |
that make up the convex hulls are then communicated to all |
| 661 |
+ |
processors. The convex hull of the system (solid line in lower |
| 662 |
+ |
panel) is the convex hull of the points on the hulls for all |
| 663 |
+ |
processors. } |
| 664 |
+ |
\end{centering} |
| 665 |
+ |
\label{fig:parallel} |
| 666 |
+ |
\end{figure} |
| 667 |
|
|
| 668 |
+ |
The individual hull operations scale with |
| 669 |
+ |
$O(\frac{n}{p}\log\frac{n}{p})$ where $n$ is the total number of |
| 670 |
+ |
sites, and $p$ is the number of processors. The hull operations |
| 671 |
+ |
create a set of $p$ hulls each with approximately $\frac{n}{3pr}$ |
| 672 |
+ |
sites (for a cluster of radius $r$). The communication costs for |
| 673 |
+ |
distributing this information to all processors is XXX, while the |
| 674 |
+ |
final computation of the system hull is of order |
| 675 |
+ |
$O(\frac{n}{3r}\log\frac{n}{3r})$. Overall, the total costs are |
| 676 |
+ |
dominated by the computations of the individual hulls, so the Langevin |
| 677 |
+ |
hull sees roughly linear speed-up with increasing processor counts. |
| 678 |
+ |
|
| 679 |
|
\section*{Acknowledgments} |
| 680 |
|
Support for this project was provided by the |
| 681 |
|
National Science Foundation under grant CHE-0848243. Computational |
