📄 node22.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>2.8 Case Study: Computational Chemistry</TITLE>
</HEAD>
<BODY>
<meta name="description" value="2.8 Case Study: Computational Chemistry">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html2107 HREF="node21.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html2115 HREF="node23.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node23.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html2113 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html2117 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html2118 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html2116 HREF="node23.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node23.html">2.9 Summary</A>
<B>Up:</B> <A NAME=tex2html2114 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B> Previous:</B> <A NAME=tex2html2108 HREF="node21.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html">2.7 Case Study: Floorplan Optimization</A>
<BR><HR><P>
<H1><A NAME=SECTION02380000000000000000>2.8 Case Study: Computational Chemistry</A></H1>
<P>
<A NAME=secchem> </A>
<P>
<A NAME=1966> </A>
Our third case study, like the first, is from computational science.
<A NAME=1967> </A>
It is an example of an application that accesses a distributed
<A NAME=1968> </A>
data structure in an asynchronous fashion and that is amenable to a
functional decomposition.
<P>
<H2><A NAME=SECTION02381000000000000000>2.8.1 Chemistry Background</A></H2>
<P>
Computational techniques are being used increasingly as an alternative
to experiment in chemistry. In what is called <em> ab initio
quantum chemistry
</em>, computer programs are used to compute fundamental
properties of atoms and molecules, such as bond strengths and reaction
energies, from first principles, by solving various approximations to
the Schrödinger equation that describes their basic structures.
This approach allows the chemist to explore reaction pathways that
would be hazardous or expensive to explore experimentally. One
application for these techniques is in the investigation of biological
processes. For example,
<A HREF="#bash">Plate 6</A>
<P>
shows a molecular model for the active site region in the enzyme
malate dehydrogenase, a key enzyme in the conversion of
glucose to the high-energy molecule ATP. This image is taken from a
simulation of the transfer of a hydride anion from the substrate,
malate, to a cofactor, nicotinamide adenine diphosphate. The two
isosurfaces colored blue and brown represent lower and higher electron
densities, respectively, calculated by using a combined quantum and
classical mechanics methodology. The green, red, blue, and white
balls are carbon, oxygen, nitrogen, and hydrogen atoms, respectively.
<P>
Fundamental to several methods used in quantum chemistry is the need
to compute what is called the <em> Fock matrix</em>, a two-dimensional
<A NAME=1977> </A>
array representing the electronic structure of an atom or molecule.
This matrix, which is represented here as <tt> F</tt>, has size
<em> N</em>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img317.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img317.gif"><em> N</em>
and is formed by evaluating the following
summation for each element:
<P><A NAME=eqnfock> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img318.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img318.gif"><P>
where <tt> D</tt> is a two-dimensional array of size
<em> N</em>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img319.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img319.gif"><em> N</em>
that is only read, not written, by this
computation and the <tt> I</tt> represent integrals that are
computed using elements <em> i</em>
, <em> j</em>
, <em> k</em>
, and <em> l</em>
of a
read-only, one-dimensional array <tt> A</tt> with <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img320.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img320.gif"> elements. An
integral can be thought of as an approximation to the repulsive force
between two electrons.
<P>
<P><A NAME=algfock> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img321.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img321.gif"><P>
<P>
Because Equation <A HREF="node22.html#eqnfock" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html#eqnfock">2.3</A> includes a double summation, apparently
2<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img322.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img322.gif"> integrals must be computed for each element of <tt> F</tt>,
for a total of 2<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img323.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img323.gif"> integrals. However, in practice it is possible
to exploit redundancy in the integrals and symmetry in <tt> F</tt> and
reduce this number to a total of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img324.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img324.gif">. When this is done, the
algorithm can be reduced to the rather strange logic given as
Algorithm <A HREF="node22.html#algfock" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html#algfock">2.3</A>. In principle, the calculation of each
element of <tt> F</tt> requires access to all elements of <tt> D</tt> and <tt>
A</tt>; furthermore, access patterns appear highly irregular. In this
respect, the Fock matrix construction problem is representative of
many numeric problems with irregular and nonlocal communication
patterns.
<P>
For the molecular systems of interest to chemists, the problem size
<em> N</em>
may be in the range <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img325.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img325.gif">. Because the evaluation
of an integral is a fairly expensive operation, involving <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img326.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img326.gif">
operations, the construction of the Fock matrix may require
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img327.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img327.gif"> operations. In addition, most methods require that
a series of Fock matrices be constructed, each representing a more
accurate approximation to a molecule's electronic structure. These
considerations have motivated a considerable amount of work on both
efficient parallel algorithms for Fock matrix construction and
improved methods that require the computation of less than <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img328.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img328.gif">
integrals.
<P>
<A NAME=2055> </A>
<P>
<H2><A NAME=SECTION02382000000000000000>2.8.2 Chemistry Algorithm Design</A></H2>
<P>
<A NAME=secchemx> </A>
<P>
<H4><A NAME=SECTION02382010000000000000> Partition.</A></H4>
<P>
Because the Fock matrix problem is concerned primarily with the symmetric
two-dimensional matrices <tt> F</tt> and <tt> D</tt>, an obvious partitioning
strategy is to apply domain decomposition techniques to these matrices
to create <em> N(N+1)/2</em>
tasks, each containing a single element from
each matrix (<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img329.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img329.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img330.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img330.gif">) and responsible for the
operations required to compute its <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img331.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img331.gif">. This yields
<em> N(N+1)/2</em>
tasks, each with <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img332.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img332.gif"> data and each responsible for
<A NAME=2069> </A>
computing 2<IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img333.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img333.gif"> integrals, as specified in Equation <A HREF="node22.html#eqnfock" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html#eqnfock">2.3</A>.
<P>
This domain decomposition strategy is simple but suffers from a
significant disadvantage: it cannot easily exploit redundancy and
symmetry and, hence, performs eight times too many
integral computations. Because an alternative algorithm based on
<A NAME=2071> </A>
functional decomposition techniques is significantly more efficient
(it does not perform redundant computation and does not incur high
communication costs), the domain decomposition
algorithm is not considered further.
<P>
<P><A NAME=2998> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img338.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img338.gif">
<BR><STRONG>Figure 2.31:</STRONG> <em> Functional decomposition of Fock matrix problem. This
yields about <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img336.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img336.gif"> data tasks, shown in the upper part of the
figure, and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img337.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img337.gif"> computation tasks, shown in the lower part of the
figure. Computation tasks send read and write requests to data
tasks.</em><A NAME=figfockd2> </A><BR>
<P>
<P>
Quite a different parallel algorithm can be developed by focusing on
the computation to be performed rather than on the data structures
manipulated, in other words, by using a functional decomposition.
When redundancy is considered, one naturally thinks of a computation
as comprising a set of integrals (the <tt> integral</tt> procedure of
Algorithm <A HREF="node22.html#algfock" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html#algfock">2.3</A>), each requiring six <tt> D</tt> elements and
contributing to six <tt> F</tt> elements. Focusing on these computations,
we define <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img339.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img339.gif"> ``computation'' tasks, each responsible for one
integral.
<P>
Having defined a functional decomposition, we next need to distribute
data structures over tasks. However, we see no obvious criteria by
which data elements might be associated with one computation task
rather than another: each data element is accessed by many tasks. In
effect, the <tt> F</tt>, <tt> D</tt>, and <tt> A</tt> arrays constitute large data
structures that the computation tasks need to access in a distributed
and asynchronous fashion. This situation suggests that the techniques
described in Section <A HREF="node17.html#seccommas" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.html#seccommas">2.3.4</A> for asynchronous communication
may be useful. Hence, for now we simply define two sets of ``data''
tasks that are responsible only for responding to requests to read and write
data values. These tasks encapsulate elements of the two-dimensional
arrays <tt> D</tt> and <tt> F</tt> (<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img340.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img340.gif">, <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img341.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img341.gif">) and of the
one-dimensional array <tt> A</tt> (<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img342.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img342.gif">), respectively. In all,
our partition yields a total of approximately <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img343.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img343.gif"> computation
tasks and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img344.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img344.gif"> data tasks (Figure <A HREF="node22.html#figfockd2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html#figfockd2">2.31</A>).
<P>
<H4><A NAME=SECTION02382020000000000000> Communication and Agglomeration.</A></H4>
<P>
<A NAME=2094> </A>
We have now defined <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img345.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img345.gif"> computation tasks and <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img346.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img346.gif"> data
<A NAME=2095> </A>
tasks. Each computation task must perform sixteen communications: six
to obtain <tt> D</tt> matrix elements, four to obtain <tt> A</tt> matrix
elements, and six to store <tt> F</tt> matrix elements. As the
computational costs of different integrals can vary significantly,
there does not appear to be any opportunity for organizing these
communication operations into a regular structure, as is advocated in
Section <A HREF="node17.html#seccommglobal" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node17.html#seccommglobal">2.3.2</A>.
<P>
On many parallel computers, the cost of an integral will be comparable
to the cost of a communication. Hence, communication requirements
must be reduced by agglomeration. We describe two alternative
strategies that can be used to achieve this goal. Their data
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -