While automatic image registration algorithms are usually being evaluated with regards to their accuracy, it is often useful to relate this accuracy to the "initial conditions", i.e., the distance between the initial navigation geolocation and the correct result. This paper describes a modular framework that was built to describe registration algorithms, and utilize this framework to attempt to classify different registration components and algorithms in terms of their responses to the initial conditions. Performances would be evaluated on synthetic data, multitemporal and multisensor data. All results of the study would be presented at the conference and would be useful for two different purposes: (1) provide automatic quality assessment of the geolocation of remote sensing data by performing interalgorithm consistency studies; and (2) be the foundations for the design of future on-board applications including planetary exploration.

The study of global environmental changes involves the comparison, fusion, and integration of multiple types of remotely-sensed data at various temporal, radiometric, and spatial resolutions. Results of this integration may be utilized for global change analysis, as well as for the validation of new instruments or for new data analysis. Furthermore, future multiple satellite missions will include many different sensors carried on separate platforms, and the amount of remote sensing data to be combined is increasing tremendously. For all of these applications, the first requires step is fast and automatic registration, and as this need for automating registration techniques is being recognized, it becomes necessary to survey all the registration methods which may be applicable to Earth and space science problems and to evaluate their performances on a large variety of existing remote sensing data as well as on simulated data of soon-to-be-flown instruments. In this paper we present one of the first steps toward such as exhaustive quantitative evaluation. First, the different components of image registration algorithms are reviewed, and different choices for each of these components are described. Then, the results of the evaluation of the corresponding algorithms combing these components are described. Then, the results of the evaluation of the corresponding algorithms combining these components are presented on several datasets. The algorithms are based on gray levels or wavelet features and compute rigid transformations (including scale, rotation, and shifts). Test datasets include synthetic data as well as data acquired over several EOS Land Validation Core Sites with the IKONOS and the Landsat-7 sensors.

Current art uses metadata associated with satellite images to facilitate their retrieval from image repositories. Typical metadata are geographic location, time, and data type. Because the metadata do not indicate which regions within an image are obscured by clouds, retrieval with such metadata may produce an image within which the region of interest (ROI) for the user is not visible. We report a system that can automatically determine whether an ROI is visible in the image, and can incorporate this into the metadata for individual images to enhance searching capability. The goal is to annotate each image with metadata regarding a number of ROIs. An experiment with the system annotated 236 advanced very high resolution radiometer (AVHRR) images of the North Atlantic from a five-month viewing period with descriptors that expressed the visibility of an ROI centered on Long Island, NY. For ground truth, we used the classifications of three human subjects to determine visibility of the same region of interest, and labeled the ROI with the majority decision of the three subjects. Partial cloud cover made the human determination subjective, and resulted in disagreements among the subjects. Using randomly selected training subsets of the images, we found the two images whose regions were most like those in images for which the Long Island region was visible.

This paper describes a fast technique for registering image pairs from visible and infrared spectra that differ by translation, small rotations, and small changes of scale. The main result of this paper is a nonlinear prefiltering and thresholding technique that substantially enhances the cross-spectral correlation, provided that the image pairs have many features in common. We show the use of the technique in conjunction with a Fourier-based normalized correlation algorithm to perform fast cross-spectral registrations. In the absence of such prefiltering, local reversals of contrast from image to image tend, to impair the quality of correlation-based registrations. The algorithm computes the translation that maximizes the overall normalized correlation of the filtered images without examining individual image features. Small rotations and scale changes can be recovered by computing the translation displacement in several different regions of the image pairs. In an experiment on a moderate-sized database, the algorithm produced a correct registration rate of over 90% at a false positive rate of less than 10%. For a particularly difficult subset of images in the database, the correct registration rate fell to approximately 85% at a false positive rate of less than 10%. This retrieval quality is comparable to that of a mutual-information-based algorithm.

This paper presents a new direct Fourier-based algorithm for performing image-to-image registration to subpixel accuracy, where the image differences are restricted to translations and uniform changes of illumination. The algorithm detects the Fourier components that have become unreliable estimators of shift due to aliasing, and removes them from the shift-estimate computation. In the presence of aliasing, the average precision of the registration is a few hundredths of a pixel. Experimental data presented here show that the new algorithm yields superior registration precision in the presence of aliasing when compared to several earlier methods and has comparable precision to the iterative method of P. Thevenaz et al. (1998).

