Patent ID: 11928473
Assignee: BEIJING TSINGMICRO INTELLIGENT TECHNOLOGY CO., LTD.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 5:
6. An instruction scheduling system for a reconfigurable array processor, comprising:
a hardware resource checking unit, configured to determine whether a fan-out of a vertex in a data flow graph is less than an actual interconnection number of a processing unit in a reconfigurable array, wherein the vertex in the data flow graph is an instruction vertex;
a retiming processing unit, configured to:
establish a corresponding relationship between the vertex in the data flow graph and a correlation operator of the processing unit in the reconfigurable array, and form a retiming inequality set, and
introduce a register required for labeling the correlation operator to a directed edge in the data flow graph according to a solution of the inequality set, acquire a retiming value of each vertex in the data flow graph, to allow each vertex to be transformed into a model of the processing unit;

an instruction ranking unit, configured to arrange instructions corresponding to the instruction vertexes in such a manner that retiming values of the instruction vertexes are in ascending order, and acquire transmission time and scheduling order of the instructions;
a resource checking unit, configured to:
fold the data flow graph according to an initial iteration period of the data flow graph, and in response to the number of instruction vertexes of the data flow graph corresponding to instructions to be transmitted in parallel at a first time being greater than the number of connected units of the processing unit in the reconfigurable array, place an instruction with a smallest dependent number to an instruction vertex corresponding to a second time after the first time, wherein a dependent number is the number of instructions previously transmitted, and
in response to determining that the number of instruction vertexes of the data flow graph corresponding to instructions to be transmitted in parallel at each time is smaller than or equal to the number of connected units of the processing unit in the reconfigurable array, and in response to a transmission time interval between one or more instruction vertexes and a previous dependent instruction vertex thereof being greater than a preset time interval, insert a register before the one or more instruction vertexes and the previous dependent instruction vertex thereof and acquire a current data flow graph, wherein the number of registers corresponds to an iteration period and a time interval; and

an instruction distributing unit, configured to acquire a common maximum subset of the current data flow graph and the reconfigurable array by a maximum clique algorithm according to the current data flow graph, and distribute the instructions corresponding to the instruction vertexes in response to a maximum subset number being equal to the number of the vertexes in the data flow graph.