CN107018201B - A method for dynamically migrating instructions using critical path information in data flow architecture - Google Patents

Abstract

The invention discloses a method for dynamically migrating instructions by using critical path information in a data flow architecture. The method is applied in a data flow architecture. The data flow architecture has N nodes and an instruction migration control unit. The first direction and the second direction perpendicular to each other are arranged in an array form, and each node has M instruction slots, a migration target address calculation unit, a critical path detection unit, a migration target address broadcast unit, and a free instruction slot detection unit , the instruction slot is used to store instructions. This method uses the critical path information detected by each node in real time to guide the dynamic migration of instructions, so that the instruction mapping of the data flow architecture can dynamically adapt to changes in load, resource usage, and network congestion. , thereby improving the running speed and computing efficiency of the data flow architecture.

Description

A method for dynamically migrating instructions using critical path information in data flow architecture

technical field

The invention relates to instruction migration in a data flow architecture, in particular to a method for dynamically migrating instructions using critical path information in a data flow architecture.

Background technique

With the development of computer architecture, domain-specific computer architecture has become the main development trend. When oriented to a specific application, the special-purpose structure uses the application characteristics to optimize the structure accordingly, so as to better exert the computing performance of the hardware. In the field of high-performance computing, data flow computing is an important branch of domain-specific computing structures, and data flow computing has shown good performance and applicability. The data flow architecture usually includes several or more than a dozen computing nodes, and each computing node is a core with strong computing capability but weak control capability and low complexity. The execution process of the data flow architecture is: through the static mapping of the compiler, the instruction mapping required for a calculation is allocated to different nodes, and then each node performs operations on different data groups. When the compiler statically maps, it will consider the resource distribution of the node, the instruction calculation distance, the communication delay, and the interdependent instructions to map to the closest execution node or the same execution node as much as possible. At the same time, it also needs to consider the concurrency independent of each other. Instructions should be mapped to different execution units as much as possible. Execution mapping plays a major role in improving the performance of data flow computing.

Although the static instruction mapping takes into account the various factors listed above, it cannot know and adapt to the dynamic changes that occur during real-time execution, including network congestion and the impact of instruction dependency chains on data delays, etc. In the process, adjustments are made according to the actual situation. Once the dynamic execution conditions change, adjustments and responses cannot be made in real time, thus limiting the possibility of further optimization of the performance of the architecture.

Contents of the invention

The present invention provides a method for dynamically migrating instructions using critical path information in a data flow architecture, so that the instruction mapping of the data flow architecture can dynamically adapt to changes in load and resource usage, thereby improving the operating speed and computing efficiency of the data flow architecture .

In order to achieve the above object, the present invention provides a method for dynamically migrating instructions using critical path information in a data flow architecture, the method is applied to a data flow architecture, and the data flow architecture has N nodes and an instruction migration A control unit, N nodes are arranged in an array along the first direction and the second direction perpendicular to each other, each node has M instruction slots, a migration target address calculation unit, a critical path detection unit, and a migration target address broadcast unit And a free instruction slot detection unit, the instruction slot is used to store instructions, the method includes the following steps:

S1: The critical path detection unit in each node sequentially detects the instructions stored in the instruction slot to confirm whether the instructions stored therein are critical paths;

S2: When a node P1 confirms that one of the instructions I is a critical path, the migration target address calculation unit in the node P1 performs calculations to obtain the node P2 to which the instruction I is to be migrated, and sends an idle query request to the node P2;

S3: After the node P2 receives the idle query request, the idle instruction slot detection unit in the node P2 starts to detect whether there is an instruction slot capable of storing instructions from the node P1, and if it is "yes", it sends a confirmation to the node P1 Migrate the command and execute step 4, if it is "none", return to step S2 to recalculate the next node to migrate to;

S4: The node P1 sends a migration request to the instruction migration control unit, and the instruction migration control unit accepts the migration request and arranges the migration request to the end of a migration queue;

S5: The instruction migration control unit detects the migration request arranged at the head of the migration queue in real time, and sends a confirmation migration instruction to the node P1 corresponding to the migration request;

S6: After the node P1 receives the confirmation migration instruction, the migration target address broadcast unit in the node P1 sends a pause operand transmission instruction to the upstream node and the downstream node of the instruction I;