This paper describes and compares techniques for registering an image with respect to a template image when one or both are partially occluded. These techniques can be used to build correlation-based image registration (alignment of similar images) and image search (finding a sub-image within a larger image) algorithms. Binary masks as developed by Stone and Shamoon [18], and extended by Stone [15] to multi-resolution images, allow exact comparison of partially occluded images. Fractional masks, introduced in this paper, extend this idea for better discrimination on low-resolution images. The low and multi-resolution images result from searching the low-pass subbands of wavelet representations of images. By operating on low-resolution images and computing the correlation function in the frequency domain, the mask based algorithms can be implemented efficiently. We present experimental evidence supporting the use of occlusion masks in the registration process and find that binary masks produce higher registration peaks while fractional masks produce sharper peaks.

This paper studies the effects of image translation on wavelet-based image registration. The main result is that the normalized correlation coefficients of low-pass Haar and Daubechies wavelet subbands are essentially insensitive to translations for features larger than twice the wavelet blocksize. The third-level low-pass subbands produce a correlation peak that varies with translation from 0.7 and 1.0 with an average in excess of 0.9. Translation sensitivity is limited to the high-pass subband and even this subband is potentially useful. The correlation peak for high-pass subbands derived from first and second-level low-pass subbands ranges from about 0.0 to 1.0 with an average of about 0.5 for Daubechies and 0.7 for Haar. We use a mathematical model to develop these results, and confirm them on real data.

This work presents the design details and experimental results for a parallel optical link. The link is designed for connections within high-speed digital systems, specifically for board- and backplane-level interconnections. The link can contain as many fibers in parallel as technology permits. The unusual aspects of this interconnection system are that it is DC-coupled and uses fully differential inputs, two optical channels per signal, to achieve self-thresholding and noise immunity. A chip set consisting of a 2.5-Gb/s bipolar differential laser driver, a 800-Mb/s GaAs MSM (metal-semiconductor-metal) preamplifier array, a 800-Mb/s GaAs MSM preamplifier-postamplifier array, and a GaAs MSM preamplifier array in which each preamplifier has a different bandwidth varying from 300 Mb/s to 2 Gb/s has been designed, fabricated, and tested to serve as a vehicle for verifying the concept. Although the experimental testing of the entire interconnect system is not yet complete, the experimental studies presented show a bandwidth in excess of 800 MHz and excellent signal isolation between channels.>

A fully differential optical link for board-to-board and onboard interconnections within digital systems is proposed and evaluated. The unique features of this link are that it transmits uncoded signals and the link receiver can be, at least in principle, fully DC-coupled, to produce a low-latency, high-bandwidth parallel synchronous interconnection. Both theory and link simulations show that a fully differential link has essentially the same SNR as a comparable single-ended link, but the differential system is less susceptible to the common-mode noise such as the switching noise generated at the transmitter or at the receiver input.>

A mathematical model for the behavior of programs or workloads is presented and from it is extracted the miss ratio of a finite, fully associative cache (or other first-level memory) using least-recently-used replacement under those workloads. To obtain miss ratios, the function u(t, L), defined to be the number of unique lines of size L referenced before time t, is modeled. Empirical observations show that this function appears to have the form u(t, L)=(W L/sup a/t/sup b/) (d/sup log/ /sup L log t/) where W, a, b, d are constants that are related, respectively, to the working set size, locality of references to nearby addresses (spatial locality), temporal locality (locality in time not attributable to spatial locality), and interactions between spatial locality and temporal locality. The miss ratio of a finite fully associative cache can be approximated as the time derivative of u(t, L) evaluated where the function has a value equal to the size of the cache. When the miss ratios from this model are compared to measured miss ratios for a representative trace, the accuracy is high for large caches. For smaller caches, the model is close but not highly precise.>

