Method and system for mounting circuit design on reconfigurable device

A system for generating a mapping of a circuit design onto a plurality of processing elements of a reconfigurable device for implementing the circuit design in the device by configuration data,

• wherein the device includes a plurality of processing elements and a routing matrix for connecting the plurality of processing elements and is reconfigured by changing functions of respective processing elements in the plurality of processing elements and/or changing at least some connections of the routing matrix,
• the plurality of processing elements are divided into a plurality of groups, processing elements included within each group are connected in a range of a first delay by a first-level routing matrix included in the routing matrix, and processing elements included in different groups are connected with a different delay to the first delay via a second-level routing matrix included in the routing matrix,
• the circuit design includes a data flow graph in which functions to be implemented in the device are expressed as a plurality of functional blocks that are capable of being implemented in processing elements out of the plurality of processing elements and connections between the plurality of functional blocks, the plurality of functional blocks including a plurality of types of functional block, and the plurality of processing elements including a plurality of types of processing element that configurable respectively correspond to restricted types of functional block out of the plurality of types of functional block, and
• the apparatus that generates the mapping of the circuit design onto the plurality of processing elements by carrying out an iterative algorithm that minimizes a cost function based on hardware information that includes definition data for the plurality of processing elements included in respective groups and definition data for the routing matrix, the cost function including an item that minimizes usage of the second-level routing matrix, the apparatus including:
• a functional unit that provisionally assigns the plurality of functional blocks to processing elements out of the plurality of processing elements divided into the plurality of groups, and includes a function that assigns the plurality of functional blocks with priority given to a type of processing element with a low number of elements included in the plurality of processing elements out of the plurality of types of processing element, and when doing so, assigns a plurality of functional blocks that can be assigned to a plurality of processing elements of a first type randomly to the plurality of processing elements of the first type;
• and
• a functional unit that changes assignments of the plurality of functional blocks to the plurality of processing elements using the iterative algorithm, and includes a function that finds a value of the cost function based on a route that connects a plurality of assigned processing elements that have been respectively assigned the plurality of functional blocks.

A method of generating configuration data for reconfiguring a reconfigurable device,

• wherein the device includes a plurality of processing elements and a routing matrix for connecting the plurality of processing elements and is reconfigured by changing functions of respective processing elements in the plurality of processing elements and/or changing at least some connections of the routing matrix,
• the plurality of processing elements are divided into a plurality of groups, processing elements included in each group are connected in a range of a first delay by a first-level routing matrix included in the routing matrix, and processing elements included in different groups are connected with a different delay to the first delay via a second-level routing matrix included in the routing matrix, and
• the method comprises:
• preparing hardware information on a computer accessible database, the hardware information including definition data for the plurality of processing elements included in respective groups and definition data for the routing matrix;
• and
• mapping a circuit design onto the plurality of processing elements for implementing the circuit design in the device by the configuration data, by having the computer carry out an iterative algorithm that minimizes a cost function,
• wherein the cost function includes an item that minimizes usage of the second-level routing matrix, the circuit design includes a data flow graph in which functions to be implemented in the device are expressed as a plurality of functional blocks that are capable of being implemented in processing elements out of the plurality of processing elements and connections between the plurality of functional blocks, and the plurality of processing elements include a plurality of types of processing element configurable respectively correspond to restricted types of functional block out of the plurality of types of functional block, and
• the step of mapping includes:
• provisionally assigning the plurality of functional blocks to processing elements out of the plurality of processing elements divided into the plurality of groups;
• and
• changing assignments of the plurality of functional blocks to the plurality of processing elements using the iterative algorithm, the step of changing the assignments including finding a value of the cost function based on a route that connects a plurality of assigned processing elements that have been respectively assigned the plurality of functional blocks wherein the plurality of functional blocks include a plurality of types of functional block, and
• wherein the step of provisionally assigning further includes assigning the plurality of functional blocks with priority given to a type of processing element with a low number of elements included in the plurality of processing elements out of the plurality of types of processing element, and when doing so, assigning a plurality of functional blocks that can be assigned to a plurality of processing elements of a first type randomly to processing elements out of the plurality of processing elements of the first type.

A method that includes mapping a circuit design onto a reconfigurable device by using a computer,

