Proximity queries that involve multiple object types are very common. In this paper, we present a parallel algorithm for answering proximity queries of one kind over object instances that lie in a one-dimensional metric space. The algorithm exploits a specialized hardware, the Dynamic Associative Access Memory chip. In most proximity queries of this kind, the number of object types is less than or equal to three and the distance d, within which object instances are required to locate to satisfy a given proximity condition, is small (dd=80e = 1). The execution time for such queries is linearly proportional to the number of object types and is independent of the size of the database. This allows numerous concurrent users to be serviced. The algorithm is extended to process 2-dimensional proximity queries efficiently. This research is supported in part by NASA under NAGW-4080 and ARO under BMDO grant DAAH04-0024. 1 1

A dynamic random access memory (DRAM) chip is to be modified to associatively search data in it as it is being refreshed in the chip and to communicate in a linear systolic array. In a preliminary logic design of a (256*4096) associative memory chip based on a 1-Mb DRAM, the approximately 10 transistors per sense amplifier in a DRAM are expanded to approximately 24 transistors per sense amplifier in the modified chip. The chip size is only slightly increased, and it is manufactured using the same processes, in the same plant, as a DRAM chip; thus, it should cost about the same as a DRAM. A large array of such modified DRAMs could store a terabit database and search all of it every 60 mu s. Bit pattern searching and search-rewrite algorithms could be economically performed over very large amounts of data. The concepts and the design of the simple modified DRAM are discussed.>

The processing features of the Texas Reconfigurable Array Computer (TRAC) are examined, with emphasis on partitioning using buses and the usefulness of SIMD-MIMD. The trees used in TRAC are considered as well as the programmer's view of a task space. It is concluded that many real algorithms require a plurality of computational mechanisms, and TRAC, having a rich set of capabilities, should provide a means to solve them efficiently.>

Construction algorithms for rectangular and nonrectangular CC-banyan networks, as well as routing algorithms for double-ended and single-ended rectangular and nonrectangular CC-banyan networks, are presented. The time complexities of the routing algorithms are O(l), where l is the number of stages in the network.>

A fetch-and-op circuit is described. A bit-serial circuit-switched implementation requires only five gates per node in a binary tree. This circuit is also capable of test-and-set primitives (priority circuits) and swap operators, as well as AND and OR operations used in SIMD (single-instruction, multiple-data-stream) tests such as branch on all carries set. It provides an alternative implementation for the combining fetch-and-add circuit to the one designed for the Ultracomputer project; this implementation is suited to SIMD computing and can be adapted to MIMD (multiple-instruction, multiple-data stream) computing.>

A novel implementation of a Two-dimensional FFT array processor is given. The reasons for its superior performance is the one-to-one and onto mapping of the problem communications topology onto the interconnection network, VLSI-based implementation, a proper choice for the number system, multiple-parallelism, and the use of packet-switching as opposed to circuit switching. A performance comparison also presented.

A resource allocation problem in a reconfigurable multicomputer architecture based on rectangular CC-banyan multistage interconnection network with arbitrary fanout and arbitrary number of levels is studied. Four commonly used problem structures such as ring, pipeline, broadcast and macropipeline are introduced and the mapping problem of these structures on the system model which is camparable to the resource allocation problem, is discussed. Analytic solutions to several mapping questions are presented and a new fault diagnosis method based on the solution to the problem of mapping the ring structure is given.

A new architecture for local area networks, based on the carry-lookahead circuit has been described in recent papers. It features a cost-effective hardware round-robin priority circuit, a bus and a shift register ring network that uses the same hardware. This paper shows that such an architecture can be used to minimize Σ Ui Wi where Ui is a real number urgency and Wi is the waiting time of message i, where Ui is a constant, or a time varying function which is a sequence of constant steps. Such a capability is useful in distributed real-time control systems. This paper demonstrates that a network that implements priority, bus and shift register ring-hardware can create new capabilities for local area networks.