A model for studying the optimal allocation of cache memory among two or more competing processes is developed and used to show that, for the examples studied, the least recently used (LRU) replacement strategy produces cache allocations that are very close to optimal. It is also shown that when program behavior changes, LRU replacement moves quickly toward the steady-state allocation if it is far from optimal, but converges slowly as the allocation approaches the steady-state allocation. An efficient combinatorial algorithm for determining the optimal steady-state allocation, which, in theory, could be used to reduce the length of the transient, is described. The algorithm generalizes to multilevel cache memories. For multiprogrammed systems, a cache-replacement policy better than LRU replacement is given. The policy increases the memory available to the running process until the allocation reaches a threshold time beyond which the replacement policy does not increase the cache memory allocated to the running process.>

An adaptive algorithm for managing fully associative cache memories shared by several identifiable processes is presented. The on-line algorithm extends an earlier model due to H.S. Stone et al. (1989) and partitions the cache storage in disjoint blocks whose sizes are determined by the locality of the processes accessing the cache. Simulation results of traces for 32-MB disk caches show a relative improvement in the overall and read hit-ratios in the range of 1% to 2% over those generated by a conventional least recently used replacement algorithm. The analysis of a queuing network model shows that such an increase in hit-ratio in a system with a heavy throughput of I/O requests can provide a significant decrease in disk response time.>

Two techniques for producing synthetic address traces that produce good emulations of the locality of reference of real programs are presented. The first algorithm generates synthetic addresses by simulating a random walk in an infinite address-space with references governed by a hyperbolic probability law. The second algorithm is a refinement of the first in which the address space has a given finite size. The basic model for the random walk has two parameters that correspond to the working set size and the locality of reference. By comparing synthetic traces with real traces of identical locality parameters, it is demonstrated that synthetic traces exhibit miss ratios and lifetime functions that compare well with those of the real traces they mimic, both in fully associative and in set-associative memories.>

Two models are presented for conducting simple searches under the assumption that the tasks within the search tree are complex and may be I/O bound. The objective is to achieve the minimum expected time to completion. The simpler model assumes that the search paths are disjoint. The optimal policy in the general case is to run the tasks with the highest ratio of success probability per cycle expended. If one task is sufficiently small compared to the other task that it completes first in all schedules, the optimum scheduling policy is based on a comparison of ratios of the form p/r, where p is the probability of success and r is the marginal processing rate of a task. For the second model the search paths are independent, and the success or failure on one path is not related to the success or failure on any other path. This model generally gives priority to the task that has the highest probability per marginal execution rate. For both models, the results reported hold only for a search with two paths. For the problem of scheduling N tasks the policy of giving priority to tasks according to descending values of probability of success over cost is generally a good idea, although it does not necessarily yield an optimum schedule.>

This paper develops an analytical model for cache-reload transients and compares the model to observations based on several address traces. The cache-reload transient is the set of cache misses that occur when a process is reinitiated after being suspended temporarily. For example, an interrupt program that runs periodically experiences a reload transient at each initiation. The reload transient depends on the cache size and on the sizes of the footprints in the cache of the competing programs, where a program footprint is defined to be the set of lines in the cache in active use by the program. The model shows that the size of the transient is related to the normal distribution function. A simulation based on program-address traces shows excellent agreement between the model and the observations.

This paper develops an analytical model for a cache-reload transient. When an interrupt program or system program runs periodically in a cache-based computer, a short cache-reload transient occurs each time the interrupt program is invoked. That transient depends on the size of the cache, the fraction of the cache used by the interrupt program, and the fraction of the cache used by background programs that run between interrupts. We call the portion of a cache used by a program its footprint in the cache, and we show that the reload transient is related to the area in the tail of a normal distribution whose mean is a function of the footprints of the programs that compete for the cache. We believe that the model may be useful as well for predicting paging behavior in virtual-memory systems with round-robin scheduling.

An investigation is made of an optimal task-assignment policy for a random-graph model of a distributed program. The model of the distributed computer system assumes that communications overhead adds to total run time and that total run time decreases as the number of processors running the program is increased. When the processors are homogeneous, the optimal task-assignments are external in the sense that tasks are totally distributed among all processors as evenly as possible or not distributed at all. The point at which the policy shows a sharp change of behavior depends upon the ratio of run times to communication times. The authors derive two important properties of the optimal task-assignments for heterogeneous processors. The first property is that an optimal policy distributes the cost of processing among the processors as evenly as possible so that a processor with higher speed gets more tasks and vice versa. The second property determines the number of processors among which to distribute the tasks evenly. In the special case when there is a uniform degradation of processing speed, it is shown that the optimal policy again exhibits an extremal characteristic.

