JP2018139017A - Memory type processor, apparatus including memory type processor, and method of using the same. - Google Patents

Abstract

The present invention provides a memory processor, a device including the memory processor, and a method of using the memory processor that reduce circuit space for parallel operation and reduce power consumption. A 1-bit computing unit 105 provided in a lower part of a data table is configured to perform logical storage 116, logical product 112, logical sum 113, logical data 116, logical data 112, logical data 113, logical data 116, logical data 112, logical sum 113, A logical negation (NOT) 114, an exclusive OR 115, a full addition 211, other optional functions, and a calculation condition 111 specified by the arithmetic unit of the combination thereof can be executed in parallel for all records. Further, a calculation result output 106 function such as a priority order output circuit (priority address encoder output circuit) 214 is provided to output the calculation result of the 1-bit calculator 105. [Selection] Figure 2

Description

The present invention relates to a memory type processor, an apparatus including the memory type processor, and a method of using the same.

In a current computer, a sequential processing type processor such as a CPU or GPU performs all information processing, so the CPU has to take care of processing that the CPU is good at and is not good at.
In considering the use of big data essentially, it is necessary to clarify two major problems of the current Neumann computer.

The first problem is the Neumann bath bottleneck.
For the CPU and GPU, the data in the memory is like a playing card that is turned upside down, and there is no other way than searching for information by turning (accessing) each piece (one address, one address).
When the CPU or GPU performs information processing that sequentially searches for information in the memory and finds specific information, the amount of information processing becomes extremely large and the waiting time increases.
In the information search process, the information on the memory needs to be accessed repeatedly over and over, so that the influence of the bus bottleneck is greater than other information processing.
This is the fate of the Neumann computer and the information search bus bottleneck.

Therefore, when performing information processing to find specific information, there is no method other than devising and using various utilization techniques (software algorithms) in order to reduce the burden on the CPU and GPU and the burden on information processing.
There are countless algorithms such as hash tables, indexes, tree structures, binary search, clustering, and combinations thereof as typical algorithms used to search for information.
These algorithms require metadata (structured data) for each algorithm.
These utilization techniques (software algorithms and metadata) are none other than utilization techniques for utilizing CPUs and GPUs born with fate, CPU burden, means for reducing the number of information processing, and fate.

In other words, all of the above algorithms sort out in advance where and what information is in the memory, create headings and their routes so that the CPU can easily find information, arrange data in order from the smallest, etc. Is the method.
Although such an algorithm eliminates the burden on the CPU and GPU at the time of search, complicated information processing is required for pre-processing and post-processing. For example, information such as data correction, insertion, and deletion Pre-processing and post-processing information processing for these algorithms is required, such as rearrangement of the metadata array created by the algorithm used every time data is modified, added, or deleted, and changing the order. ing.

Software algorithms and metadata such as those described above need to be selected according to the type and scale of the database, and an optimization system needs to be constructed. Including information processing, there is a big problem that only an expert with knowledge and experience can do it.

The second problem is an arithmetic unit of CPU or GPU.
The ALU (Arithmetic and Logic Unit), which is the heart of the CPU and GPU, has a function to perform both arithmetic (arithmetic) operations and logical (Boolean) operations based on Boolean algebra. Since the width (for example, 32 bits or 64 bits) needs to be calculated in parallel, the circuit scale of one unit must be increased.
Therefore, increasing the parallelism increases the chip size and the power consumption.
A solution to this problem has not been found even today, when the limits of miniaturization technology are approaching.

The present invention realizes various operations such as a process of searching for target information in a memory, a comparison operation, a count operation, and an arithmetic operation at a high speed only by incorporating a very small amount (space-saving) circuit in a general memory. The purpose is to realize a new concept information processing memory, that is, a memory-type processor, equipped with a parallel arithmetic element whose unit circuit scale is extremely small.

Patent No. 4588114 of the invention of the present inventor A memory having an information narrowing detection function is a memory that is good at logical product operations such as pattern matching.
PCT / JP2013 / 059260 memory with set operation function expands and expands the concept of memory with information narrowing detection function, and can perform logical product operation, logical sum operation, logical negation operation, etc. It is memory that can.

Japanese Patent Application No. 10-232531, a memory with an arithmetic function is intended to improve chip efficiency by providing an arithmetic circuit for each block as shown in the figure.

Japanese Patent Application No. 63-128849, the learning type character search device and the control method of the same device realize the search of text data, and the configuration is similar to the information processing of the patent of this application, but the content of the information processing is text However, the present invention is not limited to advanced and versatile information processing involving various calculations of data values as in the present invention.
Further, as shown in FIG. 2 of the control type document of the learning type character search device and the same device, the arithmetic unit uses an ALU, and in the configuration in which the ALUs are simply arranged as in this example, the degree of parallelism is high. As described in the effect of the invention, it can be presumed that “a considerable effect can be expected in personal use”.
What is important is to improve the degree of parallelism and sophisticate the contents of operations and overcome conflicting issues.

In addition, Japanese Patent Application No. 2013-264773 of the invention by the inventor of the present application, a memory having an information search function, a method of using the same, an apparatus, and an information processing method did not specifically show an arithmetic circuit, and the contents of the calculation It was limited to index searches, data value matches, and range searches.
It is an object of the present invention to provide a memory type processor using an arithmetic circuit most suitable for realizing various data operations in parallel without being limited to a process of searching for information such as a search.

Japanese Patent No. 4588114 PCT / JP2013 / 059260 Japanese Patent Application No. 10-232531 Japanese Patent Application No. 2013-264863 Japanese Patent Application No. 63-128849

The present invention drastically eliminates problems such as searching and collating information for which the effects of Neumann bus bottlenecks are the most problematic, and proposes an arithmetic unit suitable for parallel arithmetic and its usage. It is intended to drastically solve many of the problems of information processing centered on sequential processing processors such as CPUs and GPUs.
In other words, the calculation of a large amount of data is not left to the CPU or GPU alone, but the calculation that can be realized in the memory is performed by the memory, so that the load on the CPU and GPU is heavy, complicated, and a non-specialist can be put out. It is to realize a memory device having an information calculation function based on a completely new concept of information processing that is ideal for information processing in a big data society and can simplify power processing and reduce power consumption.

Specifically, a 1-bit arithmetic unit (logical arithmetic unit and four arithmetic units) capable of various information processing in combination with a memory cell reduces the circuit space for parallel arithmetic and reduces power consumption.

According to a first aspect of the present invention, a multi-bit memory cell capable of storing data input from an external input function, and the memory cell data are read for each bit cell and an operation is performed, and the operation result is stored in the memory cell for each bit. A 1-bit operation function that enables writing is set as one record, and a large number of the records are arranged in parallel so that the memory cells of each of the many bits of all records can be selected in parallel, and operation conditions are designated in parallel. Calculation condition specification function to
An external output function for outputting the calculation result of the record to the outside;
It is characterized by comprising.

In claim 2, the 1-bit calculation function is:
(1) logical product operation (2) logical sum operation and (3) logical negation operation (4) exclusive OR operation (5) half addition operation (6) full addition operation (7) operation storage (8) or more (1) To (7), any one of the operations is executed.

In claim 3, the external input function is:
A function of performing matrix transformation on the data to be calculated from outside and writing the data to be calculated is provided.

In claim 4, the external output function is:
(1) Output the addresses of the records in order of priority (2) Divide the record into several parts and output the divided records in order of priority (3) Whether any of the records has a calculation result (4) Output all the records in parallel (5) or more (1) to (4) any combination output function is provided.

According to a fifth aspect of the present invention, there is provided a function of transferring the calculation target data to the other record.

The present invention is characterized in that it is incorporated in a circuit of a CPU and other functions.

The present invention is characterized in that it is implemented by FPGA.

An apparatus including the memory type processor according to claim 1.

According to a ninth aspect of the present invention, in the method of using the memory type processor according to the first aspect, both the data to be calculated and the work area data for temporarily saving the calculation result are allocated to the address. By repeating the 1-bit calculation function using data,
(1) All-record parallel index search operation of the calculation target data (2) All-record parallel comparison (match, large, small, range, maximum / minimum) calculation of the calculation target data (3) All of the calculation target data Record parallel count (up / down) operation (4) All-record parallel addition / subtraction operation of the calculation target data (5) All-record parallel multiplication / division calculation of the calculation target data (6) All-record parallel of the calculation target data Encryption of plaintext and plaintext decryption operation of ciphertext (7) All-record parallel matrix conversion operation of the operation target data (8) Combination operation of all-record parallel data creation operation of the operation target data (9) or more Any one of the above operations is performed.

According to a tenth aspect of the present invention, in the method of using the memory-type processor according to the first aspect, it is determined whether or not there is a remaining record as a result of the calculation, and a calculation conditional expression is given based on the determination result.

