Algorithms for Parallel-Search Memories

ABSTRACT

The underlying logical structure of parallel-search memories is described; the characteristic operation of three major types is displayed in the execution of searches based on equality; and algorithms are presented for searches based on other specifications including maximum, miniTnum, greater than, less than, nearest to, between limits, and ordering (sorting). It is shown that there is a hierarchy of dependency among these algorithms, that they appear in pairs with each member of a pair belonging to one or the other of two distinct classes, and that every type of search can be executed within each class.

REFERENCES

• 1: McDERMID, W L., AND PETERSEN, H. E. A magnetic associative memory system. IBM J. Res. Dev. ~ (Jan. 1961), 59.
• 2: SLADE, A. E., AND MCMA~ON, H.O. A cryotron catalog memory system Proc EJCC (Dec. 1956), 115-120.
• 3: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 4: KISEDA, J R, PETERSEN, i. n., SEELBACH, W. C , AND TEI~, M. A magnetic associative memory. IBM d. Res. Dev. 5 (Apr. 1961), 106.
• 5: The incorporation of a plurality counter in each column was communicated to the author by R. I. Roth, IBM Thomas J. Watson Research Center, who has designed a memory to operate according to Program 8.
• 6: SEEBER, R. R., AND LINDqUIST, A B. Associative memory with ordered retrieval. 1BM J. ICes. Dev. 6 (Jan. 1962), 126 This article gives a detaded description of the memory system whose princxple of operation has been summarized in Program 12

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance, Theory