This paper introduces a graph space that shows concisely the relative weights among combinations of vertices of a given hypergraph. (A hypergraph is a graph in which one edge may connect two or more vertices.) The hypergraph is represented by a collection of points in graph space such that the distance between vertices in graph space reflects the weights of the edges between vertices of the original hypergraph. Vertices of the hypergraph that are connected by edges with large weights are mapped to nearby points in graph space. Thus, graph space reveals properties of the connectivity of vertices in the hypergraph. A natural application of graph space is the placement of modules in computer systems since strongly coupled modules are transformed into nearby points in graph space. The graph of the airlines network in the United States is taken as an example of a hypergraph, and the paper illustrates the corresponding graph space.

The FETCH-AND-ADD instruction provides for synchronization of multiple processes in a parallel manner. This paper explores the use of FETCH-AND-ADD in the context of database systems. We show how to enqueue locks, detect lock conflicts, and release locks without resorting to critical program sections that require mutual exclusion during execution. The scheme is compatible with a variant of lock management proposed by Rosenkrantz and Stearns. A second approach to parallel lock management is based on a reservation scheme by Milenkovic. This methodology uses FETCH-AND-ADD implementation of a priority queue. An implementation of such a queue originally reported by Gottlieb and Kruskal is used for this purpose, although the storage requirements for queue management may be unacceptably large in specific cases. Both approaches described in the paper suggest that FETCH-AND-ADD is potentially effective for eliminating serial bottlenecks caused by lock conflicts in multiprocessor systems.

An optimal unrealizable (in real time) virtual memory allocation algorithm DMIN is developed. OMIN has the following properties. A dynamic (time-varying) size of allocation is computed by DMIN to minimize the space-time product of physical memory aliocated to a task during execution. The algorithm is a function of one parameter R, the reactivation time-the average time from the occurrence of a page fault for a task to restarting execution of the task.

A recently published algorithm shows how to assign modules to a two-processor computer system with distributed execution so as to minimize the total of execution costs and interprocessor communication costs. In this paper we consider the same problem except that one processor has limited memory capacity. Although this problem is NP-complete, techniques based on the Gomory–Hu tree from network flow theory can be applied to instances of the problem to obtain a reduction in complexity. A new technique based on a graph called the inclusive cut graph is shown to be an even more powerful tool. These two techniques can solve some instances of the problem completely; still others are reduced sufficiently to be susceptible to enumerative techniques. In the worst case, the techniques yield no reduction in problem size.

This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's sorting algorithm, which makes especially good use of vector operations but has a complexity of N (log N)2 as compared to a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.

In a two-processor distributed computer network, prior research showed that a maximum flow algorithm can be used to find optimal program-module-to-processor assignments to maximize the performance of distributed programs. This paper examines the sequence of optimal assignments found as the load on one processor is held fixed and the load on the other is varied. For every program module M there exists a critical load factor fM such that when the load on the processor with variable load is below fM, M is assigned to that processor by an optimal assignment, and is otherwise assigned to the other processor. This characteristic opens the possibility of doing optimal dynamic assignments in real-time.

In a distributed computing system a modular program must have its modules assigned among the processors so as to avoid excessive interprocessor communication while taking advantage of specific efficiencies of some processors in executing some program modules. In this paper we show that this program module assignment problem can be solved efficiently by making use of the well-known Ford–Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov. A solution to the two-processor problem is given, and extensions to three and n-processors are considered with partial results given without a complete efficient solution.

In this paper, a control mechanism for a shuffle-exchange interconnection network of N cells is proposed. With this network it is possible to realize some important permutations in log2N shuffle-exchange steps. In the control mechanism presented, the control variables at step k are determined by a Boolean operation of the control variables at step k - 1. The Boolean operation is very simple so that little additional hardware is required for this computation. This control scheme requires only one bit per cell instead of a destination tag of log2N bits required by a control mechanism presented previously. The network can be used for the interconnection of memory modules and processors in an array computer, and for the accessing of blocks of consecutive data in large dynamic memories. It is also shown that the shuffle-exchange interconnection network permits the efficient partitioning of an array computer into subarrays to allow for the simultaneous computation of several identical problems.

