JP7477486B2 - DESIGN APPARATUS, OPERATION CIRCUIT, DESIGN METHOD, AND DESIGN PROGRAM - Google Patents

Description

The present invention relates to a hardware implementation method for high-speed execution of cryptographic processing.

Conventionally, in each operation implemented in an arithmetic circuit for executing a predetermined processing procedure, registers are provided at the input and output, and the operation result based on the data received from the input register is stored in the output register. If the clock period of the arithmetic circuit is short for such an operation (path) executed between registers, the operation result is discarded without being stored in the register.
Therefore, when the operating frequency is increased to improve processing performance, it is necessary to suppress the delay (computation time) of the critical path.

For example, Patent Document 1 proposes an adder-subtractor that reduces the amount of hardware required to reduce delays in the critical path. Patent Document 2 proposes an arithmetic circuit that reduces delays in the critical path in a process of sequentially converting multiple bits of a binary number into an X-ary number.

JP 2016-224596 A JP 2012-209755 A

However, the conventional technology was intended to reduce delays in the critical path in specific processes such as addition/subtraction or base conversion, and could not be used to improve the performance of any cryptographic process, for example.

The present invention aims to provide a design device, an arithmetic circuit, a design method, and a design program that can improve throughput in the hardware implementation of any process.

The design device for an arithmetic circuit according to the present invention includes a critical path selection unit that selects, from among multiple processes executed in sequence, the process with the longest delay as the critical path, and a register insertion unit that inserts a register between any of the multiple processes and adjusts the delay of the process between the registers to be equal to or less than the critical path, and the register insertion unit inserts the minimum number of registers that satisfy the condition that all delays of the process between the registers are equal to or less than the critical path.

When there are multiple processing procedures that can be performed in parallel, the critical path selection unit may select, as the critical path, the processing procedure with the longest delay among all the processing procedures included in the multiple processing procedures, and the register insertion unit may adjust the processing delay between registers for each of the multiple processing procedures to be equal to or less than the critical path.

The register insertion unit may select the maximum number of processes from the beginning of the execution order whose total delay does not exceed T, and repeatedly insert a register immediately after the selection.

The arithmetic circuit according to the present invention includes a register between any of a number of processes executed in sequence, and the registers are provided in the minimum number that satisfies the condition that the process with the greatest delay is the critical path, and all process delays between the registers are equal to or less than the critical path.

The design method of the arithmetic circuit according to the present invention is carried out by a computer to execute a critical path selection step of selecting, from among a number of processes executed in sequence, the process with the longest delay as the critical path, and a register insertion step of inserting a register between any of the plurality of processes to adjust the delay of the process between the registers to be equal to or less than the critical path, and in the register insertion step, the minimum number of registers are inserted that satisfy the condition that all delays of the process between the registers are equal to or less than the critical path.

The arithmetic circuit design program of the present invention is intended to cause a computer to function as the design device.

The present invention can improve throughput in hardware implementation of any process.

FIG. 2 is a diagram illustrating a functional configuration of a design apparatus according to an embodiment. 1 is a flowchart illustrating a design procedure for hardware implementation of cryptographic processing in an embodiment.

An example of an embodiment of the present invention will now be described.
The arithmetic circuit of this embodiment is a hardware implementation that improves throughput, with the aim of improving the performance of any process such as cryptographic processing.

When implementing cryptographic processing in hardware, one method for improving throughput is to insert a register into the middle of the processing. Inserting a register eliminates the critical path, and therefore increases the operating frequency, thereby improving throughput.
On the other hand, inserting an excessive number of registers increases the number of clocks required to complete processing, leading to a decrease in throughput. Therefore, in this embodiment, a method is shown for optimizing throughput by determining the position to insert a register based on the delay time of the critical path when implementing cryptographic processing in hardware.

FIG. 1 is a diagram showing the functional configuration of a design apparatus 1 according to this embodiment.
The design apparatus 1 is an information processing apparatus (computer) including a control unit 10, a storage unit 20, and various input/output interfaces.