The conditional MOVE processor (CMOVE) has been proposed for replacement of logic table driven sequencers like traffic light controllers and microcomputer I/O processors, in order to take better advantage of hardware-software tradeoffs. Herein the architecture of the CMOVE processor is sketched, and its application to traditional numerical control problems is studied.

This paper presents a formal scheme for addressing base and apex nodes in SW-banyan networks. This scheme is used for routing packets in the network. Packet-switching, in conjunction with the the circuit-switch mode of operation, offers a very flexible and powerful mechanism for interprocess communication in the multiprocessor architectures based on the banyan networks. Finally, a fault-tolerent scheme for re-routing the packets in the network is presented, in case the packet encounters a faulty node in its path.

The architectural characteristics and the implementation techniques of a context addressed segment sequential memory system called CASSM are described. The system provides hardware support for many database management functions. It offers associative and parallel processing capabilities for the efficient retrieval and manipulation of data in large databases. The hardware is designed mainly to support a hierarchical model for database applications but also contains facilities for supporting a wide range of data searches and operations useful for other nonnumeric data processing applications. The software development of the assembly language CASAL and its assembler, the high-level nonprocedural language CASDAL and its compiler, the interface to the CASSM-user interface computer, etc., have been carried out for the system. The hardware design and implementation techniques have been verified using a one-cell prototype system and a simulator designed for testing the system in the multicell environment. The emphasis of this paper is in the detailed description of the hardware features and techniques used in the multicell CASSM system.

Some recent controversy over tightly coupled vs. loosely coupled parallelism may be due to not applying synergism effectively, Herein, parallelism (the execution of a plurality of applications in a plurality of processors) is analyzed from the applications point of view through software, in order to demonstrate that at least five distinct modes of parallelism can be synergistically combined, and some architectures proposed in the literature are surveyed to show embodiments of these modes. This point-of-view may be better in some design studies than that developed from the control structure or from the communication structure of a parallel system, or it may augment those points of view.

A Context Addressed Segment Sequential Memory (CASSM) was built to evaluate several techniques for nonnumeric processing. Herein, it is described from the architectural point-of-view. The basic architecture is introduced, information, data and storage structures are discussed, and the principles of disc searching used by CASSM are discussed.

We propose to use the microcomputer in a network to share I/O resources such as printers and archival memories. A model of a network is developed where computers correspond to edges of a graph. This model reflects the desired characteristics of the microcomputer organization. The advantage of virtual memory in these microcomputers is discussed. Herein, pages in the virtual memory are packets in the network. Packets and requests for packets are generated by page faults and packets are stored and forwarded by hardware like that to manage virtual memory pages. The paper discusses the strategy for a micronetwork and suggests an implementation of the hardware of such a network.

The varistructure architecture gives the user the opportunity to specify the height and width of his primary memory ``at run time.'' This architecture, first proposed in 1973, has now been simplified to make it schedulable, extended to allow SIMD vector-vector operations, and further extended to provide variable structure within a task. Memory is efficiently utilized in that memory bandwidth can be increased for array processing, yet memory space is not wasted during string processing. The fetch-execute cycle operation is analyzed herein, and some tentative results regarding input-output and data communication between processing entities are reported. On the basis of the simplicity of the fetch-execute cycle, there is hope that this architecture may well be the best way to build minicomputers and large computers using a cellular array of microprocessors.

Since conventional computers are straining to handle the increased size and sophistication of non-numeric processing (data management, information retrieval, artificial intelligence), a new class of non-numeric architectures is evolving. The segment sequential architecture is one of these. Further development of this architecture requires new techniques for multiple cell operation and intercell communication to handle control and search operations. This paper describes such techniques for instruction fetching, operand recall, string, set and tree context searching, and pointer transfer. It is expected that combinations of these techniques will appear in future architectures that are needed for non-numeric processing.