This paper treats two dynamic memories, one proposed by Aho and Ullman and the other proposed by Stone. The first memory has the property that every item is accessible in 0 (log2 N) steps, and that after access to the first two items of a block of contiguous items, each successive item can be accessed in unit time. In this paper we give a new derivation of the properties, and indicate minor variations and improvements of the memory-access algorithm.

Three parallel algorithms were compared for the direct solution of tridiagonal linear systems of equations. The algorithms are suitable for computers such as ILLIAC 4 and CDC STAR. For array computers similar to ILLIAC 4, cyclic odd-even reduction has the least operation count for highly structured sets of equations, and recursive doubling has the least count for relatively unstructured sets of equations. Since the difference in operation counts for these two algorithms is not substantial, their relative running times may be more related to overhead operations, which are not measured in this paper. The third algorithm, based on Buneman's Poisson solver, has more arithmetic operations than the others, and appears to be the least favorable. For pipeline computers similar to CDC STAR, cyclic odd-even reduction appears to be the most preferable algorithm for all cases.

Tridiagonal linear systems of equations can be solved on conventional serial machines in a time proportional to N , where N is the number of equations. The conventional algorithms do not lend themselves directly to parallel computation on computers of the ILLIAC IV class, in the sense that they appear to be inherently serial. An efficient parallel algorithm is presented in which computation time grows as log 2 N . The algorithm is based on recursive doubling solutions of linear recurrence relations, and can be used to solve recurrence relations of all orders.

An mth-order recurrence problem is defined as the computation of the series x1, x2, ..., XN, where xi= fi(xi-1, ..., xi-m) for some function fi. This paper uses a technique called recursive doubling in an algorithm for solving a large class of recurrence problems on parallel computers such as the Iliac IV. Recursive doubling involves the splitting of the computation of a function into two equally complex subfunctions whose evaluation can be performed simultaneously in two separate processors. Successive splitting of each of these subfunctions spreads the computation over more processors. This algorithm can be applied to any recurrence equation of the form xi= f(bi, g(ai, xi-1)) where f and g are functions that satisfy certain distributive and associative-like properties. Although this recurrence is first order, all linear mth-order recurrence equations can be cast into this form. Suitable applications include linear recurrence equations, polynomial evaluation, several nonlinear problems, the determination of the maximum or minimum of N numbers, and the solution of tridiagonal linear equations. The resulting algorithm computes the entire series x1, ..., xNin time proportional to [log2N] on a computer with N-fold parallelism. On a serial computer, computation time is proportional to N.

Dynamic memories are commonly constructed as circulating shift registers, and thus have access times that are proportional to the size of memory. When each word in a dynamic memory is connected to r words, r ≥ 2, access time can be proportional to the base r logarithm of the size of memory. A memory that achieves minimum access time for r = 2 is described. The memory can also be operated in an efficient binary search mode. Slight variations of the interconnection patterns lead to a memory that is well suited for FFT and certain matrix computations.

Given a vector of N elements, the perfect shuffle of this vector is a permutation of the elements that are identical to a perfect shuffle of a deck of cards. Elements of the first half of the vector are interlaced with elements of the second half in the perfect shuffle of the vector.

The enumeration of the incorrectly decoded bursts for cyclic burst error-correcting codes is reported here. The enumeration yields closed formulas for long bursts, whereas an efficient algorithm for the enumeration is given for the short bursts. The enumeration is carried out for two different decoding rules. Under the first rule, the cyclic code is a full length code, and split decodable patterns are decoded by the decoder in spite of the fact that a split decodable pattern can be a burst that exceeds the decoding capability of the decoder. The analysis for the second rule assumes split patterns are not decoded. This analysis is valid for the class of shortened cyclic codes.

An algorithm is described for partitioning the elements of a digital logic design into physical packages where each package contains components of one type and where connected components of the same type are assigned to the same package.The problem is a special case of the one-dimensional cutting-stock problem.

