JP2002149395A - Asynchronous computing device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable calculation of a plurality of steps without giving an instruction for calculation from a client for each step. In an asynchronous circuit for controlling data transfer timing by a handshake signal line, a task register (200), a handshake generator (300), and an asynchronous finite state machine (400) are provided.
00 is turned on when a calculation request is received, the handshake generation unit 300 is allowed to repeatedly take a handshake with the asynchronous finite state machine 400, and is turned off when a stop request is received, and the handshake generation unit 30 is turned off.
The asynchronous finite state machine 400 has a function of prohibiting the operation of 0, and performs a plurality of steps of calculation using the data received from the client 100 as an argument, and sends a stop request to stop the task register 200 in the final step of the calculation. Have a function.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an asynchronous computer for performing digital computation by an asynchronous circuit.

[0002]

2. Description of the Related Art Finite State Machine (FSM)
achine) is a computational mechanism that has a finite number of states and defines the rules for state transitions on it. This finite state machine is one of the most basic computing mechanisms by hardware, and is an indispensable element in configuring today's digital computing devices.

Usually, when realizing a finite state machine,
The state is held by a flip-flop, and the state transition is executed by a logic circuit (combinational logic), and a synchronous configuration method is adopted in which the state transition timing is uniformly controlled by a global clock.

However, in recent years, in a synchronous circuit on the premise of the existence of a global clock, it has become difficult to distribute clock signals to flip-flops in the circuit at the same timing as the process becomes finer. Asynchronous circuits that do not use a global clock are receiving attention.

In this asynchronous circuit, a request signal and an acknowledge signal are exchanged between a data sender and a data receiver, instead of using a global clock to determine the timing of writing to the flip-flop. Controls reception timing. That is, the sender notifies the receiver of the data by sending a request signal, and the receiver returns data reception to the sender by an acknowledge signal to perform data transfer control based on handshaking.

Asynchronous finite state machine (AFSM; Asynch)
Ronous Finite State Machine) is configured by adding a handshake circuit for performing timing control to a synchronous finite state machine.

FIG. 8 is a diagram showing an example of a circuit configuration of a conventional asynchronous finite state machine. As shown, the asynchronous finite state machine has a state register 10, a delay element 20, and combinational logic 30,40. The handshake circuit must be added based on the data transfer dependency, but the next state output of the finite state machine is usually determined by the current state output. And a handshake. When the asynchronous finite state machine has an input and an output, it is necessary to add a circuit for performing a handshake for each of the input source and the output destination.

[0008]

However, in an asynchronous finite state machine having inputs and outputs, in order to perform one-step calculation, it is basically necessary to take a handshake with all input and output destinations once. . Therefore, if the input data does not arrive or the processing of the output destination is delayed, the execution cannot proceed.

However, since it is possible to construct a selector for selecting a partner of the handshake, it is possible to control whether or not to output data based on the internal state of the asynchronous finite state machine using the selector.

However, in the asynchronous finite state machine alone,
It is not possible to realize an asynchronous computing device capable of performing flexible execution control, such as performing a multi-step calculation by one-shot input and stopping the computation based on the state of the asynchronous finite state machine.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problem, and an object of the present invention is to provide an asynchronous computing device capable of performing a plurality of steps of calculation without giving an instruction to perform a calculation from a client for each step. Aim.

[0012]

According to the present invention, there is provided an asynchronous circuit for controlling data transfer timing by a handshake signal line comprising a pair of a request signal line and an acknowledge signal line.
A task register, a handshake generation unit, and an asynchronous finite state machine, wherein the task register is turned on when receiving a calculation request from an external client, and returns an acknowledgment to the client,
A function that allows the handshake generation unit to repeatedly take a handshake with the asynchronous finite state machine,
When receiving a stop request from the asynchronous finite state machine, the asynchronous finite state machine returns an acknowledgment to the stop request to the asynchronous finite state machine and is turned off, and accepts the next calculation request by withdrawing the acknowledgment to the client. The asynchronous finite state machine performs a multi-step calculation using the data received from the client as an argument while taking a handshake with the handshake generator every time. In the last step of the calculation, a function of sending the stop request for stopping the task register is provided.