According to the eleventh aspect of the present invention, in the method of using the memory type processor according to the first aspect, data of memory cells of a plurality of records are allocated and used as a set of data among the records arranged in large numbers.

According to a twelfth aspect of the present invention, the memory-type processor is used for (1) serial, parallel, or series-parallel connection, or (2) a hierarchical connection or more, or both connections.

FIG. 1 is a configuration example of a general memory. FIG. 2 is a configuration example of a memory type processor. FIG. 3 is a circuit configuration (example) of a 1-bit logic (Boolean) arithmetic unit of the memory type processor. (Example 1) FIG. 4 is an explanatory diagram of an index search calculation method (example) of a memory type processor using a 1-bit logic (Boolean) calculator. (Example 2) FIG. 5 is an explanatory diagram of a data comparison arithmetic expression (example) of a memory type processor using a 1-bit logic (Boolean) arithmetic unit. FIG. 6 is an explanatory diagram of a data match comparison calculation (match search) method (example) of a memory type processor using a 1-bit logic (Boolean) calculator. Example 3 FIG. 7 is an explanatory diagram of a data size comparison operation (above, less than search) method (example) of a memory type processor using a 1-bit logic (Boolean) arithmetic unit. (Example 4) FIG. 8 is an explanatory diagram of a maximum / minimum comparison operation (maximum / minimum search) method (example) of a memory type processor using a 1-bit logic (Boolean) arithmetic unit. (Example 5) FIG. 9 is an explanatory diagram of address allocation (example) of the data count calculation method of the memory type processor by the 1-bit logic (Boolean) arithmetic unit. FIG. 10 is an explanatory diagram of an addition count calculation method (example) of a memory type processor using a 1-bit logic (Boolean) calculator. (Example 6) FIG. 11 is an explanatory diagram of a subtraction count calculation method (example) of a memory type processor using a 1-bit logic (Boolean) arithmetic unit. (Example 7) FIG. 12 is an explanatory diagram of a full addition operation method (example) of a memory type processor by a 1-bit logic (Boolean) arithmetic unit. (Example 8) FIG. 13 is an explanatory diagram of a multiplication operation method (example) of a memory type processor using a 1-bit logic (Boolean) arithmetic unit. Example 9 FIG. 14 is a circuit configuration (example) of a 1-bit four arithmetic unit of a memory type processor. (Example 10) FIG. 15 is an explanatory diagram of a multi-bit parallel arithmetic operation method (example) by a memory type processor. (Example 11) FIG. 16 is a circuit configuration (example) of an arithmetic unit having a data shift function of a memory type processor. (Example 12) FIG. 17 is an explanatory diagram (1) of the data matrix conversion method (example) by the memory-type processor. (Example 13) FIG. 18 is an explanatory diagram (2) of the data matrix conversion method (example) by the memory type processor. FIG. 19 shows an example of series-parallel connection of memory type processors. FIG. 20 shows an example of hierarchical connection of memory type processors. FIG. 21 is an example A of a feature database by a memory type processor. (Example 14) FIG. 22 is an example B of the feature database by the memory type processor. (Example 15) FIG. 23 is an explanatory diagram of a parallel data creation method (example) by a memory type processor. (Example 16)

FIG. 1 is a configuration diagram of a general memory.
The memory 100 in FIG. 1 does not include functional circuits such as an address decoder and a data bus. The memory 100 has a configuration in which information data can be freely written to and read from the memory. One word has an n-bit width 103 and an N address 104. The memory cell 102 is made up of N × n bit cells, and generally addresses from 1 to N can be selected and designated from the outside by means such as an address decoder.
Information processing by the current CPU is that the data width 103 of the memory 100 is a constant data width such as 8 bits, 16 bits, 32 bits, and the address space of the given memory such as 1M address or 1G address is used when searching for information data. The CPU sequentially accesses the address, reads data, and performs sequential processing.
The information processing according to the present invention is based on the idea of reversing the concept of data width and address in the above general memory structure and database table structure, and is based on parallel operation in 1-bit units.

FIG. 2 shows an example of the configuration of a memory-type processor. The memory cell has a number of bits that can store data input from an external input function, and the memory cell data is read for each 1-bit cell, and the calculation is performed. A 1-bit operation function that enables writing of a result to the memory cell every 1 bit is made one record, and a large number of the records are arranged in parallel, so that the memory cells of the multiple bits of all records can be selected in parallel. And a memory type processor comprising a calculation condition specifying function for specifying calculation conditions in parallel and an external output function for outputting the calculation result of the record to the outside. explain.

As in FIG. 1, functional circuits such as an address decoder and a data bus are omitted in FIG. 2, and information data can be freely written to and read from the memory cells 102 of the memory type processor 101.

The width 103 of 1 word n bit in the normal memory corresponds to the number of records (n) in the database in the case of the memory type processor 101, and data of 1 record is arranged in a column, and N of the address 104 is a field of 1 record. It is easy to understand if it is considered as a structure corresponding to the data length.
That is, the memory unit (database unit) of the memory-type processor 101 is a data table of n records in which one record has a field data length of N bits.

The 1-bit computing unit 105 provided in the lower part of the data table performs logical storage 116, logical product 112, logical sum 113, logical negation (NOT) for each bit cell data of the storage cell 102 at the address 104 selected and designated 110. ) 114, exclusive OR 115, full addition 211, other optional functions, and a calculation condition 111 specified by the combination computing unit, all the records can be operated in parallel.
Details will be described later.

Further, a calculation result output 106 function such as a priority order output circuit (priority address encoder output circuit) 214 is provided to output the calculation result of the 1-bit calculator 105.
As will be described later, since most of the memory is the memory cell itself, and only a part of the memory cell has the 1-bit computing unit 105 and the computation result output 106 function, it is possible to incorporate these functions in a general memory in a space-saving manner. There can be a large-capacity memory optimal for a database.

As will be described in detail later, the 1-bit calculation function 105 is roughly divided into two types: a 1-bit logic (Boolean) calculation function 123 and a 1-bit four-rule (numerical) calculation function 124.
The logical operation may be true or false, or 1 bit of 0 or 1, whereas the arithmetic operation requires 2 bits of the operation result and carry.
First, the 1-bit logic (Boolean) operation function 123 will be described.

FIG. 3 shows an example of the circuit configuration of the 1-bit logic (Boolean) operation function of the memory-type processor. The 1-bit logic (Boolean) operation for calculating the data of the 1-bit memory storage cell 102 selected by the address 104 of the memory-type processor 101. The circuit of the device 123 and the contents of the calculation will be described.

In this example, when the switch 201 is switched to the 1 position, a 1-bit logical (Boolean) operation 123 can be realized.
As shown in the figure, the circuit configuration is a very simple configuration including a logical product 112, a logical sum 113, an exclusive logical sum 115, a logical negation 114, a flip-flop (FF) 202, and a selection circuit 203.
Since the exclusive OR 115 can be calculated by a combination of the logical product 112, the logical sum 113, and the logical negation 114, it is not always necessary. However, the exclusive OR 115 may be incorporated when the usage frequency is high, such as four arithmetic operations described later.

The exclusive OR 115 can be used for encryption.
When plaintext data is encrypted, the plaintext data is encrypted by performing an exclusive OR operation with the encrypted data, and the encrypted ciphertext data can be plainly obtained by performing an exclusive OR operation with the encrypted data. It is well known.
Therefore, the exclusive OR 115 of the 1-bit Boolean calculator 105 can encrypt and decrypt a large amount of plaintext data at a very high speed.

In this circuit, 1-bit data from the memory storage cell 102 selected by the address 104 can be selected by the selection circuit 203 as positive logic or negative logic (logic negation 114).
Similarly, the result output 205 of the flip-flop 202 can be selected from positive logic or negative logic (logic negation 114).

The contents that can be calculated will be described below.
First, positive or negative logic data read from the memory can be directly substituted (stored) in the flip-flop 202 as memory data 204.
Secondly, the result output 205 of the flip-flop 202 as the operation result can be directly substituted (stored) in the flip-flop 202 again.

Third, the positive logic or negative logic memory data 204 and the result 107 of the positive logic or negative logic output 205 of the flip-flop 202 which is the operation result 107 are ANDed. Any one of the logical sum 113 and the exclusive logical sum 115 can be executed, and the result can be substituted (stored) in the flip-flop 202.
The above-described calculation can be specified in parallel for all records, and the calculation condition specifying function 111 is provided.

The 1-bit logic (Boolean) operation result can be stored in the memory cell 102 selected by the address 104 by setting the switch 201 to the 3 position.

Since the 1-bit logical operation result is a normal winning remaining record and the number of records is greatly narrowed down, the record address is output to the outside for each record from the operation result output 106 function such as the priority address encoder output circuit. The number of output pins of the processor 101 chip can be minimized.
Details will be described later.