S7: The upstream node and downstream node of the instruction I suspend the transmission of the operand and send a confirmation feedback message to the node P1;

S8: The node P1 packs the relevant information of the migration instruction I to the node P2;

S9: After instruction I migration is completed, node P2 sends a migration completion message to node P1;

S10: The migration target address broadcast unit in the node P1 sends the location information of the node P2 where the instruction I is currently located to the original upstream node and downstream node of the instruction I;

S11: The original upstream node and downstream node of the instruction I accept the location information of the node P2 where the instruction I is currently located and send a change confirmation message to the node P1;

S12: Node P1 sends an instruction migration completion message to the instruction migration control unit;

S13: The node P1 sends a message to the corresponding instruction slot in the original upstream node of the instruction I, to instruct to resend the data for operation.

In an embodiment of the present invention, in step S1, the conditions for judging that an instruction is a critical path are the following (1)-(4):

(1) The difference between the dependency chains of the two source operands corresponding to the instruction exceeds a preset value L1;

(2) The spatial distance between the instruction and the downstream node exceeds a preset value L2;

(3) The number of downstream commands corresponding to the command exceeds a preset value D;

(4) The time that the instruction waits to be transmitted in the node exceeds a preset value T;

When the instruction satisfies the above (1)&(2) or (1)&(3) or (1)&(4) or (1)&(2)&(3)&(4), it is judged that the instruction is a critical path .

In an embodiment of the present invention, in step S2, the migration target address calculation unit preferentially migrates the instruction I according to the following strategies (1) and/or (2):

(1) If N is greater than a set value N1, the number of hops for each migration is greater than one hop; if N is less than a set value N2, only one hop is migrated each time, where N2≤N1;

(2) Migrate to the direction where the distance difference between the instruction I and the source operand is large along the first direction and the second direction;

(3) If the distance between the node where instruction I is located and its downstream node is L3, then the migration distance of instruction I is or

In an embodiment of the present invention, N=16, and the 16 nodes in the data flow architecture are arranged in a 4×4 array.

In an embodiment of the present invention, the maximum number of instructions stored in each node is 128.

The method for dynamic migration of instructions using critical path information in the data flow architecture provided by the present invention uses the critical path information detected by each node in real time to guide the dynamic migration of instructions, so that the instruction mapping of the data flow architecture can dynamically adapt to loads and resources Changes in usage and network congestion levels, thereby improving the operational speed and computational efficiency of the dataflow architecture.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is a schematic diagram with 16 nodes in the data flow architecture;

FIG. 2 is a hardware schematic diagram of a method for dynamically migrating instructions using critical path information in the data flow architecture provided by the present invention;

Figure 3 is a schematic diagram of the structure of the node.

Description of reference signs: PE0-PE15-node; 1-instruction migration control unit; X-first direction; Y-second direction; 2-instruction slot; 3-migration target address calculation unit; 4-critical path detection unit; 5- Migration target address broadcast unit; 6- Free instruction slot detection unit; 228- Instruction.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

In the data flow architecture, the critical path represents those instructions that wait for a long time to issue and cannot switch data contexts in a timely manner. In the traditional control flow architecture, the cause of the critical path can be judged by a single factor, for example, if the instruction waits for a long time in the launch queue, then this instruction can be considered as the critical path. However, in the data flow architecture, due to the reason of instruction mapping, it cannot be judged by such a single factor. As shown in Figure 1, there are 16 nodes in the data flow architecture. PE0~PE15 are nodes. The two source operands of an instruction in node PE15 come from node PE0 and node PE8 respectively. The two source operands need to pass through The distance between 4 hops and 6 hops reaches node PE15. Although the distance between nodes PE0, node PE8 and downstream node PE15 is relatively far from the distance point of view, on the one hand, the distance between the two source operands and node PE15 (respectively 4 hops and 6 hops) are not much different; on the other hand, if the distance between the downstream node that depends on the result of this instruction and PE15 is not too far, then it is difficult to say that this instruction must be a critical path. It can be seen from this that in the data flow architecture, multiple factors need to be considered comprehensively to determine whether an instruction is a critical path.