[0013]

1 is a schematic diagram showing an asynchronous computer according to the present invention, FIG. 2 is a detailed diagram showing the asynchronous computer shown in FIG. 1, and FIG. 3 is a block diagram of the asynchronous computer shown in FIG. FIG. 3 is a diagram illustrating a register. As shown in the figure, the asynchronous computer receives an instruction to perform a calculation, that is, a calculation request (request) from an external client 100, and the asynchronous computer receives a task register 200, a handshake generator 30
It has a zero and asynchronous finite state machine 400, which has combinational logic 410, a state register 420, a handshake switcher 430, and a delay element 440. As the asynchronous finite state machine 400, a 4-bit asynchronous finite state machine having no output (that is, capable of having a maximum of 2 ⁴ = 16 states) is used. In addition, the asynchronous calculation device includes a request signal line (gen_req signal line, fsm_req signal line, fin_req signal line) and an acknowledge signal line (gen_ack signal line, fsm_
This is an asynchronous circuit that controls data transfer timing by a handshake signal line composed of a pair of an ack signal line and a fin_ack signal line.

The task register 200 stores a muller (Mu).
ller) C elements g1 and g2, and the handshake generation unit 300 includes a gate (switch) g3 and a Muller C element g4. And the Muller C element g1,
g2 and g4 are basic logic elements of the asynchronous circuit, and the Muller C elements g1, g2 and g4 output a low level signal when all inputs are at a low level (false value), and all inputs are at a high level ( If it is (true value), a high-level signal is output; otherwise, the value of the immediately preceding output signal is output. FIG. 4 shows the truth values of the Muller C elements g1, g2, and g4.
Shown in In FIG. 4, the low level is represented by “0” and the high level is represented by “1”. The Muller C elements g1, g
In FIG. 4, a white circle is attached to one of the inputs, which means an inverter, which indicates that the polarity of the input is inverted with respect to the definition in FIG. And the Muller C elements g1, g2,
g4 functions to wait for a signal transition in the same direction in the asynchronous circuit, that is, a change from a low level to a high level and a change from a high level to a low level.
Further, the gate g3 is a logic element for connecting the fbk signal which is the latest feedback loop signal to the Muller C element g4.

The delay element 440 calculates the next state through the combinational logic 410 from the output of the current state of the state register 420 in the asynchronous finite state machine 400,
When the value is written back to the state register 420, a sufficient time is provided so that writing is performed after the value of the next state is stabilized.

The handshake switch 430 has selectors g5 and g6.
The selector g6 is a logic element that branches the handshake signal based on the value (level) of the l signal, and the selector g6 selects a handshake signal to be passed based on the value of the sel signal. The selectors g5 and g6 are s
When the el signal is at a low level, the connection on the side where "0" is written is valid. When the sel signal is at a high level, the connection on the side where "1" is written is valid. The handshake switch 430 simply turns the request signal back in the handshake switch 430 when the sel signal is at a low level, but issues a stop request to the task register 200 when the sel signal is at a high level. To form a handshake circuit that responds.

The status register 420 includes four registers R0, R1, R2, and R3.
Each of 1, R2, and R3 can hold information of one bit (a total of four bits). Also, the registers R0, R
Each of R1, R2 and R3 is configured as shown in FIG. 3 and has four data latches D1, D2, D3 and D4. Here, the data latches D1, D2, D3, D4
Is a storage element that maintains the immediately preceding output value when the signal at the G terminal as an input terminal is at a low level, and outputs the value of the signal at the D terminal as an input terminal when the signal at the G terminal is at a high level. Data latches D1, D2, D3, D
The truth value of 4 is shown in FIG. In FIG. 3, the symbol “<<” written at the branch point of the signal line indicates the register R0,
The ti1 signal or ti2 signal which is the timing signal of R1, R2, R3 passes and the to1 signal or to2
The timing constraint indicates that the value of the signal at the G terminal of the data latches D1, D2, D3, and D4 must be determined sufficiently before changing the value of the input signal to which the signal is connected.

FIG. 6 shows the relationship between the signal at the ti1 terminal, the signal at the ti2 terminal, and data transfer between the registers R0, R1, R2, and R3. In FIG. 6, the data latch D1,
The X mark on D2, D3, and D4 indicates that the signal at the G terminal is at a low level and that the data is held, and those without the X mark indicate that the signal at the G terminal is at a high level.
Indicates that data is being passed through. Also,
“Ti1 = L” indicates that the signal at the ti1 terminal is at a low level, and “ti1 = H” indicates that the signal at the ti1 terminal is at a high level.

The operation of this embodiment will be described below.

In advance, the output signals of the Muller C elements g1, g2, and g4 are initialized to low level, and the registers R0,
The output signals of R1, R2, and R3 are initialized to a high level or a low level, and the entire circuit is assumed to be more stable by its output. At this time, since the ena signal, which is the input signal of the gate g3, is kept at a low level, the output signal of the Muller C element g4 remains at a low level (the Muller C element g4 is stopped), and the handshake is generated. The unit 300 does not change the fsm_req signal. That is, if the ena signal is kept at the low level, the handshake generator 300 stops, and the asynchronous finite state machine 400 stops.

In this state, the client 100
_Req signal to high level to set the task register 200
, The task signal, which is the output signal of the Muller C element g1, changes to a high level because the output signal of the Muller C element g2 is at a low level. That is, the task register 200 stores the external client 100
It has a function to be turned on when a calculation request is received from. In this case, the gen_ack signal goes high and the ena signal goes high, opening the feedback loop fbk and allowing the stopped handshake generator 300 to operate. That is, when the ena signal which is an input signal of the gate g3 is set to a high level, the handshake generation unit 300 becomes operable. That is, the task register 200 is
When 0 is turned on, an acknowledgment is returned to the client 100 and the handshake generator 3
00 has the function of allowing the asynchronous finite state machine 400 to repeatedly take a handshake.

The operable handshake generator 3
00 sets the fsm_req signal of the Muller C element g4 to a high level to start the operation of the asynchronous finite state machine 400. This fsm_req signal is applied to each register R0,
Through the ti1-to1 of R1, R2, and R3, the values held by the registers R0, R1, R2, and R3 are sent to the combination logic 410 from the do terminal that is the output terminal. The combination logic 410 calculates the value of the next state based on the value of the current state and the argument gen_data signal passed from the client 100, and converts the argument gen_data signal into each of the registers R0, R
1. Return to di terminal which is the input terminal of R2 and R3. At the same time, the combinational logic 410 determines whether to issue a stop request to stop the task register 200 or not.
The signal is determined and sent to the handshake switch 430.

If the calculation is to be continued at the next step, the low-level se
1 signal is output. In this case, the request signal (transition from low level to high level) passed through the status register 420 is looped back inside the handshake switch 430 and returned to the status register 420 as an acknowledge signal. The acknowledge signal returned to the status register 420 is ti2 of each of the registers R0, R1, R2, and R3.
-To2, and registers R0, R1, R2, R3
, The value of the new signal is taken in from the di terminal, the fsm_ack signal is set to a high level, and a response to the first request signal is returned to the handshake generator 300. Up to this point, half of one step has been completed.

When the fsm_ack signal becomes high level, the output of the Muller C element g4 is inverted, and the fsm_req
The signal goes low. This transition also passes through ti1-to1 of each of the registers R0, R1, R2, and R3 of the state register 200, and the handshake switch 4
Then, the data is looped back at 30, and the registers R0, R1, R2,
The fsm_ack signal is set to low level through ti2-to2 of R3, and when returning ti2 to low level, di
The value of the next state signal taken from the terminal is held. Up to this point, one-step operation is completed.

When the fsm_ack signal goes low, the output signal of the Muller C element g4 is inverted and goes high again, so that the above operation is repeated.
The computations in the asynchronous finite state machine 400 can continue for multiple steps. That is, the asynchronous finite state machine 400 has a function of performing a multi-step calculation using the data received from the client 100 as an argument while performing handshaking with the handshake generation unit 300 each time.

In order for the handshake switcher 430 to operate correctly, the value of the sel signal is changed during a period when the request signal passing through the status register 420 changes from low level to high level and changes from high level to low level. Must be kept constant. However, the change in the value of the signal at the do terminal is a trigger in FIG. 6B in which the signal at the ti1 terminal becomes high level, so that the delay of the delay element 440 is determined so that the value of the sel signal is determined before the request signal. Is sufficiently large to satisfy this condition.

When it is desired to stop the operation of the asynchronous finite state machine 400 in a certain state, sel
The combinational logic 410 is configured so that the signal goes high. That is, the asynchronous finite state machine 400 has a function of sending a stop request to stop the task register 200 in the final step of the calculation.

When the sel signal goes high, f
The in_req signal goes to a high level. In this case, the output signal of the Muller C element g2 can transition to a high level, and the fin_ack signal goes to a high level. At the same time, if the gen-req signal is at a low level, the Muller C element g1 can also transition to a low level. In this case, the task register 200 task
The signal goes low. That is, task register 2
When a stop request is received from the asynchronous finite state machine 400, the 00 has a function of returning an acknowledgment to the asynchronous finite state machine 400 to the stop request and turning off.

As described above, ta of the task register 200 is
When the sk signal goes low, the gen-ack signal goes low.

When the fin_ack signal transitions to the high level, fs is transmitted via the asynchronous finite state machine 400 to fs_ack.
The m_ack signal transitions to a high level. At this time, f
If the bk signal is determined to be at the high level, the output signal of the gate g3 is at the low level regardless of the value of the ena signal. This assumption can be satisfied by making the delay of the fbk signal relatively small. Therefore, the output signal of the Muller C element g4 can also be inverted to low level, and fsm_req is independent of the state of the task register 200.
The signal fin_req signal safely transitions to low level.

When the fin_req signal goes low, as long as the output signal of the Muller C element g1 is low, the output signal of the Muller C element g2 can be inverted to low level, and the fin_ack signal can transition to low level. . Conversely, if the gen_req signal is delayed from lowering to the low level and the output signal of the Muller C element g1 remains at the high level, this transition is waited at the Muller C element g2.

When the fin_ack signal goes low, fsm_ac is passed through the asynchronous finite state machine 400.
The k signal also goes low. At this time, if the ena signal has already been lowered to the low level and the output signal of the gate g3 has been determined to be at the low level, the Muller C element g4 waits until the next ena signal becomes high.
The handshake generator 300 stops, and consequently the asynchronous finite state machine 400 also stops. This assumption is made from the Muller C element g1 through the ena signal line to the Muller C element g4.
Can be satisfied by making the delay of the signal from the Muller C element g1 to the Muller C element g2 to the Muller C element g4 through the asynchronous finite state machine 400 sufficiently smaller than that of the acknowledge signal. .

That is, when the task register 200 is turned off, the client 1
By canceling the acknowledgment to 00, it has a function of permitting the reception of the next calculation request from the client 100 and a function of prohibiting the operation of the handshake generation unit 300.

When the handshake generator 300 stops, the Muller C element g1, the gate g3, and the Muller C element g4 are in the same state as the initial state, and the output of the handshake circuit is stable at a low level. ing. Therefore, the execution of the asynchronous finite state machine 400 can be resumed by setting the gen_req signal to the high level again.

FIG. 7 shows the STG (Signal Transition) of the task register 200 in order to show that the operation is correct even when the order of the handshake with the client 100 and the handshake with the asynchronous finite state machine 400 are different. Graph).
This STG is a graph showing the dependency of signal transition in the asynchronous circuit. In FIG. 7, for example, fin_r
eq + represents a signal transition from a low level to a high level of the fin_req signal, and fin_req− represents fi.
The signal transition from the high level to the low level of the n_req signal is shown. The arrows between the signal transitions indicate the dependence of the signal transitions, and indicate that the signal transitions become possible (fire possible) when all of the input source signal transitions are established.

