Biology Reference
In-Depth Information
Chapter 5
Parallel Computing for Bayesian Networks
Abstract
Most problems in Bayesian network theory have a computational
complexity that, in the worst case, scales exponentially with the number of vari-
ables. It is polynomial even for sparse networks. Even though newer algorithms
are designed to improve scalability, it is unfeasible to analyze data containing more
than a few hundreds of variables. Parallel computing provides a way to address this
problem by making better use of modern hardware.
In this chapter we will provide a brief overview of the history and the funda-
mental concepts of parallel computing, and we will examine their applications to
Bayesian network learning and inference using the
bnlearn
package.
5.1 Foundations of Parallel Computing
A simple yet effective way to evaluate the performance of a computer program
implementing an algorithm is to measure its execution time and the resources it
requires to execute successfully. In this respect, performance is influenced by several
factors, both hardware and software.
The hardware a program runs on obviously has a profound influence on the
program's execution time. Its performance is usually referred to as the
raw
performance of the hardware
and is measured by the number of operations it can
execute in a given amount of time. Two measures of this kind are the
Input/Output
Operations Per Second
(IOPS) for the speed of nonvolatile storage and the
Floating
Point Operations Per Second
(FLOPS) for the speed of operations on real numbers.
Raw performance is limited by the constraints imposed by the hardware produc-
tion process, such as the resolution of the lithography techniques used for printing
processors on silicon, and increasingly by fundamental physical laws, such as the
speed of light and the physics of heat dissipation.
The performance of the software implementation of an algorithm depends both
on the
computational complexity
of the algorithm and on the
software architec-
ture
of the implementation itself. Computational complexity classifies algorithms
Search WWH ::
Custom Search