The control unit 10 is a part that controls the entire design device 1, and realizes each function in this embodiment by appropriately reading and executing various programs stored in the storage unit 20. The control unit 10 may be a CPU.

The storage unit 20 is a storage area for various programs for causing the hardware group to function as the design device 1, various data, etc., and may be a ROM, a RAM, a flash memory, a hard disk drive (HDD), etc.
Specifically, the storage unit 20 stores a program (design program) for causing the control unit 10 to execute each function of the present embodiment.

The control unit 10 includes a critical path selection unit 11 and a register insertion unit 12, and these functional units insert an appropriate number of registers into appropriate locations in the arithmetic circuit to optimize throughput.

The critical path selection unit 11 selects, from among a plurality of processes executed in sequence, the process with the greatest delay as the critical path.
At this time, when there are a plurality of processing procedures that can be executed in parallel, the critical path selection unit 11 selects, as the critical path, the processing procedure with the maximum delay among all the processing procedures included in the plurality of processing procedures.

The register insertion unit 12 inserts a register between any of a plurality of processes executed in sequence, and adjusts the delay caused by the processes between the registers to be equal to or smaller than the critical path.
At this time, the register insertion unit 12 inserts the minimum number of registers that satisfies the condition that all processing delays between registers are equal to or less than the critical path for each of one or more existing processing procedures.

FIG. 2 is a flowchart illustrating a design procedure for hardware implementation of cryptographic processing in this embodiment.
In hardware implementation of cryptographic processing, processes that can be executed in parallel by different circuits are designated as A and B. Note that the same applies when there are three or more processes that can be executed in parallel, so here, without loss of generality, the description will be given assuming that there are two processes that can be executed in parallel.

Moreover, the process A is divided into processes that are executed sequentially, and these processes are designated as _a1 , _a2 , ..., _am . For example, if A is the round function of AES (Advanced Encryption Standard), the processes of SubBytes, ShiftRows, MixColumns, and AddRoundKey can be designated as _a1 , _a2 , _a3 , and _a4 , respectively. Alternatively, each process can be further subdivided.
Similarly, process B is divided into b ₁ , b ₂ , . . . , b _n which are executed in sequence.

Here, the design device 1 determines the position to insert the register according to the following algorithm.
Here, t(a _i ) means the delay in processing a _i (the processing time of a _i ).

In step S1, the critical path selection unit 11 selects the process with the greatest delay from among processes _a1 , _a2 , ..., _am and processes _b1 , _b2 , ..., _bn . If process _amax is selected, T = t( _amax ) becomes the critical path in the hardware implementation of the cryptographic process.

In step S2, the register insertion unit 12 judges whether t( _a1 )+t( _a2 )+...+t( _am ) is equal to or less than T. If the judgment is YES, the register insertion for process A is completed and the process proceeds to step S5. On the other hand, if the judgment is NO, the process proceeds to step S3.

In step S3, the register insertion unit 12 searches for i such that t( _a1 ) + t( _a2 ) + ... + t( _ai ) ≦ T and t( _a1 ) + t( _a2 ) + ... + t( _ai+1 ) > T, and inserts a register between process _ai and process _ai+1 to make the delay of processes _a1 to _ai between the registers less than or equal to the critical path T.

In step S4, the register insertion unit 12 replaces the processes a _i+1 to a _m after the register insertion in step S3 with a ₁ to a _m , and the process proceeds to step S2.

In step S5, the register insertion unit 12 executes the same procedure as steps S2 to S4 for process B as in process A, and completes register insertion for process B.
If there are three or more parallel processes, steps S2 to S4 are repeatedly executed.

Note that this algorithm is just one example, and any procedure can be used to insert the minimum number of registers that satisfies the condition that all delays due to processing between registers are below the critical path.