The tokens (black circles) written above the arrows in the figure indicate the condition that this condition is satisfied. For example, g
Since there is a token in the arrow input to en_req +, gen_req + can transition (fire). On the other hand, looking at the arrow input to task +, gen_r
This signal transition is not yet transitionable (firing) because there is no token in the one from eq +.

The fact that a signal transition has actually occurred is modeled as removing all tokens from the input arrow and placing a new token over all arrows pointing to the output. Therefore, the transition of gen_req + (ignition)
After that, task + can transition (fire), and task +
After the + transition (firing), fin_req + and gen_r
eq- can transition (fire).

It is known that the STG does not deadlock if there is at least one token in every closed circuit (closed loop formed by the arrow and the signal transition node), but this condition is satisfied. I have. Also, since at most one token exists in every closed circuit, signal transition cannot be overtaken. From FIG. 7, it can be seen that the result is the same irrespective of the order even when the waiting is correctly performed and there are a plurality of signal transitions that can be shifted (ignited).

As described above, in the asynchronous computer shown in FIGS. 1 to 3, a plurality of steps of calculation can be performed without giving an instruction to perform the calculation from the client for each step, and a flexible asynchronous computer is provided. Can be configured. Further, the configuration of an asynchronous system utilizing the advantages of hardware, such as spatially developing a target process by combining a plurality of finite state machines and driving each of the processes as needed, becomes easy.