As described in the background art, for example, the ALU 210 needs to calculate two sets of 32-bit data at a time, so the circuit scale of one unit is inevitably large. However, the 1-bit logic (Boolean) operation of this configuration is necessary. Since the unit 105 can be realized with a circuit scale of about 150 transistors and several hundred transistors including the operation result output 106, it is optimal as a parallel processing operation unit.
A 1-bit four arithmetic (numerical value) calculation function 124, which will be described later, is also an extremely space-saving calculation circuit.

The following introduces the fact that the above-mentioned space-saving calculation function can realize various operations at ultra-high speed.

FIG. 4 is an example of a memory type processor index search calculation method using a 1-bit logic (Boolean) calculator.
The index search operation has various uses such as Internet search, patent search, and full-text search.
There are two types of normal character string information: a search using only a keyword, and a method of specifying conditions for both the keyword and the arithmetic expression.

In this example, as a search for patent documents, a key index such as “information processing”, “information search”, “CPU” and the like and a logical product 112, a logical sum 113, and a logical negation 114 can be calculated. By providing both key vocabulary and arithmetic expressions, the records are narrowed down, and if there are documents (records) that match these keywords and logical operation conditions, or if there are any documents (records) An index search for determining

Hereinafter, an example in which the memory type processor 101 is used for index search calculation such as document search will be described.

In this example, vocabulary such as “information processing”, “information retrieval”, “patent”, “CPU”, etc. is assigned as an index to addresses 1 to N, and one record corresponds to one document.
That is, if there is at least one character such as “information processing”, “information retrieval”, “patent”, “CPU” in one document, “1” is written in the corresponding memory cell (field). Register every time.
("0" is omitted, and so on).

Therefore, in this example, N vocabularies (indexes) and n books (n records) are registered as a database.

In this example, the address 18 is “information processing”, the address 5 is “information retrieval”, the address 24 is “patent”, the address 10 is “CPU”, the index vocabulary (key vocabulary) is assigned, and the calculation condition is (“ The case will be described where “information processing” + “information search” vocabulary is included) * (documents not including the “patent” vocabulary) * (documents including the “CPU” vocabulary).

The lower part of FIG. 4 shows the above keyword search calculation method.
As a result of the logical sum (OR) operation of the “information processing” at the address 18 and the “information retrieval” at the address 5, the records of the documents including both vocabularies are 3, 4, 5, 13, 14, 16, 19, 21 , 25.
Next, the documents that do not include the “patent” vocabulary at the address 24 are 4, 8.11, 16, 22, and 25 as a result of the logical NOT operation.
The result of the previous calculation, the document records 3, 4, 5, 13, 14, 16, 19, 21, 25 and the result of performing a logical product (AND) operation of the logical negation (NOT) calculation result is 4 winning documents. 16, 25.

Finally, by performing a logical product (AND) operation between the document records 3, 7, 9, 12, 15, 16, 22 including the “CPU” at the address 10 and the previous winning remaining document, the last winning remaining document 107 is stored in the record 16. It has become.

When various operations are performed by a 1-bit arithmetic unit composed of one register, when it is necessary to temporarily save and store an intermediate operation result such as the operation result in (), for example, the address N is temporarily stored. It can be realized by using it as the buffer 207.

That is, the document 16 is (a document including any vocabulary of “information processing” + “information retrieval”) * (a document including no patent vocabulary) * (a document including the vocabulary of the CPU).
The above results may be read sequentially from the operation result output 106 such as a priority address encoder output circuit.

The CPU or GPU simply detects the target information from the memory type processor 101 without performing any search for the information of the entire memory space by simply performing the address selection designation 110 and the calculation condition designation 111 to the memory type processor 101. It becomes possible to do.

The above description is an example of a document search operation. However, if a record is replaced with a URL, it can be used for a database for Internet search.

The above document search is all index data with or without 1-bit data. Information processing of data in which data is stored (registered) by value will be described.

FIG. 5 is an explanatory diagram of an example of a data comparison arithmetic expression of a memory type processor using a 1-bit logic (Boolean) arithmetic unit.
The symbol “/” represents a logical negation 114 operation, “*” represents a logical product 112 operation, and “+” represents a logical sum 113 operation.
This example shows an arithmetic expression for performing a comparison operation of data in the case of a binary number and 4 bits, that is, a coincidence, magnitude, and range operation.
As shown in the figure, decimal numbers are converted to binary numbers, and in either case, MSB “8” is changed to LSB.
The addresses 104 of “8”, “4”, “2”, and “1” allocated to “1” that are “1” are selected so as to match the operation condition to be compared, and logical negation 114, logical product 112, the logical sum 113 indicates that it is possible to detect data that is equal to or less than or equal to.
By referring to this table, the calculation condition can be set to the following or range, and the calculation condition expression for comparing multiple bit data can be easily described.

As described above, when it is necessary to temporarily save and store an intermediate calculation result in performing these calculations, for example, the address N is used as the temporary temporary calculation buffer 207.
This can be applied to any of the following operations.

FIG. 6 is an example of a data coincidence comparison calculation method using a 1-bit logic (Boolean) arithmetic unit in a memory type processor.
This example is an example of binary, 8-bit data matching operation using a memory having a 1-bit logic (Boolean) operation function.

For example, consider a case where 8-bit data having address 10 as the most significant bit (MSB) “128” and address 17 as the least significant bit (LSB) “1” is assigned to the field.
Since it is 8-bit data, it is possible to store 256 types of data, and by selecting eight addresses from address 10 to address 17 appropriately, completely matching data is detected from 256 types of data. It becomes possible to output the address of the record.

For example, when the decimal data value “10” = binary number “000001010” is searched with a perfect match, address 10 is the most significant bit (MSB) “128” and address 17 is the least significant bit (LSB) “1” eight times. It is only necessary to calculate and detect data that is “00001010”.

As shown in the lower part of the figure, in this example, calculation is performed in the order of “128”, “64”, “32”, “16”, “8”, “4”, “2”, “1” from the MSB address 10. It is carried out.
In this case, in the case of the digit “00001010” in the digit “0”, the logical negation is performed, and in the case of the digit “1”, the positive logic is performed. Two records have the decimal data value “10”.
By repeating the 1-bit operation as described above, an arbitrary data value can be detected.

FIG. 7 shows an example of a data size comparison operation method of a memory type processor using a 1-bit logic (Boolean) arithmetic unit.
In the description so far, the exact match of the decimal data value “10” has been obtained, but when searching for the decimal data value “10” or more, as shown in FIG. By taking the logical sum of the addresses, it is possible to collectively detect records having a decimal data value of “16” or more.

Further, the logical value of the lower 4 bits of the addresses 15 and 16 and the address 14 are subjected to a logical product operation to obtain a decimal data value “10” or more and less than “16”. By taking a logical OR with the record, it is possible to detect a record having a data value of decimal data value “10” or more.
Further, as shown in the figure, if a record having a data value of decimal data “10” or more is negated, a record of less than “10”, that is, “9” or less is detected.

For other data values and range searches, the same 1-bit operation may be repeated.
The above calculation is the result of processing all records in parallel with the number of calculation steps within the number of digits. A range search operation can be realized.
Further, even when the data width is increased from 8 bits to 9 bits or 10 bits, it is very simple, and it is not always necessary that the addresses are continuous, and the data width can be increased by 1 bit to 17 bits or 33 bits without discomfort.

In other words, this memory-type processor can allocate data having an arbitrary data width such as one bit data with / without one to 256 bit width as field data in the record.
For example, in the case of personal information, the data width varies, such as “name”, “address”, “workplace”, “birth date”, “height”, “weight”, “gender”, etc. One of the features is that the data width can be allocated so that only necessary data bits are calculated, and unnecessary bits are not calculated.
Details will be described later.

FIG. 8 is an example of a maximum / minimum comparison calculation method using a 1-bit logic (Boolean) arithmetic unit in a memory type processor.
8-bit data of MSB “128” is assigned to address X and LSB “1” is assigned to address X + 7. Data to be compared is represented in each record, decimal numbers “69, 109, 21, 14, 5, 105, 5-34 "are written.

In order to find the maximum value from such data, it is preferable to set a calculation conditional expression based on the determination result using the calculation result as to whether or not there is data in any record.
The procedure is shown below.

