Grid Processing Electronic Memory

Abstract

The invention adds execution units to a conventional memory bank, and connects memory units in two dimensions in a grid. Highly enabled execution units occur in every row in the grid; individual grid units are also enabled to varying degrees with reduced execution capabilities. The multiple execution units follow a single instruction. Row-aligned or vector operations, and cross-row or vector-internal operations, can be performed simultaneously without crossing the front-side bus. Constant-time list copying and read-write array accessing, and linear- and sublinear-time sorting are possible as a result. Extended content-addressing is introduced. The running times of matrix multiplication and Gaussian elimination are improved by factors of the size of the matrix.

What is claimed is: 
     
         1 . An electronic memory device, comprising:
 a plurality of memory cells configured in a grid having a plurality of rows and columns;   a plurality of horizontal pathways, each connecting between neighboring individual memory cells in said plurality of rows respectively; and   a plurality of vertical pathways, each connecting between neighboring individual memory cells in said plurality of columns respectively,   wherein each individual of said plurality of memory cells is configured to function as a storage unit or a computation unit or both, and computation operations are configured to be performed in situ said plurality of memory cells.   
     
     
         2 . The electronic memory device of  claim 1 , wherein multiple simultaneous computation operations are configured to be performed in situ said plurality of memory cells. 
     
     
         3 . The electronic memory device of  claim 1 , wherein a row of said memory cells are configured to be computation units, and a primary computation unit is connected to said row via a horizontal pathway. 
     
     
         4 . The electronic memory device of  claim 1 , wherein a column of said memory cells are configured to be computation units, and a primary computation unit is connected to said column via a vertical pathway. 
     
     
         5 . The electronic memory device of  claim 1 , wherein said plurality of horizontal or vertical pathways are configured in two logical dimensions along which contents of memory cells are configured to be transferred. 
     
     
         6 . The electronic memory device of  claim 5 , wherein said horizontal pathways connecting computation units are configured to transfer data. 
     
     
         7 . The electronic memory device of  claim 1 , wherein said computation operations include Unary operations, Binary operations in 9 configurations given by the square of the set {column list, row list, register}, Ternary operations in the  27  configurations given by the cube of the set {column list, row list, register}, Address copy, Multiple result columns, Offset read, Offset write, Addressable content operations with equality criteria, Addressable content operations with inequality criteria, Producing the indices of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing the values that are matched in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing Boolean values indicating the outcome of the test in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Counting the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Access to the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) by indices counted among the results only, Shifting or collating the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) to remove entries for failed outcomes, Direct folding, Deferred folding, Transpose, Reverse transpose, Offset transpose, Reverse offset transpose, Word shift, Concurrent bubble sort, Concurrent insertion sort, Concurrent merge sort, and/or Cartesian sort, or the combination thereof. 
     
     
         8 . The electronic memory device of  claim 1 , wherein a plurality of neighboring columns of said memory cells are configured to function as computation units, and a plurality of neighboring rows of said memory cells are configured to function as computation units, and a single computation operation is dividedly configured to be conducted simultaneously between said neighboring columns of said memory cells or to be conducted simultaneously between said neighboring rows of said memory cells. 
     
     
         9 . The electronic memory device of  claim 8 , wherein said single computation operation is related to Unary operations, Binary operations in 9 configurations given by the square of the set {column list, row list, register}, Ternary operations in the  27  configurations given by the cube of the set {column list, row list, register}, Address copy, Multiple result columns, Offset read, Offset write, Addressable content operations with equality criteria, Addressable content operations with inequality criteria, Producing the indices of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing the values that are matched in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing Boolean values indicating the outcome of the test in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Counting the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Access to the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) by indices counted among the results only, Shifting or collating the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) to remove entries for failed outcomes, Direct folding, Deferred folding, Transpose, Reverse transpose, Offset transpose, Reverse offset transpose, Word shift, Concurrent bubble sort, Concurrent insertion sort, Concurrent merge sort, and/or Cartesian sort, or the combination thereof. 
     
     
         10 . The electronic memory device of  claim 1 , further comprising:
 an independent instruction counter configured to be located in one of said memory cells or a row of said memory cells or a column of said memory cells, wherein said independent instruction counter contains addresses of a computation operation.   
     
     
         11 . The electronic memory device of  claim 1 , further comprising:
 a set of unique keys configured to be located in one of said memory cells or a row of said memory cells or a column of said memory cells, wherein said set of unique keys link to a set of associative containers.   
     
     
         12 . A method for conducting computation operations in memory bank, comprising the steps of:
 constructing a memory bank having a plurality of memory cells configured in a grid having a plurality of rows and columns;   constructing a plurality of horizontal pathways on said memory bank, each connecting between neighboring individual memory cells in said plurality of rows respectively; and   constructing a plurality of vertical pathways on said memory bank, each connecting between neighboring individual memory cells in said plurality of columns respectively,   wherein each individual of said plurality of memory cells is configured to function as a storage unit or a computation unit or both, and computation operations are configured to be performed in situ said plurality of memory cells.   
     
     
         13 . The method for conducting computation operations in memory bank of  claim 11 , wherein multiple simultaneous computation operations are configured to be performed in situ said plurality of memory cells. 
     
     
         14 . The method for conducting computation operations in memory bank of  claim 11 , wherein a row of said memory cells are configured to be computation units, and a primary computation unit is connected to said row via a horizontal pathway. 
     
     
         15 . The method for conducting computation operations in memory bank of  claim 11 , wherein a column of said memory cells are configured to be computation units, and a primary computation unit is connected to said column via a vertical pathway. 
     
     
         16 . The method for conducting computation operations in memory bank of  claim 11 , wherein said plurality of horizontal or vertical pathways are configured in two logical dimensions along which contents of memory cells are configured to be transferred. 
     
     
         17 . The method for conducting computation operations in memory bank of  claim 15 , wherein said horizontal pathways connecting computation units are configured to transfer data. 
     
     
         18 . The method for conducting computation operations in memory bank of  claim 11 , wherein said computation operations include Unary operations, Binary operations in 9 configurations given by the square of the set {column list, row list, register}, Ternary operations in the  27  configurations given by the cube of the set {column list, row list, register}, Address copy, Multiple result columns, Offset read, Offset write, Addressable content operations with equality criteria, Addressable content operations with inequality criteria, Producing the indices of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing the values that are matched in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing Boolean values indicating the outcome of the test in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Counting the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Access to the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) by indices counted among the results only, Shifting or collating the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) to remove entries for failed outcomes, Direct folding, Deferred folding, Transpose, Reverse transpose, Offset transpose, Reverse offset transpose, Word shift, Concurrent bubble sort, Concurrent insertion sort, Concurrent merge sort, and/or Cartesian sort, or the combination thereof. 
     
     
         19 . The method for conducting computation operations in memory bank of  claim 11 , wherein a plurality of neighboring columns of said memory cells are configured to function as computation units, and a plurality of neighboring rows of said memory cells are configured to function as computation units, and a single computation operation is dividedly configured to be conducted simultaneously between said neighboring columns of said memory cells or to be conducted simultaneously between said neighboring rows of said memory cells. 
     
     
         20 . The method for conducting computation operations in memory bank of  claim 19 , wherein said single computation operation is related to Unary operations, Binary operations in 9 configurations given by the square of the set {column list, row list, register}, Ternary operations in the  27  configurations given by the cube of the set {column list, row list, register}, Address copy, Multiple result columns, Offset read, Offset write, Addressable content operations with equality criteria, Addressable content operations with inequality criteria, Producing the indices of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing the values that are matched in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Producing Boolean values indicating the outcome of the test in (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Counting the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria), Access to the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) by indices counted among the results only, Shifting or collating the results of (Addressable content operations with equality criteria) and (Addressable content operations with inequality criteria) to remove entries for failed outcomes, Direct folding, Deferred folding, Transpose, Reverse transpose, Offset transpose, Reverse offset transpose, Word shift, Concurrent bubble sort, Concurrent insertion sort, Concurrent merge sort, and/or Cartesian sort, or the combination thereof. 
     
     
         21 . The method for conducting computation operations in memory bank of  claim 11 , further comprising:
 an independent instruction counter configured to be located in one of said memory cells or a row of said memory cells or a column of said memory cells, wherein said independent instruction counter contains instructions for a computation operation.   
     
     
         22 . The method for conducting computation operations in memory bank of  claim 11 , further comprising:
 a set of unique keys configured to be located in one of said memory cells or a row of said memory cells or a column of said memory cells, wherein said set of unique keys link to a set of associative containers.