In this embodiment, the registers R0 and R0 of the state register 420 of the asynchronous finite state machine 400 are used.
The number (bit number) of 1, R2, and R3 is set to 4 and there is no output to the outside.
The number of 0, R1, R2, and R3 can be arbitrarily changed, and can be applied to various asynchronous finite state machines, such as having an external output.

Each of the registers R0, R1, R2, R3 of the status register 420 used in this embodiment is composed of four stages of data latches D1, D2, D3, D4, but the number of stages is three or more. , The configuration of the handshake circuit needs to be changed, but can be replaced and used.

In this embodiment, the client 1
00 is assumed to be one, but calculation requests from a plurality of clients can be competed and received by using an arbiter, or calculation requests from a plurality of clients can be received in a queue by using a Muller C element. .

Further, in the present embodiment, a single computer having the task register 200, the handshake generator 300, and the asynchronous finite state machine 400 is used, but a plurality of asynchronous computers according to the present invention are used. Connect them in a pipeline, insert an arithmetic circuit between the connections, branch multiple pipelines,
It is also possible to connect and use in various topologies such as merging.

[0044]

In the asynchronous computing device according to the present invention, a plurality of steps of calculation can be performed without giving an instruction to perform the calculation from the client for each step.

[Brief description of the drawings]

FIG. 1 is a schematic diagram showing an asynchronous computing device according to the present invention.