First, the address “128” of the MSB is selected and the calculation result is judged.
As a result, since there is no data in any record, an operation of “/ 128” is performed. (Can be omitted)
Next, an operation of “/ 128” * “64” is performed. Since data exists in any record, an operation of “/ 128” * “64” * “32” is performed.
As a result, since any record has data, the calculation of “/ 128” * “64” * “32” * “16” is performed.
As a result, since there is no data in any record, an operation of “/ 128” * “64” * “32” * “/ 16” is performed.
As a result, since there is data in one of the records, an operation of “/ 128” * “64” * “32” * “/ 16” * “8” is performed.
As a result, since there is data in any of the records, the calculation of “/ 128” * “64” * “32” * “/ 16” * “8” * “4” is performed.
As a result, since there is data in any of the records, the calculation of “/ 128” * “64” * “32” * “/ 16” * “8” * “4” * “2” is performed.
As a result, since there is no data in any record, an operation of “/ 128” * “64” * “32” * “/ 16” * “8” * “4” * “/ 2” is performed.
As a result, since there is data in any of the records, an operation of “/ 128” * “64” * “32” * “/ 16” * “8” * “4” * “/ 2” * “1” is performed. .
As a result, the record that has been won is the maximum value, and it can be seen that the value is 64 + 8 + 4 + 1 = 109.
This 8-bit maximum value detection calculation is a total of 48 steps.

Next, in order to obtain the minimum, as shown in the figure, it is possible to obtain it by repeatedly calculating so that the complement data of each data remains as opposed to the maximum.
In this example, the minimum value of 5 is detected in two records.

As described above, in the maximum / minimum calculation, the remaining calculation results are determined, and the condition is set based on the determination result.

Such a calculation can be applied to various calculations in the same manner as the CPU condition determination calculation.
Accordingly, the calculation result output is not only output of the address of each record, but it is possible to perform efficient condition determination calculation by providing an output that can determine only whether any record has a winning bit or not.

So far, the calculation for mainly searching for data has been described, but other calculation examples are introduced below.

FIG. 9 is an example of address allocation in a data count calculation method by a 1-bit logic (Boolean) arithmetic unit of a memory type processor.
This example shows an example of address allocation when performing addition / subtraction counting of binary numbers and 4-bit data.
Address X to address X + 3 are count data 206, “8”, “4”, “2”, “1” bit storage areas, address X + 4 is temporary temporary buffer 207, and addresses X + 5 to X8 are “8”. , “4”, “2”, and “1”, a configuration in which each bit of carry data 208 (or borrow data 209) necessary for count calculation of each bit is allocated.

FIG. 10 shows an example of an addition count calculation method using a 1-bit logic (Boolean) calculator in a memory type processor.
This example shows an example of addition count of record data, and shows an example of allocation of addresses and records for executing addition count of binary number and 4-bit data.

As shown in the initial state in the upper part of the figure, “8”, “4”, “2”, “1” 4-bit data is assigned count data from address X to address X + 3. In this example, the left record As an initial value, count data of “0, 8, 1, 15, 7, 3, 5, 10” is written.
It is shown from the record on the left side that the 1-bit logic operation result (unwined) is “0, 1, 0, 1, 1, 1, 0 to 1”, and the current count data includes the 1-bit operation unit ( FF) calculation results (remaining winnings) are added and the calculation result “0, 9, 1, 0, 8, 4, 5,...

When the 1-bit logic (Boolean) operation is repeatedly added, the counter function can be realized by using the carry address of the addition result and the buffer address for temporarily storing the 1-bit calculator result as the work area. .
In this example, the address X + 4 is a 1-bit computing unit buffer 207, and the addresses X + 5 to X + 8 are carry data 208 of each bit.
In the initial state, these addresses are cleared and all are set to “0”.
The address assignment is not limited to this.

An example in which addition counting is performed using the canter data 206 and the work address assigned above will be described below.

In order from the top of the figure, an initial state, a bit calculation of “1”, a bit calculation of “2”, a bit calculation of “4”, a bit calculation of “8”, and a calculation result are shown.

In step 1, the contents of the 1-bit logic operator are saved in the 1-bit operator buffer 207 and the address X + 4.
The contents of the 1-bit calculator (FF) do not change.
In step 2, the bit of the count data “1” and the contents of the address X + 3 are substituted, and the result of operation of the 1-bit arithmetic unit (FF) and the logical product 105 are calculated. The operation result data is the carry data 208 of “1” bit. is there.
In step 3, this carry data 208 is assigned to address X + 8.
In step 4, the data of the 1-bit arithmetic unit in the initial state (added value) is substituted from the address X + 4 which is the 1-bit logical arithmetic unit buffer 207.
An exclusive OR operation is performed by substituting the addition value substituted in step 5 and the digit “1” of the count data 206 and the address X + 3. The calculation result is the calculation result of the digit “1”.
In step 6, this result is written as new data “1” at address X + 3, and the bit calculation of “1” is completed.

Similarly, from step 7 to step 24, the bit calculation of “2”, the bit calculation of “4”, and the bit calculation of “8” are repeated to rewrite the data of the digits “2”, “4”, and “8”. .

At the bottom of the figure, it is shown that the counter data is updated to “0, 9, 1, 0, 8, 4, 5, 11”, and the addition count is calculated by 1-bit logic (Boolean) operation. It is shown that it has been successfully realized.

In the case of 4-bit data, the above 24 steps are required. However, in the case of 8-bit data, it is 48 steps, which is twice as much, and in the case of 16-bit data, 96 steps are required.

As described above, the 1-bit operation seems to be inefficient at first glance. However, when parallel processing is possible such as thousands, tens of thousands, and 1 million records, the calculation efficiency is extremely high and high speed.

The count operation described above is extremely efficient when used continuously after some arithmetic processing.
For example, if the search ranking counter of the hit record is incremented by 1 after completion of the search operation of record data like the search ranking that counts the number of searches on the Internet, the counter is automatically set in the memory. It is very convenient because it can be updated.
It goes without saying that the values of these counters can be read at a high speed from the size comparison, range comparison, and maximum / minimum records.
The present invention is not limited to the above-described search ranking, and various uses such as a majority decision operation of various data, such as a majority decision of identification results of a plurality of features such as eyelid recognition and vein authentication, and a class decision operation are possible.

FIG. 11 is an example of a subtraction count operation by a 1-bit logic (Boolean) arithmetic unit of a memory type processor.
The difference between the addition and the subtraction described above is that the carry is replaced with a borrow and the complement operation is performed.
The carry data 208 is replaced with the borrow data 209 and assigned an address.
It is well known that the borrow data can be realized in the same manner as the addition by a complement operation that performs logical negation 114 on the target data.
Therefore, in the logical product operation of Steps 2, 8, 14, and 20, it is realized by calculating with logical negative data of “1”, “2”, “4”, and “8”.
The result is “0, 7, 1, 14, 8, 2, 5,... 9”, which indicates that the target subtraction count operation can be correctly realized by the 1-bit logic (Boolean) operation.

The above example shows an example of 4 bits, but for the calculation of a larger number of digits, the required number of digits may be repeatedly calculated.

FIG. 12 is an example of a full addition operation by a 1-bit logic (Boolean) arithmetic unit of a memory type processor.
The upper part of the figure represents a truth table for a binary 4-digit full addition operation.
Each figure is a truth table of the arithmetic output S and carry Co output after performing full addition calculation of three inputs of input A, input B, and input Ci (carry).

In the case of the first digit, a full addition operation of three inputs of input A “1”, input B “1”, and input Ci “1” is performed, and as a result, output S “1” and output Co “1” are output. Normally, Ci is not input in the first digit.
In the second digit, a full addition operation of three inputs of input A “2”, input B “2”, and input Ci “2” is performed, and as a result, output S “2” and output Co “2” are output. The input Ci “2” is the output Co “1” in the first digit.
Therefore, there are 8 combinations in the second digit.
The third digit and the fourth digit are the same calculation as the second digit.

Therefore, when full addition is performed by a 1-bit logic (Boolean) arithmetic unit, there are eight ways in which the three values of the input are “0” or “1” (the first digit may be four). And the result is temporarily stored, and the output S and the output Co are obtained from the result based on the truth table.
In the lower part of the figure, based on the above concept, the assignment of addresses in the case of executing a full addition operation of 4 bits each of input A and input B is shown.
Addresses X to X + 3 store data from A “8” to A “1”, and addresses X + 4 to X + 7 store data from B “8” to B “1”.
Addresses X + 8 to X + 11 are areas for storing the calculation result of the calculation result output S.
Address X + 12 is an MSB “8” digit carry storage area.
Addresses X + 13 to X + 20 are areas for determining which of the eight inputs A, B, and Ci is in eight states and temporarily storing the results.
As shown in the figure, ABCi determinations 1 to 8, “/ A” * “/ B” * “/ Ci” in address X + 13, that is, “0” in all three values, “A” * “B” * in address X + 20 “Ci”, that is, all three values are “1”, and all eight combinations of three values are calculated, and the result is stored in a predetermined address.

The eight determination results from ABCi determinations 1 to 8 are “1” for only one address from address X + 13 to address X + 20 per record.
Therefore, according to the truth table of the full addition operation shown above, if there is “1” in any of 2, 3, 5, and 8 of the above ABCi determination, the output S is set to “1”, otherwise The logical sum 113 operation to make “0” is performed, and the result is temporarily stored in the address X + 21, and the operation result for each digit of the output S is stored in any of the address X + 8 to the address X + 11.