• wherein the device includes a plurality of processing elements and a routing matrix for connecting the plurality of processing elements and is reconfigured by changing functions of respective processing elements in the plurality of processing elements and/or changing at least some connections of the routing matrix,
• the plurality of processing elements are divided into a plurality of groups, processing elements included in each group are connected in a range of a first delay by a first-level routing matrix included in the routing matrix, and processing elements included in different groups are connected with a different delay to the first delay via a second-level routing matrix included in the routing matrix,
• the circuit design includes a data flow graph in which functions to be implemented in the device are expressed as a plurality of functional blocks that are capable of being implemented in processing elements out of the plurality of processing elements and connections between the plurality of functional blocks, and the plurality of processing elements include a plurality of types of processing element configurable respectively correspond to restricted types of functional block out of the plurality of types of functional block and
• the mapping comprising:
• provisionally assigning the plurality of functional blocks to processing elements out of the plurality of processing elements divided into the plurality of groups;
• and
• changing assignments of the functional blocks to the plurality of processing elements using an iterative algorithm that minimizes a cost function by using a computer;
• wherein the cost function includes an item that minimizes usage of the second-level routing matrix, the changing assignments includes finding a value of the cost function based on a route that connects a plurality of assigned processing elements that have been respectively assigned the plurality of functional blocks wherein the plurality of functional blocks include a plurality of types of functional block, and the provisionally assigning further includes assigning the plurality of functional blocks with priority given to a type of processing element with a low number of elements included in the plurality of processing elements out of the plurality of types of processing element, and when doing so, assigning a plurality of functional blocks that can be assigned to a plurality of processing elements of a first type randomly to processing elements out of the plurality of processing elements of the first type.

A program product for causing a computer to generate configuration data for configuring a reconfigurable device,

• wherein the device includes a plurality of processing elements and a routing matrix for connecting the plurality of processing elements and is reconfigured by changing functions of respective processing elements in the plurality of processing elements and/or changing at least some connections of the routing matrix,
• the plurality of processing elements are divided into a plurality of groups, processing elements included in each group are connected in a range of a first delay by a first-level routing matrix included in the routing matrix, and processing elements included in different groups are connected with a different delay to the first delay via a second-level routing matrix included in the routing matrix, and
• the program product comprises:
• preparing hardware information on a computer accessible data base, the hardware information including definition data for the plurality of processing elements included in the respective groups and definition data for the routing matrix;
• and
• mapping a circuit design onto the plurality of processing elements for implementing the circuit design in the device by the configuration data, by having the computer carry out an iterative algorithm that minimizes a cost function,
• wherein the cost function includes an item that minimizes usage of the second-level routing matrix, the circuit design includes a data flow graph in which functions to be implemented in the device are expressed as a plurality of functional blocks that are capable of being implemented in processing elements out of the plurality of processing elements and connections between the plurality of functional blocks, and the plurality of processing elements include a plurality of types of processing element configurable respectively correspond to restricted types of functional block out of the plurality of types of functional block, and
• the mapping includes:
• provisionally assigning the plurality of functional blocks to processing elements out of the plurality of processing elements divided into the plurality of groups;
• and
• changing assignments of the plurality of functional blocks to the plurality of processing elements using the iterative algorithm, the step of changing the assignments including finding a value of the cost function based on a route that connects a plurality of assigned processing elements that have been respectively assigned the plurality of functional blocks wherein the plurality of functional blocks include a plurality of types of functional block, and
• wherein the step of provisionally assigning further includes assigning the plurality of functional blocks with priority given to a type of processing element with a low number of elements included in the plurality of processing elements out of the plurality of types of processing element, and when doing so, assigning a plurality of functional blocks that can be assigned to a plurality of processing elements of a first type randomly to processing elements out of the plurality of processing elements of the first type.

A program product for causing a computer to map a circuit design onto a reconfigurable device,

• wherein the device includes a plurality of processing elements and a routing matrix for connecting the plurality of processing elements and is reconfigured by changing functions of respective processing elements in the plurality of processing elements and/or changing at least some connections of the routing matrix,
• the plurality of processing elements are divided into a plurality of groups, processing elements included in each group are connected in a range of a first delay by a first-level routing matrix included in the routing matrix, and processing elements included in different groups are connected with a different delay to the first delay via a second-level routing matrix included in the routing matrix,
• the circuit design includes a data flow graph in which functions to be implemented in the device are expressed as a plurality of functional blocks that are capable of being implemented in processing elements out of the plurality of processing elements and connections between the plurality of functional blocks, and the plurality of processing elements include a plurality of types of processing element configurable respectively correspond to restricted types of functional block out of the plurality of types of functional block, and
• the program product comprising:
• provisionally assigning the plurality of functional blocks to processing elements out of the plurality of processing elements divided into the plurality of groups;
• and
• changing assignments of the functional blocks to the plurality of processing elements using an iterative algorithm that minimizes a cost function,
• wherein the cost function includes an item that minimizes usage of the second-level routing matrix, and the changing assignments includes finding a value of the cost function based on a route that connects a plurality of assigned processing elements that have been respectively assigned the plurality of functional blocks wherein the plurality of functional blocks include a plurality of types of functional block, and the provisionally assigning further includes assigning the plurality of functional blocks with priority given to a type of processing element with a low number of elements included in the plurality of processing elements out of the plurality of types of processing element, and when doing so, assigning a plurality of functional blocks that can be assigned to a plurality of processing elements of a first type randomly to processing elements out of the plurality of processing elements of the first type.