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 our colleagues at Edinburgh and Syracuse. Also some materials were adapted form the computing glossary of Sun Microsystems.
absolute address (n.)
(1) An
address that identifies storage location or a device without
the use of any intermediate reference. (2) An address
permanently assigned by the designer to a storage
location. (3) Synonymous with explicit address, machine
address, specific address.
action server (n.)
A host computer that provides access to a collection of actions. See
also application server,
caching-only server,
communications server,
file server,
session server.
active star (n.)
A configuration of networked computers in which information
goes from workstations to a central node,
then on to its destination. The central node manages and controls all
the traffic on the network.
acyclic graph (n.)
A graph without
any cycles.
adaptive (adj.)
Taking available
information into account. For example, an adaptive mesh-generating
algorithm generates a finer resolution mesh near to discontinuities
such as boundaries and corners. An adaptive routing algorithm may
send identical messages in different directions at different times
depending on the local density information it has on message traffic.
See also oblivious
address bus (n.)
A hardware pathway,
typically consisting of from 20 to 32 separate lines, that
carries the signals specifying locations in a computer's
memory. The address bus enables the microprocessor to select a
specific location in memory for transfer of data via the data
bus. See also data bus
address generation (n.)
A
cycle during execution of an instruction in which an effective address
is calculated by means of indexing or indirect addressing.
address mask (n.)
In Internet
communications, a 32 bit long mask used to select an
IP address for subnet addressing.
The mask selects the network portion of the IP address and one or more bits of the
local LAN address. Synonymous with subnet mask.
address space (n.)
A region of a
computer's total memory within which addresses are contiguous and may
refer to one another directly. A shared
memory computer has only one user-visible address space; a disjoint memory computer can have
several.
address translation (n.)
In
networking, the process of converting external addresses into
standardized network addresses and vice versa. This facilitates the
interconnection of multiple networks which each have their own address
plan.
adjacency matrix (n.)
A boolean
matrix indicating for each pair of vertices I and J whether there is
an edge from I to J.
AFS (n.)
A distributed file system that
allows users on different machines to access the same files. AFS
allows files to be shared not only on different machines at the
same site, but also at different sites across the country.
The AFS acronym stands for Andrew File System, a project of
Carnegie-Mellon University.
AIX (n.)
Advanced Interactive Executor,
IBM's distribution of UNIX for systems including RS/6000s and
SPs. AIX includes features of both AT&T's System V UNIX and BSD
(Berkeley Standard Distribution) UNIX.
algorithm (n.)
A sequence of steps
designed to solve a problem or execute a process. Technically,
an algorithm must reach a result after a finite number of
steps, thus ruling out brute force search methods for certain
problems, though some might claim that brute force search was
also a valid (generic) algorithm. The term is also used
loosely for any sequence of actions (which may or may not
terminate).
all-pairs shortest-path
problem (n.)
Given a weighted graph, find the shortest path
between every pair of vertices.
alpha-beta pruning (n.)
An
algorithm used to determine the minimax
value of a game tree. Alpha-beta algorithm avoids searching
subtrees whose evaluation cannot influence the outcome of the
search.
ALU (n.)
See
arithmetic and logic
unit.
Amdahl's Law (n.)
A rule first
formalized by Gene Amdahl in 1967, which states that if F is the
fraction of a calculation that is serial and 1-F the fraction that can
be parallelized, then the
speedup that can be
achieved using P processors is: 1/( F + (1-F)/P) which has a limiting
value of 1/F for an infinite number of processors. This no matter how
many processors are employed, if a calculation has a 10% serial
component, the maximum speedup obtainable is 10.
AMI (n.)
Alternate mark inversion, a line
code used for T1 and E1 lines that has a 12.5% ones density minimum,
and the one conditions of the signal alternate between positive and
negative polarity.
AND tree (n.)
A search tree whose
nonterminal nodes are all AND nodes.
AND-parallelism (n.)
A form of
parallelism exploited by some implementations of parallel logic
programming languages, in which the terms in conjunctions are
evaluated simultaneously, and parent computations are allowed to
proceed only once their immediate children have completed. See also
OR-parallelism .
AND/OR tree (n.)
A search tree with
both AND and OR nonterminal nodes.
ANSI (n.)
American National Standards
Institute, a United States based organization which develops standards
and defines interfaces for telecommunications amongst other things.
antidependence (n.)
See dependence.
AppleTalk (n.)
Apple Computer's
proprietary network suite of protocols.
Applet (n.)
A small Java program that can be embedded in an HTML page. Applets differ from full-fledged Java applications in that they are not
allowed to access certain resources on the local computer, such as
files and serial devices (modems, printers, etc.) and are prohibited
from communicating with most other computers across a network.
application (n.)
A software program specially designed for a particular task or the
specific use of a software program. Graphics applications are usually
designed to enable the user to manipulate data or images, or to
create images from data or from a library of shapes.
application server (n.)
A host computer that provides access to a software application. See
also action server,
caching-only server,
communications server,
session server.
applicative language
(n.)
A language that performs all computations by applying
functions to values.
application programmer's interface (API)
(n.)
A software interface that enables applications to
communicate with each other. An API is the set of programming
language constructs or statements that can be coded in an
application program to obtain the specific functions and
services provided by an underlying
operating system or
service program.
architecture (n.)
The basic
plan along which a computer has been constructed. Popular parallel
architectures include processor
arrays, bus-based multiprocessors
(with caches of various sizes and structures)
and disjoint memory multicomputers. See
also Flynn's taxonomy. It may
also be used of any complex system, e.g. "software
architecture", "network architecture".
arithmetic and logic
unit (n.)
The part of the
central processing unit which performs operations such as
addition, subtraction and multiplication of integers and
bit-wise AND, OR, NOT, XOR and other Boolean operations.
arity (n.)
The number of arguments
taken by a function. Arity is also sometimes used in place of valence.
ARP (n.)
Address resolution protocol under
TCP/IP used to dynamically bind a high
level IP address to a low-level
physical hardware address. ARP is limited to a single physical
network that supports hardware broadcasting.
ARPAnet (n.)
The US Advanced Research
Project Agency network, which was the first large multi-site computer
network.
array (n.)
A sequence of objects in which
order is significant (as opposed to a set, which is a group of
objects in which order is not significant). An array variable in
a program stores an n-dimensional matrix or vector of data. The
term computer array is also used to describe the set of nodes of
a concurrent processor; this term implies but does not require
that the processor has a geometric or matrix-like
connectivity.
array constant (n.)
An array
reference within an iterative loop, all of whose subscripts are
invariant.
array processor (n.)
Any
computer designed primarily to perform
data parallel calculations on arrays or matrices.
The two principle architectures used are the
processor array and the
vector processor.
artificial intelligence
(n.)
A class of problems such as pattern recognition, decision making
and learning in which humans are clearly very proficient compared with
current computers.
ASCII (American Standard Code for Information
Interchange) (n.)
The ANSI and ISO supported standard for world-wide
representation of upper and lower-case Latin letters,
numbers, punctuation, special characters, etc, in
computerized data transmissions and operations. Includes
128 unique ASCII codes, each of which can be represented
by a 7 digit binary number in the range from 0000000
through 1111111. ASCII text is a subset of the ASCII
character set consisting principally of the printable
characters. HTML documents are
sent as ASCII files with tags that are interpreted by Web
browsers to display the content.
associative address (n.)
A method whereby access is made to an item whose key matches an access
key, as distinct from an access to an item at a specific address in
memory. See associative memory.
associative array (n.)
A collection of data (an array) where
individual items may be indexed (accessed) by a string, rather than by
an integer as is common in most programming languages.
associative memory (n.)
Memory
that can be accessed by content rather than by address; content addressable is
often used synonymously. An associative memory permits its user to
specify part of a pattern or key and retrieve the values
associated with that pattern. The
tuple space used to implement the generative
communication model is an associative memory.
associative processor (n.)
A processor array with associative memory.
asymmetric
multiprocessing (n.)
A form of multiprocessing in which a single processor acts as a
master to a series of slave processors. Contrast with
symmetric
multiprocessing.
asynchronous (n.)
A method of
transmission which does not require a common clock, but separates
fields of data by stop and start bits. See also synchronous.
asynchronous algorithm
(n.)
See relaxation method.
asynchronous message
passing (n.)
See message passing
.
asynchronous transfer
mode (n.)
A broadband cell relay protocol that cuts subscriber
data into fixed size packets for transfer across the wide area
network.
ATM (n.)
See
asynchronous transfer
mode.
atomic (adj.)
Not interruptible. An
atomic operation is one that always appears to have been executed as a
unit.
attached
vector-processor (n.)
A specialized processor for vector
computations, designed to be connected to a general purpose host
processor. The host processor supplies I/O
functions, a file system and other aspects of a computing system
environment.
automatic
vectorization (n.)
A compiler that takes code written in a
serial language (often Fortran or C) and translates it into
vector instructions. The vector instructions may be machine
specific or in a source form such as array extensions or as
subroutine calls to a vector library. See also compiler
optimization.
autonomous system (n.)
Internet (TCP/IP) terminology for a
collection of gateways (routers) that
fall under one administrative entity and cooperate using a common
interior gateway protocol (IGP). See subnetwork.
auxiliary memory (n.)
Memory
that is usually large, in capacity, but slow and inexpensive, often a
rotating magnetic or optical memory, whose main function is to store
large volumes of data and programs not being actively used by the
processors.
AVL tree (n.)
Binary tree having the
property that for any node in the tree, the difference in height
between the left and right subtrees of that node is no more than 1.
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.
backbone (n.)
The primary connectivity mechanism of a hierarchical distributed
system. All systems that have connectivity to an intermediate system on the
backbone are assured of connectivity to each other. This does not prevent
systems from setting up private arrangements with each other to bypass the
backbone for reasons of cost, performance, or security.
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 Subprograms: 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.
block distribution (n.)
A technique for distributing one dimensional data arrays to different
processors
in a parallel application that gives the first group or block of
values to the first processor, the
second values to the second processor, and so on. Each processor ends up with one contiguous
group of data values. See
cyclic distribution.
block-block distribution
(n.)
A technique for distributing two dimensional data arrays to different
processors in a parallel application
that gives a rectangular block of data values to each processor.
block-cyclic distribution
(n.)
A technique for distributing two dimensional data arrays to different
processors in a parallel application
that gives a one or more columns or rows of data values to each
processor. Whether rows or columns are
distributed depends on the programming language used.
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
neighbors. 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.
broadband (n.)
Characteristic of any network that multiplexes multiple,
independent network carriers onto a single cable. This is usually done
using frequency division multiplexing. Broadband technology allows
several networks to coexist on one single cable. Traffic from one
network does not interfere with traffic from another since the
conversations happen on different frequencies in the ether, rather
like the commercial radio system.
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
vendors, normally referring 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.
bus-based network (n.)
A communication network in which all processors are connected to
memory by means of a global, shared bus.
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 organized 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.
C (n.)
A programming language, originally
based on "B", designed by Dennis Ritchie. C is a low-level language
that has many features commonly found in higher-level languages. C and
C++ are two of the most common programming
languages used today.
C++ (n.)
An object-oriented programming
(OOP) language based on (or rather a superset of) C. It allows the user to use the key concepts of
OOP which are abstraction, classes, objects, encapsulation, and
inheritance.
cache (n.)
A high-speed memory, local
to a single processor, whose data transfers are carried out
automatically in hardware. Items are brought into a cache when they
are referenced, while any changes to values in a cache are
automatically written when they are no longer needed, when the cache
becomes full, or when some other process attempts to access them.
Also (v.) To bring something into a cache.
cache coherence (n.)
The problem that arises when copies of the same memory block are present
in the caches of one or more processors;
if a processor writes to and hence modifies that memory block, then
other processors will continue to access the old copy of the block
that is in their caches. Developing mechanisms for maintaining cache
coherence is a key design issue in parallel computers.
cache consistency (n.)
The problem of ensuring that the values associated with a particular
variable in the caches of several
processors are never visibly different. Also, see cache coherence.
cache hit (n.)
A cache access that
successfully finds the requested data.
cache line (n.)
The unit in which
data is fetched from memory to cache.
cache miss (n.)
A cache access that
fails to find the requested data. The cache must then be filled from
main memory at the expense of time.
caching-only server (n.)
A domain name server that is not
authoritative for any domain. This server queries servers that have
authority for the information needed and caches that data. See also
action server,
application server,
communications server,
session server.
CAD (n.)
Computer-Aided Design; a term which
can encompass all facets of the use of computers in manufacturing
although the term CAM is also in use.
CAE (n.)
Computer-Aided Engineering, like CAD, but usually applied to the use of
computers in fields such as civil and nautical engineering.
CAM (n.)
Computer-Aided Manufacturing.
CCITT (n.)
Consultative Committee
International Telephone and Telegraph is an international organization
which develops standards and defines interfaces for
telecommunications.
cell relay (n.)
Packet switching
technique which uses packets of fixed length, resulting in lower
processing speeds. Also known as BISDN
and ATM.
cellular automata (n.)
A
system made up of many discrete cells, each of which may be in one of
a finite number of states. A cell or automaton may change state only
at fixed, regular intervals, and only in accordance with fixed rules
that depend on cells own values and the values of neighbors within a
certain proximity.
cellular computer (n.)
A term
sometimes used to describe fine grain systems such as
neural networks,
systolic array, and
SIMD systems. Such
systems tend to be well suited for the implementation of cellular automata .
CFD (n.)
Computational fluid dynamics; the
simulation or prediction of fluid flow using computers, a field which
has generally required twice the computing power available at any
given time.
CGI (n.)
Common Gateway Interface. A specification of how a Web server can
communicate with a program (script or binary) in a way that provides
complete isolation of the server from the program, for the safety of
the server. Often such programs are referred to as CGI scripts.
When a Web client accesses a URL that points to a CGI script, the HTTP server specified in the URL executes the
program, passing to it any data provided by the client in a query
string. The output of the CGI script is then returned to the
originating client by the HTTP server specified in the original URL.
chain (n.)
A topology in which every processor is connected to
two others, except for two end processors that are connected to only
one other. See also Hamiltonian, ring.
chaining (n.)
The ability to take the
results of one vector operation and use them directly as input operands
to a second vector instruction, without the need to store to memory or
registers the results of the first vector operation. Chaining (or
linking as it is sometimes called) can significantly speed up a
calculation.
channel (n.)
A point-to-point connection
between two processes through which messages can be sent. Programming
systems that rely on channels are sometimes called
connection-oriented, to distinguish them from the more widespread
connectionless systems in which messages are sent to named destinations
rather than through named channels. See also CSP,
channel mask.
channel mask (n.)
A non-negative
integer specifying a set of communication channels. If the numbers of the channels
to be specified are I0,I1,...In-1, then the channel mask is the
integer for which these bit numbers are set to 1 and all other bits
are 0. For example, if the channels to be specified are numbered 0, 1
and 4, the corresponding channel mask is the binary number 10011, or
19, in which the bits numbered 0, 1 and 4 are set to 1.
chime (n.)
Chained vector time,
approximately equal to the vector length in a DO-loop. The number of
chimes required for a loop dominates the time required for execution.
A new chime begins each time a resource such as a functional unit,
vector register or memory path, must be reused.
chunksize (n.)
The number of
iterations of a parallel DO-loop grouped together as a single task in
order to increase the granularity of the task.
circuit switching (n.)
A
switching method where a dedicated path is set up between the
transmitter and receiver. The connection is transparent, meaning that
the switches do not try to interpret the data.
CISC (adj.)
Complicated instruction set
computer; a computer that provides many powerful but complicated
instructions. This term is also applied to software designs that give
users a large number of of complex basic operations. See also RISC.
clausal logic (n.)
A form of logic
in which all propositions are expressed in terms of AND, OR and NOT.
A six-stage process transforms any predicate calculus formula into
clausal form. See also clause.
clause (n.)
A sentence in formal logic.
See also clausal logic.
client (n.)
The terms server and
client are sometimes used to refer to computers and sometimes
used to refer to computer programs. For example, www.npac.syr.edu is a server, and
the HTTPD process running on www.npac.syr.edu is its server
process. Your office computer is a client and the Web browser running
on it acts as the client process.
CLNP (n.)
Connectionless network protocol,
also known as ISO-IP. This protocol
provides a datagram service and is OSI's
equivalent to IP.
clock cycle (n.)
The fundamental
period of time in a computer. Current technology will typically have
this measured in nanoseconds.
clock time (n.)
Physical or elapsed
time, as seen by an external observer. Nonrelativistic time. In
small computer systems where all components can be synchronized, clock
time and logical time may be the
same everywhere, but in large systems it may be difficult for a
processor to correlate the events it sees with the clock time an
external observer would see. The clock times of events define a
complete order on those events.
clustering (n.)
A type of
multiprocessor or architecture in which there is a
hierarchy of the units of replication. At the lowest level,
"processors" are replicated to form a "cluster". The cluster consists
of M processors and a shared switching network that provides
communication among the processors and access to a shared local
memory. At the next higher level, the clusters are replicated. A
clustered "system" consists of N clusters interconnected through a
global network that allows communication among the clusters and access
to a global memory that is shared among the cluster. The purpose of
clustering is to reduce conflicts in accessing shared resources,
whether these resources are the communication network or the storage
system. Typically, a clustered architecture is a "hyperstar", that is,
a star of stars. The cluster is a "star of processors" sharing a local
communication network and a local memory. The system is then a "star
of clusters" in which the shared resources are the global network and
the global memory.
CLTP (n.)
ConnectionLess Transport
Protocol, which provides end-to-end transport data addressing and is
OSI's equivalent to UDP.
CMIP (n.)
Common Management internet protocol is the OSI protocol for network management.
CMIS (n.)
Is the service performed by the
common management Internet protocol.
CMOS (n.)
Complementary Metal Oxide on
Silicon. A widely used chip technology. See also BiCMOS.
CMOT (n.)
Common management Internet
protocol (CMIP) over TCP is ISO's CMIP/CMIS mapping
of the OSI network management protocols and is based on the internet suite of protocols.
co-processor (n.)
An additional
processor attached to a main processor, to accelerate arithmetic, I/O or graphics operations.
coarse grain (adj.)
See granularity
Cobegin/Coend (n.)
A structured
way of indicating a set of statements that can be executed in
parallel.
combining (v.)
Joining messages
together as they traverse a network.
Combining may be done to reduce the total traffic in the network, to
reduce the number of times the start-up penalty of messaging is
incurred, or to reduce the number of messages reaching a particular
destination.
combining switch (n.)
An
element of an interconnection network that can combine certain types
of requests into one request and produce a response that mimics serial
execution of the requests.
common subexpression
(n.)
A combination of operations and operands that is repeated,
especially in a loop. A good compiler will not recompute the common
subexpressions but will save them in a register for reuse.
communicating
sequential processes (n.)
See CSP.
communication channel (n.)
See
channel
communication overhead (n.)
A
measure of the additional workload incurred in a parallel algorithm
due to communication between the nodes of the
parallel system. See also latency, startup cost
communications server (n.)
A type of gateway computer that translates packets on a local area
network into asynchronous signals, such as those used on telephone
lines or in serial communications. See also
action server,
application server,
caching-only server,
file server,
session server.
communication width (n.)
The
size of shared memory in an SIMD model assuming a global memory.
comparator (n.)
A device that
performs the compare-exchange
operation.
compare-exchange (v.)
The
fundamental operation of the bitonic
merge algorithm. Two numbers are brought together, compared,
and then exchanged, if necessary, so that they are in the proper order.
compiler directives
(n.)
Special keywords often specified as comments in the source code,
but recognized by the compiler as providing additional information
from the user for use in optimization.
compiler optimization (n.)
Rearranging or eliminating sections of a program during compilation to
achieve higher performance. Compiler optimization is usually applied
only within basic blocks and must
account for the possible dependence
of one section of a program on another.
complex instruction set
computer (adj.)
See CISC.
complexity (n.)
A measure of time or
space used by an algorithm. Without adjective this refers to time
complexity.
compress/index (n.)
A vector
operation used to deal with the nonzeroes of a large vector with
relatively few nonzeroes. The location of the nonzeroes is indicated
by an index vector (usually a bit vector of the same length in bits as
the full vector in words). The compress operation uses the index
vector to gather the nonzeroes into a dense vector where they are
operated on with a vector instruction. See also gather/scatter.
computation-to-communication ratio (n.)
The ratio of the
number of calculations a process does to the total size of the
messages it sends. A process that performs a few calculations and
then sends a single short message may have the same
computation-to-communication ratio as a process that performs millions
of calculations and then sends many large messages. The ratio may
also be measured by the ratio of the time spent calculating to the
time spent communicating, in which case the ratio's value depends on
the relative speeds of the processor and communications medium, and on
the startup cost and latency of communication. See also granularity.
communication overhead
(n.)
A measure of the additional workload incurred in a concurrent
algorithm due to communication between the nodes of the concurrent
processor. If communication is the only source of overhead, then the
communication overhead is given by: ((number of processors * parallel
run time) - sequential run time) / sequential run time.
computational science (n.)
A field that concentrates on the effective use of computer software,
hardware and mathematics to solve real problems. It is a term used
when it is desirable to distinguish the more pragmatic aspects of
computing from (1) computer
science, which often deals with the more theoretical aspects
of computing; and from (2) computing engineering, which deals
primarily with the design and construction of computers
themselves. Computational science is often thought of as the third leg
of science along with experimental and theoretical science.
computer science (n.)
The systematic study of computing systems and computation. The body of
knowledge resulting from this discipline contains theories for
understanding computing systems and methods; design methodology,
algorithms, and tools; methods for the testing of concepts; methods of
analysis and verification; and knowledge representation and
implementation.
concurrent computer (n.)
A
generic category, often used synonymously with
parallel computer to include
both multicomputer and multiprocessor.
concurrent processing
(adj.)
Simultaneous execution of instructions by two or more
processors within a computer.
condition
synchronization (n.)
Process of delaying the continued
execution of a process until some data object it shares with another
process is in an appropriate state.
configuration (n.)
A particular
selection of the types of processes that could make up a parallel
program. Configuration is trivial in the SPMD
model, in which every processor runs a single identical process, but
can be complicated in the general MIMD case,
particularly if user-level processes rely on libraries that may
themselves require extra processes. See also mapping.
conjugate gradient
method (n.)
A technique for solving systems of linear
algebraic equations, which proceeds by minimizing a quadratic residual
error function. The method is iterative but quite powerful: in the
absence of roundoff error, it will converge exactly in M steps, where
M is the order of the system in question.
content addressable (adj.)
See associative memory.
contention (n.)
Conflict that arises
when two or more requests are made concurrently for a resource that
cannot be shared. Processes running on a single processor may contend
for CPU time, or a network may suffer from
contention if several messages attempt to traverse the same link at the same time.
context switching (n.)
Saving
the state of one process and replacing it with that of another that is
time sharing the same processor. If
little time is required to switch contexts,
processor overloading can
be an effective way to hide latency in a
message passing system.
control process (n.)
A process
which controls the execution of a program on a
concurrent computer. The
major tasks performed by the control process are to initiate execution
of the necessary code on each node and to
provide I/O and other service facilities for the
nodes.
control-driven (adj.)
Refers to
an architecture with one or more program
counters that determine the order in which instructions are executed.
cost (n.)
Complexity of an algorithm
multiplied by the number of processors used.
COW (cluster of workstations) (n.)
A group of workstations interconnected through a high speed network
that can be used for high performance computing. It provides
excellent price/performance. See also clustering and NOW.
cpu (n.)
Central Processing Unit or
processor unit of a sequential computer system. Sometimes used to
mean one processor element of a
parallel computer system.
critical node (n.)
when a node is
inserted into an AVL tree, the critical node is the root of the
subtree about which a rebalancing is going to take place.
critical section (n.)
A section
of program that can be executed by at most one process at a time.
CSP (n.)
Communicating sequential processes;
an approach to parallelism in which anonymous processes communicate by
sending messages through named point-to-point channels. CSP was coined by Hoare in 1985. All
communication is synchronous in that the
process that reaches the communication operation first is blocked until a complementary process reaches the
same operation. See also guard.
cube-connected cycles
network (n.)
A processor organization that is a variant of a hypercube. Each hypercube node becomes a
cycle of nodes, and no node has more than three connections to other
nodes.
cycle (n.)
A cycle of the computer
clock is an electronic signal that counts a single unit of time within
a computer.
cycle time (n.)
The length of of a
single cycle of a computer function such as a memory cycle or
processor cycle. See also clock cycle.
cyclic distribution (n.)
A technique for distributing one dimensional data arrays to different
processors in a parallel application
that gives the first value to the first processor, the second value to the second
processor, and so on until all the
data values have been given to the processors. This method is similar
to dealing cards from a deck to players. See
block distribution.
cyclic reduction (n.)
A
parallel algorithm to solve general first order linear recurrence
relations.
D4 (n.)
An AT&T specified format for T1 facilities. Designates every 193rd bit as
reserved for framing and synchronization information. Term originates
from the fourth generation digital channel bank.
DACS (n.)
Digital Access Cross-connect
System is a switch that enables test access and switching of digital
signals in a T system.
data bus (n.)
A set of hardware lines
(wires) used for data transfer among the components of a computer
system. See also address bus.
data cache (n.)
A cache that holds
data but does not hold instructions.
data dependency (n.)
A situation
existing between two statements if one statement can store into a
location that is later accessed by the other statement. See also dependence.
data flow analysis (n.)
A process of finding dependencies among instructions.
data flow graph (n.)
(1) Machine
language for a data flow computer; (2) Result of data flow analysis.
data parallelism (n.)
A model
of parallel computing in which a single operation can be applied to
all elements of a data structure simultaneously. Typically, these
data structures are arrays, and the operations are arithmetic and act
independently on every array element, or
reduction operations.
See also array processor,
processor
array, SIMD and
vector processor.
data-driven (n.)
A data flow
architecture in which execution of instructions depends on
availability of operands.
dataflow (n.)
A model of parallel
computing in which programs are represented as
dependence graphs and each
operation is automatically blocked until
the values on which it depends are available. The parallel functional
and parallel logic programming models are very similar to the dataflow
model.
dead code (n.)
A portion of a program
that does not have to be executed (because the values it calculates
will never be used) or that will never be entered.
Compiler optimization
usually removes sections of dead code. See also dependence.
deadlock (n.)
A situation in which each
possible activity is blocked, waiting on some
other activity that is also blocked. If a directed graph represents
how activities depend on others, then deadlock arises if and only if
there is a cycle in this graph. See also
dependence graph.
decision problem (n.)
A problem
whose solution, if any, is found by satisfying a set of constraints.
declustered (adj.)
A
file system that distributes blocks
of individual files between several disks. This contrasts with a
traditional file system, in which all blocks of a single file are
placed on the same disk. See also striped.
decomposition (n.)
A division of a
data structure into substructures that can be distributed separately,
or a technique for dividing a computation into subcomputations that
can be executed separately. The most common decomposition strategies
in parallel computing are:
functional decomposition; geometric decomposition and
iterative decomposition.
dedicated throughput (n.)
The number of results returned for a single job per time unit.
demand-driven (n.)
data flow
architecture in which
execution of an instruction depends upon both availability of its
operands and a request for the result.
dependence (n.)
The relationship of a
calculation B to a calculation A if changes to A, or to the ordering
of A and B, could affect B. If A and B are calculations in a program,
for example, then B is dependent on A if B uses values calculated by
A. There are four types of dependence: true dependence, where B uses
values calculated by A; antidependence, where A uses values
overwritten by B; output dependence, where A and B both write to the
same variables; control dependence, where B's execution is controlled
by values set in A. Dependence is also used in message routing to mean that some activity X cannot
proceed until another activity Y has completed. For example, if X and
Y are messages attempting to pass through a region with limited buffer space, and Y currently holds some or
all of the buffer, X may depend on Y releasing some buffer space
before proceeding.
dependence graph (n.)
A
directed graph whose nodes represent calculations and whose edges
represent dependencies among those calculations. If the calculation
represented by node k depends on the calculations represented by nodes
i and j, then the dependence graph contains the edges i-k and j-k.
See also compiler
optimization, dataflow,
dependence.
dependence analysis (n.)
An
analysis by compiler or precompiler that reveals which portions of a
program depend on the prior completion of other portions of the
program. Dependency analysis usually relates statements in an
iterative code construct.
depth (n.)
Parallel time complexity.
deque (n.)
A double ended queue; that is a
list of elements on which insertions and deletions can be performed at
both the front and rear.
deterministic model (n.)
A
task model in which precedence relations between tasks and the
execution time needed by each task are fixed and known before the
schedule is devised.
diameter (n.)
The distance across a
graph, measured by the number of links traversed.
Diameter is usually taken to mean maximum diameter (ie the greatest
internode distance in the graph, but it can also mean the average of
all internode distances. Diameter is sometimes used as a measure of
the goodness of a topology.
direct mapping (n.)
A cache that
has a set associativity of one so that each item has a unique place in
the cache at which it can be stored.
direct memory access (n.)
See DMA.
direct method (n.)
Any technique
for solving a system of equations that relies on linear algebra
directly. LU decomposition with back substitution is an example of a
direct method. See also
indirect method.
direct naming (n.)
A message passing scheme in which
source and destination designators are the names of processes.
directed graph (n.)
A graph in
which the edges have an orientation, denoted by arrowheads.
disjoint memory (n.)
Memory that
appears to the user to be divided amongst many separate address spaces. In a multicomputer, each processor typically has
its own private memory and manages
requests to it from processes running on other processors. Disjoint
memory is more commonly called
distributed memory, but the
memory of many shared memory>
computers is physically distributed.
disk striping (n.)
A technique of
interleaving a disk file across two or more disk drives to enhance
input/output performance. The performance gain is a function of the
number of drives and channels used.
distributed computer (n.)
A
computer made up of many smaller and potentially independent
computers, such as a network of workstations.
This architecture is increasingly studied
because of its cost effectiveness and flexibility. Distributed
computers are often heterogeneous. See
also multi-processor, multicomputer.
distributed memory (n.)
Memory that is physically distributed amongst several modules. A distributed memory architecture may appear to users to have a
single address space and a single shared memory or may appear as disjoint memory made up of many separate
address spaces.
divide and conquer (n.)
A
problem solving methodology that involves partitioning a problem into
subproblems, solving the subproblems, and then combining the solutions
to the subproblems into a solution for the original problem.
DLCI (n.)
Data Link Connection Identifier,
a frame relay header field that
identifies the destination of the packet.
DMA (n.)
Direct Memory Access; allows
devices on a bus to access memory without requiring intervention by the CPU.
DNA (n.)
Digital Network Architecture is
Digital Equipment Corporation's proprietary digital network
architecture and is also known as DECnet.
domain (n.)
That part of a larger
computing resource allocated for the sole use of a specific user or
group of users. See also space sharing.
domain decomposition (n.)
See decomposition
domain name (n.)
The name assigned to a group of systems on a local network that share
administrative files. The domain name is required for the network
information service database to work properly. See also domain.
double buffering (n.)
In computer graphics, the process of using two
frame buffers for
smooth animation. Graphical contents of one frame buffer are displayed
while updates occur on the other buffer. When the updates are
complete, the buffers are switched. Only complete images are
displayed, and the process of drawing is not shown. The result is the
appearance of smooth animation.
DRAM (n.)
Dynamic RAM; memory which periodically needs
refreshing, and is therefore usually slower than SRAM but is cheaper to produce.
DS0 (n.)
Digital service hierarchy level 0
with a maximum channel capacity of 64kbps.
DS1 (n.)
Digital service hierarchy level 1
with a maximum channel capacity of 1.544Mbps. This term is used
interchangeably with T1. 24 DS-0 channels per DS1.
DS3 (n.)
Digital service hierarchy level 3
with a maximum channel capacity of 44.736. This term is used
interchangeably with T3. 28 DS1 channels per
DS3.
dusty deck (n.)
A term applied to old
programs (usually Fortran or Cobol). The term is derived from the
image of a deck of punched cards grown dusty over the years.
dynamic allocation (n.)
(1) An allocation technique in which the resources assigned to a
system are determined by criteria applied at the moment of need. (2)
Assignment of system resources to a program at the time the program is
executed rather than at the time it is loaded into main
storage. Dynamic allocation almost always implies that dynamic
deallocation is possible too, so data structures can be created and
destroyed as required.
dynamic channel naming
(n.)
A message passing scheme
allowing source and destination designators to be established at run
time.
dynamic decomposition (n.)
A task allocation policy that assumes tasks are generated at execution
time. See also decomposition.
e-cube routing (n.)
A message routing algorithm used on binary hypercubes. If <|Sn-1...S0|> and <|Dn-1...D0|>
are the binary co-ordinates of the source and destination of the
message, and <|Xn-1...X0>| their difference, then the e-cube algorithm
routes the message along link parallel to the axes
corresponding to 1's in <|Xn-1...X0|>, in order from highest to
lowest. See also Metropolis
routing, randomized
routing.
E1 (n.)
The European standard for high speed
digital transmission, defined as 2.048Mbps. The E1 has 31 available
64k channels for traffic use. Also referred as a 2Meg, European T1 and CEPT.
eager evaluation (n.)
A
scheduling policy under which each computation begins as soon as its
inputs are ready or its necessary preconditions have been satisfied.
This is the scheduling policy used in most programs, but contrasts
with the lazy evaluation policy often
used in functional and logic programming. See also dataflow,
dependence, and
dependence graph.
ECL (n.)
Emitter-coupled logic; a high
speed, high power transistor technology for chip manufacture. See
also BiCMOS, CMOS.
efficiency (n.)
A measure of hardware
utilization, equal to the ratio of speedup
achieved on P processors to P itself. See also isoefficiency, optimality.
EGP (n.)
External Gateway protocol is used
by gateways in different autonomous systems. EGP allows gateways to
share routing information through advertisements.
enumeration sort (n.)
A sort
that finds the position of each name by determining the number of
names smaller than it.
EPROM (n.)
(Pronounced "ee-prom.") Acronym for erasable programmable read-only
memory. A non-volatile memory chip that is programmed after they it is
manufactured. EPROMS are a good way for hardware vendors to put
variable or constantly changing code into a prototype system when the
cost of producing many PROM chips would be prohibitive. EPROMs differ
from PROMs in that they can be erased (generally by removing a
protective cover from the top of the chip package and exposing the
semiconductor material to the ultraviolet light) and can be
reprogrammed after having been erased. See also ROM.
ES-IS (n.)
End System to Intermediate
System is an OSI protocol that allows end
systems to announce themselves as intermediate systems. End Systems
are equivalent to the Internet concept
of a host that uses all layers in the communications model.
Intermediate Systems are relay communications nodes or forwarders
between End Systems and are effectively a subset of End Systems.
ethernet (n.)
A LAN protocol that
supports high speed communications in the local area. Usually rates
are at 10Mbps.
expand (n.)
A vector computer instruction
that stores the elements of a vector according to the values in a
corresponding masking vector.
expected space
complexity (n.)
The average amount of space used by an
algorithm over all possible inputs.
expected time
complexity (n.)
The average amount of time used by an
algorithm over all possible inputs.
explicitly parallel (n.)
Language semantics that describe which computations are independent
and can be performed in parallel. See also
implicitly parallel.
fact (n.)
In the context of logic
programming, a fact is a Horn clause with
a head but no body.
fairness (n.)
A property of a
concurrent system. If a system is fair, then in the long run all
processes are served equally. No process has preferential access to
semaphores and in particular no process can
livelock. See also deadlock.
fast Fourier transform
(n.)
See FFT
fast packet (n.)
Fast packet is a
general term for various streamlined packet technologies including frame relay, BISDN and ATM.
Compared to X.25 packet switching, fast packet contains a much reduced
functionality, but with the lower overhead, fast packet systems can
operate at higher rates at the same processing cost.
FastPacketTM (n.)
StrataCom
Corporation's trademarked term for their proprietary switching
technique, which uses 192 bit packets.
FDDI (fiber distributed data interface)
(n.)
A fast digital data interface. The underlying medium is fiber
optics, and the topology is a dual-attached, counter-rotating token ring.
See also ethernet.
fetch-and-add (n.)
A computer
synchronization instruction that updates a word in memory, returns the
value before the update, and produces a set of results as if the
processors executed in some arbitrary order. See also prefetch.
FFT (n.)
The fast Fourier transform is a
technique for the rapid calculation of discrete Fourier transform of a
function specified discretely at regular intervals. The technique
makes use of a butterfly data structure.
FIFO (n.)
First in, first out, a queue.
file server (n.)
A process running
on a computer that provides access to files for remote user
systems. See also server.
file system (n.)
The hardware used
for nonvolatile data storage; the system software that controls this
hardware; the architecture of this
hardware and software. A parallel file system is one that can be read
or written to by many processors simultaneously. See also RAID.
fine grain (adj.)
See granularity
finite difference
method (n.)
A direct method for
the approximate solution of partial differential equations on a
discrete grid, by approximating derivatives of the unknown quantities
on the grid by linear differences. Array
processors lend themselves very well to the efficient
implementation to this sort of application. See also
finite element method.
finite element method
(n.)
An approximate method for solving partial differential equations by
replacing continuous functions by piecewise approximations defined on
polygons, which are referred to as elements. Usually polynomial
approximations are used. The finite element method reduces the
problem of finding the solution at the vertices of the polygons to
that of solving a set of linear equations. This task may then be
accomplished by a number of methods, including
Gaussian elimination, the
conjugate gradient
method and the multigrid
method. See also
finite difference method.
flit (n.)
A flow control unit - the basic
unit of information sent through a message
passing system that uses virtual
cut-through or wormhole routing.
FLOPS (n.)
Floating point operations per
second; a measure of memory access performance, equal to the rat eat
which a machine can perform single-precision floating-point
calculations. See also WARPS, MFLOPS, and MIPS.
Flynn's Taxonomy (n.)
A
classification system for architectures
that has two axes: the number of instructions streams executing
concurrently, and the number of data sets to which those instructions
are being applied. The scheme was proposed by Flynn in 1966. See
also SPMD, MIMD, SIMD, SISD.
forall (n.)
A programming construct that
specifies a set of loop iterations and further specifies that these
iterations can be done in any order. data parallel and shared variable programs are often
expressed using forall loops.
fork (v.)
To create a new process that is a
copy of its immediate parent. See also: join, spawn.
forward reduction (n.)
See LU decomposition.
FPU (n.)
Floating point unit; either a
separate chip or an area of silicon on the CPU
specialized to accelerate floating point arithmetic.
FRAD (n.)
Frame relay
assembler/disassembler, used to interface a LAN with a frame
relay WAN.
frame buffer (n.)
Display memory that temporarily stores (buffers) a full frame of
picture data at one time. Frame buffers are composed of arrays of bit
values that correspond to the display's pixels. The number of bits per
pixel in the frame buffer determines the complexity of images that can
be displayed. See also double
buffering.
frame relay (n.)
A packet interface
data transmission protocol used for connecting LANs via a WAN topology
at rates from 56Kbps to T1/E1.
frame slip (n.)
Also called just
slip, is any shift of the timing on a circuit.
FT-1 (n.)
Fractional digital service
hierarchy level 1 with service in multiples of 56/64Kbps 2 channels
(112/128Kbps) or above, and up to 23 channels. 256/512/768/1024Kbps
are common rates for this type of service. Also called fractional T1.
FT-3 (n.)
Fractional digital service
hierarchy level 3 with service in multiples of 1.544Mbps. Also called
fractional T3.
FTP (n.)
File transfer protocol is the TCP/IP standard for remote file transfer.
FTP uses telnet and TCP protocols.
full matrix (n.)
A full matrix is
one in which the number of zero elements is small (in some sense)
compared to the total number of elements. See also
sparse matrix.
functional
decomposition (n.)
See decomposition.
functional unit (n.)
Functionally independent part of the ALU each of which performs a
specific function, for example: address calculation; floating-point
add or floating-point multiply.
futures (n.)
A programming construct
specifying that the value of some computation will be needed at some
later point, but allowing the system to schedule that computation to
run at any arbitrary time. Futures are one way to present lazy evaluation in shared variable programming. See also eager evaluation.
fuzzy barrier (n.)
A pair of points
in a program such that no process may pass the second point before all
processes have reached the first. Fuzzy barriers are often used
inside loop iterations to ensure that no changes are made during an
iteration before all values needed in the previous iteration have been
read. See also barrier,
barrier synchronization,
dependence.
GaAs (n.)
Gallium arsenide; an relatively
new semiconductor material, still not yet fully mastered by chip
manufacturers. GaAs components can run much faster than silicon-based
components. See also CMOS.
game tree (n.)
The state space tree
representation of a game position.
Gantt chart (n.)
A diagram used to
illustrate a deterministic schedule.
gather/scatter (n.)
The
operations related to large sparse data structures. A full vector
with relatively few nonzeroes is transformed into a vector with only
those nonzeroes by using a gather operation. The full vector, or one
with the same structure, is built from the inverse operation or
scatter. The process is accomplished with an index vector, which is
usually the length of the number of nonzeroes, with each component
being the relative location in the full vector. See also compress/index.
gateway (n.)
The original Internet term for what is now called a router or more
precisely, IP router. In modern usage, the terms "gateway"
and "application gateway" refer to systems that do translation from
some native format to another. Examples include X.400 to/from RFC 822
electronic mail gateways.
Gauss-Seidel method (n.)
An
iterative method for solving partial differential equations on a grid.
When updating a grid point the new value depends on the current values
at the neighboring grid points, some of which are from the previous
iteration and some, which have already been updated, are from the
current iteration. So updates are performed by sweeping through the
grid in some user-chosen fashion. The key feature of this algorithm
is that it makes use of new information (updated grid point values) as
soon as they become available.
Gaussian elimination (n.)
A
method for solving sets of simultaneous linear equations by
eliminating variables from the successive equations. The original
equation in the form Ax=b (A is a matrix, b the vector of known
values, and x the unknown solution vector) is reduced to Ux=c, where U
is an upper triangular matrix. The solution vector x can then be
found by back substitution. This
method is usually formulated as LU
decomposition.
GAXPY (n.)
A generalized SAXPY operation, taking linear combinations of a set
of columns and accumulating the columns in a vector, as in a
matrix-vector product.
generative
communication (n.)
A model of parallel computing in which
processes that have been spawned dynamically turn
into data upon completion, and data may be stored in tuples in one or more shared
tuple spaces. A process may add
tuples to a tuple space, or remove then by matching against their
contents. See also associative
memory, shared variables,
virtual shared memory.
geographic
information systems (GIS) (n.)
A graphic application using a database of specialized
information, such as geographical and demographic data. Applications
written for the GIS market use the database information to determine
such things as the best location for a new fire station or shopping
center, the most likely location of archaeological remains, and so on.
geometric decomposition
(n.)
See decomposition.
GGP (n.)
Gateway to gateway protocol is the
protocol used by core gateways to exchange routing information.
GKS (n.)
The Graphics Kernel Standard; a
graphics standard developed for pen plotters and now supported on a
wide variety of pixel based devices.
global addressing (n.)
A frame
relay addressing scheme which uses the DLCI
to identify a specific end across device somewhere else in the frame
relay network. In a global addressing scheme, the DLCI is a unique
identifier for each IPX port in the
network.
grain (n.)
See granularity
granularity (n.)
The size of
operations done by a process between communications events. A fine
grained process may perform only a few arithmetic operations between
processing one message and the next, whereas a coarse grained process
may perform millions. See also
computation-to-communication ratio.
graph (n.)
an entity consisting of a set
of vertices and a set of edges between pairs of vertices.
graphical user interface
(GUI) (n.)
The graphical user interface, or GUI, provides the user with a
method of interacting with the computer and its special applications,
usually via a mouse or other selection device. The GUI usually
includes such things as windows, an intuitive method of manipulating
directories and files, and icons.
Gray code (n.)
A mapping which labels the lattice points on an
n-dimensional grid with the integers 0,1,2,...2^d-1, so that the
labels at adjacent grid points differ in precisely one bit in their
integer representation.
Grosch's Law (n.)
an empirical rule
that the cost of computer systems increases as the square root of the
computational power of the systems.
guard (n.)
A logical condition that
controls whether a communication operation can take place. Guards are
usually defined as part of the syntax and semantics of CSP-based languages.
guard ring (n.)
Parallel algorithms
operating on a two dimensional grid generally store grid values in a
two dimensional array, geometrically
decomposed across the nodes of the parallel computer. The guard
ring is the additional storage allocated around the edges of the array
to hold the values at the grid points lying along the adjacent
boundaries of neighboring nodes. These values are obtained by
communication between nodes.
Gustafson's Law (n.)
A rule
stating that if the size of most problems is scaled up sufficiently,
then any required efficiency can be
achieved on any number of processors, as stated by Gustafson in 1988.
See also Amdahl's Law, efficiency.
halo (n.)
The region around a point in a mesh, whose values are used when updating the
value of the central point. In a
cellular automata, The halo
comprises those neighboring cells whose values are used by the
automaton's update rule.
Hamiltonian (n.)
A closed path
through a graph which passes through each node in the graph exactly
once.
HDB3 (n.)
High density bipolar three, a
line interface standard for E1 which is
similar to B8ZS, which eliminates data
streams with 8 or more consecutive zeros. Allows for 64Kbps clear
channel capacity and still assure a minimum ones density required by
E1 lines.
HDLC (n.)
High level link control is an ISO link level protocol standard. CCITT uses HDLC for its link access protocol
with X.25 networks. HDLC was used in the
ARPANET to transfer frames between hosts
and packet switched networks.
height (n.)
In graph theory, height is
the length of the longest path from the root of a tree to one of its
leaves.
heterogeneous (adj.)
Containing
components of more than one kind. A heterogeneous architecture may be one in which some
components are processors, and others memories, or it may be one that
uses different types of processor together. See also distributed computer, homogeneous.
hexadecimal (n.)
Pertaining to a fixed-radix numeration
system having a radix of sixteen - a base-16 number.
high-order interleaving
(n.)
Memory interleaving strategy based on high-order bits of an
address.
HiPPI (n.)
High performance parallel
interface; a point to point 100 MByte/sec interface standard used for
networking components of high performance multicomputers together.
hit ratio (n.)
The ratio of the number
of times data requested from a cache is found (or hit) to the number
of times it is not found (or missed).
homogeneous (adj.)
Made up of
identical components. A homogeneous architecture is one in which each
element is of the same type; processor
arrays and multicomputers
are usually homogeneous. See also heterogeneous.
hop (n.)
A network connection between two
distant nodes.
horizontal processing (n.)
Act of processing a two dimensional array row by row.
Horn clause (n.)
Also known as a definite clause. It is a clause that
contains at most one conclusion.
HotJava (n.) A
world wide web (WWW) browser, developed by Sun Microsystems, that
uses Java. HotJava provides the ability to
import code fragments, called applets,
across the net and execute them.
hot-spot contention (n.)
An
interference phenomenon observed in multiprocessors caused by memory
access statistics being slightly skewed from a uniform distribution to
favor a specific memory module.
HPCC (n.)
An acronym for High Performance
Computing and Communications, which is the field of information
addressed by this glossary. A
USA National Coordination
Office for HPCC also exists, and other information on HPCC can
be found from the Northeast Parallel
Architectures Center, the Center for Research in
Parallel Computing the National Software Exchange or
the Edinburgh Parallel Computing
Center depending upon your geography.
HPF (n.)
An acronym for High Performance Fortran, which is a programming language
based on Fortran90, which offers facilities to parallelize one's
Fortran code on a fairly high level.
HTML (n.)
Hypertext Transfer
Protocol. Based on SGML, this is a file
format for hypertext documents on the Internet. It is very simple and
allows for the embedding of images, sounds, video streams, form
fields, and simple text formatting. References to other objects are
embedded using URLs.
HTTP (n.)
An acronym for Hypertext
Transfer Protocol, which is the Internet protocol, based on TCP/IP, used to fetch hypertext objects from
remote hosts.
hypercube (n.)
A topology of which each node is the vertex
of a d-Dimensional cube. In a binary hypercube, each node is connected to n others, and its
co-ordinates are one of the 2^n different n-bit sequences of binary
digits. Most early American multicomputers used hypercubic
topologies, and so the term hypercube is sometimes used as a synonym
for multicomputers. See also butterfly,
e-cube routing,
shuffle exchange
network.
I/O (n.)
Refers to the hardware and software
mechanisms connecting a computer with its environment. This includes
connections between the computer and its disk and bulk storage system
and also connections to user terminals, graphics systems, and networks
to other computer systems or devices. Standard I/O is a particular
software package developed under UNIX for the C programming language.
ICMP (n.)
Is the Internet control message
protocol and is used to handle errors and control messages at the
Internet protocol layer. ICMP is considered to be part of IP and is used to test whether a destination is
reachable and responding.
IEEE 802.3 (n.)
The standard for
Carrier Sense Multiple Access with Collision Detection is one of the
most used LAN protocols.
IGP (n.)
Interior Gateway Protocol is used
to exchange routing information between routers in the routers within an autonomous system. The
RIP and OSPF are
examples of IGP.
ILMI (n.)
Interim Local Management
Interface that is the de facto standard until a standard based
committee designates a standardized protocol suite. In the last few
years ILMI has been popular due to the frequency of changes in the
tele-communications industry.
implicitly parallel (n.)
Language semantics that do not allow the user to explicitly describe
which computations are independent and can be performed in parallel.
For an implicitly parallel language, the compiler must deduce or prove
independence in order to make use of parallel hardware. The
comparative difficulty of the deduction separates implicitly parallel
languages from explicitly parallel ones.
indirect method (n.)
Any
technique for solving a system of equations that does not rely on
linear algebra directly. Successive over-relaxation is an example of
an indirect method. See also
direct method.
information (n.)
A collection of
related data objects.
inner product method (n.)
Method of matrix multiplication in which one element of the resultant
matrix is computed at a time. See also
middle product method
input/output (n.)
See I/O.
instruction buffering (n.)
Process of prefetching instructions
with the goal of never making the processor wait for an instruction to
be fetched. This is sometimes also known as instruction
look-ahead.
instruction cache (n.)
A cache
memory that holds only instructions but not data.
instruction pipelining
(n.)
Strategy of allowing more than one instruction to be in some
stage of execution at the same time. See also MISD.
instruction scheduling
(n.)
A strategy of a compiler to analyze the outcome of the
operations specified in a program and to issue instructions in an
optimal manner. That is, the instructions are not necessarily issued
in the order specified by the programmer, but in an order that
optimally uses the registers, functional units and memory paths of the
computer, while at the same time guaranteeing correct results for the
computation.
instruction set (n.)
The set of
low level instructions that a computer is capable of executing.
Programs expressed in a high level language must ultimately be reduced
to these.
instruction stream (n.)
A set of instructions that must be executed serially, although these
instructions may be executed on different processors.
interactive vectorizer
(n.)
An interactive program to help a user vectorize source code.
See also true ratio.
interconnection network
(n.)
The system of logic and conductors that connects the processors
in a parallel computer system. Some examples are bus, mesh, hypercube
and Omega networks.
interleaved memory (n.)
Memory divide into a number of modules or banks that can be accessed
simultaneously.
internal sort (n.)
Sorting a table
of names contained entirely in primary memory.
internationalization
(n.)
The process of altering a program so that it is portable across
several native languages. This portability may support both different
character sets, such as the 8-bit ISO 8859/1 (ISO Latin 1) character
set and the 7-bit ASCII character set, and different languages for
documentation, help screens, and so on. See also localization.
interprocess control
(IPC) (n.)
The process of sharing data between
processes and, when necessary, coordinating access to the shared data.
interprocessor
communication (n.)
The passing of data and information among
the processors of a parallel computer during the execution of a
parallel program.
interprocessor
contention (n.)
Conflicts caused when multiple CPU's compete
for shared system resources. For example, memory bank conflicts for a
user's code in global memory architectures are caused by other
processors running independent applications.
interrupt-driven system
(n.)
A system whose processes communicate by
message passing in such a way
that when a message is delivered to its destination process it
interrupts execution of that process and initiates execution of an
interrupt handler process, which stores the message for subsequent
retrieval. On completion of the interrupt-handler process (which sets
some flag or sends some signal to denote an available message), the
original process resumes execution.
interval routing (n.)
A routing algorithm that assigns an integer
identifier to each possible destination and then labels the outgoing
links of each node with a single contiguous interval or
window so that a message can be routed simply by sending it out the
link in whose interval its destination identifier falls.
intranet (n.)
An enterprise's network
infrastructure, particularly the part that is accessible via Internet
TCP/IP protocols and is shielded from
general public view.
invariant (n.)
A variable, especially
in a DO-loop, that appears only on the right side of an equals sign.
The variable is read only, it is never assigned a new value.
invariant expression (n.)
An expression, especially in a DO-loop, all of whose operands are invariant or constant.
IP (n.)
The Internet protocol that defines
the unit of information passed between systems that provides a basis
packet delivery service. It handles best effort hpccgloss.html
delivery service and includes ICMP. See
also IP address.
IP address (n.)
The Internet protocol
address which is a 32-bit address assigned to a host. The IP address
has a host component and a network component.
IPX (n.)
Integrated Packet Exchange for
example Stratacom's Packet switch for public and private T1 and E1 networks.
IPX/link (n.)
This application for
NetWare connects a PC Novell NetWare LAN through a network interface
device.
ISDN (n.)
Integrated Services Digital Network. An emerging technology that is
beginning to be offered by the telephone carriers of the world. ISDN
combines voice and digital network services in a single medium making
it possible to offer customers digital data services as well as voice
connections through a single "wire."
IS-IS (n.)
Intermediate system to
intermediate system protocol is the ISO
protocol that defines how intermediate systems exchange routing
information.
ISO (n.)
International Standards
Organization, which, among other things, sets standards for
programming languages.
ISODE (n.)
ISO
development environment software provides an ISO transport level
protocol interface that resides on top of TCP/IP.
isoefficiency (n.)
A way to
quantify the effect of scaling problem size on an algorithm's efficiency. For a given efficiency, the
isoefficiency function for an algorithm specifies what size of problem
must be solved on a given number of processors to achieve that
efficiency.
iterative decomposition
(n.)
A decomposition involving
breaking down a calculation in which one or more operations are
repeatedly applied to one or more data values by treating each data
subset / operation subset as a separate task and distributing tasks
amongst available processors, either deterministically or randomly.
In a deterministic decomposition, the data to be processed are fixed
and the same operations are applied to each. In a speculative
decomposition, different operations are applied simultaneously to the
same input until at least one has completed. See also functional decomposition
and geometric
decomposition.
iterative deepening (n.)
Use of a D-ply search to prepare for a (D+1)-ply search.
Jacobi method (n.)
A stationary,
iterative method for solving a partial differential equation on a
discrete grid. The update of each grid point depends only on the
values at neighboring grid points from the previous iteration. See
also Gauss-Seidel method.
Java (n.)
An object-oriented programming
language for portable, interpretive code that supports interaction
among remote objects. Java was developed and specified by Sun
Microsystems, Incorporated. The Java environment consists of the
JavaOS, the Virtual Machines for various platforms, the
object-oriented Java programming language, and several class
libraries.
JPEG (Joint Photographic Experts Group)
(n.)
The name of the committee that designed the photographic
image-compression standard. JPEG is optimized for
compressing full-color or gray-scale photographic-type,
digital images.
join (v.)
To wait for the termination of one
or more descendent processes that were forked at
some earlier time. See also spawn.
KA9Q (n.)
An implementation of TCP/IP for amateur packet radio systems.
Kermit (n.)
A public domain file
transfer and terminal emulation program. Similar in functionality to
uucp.
kernel (n.)
A process providing basic
services. A service kernel can run on every processor to support
minimal operating system services,
while a routing kernel can handle or forward
incoming messages.
key (n.)
Unique object of a search.
kHz (n.)
Abbreviation for kilohertz (1000 Hertz).
kilobyte (Kbyte) (n.)
A unit of measure equal to 1024 bytes.
knowledge (n.)
Information plus
semantic meaning.
knowledge
information processing system (n.)
A computer system that
processes knowledge, rather than data or
information.
LAN (n.)
Local area network, a network of
multiple interconnected data terminals or devices within a local area
to facilitate data transfer. Most notable of LAN topologies is
ethernet,
token ring, FDDI, etc.
LAP (n.)
Link access procedure is a modified
form of HDLC that CCITT specified for X.25 networks. LAP-B is link access
procedures- balanced and is the X.25 implementation of SDLC and similarly, LAP-D is the ISDN and frame relay implementation of SDLC.
LAPACK (n.)
A linear algebra software
package, which has been mounted on a wide range of platforms. It
evolved from the older LINPACK package from Netlib. See also ScaLAPACK.
latency (n.)
The time taken to service a
request or deliver a message which is independent of the size or
nature of the operation. The latency of a
message passing system is the
minimum time to deliver a message, even one of zero length that does
not have to leave the source processor; the latency of a file system is the time required to
decode and execute a null operation. See also
startup cost.
lazy evaluation (n.)
A
Scheduling policy under which no calculation is begun until it is
certain that its result is needed. This policy contrasts with the eager evaluation used in most programs,
but is often used in functional and logic programming. See also dataflow, dependence,
dependence graph, futures.
LD-1 (n.)
An integrated T1 with possibly voice, data and
frame relay circuits. Fractional
digital service hierarchy level 1 with service much the same as FT-1
except the service is integrated with voice, data, video and frame
relay.
light-weight process (n.)
A
process which executes concurrently with other processes, in the same
address space and in an unprotected fashion. Light-weight processes
are used by systems such as MACH to reduce the
overhead of process start-up.
linear speedup (n.)
Speedup that is directly proportional to the
number of processors used. According to
Amdahl's Law, linear speedup is not
possible for a problem that contains any sequential portion, no matter
how small. Gustafson's Law
however, states that linear speedup can be achieved if the problem
size is increased as well as the number of processor employed. See
also superlinear speedup.
linear vector scan (n.)
a
table lookup algorithm for pipelined vector processors that in a
single operation compares a large number of contiguous elements of the
table against the key.
link (n.)
A one-to-one connection between
two processors or nodes in a multicomputer. See also bus.
link loading (n.)
The amount of
communication traffic carried by a link, or by the
most heavily loaded link in the system. As link loading increases,
both latency and contention are likely to increase. See also bisection bandwidth.
linked array (n.)
a data structure
designed to allow the joining of various sized lists so that the
inserting and deleting of the list elements can be done in parallel
without contention.
linked triadic
operation (n.)
act of executing a pair of vector operations,
such as V+S*V as if they were a single, longer operation by taking the
output of the first pipelined functional unit and directing it to the
second pipelined functional unit, avoiding a trip to main memory and
back.
LINPACK (n.)
A linear algebra software
package, which has been mounted on a wide range of platforms. It has
now been superceded by LAPACK. (n.)
also a set of widely quoted
performance benchmarks based on linear algebra and available from
the National Software
Exchange.
LIPS (n.)
logical inferences per second;
procedure calls per second in a logic programming system.
live variable (n.)
A variable
visible to a process and whose value can be changed by actions taken
outside that process. For example, if a variable is shared by two
processes, one of which can write to it at some point, then that
variable is live within the other process. See also
race condition,
shared variables.
livelock (n.)
A situation in which a
process is forever blocked because another
process has preferential access to a resource needed by both
processes.
LIW (n.)
Long Instruction Words: the use of
long (64 or more bits) instruction words in a processor to improve its
ability to pipeline calculations.
LMI (n.)
Local Management Interface, a
protocol, with 4 different versions, used to control the local
interface from a routing device to the IPX
Switch. Also used for configuration, flow control and maintenance of
the local connection.
load balance (n.)
The degree to
which work is evenly distributed among available processors. A
program executes most quickly when it is perfectly load balanced, that
is when every processor has a share of the total amount of work to
perform so that all processors complete their assigned tasks at the
same time. One measure of load imbalance is the ratio of the
difference between the finishing times of the first and last
processors to complete their portion of the calculation to the time
taken by the last processor.
locality (n.)
The degree to which the
computations done by a processor depend only on data values held in
memory that is close to that processor, or the degree to which
computations done on a point in some data structure depend only on
values near that point. Locality can be measured by the ratio of
local to nonlocal data accesses, or by the distribution of distances
of, or times taken by, nonlocal accesses. See also halo, stencil.
locality of reference (n.)
The observation that references to memory tend to cluster. Temporal
locality refers to the observation that a particular datum or
instruction, once referenced, is often referenced again in the near
future. Spatial locality refers to the observation that once a
particular location is referenced, a nearby location is often
referenced in the near future.
localization (n.)
The process of altering a program so that it is appropriate for the
area in which it is used. For example, the developers of a word
processing program must localize the sorting tables in the program for
different countries or languages because the correct order of
characters in one language might not be correct in another. See also
internationalization.
lock (n.)
Any device or algorithm whose use
guarantees that only one process can perform some action or use some
resource at a time.
logarithmic cost
criterion (n.)
Cost criterion that assumes the cost of
performing an instruction is proportional to the length of the
operands. The integer N requires at least log N + 1 bits of memory,
hence the name.
logic (n.)
The branch of mathematics that
investigates the relationships between premises and conclusions of
arguments.
logic program (n.)
A set of Horn clauses, or procedures.
logical inferences per
second (n.)
See LIPS.
logical time (n.)
Elapsed time as
seen from within processes. This may differ from
clock time, because processes can block or be suspended during multitasking and because they can run at
different speeds. The logical times of events only define a partial
order on those events.
loop unrolling (n.)
A compiler optimization technique in
which the body of a loop is replicated L times, and the number of
iterations of that loop reduced by a corresponding factor L. By
lengthening the basic block inside the
loop, this can increase the scope for vectorization and other optimizations.
loopback test (n.)
A circuit test
at any device which will tie the transmit data to the receive data in
order to apply a signal and receive the data back for interpretation.
loose synchronization
(adj.)
A program running on a
concurrent computer is said
to be running in loose synchronization if the nodes are constrained to intermittently
synchronize with each other via some communication.
Frequently, some global computational parameter such as a time or
iteration count provides a natural synchronization reference. This
parameter divides the running program into compute and communication cycles.
See also synchronous.
low-order interleaving
(n.)
A memory interleaving based on the low-order bits of the
address.
lower triangular matrix
(n.)
A matrix with no nonzero elements above the main diagonal.
LU decomposition (n.)
A
technique where a matrix A is represented as the product of a lower
triangular matrix, L, and an upper triangular matrix U. This
decomposition can be made unique either by stipulating that the
diagonal elements of L be unity, or that the diagonal elements of L
and U be correspondingly identical.
luminance (n.)
(1) The generic flux from a light-emitting or light-reflecting
surface. The subjective response to luminance is brightness. (2) The
specific ratio of color primaries that provides a match for the white
point in a specified color space. (3) The portion of a composite
signal that carries brightness information.
M-section (n.)
A table lookup
algorithm for pipelined vector processors that combines features of
bisection and linear vector scan.
MACH (n.)
An operating system based on
Berkeley UNIX developed by Carnegie Mellon University.
macropipelining (n.)
See pipelining.
macrotasking (n.)
Technique of
dividing a computation into two or more large tasks to be executed in
parallel. Typically the tasks are subroutine calls executed in
parallel.
mailbox (n.)
An address used as a source
or destination designator in a message.
mapping (n.)
Often used to indicate an
allocation of processes to processors; allocating work to processes is
usually called scheduling. See also load
balance.
marshall (v.)
To compact the values of
several variables, arrays, or structures into a single contiguous
block of memory; copying values out of a block of memory is called
unmarshalling. In most message passing
systems, data must be marshalled to be sent in a single message.
mask (n.)
A Boolean array or array-valued
expression used to control where a data parallel operation has effect; the
operation is only executed where array elements are true.
memory bank conflict (n.)
A
condition that occurs when a memory unit receives a request to fetch
or store a data item prior to completion of its bank cycle time since
its last such request.
memory protection (n.)
Any
system that prevents one process from accessing a region of memory
being used by another. Memory protection is supported both in
hardware and by the operating system
of most serial computers, and by the hardware kernel and service kernel of the processors in most
parallel computers.
mesh (n.)
A topology
in which nodes form a regular acyclic d-dimensional grid, and each
edge is parallel to a grid axis and joins two nodes that are adjacent
along that axis. The architecture of many
multicomputers is a two or three
dimensional mesh; meshes are also the basis of many scientific
calculations, in which each node represents a point in space, and the
edges define the neighbors of a node. See also hypercube, torus.
message passing (n.)
A style of
interprocess communication in which processes send discrete messages
to one another. Some computer architectures are called message passing
architectures because they support this model in hardware, although
message passing has often been used to construct
operating systems and network software for uniprocessors and distributed computers. See
also routing.
message passing interface
(MPI) (n.)
A standard portable message-passing library developed in 1993 by a
group of parallel computer vendors, software writers, and application
scientists. Available to both Fortran and C programs and available on
a wide variety of parallel machines. Target platforms are distributed
memory systems.
message typing (n.)
The
association of information with a message that identifies the nature
of its contents. Most message passing
systems automatically transfer information about a message's sender to
its receiver. Many also require the sender to specify a type for the
message, and let the receiver select which types of messages it is
willing to receive.
message-oriented
language (n.)
A programming language in which process
interaction is strictly through message
passing.
Metropolis routing (n.)
A
routing algorithm for meshes, in which an
ordering is imposed on axes, and messages are sent as far along the most
significant axis as they need to go, then as far along the next most
significant axis, and so on until they reach their destination. See
also e-cube routing, randomized routing.
MFLOPS (n.)
An acronym for millions of floating point operations per
second. MFLOPS are standardized units of execution speed used to rate
the floating point performance of a computer.
See also FLOPS, MIPS, and SPECmarks.
MHS (n.)
Is CCITT's X.400
series of recommendations for electronic mail transfer. MHS defines
the system of message user agents, message transfer agents, message
stores and access units.
MIB (n.)
Management Information Base is a
variable database for gateways running CMOT
or SNMP. MIB-II refers to a database not
shared by CMOT and SNMP.
microtasking (n.)
Technique of
employing parallelism at the DO-loop level. Different iterations of
a loop are executed in parallel on different processors.
middle product method
(n.)
A method of matrix multiplication in which entire columns of the
result are computed concurrently. See also
inner product method.
MIMD (n.)
Multiple Instruction, Multiple
Data; a category of Flynn's taxonomy
in which many instruction streams are concurrently applied to multiple
data sets. A MIMD architecture is one in
which heterogeneous processes may execute
at different rates.
minimax (n.)
Algorithm used to determine
the value of a game tree.
minimum spanning tree (n.)
A spanning tree with the smallest possible weight among all spanning
trees for a given graph.
MIPS (n.)
One Million Instructions Per
Second. A performance rating usually referring to integer or
non-floating point instructions. See also MOPS.
MIR (n.)
Minimum Information Rate or
Committed Information Rate (CIR), is the minimum transmit and receive
data rate for a connection.
MISD (n.)
Multiple Instruction, Single
Data. A member of Flynn's taxonomy almost never used. This category
has an ambiguous meaning. It refers to a computer which applies
several instructions to each datum. The closest real implementation
to this category is a vector computer with an instruction pipeline.
module (n.)
A memory bank, often used in
the context of interleaved memory.
monitor (n.)
A structure consisting of
variables representing the state of some resource, procedures to
implement operations on that resource, and initialization code.
Monte Carlo (adj.)
Making use of
randomness. A simulation in which many independent trials are run
independently to gather statistics is a Monte Carlo simulation. A
search algorithm that uses randomness to try to speed up convergence
is a Monte Carlo algorithm.
MOPS (n.)
One Million Operations Per Second.
Usually used for a general operation, either integer, floating point
or otherwise. See also MIPS, FLOPS.
MOS (n.)
Metal oxide on Silicon: a basic
technology for fabricating semiconductors. See also CMOS, BiCMOS.
motherboard (n.)
A printed circuit
board or card on which other boards or cards can be mounted.
Motherboards will generally have a number of slots for other boards,
by which means the computer system may be expanded. When all the
slots are used up however, it is usually difficult to expand further,
and this is the manufacturer's way of telling you to buy a bigger
system.
multicast (n.)
To send a message to
many, but not necessarily all possible recipient processes. See also
broadcast,
process group.
multicomputer (n.)
A computer in
which processors can execute separate instruction streams, have their
own private memories and cannot directly access one another's
memories. Most multicomputers are disjoint
memory machines, constructed by joining nodes
(each containing a microprocessor and some memory) via links. See also architecture,
distributed computer, multiprocessor,
processor array.
multigrid method (n.)
A method
for solving partial differential equations in which an approximate
solution on a coarse resolution grid is used to obtain an improved
solution on a finer resolution grid. The method reduces long
wavelength components of the error or residual by iterating between a
hierarchy of coarse and fine resolution grids.
multiprocessor (n.)
A computer in
which processors can execute separate instruction streams, but have
access to a single address space.
Most multiprocessors are shared memory
machines, constructed by connecting several processors to one or more
memory banks through a bus or switch. See also architecture,
distributed computer, multicomputer,
processor array.
multiprocessing (n.)
The ability
of a multiprocessor to intermix
jobs on one or more CPUs.
multiprogramming (n.)
The
ability of a computer system to time share its (at least one) CPU with
more than one program at once. See also multitasking.
multitasking (n.)
Executing many
processes on a single processor. This is usually done by time-slicing
the execution of individual processes and performing a context switch
each time a process is swapped in or out, but is
supported by special-purpose hardware in some computers. Most operating systems support multitasking,
but it can be costly if the need to switch large caches or execution pipelines makes
context switching expensive in
time.
multithreading (n.)
(1) A technique that enables multiprocessing applications to run more
efficiently by breaking sequences of instructions (threads) into
multiple sequences that can be executed from the kernel
simultaneously. See also
asymmetric
multiprocessing and
symmetric
multiprocessing. (2) In data manipulation, a technique in
which nodes in a tree data structure contain pointers to higher nodes
to make traversal of the structure more efficient.
mutual exclusion (n.)
A
situation in which at most one process can be engaged in a specified
activity at any time. Semaphores are often
used to implement this. See also contention, deadlock,
critical sections.
n-1/2 (n.)
(pronounced as n-one-half,
usually written with a subscript.) The minimum vector length on which
a pipelined architecture delivers one half of its
theoretical peak performance. The larger n-1/2 is, the longer
calculations must be to amortize the startup
cost of the pipeline. This measure was coined by Hockney and
Jesshope in 1988. See also r-inf.
NAND (n.)
A logical operator having the property that if P is a statement, Q is
a statement, R is a statement,..., then the NAND of P, Q, R,... is
true if at least one statement is false, false if all statements are
true.
NC (n.)
The class of parallel algorithms that
can run in polylogarithmic (polynomial in the logarithm of the problem
size) time on a polynomial number of processors in the PRAM model.
necklace (n.)
The nodes a data item
travels through in response to a sequence of shuffles.
need-predictable (adj.)
Used to
describe a concurrent algorithm in which the need for but not the
nature of point-to-point communication between nodes is known prior to program execution.
Need predictable problems are loosely
synchronous.
NeTBIOS (n.)
Network Basic Input/Output
System that provides a Session layer interface between network
applications running on a PC and the underlying protocol software of
the Transport and Network layers on the OSI
model. Normally a LAN protocol.
network (n.)
A physical communication
medium. A network may consist of one or more buses, a switch,
or the links joining processors in a multicomputer.
network address (n.)
The address, consisting of up to 20 octets, used to locate an OSI transport
entity. The address is formatted into an initial domain part that is
standardized for each of several addressing domains, and a domain
specific part that is the responsibility of the addressing authority
for that domain.
neural network (n.)
Man made
devices using interconnects and processing capabilities suggested by
models of the cortex are termed neural networks. These systems are
widely used for optimization problems including content addressable
memories and pattern recognition.
NFS (n.)
Network File System ia a protocol
developed to use IP and allow a set of computers to access each
other's file systems as if they were on the local host.
NNTP (n.)
Network news transport protocol
is used with uucp to transfer news across
the Usenet.
node (n.)
Generic term used to refer to an
entity that accesses a network. Or an addressable point on a network.
non-blocking (adj.)
An operation
that does not block the execution of the
process using it. Usually applied to communications operations, where it
implies that the communicating process may perform other operations
before the communication has completed. See also blocking.
non-deterministic model
(n.)
a task model in which the execution time of each task is
represented by a random variable.
non-uniform memory
access (adj.)
See NUMA.
NOW (network of workstations) (n.)
A cluster of workstations interconnected through a high speed network
that can be used for high performance computing. It provides
excellent price/performance. See also clustering and COW.
NP complete (adj.) A term used to describe a problem if it can only be solved in polynomial time by non-deterministic methods. In practice such problems are "hard" and are can only be tackled by a number of heuristic methods that only give approximate answers near to the optimum solution.
NUMA (adj.)
Nonuniform memory access; not
supporting constant-time read and write operations. In most NUMA architectures, memory is organized
hierarchically, so that some portions can be read and written more
quickly by some processors than by others. See also UMA
oblivious (adj.)
Working in the same
fashion regardless of surroundings or history. An oblivious
scheduling strategy always schedules processes in the same way, no
matter how much work they have done in the past; an oblivious routing algorithm always routes messages in the
same direction, regardless of local load. See also adaptive.
octet (n.)
A byte composed of eight binary elements.
OEM (n.)
Original Equipment Manufacturer; a
company which adds components to someone else's computers and sells the
result as a complete product.
OLTP (n.)
On-line transaction processing;
handling transactions (such as deposits and withdrawals) as they
occur. An application area of great importance to banks and insurance
companies.
Omega network (n.)
a composition
of shuffle-exchange networks with programmable switches.
ones complement (n.)
A number in the binary (base-two) system that is the complement of
another number. Because binary is based on only two digits, the one's
complement is easy to derive. Each digit in a number can simply be
reversed. For example, reversing the digits in 0101 produces the one's
complement, 1010. Contrast with twos
complement.
OOF (n.)
out of frame condition counter that
increments every change in the framing status of a circuit or device.
operating system (n.)
That
software responsible for providing standard services and supporting
standard operations such as multitasking
and file access. See also kernel.
operation oriented
language (n.)
a programming language using remote procedure
calls as the principle means for interprocess communication and
synchronization.
optimal (adj.)
Cannot be bettered. An
optimal mapping is one that yields the best
possible load balance; an optimal
parallel algorithm is one that has the lowest possible time-processor
product.
optimization block (n.)
a
block of code (rarely a whole subprogram, but often a single DO-loop)
in which a compiler optimizes the generated code. A few compilers
attempt to optimize across such blocks; many just work on each block
separately.
optimization problem (n.)
a
problem whose solution involves satisfying a set of constraints and
minimizing (or maximizing) and objective function.
OR-parallelism (n.)
A form of
parallelism exploited by some implementations of parallel logic
programming languages, in which the terms in disjunctions are
evaluated simultaneously, and the parent computation allowed to
proceed as soon as any of its children have completed. See also AND-parallelism.
OS (n.)
See
operating system.
OSF (n.)
Open Software Foundation; an
organization established by a number of the major computer
manufacturers to set software standards.
OSPF (n.)
open shortest path first is a
proposed IGP for the internet.
output dependence (n.)
See dependence.
packet switching (n.)
A routing
technique in which intermediate nodes wait until
they have received the whole of a message before forwarding any of it.
Packet switching often requires a large amount of buffer space, and contention for access to this space can lead to
deadlock. See also
virtual cut-through,
wormhole routing.
PAD (n.)
packet assembler/disassembler, a
device that converts a serial data stream into discrete packets in the
transmit direction and converts the received packets back into a
serial data stream. Adds header information in the transmit packet to
allow it to be routed to the proper destination.
page (n.)
The smallest unit of a virtual
memory system. The system maintains separate virtual-to-physical
translation information for each page.
parallel balance point
(n.)
The point at which using more processors to do a calculation
increases the time taken to complete that calculation. See also Amdahl's Law, efficiency,
Gustafson's Law, isoefficiency,
speedup.
parallel computation
thesis (n.)
time on an unbounded parallel model of computation
is (polynomially) equivalent to space on a sequential model of
computation. (Unproved)
parallel computer (n.)
A
computer system made up of many identifiable processing units working
together in parallel. The term is often used synonymously with concurrent computer to include both multiprocessor and multicomputer. The term concurrent generally
dominates in usage in the USA, whereas the term parallel is the more
widely used in Europe.
parallel prefix (n.)
An
operation applying an associative binary operator o to an n-vector V
to produce: <(V0)(V0oV1)(V0oV1oV2)...(V0oV1o...oVn)>. Variations of
this operation, which is also sometimes called a scan, may leave the operations identity element in
the first element of the vector, apply the operation downward from the
last element of the vector, and so on. See also reduction,
scan-vector model,
segmented parallel
prefix operation.
parallel random access
machine (n.)
See PRAM
parallel slackness (n.)
Hiding the latency of communication by giving
each processor many different task, and having them work on the tasks
that are ready while other tasks are blocked
(waiting on communication or other operations).
parallel unification (n.)
finding the set of possible unifications for a goal in parallel.
parallelization (n.)
Turning a
serial computation into a parallel one. Also sometimes turning a
vector computation into a parallel one. This may be done
automatically by a parallelizing compiler or (more usually) by
rewriting (parts of) the program so that it uses some parallel
paradigm. See also dataflow,
data parallelism,
futures, generative communication, message passing,
shared variables.
parsing (n.)
process whereby a compiler
analyzes the syntax of a program to establish the relationship among
operators, operands, and other tokens of a program. Parsing does not
involve any semantic analysis.
partial cascade sum
(n.)
parallel algorithms to compute partial sums in logarithmic time.
partial sum (n.)
the result from a
summation of some subsequence of the elements in a sequence of
operands.
partitioning (n.)
process of
restructuring a program or algorithm into independent computational
segments. The goal is to have multiple processors simultaneously work
on these independent computational segments.
PDE (n.)
partial differential equation.
percentage
parallelization (n.)
the percentage of processor expenditure
processed in parallel on a single job. It is not usually possible to
achieve 100 percent of an application's processing time to be shared
equally on all processors. See Amdahl's
Law.
percentage
vectorization (n.)
The percentage of an application executing
in vector mode. This percentage may be calculated as a percentage of
CPU time or as the percentage of lines of code (usually Fortran) in
vector instructions. The two approaches are not consistent and may
give very different ratings. The first calculation method leads to
performance improvement as measured by CPU time, while the second
method measures the success rate of the compiler in converting scalar
code to vector code. The former is the more meaningful hardware
performance measure. See also vectorize.
performance model (n.)
A
formula that predicts the speed, efficiency,
memory requirements, or other execution characteristics of a program
on a particular architecture
ping (n.)
The packet Internet groper is a
program useful in testing and debugging LAN/WAN troubles. It sends
out an Internet control message protocol
(ICMP) echo and expects a specified host to respond back in a
specified time frame.
pipe (n.)
A communication primitive which
involves the transmission of information through a linearly connected
subset of the nodes of a
parallel computer.
pipelining (n.)
Overlapping the
execution of two or more operations. Pipelining is used within
processors by prefetching instructions
on the assumption that no branches are going to preempt their
execution; in vector
processors, in which application of a single operation to the
elements of a vector or vectors may be pipelined to decrease the time
needed to complete the aggregate operation; and in multiprocessors and multicomputers, in which a process
may send a request for values before it reaches the computation that
requires them. See also architecture.
PIR (n.)
peak information rate, is the peak
rate of information transfer available on a connection. See also MIR and CIR and QIR.
pivot (n.)
A particular element of a
matrix during some algorithm. Many matrix algorithms need carefully
chosen pivots to improve their numerical accuracy and stability.
Pivoting involves arranging that the pivotal element has an
appropriate numerical value by reordering and/or swapping rows and
columns in the matrix.
PLN (n.)
Packet Line, an inter-switch trunk,
usually an E1 or T1,
designed to carry packets between IPX
nodes.
point of presence (pop)
(n.)
The physical access location interface between a local exchange
carrier and the main network. The point to which the telephone
company terminates a subscriber's circuit for long distance service or
leased line communications.
polling (adj.)
of a communication
system. Polling involves a node inspecting the
communication hardware - typically a flag bit - to see if information
has arrived or departed. Polling is an alternative to an interrupt driven system. The
natural synchronization of the nodes
imposed by polling is used in the implementation of blocking communications primitives.
ports (n.)
a variant of mailboxes allowing
multiple client processes but only a single server process.
POSIX (n.)
A standard of definition of the
interface to the UNIX operating system.
PPP (n.)
point to point protocol is an
alternative to SLIP and provides router to router and host to network
connections over both synchronous and asynchronous circuits.
PRAM (n.)
Parallel random access machine; a
theoretical model of parallel computation in which an arbitrary but
finite number of processors can access any value in an arbitrarily
large shared memory in a single
time step. Processors may execute different instruction streams, but
work synchronously. The three most
important variations of the PRAM are: EREW - Exclusive
read, exclusive write; any memory location may only be accessed once
in any one step. CREW - Concurrent read, exclusive write;
any memory location may be read any number of times during a single
step, but only written to once, with the write taking place after the
reads. CRCW - Concurrent read, concurrent write; any memory
location may be written to or read from any number of times during a
single step. A CRCW PRAM model must define some rule for resolving
multiple writes, such as giving priority to the lowest-numbered
processor or choosing amongst processors randomly. The PRAM is
popular because it is theoretically tractable and because it gives
algorithm designers a common target. However, PRAMs cannot be
emulated optimally on all architectures. See also NC.
preconditioning (n.)
a technique
for improving the convergence of iterative matrix inversion algorithms
such as the conjugate gradient
method, by transforming the matrix of equation coefficients so
that the eigenvalues are redistributed.
prefetch (v.)
to fetch or load a data
entity or program instruction from memory in advance of actually
starting to process it. Processors that have prefetch instructions
can avoid some of the bottlenecks that arise from a memory system that
is slower than processing speed.
print server (n.)
A host computer to which one or more printers are connected, or the
UNIX process that manages those printers. See also server.
private line (n.)
A full duplex
dedicated channel between two specified points.
private memory (n.)
Memory that
appears to the user to be divided between many
address spaces, each of which can
be accessed by only one process. Most
operating systems rely on some
memory protection mechanism
to prevent one process from accessing the private memory of another;
in disjoint memory machines, the
problem is usually finding a way to emulate
shared memory using a set of
private memories. See also
virtual shared memory.
procedure oriented
language (n.)
a programming language in which process
communication and synchronization are accomplished through the use of
of shared variables.
process (n.)
the fundamental entity of
the software implementation on a computer system. A process is a
sequentially executing piece of code that runs on one processing unit
of the system.
process creation (n.)
The act
of forking or spawning a new
process. If a system permits only static process creation, then all
processes are created at the same logical
time, and no process may interact with any other until all have
been created. If a system permits dynamic process creation, then one
process can create another at any time. Most first and second
generation multicomputers only supported
static process creation, while most multiprocessors, and most operating systems on uniprocessors, support dynamic process
creation. See also configuration, generative communication.
process flow graph (n.)
an
acyclic directed graph in which vertices
represent processes and edges represent execution constraints.
process group (n.)
A set of
processes that can be treated as a single entity for some purposes,
such as synchronization and broadcast or multicast
operations. In some parallel programming systems there is only one
process group, which implicitly contains all processes; in others,
programmers can assign processes to groups statically when configuring
their program, or dynamically by having processes create, join and
leave groups during execution.
process migration (n.)
Changing the processor responsible for executing a process during the
lifetime of that process. Process migration is sometimes used to
dynamically load balance a program or
system.
processor (n.)
A hardware device that
executes the commands in a stored program in a computer system. In
addition to the central processing unit (CPU),
many sophisticated graphics systems contain a dedicated processor for
use in the graphics accelerator.
processor array (n.)
A computer
that consists of a regular mesh of simple
processing elements, under the direction of a single control
processor. Processor arrays are usually SIMD
machines, and are primarily used to support
data parallel computations. See also
array processor, vector processor.
processor overloading (n.)
Mapping many processes to a single processor,
so that parallel slackness can be
exploited.
Prolog (n.)
a language for logic
programming.
PROM (n.)
An acronym for programmable read-only memory. A type of read-only
memory (ROM) that allows data to be written into the device with
hardware called a PROM programmer. After the PROM has been programmed,
it is dedicated to that data and cannot be reprogrammed. See also
EPROM, and ROM.
pseudovector (n.)
a scalar
temporary variable.
PVC (n.)
permanent virtual circuit, is a
permanent logical connection between two end points which is carrying
user frame relay encapsulated data.
QCD (n.)
Quantum Chromodynamics; a model of
the behavior of matter on sub-nuclear scales, the simulation of which
is very hungry of computing power.
QIR (n.)
quiescent information rate, is the
transmit and receive connection information rate which is the initial
transmit rate after a period of channel inactivity. Used with
Foresight connections only. A value between the MIR and the PIR,
normally equals the QIR.
query (n.)
(1) The process by which a master station asks a slave station to
identify itself and give its status. (2) The process of extracting
data from a database and presenting it for use. (3) A specific set of
instructions for extracting particular data repetitively. For example,
a query might be created to present sales figures for a particular
region of the country. This query could be run periodically
to obtain current reports.
r-inf (n.)
(pronounced r-inf, often
written with a subscript) The performance a pipelined architecture would deliver on an
infinitely long vector; that is, the performance of such an
architecture when startup costs are
not considered. This parameter was coined by Hockney and Jesshope in
1988. See also n-1/2.
race condition (n.)
A situation in
which the final result of operations being executed by two or more
processes depends on the order in which those processes execute. For
example, if two processes A and B are to write different values VA and
VB to the same variable, then the final value of the variable is
determined by the order in which A and B are scheduled.
radix (n.)
In a radix numeration
system, the positive integer by which the weight of the digit place is
multiplied to obtain the weight of the digit place with the next
higher weight. For example, in the decimal numeration system, the
radix of each digit place is 10. In a biquinary code, the radix of
each fives position is 2.
RAID (n.)
Redundant array of inexpensive
disks; a file system containing many disks,
some of which are used to hold redundant copies of data or error
correction codes to increase reliability. RAIDS are often used as
parallel access file systems, where the sheer size of storage capacity
required precludes using more conventional (but more expensive) disk
technology.
RAM (n.)
Random Access Memory; computer
memory which can be written to and read from in any order by the CPU
or other hardware devices. See also
DRAM, SRAM,
and ROM.
random uniform game
tree (n.)
a game tree whose terminal node values are randomly
chosen from some uniform distribution.
randomized routing (n.)
A routing technique in which each message is sent to
a randomly chosen node, which then then forwards
it to its final destination. Theory and practice show that this can
greatly reduce the amount of contention for
access to links in a multicomputer.
rank (n.)
row of a
butterfly network.
RDMS (n.)
Relational Database Management
System; software to manage a database in which data are stored by
attribute.
ready list (n.)
OS
list containing ready-to-run processes.
reasonable (adj.)
a parallel model is
said to be reasonable if the number of processors each processor can
communicate with directly is bounded by a constant.
recurrence (n.)
a relationship in a
DO-loop whereby a computation in one iteration of the loop depends
upon completion of a previous iteration of the loop. Such dependencies
inhibit vectorization.
reduced instruction set
computer (adj.)
See RISC
reduction operation (n.)
An
operation applying an associative and commutative binary operator to a
list of values, See also parallel
prefix.
redundant array of
inexpensive disks (n.)
See RAID
redundant computation (n.)
Calculations that are carried out more than once or by more than one
processor. Computations may be done redundantly because it is cheaper
to have every processor calculate a value for itself than to have one
processor calculate the value and then broadcast it, or because processes may
not have enough memory to store all the values they calculate and may
need to overwrite some during execution.
refute (v.)
to make a move that causes an
alpha-beta cutoff.
relaxation method (n.)
A type
of indirect method in which the
values making up a trial solution to an equation are repeatedly updated
according to some rule until convergence criteria are met. See also
direct method
remote procedure call (n.)
a structured implementation of a client-server interaction.
rendezvous (n.)
when the server side
of a remote procedure call is
specified by using an accept statement or similar construct.
repeater (n.)
A device that propagates electrical signals from one cable to
another without making routing decisions or providing packet
filtering. In International Organization for Standardization's open
systems interconnection (OSI) terminology, a repeater is a physical
layer intermediate system. See bridge and
router.
reply message (n.)
passing of
results back to the client in a
remote procedure call.
RGB (adj.)
Red-Green-Blue; the most common form of
color display hardware.
ring (n.)
A topology in which each node
is connected to two others to form a closed loop. See also chain, Hamiltonian.
RIP (n.)
routing information packet is an IGP supplied with BSD
networking Unix.
RISC (adj.)
Reduced instruction set
computer; a computer that provides only a few simple instructions but
executes them extremely quickly. RISC machines typically rely on instruction prefetching and caching to achieve higher performance than CISC machines. The term is also applied to
software designs that give users a small number of simple but
efficient operations.
ROM (n.)
Read Only Memory; a computer memory
which cannot be written to during normal operation.
router (n.)
A system responsible for making decisions about which of several
paths network (or Internet) traffic will follow. To do this it uses a
routing protocol to gain information about the network, and algorithms
to choose the best route based on several criteria known as "routing
metrics." In International Organization for Standardization's open
systems interconnection (OSI) terminology, a router is a network layer
intermediate system. See
gateway, bridge, and repeater.
routing (n.)
The act of moving a message
from its source to its destination. A routing technique is a way of
handling the message as it passes through individual nodes. See also
e-cube routing,
interval routing,
Metropolis routing, packet switching, randomized routing,
virtual cut-through, wormhole routing.
routing algorithm (n.)
a rule
for deciding, at any intermediate node, where to
send a message next. See also routing.
routing kernel (n.)
See kernel.
RPC (n.)
remote procedure call is a popular
model for implementing distributed client-server computing
environments. It is an alternative to inter-process communication (IPC) which allows remote systems to execute a
set of procedures to share information.
rule (n.)
in the context of logic
programming, a rule is a Horn clause
with a head and a body.
satisfiable (adj.)
True under the
rules of logic.
SAXPY (n.)
elemental
BLAS operation involving "constant (a)
times vector (x) plus vector (y)". The S refers to Fortran Single
precision. SAXPY and related BLAS operations are often implemented by
the hardware manufacturer as part of the system software and the
execution time for such operations has been used a a primitive
benchmark of a high performance computing system.
scalable (adj.)
Capable of being
increased in size, or more accurately, capable of delivering an
increase in performance proportional to an increase in size. A
scalable architecture is one that can be
used as a design for arbitrarily large machines, or one whose increase
in performance is linear in the amount of hardware invested. The term
is also applied to programming systems, although its meaning is less
clear in these cases. It is generally used to imply that the methods
and algorithms employed in such systems are in principle capable of
performing correctly equally well on large and small hardware systems.
See also Gustafson's Law.
ScaLAPACK (n.)
A linear algebra
software package, which has been mounted on a wide range of platforms.
This is a version of LAPACK suitable for distributed memory computer systems.
The software
is available from the
National Software Exchange. See also LAPACK.
scalar processor (n.)
A
computer in the traditional Von Neumann sense of operating only on
scalar data. See also uniprocessor, vector processor,
array processor.
scalar temporary (n.)
a
compiler created scalar variable that holds the value of a
vectorizable expression on each iteration of a DO-loop.
scan (n.)
See
parallel prefix.
scan-vector model (n.)
A
theoretical model of parallel computing in which a
scalar processor and a
vector processor have access,
respectively to a memory holding scalar values and a memory holding
vectors of arbitrary length. Vector operations take either a single
time step or a time proportional to the logarithm of the number of
elements. See parallel prefix,
data parallelism, reduction operation.
scattered decomposition
(n.)
See decomposition.
scheduling (n.)
Deciding the order in
which the calculations in a program are to be executed, and by which
processes. Allocating processes to processors is usually called mapping.
See also load balance.
scoreboard (n.)
A hardware device
that maintains the state of machine resources to enable instructions
to execute without conflict at the earliest opportunity.
SCSI (n.)
Small Computer Systems Interface;
a hardware standard for interfacing to devices such as disks.
secondary memory (n.)
a larger
but slower memory than primary memory. Access to secondary memory
often requires special instructions, such as I/O
instructions.
segmented parallel
prefix operation (n.)
A parallel
prefix operation in which the vector being operated on is divided
into segments, and the operator is applied to each segment as if it
were a separate vector. This is usually implemented by supplying a
separate vector of segment lengths.
self-scheduling (adj.)
Automatically allocating work to processes. If T tasks are to be done
by P processors, and P less than T, then they may be self-scheduled by
keeping them in a central pool from which each processor claims a new
job when it finishes executing its old one. See also
task farming.
semaphore (n.)
A data type for
controlling concurrency. A semaphore can be initialized to any non
negative integer value. After that, only two operations may be
applied to it: "signal" which increments the semaphore's value by one,
and "wait" which blocks its caller until the
semaphore's value is greater than zero, then decrements the semaphore.
The value of a semaphore typically represents the amount of some
resource that is currently available, while waiting on a semaphore
forces processes to block until some of that resource can be claimed.
A binary semaphore is one that can only take on the values 0 and 1.
sequential bottleneck (n.)
A part of a computation for which there is little or no parallelism.
See also Amdahl's Law.
sequential computer (n.)
synonymous with a Von Neumann
architecture computer and is a "conventional" computer in which
only one processing element works on a problem at a given time. See
also uniprocessor.
serialize (v.)
To put potentially
concurrent operations in a strictly sequential order. If concurrent
processes must claim a lock before doing some
operation, for example, then their operations will be serialized.
server (n.)
A system that supplies services to a client. See also
action server,
application server,
caching-only server,
communication server,
file server,
print server,
session server,
X server.
service kernel (n.)
See kernel.
session server (n.)
A system that provides networked sessions. Session files reside on the
session server and are used whenever a user logs in to a system on the
network. See also action server,
application server,
caching-only server,
communications server,
file server.
set associative (n.)
A cache
structure in which all tags in a particular set are compared with an
access key in order to access an item in cache. The set may have as
few as one element or as many elements as there are lines in the full
cache.
shared memory (n.)
Memory that
appears to the user to be contained in a single
address space and that can be
accessed by any process. In a uniprocessor or multiprocessor there is typically a
single memory unit, or several memory units interleaved to give the
appearance of a single memory unit. See also
disjoint memory,
distributed memory.
shared variables (n.)
Variables
to which two or more processes have access, or the model of parallel
computing in which interprocess communication and synchronization are managed through such
variables. See also data parallelism,
futures, generative communication, live variable, message
passing.
short necklace (n.)
a necklace of length less than k in a shuffle
exchange network containing 2^k nodes.
shortstopping (v.)
using the
output of a functional unit before it is routed back to memory.
shuffle exchange
network (n.)
A topology containing N =
2^L nodes, each of which is labeled by a unique
L-bit integer. If two nodes have labels <|IL...I0|> and <|JL...J0|>,
then I and J are connected if Ik=Jk for 1<=k<(L-1) and I0<>J0, or if J
is a left or right cyclic shift of I. See also butterfly, hypercube.
SIMD (adj.)
Single instruction, multiple
data; a category of Flynn's taxonomy
in which a single instruction stream is concurrently applied to
multiple data sets. A SIMD architecture
is one in which homogeneous
processes
synchronously execute the same
instructions on their own data, or one in which an operation can be
executed on vectors of fixed or varying size. See also
array processor,
processor array,
vector processor.
SIMD-CC (n.)
cube-connected (
hypercube) SIMD architecture.
SIMD-CCC (n.)
cube connected cycles
SIMD architecture. See also SIMD-CC.
SIMD-MC (n.)
mesh connected SIMD architecture.
Superscript refers to the number of dimensions in the architecture.
SIMD-P (n.)
SIMD architecture with pyramid processor
organization.
SIMD-PS (n.)
SIMD architecture with perfect shuffle
connections.
SIMD-SM (n.)
shared memory SIMD architecture. Two processors may not
read from or write into the same shared memory location during the
same instruction.
SIMD-SM-R (n.)
shared memory SIMD architecture. Two processors may read
from the same memory location during an instruction, but concurrent
writing into the same location is forbidden.
SIMD-SM-RW (n.)
shared memory SIMD architecture.
Concurrent reading from and writing to the same memory location is
allowed.
SNMP (n.)
simple network management
protocol, a network management tool used in
TCP/IP based networks that is used to manage
the network equipment and processes. Usually graphic on an X-window
display.
simple network
management protocol (n.)
See SNMP.
simulated annealing (n.)
An
optimization technique introduced by Kirkpatrick in 1983 which uses
statistical physics methods to find an approximate optimal solution to
a problem. Typically a thermodynamic analogy is used for the model
system under study and the task of finding an optimal solution is
mapped to that of finding the ground state of the thermodynamic
system.
single instruction,
multiple data (adj.)
See SIMD.
single instruction,
single data (adj.)
See SISD.
single program, multiple
data (adj.)
See SPMD.
single-source
shortest-path problem (n.)
problem of finding the shortest
path from a single designated vertex (the source) to all the other
vertices in a weighted, directed graph.
SISD (adj.)
Single instruction, single
data; a category of Flynn's taxonomy
in which a single instruction stream is serially applied to a single
data set. Most uniprocessors are SISD
machines.
SLIP (n.)
serial line Internet protocol is
used to run IP over serial lines,
telephone circuits or RS-232 cables
connecting two hosts.
SMTP (n.)
simple mail transfer protocol is
the internet's electronic mail
protocol.
socket (n.)
A software endpoint for network communication. Two programs on
different machines each open a socket in order to communicate over the
network. This is the low-level mechanism that supports most networking
programs.
software lockout (n.)
See lock.
SOR (n.)
Successive over-relaxation is a
technique for accelerating the convergence of relaxation methods for solving
sets of simultaneous linear equation, Ax=b. It typically involves
adding an appropriate multiple of the unit matrix to the matrix of
coefficients A.
space complexity (n.)
space
used up by an algorithm as a function of problem size.
space sharing (n.)
Dividing the
resources of a parallel computer among many programs so they can run
simultaneously without affecting one another's performance. See also
time sharing.
spanning tree (n.)
A
tree containing a subset of the
links in a graph which reaches every node
in that graph. A spanning tree can always be constructed so that its
depth (the greatest distance between its root and any leaf) is no
greater than the diameter of the graph.
Spanning trees are frequently used to implement broadcast operations.
SPARC (n.)
Scalable Processor ARChitecture;
a family of chips which can be manufactured using a variety of
technologies, but still be compatible in some ways.
sparse matrix (n.)
A matrix with
the majority of its elements equal to zero. See also
full matrix.
spawn (v.)
To create a new process with
arbitrary initial memory contents and instructions. See also fork.
SPEC (n.)
The Systems Performance Evaluation
Cooperative, made up of a number of participating computer system
manufacturers to develop a series of accepted test programs to measure
system computing performance.
SPECmarks (n.)
A benchmark measure of relative computer system
performance, developed by the Systems Performance Evaluation
Cooperative. See SPEC. See also MFLOPS and MIPS.
speedup (n.)
The ratio of two program
execution times, particularly when times are from execution on 1 and P
nodes of the same computer. Speedup is usually
discussed as a function of the number of processors, but is also a
function (implicitly) of the problem size. See also Amdahl's Law,
Gustafson's Law,
isoefficiency,
optimal.
spin lock (n.)
an implementation of
the lock primitive that causes a processor to retest a semaphore until
it changes value. Busy-waits will spin until the lock is free.
spinning (adj.)
a process waiting for
the value of a spin lock to change is
said to be spinning.
SPMD (adj.)
Single program, multiple data;
a category sometimes added to Flynn's
taxonomy to describe programs made up of many instances of a
single type of process, each executing the same code independently.
SPMD can be viewed either as an extension of SIMD, or as a restriction of MIMD. See also
process group,
SISD.
SPX (n.)
Novell's proprietary version of
TCP.
SQL (n.)
Standard Query Language; a standard
for adding data to, or recovering data from, databases.
SRAM (n.)
Static RAM;
memory which stores data in such a way that it requires no memory
refresh cycle and hence have low power consumption. Generally this
type of RAM is faster but more expensive than DRAM.
startup cost (n.)
The time taken to
initiate any transaction with some entity. The startup cost of a message passing system, for
example, is the time needed to send a message of zero length to
nowhere. See also latency.
static channel naming (n.)
a message passing scheme in
which source and destination designators are fixed at compile time.
static decomposition (n.)
task allocation policy that assumes tasks and their precedence
relations are known before execution.
stencil (n.)
A pattern of data accesses
used when updating the values in a mesh. A
stencil is usually represented as a grid around a central point, which
indicates the location of the value being updated.
stream parallelism (n.)
a
pipelined variant of AND parallelism.
STREAMS (n.)
A kernel mechanism that supports development of network services and
data communications drivers. STREAMS defines interface standards for
character input/output within the kernel, and between the kernel and
user level. The STREAMS mechanism comprises integral functions,
utility routines, kernel facilities, and a set of structures.
STREAMS-based pipe (n.) A mechanism for bidirectional data transfer implemented using STREAMS, and sharing properties of STREAMS-based devices.
stream unit (n.)
transmits vectors
into the vector arithmetic section on some vector CPUs.
strength reduction (n.)
a
process whereby a compiler attempts to replace instructions with less
time-costly instructions that produce identical results. For example
in Fortran, X**2 might be automatically replaced by X*X.
stride (n.)
a term derived from the
concept of walking or striding through data from one location to the
next. The term is often used in relation to vector storage. A
mathematical vector is represented in a
computer as an array of numbers. Most computers use contiguous
storage of vectors, locating them by the address of the first word and
by the vector length. Many applications in linear algebra however,
require load and store of vectors with components that do not reside
contiguously in memory, such as the rows of a matrix stored in column
order. The row vectors are spaced in memory by a distance or stride
of the leading dimension of the array representing the matrix. Some
vector computers allow vector fetching and
storing to occur with randomly stored vectors. An index vector
locates successive components. This is often useful in storing the
nonzero elements of a sparse vector.
striped (adj.)
A
file system that distributes files
across disks by distributing individual blocks, often at the
single-bit level. See also declustered.
stripmining (n.)
a process used by a
compiler on a register-to-register vector processor whereby a DO-loop
of long or variable iteration count is executed in strips which are
the length of a vector register, except for a remainder strip whose
length is less.
strong search (n.)
an algorithm
that searches for a given key, locks the node associated with that
key, and returns the node.
strongly ordered game
tree (n.)
game tree with the following properties: (1) 70
percent of the time the first move chosen from any nonterminal node is
the best move, and (2) 90 percent of the time the best move from any
nonterminal node is one of the first 25 percent of the moves searched.
subcube (n.)
term for a subset of
nodes of a
hypercube
hypercube. The hypercube
architecture has a natural recursive definition so that a cube of
dimension d1 includes within it 2^(d1-d2) lower dimensional sets of
nodes, each of which is itself a hypercube of dimensionality d2.
These subsets of nodes are known as subcubes.
subgraph (n.)
given a graph, a subgraph
is another graph whose vertices and edges are in the original graph.
subnet address (n.)
An extension
of the IP address that allows a
network to be autonomous by itself and still be a subsection of a
larger user network.
subnet mask (n.)
See address mask.
subnetwork (n.)
A collection of International Organization for Standardization's
open systems interconnection (OSI) end systems and intermediate
systems under the control of a single administrative domain and using
a single network access protocol. Examples: private X.25 networks,
collection of bridged LANs.
successive over
relaxation (n.)
See SOR.
supercomputer (n.)
A time
dependent term which refers to the class of most powerful computer
systems worldwide at the time of reference. See also
concurrent computer,
parallel computer.
superlinear speedup (n.)
Speedup that is greater than an amount
proportional to the number of processors used. While super-linear
speedup is theoretically impossible, in practice it may occur because
distributing a problem among many processors may increase the
effective total size of the cache being
used, or because distribution may change the order in which
nondeterministic operations are carried out, which can lead to earlier
termination of the program.
superword (n.)
a term used on some
computers to describe a group of eight 64-bit words, or alternatively,
sixteen 32-bit half-words. The memory units on such machines,
generally fetch and store data in superwords (also called swords),
regardless of the size of the data item referenced by the user
program.
SV+TM (n.)
Strataview Plus, a UNIX based
graphic user interface used to manage frame
relay networks.
swap (v.)
To exchange two items. The term
refers to swapping a section of real memory (contents) for a section
of virtual memory.
swap space (n.)
The memory used
for the transfer of a currently operating program from system memory
to an external storage device.
switch (n.)
A physical communication
medium containing nodes that perform only communications functions.
Examples include crossbar switches, in which N+M buses cross orthogonally at NM switching points
to connect N objects of one type to M objects of another, and
multistage switches in which several layers of switching nodes connect N objects of one type to N
objects of another type. See also butterfly,
combining, network,
shuffle exchange
network.
symmetric
multiprocessing (n.)
A form of multiprocessing in which
more than one processor can run kernel-level code
simultaneously. Contrast with
asymmetric
multiprocessing.
synchronization (n.)
The act of
bringing two or more processes to known points in their execution at
the same clock time. Explicit
synchronization is not needed in SIMD programs
(in which every processor either executes the same operation as every
other or does nothing), but is often necessary in SPMD and MIMD
programs. The time wasted by processes waiting for other processes to
synchronize with them can be a major source of inefficiency in
parallel programs. See also asynchronous,
barrier synchronization,
synchronous.
synchronous (adj.)
Occurring at the
same clock time. For example, if a
communication event is synchronous, then there is some moment at which
both the sender and the receiver are engaged in the operation. See
also asynchronous.
systolic (adj.)
Driven by the
availability of data or other resources. In a systolic system,
processes execute operations synchronously as their inputs become
available.
systolic array (n.)
A class of parallel computers with a fixed array of fine grain nodes through which data is pumped by a master
or control processor.
T1 (n.)
Transmission facility at digital
service (DS1) level 1 with 1.544Mbps in
North America and 2.048Mbps in Europe. See also T3.
T3 (n.)
Transmission facility at digital
service (DS3) level 3 with 44.736Mbps. STS1
or OC1 at 51.84Mbps is the Sonet equivalent for broadband services.
Sometimes called a 45meg circuit. See also T1.
task farming (n.)
A technique for
implementing self-scheduling
calculations. In a task farm, a source process generates a pool of
jobs, while a sink process consumes results. In between, one or more
worker processes repeatedly claim jobs from the source, turn them into
results, dispatch those results to the sink, and claim their next
jobs. If the number of jobs is much greater than the number of
workers, task farming can be an effective way to
load balance a computation.
TCP (n.)
Transmission Control Protocol is
the main transport protocol in the
internet protocol suite. It provides
reliable, stateful and connection/stream oriented end to end
connectivity.
TCP/IP (n.)
is a compound acronym used
synonymously with transmission control protocol TCP which is an internet
protocol.
telnet (n.)
An application that provides
virtual terminal services for a wide variety of remote systems. It
allows a user at one site to interact with applications at other sites
as if the user's terminal is local.
thrashing (n.)
A phenomenon of virtual
memory systems that occurs when the program, by the manner in which
it is referencing its data and instructions, regularly causes the next
memory locations referenced to be overwritten by recent or current
instructions. The result is that referenced items are rarely in the
machines physical memory and almost always must be fetched from
secondary storage, usually a disk. Cache thrashing involves a similar
situation between cache and physical
memory.
thread (n.)
A lightweight or small
granularity process.
throughput (n.)
Number of results
produced per unit time.
tiling (n.)
A regular division of a mesh into patches, or tiles. Tiling is the
most common way to do geometric
decomposition.
time sharing (adj.)
Dividing the
effort of a processor among many programs so they can run
concurrently. Time sharing is usually managed by an operating system. See also space sharing.
time-processor product
(n.)
The product of the time taken to execute a program and the number
of processors used to achieve that time, often used as a measure of
goodness for parallel algorithms. See also
Amdahl's Law,
efficiency,
Gustafson's Law,
speedup.
TLB (n.)
Translation look-aside buffer; the
memory cache of the most recently used page table entries within the
memory management unit.
token ring (n.)
Token ring is an IBM
based LAN protocol that uses a ring shaped
network topology. Token Ring has speeds at 4Mbps and 16Mbps. A
distinguishing packet is transferred from machine to machine and only
the machine that is in control of the token is able to transmit.
topology (n.)
A family of graphs
created using the same general rule or that share certain properties.
The processors in a multicomputer,
and the circuits in a switch, are usually
laid out using one of several topologies, including the mesh, the hypercube, the butterfly, the torus and the
shuffle exchange
network. See also bisection
bandwidth, diameter.
torus (n.)
A topology in which nodes form a regular cyclic d-dimensional
grid, and each edge is parallel to a grid axis and joins two nodes
that are adjacent along that axis. The architecture of some multicomputers is a two or three
dimensional torus. See also hypercube, mesh.
TP4 (n.)
OSI's
transport protocol class 4. This includes error detection and
recovery and is the most powerful OSI transport layer protocol. TP4
is the OSI equivalent of the internet's TCP.
trace scheduling (n.)
A compiler optimization
technique that vectorizes the most
likely path through a program as if it were a single
basic block, includes extra
instructions at each branch to undo any ill effects of having made a
wrong guess, vectorizes the next most likely branches and so on.
transposition table (n.)
A
hash table that stores previously evaluated game positions.
transputer (n.)
A single integrated
circuit which contains a CPU, communications
links, memory and some cache memory. The name transputer refers to
a proprietary series of chips manufactured by Inmos, although other node chips have had similar
characteristics.
tree (n.)
A connected, undirected, acyclic
graph. The most commonly encountered tree in computer science is the
regular binary tree, in which a root node
has two children but no parent, each interior node has a single parent
and two children, and leaf nodes have a single parent but no children.
true dependence (n.)
See
dependence.
true ratio (n.)
The frequency with
which the "true" branch of a Fortran IF-test occurs. If the true
ratio is know at compile time, some compilers can take advantage of
this knowledge. However the true ratio is often data dependent and
cannot effectively be dealt with automatically. See also interactive vectorizer.
tuple (n.)
An ordered sequence of fixed
length of values of arbitrary types. Tuples are used for both data
storage and interprocess communication in the
generative
communication paradigm. See also
tuple space.
tuple space (n.)
A repository for
tuples in a generative
communication system. Tuple space is an
associative memory.
twos complement (n.)
A system used in some computers to represent negative numbers in
binary. Each bit of the number is inverted (zeros are replaced with
ones and vice versa), as for ones complement, but then one
(000...0001) is added (ignoring overflow). This avoids the two
representations for zero found in ones complement by using all ones to
represent -1. (..., 000...00011 = +3, 000...00010 = +2, 000...00001 =
+1, 000...00000 = 0, 111...11111 = -1, 111...11110 = -2, 111...11101
= -3, ...)
This representation simplifies the logic required for addition and
subtraction, at the expense of a little extra complexity for negation.
UART (n.)
Universal Asynchronous
Receive-Transmit; a standard protocol for device drivers.
UDP (n.)
User datagram protocol is a
transport layer protocol in the internet protocol suite. UDP uses IP for packet delivery, and is unreliable,
connectionless, and stateless. However, UDP does not use handshaking
before exchanging data and therefore acknowledgments and guaranteed
delivery are not available. UDP relies on higher protocol layers to
provide end to end data delivery and integrity.
UMA (adj.)
Uniform memory access; permitting
any memory element to be read or written in the same, constant time.
See also NUMA.
undirected graph (n.)
A graph
whose edges have no orientation.
unification (v.)
Instantiation of a
variable with a value.
uniform cost criterion
(n.)
The assumption that every instruction takes one unit of time and
every register requires one unit of space.
uniform memory access
(adj.)
See UMA.
uniprocessor (n.)
A computer
containing a single processor. The term is generally synonymous with
scalar processor.
UNIX (n.)
An OS
originally developed by AT&T which, in various incarnations, is now
available on most types of supercomputer.
unneeded store (n.)
Situation
resulting when two or more stores into the same memory location
without intermediate reads occur in an optimization block, especially
within a DO-loop, such that only the last store need actually be
performed.
URL (n.)
Uniform Resource Locator. A standard for writing a textual reference
to an arbitrary piece of data in the world wide web
(WWW). A URL looks like "protocol://host/localinfo" where
"protocol" specifies a protocol to use to fetch the object (like HTTP or FTP), "host"
specifies the Internet name of the host on which to find it, and
"localinfo" is a string (often a file name) passed to the protocol
handler on the remote host.
utilization (n.)
Percentage of time
a processor spends executing useful tasks during execution of a
program.
uucp (n.)
Unix to Unix copy program is a
protocol used for communicating between Unix hosts using serial
interfaces.
V.35 (n.)
A data communications interface
standard adopted for use with circuits 56Kbps and above.
valence (n.)
The number of edges
connected to a vertex in a graph; for example, every node in a regular square mesh has a valence of 4. Confusingly, valence
also means the number of branches below a tree node, which is one fewer than the number
of edges incident to that node - every node in a binary tree has a
valence of 2. The term arity is sometimes
also used in this sense.
vector (n.)
An ordered list of items in a
computer's memory. A simple vector is defined as having a starting
address, a length, and a stride. An indirect address vector is
defined as having a relative base address and a vector of values to be
applied as indices to the base.
vector processor (n.)
A
computer designed to apply arithmetic operations to long vectors or
arrays. Most vector processors rely heavily on pipelining to achieve high performance.
See also array processor.
vector register (n.)
A storage
device that acts as an intermediate memory between a computer's
functional units and main memory.
vectorize (v.)
To transform a sequence
of identical arithmetic operations into a single instruction. See
also array processor,
vector processor.
vertex (n.)
component of a graph, also
sometimes called a node.
vertical processing (n.)
processing a two dimensional array column by column.
virtual channel (n.)
A logical
point-to-point connection between two processes. Many virtual
channels may time share a single link to hide latency and to avoid deadlock. See also
wormhole routing.
virtual concurrent computer
(or virtual machine) (n.)
A computer system that is programmed
as a concurrent computer of
some number of nodes P, but which is
implemented on either a real concurrent computer of some number of
nodes less than P or on a uniprocessor running software to
emulate the environment of a concurrent machine. Such an emulation
system is said to provide virtual nodes to the user.
virtual cut-through (n.)
A
technique for routing messages in which
the head and tail of the message both proceed as rapidly as they can.
If the head is blocked because a link it wants to cross is being used by some
other message, the tail continues to advance, and the message's
contents are put into buffers on
intermediate nodes. See also packet switching, wormhole routing.
virtual memory (n.)
A system that
stores portions of an address
space that are not being actively used in in some medium other
than main high-speed memory, such as a disk or slower auxiliary memory
medium. When a reference is made to a value not presently in main
memory, the virtual memory manager must swap some values in main memory for the values
required. Virtual memory is used by almost all uniprocessors and multiprocessors, but is not
available on some array
processors and multicomputers, which still employ
real memory storage only on each node.
virtual shared memory (n.)
Memory that appears to users to constitute a single
address space, but which is
actually physically disjoint. Virtual shared memory is often
implemented using some combination of hashing and local
caching.
VLIW (n.)
Very Long Instruction Word; the
use of extremely long instructions (256 bits or more) in a computer to
improve its ability to chain operations together.
VLSI (adj.)
Very Large Scale Integration;
applied to technologies capable of putting hundreds of thousands or
more components on a single chip, or sometimes applied to those chips
so manufactured.
VMS (n.)
Virtual Machine System; an operating
system developed by DEC and widely used on VAX machines. Popularity
of this OS is probably waning in favor of UNIX like systems.
Von Neumann
architecture (n.)
Used to describe any computer which does not
employ concurrency or parallelism. Named after John Von Neumann
(1903-1957) who is credited with the invention of the basic
architecture of current sequential computers.
WAN (n.)
Wide area network, a network of
circuits spanning a large region or global in proportions, that is
used to transmit data between widespread subscribers. See also LAN.
WARPS (n.)
Words accessed randomly per
second; a measure of memory access performance, equal to the rate of
uniformly random accesses across the whole of the
address space visible to a process
that a machine supports. See also FLOPS.
weak search (n.)
A search algorithm
that searches for a key and returns the node that contained the key
at the time it was examined. Weak searches are not guaranteed to
provide an up-to-date result. See also
strong search.
weight (n.)
A real number assigned to an
edge in a weighted graph.
weight matrix (n.)
A matrix
indicating, for each pair of vertices I and J, the weight of the edge
from vertex I to vertex J.
weighted graph (n.)
A graph with
a real number assigned to each edge.
working set (n.)
Those values from
shared memory that a process has
copied into its private memory,
or those pages of virtual memory
being used by a process. Changes a process makes to the values in its
working set are not automatically seen by other processes.
wormhole routing (n.)
A
technique for routing messages in which
the head of the message establishes a path, which is reserved for the
message until the tail has passed through it. Unlike virtual cut-through, the tail
proceeds at a rate dictated by the progress of the head, which reduces
the demand for intermediate buffering.
See also packet switching.
worst-case space
complexity (n.)
Greatest amount of space used by an algorithm,
over all possible inputs of a given size.
wrap-around scalar (n.)
A
scalar variable whose value is set in one iteration of a DO-loop and
referenced in a subsequent iteration and is consequently recursive.
All common reduction-function scalars are wrap-around scalars and
usually do not prevent vectorization. All other wrap-around scalars
usually do prevent vectorization of the loop in which they appear.
write-back cache (n.)
See write-in cache.
write-in cache (n.)
A cache in which writes to memory are stored in
the cache and written to memory only when a rewritten item is removed
from cache. This is also referred to as
write-back cache.
write-through cache (n.)
A
cache in which writes to memory are
performed concurrently both in cache and in main memory.
WWW (n.)
The collection of all the resources (HTML
documents, images, and other files, as well as CGI interface programs) accessible on the
Internet mainly via HTTP but also via older
protocols and mechanisms, such as FTP or Gopher, which are supported
by most Web browsers. The emergence of Web browsers has made access to
these resources achievable to a broad base of users beyond the more
technically savvy traditional users of the Internet who relied on less
user-friendly access tools than currently available browsers.
X11 (n.)
The X Window System, Version 11, developed by the Massachusetts
Institute of Technology (MIT) X Consortium. X11 is a network-based
protocol.
X.25 (n.)
is the CCITT standard protocol for transport-level
network services and was originally created for connecting terminals
to computers. It provides reliable stream-oriented transmission
services and is widely used in Europe. TCP/IP can be implemented as a layer above
X.25.
X.400 (n.)
is a CCITT protocol for electronic mail. See also
X.500.
X.500 (n.)
is a CCITT protocol for electronic mail. See also
X.400.
XDR (n.)
eXternal Data Representation is
a standard for machine independent data structures.
XNS (n.)
Xerox Networking Standard is
Xerox's proprietary networking suite of protocols and is similar to TCP/IP.
X server (n.)
In the X protocol, a basic windowing mechanism that handles
interprocess control
(IPC) connections from clients, demultiplexes graphics
requests onto the screens, and multiplexes input back to the
appropriate clients. An X server controls a single keyboard and
pointer and one or more screens that make up a single display.
Y2K (n.)
This is an acronym for the year 2000 problem, where programmers
wrote code without considering how it would work beyond 1999.
YACC (n.)
Yet Another Compiler Compiler. Together with LEX, YACC allows you
to describe a grammar in LALR(1) notation and YACC generates C code
for a program to parse it incorporating your action stub code. Similar
tools exist to generate Java source code.
ZIP (n.)
An open standard for compression and decompression used
widely for PC download archives.
Ken Hawick, hawick@npac.syr.edu Saleh Elmohamed, saleh@npac.syr.edu