The present invention provides a method for dynamically migrating instructions using critical path information in a data flow architecture. The method is applied to a data flow architecture. Figure 2 shows the dynamic migration of instructions using critical path information in the data flow architecture provided by the present invention. The hardware schematic diagram of the method, as shown in Figure 2, has 16 nodes PE0-PE15 and an instruction migration control unit 1 in the data flow architecture, and the 16 nodes are arranged as 4 along the first direction X and the second direction Y perpendicular to each other. In the form of an array of ×4, the coordinates of each node in the first direction X and the second direction Y are also marked in FIG. 2 to facilitate the calculation of the number of hops during migration. In other embodiments, the number of nodes in the data flow architecture can be adjusted according to actual conditions, for example, 64 or other numbers, and the present invention is not limited to 16. Fig. 3 is a schematic structural diagram of a node, as shown in Fig. 3, each node in this embodiment has an instruction slot 2, a migration target address calculation unit 3, a critical path detection unit 4, a migration target address broadcast unit 5 and a The idle instruction slot detection unit 6, the instruction slot 2 is used to store instructions, in this embodiment, the number of instructions stored in the instruction slot 2 is 128, but it is not limited thereto, it can be increased or decreased according to actual needs, the method includes The following steps:

S1: the critical path detection unit 4 in each node sequentially detects the instructions stored in the instruction slot 2 to confirm whether the instructions stored therein are critical paths;

Wherein, in step S1, the conditions for judging that an instruction is a critical path are the following (1)-(4):

(1) The difference between the dependency chains of the two source operands corresponding to the instruction exceeds a preset value L1, for example, when there are two source operands, the path between the two source operands to the node where the instruction is located The difference is greater than the preset value L1;

(2) The spatial distance between the instruction and the downstream node exceeds a preset value L2;

(3) The number of downstream commands corresponding to the command exceeds a preset value D;

(4) The time that the instruction waits to be transmitted in the node exceeds a preset value T;

When the instruction satisfies the above (1)&(2) or (1)&(3) or (1)&(4) or (1)&(2)&(3)&(4), it is judged that the instruction is a critical path , that is, (1) is the main factor for judging whether an instruction is a critical path, and (2), (3) and (4) are auxiliary factors. It should be noted that L1, L2, D and T can all be set by themselves.

S2: When a node P1 confirms that one of the instructions I is a critical path, the migration target address calculation unit 3 in the node P1 performs calculations to obtain the node P2 to which the instruction I is to be migrated, and sends an idle query request to the node P2;

In step S2, the migration target address calculation unit preferentially migrates the instruction I according to the following strategies (1) and/or (2):

(1) If N is greater than a set value N1, the number of hops for each migration is greater than one hop; if N is less than a set value N2, only one hop is migrated each time, where N2≤N1;

That is to say, when the number of nodes in the data flow architecture is small, the number of hops for each migration can be set less, for example, one hop. As the number of nodes in the data flow architecture increases, the number of hops for each migration More can be set, the above N1, N2 can be set by the user according to actual needs.

(2) Migrate to the direction where the distance difference between the instruction I and the source operand is large along the first direction and the second direction;

(3) If the distance between the node where instruction I is located and its downstream node is L3, then the migration distance of instruction I is or Here L3 is the distance along the first direction or along the second direction, and They are rounding down or rounding up for L3 respectively, that is, if L3 is not an integer, is the largest integer smaller than L3, Then it is the smallest integer greater than L3.

S3: After the node P2 receives the idle query request, the idle instruction slot detection unit 6 in the node P2 starts to detect whether there is an instruction slot capable of storing instructions from the node P1, and if it is "yes", it sends a confirmation migration to the node P1 Command and execute step 4, if it is "none", return to step S2 to recalculate the next node to migrate to;

S4: The node P1 sends a migration request to the instruction migration control unit 1, and the instruction migration control unit 1 accepts the migration request and arranges the migration request to the end of a migration queue;

S5: The instruction migration control unit 1 detects the migration request arranged at the head of the migration queue in real time, and sends a confirmation migration instruction to the node P1 corresponding to the migration request;

What needs to be explained here is that when a migration request is queued to the end of the migration queue, it usually takes a while before it can be processed. During the waiting time, it needs to process other Migration request, for the convenience of explanation, the situation when the migration request is processed after a waiting period is directly described here.

S6: After the node P1 receives the confirmation migration instruction, the migration target address broadcast unit 3 in the node P1 sends a pause operand transmission instruction to the upstream node and the downstream node of the instruction I;

