Abstract:
The toroidal computer memory system utilizes toroidal memory paths in its chitecture to enable memory locations along those paths to be obtained in a single access, as compared to multiple accesses typically required by conventional linear computer memory. The storage/retrievable media is designed to replicate paths on the surface of a torus. By defining certain parameters and the mathematical properties of these memory paths in the electronics of a controller, points on the memory paths can be accessed from the storage/retrieval media more efficiently than conventional computer memory.

Description:
BACKGROUND OF THE INVENTION 
     The invention disclosed herein was made in the performance of official duties by employees of the Department of the Navy and may be manufactured, used, and licensed by or for the Government for any governmental purpose without payment of royalties. 
    
    
     The invention relates generally to computer memory architecture and specifically to a toroidal computer memory for serial and parallel processors. 
     Conventional computer memory is structurally linear in nature and data is stacked linearly in the memory chips. Thus, access can only occur in a one directional linear manner. The efficiency of this type of memory architecture is limited when used in such applications as matrix and array processing. As a result, software must be used to manipulate accessed data outside memory in order to place it in proper form for processing and updating. In addition, when conventional memory is shared in a multiple processor environment, memory access control acquires additional complexity in order to prevent access collision. 
     OBJECTS OF THE INVENTION 
     The object of a toroidal memory architecture is to alleviate the problems associated with conventional computer memory by providing a storage/retrieval media which can efficiently service associated computational processes with closed paths of memory locations that can be obtained in a single access. Multiple accesses are typically required to obtain these same memory locations when using conventional computer memory. 
     SUMMARY OF THE INVENTION 
     The toroidal computer memory system accomplishes its stated objectives by utilizing selectable memory paths to store and retrieve data. The memory paths are designed to model paths on the surface of a torus. By using the mathematical properties of the toroidal paths, the memory system is configured to store or retrieve data corresponding to points on the memory paths. These paths can be obtained in a single access compared to the multiple accesses typically required by conventional computer memory. Random Access Memory (RAM) chips, multi-port RAM integrated circuits, optical storage devices, or specially designed chips can be used as the storage/retrieval media for the toroidal computer memory system. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a conceptual depiction of a toroidal memory with associated toroidal and memory paths. 
     FIG. 2 is a simple configuration of the components of a toroidal computer memory system using toroidal and memory paths as depicted in FIG. 1. 
     FIG. 3 is a rectangular representation of the set of memory words corresponding to the toroidal memory system in FIG. 2. The arrows indicate the edges of the rectangle which must be identified by Φ 2  to produce a torus. 
     FIG. 4 shows a few of the specific memory paths capable of being selected in the simple toroidal memory system of FIG. 2. 
     FIG. 5 is a process flow diagram showing how the controller functions process the path requests to access the memory paths within the system, as exemplified in FIG. 4. 
     FIG. 6 is a logic flow diagram showing the computational processes of the address pair generator of FIG. 5. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The toroidal computer memory overcomes certain inherent limitations of conventional computer memory by using the properties of a torus to design a memory architecture which can read from or write to memory path locations in a single access as compared to the multiple accesses typically required to access these same memory locations by conventional memory. 
     The toroidal memory system is designed by defining the following concepts. Each memory word corresponds to a tuple in the set M=N 1  ×N 2  where N i={  0,1,2, . . . ,n i  }, i=1,2. The symbol, l, represents the wordlength of each memory word. For example, if l=1, the wordlength corresponds to one bit and the system can be programmed for bit level processing. If l&gt;1, the system can be programmed for word level processing. As indicated in FIG. 3, a torus is obtained by identifying the opposite edges of the rectangle R={(x,y)R 2 | 0≦×≦n 1  +1, 0≦y≦n 2  +1}, where R is the set of real numbers. If Φ=Φ 2  ·Φ 1 , where Φ 1  :M→R is an imbedding such that (i,j) |→(i,j) and Φ 2  :R→T is the identification cap, then the associated toroidal memory is defined by the triple (M,R,Φ ). Thus, each memory word in M is associated with a point on the surface of the torus. 
     A toroidal path is a simple, not necessarily closed, curve on a torus which originates at the origin of rectangle R. A toroidal memory with path accessibility is one in which certain paths contain required collections of retrievable/updatable memory words as subsets. Such collections are called memory paths. If m/n, where 0≦m&lt;n 2  and 0&lt;n&lt;n 1 , is the slope of a toroidal path in R which contains a memory path, then K m ,n and P m ,n will be the toroidal path and its associated memory path. A conceptual depiction of a toroidal path 10 and its associated memory path 12 is shown in FIG. 1. 
     The following theorems describe the key features of toroidal and memory paths. These theorems are paramount to the design of the toroidal memory system and are embodied within the electronics of the memory controller. Let (a,b) denote the greatest common divisor of a and b, X denote the set of all i coordinates in P m ,n, k be a non-negative integer, k max  a maximum permitted value for k, and n i  &#39;=n i+  1, i=1,2. 
     
         ______________________________________Theorem 1. P.sub.m,n = {(mod (kn,n.sub.1 &#39;), mod (km,n.sub.2 &#39;))      |      0 ≦ k ≦ k.sub.max }Theorem 2. If (n.sub.1 &#39;,n) = 1 and k.sub.max ≧ n.sub.1, then X =      N.sub.1.Theorem 3. Let (n.sub.1 &#39;,n.sub.2 &#39;) = r, where n.sub.1 &#39; = ar, n.sub.2 &#39;      = br,      (b,m) = q, and b = cq. If (n.sub.1 &#39;,n) = 1,      then K.sub.m,n is closed for k.sub.max = (cn.sub.1 &#39; -______________________________________      1). 
    
     It is important to note for design purposes, that if n 1  &#39;=n 2  &#39; is chosen to be a prime number, then (n 1  &#39;,n)=1 for all n≦n 1 , c=1, and k max  =n 1 . 
     The toroidal computer memory can be constructed using the Random Access Memory (RAM) chip as the basic building block for the system. The memory system utilizes n 1  +1 groups of l independently addressable RAM circuits and n 2  +1 address locations within each RAM circuit, where the RAM group IDs are in one-to-one correspondence with N 1  and the RAM addresses are in one-to-one correspondence with N 2 , so that (RAM group ID, RAM address) is an element of M. The associated toroidal memory (M,R, Φ ) with memory path access can be obtained by identifying the opposite edges of R and using Theorem 1 as a memory path location address pair generator, where RAM group ID=mod(kn, n 1  &#39;) and RAM address=mod(km, n 2  &#39;). Thus, for each k, 0≦k≦k max , an address pair (RAM group ID, RAM address) is generated for a memory location in memory path P m ,n. The rule, RAM identifier=l * RAM group ID+(J-1), where 1≦J≦l is used to control the addressing within a RAM group and insures that identical RAM addresses are received by each RAM circuit within the group. 
     An example of a simple toroidal memory system is shown in FIG. 2. This example uses five independently addressable RAM circuits, five consecutive RAM addresses within each circuit, a five-bit data bus, and a wordlength, l, of one (bit level processing). The group/address controller contains functions which control the memory access of the system. Theorem 1 above is used as a RAM group ID and address pair generator function. Thus, for a given k, m, and n, the RAM group ID=mod(kn, n 1  &#39;) and the RAM address=mod(km, n 2  &#39;). In this particular example, the RAM identifier will be identical to the RAM group ID since l=1. Additionally, an origin shift parameter, y o , and origin controller function can be used to shift the origin to a desired location. Otherwise, the origin will always be at zero. Use of the origin shifter will provide additional autonomy to the toroidal memory system. In the examples below, y o  =0. Y o  is, however, shown explicitly on pertinent figures. Also, in general, since there are typically many more than N 2  RAM addresses available in each RAM circuit, many toroidal memory structures can be placed in such an architectural configuration by layering them consecutively. Thus, an OFFSET parameter can be used by the controller to access a particular toroidal memory structure contained within the configuration. 
     The set of all memory locations contained within the simple memory system of FIG. 2 is shown in FIG. 3. The RAM group ID represents the i axis and the RAM address represents the j axis. The memory location pair (RAM group ID, RAM address) is a point of M=N 1  ×N 2 , where N 1  =N 2  {0,1,2,3,4}. P m ,n n memory path requests, i.e. 3-tuples of the form (m,n,k max ), are sent to the controller for use in path access. The controller functions process the path requests to access the memory paths within the system as shown in the process flow diagram of FIG. 5. 
     Referring to FIG. 5, Request contains encoded information concerning m, n, y o , and whether to &#34;read&#34; or &#34;write&#34;. The former three will determine the slope of the memory path and the first memory location. Also, OFFSET and l are provided to control RAM group ID addressing. DECODE then decodes the request. If the request is a &#34;write data&#34;, then LATCH, as used here, means that the data is held here for l-bit partitioning by WORD PARTITION. If the request is &#34;read&#34;, WORD PARTITION associates each l bits to be read with the appropriate 0≦k≦k max . If the request is &#34;write&#34;, WORD PARTITION breaks the data word into its l-bit subwords and associates the appropriate 0≦k≦k max  with each subword. (Note that kmax is a parameter fixed by the electronics). 
     The address pair generator uses the memory path slope in conjunction with k, y o , l, and OFFSET to determine the RAM group ID address and the RAM address for each group. FIG. 6 shows the processes used to calculate each address. If the request was &#34;write&#34;, the address pair generator associates each l bit of write data with an address pair (RAM identifier, RAM address). If the request was &#34;read&#34;, the address pair generator creates address pairs for each l bit of read data. The information is then sent to the ROUTER. If the request is &#34;read&#34;, then ROUTER sends the read request for each l bit to the appropriate RAM identifier and provides each RAM circuit with the required RAM address. If the request is &#34;write&#34;, then ROUTER sends write request with each l bit of data to the appropriate RAM identifier and provides each RAM circuit with the required RAM address. 
     FIG. 4 shows several examples of P m ,n &#39;s accessed from the system in FIG. 2. FIG. 4A shows P 2 ,3 with a path slope of 2/3. Here, since five addresses in each of the five independently addressable RAM circuits are used, n 1  &#39;=n 2  &#39;=5, which is a prime number. Therefore, k max  =4 and all K m ,n  P m ,n are closed (Theorem 3). The toroidal path K 2 ,3 begins at the origin, increases with a slope of 2/3, and closes upon itself at the origin after spiraling around the torus twice latitudinally and three times longitudinally. The address pairs corresponding to the set of memory locations which comprise the memory path P 2 ,3 associated with K 3  are given by P 2 ,3 ={(mod(3*k,5), mod(2*k,5))|0≦k≦4}, and are evaluated in Table 1. 
     
                       TABLE 1______________________________________P.sub.2,3 Memory Locations RAM Group ID =  RAM address =k     mod(3*k,5)      mod(2*k,5)   P.sub.2,3______________________________________0     0               0            (0,0)1     3               0            (3,2)2     1               4            (1,4)3     4               1            (4,1)4     2               3            (2,3)______________________________________ 
    
     Note that the modular arithmetic functions in the controller wrap the path around the torus to access all the other points shown in FIG. 4A. FIGS. 4B-D are representations of P 3 ,2, P 1 ,2, and P 0 ,1 with path slopes of 3/2, 1/2, and 0 respectively. These paths are generated in the same way as P 2 ,3, shown in FIG. 4A. FIG. 4D shows P 0 ,1 with a path slope of zero. Thus, P 0 ,1 is identical to a word extracted from conventional RAM memory with address of zero. By continuously shifting the origin from one RAM address to the next via the origin shift parameter, the toroidal memory replicates the structure of conventional linear RAM memory. The data contained in each P m ,n shown above is retrievable or updatable in a single access and multi-port RAM devices may be used to service multiple processors in a shared memory environment. 
     The example shown in FIG. 2 is merely one representative embodiment of a toroidal computer memory system and general RAM based toroidal memory systems can utilize as many RAM circuits as is feasible for the associated data bus of the processor(s). The memory system can also be constructed using multi-port RAM integrated circuits, optical storage devices, or specially designed chips in place of the conventional RAM devices.