A significant part of the material of this glossary was adapted from material originally written by Gregory V. Wilson which appeared as "A Glossary of Parallel Computing Terminology" (IEEE Parallel & Distributed Technology, February 1993), and is being re-printed in the same author's "Practical Parallel Programming" (MIT Press, 1995). Several people have contributed additions to this glossary, especially Jack Dongarra, Geoffrey Fox and many of my colleagues at Edinburgh and Syracuse.
Original version is from NPAC at <URL:http://nhse.npac.syr.edu/hpccgloss/>
Original author: Ken Hawick, khawick@cs.adelaide.edu.auSee also the index of all letters and the full list of entries (very large)
Sections: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B8ZS (n.) Bipolar with eight zero substitution, a line code used for T1 which converts any string of 8 zeros of a DS-1 signal into a code which at the far end is converted back to eight zeros. The coding actually inserts BPVs that are realized at the next multiplexer point and that taken out of the signal.
back substitution (n.) See LU decomposition.
banded matrix (n.) a matrix in which the non-zero elements are clustered around the main diagonal. If all the non-zero elements in the matrix are within m columns of the main diagonal, then the bandwidth of the matrix is 2m+1.
bandwidth (n.) The communications capacity (measured in bits per second) of a transmission line or of a specific path through the network. Contiguous bandwidth is a synonym for consecutive grouped channels in mux, switch or DACS; i.e. 256kbps (4 64kbps channels).
bank conflict (n.) A bank "busy-wait" situation. Memory chip speeds are relatively slow when required to deliver a single word, so supercomputer memories are placed in a large number of independent banks (usually a power of 2). A vector of data laid out contiguously in memory with one component per successive bank, can be accessed at one word per cycle (despite the intrinsic slowness of the chips) through the use of pipelined delivery of vector-component words at high bandwidth. When the number of banks is a power of two, then vectors requiring strides of a power of 2 can run into a bank conflict.
bank cycle time (n.) The time, measured in clock cycles, taken by a memory bank between the honoring of one request to fetch or store a data item and accepting another such request. On most supercomputers this value is either four or eight clock cycles. See also prefetch.
barrier (n.) A point in a program at which barrier synchronization occurs. See also fuzzy barrier.
barrier synchronization(n.) An event in which two or more processes belonging to some implicit or explicit group block until all members of the group have blocked. They may then all proceed. No member of the group may pass a barrier until all processes in the group have reached it. See also fuzzy barrier.
basic block (n.) A section of program that does not cross any conditional branches, loop boundaries or other transfers of control. Most compiler optimization is done within basic blocks.
batch search (n.) a concurrent search for a number of names.
benchmark (n.) a quantitative measure of performance for a computing system. The measure may be in terms of computational performance, which is often rated in FLOPS, or in terms of memory speed, or communications bandwidth or some more application-oriented measure such as LIPS or OLTPS. A collection of benchmark results for many computer systems is available on line from the National Software Exchange.
Bernstein's Condition (n.) A sufficient condition for the independence of two sections of a program as stated by Bernstein in 1966. If Ri(Wi) is the set of variables read(written) by a section of code i, then Bernstein's Condition states that sections i and j may be executed in an arbitrary order, or concurrently if: there is no true dependence, output dependence or antidependence among the statements in the sections.
BGP (n.) border gateway protocol.
BiCMOS (n.) Bi-polar CMOS. BiCMOS is a merger of ECL and CMOS wafer processes allowing both types of circuit to exist on the same chip. This gives the advantage of the small feature size and large scale integration of CMOS with ECL's high power, fast driver circuits.
binary semaphore (n.) a semaphore that can only take on the values 0 and 1.
BISDN (n.) Broadband Integrated Services Digital Network is a packet switching technique which uses packets of fixed length, resulting in lower processing and higher speeds. See also ATM or cell relay.
bisection bandwidth(n.) The rate at which communication can take place between one half of a computer and the other. A low bisection bandwidth, or a large disparity between the maximum and minimum bisection bandwidths achieved by cutting the computers elements in different ways is a warning that communications bottlenecks may arise in some calculations.
bit-addressable (adj.) Allowing direct access to individual bits, rather than requiring bits to be selected by applying arithmetic or other operations to whole words. The local memory of each processing element in many processor arrays is bit addressable.
bitonic merge (n.)a parallel algorithm to merge two bitonic sequences of length 2^k into a single bitonic sequence of length 2^(k+1) in k+1 steps.
bitonic sequence (n.) a sequence of numbers A0,A1,...An-1 with the property that (1) there exists an index i, 0<=i<=n-1, such that A0 through Ai is monotonically increasing and Ai through An-1 is monotonically decreasing, or else (2) there exists a cyclic shift of indices so that condition 1 is satisfied.
BLAS (n.) Basic linear algebra software: a suite of very basic linear algebra routines, out of which almost any other matrix calculation can be built. See the National Software Exchange for the BLAS source and documentation.
block (v.) To suspend one's own operation, or the operation of another process. A process may block itself, or be blocked by the system, until some event occurs. If all processes are simultaneously blocked, and no external event can cause any of them to become unblocked, then deadlock has occurred. The term block is also often used to refer to a chunk of data or program. See also basic block.
blocking (adj.) An operation that causes the process executing it to block. Usually applied to communications operations, where it implies that the communicating process cannot perform any other operations until the communication has completed. See also asynchronous, non-blocking and synchronous.
boundary value swapping(n.) A technique used when performing calculations on a mesh on which geometric decomposition has been used. During a boundary value swap, each process exchanges values on the edges of its tile or tiles for the complementary values of its neighbours. See also indirect method.
BPS (n.) bytes per second, a unit of memory access speed or communications transfer speed. See also WARPS and FLOPS.
bridge (n.) A LAN internetworking device that filters and passes data between LANs based on Layer 2 (MAC layer) information. Bridges do not use any routing algorithms.
broadcast (n.) To send a message to all possible recipients. Broadcast can be implemented as a repeated send, but is more efficiently implemented by using spanning trees and having each node in the tree propagate the message to its descendants. See also multicast and process group.
brouter (n.) A term used by some venders, normally refering to a bridge also having some of the characteristics of a router.
buffer (n.) A temporary storage area in memory. Many methods for routing messages between processors use buffers at the source and destination, or at intermediate processors. See also packet switching, virtual cut-through and wormhole routing.
buffered message passing (n.) See message passing system.
bus (n.) A single physical communications medium shared by two or more devices. The network shared by processors in many distributed computers is a bus, as is the shared data path in many multiprocessors. See also link.
busy-waiting (n.) a situation whereby processor cycles are used to test a variable until it assumes a desired value.
butterfly(n.) A topology in which nodes are organised into levels, and there is a unique path from any node in the first level to any node in the last. A butterfly is a recursive topology . See also hypercube and shuffle exchange network.