HBJ model

Last updated August 04, 2023

In computer science, the Helman-Bader-JaJa model^[1] is a concise message-passing model of parallel computing defined with the following parameters:

$p$ is number of processors.
$n$ is the problem size.
$m$ is number of machine words in a packet sent over the network.
$\tau$ is the latency, or time at which a processor takes to initiate a communication on a network.
$\sigma$ is the bandwidth, or time per machine word at which a processor can inject or receive $m$ machine words from the network.
$T_{comp}$ is the largest computation time expended on a processor.
$T_{comm}$ is the time spent in communication on the network.

This model assumes that for any subset of $q$ processors, a block permutation among the $q$ processors takes $(\tau +\sigma m)$ time, where $m$ is the size of the largest block.

Analysis of common parallel algorithms

Complexities of common parallel algorithms contained in the MPI libraries:^[2]

Point to point communication: $O(\tau +\sigma m)$
Reduction : $O(log(p)(\tau +\sigma m))$
Broadcast: $O(log(p)(\tau +\sigma m))$
Parallel prefix: $O(log(p){n \over p}(\tau +\sigma m))$
All to all: $O(p(\tau +\sigma m)))$

Related Research Articles

Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable as a function of the time lag between them. The analysis of autocorrelation is a mathematical tool for finding repeating patterns, such as the presence of a periodic signal obscured by noise, or identifying the missing fundamental frequency in a signal implied by its harmonic frequencies. It is often used in signal processing for analyzing functions or series of values, such as time domain signals.

In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

In statistics, an expectation–maximization (EM) algorithm is an iterative method to find (local) maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The EM iteration alternates between performing an expectation (E) step, which creates a function for the expectation of the log-likelihood evaluated using the current estimate for the parameters, and a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step. These parameter-estimates are then used to determine the distribution of the latent variables in the next E step.

The Drude model of electrical conduction was proposed in 1900 by Paul Drude to explain the transport properties of electrons in materials. Basically, Ohm's law was well established and stated that the current J and voltage V driving the current are related to the resistance R of the material. The inverse of the resistance is known as the conductance. When we consider a metal of unit length and unit cross sectional area, the conductance is known as the conductivity, which is the inverse of resistivity. The Drude model attempts to explain the resistivity of a conductor in terms of the scattering of electrons by the relatively immobile ions in the metal that act like obstructions to the flow of electrons.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

Mohr–Coulomb theory is a mathematical model describing the response of brittle materials such as concrete, or rubble piles, to shear stress as well as normal stress. Most of the classical engineering materials follow this rule in at least a portion of their shear failure envelope. Generally the theory applies to materials for which the compressive strength far exceeds the tensile strength.

Variational Bayesian methods are a family of techniques for approximating intractable integrals arising in Bayesian inference and machine learning. They are typically used in complex statistical models consisting of observed variables as well as unknown parameters and latent variables, with various sorts of relationships among the three types of random variables, as might be described by a graphical model. As typical in Bayesian inference, the parameters and latent variables are grouped together as "unobserved variables". Variational Bayesian methods are primarily used for two purposes:

To provide an analytical approximation to the posterior probability of the unobserved variables, in order to do statistical inference over these variables.
To derive a lower bound for the marginal likelihood of the observed data. This is typically used for performing model selection, the general idea being that a higher marginal likelihood for a given model indicates a better fit of the data by that model and hence a greater probability that the model in question was the one that generated the data.

In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an $n \times n$ matrix $B$ as a weighted sum of minors, which are the determinants of some $(n - 1) \times (n - 1)$ submatrices of $B$ . Specifically, for every $i$ ,

The lattice Boltzmann methods (LBM), originated from the lattice gas automata (LGA) method (Hardy-Pomeau-Pazzis and Frisch-Hasslacher-Pomeau models), is a class of computational fluid dynamics (CFD) methods for fluid simulation. Instead of solving the Navier–Stokes equations directly, a fluid density on a lattice is simulated with streaming and collision (relaxation) processes. The method is versatile as the model fluid can straightforwardly be made to mimic common fluid behaviour like vapour/liquid coexistence, and so fluid systems such as liquid droplets can be simulated. Also, fluids in complex environments such as porous media can be straightforwardly simulated, whereas with complex boundaries other CFD methods can be hard to work with.

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers $x 0, x 1, x 2, ...$ is a second sequence of numbers $y 0, y 1, y 2, ...$ , the sums of prefixes of the input sequence:

The softmax function, also known as softargmax or normalized exponential function, converts a vector of $K$ real numbers into a probability distribution of $K$ possible outcomes. It is a generalization of the logistic function to multiple dimensions, and used in multinomial logistic regression. The softmax function is often used as the last activation function of a neural network to normalize the output of a network to a probability distribution over predicted output classes, based on Luce's choice axiom.

Neural cryptography is a branch of cryptography dedicated to analyzing the application of stochastic algorithms, especially artificial neural network algorithms, for use in encryption and cryptanalysis.

Location estimation in wireless sensor networks is the problem of estimating the location of an object from a set of noisy measurements. These measurements are acquired in a distributed manner by a set of sensors.

In the fields of computer vision and image analysis, the scale-invariant feature operator is an algorithm to detect local features in images. The algorithm was published by Förstner et al. in 2009.

In data structures, a range query consists of pre-processing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. An extension of this model with more than one server is the M/D/c queue.

An affine term structure model is a financial model that relates zero-coupon bond prices to a spot rate model. It is particularly useful for deriving the yield curve – the process of determining spot rate model inputs from observable bond market data. The affine class of term structure models implies the convenient form that log bond prices are linear functions of the spot rate.

ProbOnto is a knowledge base and ontology of probability distributions. ProbOnto 2.5 contains over 150 uni- and multivariate distributions and alternative parameterizations, more than 220 relationships and re-parameterization formulas, supporting also the encoding of empirical and univariate mixture distributions.

Anelasticity is a property of materials that describes their behaviour when undergoing deformation. Its formal definition does not include the physical or atomistic mechanisms but still interprets the anelastic behaviour as a manifestation of internal relaxation processes. It's a special case of elastic behaviour.

In mathematics, the Chambolle-Pock algorithm is an algorithm used to solve convex optimization problems. It was introduced by Antonin Chambolle and Thomas Pock in 2011 and has since become a widely used method in various fields, including image processing, computer vision, and signal processing.

References

↑ David R., Helman; David A., Bader; JaJa, Joseph (1998). "A Randomized Parallel Sorting Algorithm with an Experimental Study" (PDF). Journal of Parallel and Distributed Computing. 52: 1–23. doi:10.1006/jpdc.1998.1462. hdl:1903/835 . Retrieved 26 October 2012.^{[ dead link ]}
↑ Bader, David A.; Jaja, Joseph (1996). "Practical parallel algorithms for dynamic data redistribution, median finding, and selection". Proceedings of the 10th IEEE International Parallel Processing Symposium: 292–301.

This computer science article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] David R., Helman; David A., Bader; JaJa, Joseph (1998). "A Randomized Parallel Sorting Algorithm with an Experimental Study" (PDF). Journal of Parallel and Distributed Computing. 52: 1–23. doi:10.1006/jpdc.1998.1462. hdl:1903/835 . Retrieved 26 October 2012.^{[ dead link ]}

[2] Bader, David A.; Jaja, Joseph (1996). "Practical parallel algorithms for dynamic data redistribution, median finding, and selection". Proceedings of the 10th IEEE International Parallel Processing Symposium: 292–301.

[1]

[2]