S7: The upstream node and downstream node of the instruction I suspend the transmission of the operand and send a confirmation feedback message to the node P1;

S8: The node P1 packs the relevant information of the migration instruction I to the node P2;

S9: After instruction I migration is completed, node P2 sends a migration completion message to node P1;

S10: The migration target address broadcast unit 5 in the node P1 sends the location information of the node P2 where the instruction I is currently located to the original upstream node and downstream node of the instruction I;

S11: The original upstream node and downstream node of the instruction I accept the location information of the node P2 where the instruction I is currently located and send a change confirmation message to the node P1;

S12: Node P1 sends an instruction migration completion message to the instruction migration control unit 1;

S13: The node P1 sends a message to the corresponding instruction slot in the original upstream node of the instruction I, to instruct to resend the data for operation.

The following uses Figure 2 as an example for illustration:

S1: The two source operands of instruction 228 in node PE15 in Figure 2 are from nodes PE1 and PE13 respectively, and the corresponding downstream node is PE10, and instruction 228 satisfies the condition (1) for judging that the instruction is a critical path in the above step S1 ~(4), therefore, the critical path detection unit 4 in the node PE15 detects that the instruction 228 is a critical path;

S2: The migration target address calculation unit 3 in the node PE15 performs calculations, wherein the number of migration target address calculation units 3 for each migration is one hop, thus calculating that the node to be migrated to by the instruction 228 is the node PE11 or PE14, The Y direction priority strategy is adopted here, therefore, the migration target address calculation unit 3 determines that the node PE11 is the target node to be migrated to and sends an idle inquiry request to the node PE11;

S3: The idle instruction slot detection unit 6 in the node PE11 starts to detect whether there is an instruction slot capable of storing instructions from the node PE11, after detection, the idle instruction slot detection unit 6 in the node PE11 does not have an instruction slot capable of storing instructions from the node PE15 Therefore, it is necessary to return to the previous step to recalculate the node to be migrated to, and calculate again through the migration target address calculation unit 3 to determine that the next node to be migrated to is node PE14 and send an idle query request to node PE14, After the node PE14 receives the idle query request, the idle instruction slot detection unit 6 in the node PE14 begins to detect whether there is an instruction slot capable of storing instructions from the node PE15, after detection, the idle instruction slot detection unit 6 in the node PE14 has the ability to an instruction slot storing instructions from node PE15;

S4: The node P15 sends a migration request to the instruction migration control unit 1, and the instruction migration control unit 1 accepts the migration request and arranges the migration request to the end of a migration queue;

S5: The instruction migration control unit 1 detects the migration request arranged at the head of the migration queue in real time, and when other migration requests in front of the migration request are sequentially processed so that the migration request is arranged at the head of the migration queue, the instruction migration control unit 1 Send a confirmation migration command to the node PE15;

S6: After the node PE15 receives the confirmation migration instruction, the migration target address broadcast unit 3 in the node PE15 sends a pause operand transmission instruction to the upstream nodes PE1, PE13 and downstream node PE10 of the instruction 228;

S7: The upstream nodes PE1, PE13 and the downstream node PE10 of the instruction 228 suspend the transmission of the operand and send a confirmation feedback message to the node PE15;

S8: Node PE15 packs information about migration instruction 228 to node PE14;

S9: After instruction 228 migration is completed, node PE14 sends a migration completion message to node PE15;

S10: The migration target address broadcast unit 5 in the node PE14 sends the location information of the node PE14 where the instruction 228 is currently located to the original upstream nodes PE1, PE13 and downstream node PE10 of the instruction 228;

S11: The original upstream nodes PE1, PE13 and downstream node PE10 of the instruction 228 accept the location information of the node PE14 where the instruction 228 is currently located and send a change confirmation message to the node PE14;

S12: The node PE15 sends an instruction migration completion message to the instruction migration control unit 1;

S13: The node PE14 sends a message to the corresponding instruction slots in the original upstream nodes PE1 and PE13 of the instruction 228 to instruct to resend data for operation.

The method for dynamic migration of instructions using critical path information in the data flow architecture provided by the present invention uses the critical path information detected by each node in real time to guide the dynamic migration of instructions, so that the instruction mapping of the data flow architecture can dynamically adapt to loads and resources Changes in usage and network congestion levels, thereby improving the operational speed and computational efficiency of the dataflow architecture.

