High Performance Computing and Communications Glossary 2.1

A significant part of the material of this glossary was adapted from material originally written by Gregory V. Wilson which appeared as "A Glossary of Parallel Computing Terminology" (IEEE Parallel & Distributed Technology, February 1993), and is being re-printed in the same author's "Practical Parallel Programming" (MIT Press, 1995). Several people have contributed additions to this glossary, especially Jack Dongarra, Geoffrey Fox and many of my colleagues at Edinburgh and Syracuse.

Original version is from NPAC at <URL:http://nhse.npac.syr.edu/hpccgloss/>

Original author: Ken Hawick, khawick@cs.adelaide.edu.au

See also the index of all letters and the full list of entries (very large)

Sections: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


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 parallelising 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 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.

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 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.

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.