Next, when there is “1” in any of 4, 6, 7, and 8 of the ABCi determination, the logical sum operation 113 is performed to set the Co output to “1” and set it to “0” otherwise. The result is stored at address X + 22.
In other words, 8 × 3 = 24 steps of determination calculation for determining any of the eight combinations, 8 steps of determination calculation for determining the calculation result S and C (carry), and a total of 32 steps of calculation may be executed. .
The above is the calculation for one digit. In the case of 4 bits, this may be repeated four times, that is, 128 steps.
In the case of 8 bits, 256 steps may be repeated.

The above is an example of addition, but it is well known that subtraction can be realized by converting carry data into borrow data and performing a complement operation, and is omitted here.

FIG. 13 is an explanatory diagram of a multiplication operation method (example) of a memory type processor by a 1-bit logic (Boolean) arithmetic unit.
It is known that a multiplication operation can be realized by shifting the result calculated for each digit of the multiplicand for each digit of the multiplicand and shifting each digit of the result for each digit.

For example, the decimal multiplicand “11” × multiplier “14” = “154”
When multiplying the binary multiplicand “1011” × multiplier “1110”,
The calculation of the first digit of the multiplier is “1011” × “0” = “0000”, the calculation result shift 0 “00000000”
The calculation of the second digit of the multiplier is “1011” × “1” = “1011”, the calculation result shift 1 “00010110”
The calculation of the third digit of the multiplier is “1011” × “1” = “1011”, the calculation result shift 2 “00101100”
The calculation of the fourth digit of the multiplier is “1011” × “1” = “1011”, the calculation result shift 3 “01011000”
Add all four operations above = "10011010"
The procedure in the case where this calculation content is executed by a multiplication operation by a 1-bit logic (Boolean) calculator of the memory type processor 101 is shown up to the second digit calculation result S3.

4-bit multiplicand data A is stored from address X to address X + 3, and 4-bit multiplicand data B is stored from address X + 4 to address X + 7.
Addresses X + 8 to X + 15 are areas for temporarily storing the calculation result of the first digit of the multiplier for each digit.
Addresses X + 16 to X + 39 are areas for temporarily storing the calculation results of the second to fourth multipliers for each digit.
Calculation of the digits of the multiplicand A and the multiplier B is performed, and the storage data of each area is shifted by 1 bit and the calculation result is stored.
This calculation is a simple process with a total of 16 steps since no carry data 208 is output.

The above four-digit calculation result is subjected to the full addition operation shown above, and the result is stored as the final result from address X + 40 to address X + 47.
Although this calculation is a little complicated because the carry data 208 is output, the calculation may be performed by the full addition calculation method described above.
4-digit multiplication can be realized in a total of 1056 steps.

In the case of division, it is known that the operation may be repeated from the upper digit of the dividend A to the digit divisible by the divisor B, and the multiplication / division operation can be performed by this method of the 1-bit logic (Boolean) operation function 123.
In the above description, various arithmetic operations including various arithmetic operations can be executed only by a Boolean arithmetic element without using four arithmetic (numerical) arithmetic units such as a half adder and a full adder. Is shown.
The calculation methods that have been described so far seem to be meaningless because it takes time and effort to perform repeated calculations, but it is possible to implement massively parallel calculations and perform calculations inside the memory without the help of the CPU or GPU. Considering that it can be completed, it has great significance.

In the following, a method for reducing the processing load of carry data 208 and borrow data 209 unique to numerical operations will be introduced in the case of information processing that frequently uses four arithmetic (numerical) operations.

FIG. 14 shows a circuit designed to efficiently realize the four arithmetic (numerical) operations 124 of the memory type processor.
In this example, when the switch 201 is switched to 2, a 1-bit four arithmetic (numerical value) calculation 124 can be realized.
The data for each bit from the memory is three flip-flops 202 that sequentially store data of each of the three inputs A, B, and Ci of the full adder 211 composed of two half adders 210 and a logical sum 113. And any one of them is selected and specified by a logical product 112 gate, and is added to the full adder 211.

As a result, the S output and C output of the full adder 211 are temporarily stored in the two flip-flops 202 once, and the output selected and designated by the OUT S selection input or the OUT C selection input is stored in the memory 100 through the switch 201. It is configured to be stored in the cell 102.
By configuring as described above, an arithmetic unit capable of realizing four-digit arithmetic operation with one digit in five steps is completed.
The above configuration is described as an adder, but as described above, it can be used for a subtracter and multiplication / division calculation.

The 1-bit four arithmetic (numerical) operation 124 described above is optimal for information processing in which four arithmetic operations are frequently used.
In addition, a multi-bit data calculation method and a data shift circuit capable of maximizing the performance of the four arithmetic (numerical) arithmetic units will be introduced.

FIG. 15 shows an example of the multi-bit data parallel arithmetic operation method of the memory type processor.
All the calculation methods so far have been completed and executed within one record. However, this calculation method calculates a plurality of records as one record group.
That is, the record group is one data, and the record width (data length) is arbitrary.
In the case of this example, nine records from record Y to record Y + 8 are assigned as one record group and assigned as one data, and the assignment is 8-bit data with record Y + 8 as LSB and record Y + 1 as MSB. Record Y is a carry output that is output as a result of four arithmetic operations.
The address X is assigned the operation input data Ai, the address X + 1 is assigned the operation input data Bi, the address X + 2 is assigned the operation output data Co, and the address X + 3 is assigned the operation output data So.

In the arithmetic unit in the lower part of the figure, a temporary storage device that temporarily stores data from the memory and data to the memory and an arithmetic operation device that performs the four arithmetic operations are arranged in parallel.

The 1-bit four arithmetic (arithmetic) arithmetic unit 124 described so far has been an operation completed within one record, but this multi-bit arithmetic unit 103 has a function of laterally feeding data to other records, that is, from LSB to MSB. In this configuration, a carry Co output, which is carry data 208 of each bit, is input to an upper carry Ci input.
This connection is necessary for the width of the data, and it can be configured such that any record can be arbitrarily specified for each record, such as connecting from which record to which record or not connecting.

With this configuration, the input data of Ai and Bi assigned in parallel from the memory address X and the address X + 1 is stored in the temporary memory, and the output of the temporary memory is connected to the input of the four arithmetic units. Therefore, the four arithmetic units for each record from the LSB to the MSB execute the calculation in parallel for each record and output the calculation output So and the carry output Co to the temporary storage unit and output the result to the memory address Y + 2 and the address. Y + 3 can be stored as a calculation result.

Although this calculation method will be described later in detail, it is extremely efficient and high-speed compared to any of the calculation methods so far. However, by providing optional functions such as a multiplier and a carry look-ahead function in the four arithmetic units. Further, high-speed computation can be realized.
Since the circuit structure of the carry prefetch circuit increases as the data width increases, the data width of the operation is limited to about 8 bits or 16 bits, and if the operation with a wide data width is performed repeatedly including the carry, the space can be saved. A high-speed arithmetic circuit can be realized.

In the conventional methods, for example, when an 8-bit addition operation is performed by a 1-bit logic (Boolean) arithmetic unit, 256 steps are required in the case of a 1-bit four arithmetic operation unit. In this case, four arithmetic operations can be realized with a total of about 5 steps regardless of the data width, which is extremely efficient as compared with the conventional calculation methods.
It goes without saying that this carry calculation method can be applied to all of the counter calculation and addition / subtraction / multiplication / division calculations described above.

In this calculation method, data transfer between records of carry data 208 and borrow data 209, which is indispensable in the four arithmetic operations, is realized by a data lateral feed function. Needless to say, this method is limited to data of one set of record groups. It can be used with a large number of records.
Since the effect increases as the degree of parallelism increases, it can be used for the entire record.

In the case of this method, the input data (A, B) can be signed, and the calculation result has a maximum data width, for example, multiplication, and a data width (record) considering carry, borrow, and sign. It is better to make an allocation considering the width.

As described above, this 1-bit operation function (logical operation, four arithmetic operations) has a large feature not found in a normal ALU because it can perform bi-directional operation of rows and columns. The appropriate calculation method can be selected by properly using the data to be calculated in.
In the following, the data conversion function indispensable for performing data conversion in the row direction and column direction and various operations will be described.

FIG. 16 is a circuit configuration example of a memory type processor having a data shift function.
As shown in the figure, record data 215 is stored in the memory cell 102 for each address.
A 1-bit calculator 105 is connected for each record.
In the description so far, the register of the 1-bit arithmetic unit 105 is the flip-flop 202. In this case, the data in the same record can be freely moved and operated for each 1-bit, but the data is moved between the records and operated. I couldn't do it.

