Method and apparatus for instruction scheduling using software pipelining

Patent metadata

Field	Value
Publication number	US-9354850-B2
Application number	US-201414507272-A
Country	US
Kind code	B2
Filing date	Oct 6, 2014
Priority date	Oct 7, 2013
Publication date	May 31, 2016
Grant date	May 31, 2016

Abstract

A method for scheduling loop processing of a reconfigurable processor includes generating a dependence graph of instructions for the loop processing; mapping a first register file of the reconfigurable processor on an arrow indicating inter-iteration dependence on the dependence graph; and searching for schedules of the instructions based on the mapping result.

First claim

What is claimed is:

1. A method for scheduling processing of a loop in a reconfigurable processor, the method comprising:
generating a dependence graph of instructions for the processing of the loop;
detecting an arrow of the dependence graph indicating inter-iteration dependence on the dependence graph;
mapping a register file of the reconfigurable processor on the detected arrow of the dependence graph indicating the inter-iteration dependence on the dependence graph; and
searching for schedules of the instructions for the processing of the loop based on the mapping.

2. The method of claim 1 , wherein the register file is a central register file connected to at least one load/store unit of the reconfigurable processor implementing a memory access instruction.

3. The method of claim 1 , wherein the mapping of the register file comprises:
adding a node between a function-unit-type (FU-type) node when the arrow is directed towards the FU-type node; and
allocating the register file to the node.

4. The method of claim 1 , wherein the mapping of the register file comprises allocating the register file to a register-file-type (RF-type) node when the arrow is directed towards the RF-type node.

5. The method of claim 1 , further comprising adding a node onto the dependence graph, wherein the node resets a control signal for storing a context of the reconfigurable processor in a predetermined cycle.

6. The method of claim 5 , wherein the predetermined cycle is an integer-multiple cycle of an initiation interval between iterations of the loop.

7. The method of claim 5 , further comprising adding another node onto the dependence graph, wherein the another node temporarily stops the processing of the loop when the control signal is reset or an end condition of the loop is satisfied.

8. A non-transitory computer-readable recording medium having recorded thereon a computer program for executing the method of claim 1 .

9. A scheduling apparatus comprising:
a memory that stores instructions for processing of a loop; and
a modulo scheduler that generates a dependence graph of the instructions for the processing of the loop and schedules operations of a reconfigurable processor that processes the loop,
wherein the modulo scheduler detects an arrow of the dependence graph indicating inter-iteration dependence on the dependence graph, maps a register file of the reconfigurable processor on the detected arrow of the dependence graph indicating the inter-iteration dependence on the dependence graph, and searches for schedules of the instructions for the processing of the loop based on the mapping.

10. The scheduling apparatus of claim 9 , wherein the modulo scheduler adds a node between a function-unit-type (FU-type) node when the arrow is directed towards the FU-type node in order to allocate the register file to the node, and allocates the register file to a register-file-type (RF-type) node when the arrow is directed towards the RF-type node.

11. The scheduling apparatus of claim 9 , wherein the modulo scheduler adds a node onto the dependence graph that resets a control signal to store a context while processing the loop, and adds another node onto the dependence graph that temporarily stops the processing of the loop according to an input of the control signal.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Ahn Min-Wook
• Kim Won-Sub
• Jin Tai-Song
• Lee Seung-Won
• Lee Jin-Seok

Classifications

• G06F9/3012

  Organisation of register space, e.g. banked or distributed register file · CPC title

• G06F8/443 Primary

  Optimisation · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/4452 Primary

  Software pipelining · CPC title