C
C a language developed at AT&T Bell Laboratories in the 1970s, a derivative of BCPL.
C&P See capture and playback.
C++ a language developed at AT&T Bell Laboratories in the 1980s, an object-oriented variant of the C language. A language based loosely on the principles of SIMULA-67.
cable drive in robotic manipulators, transmission of motive forces from actuators to links via wire cables.
cache (1) an intermediate memory store having storage capacity and access times somewhere in between the general register set and main memory. A cache is usually invisible to the programmer, and its effectiveness comes from being able to exploit program locality to anticipate memory-access patterns and to hold closer to the CPU; most accesses to main memory can be satisfied by the cache, thus making main memory appear to be faster than it actually is.
There may be more than one cache; if so, they are traditionally numbered by their nearness to the processor. The closest, and usually smallest but fastest, cache is called the âLI cacheâ, the next one out is called the âL2 cacheâ, and so on. A compiler may be able to take advantage of the presence of a cache to optimize the performance of code.
See code cache, data cache, direct mapped cache, fully associative cache, set-associative cache, cache line, cache line size, and unified cache.
(2) a data structure which holds a (typically small) number of values, used to expedite access to larger data structures. When a cache is filled and a new element must be placed in it, a cache replacement algorithm is used to determine which element to discard.
cache aliasing a situation where two or more entries (typically from different virtual addresses) in a cache correspond to the same address(es) in main memory. Considered undesirable, as it may lead to a lack of consistency (coherence) when data is written back to main memory.
cache associativity the number of cache entries that can be searched concurrently.
cache block the number of bytes transferred as one piece when moving data between levels in the cache hierarchy or between main memory and cache. The term line is sometimes used instead of block. Typical block size is 16128 bytes and typical cache size is 1-256 KB. The block size is chosen so as to optimize the relationship of the âcache miss ratioâ, the cache size, and the block transfer time.
cache coherence the problem of keeping consistent the values of multiple copies of a single variable, residing either in main memory and cache in a uni-processor, or in different caches in a multi-processor computer. In a uni-processor, the problem may arise if the I/O system reads and writes data into the main memory, causing the main memory and cache data to be inconsistent, or if there is aliasing. Old (stale) data could be output if the CPU has written a newer value in the cache, and this has not been transported to the memory. Also, if the I/O system has input a new value to main memory, new data would reside in main memory, but not in the cache.
cache coherence protocol a mechanism to maintain data coherence among multiple caches so that every data access will always return the latest version of that datum in the system.
cache consistency in a system with multiple processors, each with its own local cache, the caches are consistent if each cache always contains exact copies of remote data. The problem of keeping local cache copies up to date with changes in remote data is known as the cache consistency problem.
cache hit when the data referenced by the processor is already in the cache.
cache hit ratio the percentage of time in which a requested instruction or data is actually in the cache.
cache line (1) the fundamental quantum of caching. From the notion of a hardware cache, in which some number of bits, bytes, or other storage units are transferred to the next outer cache as a single unit of information. This unit of information is a cache line. Each level of cache in a multilevel system may have its own cache line size.
(2) a block of data associated with a cache tag.
cache line size the number of bits, bytes, or other storage units that can be stored in a single cache line. Knowledge of the cache line size and the cache replacement algorithm can allow a compiler to optimize the code to work with, rather than against, the cache. Speedups by factors of 20 or more have been seen for FORTRAN programs accessing array data.
cache memory See cache.
cache miss a reference by the processor to a memory location currently not housed in the cache.
cache replacement when a âcache missâ occurs, the block containing the accessed location must be loaded into the cache. If this is full, an âoldâ block must be expelled from the cache and replaced by the ânewâ block. The âcache replacement algorithmâ decides which block should be replaced. An example of this is the Least Recently Used (LRU) algorithm, which replaces the block that has gone the longest time without being referenced.
cache replacement algorithm a means of determining which element of a cache to replace when the cache is full and a new element must be placed in the cache. Most caches are commonly managed by using a Least Recently Used algorithm, but other techniques including hash associative and set associative can be used.
cache set See set-associative cache.
cache synonym See cache aliasing.
cache tag a bit held associated with each block in the cache. It is used to determine where (and if) a referenced block resides in the cache. The tags are typically housed in a separate (and even faster) memory (the âtag directoryâ), which is searched in for each memory reference. In this search, the high order bits of the memory address are associatively compared with the tags to determine the block location. The number of bits used in the tag depends on the cache block âmapping functionâ used: âDirect-mappedâ, âFully associativeâ or the âBlock-set-associativeâ mapped cache.
cactus stack a representation of a stack in which multiple threads of control share the stack-defined namespace hierarchy; so named because a diagram of the stack relationships resembles a saguaro cactus.
CAD See computer-aided design.
calculus of communicating system (CCS) Robin Milnerâs algebraic theory to formalize the notion of concurrent computation. This process algebra is used to describe process behavior, mainly used in the study of parallelism. It has operators for the parallel composition of processes, for synchronization, to hide events, etc. Programs written in CCS can be compared using the notion of observational equivalence that checks if two processes have the same external behavior. See process algebra, CSP.
calendar time synonymous with real-time.
calibration process of adjusting system parameters to optimize accuracy or to ensure conformity to a standard.
call See function call.
call-by-address See call-by-reference.
call-by-name a mechanism defined by the Algol-60 specification, stating that the appearance of a formal parameter of a function in a function body would evaluate the actual parameter expression each time such a use occurred. This led to interesting problems in side effects. See also call-by-reference, call-by-value.
call-by-name reduction See normal-order reduction.
call-by-reference a mechanism for parameter passing in many languages which states that the value of the actual parameter is not passed to the called function, but rather a reference (memory address) to the value is passed instead. Use of the actual parameter in the function body uses or modifies the value thus referenced. Also called call-by-address. See also call-by-name, call-by-value, call-by-value-result.
call-by-result a mechanism for parameter passing in many languages which states that the actual parameter must reference a value that can be modified. In the body of the function, the appearance of the formal parameter can only be as the target of an assignment (or it can be passed as a call-by-result parameter to another function). The formal parameter represents a local variable. Upon return from the function, the contents of the local variable representing the formal parameter are copied to the location specified by the actual parameter. See also call-by-value, call-by-value-result.
call-by-value a mechanism for parameter passing in many languages that states that the expression defining the value of an actual parameter is computed once and the resulting value is passed to the function being called. In the body of the function, the appearance of the formal parameter represents the copy of the value that has been made. Some languages do not permit the value represented by the formal parameter to be modified in the body of the function.
call-by-value-result a mechanism for parameter passing in many languages that states that the actual parameter to a function must reference a value that can be modified. A copy of this value is made and is passed into the function that is called. Upon return from the function, the value of the formal parameter is copied back to the location from which it was originally copied. While this appears to be similar to call-by-reference, its behavior with respect to side effects is quite different, particularly when aliasing occurs, and it can also support alternate value representations between the actual parameter type and formal parameter type. See also call-by-name, call-by-reference, c...