This paper describes the organization of a multi-module memory, designed to facilitate parallel block transfers. All modules are assumed to be identical, and the individual modules can fetch or store no more than one word or word group during any single memory cycle. Parallel block transfers are made possible in multimodule memories by utilizing a device called the memory circulator and by organizing the memory in a particular way. The memory circulator consists of a bank of interconnected registers, one for each memory, and control circuitry. The memory system is organized so that ascending logical addresses are distributed cyclically among the modules. If there are 2bmodules, then any individual word is accessed by using the least significant b bits of a memory address to select a module and by using the remaining bits to select an address within a module. The memory circulator can load and store a contiguous block of 2bwords by selecting all modules and broadcasting a single address to all modules. A contiguous block can be displaced in memory by a multiple of 2bwords by broadcasting different load and store addresses for a block of data. The circulator control circuitry includes a masking capability so that blocks smaller than 2bcan be moved in this fashion. When the displacement of a block transfer is not a multiple of 2ba physical circulation of the data in the memory circulator registers is required.

If, as presently projected, the cost of microelectronic arrays in the future will tend to reflect the number of pins on the array rather than the number of gates, the logic-in-memory array is an extremely attractive computer component. Such an array is essentially a microelectronic memory with some combinational logic associated with each storage element. A logic-in-memory computer is described that is organized around a logic-enhanced ``cache'' memory array. Used as a cache, a logic-in-memory array performs as a high-speed buffer between a conventional CPU and a conventional memory. The effect on the computer system of the cache and its control mechanism is to make the main memory appear to have all of the processing capabilities and almost the same performance as the cache. Operations within the array are naturally organized as operations on blocks of data called ``sectors.'' Among the operations that can be performed are arithmetic and logical operations on pairs of elements from two sectors, and a variety of associative search operations on a single sector. For such operations, the main memory of the computer appears to the program to be composed of a collection of logic-in-memory arrays, each the size of a sector. Because of the high-speed, highly parallel sector operations, the logic-in-memory computer points to a new direction for achieving orders of magnitude increase in computer performance. Moreover, since the computer is specifically organized for large-scale integration, the increased performance might be obtained for a comparatively small dollar cost.

Scheduling and resource allocation have come to the forefront of the problems that confront the designers of computer systems. This is particularly true in time-sharing, multiprogramming, and real-time systems, but it is also the case for somewhat less sophisticated systems due to problems created by disk accessing. Theory of Scheduling is a very readable treatment of some of the "classical" solutions to scheduling problems, as well as some heuristic ad hoc approaches that are suitable in particular computer environments. The operating systems designer should not consider this book as the panacea for all of his ills, however, because the methodology that is given for solving his scheduling problems may be unsatisfactory in the context in which he chooses to use it. For example, in a real-time system the scheduling algorithm must satisfy constraints on maximum computation time which are not necessarily satisfied by the algorithms described in the text.

The equivalence relation that partitions switching functions into affine families leads to a natural graphic representation of the families. From the graphs, it is possible to derive information on the self-symmetries of switching functions and the relative symmetries of functions that are in the same family. A catalog of the structures of the 39 families of four-variable functions appears in the paper. The catalog and, more generally, the theory of affine equivalence are useful tools for the design of logic networks that contain exclusive-OR modules among the set of primitive building blocks.

Cascades of two-input, one-output general function cells have been studied previously with the restriction that no external variable may drive more than one cell. Upon relaxing this restriction, it is shown that a variable that drives more than one cell in a cascade need never drive more than one cell that is not an EXCLUSIVE-OR cell, and that cell must be the first cell driven by the variable in the cascade. From this it follows that there exists a canonical form for cellular cascades with repeated inputs. Furthermore, the length of a cascade required to produce an n-variable function is bounded by (n2+n-4)/2, and there are functions that meet this bound for all n. Derived from knowledge of the canonical form, a realizability and synthesis algorithm is described that is an extension of previously described algorithms. The algorithm has been used to test the 402 Harvard functions, and a table of minimal-length cascades of realizable functions is included in the paper. Although the number of realizable functions is greatly increased when the input restriction is relaxed, it is shown that the fraction of n-variable functions that are realizable becomes vanishingly small as n grows large. In particular, for example, of the 2n+1symmetric functions of n-variables, precisely 12 are realizable for all n≥3.