According to this embodiment, the design device 1 selects the process with the longest delay as the critical path from among multiple processes executed in sequence, and adjusts the delay of the process between the registers to be equal to or less than the critical path by inserting registers between any of the multiple processes. At this time, the design device 1 inserts the minimum number of registers that satisfy the condition that all delays of the processes between the registers are equal to or less than the critical path.
Therefore, the design apparatus 1 can eliminate the critical path and suppress an increase in the number of clocks due to an increase in the number of registers, thereby improving throughput by increasing the operating frequency of the arithmetic circuit.

As a result, this embodiment can be applied to hardware implementation of various encryption processes, such as stream encryption and Feistel-type common key encryption. In particular, in stream encryption intended for application to Beyond 5G/6G, a state update function that combines the AES round function and an ARX structure (AND, OR, XOR) is adopted to improve the throughput in software implementation. When multiple operations are executed sequentially in each path of the state update function, the throughput of the hardware implementation is also improved by inserting a minimum number of registers.
The application of this embodiment is not limited to encryption processing.

In addition, when there are multiple processing procedures that can be performed in parallel, the design device 1 selects the processing procedure with the longest delay from all the processing procedures included in these multiple processing procedures as the critical path, and adjusts the processing delay between registers for each of the multiple processing procedures to be equal to or less than the critical path.
Therefore, the design apparatus 1 can minimize delays and improve throughput for all of a plurality of processing procedures that can be processed in parallel.

The above-mentioned embodiment can improve throughput in hardware implementations of cryptographic processing, which can contribute to the achievement of Goal 9 of the United Nations-led Sustainable Development Goals (SDGs), which is to "build resilient infrastructure, promote sustainable industrialization and foster innovation."

Although the embodiments of the present invention have been described above, the present invention is not limited to the above-described embodiments. Furthermore, the effects described in the above-described embodiments are merely a list of the most favorable effects resulting from the present invention, and the effects of the present invention are not limited to those described in the embodiments.

The design method using the design device 1 is realized by software. When realized by software, the programs that make up this software are installed in an information processing device (computer). These programs may be recorded on removable media such as CD-ROMs and distributed to users, or may be distributed by being downloaded to the user's computer via a network. Furthermore, these programs may be provided to the user's computer as a web service via a network without being downloaded.

REFERENCE SIGNS LIST 1 design device 10 control unit 11 critical path selection unit 12 register insertion unit 20 storage unit

Claims (6)

a critical path selection unit that selects, from among a plurality of processes that are executed sequentially, one process having the maximum delay as a critical path;
a register insertion unit that inserts a register between successive processes and adjusts a total delay due to one or more processes between the registers to be equal to or less than a delay of the critical path,
The register insertion unit is an apparatus for designing an arithmetic circuit that inserts a minimum number of registers that satisfies a condition that the total delay between all registers is equal to or less than the delay of the critical path. the critical path selection unit, when there are a plurality of processing procedures that can be executed in parallel, selects, as the critical path , one processing procedure having a maximum delay among all processing procedures included in the plurality of processing procedures;
2 . The design device according to claim 1 , wherein the register insertion unit adjusts a total delay due to one or more processes between registers for each of the plurality of processing procedures to be equal to or less than a delay of the critical path. 3. The design device according to claim 1, wherein the register insertion unit selects, from the plurality of processes, a maximum number of processes whose total delay from the beginning of the execution order does not exceed a delay of the critical path , and repeatedly inserts a register immediately after the maximum number of processes. A register is provided between successive processes ,
The registers are provided in a minimum number of arithmetic circuits that satisfy the condition that the critical path is one of multiple processes that are executed sequentially and that the total delay due to one or more processes between the registers is all less than the delay of the critical path. a critical path selection step of selecting, as a critical path, one process having the maximum delay among a plurality of processes executed sequentially;
a register insertion step of inserting a register between successive processes and adjusting a total delay due to one or more processes between the registers to be equal to or less than the delay of the critical path,
A method for designing an arithmetic circuit, comprising inserting a minimum number of registers that satisfies a condition that the total delay between all registers is equal to or less than the delay of the critical path, in the register insertion step. A design program for causing a computer to function as a design device according to any one of claims 1 to 3.

Images