Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a k -attribute Cartesian product file and an m -disk system, allocate buckets among the m disks in such a way that, for all possible partial match queries, the concurrency of disk accesses is maximized. The Disk Modulo (DM) allocation method is described first, and it is shown to be strict optimal under many conditions commonly occurring in practice, including all possible partial match queries when the number of disks is 2 or 3. It is also shown that although it has good performance, the DM allocation method is not strict optimal for all possible partial match queries when the number of disks is greater than 3. The General Disk Modulo (GDM) allocation method is then described, and a sufficient but not necessary condition for strict optimality of the GDM method for all partial match queries and any number of disks is then derived. Simulation studies comparing the DM and random allocation methods in terms of the average number of disk accesses, in response to various classes of partial match queries, show the former to be significantly more effective even when the number of disks is greater than 3, that is, even in cases where the DM method is not strict optimal. The results that have been derived formally and shown by simulation can be used for more effective design of optimal file systems for partial match queries. When considering multiple-disk systems with independent access paths, it is important to ensure that similar records are clustered into the same or similar buckets, while similar buckets should be dispersed uniformly among the disks.

Many cases arise in practice where a versatile hardwired pseudorandom number or pseudonoise generator would be extremely useful. General-purpose pseudonoise devices are not available today. We present a new sampling method, conditional bit sampling, which is suited for hardwired sampling devices because of its generality, simplicity, and accuracy. Random variables sampled from an arbitrary distribution are generated bit by bit from high- to low-order bits with the conditional bit algorithm. The result of a comparison of a uniform number to a conditional probability determines whether a bit in the sampled random number is set to one. The conditional probabilities are easily calculated for any probability distribution and must be arranged in special order. Simple Fortran programs make all necessary computations. Agreement between actual and theoretical performance of the conditional bit algorithm was excellent when sampling accuracy was evaluated for several examples of continuous and discrete densities. Sampling from empirically known, perhaps erratic-shaped, densities presents no problems. Only a small memory containing the conditional probabilities needs to be changed to alter the sampled distribution. The conditional bit algorithmic process always remains the same.

A hardwired device that produces a voltage with arbitrary amplitude distribution was constructed using a "conditional bit" algorithm to sample from an arbitrary voltage amplitude distribution. The sampling algorithm and hardware processor are independent of the distribution sampled. Only a small read-only memory ROM needs to be changed to alter the distribution sampled. It is possible to compute the accuracy of the sampled random variables from knowledge of the read-only memory contents. The sampling accuracy of the device may be arbitrarily increased by varying any of several design parameters. Our particular pseudonoise generator produced 200 000 random seven-bit variables/s. Contents of read-only memories for both a Gaussian and an arbitrary density were computed so that the maximum error was less than 2.73 percent. Both the sampling speed and accuracy of a conditional bit pseudonoise generator can be increased much in excess of our implementation.

Most large time-sharing computers require some sort of a data concentrator or multiplexor to accept inputs from a large number of low-speed remote terminals. Two major disadvantages of most of these concentrators are that they are nonprogrammable and relatively expensive. This paper describes the use of a small microprogrammed computer with a special instruction wired into the READ-ONLY memory to perform the multiplexing action. This approach has resulted in a programmable terminal controller which will handle up to 32 remotes, and provides enough processing capability to do code conversion and editing. This not only relieves the main computer of these routine tasks, but also reduces the amount and complexity of system modification within the main computer.