Those skilled in the art can understand that the accompanying drawing is only a schematic diagram of an embodiment, and the modules or processes in the accompanying drawing are not necessarily necessary for implementing the present invention.

Those of ordinary skill in the art can understand that: the modules in the device in the embodiment may be distributed in the device in the embodiment according to the description in the embodiment, or may be changed and located in one or more devices different from the embodiment. The modules in the above embodiments can be combined into one module, and can also be further divided into multiple sub-modules.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some of the technical features; these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (4)

1. A method for dynamic migration of instructions by using critical path information in a data flow architecture is characterized in that the method is applied to the data flow architecture, the data flow architecture is provided with N nodes and an instruction migration control unit, the N nodes are arranged in an array form along a first direction and a second direction which are mutually perpendicular, each node is provided with M instruction slots, a migration target address calculation unit, a critical path detection unit, a migration target address broadcast unit and a free instruction slot detection unit, and the instruction slots are used for storing instructions and comprise the following steps:

s1: the critical path detection unit in each node sequentially detects the instructions stored in the instruction slot to determine whether the instructions stored in the instruction slot are critical paths; the conditions for determining that the instruction is a critical path are the following (1) to (4):

(1) the difference between the dependency chains of the two corresponding source operands of the instruction exceeds a preset value L1;

(2) the spatial distance between the command and the downstream node exceeds a preset value L2;

(3) the number of the downstream instructions corresponding to the instructions exceeds a preset value D;

(4) the time for waiting to be transmitted in the node is instructed to exceed a preset value T;

when the instruction meets the above (1) & (2) or (1) & (3) or (1) & (4) or (1) & (2) & (3) & (4), judging the instruction as a critical path;

s2: when a node P1 confirms that a command I is a critical path, the migration target address calculation unit in the node P1 calculates to obtain the node P2 to which the command I is to be migrated and sends an idle inquiry request to the node P2;

s3: after the node P2 receives the idle inquiry request, the idle instruction slot detection unit in the node P2 starts to detect whether there is an instruction slot capable of storing an instruction from the node P1, if yes, sends a migration confirmation instruction to the node P1 and executes step S4, and if no, returns to step S2 to recalculate the next migrated node;

s4: the node P1 sends a migration request to the instruction migration control unit, and the instruction migration control unit receives the migration request and arranges the migration request to the tail of a migration queue;

s5: the instruction migration control unit detects the migration request arranged at the head of the migration queue in real time and sends a migration confirmation instruction to the node P1 corresponding to the migration request;

s6: after the node P1 receives the confirmed migration instruction, a migration target address broadcasting unit in the node P1 sends a pause operand transmission instruction to an upstream node and a downstream node of the instruction I;

s7: the upstream and downstream nodes of instruction I suspend operand transfers and send acknowledgement feedback messages to node P1;

s8: the node P1 packs the related information of the migration instruction I to the node P2;

s9: after the instruction I completes the migration, the node P2 sends a migration completion message to the node P1;

s10: a migration target address broadcasting unit in the node P1 sends the position information of the node P2 where the instruction I is currently located to the original upstream node and the original downstream node of the instruction I;

s11: the original upstream node and the original downstream node of the instruction I receive the position information of the node P2 where the instruction I is currently located and send a change confirmation message to the node P1;

s12: the node P1 sends an instruction migration completion message to the instruction migration control unit;

s13: node P1 sends a message to the corresponding instruction slot in the node upstream from instruction I to indicate that the data is to be resent for operation.

2. The method for dynamically migrating instructions according to the data flow architecture of claim 1, wherein in step S2, the migration target address calculation unit preferentially migrates the instruction I according to the following policies (1) and/or (2):

(1) if N is larger than a set value N1, the hop count of each time of migration is larger than one hop, if N is smaller than a set value N2, only one hop of migration is performed each time, wherein N2 is not more than N1;

(2) migrating to a direction between the instruction I and a source operand along a direction with a large distance difference between a first direction and a second direction;

(3) if the distance between the node where instruction I is located and the node downstream of the node is L3, the migration distance of instruction I isOr

3. The method of claim 1, wherein N is 16, and 16 nodes in the data flow architecture are arranged in a 4 × 4 array.

4. The method of claim 3, wherein the maximum number of instructions stored in each node is 128.