As shown in the figure, the flip-flop 202 described so far is used as the shift register 212, the clock signal 216 is given from the outside, and the flip-flop result output 205 (in this case, the shift register output) and the clock signal 216 are shifted to the next record. By connecting to the input of the register, data movement (shift transfer) between records becomes possible.

When shift transfer between data records as described above becomes possible, it is possible to make the conventional calculation functions more sophisticated and faster.

A normal shift register can only implement a data shift of one record in one clock, but it is also possible to adopt a shift register configuration that fast forwards 8 records or 16 records in one clock.
The multi-bit arithmetic unit 103 and the shift register 212 described above are one of functions for transferring data to be calculated to other records, and this function greatly increases the performance of the memory processor.

17 and 18 show an example of data matrix conversion by the memory type processor.
As described above, a memory type processor having a 1-bit operation function has a feature that can perform bi-directional operation of rows and columns.
In order to make good use of the above features, we introduce a method for matrix conversion of operation data using the shift function described above.

FIG. 17 shows the steps of preprocessing operations for matrix conversion.
Data to be subjected to matrix conversion is written from address 1 to address 4.
This data is data having a 4-bit data width that is a set of 4 bits of records 5 to 8, records 9 to 12, and records 13 to 16.

Mask data which is operation auxiliary data is written in addresses 5 to 8 of the record.

The address X is assigned the logical product of addresses 1 and 5.
The logical product of address 1 and address 6 is assigned to address X + 1.
The logical multiplication result of address 1 and address 7 is assigned to address X + 2.
The logical product of address 1 and address 8 is assigned to address X + 3.

The logical product operation result at the address X is not shifted.
The logical product operation result at the address X + 1 is shifted by -1 (one shift to the left).
The logical product operation result at address X + 2 is shifted by -2 (2 shifts to the left).
The logical product operation result at address X + 3 is shifted by -3 (three shifts to the left).
Thus, the preprocessing calculation related to the data at address 1 is completed.

The operation related to the data at address 2 is performed in the same manner from address X + 4 to address X + 7.
An operation related to the data at address 3 is performed from address X + 8 to address X + 11.
An operation related to the data at address 4 is performed from address X + 12 to address X + 15.
The above is the preprocessing operation for matrix conversion.

FIG. 18 shows a step of performing matrix transformation on the above preprocessing calculation result.
All of the addresses X + 3 from the address X, which is the result of the preprocessing operation on the data at the address 1, are not shifted.
All of the addresses X + 4 to X + 7, which are the result of the preprocessing operation on the data at address 2, are shifted by +1 (1 to the right).
Address X + 8 to address X + 11, which are the pre-processing calculation results for the data at address 3, are all shifted by +2 (2 to the right).
Address X + 12 to address X + 15, which are the results of the preprocessing operation on the data at address 4, are all shifted by +3 (3 to the right).

The logical sum operation of the address X, the address X + 4, the address X + 8, and the address X + 12 is assigned to the address X + 16.
The logical sum operation of address X + 1, address X + 5, address X + 9, and address X + 13 is assigned to address X + 17.
The logical sum operation of address X + 2, address X + 6, address X + 10, and address X + 14 is assigned to address X + 18.
The logical sum operation of address X + 3, address X + 7, address X + 11, and address X + 15 is assigned to address X + 19.

The data of the 4-bit data width of records 5 to 8, records 9 to 12, and records 13 to 16 of addresses X + 16 to X + 19, which are the above calculation results, is obtained by matrix conversion of data of addresses 1 to 4.

In this example, the data is 4-bit data, but 8-bit, 16-bit, or even larger data is possible.
Although the number of repeated operations increases, as described above, it is an effective matrix transformation considering that parallel operations can be performed.

In this example, a pre-processing operation necessary for performing matrix operation on addresses 5 to 8 is performed using auxiliary data and matrix conversion is performed using a shift register function.
This memory type processor greatly expands the utilization method by utilizing the auxiliary data as described above.

Next, the data input function of the memory type processor 101 will be described.
The biggest consideration of this technology is how to store record data.
As a method that can be realized relatively easily, when writing target data to the memory type processor 101, external data can be written and read through the flip-flop 202 of the 1-bit arithmetic unit.

In this case, in principle, writing is performed for each 1 bit, and this memory type processor 101 has an array in which normal database data is inverted vertically and horizontally, so for example, array data such as record data 64 bits * 64 bits stored in a normal memory is stored. Then, after transferring from the input of the memory 101, matrix conversion is performed inside the memory type processor 101, and only 64 flip-flops 202 of the designated write destination record are valid (does not affect the memory cells of other records). The external data can be stored by storing the data 64 times for each write destination address.
That is, it is only necessary to sequentially write 64-bit data every 64 addresses.
In this case, even if the data for one record is changed, it is overwritten for the width of 64 records.

Next, the output function of the memory type processor 101 will be described.
If the record width is relatively small, the operation results can be output in parallel.
However, when the number of records becomes several thousand or more, it is not practical to pull out the output pin to the chip of this memory.
Therefore, when the number of records is large, the priority order output circuit (priority encoder) 124 may output the address of the record of the calculation result for each record.
The priority order output circuit (priority encoder) 124 is convenient when the calculation result is narrowed down.
Considering that many records are searched, if the operation result output 106 such as the priority address encoder output circuit is divided into several blocks and can be read out in units of blocks, It becomes possible to increase the address output of records.
Further, as described above, if there is an output for determining whether or not there are remaining winning records, it is efficient for processing with many condition determinations.
Needless to say, the operation results of the main records may be output in parallel as long as the output pins can be drawn from the chip.

Various circuit configurations have been introduced so far, but the minimum configuration of a 1-bit computing unit is 1 unit (1 record). If the circuit is limited to a single function, from a few hundred transistors to a standard circuit configuration of 1000 (1K) It can be realized with a transistor circuit scale of about.

Consider the case where the present invention is realized with a semiconductor on the assumption of the above,
In the current semiconductor miniaturization technology, 10 billion transistors can be mounted on one chip, and the memory capacity of a one-chip DRAM is about 8 Gbit.
In the future, it is expected that about 100 billion transistors will be mounted.

However, miniaturization technology based on Moore's Law is approaching its limit, and it is said that the improvement of the integration after that will only have to be switched to other methods such as three-dimensional mounting.
So far, the parallelism of multi-cores and manycores using ALU has been improved according to Moore's Law, but if Moore's Law reaches the limit, the improvement of parallelism cannot be expected.
However, since the arithmetic unit according to the present invention has a very simple circuit configuration as described above, it has about 1000 (1K) transistors in the case of a standard function.

Therefore, 10,000 units (record) has about 10M transistors, 100,000 units have about 100M (100 million) transistors, and one million units (1M record) has about 1 billion transistors.
Therefore, even in the case of 1M record, it accounts for 10% of 10 billion transistors that can be mounted on one chip at present.
Since it occupies 1% at the time of the limit of miniaturization, the space-saving property is specially noted.

Also, when accessing a wide address such as a 1M record, the inrush current is minimized by adopting a circuit configuration in which the record is distributed to several banks and the operation is performed by delaying the minute access time. It can be a chip that can be operated with reduced power consumption.
It is also possible to save power by excluding unused records.

In the case of a FLASH memory in which the stacking technology advances, the memory capacity per chip at the present time is about 1 Tbit.
Therefore, the memory type processor 101 having a nonvolatile 1-bit arithmetic function of 1 M (million) bits in the vertical and horizontal directions is realized.
In the case of SRAM, the degree of integration does not increase like DRAM and FLASH memory, high-speed computation can be expected, and the semiconductor development cost can be realized at a relatively low cost.

In addition to the DRAM, FLASH, and SRAM described above, recently, non-volatile and magnetic storage type memory cells that are expected to save power have been actively studied, and this memory can be used in common for such memories. Since only a small part of the logical operation function is added, it is possible to perform simple information processing with a very large capacity and at an ultra-high speed.

This memory is an in-memory database, and a memory having a self-contained calculation function that does not rely on the CPU for calculation is a memory type processor.
The memory type processor is not necessarily intended for large data, and is optimal for information processing that requires repeated calculation even for small data. Therefore, the algorithm of the memory type processor 101 can be easily implemented in an FPGA. .
The multi-bit arithmetic unit 122 and the like having various cases can be used flexibly if it is an FPGA.
It is also effective for a device configuration in which the memory type processor and the CPU are integrated, and a cache memory of the CPU.

FIG. 19 shows an example of serial-parallel connection of memory type processors.
This memory 101 is a completely independent memory and can be expanded in the vertical direction (address direction) or in the horizontal direction (data width direction), so that the expansion of the system is extremely simple and the system is made persistent. I can do it.
In the case of full-text search, there are hundreds of thousands of addresses. However, in the case of personal information, it is sufficient if there are addresses from several K to several K per person.