FIG. 2 is a detailed diagram illustrating the asynchronous computer illustrated in FIG. 1;

FIG. 3 is a diagram illustrating registers of the asynchronous calculation device illustrated in FIG. 2;

FIG. 4 is a diagram showing a truth value of a Muller C element.

FIG. 5 is a diagram showing a truth value of a data latch.

FIG. 6 is a diagram showing a relationship of data transfer between registers.

FIG. 7 is a diagram showing an STG of a task register.

FIG. 8 is a diagram showing an example of a circuit configuration of a conventional asynchronous finite state machine.

[Explanation of symbols]

 100 client 200 task register 300 handshake generator 400 asynchronous finite state machine

 ──────────────────────────────────────────────────続 き Continuation of the front page (72) Inventor Hiroshi Nakata 2-3-1 Otemachi, Chiyoda-ku, Tokyo F-term in Nippon Telegraph and Telephone Corporation 5B022 CA01

Claims (1)

[Claims] 1. An asynchronous circuit for controlling data transfer timing by a handshake signal line comprising a pair of a request signal line and an acknowledge signal line, comprising: a task register, a handshake generator, and an asynchronous finite state machine. The task register is turned on when a calculation request is received from an external client, returns an acknowledgment to the client, and permits the handshake generation unit to repeatedly take a handshake with the asynchronous finite state machine. Upon receiving a stop request from the asynchronous finite state machine, the function returns an acknowledgment to the asynchronous finite state machine to the stop request and turns off, and withdraws the acknowledgment to the client to accept the next calculation request. And allow Has a function to prohibit the operation of the handshake generation unit, the asynchronous finite state machines,
It has a function of performing a plurality of steps of calculation using the data received from the client as an argument while taking a handshake each time with the handshake generation unit, and sending the stop request to stop the task register in the final step of the calculation. Asynchronous computing device.