A Self Managing Secondary Memory (SMSM) organization is proposed herein, in which hardware directly assists the storage, retrieval and management of arbitrary length records on such devices as fixed head discs or charge coupled devices (CCD's). This paper emphasizes some of the techniques used to implement an SMSM system.

A very simple analog to digital converter and digital to analog converter is described for residue number digital processing. These simple devices make it feasible to replace analog components with comparitively inexpensive digital processors that use residue, or modulus, arithmetic capable of operating at very high speeds. Using off-the-shelf integrated circuits, addition, subtraction or multiplication of about 15 bits of accuracy can easily be done in as little as fifty nanoseconds. Any function using these operations (polynomial expansions, linear filters, fast fourier transforms) can be economically implemented in a pipeline or other structure to get very fast systems. Moreover, a stage in the pipeline can correct for non-linearities in the A/D or D/A converters. The simple devices described herein make residue arithmetic digital processors extremely attractive for use in fast analog systems.

This paper describes an on-going National Science Foundation sponsored project on the design and implementation of an associative memory system for handling large data base information storage and retrieval. The system uses a Clontext Addressed Segment Sequential Memory (CASSM) implemented on a head-per-track disc and an array of non-numeric microprocessors for processing data in parallel and in an associative manner. It provides hardware support to carry out Boolean searches, data base collection, and the execution of high-level data processing functions. It also contains facilities for processing data represented in several data models. The content and context addressing and parallel processing capabilities of CASSM offer potential solutions to several large data base problems. In this paper, the application view of CASSM is emphasized.

A virtual memory system for microprocessors is described. The system is designed to be extensible, to minimize software and execution overhead and to minimize operating system requirements. Specific application of the virtual memory system with the INTEL 8080 microprocessor is given, describing the necessary software constraints and operating system requirements.

A new architecture is proposed for the effective use of program memory in highly parallel applications. This architecture is particularly suited (but not limited) to being built with standard microprocessors. This architecture utilizes a combination of the state switching idea of the SIMD organization and the multiple data stream idea of MIMD organizations. Through scheduling, the program segments are broadcast at the times required to achieve efficient utilization of the parallel processing array. Relationships are developed to determine, for a given application, if this architecture is more cost effective than comparable SIMD and MIMD organizations.

This paper presents the architecture of a context-addressed cellular system for non-numeric information processing, using an inexpensive, large-capacity circulating memory device. The system allows data to be represented in a structure very close to the form as the user perceives it (information structure) and allows the search operations of high level queries to be implemented directly. The information structures currently used in existing information systems are described. Then the architecture of the system as a whole is presented, as well as the implementation of these information structures as basic data types and hardware management of storage allocation and garbage collection.

The architecture of a von-Neumann class computer is considered, in which the user programmer can request, at the beginning of his task, one of many word widths, and one of many memory heights. Several users are able to space share the computer. We call this feature varistructure. The computer is a minimally, yet strongly connected cellular structure consisting of microcomputers, and has the capability of being fail-soft.

A methodology is developed for determining how much parallelism is optimal if a given job stream is to be executed without multiprogramming. Qualitative design tradeoffs are inferred from the cost-performance effect of parallelism on different hardware subsystems. Measures of software parallelism are analytically related to measures of hardware performance. It is shown that an increase in hardware parallelism may be desirable even though it causes an increase in job processing cost and/or a decrease in hardware efficiency.

One possible hardware implementation for the fast Fourier transform (FFT) of 2m samples is to have 2m-1 cells, each of which performs two of the necessary computations during each of the m passes through the processor. But in each of these m passes, each of the 2m-1cells may require a different multiplier coefficient for its computations. The two most obvious solutions are costly. The multipliers could be stored in a central memory and sent to each cell when needed; however, it takes time to transmit them and uses many pins, or interconnections between cells. Alternatively, the multipliers could be stored in a ROM in each cell. This makes each cell bigger, and the cells are no longer identical copies of one another. We consider a third possibility in this note. In each pass the multipliers are generated from the values of the multipliers used in the previous pass. This technique requires no increase in the number of pins per cell and little increase in the time required to perform the Fourier transformation.