Normally, when one CPU finds specific information from a memory having no array definition or index at all, for example, even if the memory is accessed and collated with an average of 10 ns, it takes about 10 milliseconds for a 1M address. It takes 10 seconds for 1G and 10,000 seconds (about 3 hours) for 1T.
If CPUs are used in parallel and distributed processing is performed, the processing time can be reduced in principle in proportion to the number of CPUs.
However, it is difficult to perform a search calculation or data mining in real time (for example, within 1 second) for an in-memory database exceeding 1 TB.

In the case of the memory type processor 101, it is possible to perform parallel processing of all memories even if the data is, for example, 10 TB data, and the address selection 110 and the calculation condition specification 111 can be performed several times to several tens of times. Just repeat it a hundred times.

Although the access speed varies depending on the memory element, for example, if the speed of one logical operation is 10 ns, if 1 s, 1 million seconds can be realized, and 100,000 parallel operations can be realized. Even with big data of any size, it is possible to find the target record in hundreds of nanoseconds, microseconds, and 1 millisecond, regardless of its size.
In other words, it can be said that the greatest feature of this technology is that the effect is as remarkable as big data.
The idea of reversing the vertical / horizontal relationship between the memory structure and the data of the present invention clearly shows that the number of times of information processing is greatly reduced and the processing time is greatly reduced.

This is extremely effective for data mining of big data that needs to be repeatedly searched based on various assumptions and data matching processing that requires brute force calculation. Details will be described later.

FIG. 20 shows an example of hierarchical connection of memory type processors.
In the example shown in the figure, the memory type processor 101 shown at the top of the figure is used as a master so that each sub-memory type processor 101 storing more detailed data for each record can be searched corresponding to each record. In particular, in the case of big data, it is possible to deal with any size database by using such a hierarchical database.

FIG. 21 is an example of the feature database A by a memory type processor.
Matching operations that require brute force operations or a large number of combination operations of all records and all field data can make the most effective use of this memory feature.
This example is an extremely small data table that only shows an image of the configuration, but five types of feature data from features A to E of 4-bit data are stored in a database from address 1 to address 20 as record data 215.

Five types of data A to E of comparison data 213 to be compared are compared with this database, and the number of matched features, the number of approximate features, and the difference between the database and the verification data are calculated. In this configuration, the collation results obtained by performing various operations such as accumulating the results are stored at addresses 21 and below, and the addresses are assigned so as to determine the results.
The data width of the feature data can be increased or decreased individually, or the number of features can be greatly increased.

FIG. 22 shows an example of the feature database B by the memory type processor.
The database of this example is the same as that described above, but is a feature database of 8-bit data using the multi-bit four arithmetic operation method described above.

In this example, 8-bit feature data from feature data A to feature data T up to address 20 of the memory-type processor is written for every 12 record groups.
The database is collated in parallel (in this example, 12 record groups) for each feature collation data given from the outside.
This method can perform computations much faster than the feature database A described above.

In this example, the collation data is substituted into the address 21, and the target feature and collation are repeated. At this time, the 8-bit data at the address 21 is exactly the same data as the parallel number (12 sets in this example). Need to write.
When the record group becomes large (the degree of parallelism becomes large), the transfer time of verification data becomes a problem.
In such a case, extremely high-speed collation data can be obtained by using the following method.

FIG. 23 shows an example of parallel data creation by a memory type processor.
As shown in the figure
From address X to address X + 3, 4-bit auxiliary data address X + 4 to address X + 11, 8-bit auxiliary data address X + 12 to address X + 27 are previously written with 16-bit auxiliary data.

If these auxiliary data are prepared in advance,
For example, the address X + 28 is data obtained by ORing the address X of the 4-bit data and the address X + 2.
The address X + 29 is data obtained by ORing the address X + 6, the address X + 9, and the address X + 11 of 8-bit data.
The address X + 30 is data obtained by ORing the address X + 27 from the address X + 12 of 16-bit data.
Further, the address X + 31 is data obtained by ORing the address X + 28, the address X + 29, and the address X + 30.

The auxiliary data is also effective when the storage cell at a specific address in a specific record is set to “0” or “1” or when data is overlapped.
By preparing the auxiliary data as described above in advance, arbitrary data having an arbitrary data width can be obtained in parallel (at high speed).
The above is an example of utilization of auxiliary data, and auxiliary data greatly expands the capacity of the memory type processor.

As an example, the data for checking the bag is about 1 KB per person.
Since the data for 1,000 people is 1 MByte, real-time processing is not so difficult even with a normal personal computer. However, the data for 1 million people becomes 1 GByte, which is difficult for a normal personal computer and has many CPUs and GPUs. The dedicated system used is necessary.
Furthermore, in the case of Japan as a whole, a system that is 100 times as large as 100 GBytes, and if you try to process the faces of people all over the world in real time, it will become a huge system with 100 times as many as 10 TBytes. It's not realistic.
If this invention is used, it is only necessary to prepare many memory type processors 101 of this invention.
If there are 80 1Tbit FLASH memories, the database for collation of all human beings is completed.
With a 10Tbit FLASH memory born in the near future, a database for collation of all human beings will be completed with only eight.
Although it depends on the calculation contents, in many cases, collation determination calculation is possible in about several tens of microseconds, and as described above, the biggest feature is that the record time is the same time for 1 million records or 10 billion records, for example. .
Less heat is generated and complicated peripheral circuits are not required, so that the system can be greatly reduced in size and saved in power.

The above is the collation operation of the feature data. However, if the feature data is applied to various things such as the data category, the data class, and the data area, the application is infinite.
For personal information, data of various data widths such as “name”, “address”, “workplace”, “birth date”, “height”, “weight”, “gender”, etc. are assigned as data categories. That's fine.
It is not necessary to prepare various indexes for searching for information for these personal information, and calculation can be started immediately after data registration is completed.
Even if the performance of the CPU or GPU is improved, an information processing environment that does not require such an index cannot be obtained.
Details of this technique will be described later.

Therefore, the effect is more remarkable as the number of records increases, and it is most suitable for all uses such as fingerprint data verification, voiceprint authentication, character recognition data feature verification, etc. It is.

This technology greatly improves the performance by incorporating it into a part of artificial intelligence that has a lot of combined information processing.
The learning function used in artificial intelligence needs to read a lot of sample information and learn until the expected answer is obtained, but it takes a very long time if the scale or class of information to be learned increases.
If this technology is used, complicated information processing can be eliminated even with large-scale knowledge information, so the learning time can be shortened and the recognition ability can be greatly improved.
In addition, it is ideal for analysis and data mining of weather information where various conditions are intricately intertwined.

Hereinafter, various effects obtained by this technique will be described.
In order to construct a database using the memory type processor 101, it is possible to use only by assigning the addresses of records and field data, and only by specifying the calculation condition 111 thereafter.
Accordingly, by preparing an application interface of the memory type processor 101, it can be incorporated into a database such as a conventional search algorithm such as SQL.

There are various usage techniques for searching for information using a CPU in order to reduce the burden on the CPU.
A binary search is a typical example.
This algorithm is a standard technology for information processing as a technology that can extremely reduce the number of searches for information data. However, when data values are written in a data table on a memory, for example, prior arrangement is made such that data is arranged in order from small data to large data. It is necessary to rearrange the data on the memory (data maintenance) whenever preparation is necessary and data increases or decreases.

In other words, this algorithm reduces the burden on the CPU when searching for a specific data value, but the burden on pre-processing and data maintenance before that is quite small.
The above is an example of binary search, but other algorithms such as a hash table and a B-tree structure (index) are exactly the same.

By using the present invention, it is not necessary to use the above algorithm, so information processing such as advance preparation and maintenance is completely unnecessary. It only requires registration or deletion, and no data maintenance such as annoying array changes or data rearrangements is required.

This indicates that the information processing configuration is greatly simplified and simplified as compared with the conventional CPU and GPU-only information processing.
Since the various information processing introduced so far is the central processing of information processing, it results in greatly reducing the burden on many users (engineers) who are involved in information processing.

In addition, since the CPU that controls the memory type processor 101 and controls the entire information processing does not need to be high speed, it is possible to greatly reduce the power related to the information processing.
Therefore, the burden on the user involved in information processing and the burden on the CPU, GPU, and peripheral circuits are greatly reduced at the same time.

The current information processing is such that the CPU sequentially accesses the address, reads the data, and sequentially performs the information processing with a constant data width such as the data width of the memory 100 such as 32 bits, 64 bits, and 128 bits.
The wider the data width (bus width), the higher the efficiency of information processing, but there are limits to the expansion of the data bus width, such as the increase in the number of input / output pins of the device and the increased wiring burden on the printed circuit board on which the device is mounted. There is.

In addition, in the case of a personal database or the like, there is a lot of useless bit processing because data having a small data width such as age is 7-bit data (up to 127) and sex is 1-bit, and an arithmetic unit with a wide data width is used. become.
The memory-type processor 101 of the present invention can perform parallel calculation in an arbitrary data width of 1 bit or more and in a row direction, a column direction, and an arbitrary data width, and therefore can perform information processing with no wasteful bits.

The inventor of the present application has been researching various types of memory devices so far. Patent No. 4588114 A memory having an information narrowing detection function is a memory that is good at AND operations such as pattern matching.
PCT / JP2013 / 059260 memory with set operation function expands and expands the concept of memory with information narrowing detection function, and can perform logical product operation, logical sum operation, logical negation operation, etc. It is a memory type device that can
A feature of the memory type device is that the processing time is always constant regardless of whether the capacity of information processing is large or small. Therefore, the effect increases as the information processing capacity increases.

Demonstration machines using FPGAs with relatively small information processing capacities have been verified to be tens of thousands of times more powerful than conventional information processing. If an ASIC chip with a large information processing capacity is created, several hundreds It has been verified that the speed can be increased 10,000 times.

In addition, as a result of developing a document retrieval system using FPGA with the Japanese Patent Application No. 2013-264863 of the invention by the inventor of the present invention and a memory having an information retrieval function, the retrieval time which takes about 76 milliseconds in normal software processing is 207 nanoseconds. It has been demonstrated that it can be realized at a speed as high as 370,000 times.
The above content is widely disclosed as a “technology for speeding up data retrieval 1 million times” through academic conferences, exhibitions, and the media, and practical products are being developed.

Based on the above results, the present invention provides an arithmetic circuit capable of extracting various features of the memory type device to the maximum and various usage methods, and can perform a wide range of information processing as follows. It shows that.
1. Index calculation .... Contribute search, database search Data comparison (match, large, small, range, maximum / minimum) ... database search Calculation result judgment Conditional calculation 4. Addition and subtraction counters · Cumulative calculation results Adder, subtractor ... Addition and subtraction of data 6 Cryptographic processing: Plain text encryption, cipher text decryption7. Matrix transformation8. 8. Creation of data Combined operation above

The feature of this technology is that by using abundant memory resources as a data area and work area, a variety of operations can be performed with only a 1-bit logic (Boolean) arithmetic unit using a Boolean operation element (logical operation element) with an extremely simple circuit configuration. It is specifically shown that it is possible.
In addition, when the use frequency of numerical operations is high, it is specifically shown that efficient numerical operation processing can be performed by adding and incorporating a 1-bit four arithmetic (arithmetic) operation element.
In addition, by providing a data transfer function between records, it is possible to perform more effective and high-speed operations, such as performing data operations as a group of records and performing matrix transformations. It is shown in.

It is well known that arithmetic elements such as logical product (AND), logical sum (OR), logical product (NOT), exclusive logical sum (XOR), and an adder combining them are the basis of information processing (computer). The usage and application methods are widely introduced in various documents and the Internet.
A typical element is ALU, and CPUs and GPUs using ALU 217, which is usually a multi-bit arithmetic unit 122 of 8 bits or more, are used in every corner of our lives and industries.
As a matter of course, performing all operations with a 1-bit arithmetic unit has not been studied, introduced, or used because it takes time for repeated operations as described above.

However, the main points of the memory type processor operation by the 1-bit arithmetic unit described so far are summarized as follows.
1. The calculation by the 1-bit arithmetic unit is inefficient at first glance, but if the parallel operation is performed, the calculation becomes extremely fast and bi-directional matrix operation is possible.
2. Regardless of whether the amount of data (number of records) is large or small, the computation time is always constant, so it is optimal for big data.
3. The burden on the CPU and GPU is reduced, and the power of the information processing apparatus is reduced.
4). 4. No need to consider complicated information processing algorithms and their metadata, reducing the burden on developers. Since metadata such as an index is not necessary, advance preparation and metadata data maintenance are not required.
6). Just storing the basic data in the memory makes it possible to perform calculations immediately.

The calculation method introduced in the present invention cannot be generated except for knowing the ability of a 1-bit arithmetic unit having the above-mentioned various merits by massively parallel calculation.
The calculation method introduced in the patent of this application was originally devised and systematized by the inventor of the present application, but the information processing method in which the rows and columns are reversed is summarized from the state almost completely blank to the present application. It took a lot of patience and time to put together.

The introduced calculation methods show typical calculation methods that are frequently used in information processing and the most suitable calculators. In addition, various optional functions can be added to the necessary minimum. It is also free to use.
There are innumerable calculation methods and their applications as well as CPU.

By setting these calculation methods as a standard library, the user can incorporate and use it in general software without being aware of the hardware.

The present invention is a memory-type processor that pursues the ideal form of a computer in a big data society, solves many of the problems of computer technology for information processing using only a CPU and GPU, and complements the weak points of the CPU and GPU.

The memory-type processor according to the present invention can be widely used as a part of a function of an artificial intelligence device as well as a general data database, a super-large database, a super-large parallel processing, various types of authentication, a verification process, and the like. .
In addition, this technology reduces the burden on engineers involved in information processing development, and can significantly reduce the power of information processing, so it has great significance in solving environmental problems in IT equipment.
In the future, memory processors with more advanced information processing functions such as multi-bit, space-saving massively parallel computing elements, XY 2-axis bidirectional address access, and 2-axis bidirectional record parallel computing elements Can be expected.

100 Memory 101 Memory type processor 102 Memory cell 103 Word width (number of records)
104 Address 105 1-bit computing unit (calculation function)
106 operation result output 107 operation result 110 address selection 111 operation condition designation function 112 logical product 113 logical sum 114 logical negation 115 exclusive logical sum 116 logical storage
122 Multi-bit computing unit (calculation function)
123 1-bit logic (Boolean) arithmetic unit (arithmetic function)
124 1-bit four arithmetic (arithmetic) arithmetic unit
201 switch 202 flip-flop (FF)
203 selection circuit 204 memory data 205 flip-flop result output 206 count data 207 1-bit arithmetic unit buffer 208 carry data 209 borrow data 210 half adder 211 full adder 212 shift register 213 collation data 214 priority order output circuit (priority encoder output)
215 Record data 216 Clock signal 217 ALU

Claims (12)

A multi-bit memory cell capable of storing data input from an external input function, an operation for reading the data of the memory cell every 1 bit, performing an operation, and writing the operation result to the memory cell every 1 bit An operation condition designating function for arranging a plurality of records in parallel, enabling the address selection of the memory cells of the many bits of all records in parallel, and designating operation conditions in parallel. ,
An external output function for outputting the calculation result of the record to the outside;
A memory type processor. The calculation function is
(4) logical product operation (5) logical sum operation and (6) logical negation operation (4) exclusive OR operation (5) half addition operation (6) full addition operation (7) operation storage (8) or more (1) The memory type processor according to claim 1, wherein any one of the combinations of (7) to (7) is executed. The external input function is:
2. The memory type processor according to claim 1, further comprising a function of performing matrix transformation on the data to be calculated from outside and writing the data to be calculated. The external output function is:
(5) Output the addresses of the records in order of priority (6) Divide the records into several parts and output the divided records in order of priority (7) Whether any of the records has a calculation result The memory type according to claim 1, further comprising: an output function that outputs any one of the combinations (1) to (4). Processor. 2. The memory type processor according to claim 1, further comprising a function of transferring the calculation target data to the other record. 2. The memory type processor according to claim 1, wherein the memory type processor is incorporated in a circuit of a CPU and other functions. 2. The memory type processor according to claim 1, wherein the memory type processor is implemented by an FPGA. An apparatus comprising the memory-type processor according to claim 1. 2. The method of using a memory-type processor according to claim 1, wherein both the data to be calculated and the work area data for temporarily saving the calculation result are allocated to the address, and both the data are used. By repeating the 1-bit calculation function,
(1) All-record parallel index search operation of the calculation target data (2) All-record parallel comparison (match, large, small, range, maximum / minimum) calculation of the calculation target data (3) All of the calculation target data Record parallel count (up / down) operation (4) All-record parallel addition / subtraction operation of the calculation target data (5) All-record parallel multiplication / division calculation of the calculation target data (6) All-record parallel of the calculation target data Encryption of plaintext and plaintext decryption operation of ciphertext (7) All-record parallel matrix conversion operation of the operation target data (8) Combination operation of all-record parallel data creation operation of the operation target data (9) or more A method of using a memory-type processor, characterized by performing any of the above operations. A method of using a memory type processor according to claim 1, wherein it is determined whether or not there is a record remaining after winning the operation result, and an operation conditional expression is given based on the determination result. how to use. 2. Use of a memory type processor according to claim 1, wherein the data of a plurality of memory cells are allocated to a set of data from the large number of records and used. Method. A method of using a memory-type processor, characterized in that the memory-type processor is used in (1) serial, parallel, or series-parallel connection, or (2) any one or more of hierarchical connections.

Images